감사의 말씀: 본 연구는 Emanuele Viterbo 및 Dankrad Feist와의 공동 연구이며, ESP Grant FY24-1745 "DAS에서 2D Reed-Solomon 코드 개선"의 지원을 받았습니다.
이 글에서는 블록 순환(BC) 코드가 이더리움 PeerDAS 프로토콜에서 1차원(1D) 및 2차원(2D) 리드-솔로몬(RS) 코드의 대안으로 사용될 수 있는 방법을 설명합니다. 효율적인 인코딩 및 복원 방법을 제시합니다.
BC 코드용 알고리즘은 동일한 구현 프레임워크 내에서 개발되었습니다.
각각의 1D RS 알고리즘. 제안된 인코딩 알고리즘은 또한 다음을 허용합니다.
KZG 약정 제도의 원활한 통합. 본 연구에서는 이를 평가하고 비교합니다.
BC 코드의 성능을 코드율, 정지율 및 포함된 로컬 코드 크기 측면에서 1D 및 2D RS 코드와 비교했습니다. 이 글의 더 자세한 내용은 SVF2026 에서 확인할 수 있습니다.
순환 코드 차단
SVD2025 에서는 PeerDAS에서 현재 사용되는 1D RS 코드와 추후 도입 예정인 2D RS 코드 모두에 대한 실행 가능한 대안으로 블록 순환(BC) 코드가 도입되었습니다. 2D RS 코드와 유사하게, BC 코드는 여러 개의 로컬 코드를 포함하며, 각 로컬 코드는 [(n_0,k_0),D] [ ( n 0 , k 0 ) , D ] 스택형 1D RS 코드로 설계될 수 있습니다. 스택형 1D RS 코드란 코드워드가 D개의 가로 행(각 행의 길이는 n_0 n 0 ) 과 k_0 개의 세로 행(정보 심볼을 나타냄)에 쌓인 [ n_0D , k_0D] [ n 0 D , k 0 D ] RS 코드 를 의미 합니다 . 따라서 KZG 방식과 호환됩니다. BC 코드는 1D 또는 2D RS 코드로는 불가능한 특정 동작 모드(전송률, 정지율 및 로컬 코드 크기)를 달성하는 것으로 밝혀졌습니다.
2D RS 코드에서는 심볼들이 2차원 정사각형 격자에 배열되어 있으며, 각 행 또는 열에 속하는 심볼들은 선형 제약 조건에 의해 구속됩니다. BC 코드의 경우, 심볼들은 원형으로 배열되고, 이 원은 여러 개의 겹치는 호로 나뉩니다. 각 호는 시계 방향을 기준으로 왼쪽과 오른쪽에 인접한 두 개의 겹치는 호를 가집니다. 각 호에 속하는 심볼들은 일련의 선형 제약 조건을 따릅니다. 다음 하위 절에서 더 구체적인 설명을 제시합니다.
BC 코드에 대한 설명
그림 1: 블록 순환 부호의 모식도. 이 예시에서는 녹색 배경의 정보 기호와 분홍색 배경 영역의 패리티 기호가 결합되어 최종 배열을 이룬다. 닫힌 곡선 안의 기호 그룹은 로컬 부호를 나타낸다.
그림 1에 제시된 n= 16 개의 기호 로 구성된 예를 생각해 보겠습니다. 원에는 각각 n₀=6 개의 기호 를 포함 하는 μ₄= 4 개의 호 (그중 두 개는 닫힌 곡선으로 표시됨)가 있으며, 각 호는 원 위에 등간격으로 배치되어 있습니다. 제약 조건이 없는 기호는 총 k=8개 이며 , d₁ , ... , d₈ 로 표시 됩니다 . 각 로컬 코드는 k₀=4 개의 제약 조건 이 없는 기호를 포함합니다. 나머지 기호는 특정 선형 제약 조건에 따라 생성됩니다. 각 호에는 ρ=n₀-k₀=2 = n₀ - k₀ = 2 개의 중복 기호 가 추가되어 해당 호에 해당하는 로컬 코드가 1D RS 코드가 됩니다. 예를 들어, 단일 아크에 대응하는 심볼 벡터 (d_1,d_2,p_{11},p_{12},d_3,d_4) ( d 1 , d 2 , p 11 , p 12 , d 3 , d 4 ) 는 1차원 RS 코드의 코드워드를 형성합니다. 따라서 아크는 고유한 로컬 코드와 식별되며, 아크와 로컬 코드를 상호 교환적으로 사용할 수 있습니다. 두 개의 인접한 로컬 코드가 겹치는 영역에는 정확히 ω=2ω = 2 개의 심볼이 존재하므로 ω 를 겹침 폭이라고 합니다. 제약 없는 모든 심볼은 서로 다른 두 로컬 코드의 일부이며, 이를 겹침 인자라고 하고 λ 로 나타냅니다. 현재 구성에서는 λ =2λ = 2 입니다 . SVD2025 에 제시된 일반적인 BC 코드에서는 λ 값이 더 큰 구성 도 가능합니다. ω 와 ρ 와 같은 다른 매개변수도 적절하게 수정할 수 있습니다. SVD2025 에서는 λ =2,3 ( λ = 2,3 ) 인 BC 코드에서 복구 가능한 총 소거 횟수가 λρλρ 임을 보여 줍니다 . 허용 가능한 총 소거 횟수와 n/ n 의 비율을 정지율이라고 하며 SS 로 나타냅니다. 아래 표에는 BC 코드의 조정 가능한 매개변수에 사용 되는 표기법을 요약했습니다.
BC 코드의 매개변수
| 표기법 | 매개변수의 의미 |
|---|---|
| μ | 지역 코드 수 |
| λ | 중복 계수 (모든 기호 는 λ 로컬 코드의 일부입니다) |
| ρ | 로컬 코드의 중복 기호 수 |
| \omega ω | 겹침 폭(인접한 두 로컬 코드가 겹치는 기호의 수) |
| [n_0,k_0]=[\lambda\omega+\rho,\lambda\omega] [ n 0 , k 0 ] = [ λ Ω + ρ , λ Ω ] | 로컬 코드 블록 길이 및 차원 |
| [n,k]=[\mu(\omega+\rho),\mu\omega] [ n , k ] = [ μ ( Ω + ρ ) , μ Ω ] | 글로벌 코드 블록 길이 및 차원 |
| R=\frac{\omega}{\omega+\rho} R = Ω Ω + ρ | 비율 |
| S=\frac{\lambda\rho}{\mu(\omega+\rho)} S = λ ρ μ ( Ω + ρ ) | 정지율 |
| R_0=\frac{\lambda\omega}{\lambda\omega+\rho} R 0 = 람 Ω λ Ω + ρ | 지역 코드 요금 |
| S_0=\frac{\rho}{\lambda\omega+\rho} S 0 = ρ λ Ω + ρ | 로컬 코드 중지율 |
스택형 BC 코드
1차원 RS 코드를 스택형 1차원 RS 코드로 변환하는 절차는 WZ2024 에 자세히 설명되어 있습니다. 이 절차는 BC 코드에도 동일하게 적용 가능한데, 그 이유는 (a) BC 코드의 각 로컬 코드가 1차원 RS 코드이고, (b) 각 로컬 코드에 대해 신중하게 선택된 평가점 집합을 사용하는 일련의 로컬 1차원 RS 인코더를 통해 인코딩을 수행할 수 있기 때문입니다. 예제를 통해 스택형 BC 코드 의 인코딩 절차를 설명하겠습니다.
인코딩 알고리즘
그림 2. 인코딩 전 블롭 0의 구조.
그림 3. BC 코드에서 확장된(인코딩된) 블롭 0의 구조.
그림 2와 3에 나타낸 예시를 통해 인코딩 방식을 설명합니다. 여기서 중첩 계수 λ = 2 이고 , 로컬 코드의 개수는 μ = 4 입니다 . 스태킹 파라미터 D=64 를 선택 하면 , 하나의 블롭은 k=128 개의 셀 에 배열된 8192개의 유한 체 심볼로 구성됩니다. 각 블롭은 Fq^{(D \times k)}=Fq^{(64 \times 128)} F ( D × k ) q = F ( 64 × 128 ) q 의 원소이고, 각 셀은 Fq^{64} F 64 q 에 속합니다 . 유한체 q 의 크기에 대한 요구 사항은 곧 설명하겠습니다. 먼저 Blob 0의 128 ×128개 셀을 μ=4μ = 4 개의 세그먼트 로 분할하고, 각 세그먼트는 ω=32μ = 32 개의 셀을 포함합니다. 이 네 개의 세그먼트는 각각 Segment(0,0), Segment(0,2), Segment ( 0,4 ) , Segment ( 0,2 ) , Segment ( 0,4 ) , Segment ( 0,6 ) 으로 인덱싱 됩니다 . 인코딩 과정 에서 , 연속된 두 세그먼트 사이에 중복 심볼을 포함하는 세그먼트를 생성하고 배치합니다(순환적으로 볼 때 Segment ( 0,6 ) 은 Segment ( 0,0 ) 에 인접한 것으로 간주 합니다 ). 결과적으로 생성된 8 ×8 세그먼트는 \text{Segment}(0,0 ) 부터 \ text { Segment }(0,7) 까지 인덱싱 되어 확장 된 ( 인코딩된) 블롭을 구성합니다. 일반적으로 중복 세그먼트는 \rho ρ 개의 셀을 갖지만, 이 예에서는 전송률이 R = 0.5 로 선택되었으므로 \rho=\omega=32 ρ = ω = 32 입니다. 따라서 확장된 블롭의 각 세그먼트는 32× 32 개의 셀로 구성됩니다.
그림 2에는 128개의 세포 로 이루어진 블롭 0 이 표시되어 있습니다. 확장된 블롭의 구조를 예상하여 블롭 0 과 관련된 세포 의 두 번째 인덱스 는 0-31 , 64-95 , 128-159 , 192-223 으로 유지 됩니다 . 위의 인덱스를 가진 확장 블롭 0 내의 셀은 블롭 0과 동일한 데이터를 유지합니다. 확장 블롭 0 에서 32-63 , 96-127 , 160-191 , 224-255 로 인덱싱 된 셀 은 인코딩 중에 중복 데이터 로 채워집니다.
우리는 다음 과 같은 조건을 만족하는 소수체 \mathbb{ H}_3 \subset \mathbb{H}_2 \subset \mathbb{H}_1 \subset \mathbb{H}_0 \subset \mathbb{F}_q^* H 3 ⊂ H 2 ⊂ H 1 ⊂ H 0 ⊂ F ∗ q 를 선택합니다. 여기서 \mathbb{H}_q^* F ∗ q 는 크기 제약 조건을 만족하는 \mathbb{F}_q^* F ∗ q 의 부분군들의 사슬입니다.
타원 곡선 bls12-381 과 관련된 소수 q q 는 2^{32} \mid (q-1) 2 32 ∣ ( q − 1 ) 를 만족하므로 위의 부분군 사슬을 찾는 데 적합하다는 것을 알 수 있습니다. 부분군 트리는 그림 4에 나와 있습니다. 다음으로, 확장된 블롭 0 0 이 어떻게 구성되는지 설명합니다.
이 코드는 0-3 으로 인덱싱된 4 개의 로컬 코드로 구성되며, 각 로컬 코드 를 하나씩 개별적으로 인코딩하는 방식으로 인코딩이 수행됩니다. 그림 3에서 각 로컬 코드를 구성하는 셀이 명확하게 표시되어 있습니다.
첫 번째 3\omega=96 3 ω = 96 셀 \text{Cells}(0,0\text{-}95) 셀 ( 0 , 0 - 95 ) 은 3\omega D = 96 \times 64=6144 3 ω D = 96 × 64 = 6144 유한 필드 기호로 구성되어 ([n_0=96,k_0=64],D=64) ( [ n 0 = 96 , k 0 = 64 ] , D = 64 ) 스택형 1D RS 코드워드를 형성합니다. 확장 된 블롭 의 각 셀 은 다음 과 같이 H₃ 의 코셋 과 연결 됩니다 .
\begin{aligned}\text{Cells}(0,0\text{-}31) &\Leftrightarrow \mathbb{H}_3, \beta^{64}\mathbb{H}_3, \beta^{32}\mathbb{H}_3, \ldots, \beta^{124}\mathbb{H}_3 \\\text{Cells}(0,64\text{-}95) &\Leftrightarrow \beta^{2}\mathbb{H}_3, \beta^{66}\mathbb{H}_3, \beta^{34}\mathbb{H}_3, \ldots, \beta^{126}\mathbb{H}_3 \\\text{Cells}(0,32\text{-}63) &\Leftrightarrow \beta\mathbb{H}_3, \beta^{65}\mathbb{H}_3, \beta^{33}\mathbb{H}_3, \ldots, \beta^{125}\mathbb{H}_3\end{aligned}세포 ( 0 , 0-31 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3 세포 ( 0 , 64-95 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3 세포 ( 0 , 32-63 ) ⇔ β H 3 , β 65 H 3 , β 33 H 3 , … , β 125 H 396개의 각 셀에서 f_0(X ) 는 해당 코셋 에서 평가되고, 평가 결과는 해당 셀의 내용이 됩니다. 이렇게 하여 로컬 코드 0 0 의 스택형 RS 코드워드가 생성됩니다. 다항식 f_0(X ) 는 확장 된 블롭 의 셀 ( 0,0-31 ) 과 셀 ( 0,32-63 ) 에서 의 평가 결과 가 블롭 내의 해당 값과 정확히 동일하도록 구성됩니다. 이는 데이터 값을 평가 결과로 취하고 이러한 데이터 값으로부터 다항식을 보간함으로써 달성됩니다.
로컬 코드 1, 2 , 3 에 대해서도 동일한 절차가 반복됩니다. 해당 다항식은 f_1(X), f_2(X) , f_2 ( X ) , f_3 ( X ) 로 표시 됩니다 . 각 로컬 코드 와 관련된 셀 f_i(X), i = 1 , 2 , 3 을 구성 하는 데 사용 된 블롭 데이터와 평가 지점으로 사용된 코셋은 아래에 나열되어 있습니다.
(a) 로컬 코드 1 1 : \text{Cells}(0,64\text{-}159) Cells ( 0 , 64 - 159 )
\begin{aligned}f_1(X) &\Leftrightarrow \text{Cells}(0,64\text{-}95) \text{ 및 } \text{Cells}(0,128\text{-}159) \text{ 블롭 } 0 \\\text{Cells}(0,64\text{-}95) &\Leftrightarrow \beta^2 \mathbb{H}_3, \beta^{66} \mathbb{H}_3, \beta^{34} \mathbb{H}_3, \ldots, \beta^{126} \mathbb{H}_3 \\\text{Cells}(0,96\text{-}127) &\Leftrightarrow \beta^3 \mathbb{H}_3, \beta^{67} \mathbb{H}_3, \beta^{35} \mathbb{H}_3, \ldots, \beta^{127} \mathbb{H}_3 \\\text{Cells}(0,128\text{-}159) &\Leftrightarrow \mathbb{H}_3, \beta^{64} \mathbb{H}_3, \beta^{32} \mathbb{H}_3, \ldots, \beta^{124} \mathbb{H}_3\end{aligned}f 1 ( X ) ⇔ 블롭 0 의 세포 ( 0 , 64-95 ) 및 세포 ( 0 , 128-159 ) 세포 ( 0 , 64-95 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3 세포 ( 0 , 96-127 ) ⇔ β 3 H 3 , β 67 H 3 , β 35 H 3 , … , β 127 H 3 세포 ( 0 , 128-159 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3(b) 로컬 코드 2 2 : \text{Cells}(0,128\text{-}223) Cells ( 0 , 128 - 223 )
\begin{aligned}f_2(X) &\Leftrightarrow \text{Cells}(0,64\text{-}95) \text{ 및 } \text{Cells}(0,128\text{-}159) \text{ of blob } 0 \\\text{Cells}(0,128\text{-}159) &\Leftrightarrow \mathbb{H}_3, \beta^{64} \mathbb{H}_3, \beta^{32} \mathbb{H}_3, \ldots, \beta^{124} \mathbb{H}_3 \\\text{Cells}(0,160\text{-}191) &\Leftrightarrow \beta \mathbb{H}_3, \beta^{65} \mathbb{H}_3, \beta^{33} \mathbb{H}_3, \ldots, \beta^{125} \mathbb{H}_3 \\\text{Cells}(0,192\text{-}223) &\Leftrightarrow \beta^2 \mathbb{H}_3, \beta^{66} \mathbb{H}_3, \beta^{34} \mathbb{H}_3, \ldots, \beta^{126} \mathbb{H}_3\end{aligned}f 2 ( X ) ⇔ 블롭 0 의 세포 ( 0 , 64-95 ) 및 세포 ( 0 , 128-159 ) 세포 ( 0 , 128-159 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3 세포 ( 0 , 160-191 ) ⇔ β H 3 , β 65 H 3 , β 33 H 3 , … , β 125 H 3 세포 ( 0 , 192-223 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3(c) 로컬 코드 3 3 : \text{Cells}(0,192\text{-}255) Cells ( 0 , 192 - 255 ) 및 \text{Cells}(0,0\text{-}31) Cells ( 0 , 0 - 31 )
\begin{aligned}f_3(X) &\Leftrightarrow \text{Cells}(0,64\text{-}95) \text{ 및 } \text{Cells}(0,128\text{-}159) \text{ 블롭 } 0 \\\text{Cells}(0,192\text{-}223) &\Leftrightarrow \beta^2 \mathbb{H}_3, \beta^{66} \mathbb{H}_3, \beta^{34} \mathbb{H}_3, \ldots, \beta^{126} \mathbb{H}_3 \\\text{Cells}(0,224\text{-}255) &\Leftrightarrow \beta^3 \mathbb{H}_3, \beta^{67} \mathbb{H}_3, \beta^{35} \mathbb{H}_3, \ldots, \beta^{127} \mathbb{H}_3 \\\text{Cells}(0,0\text{-}31) &\Leftrightarrow \mathbb{H}_3, \beta^{64} \mathbb{H}_3, \beta^{32} \mathbb{H}_3, \ldots, \beta^{124} \mathbb{H}_3\end{aligned}f 3 ( X ) ⇔ 블롭 0 의 세포 ( 0 , 64-95 ) 및 세포 ( 0 , 128-159 ) 세포 ( 0 , 192-223 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3 세포 ( 0 , 224-255 ) ⇔ β 3 H 3 , β 67 H 3 , β 35 H 3 , … , β 127 H 3 세포 ( 0 , 0-31 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3로컬 코드 3 3은 오른쪽 끝 셀의 데이터와 왼쪽 시작 셀의 데이터를 결합하는 방식으로 순환적으로 순환함을 알 수 있습니다. 이는 그림\ref{fig:bcexblob}에 나타나 있습니다. 인코딩은 체계적이며, 즉 블롭의 데이터는 확장된 블롭에서도 그대로 사용 가능합니다.
그림 2 BC 코드에 대한 부분군 트리. 여기서 \beta β는 \mathbb{H}_0 H 0 의 생성자입니다.
다음은 FFT를 사용하는 정확한 알고리즘입니다. 블롭 0을 나타내기 위해 {\bf u} \in \mathbb{F}_q^{64 \times 128} u ∈ F 64 × 128 q 를 사용하겠습니다 . 셀 \text{Cell}(0,\textsf{start}) Cell ( 0 , start )부터 \text{Cell}(0,\textsf{end}) Cell ( 0 , end )까지의 데이터를 나타내기 위해 {\bf u}[\textsf { start }\text{-}\textsf{end}] u [ start - end ] 를 사용 합니다 . 벡터화 된 형태 , 즉 2048× 2048 길이의 벡터로 표현되는 네 개의 (D\times \omega) = (64 \times 32) ( D × ω ) = ( 64 × 32 ) 블롭 데이터 배열을 정의하겠습니다.
