Lời cảm ơn: Đây là công trình hợp tác với Emanuele Viterbo và Dankrad Feist, được hỗ trợ bởi khoản tài trợ ESP Grant FY24-1745 có tiêu đề “Cải tiến mã Reed-Solomon 2D trong DAS”.
Trong bài viết này, chúng tôi mô tả cách mã khối tuần hoàn (BC) có thể được sử dụng như một giải pháp thay thế cho mã Reed-Solomon (RS) một chiều (1D) và hai chiều (2D) trong giao thức Ethereum PeerDAS. Chúng tôi trình bày phương pháp mã hóa và tái tạo hiệu quả.
các thuật toán cho mã BC, được phát triển trong cùng một khuôn khổ triển khai như
các thuật toán RS 1D tương ứng. Thuật toán mã hóa được đề xuất cũng cho phép một
Tích hợp một cách khéo léo chương trình cam kết của KZG. Chúng tôi đánh giá và so sánh.
Hiệu năng của mã BC xét về tốc độ mã, tốc độ dừng và kích thước của các mã cục bộ mà chúng chứa, so với cả mã RS 1D và 2D. Phiên bản dài hơn của bài đăng này có trong SVF2026 .
Mã lưu thông khối
Mã khối tuần hoàn (BC) được giới thiệu trong SVD2025 như một giải pháp thay thế khả thi cho cả mã RS 1D (hiện đang được sử dụng) và mã RS 2D (dự kiến sẽ được tích hợp sau này) trong PeerDAS. Tương tự như mã RS 2D, mã BC chứa nhiều mã cục bộ, và mỗi mã cục bộ có thể được thiết kế như một mã RS 1D xếp chồng [(n_0,k_0),D] [ ( n 0 , k 0 ) , D ] . Mã RS 1D xếp chồng ở đây có nghĩa là một mã RS [n_0D ,k_0D] [ n 0 D , k 0 D ] có các từ mã được xếp chồng lên nhau trong D hàng ngang (mỗi hàng có độ dài n_0 n 0 , và k_0 k 0 cột đại diện cho các ký hiệu thông tin). Do đó, nó tương thích với lược đồ KZG. Kết quả cho thấy mã BC đạt được một số chế độ hoạt động về tốc độ, tốc độ dừng và kích thước mã cục bộ mà cả mã RS 1D hoặc 2D đều không thể đạt được.
Trong mã RS 2D, các ký hiệu được sắp xếp trong một lưới vuông hai chiều và có các ràng buộc tuyến tính liên kết các ký hiệu thuộc mỗi hàng hoặc cột. Trong trường hợp mã BC, các ký hiệu được sắp xếp trên một vòng tròn và vòng tròn được chia thành nhiều cung tròn chồng chéo. Mỗi cung tròn có hai cung tròn chồng chéo liền kề, một bên trái và một bên phải, giả sử theo chiều kim đồng hồ. Các ký hiệu thuộc mỗi cung tròn đều phải tuân theo một tập hợp các ràng buộc tuyến tính. Chúng tôi sẽ trình bày mô tả cụ thể hơn trong phần tiếp theo.
Mô tả về Bộ luật BC
Hình 1: Minh họa mã vòng khối. Trong ví dụ này, các ký hiệu thông tin trên nền màu xanh lá cây được kết hợp với các ký hiệu chẵn lẻ trên vùng nền màu hồng, tạo nên cấu trúc cuối cùng. Các nhóm ký hiệu bên trong các đường cong khép kín biểu thị các mã cục bộ.
Hãy xem xét ví dụ gồm n= 16 ký hiệu như trong Hình 1. Có μ= 4 cung ( hai trong số đó được đánh dấu bằng đường cong khép kín), mỗi cung chứa n_0=6 ký hiệu , được phân bố đều trên vòng tròn. Có tổng cộng k= 8 ký hiệu không bị ràng buộc được ký hiệu là d_1, ... , d_8 . Mỗi mã cục bộ chứa k_0=4 ký hiệu không bị ràng buộc. Các ký hiệu còn lại được tạo ra tuân theo một số ràng buộc tuyến tính nhất định. Trong mỗi cung, ρ=n_0-k_0= 2 ký hiệu dư thừa được thêm vào sao cho mã cục bộ tương ứng với cung đó trở thành mã RS 1D. Ví dụ, vectơ các ký hiệu (d_1,d_2,p_{11},p_{12},d_3,d_4) ( d 1 , d 2 , p 11 , p 12 , d 3 , d 4 ) tương ứng với một cung duy nhất tạo thành một từ mã của mã RS 1D. Do đó, một cung được xác định duy nhất với một mã cục bộ, và chúng ta có thể viết cung và mã cục bộ thay thế cho nhau. Có chính xác \omega=2 ω = 2 ký hiệu tại vùng chồng lấp của hai mã cục bộ liền kề và do đó chúng ta gọi \omega ω là độ rộng chồng lấp. Mỗi ký hiệu không bị ràng buộc là một phần của hai mã cục bộ khác nhau và chúng ta gọi nó là hệ số chồng lấp, được ký hiệu là \lambda λ . Trong cách sắp xếp hiện tại, chúng ta có \lambda=2 λ = 2 . Trong mã BC tổng quát được trình bày trong SVD2025 , các cách sắp xếp với giá trị \lambda λ cao hơn là có thể. Các tham số khác như ω và ρ cũng có thể được điều chỉnh cho phù hợp. Trong SVD2025 , người ta chỉ ra rằng với mã BC có λ = 2,3 và λ = 2,3 , tổng số lần xóa có thể được khôi phục bởi mã BC được chứng minh là λρ . Tỷ lệ giữa tổng số lần xóa có thể chấp nhận được và n được gọi là tỷ lệ dừng và được ký hiệu là S/ S . Chúng tôi tóm tắt các ký hiệu được sử dụng cho các tham số có thể điều chỉnh của mã BC trong bảng dưới đây.
Các tham số của mã BC
| Ký hiệu | Ý nghĩa của tham số |
|---|---|
| \mu μ | Số lượng mã vùng địa phương |
| \lambda λ | Hệ số chồng chéo (Mỗi ký hiệu là một phần của mã cục bộ \lambda λ ) |
| \rho ρ | Số lượng ký hiệu dư thừa trong mã cục bộ |
| \omega ω | Độ rộng vùng chồng lấp (Số lượng ký hiệu mà hai mã vùng cục bộ liền kề chồng lấp lên nhau) |
| [n_0,k_0]=[\lambda\omega+\rho,\lambda\omega] [ n 0 , k 0 ] = [ λ ω + ρ , λ ω ] | Độ dài và kích thước khối mã cục bộ |
| [n,k]=[\mu(\omega+\rho),\mu\omega] [ n , k ] = [ μ ( ω + ρ ) , μ ω ] | Độ dài và kích thước khối mã toàn cầu |
| R=\frac{\omega}{\omega+\rho} R = ω ω + ρ | Tỷ lệ |
| S=\frac{\lambda\rho}{\mu(\omega+\rho)} S = λ ρ μ ( ω + ρ ) | Tỷ lệ dừng |
| R_0=\frac{\lambda\omega}{\lambda\omega+\rho} R 0 = λ ω λ ω + ρ | Cước phí mã vùng |
| S_0=\frac{\rho}{\lambda\omega+\rho} S 0 = ρ λ ω + ρ | Tỷ lệ dừng mã cục bộ |
Mã BC xếp chồng
Quy trình chuyển đổi mã RS 1D sang mã RS 1D xếp chồng được mô tả chi tiết trong WZ2024 . Quy trình chính xác này cũng áp dụng được cho mã BC vì (a) mỗi mã cục bộ trong mã BC là một mã RS 1D, (b) việc mã hóa có thể được thực hiện bằng một loạt các bộ mã hóa RS 1D cục bộ với tập hợp các điểm đánh giá được lựa chọn cẩn thận cho mỗi mã cục bộ. Chúng tôi sẽ mô tả quy trình mã hóa cho mã BC xếp chồng bằng một ví dụ.
Thuật toán mã hóa
Hình 2. Cấu trúc của khối dữ liệu 0 trước khi mã hóa.
Hình 3. Cấu trúc của khối dữ liệu mở rộng (được mã hóa) 0 trong mã BC.
Chúng tôi mô tả quá trình mã hóa bằng một ví dụ minh họa trong Hình 2 và 3. Ở đây, hệ số chồng chéo \lambda=2 λ = 2 và có \mu=4 μ = 4 mã cục bộ. Chúng tôi chọn tham số xếp chồng D=64 và một khối gồm 8192 ký hiệu trường hữu hạn được sắp xếp trong k=128 ô . Mỗi khối là một phần tử của \mathbb{F}_q^{(D \times k)}=\mathbb{F}_q^{(64 \times 128)} F ( D × k ) q = F ( 64 × 128 ) q , trong khi mỗi ô thuộc về \mathbb{F}_q^{64} F 64 q . Yêu cầu về kích thước của trường hữu hạn q sẽ được mô tả ngắn gọn sau đây. Đầu tiên, chúng ta chia 128 ô của Blob 0 thành μ = 4 phân đoạn , mỗi phân đoạn chứa ω = 32 ô . Bốn phân đoạn này được đánh số là \text{Segment}(0,0), \text{Segment}(0,2), \text{Segment}(0,4) , Segment ( 0,0 ) , Segment ( 0,2 ) , Segment ( 0,4 ) và \ text { Segment } ( 0,6 ) . Trong quá trình mã hóa, chúng ta sẽ tạo và đặt các phân đoạn chứa các ký hiệu dư thừa ở giữa hai phân đoạn liên tiếp ( \text{Segment}(0,6 ) được coi là liền kề với \text{Segment}(0,0) , xem xét chúng theo chu kỳ). Kết quả là 8 phân đoạn được đánh số từ \text{Segment}(0,0) Segment ( 0 , 0 ) đến \text{Segment}(0,7) Segment ( 0 , 7 ) cùng nhau tạo thành khối mở rộng (được mã hóa). Nói chung, các phân đoạn dư thừa sẽ có \rho ρ ô, nhưng trong ví dụ này, chúng ta có \rho=\omega=32 ρ = ω = 32 vì tỷ lệ được chọn là R=0,5 R = 0,5 . Do đó, mỗi phân đoạn của khối mở rộng bao gồm 32 32 ô.
Hình 2 thể hiện khối 0 với 128 ô . Dự đoán cấu trúc của khối mở rộng, chỉ số thứ hai của các ô liên kết với Khối 0 được giữ nguyên như sau: 0 - 31 , 64 - 95 , 128 - 159 , 192 - 223 . Các ô trong khối dữ liệu mở rộng 0 với các chỉ số nêu trên được giữ nguyên dữ liệu giống như khối dữ liệu 0. Các ô được đánh số là 32-63 , 96-127 , 160-191 , 224-255 trong khối dữ liệu mở rộng 0 sẽ được điền dữ liệu dư thừa trong quá trình mã hóa.
Chúng ta chọn một trường nguyên tố \mathbb{F}_q F q sao cho \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 là một chuỗi các nhóm con trong \mathbb{F}_q^* F ∗ q thỏa mãn các ràng buộc về kích thước.
Có thể nhận thấy rằng số nguyên tố q q liên kết với đường cong elip bls12-381 thỏa mãn 2^{32} \mid (q-1) 2 32 ∣ ( q − 1 ) và do đó phù hợp để tìm chuỗi nhóm con ở trên. Cây các nhóm con được cho trong Hình 4. Tiếp theo, chúng ta mô tả cách xây dựng khối mở rộng 0 0 .
Mã này bao gồm 4 mã cục bộ được đánh số từ 0 đến 3 , và quá trình mã hóa được thực hiện bằng cách mã hóa riêng từng mã cục bộ một. Trong Hình 3, các ô tạo thành mỗi mã cục bộ được thể hiện rõ ràng.
3\omega=96 3 ω = 96 ô đầu tiên \text{Cells}(0,0\text{-}95) Cells ( 0 , 0 - 95 ) bao gồm 3\omega D = 96 \times 64=6144 3 ω D = 96 × 64 = 6144 ký hiệu trường hữu hạn tạo thành một ([n_0=96,k_0=64],D=64) ( [ n 0 = 96 , k 0 = 64 ] , D = 64 ) mã RS 1D xếp chồng. Một đa thức f_0(X) \in \mathbb{F}_q[X] f 0 ( X ) ∈ F q [ X ] có bậc tối đa 2\omega D = 4096 2 ω D = 4096 có thể được hình thành bằng cách sử dụng các ký hiệu trong dữ liệu blob 0 0 tại \text{Cells}(0,0\text{-}31) Cells ( 0 , 0 - 31 ) và \text{Cells}(0,64\text{-}95) Cells ( 0 , 64 - 95 ) . Mỗi ô trong blob mở rộng được liên kết với một coset của \mathbb{H}_3 H 3 như sau:
\begin{aligned}\text{Tế bào}(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{Tế bào}(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{Tế bào}(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}Tế bào ( 0 , 0 - 31 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3 Tế bào ( 0 , 64 - 95 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3 Tế bào ( 0 , 32 - 63 ) ⇔ β H 3 , β 65 H 3 , β 33 H 3 , … , β 125 H 3Trong mỗi 96 ô , f_0(X) f 0 ( X ) được đánh giá tại tập hợp con tương ứng và các giá trị đánh giá trở thành nội dung của ô đó. Điều này tạo ra một từ mã RS xếp chồng của mã cục bộ 0 0 . Đa thức f_0(X) f 0 ( X ) được xây dựng theo cách sao cho các giá trị đánh giá tại \text{Cells}(0,0\text{-}31) Cells ( 0 , 0 - 31 ) và \text{Cells}(0,32\text{-}63) Cells ( 0 , 32 - 63 ) trong khối mở rộng hoàn toàn giống với các giá trị tương ứng trong khối. Điều này đạt được bằng cách lấy các giá trị dữ liệu làm giá trị đánh giá và nội suy một đa thức từ các giá trị dữ liệu này.
Quy trình tương tự được lặp lại cho Mã cục bộ 1, 2, 1 , 2 và 3. Các đa thức tương ứng được ký hiệu là f_1(X), f_2(X) , f_1 ( X ) , f_2 ( X ) và f_3( X ) . Dữ liệu blob được sử dụng để xây dựng mỗi f_i(X), i=1,2,3, f_i ( X ) , i = 1,2,3 , các ô liên kết với mỗi mã cục bộ và các tập hợp con được sử dụng làm điểm đánh giá được liệt kê bên dưới.
(a) Mã cục bộ 1 1 : \text{Ô}(0,64\text{-}159) Ô ( 0 , 64 - 159 )
\begin{aligned}f_1(X) &\Leftrightarrow \text{Các ô}(0,64\text{-}95) \text{ và } \text{Các ô}(0,128\text{-}159) \text{ của blob } 0 \\\text{Các ô}(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{Các ô}(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 ) ⇔ Các ô ( 0 , 64 - 95 ) và các ô ( 0 , 128 - 159 ) của khối 0 Tế bào ( 0 , 64 - 95 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3 Tế bào ( 0 , 96 - 127 ) ⇔ β 3 H 3 , β 67 H 3 , β 35 H 3 , … , β 127 H 3 Tế bào ( 0 , 128 - 159 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3(b) Mã cục bộ 2 2 : \text{Ô}(0,128\text{-}223) Ô ( 0 , 128 - 223 )
\begin{aligned}f_2(X) &\Leftrightarrow \text{Các ô}(0,64\text{-}95) \text{ và } \text{Các ô}(0,128\text{-}159) \text{ của blob } 0 \\\text{Các ô}(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{Các ô}(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 ) ⇔ Các ô ( 0 , 64 - 95 ) và các ô ( 0 , 128 - 159 ) của khối 0 Tế bào ( 0 , 128 - 159 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3 Tế bào ( 0 , 160 - 191 ) ⇔ β H 3 , β 65 H 3 , β 33 H 3 , … , β 125 H 3 Tế bào ( 0 , 192 - 223 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3(c) Mã cục bộ 3 3 : \text{Ô}(0,192\text{-}255) Ô ( 0 , 192 - 255 ) và \text{Ô}(0,0\text{-}31) Ô ( 0 , 0 - 31 )
\begin{aligned}f_3(X) &\Leftrightarrow \text{Các ô}(0,64\text{-}95) \text{ và } \text{Các ô}(0,128\text{-}159) \text{ của blob } 0 \\\text{Các ô}(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{Các ô}(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 ) ⇔ Các ô ( 0 , 64 - 95 ) và các ô ( 0 , 128 - 159 ) của khối 0 Tế bào ( 0 , 192 - 223 ) ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3 Tế bào ( 0 , 224 - 255 ) ⇔ β 3 H 3 , β 67 H 3 , β 35 H 3 , … , β 127 H 3 Tế bào ( 0 , 0 - 31 ) ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3Hãy lưu ý rằng mã cục bộ 3 3 được cuộn vòng theo chu kỳ, nghĩa là nó liên kết dữ liệu trong các ô ở đầu bên phải với các ô ở đầu bên trái. Điều này được thể hiện trong Hình\ref{fig:bcexblob}. Chúng ta nhận thấy rằng mã hóa này có tính hệ thống, tức là dữ liệu trong blob có sẵn nguyên trạng trong blob mở rộng.
Hình 2. Cây các nhóm con cho mã BC. Ở đây, \beta β là phần tử sinh của \mathbb{H}_0 H 0 .
Thuật toán chính xác sử dụng FFT được trình bày tiếp theo. Chúng ta hãy sử dụng {\bf u} \in \mathbb{F}_q^{64 \times 128} u ∈ F 64 × 128 q để ký hiệu khối 0. Chúng ta sử dụng {\bf u}[\textsf{start}\text{-}\textsf{end}] u [ start - end ] để ký hiệu dữ liệu tại các ô \text{Cell}(0,\textsf{start}) Cell ( 0 , start ) đến \text{Cell}(0,\textsf{end}) Cell ( 0 , end ) . Chúng ta hãy định nghĩa bốn mảng dữ liệu khối (D\times \omega) = (64 \times 32) ( D × ω ) = ( 64 × 32 ) ở dạng vectơ hóa, tức là các vectơ dài 2048 × 2048 :
