Tác giả gốc:Vitalik Buterin

Tác giả gốc:

• Sơ đồ Lấy mẫu tính khả dụng của dữ liệu (Lấy mẫu DA hoặc DAS) hiện tại được thực hiện bằng cách sử dụng các cam kết KZG. Ưu điểm của lời hứa KZG là chúng rất dễ sử dụng và có một số tính chất đại số rất hay:

• Một bằng chứng đánh giá có kích thước không đổi và có thể được xác minh trong thời gian không đổi.

• Ở đây tồn tại một thuật toán để tính toán tất cả các bằng chứng đánh giá deg tại mỗi N nghiệm đơn vị trong thời gian O(N∗log(N))

• Bạn có thể kết hợp tuyến tính các cam kết để có được tổ hợp cam kết tuyến tính này: com(P)+com(Q)=com(P+Q)

Bạn có thể kết hợp tuyến tính các bằng chứng: Bằng chứng(P,x)+Bằng chứng(Q,x)+Bằng chứng(P+Q,x)

Điểm đầu tiên là đảm bảo hiệu quả tốt. Điểm thứ hai đảm bảo rằng có thể dễ dàng tạo các đốm màu sẵn sàng cho lấy mẫu DA: nếu phải mất O(N2) thời gian dài như vậy để tạo ra tất cả các bằng chứng, thì nó sẽ yêu cầu các tác nhân tập trung cao độ hoặc các thuật toán phân tán phức tạp để sẵn sàng cho DAS.

• Điểm thứ ba và thứ tư rất có giá trị để lấy mẫu 2D và cho phép các nhà sản xuất khối phân tán cũng như khả năng tự phục hồi hiệu quả:

• Các nhà sản xuất khối chỉ cần biết cam kết M ban đầu để sử dụng FFT-over-the-curve để "mở rộng cột" và tạo

Bạn không chỉ có thể thực hiện tái tạo theo hàng mà còn có thể thực hiện tái tạo theo từng cột: nếu một số giá trị và bằng chứng trên một cột bị thiếu (nhưng vẫn còn hơn một nửa), bạn có thể thực hiện FFT để khôi phục thiếu giá trị và bằng chứng.Tuy nhiên, KZG có một điểm yếu: nó dựa vào mật mã ghép nối phức tạp và cài đặt đáng tin cậy. Mật mã cặp đã được nghiên cứu và sử dụng trong hơn 20 năm, thiết lập đáng tin cậy là 1 giả định tin cậy trong N, trong đó N có hàng trăm người tham gia, vì vậy rủi ro trong thực tế là cao và các tác giả cảm thấy rằng việc tiếp tục sử dụng KZG là hoàn toàn có thể chấp nhận được. Tuy nhiên, thật đáng để đặt một câu hỏi:

Nếu chúng tôi không muốn trả chi phí KZG, chúng tôi có thể sử dụng tham số sản phẩm bên trong (IPA) thay thế không?

Xem nửa đầu của bài viết này để biết giải thích về IPA.

• IPA có các thuộc tính sau:

• Đánh giá chứng minh có kích thước logarit và có thể được xác minh trong thời gian tuyến tính (khoảng 40 ms đối với đa thức có kích thước 4096)

• Không có thuật toán tạo đa bằng chứng hiệu quả nào được biết đến.

• Các cam kết là các điểm đường cong elip, bạn có thể kết hợp chúng một cách tuyến tính như các cam kết KZG

Không có phương pháp nào được biết đến để chứng minh các kết hợp tuyến tính.

Vì vậy, chúng tôi giữ một số tài sản và mất một số. Trên thực tế, chúng tôi đã mất quá nhiều thứ đến mức "phương pháp hiện tại" của chúng tôi để tạo, phân phối và tự phục hồi bằng chứng không còn khả thi nữa. Bài đăng này mô tả một phương pháp thay thế, hơi rắc rối nhưng vẫn đạt được mục tiêu.

một sự thay thế

Đầu tiên, chúng tôi tạo ra một cây bằng chứng thay vì deg

Chúng tôi giải thích dữ liệu ở dạng đánh giá, coi dữ liệu đó là một vectơ:

, trong đó đa thức

(trong đó Li là đa thức deg<2N bằng 1 tại tọa độ i và 0 tại các tọa độ khác trong tập hợp).

Mỗi nút trong cây bằng chứng là một cam kết đối với phần dữ liệu đó và là bằng chứng cho thấy cam kết này thực sự "trong giới hạn". Ví dụ,

Nút sẽ chứa lời hứa

. Sẽ có chứng chỉ IPA,

Trên thực tế, một sự kết hợp tuyến tính của những điểm này và không có điểm nào khác.

Chúng tôi tạo ra hai cây, cây đầu tiên cho

, thứ hai cho
, cam kết "đầy đủ" đối với một phần dữ liệu bao gồm C[0,N−1] và C[N,2N−1].

Để chứng minh một giá trị xi cụ thể, chúng ta chỉ cần cung cấp một danh sách các cặp (cam kết phụ, bằng chứng) bao gồm toàn bộ phạm vi 0...N−1 hoặc N....2N−1 (tùy theo giá trị nào chứa i), Không bao gồm i và một cam kết cấp cao nhất mà tôi không thuộc về là bằng chứng về việc xây dựng đúng. Ví dụ: nếu N=8 và i=3, bằng chứng sẽ chứa C[0,1], C2, C[4,7] và các chứng minh của chúng, đồng thời chứng minh rằng C[8,15] được xây dựng đúng. Bằng chứng sẽ được xác minh bằng cách xác minh các bằng chứng riêng lẻ và kiểm tra xem các cam kết có phải là một cam kết đầy đủ hay không.

Màu xanh lam: đoạn 3, màu vàng: bằng chứng của đoạn 3.

Lưu ý rằng mỗi đoạn không cần phải là một đánh giá duy nhất về hiệu quả; thay vào đó, chúng ta có thể tỉa bớt cây sao cho một đoạn là một tập hợp gồm 16 đánh giá. Cho rằng kích thước kết hợp của bằng chứng dù sao cũng sẽ lớn hơn kích thước này, nên chúng tôi mất rất ít bằng cách tạo các khối lớn hơn như thế này.

Việc tạo các bằng chứng này mất O(N∗log(N)) thời gian. Việc xác minh một bằng chứng mất O(N) thời gian, nhưng lưu ý rằng nhiều bằng chứng có thể được xác minh theo đợt: bước O(N) để xác minh IPA là sự kết hợp tuyến tính của các đường cong elip, nhiều trong số đó chúng ta có thể kiểm tra bằng cách sử dụng các kết hợp tuyến tính ngẫu nhiên. Mỗi bằng chứng vẫn yêu cầu thao tác trường O(N), nhưng điều này chỉ mất <1 ms.

Mở rộng: phân tán (fanout) lớn hơn 2

Thay vì có 2 lần xuất phát cho mỗi bước, chúng ta có thể có số lần xuất phát cao hơn, chẳng hạn như 8 lần xuất phát. Thay vì một bằng chứng cho mỗi cam kết, chúng tôi sẽ có 7 bằng chứng cho mỗi cam kết. Ví dụ: ở lớp dưới cùng, chúng tôi sẽ có một bằng chứng {1,2,3,4,5,6,7}, {0,2,3,4,5,6,7}, {0,1,3 ,4,5,6,7}, v.v. Điều này làm tăng tổng công việc tạo bằng chứng bằng cách

(7 bản in thử trên mỗi nút, kích thước mỗi bản in thử gấp 1,75 lần kích thước ban đầu, nhưng số lớp ít hơn 3 lần, do đó cần nhiều nỗ lực hơn ~4,08 lần), nhưng nó giảm kích thước bản in thử xuống 3 lần.

kích thước bằng chứng

Giả sử chúng ta đang xử lý N=128 khối có kích thước 32 (vì vậy chúng ta có đa thức deg<4096) và phân tán của (4x, 4x, 8x). Một bằng chứng nhánh đơn sẽ chứa 3 IPA với tổng kích thước là 2∗(7+9+12)=56 điểm đường cong (~1792 byte) cộng với 512 byte của đoạn. Ngày nay, một đoạn 256 byte hoặc 512 byte có bằng chứng 48 byte.

Tạo bằng chứng yêu cầu tổng cộng 2∗8192∗(3∗2+7) phép nhân đường cong (3*2 cho hai lớp fanout-4, 7 cho lớp fanout-8) hoặc tổng cộng ~212992 phép nhân. Vì vậy, điều này cần được thực hiện nhanh chóng bởi một máy tính mạnh (một máy tính bình thường có thể thực hiện phép nhân trong khoảng 50 micro giây, do đó, quá trình này mất 10 giây, hơi lâu một chút) hoặc một quy trình phân tán trong đó các Nút khác nhau chuyên về các khối khác nhau.

Việc xác minh bằng chứng rất dễ dàng vì các bằng chứng có thể được xác minh theo lô và chỉ thực hiện một phép nhân đường cong elip. Vì vậy, nó không nên chậm hơn nhiều so với việc sử dụng bằng chứng KZG.

tự chữa bệnh

Không thể tự phục hồi hiệu quả trên cơ sở từng cột. Nhưng chúng ta có thể tránh yêu cầu một bản sửa lỗi duy nhất để có tất cả dữ liệu (tất cả các khối 2N từ tất cả các đa thức 2M) không?

Giả sử một hàng bị mất hoàn toàn. Có thể dễ dàng sử dụng bất kỳ cột nào để xây dựng lại các giá trị ở các hàng bị thiếu trong cột đó. Nhưng làm thế nào để chứng minh điều đó?

Kỹ thuật đơn giản nhất là kinh tế học tiền điện tử: bất kỳ ai cũng có thể chỉ cần phát hành một trái phiếu yêu cầu một giá trị và sau đó ai đó có thể sử dụng yêu cầu đó với bằng chứng chi nhánh chứng minh một giá trị khác để cắt giảm trình xác thực đó. Miễn là có đủ các yêu cầu hợp pháp, ai đó trên mạng con của ngân hàng có thể tập hợp các yêu cầu lại với nhau và xây dựng lại cam kết và bằng chứng. Trình xác nhận thậm chí có thể được yêu cầu đưa ra các yêu cầu như vậy đối với các chỉ số mẫu được chỉ định cho chúng.Một giải pháp thay thế không có kinh tế học tiền điện tử nhưng phức tạp hơn và chậm hơn về mặt kỹ thuật là chuyển bằng chứng nhánh M của giá trị dọc theo cột đó, cùng với bằng chứng xác minh chính xác。