Vitalik: Binius, bằng chứng hiệu quả cho trường nhị phân

Bài viết gốc của: Vitalik Buterin

Bản dịch gốc: Kate, MarsBit

Bài đăng này chủ yếu dành cho những độc giả đã quen thuộc với mật mã thời kỳ 2019, đặc biệt là SNARK và STARK. Nếu chưa, tôi khuyên bạn nên đọc những điều đó trước. Đặc biệt cảm ơn Justin Drake, Jim Posen, Benjamin Diamond và Radi Cojbasic vì những phản hồi và nhận xét của họ.

Trong hai năm qua, STARK đã trở thành một công nghệ quan trọng và không thể thay thế để tạo ra các bằng chứng mật mã có thể xác minh dễ dàng cho các tuyên bố rất phức tạp (ví dụ: chứng minh rằng khối Ethereum là hợp lệ) một cách hiệu quả. Một trong những lý do chính cho điều này là kích thước trường nhỏ: SNARK dựa trên đường cong elip yêu cầu bạn làm việc trên số nguyên 256 bit để đủ an toàn, trong khi STARK cho phép bạn sử dụng kích thước trường nhỏ hơn nhiều với hiệu quả cao hơn: đầu tiên là trường Goldilocks (số nguyên 64 bit), sau đó là Mersenne 31 và BabyBear (cả 31 bit). Do những hiệu quả này gains, Plonky 2 sử dụng Goldilocks nhanh hơn hàng trăm lần so với các phiên bản tiền nhiệm trong việc chứng minh nhiều loại tính toán.

Một câu hỏi tự nhiên là: liệu chúng ta có thể đưa xu hướng này đi đến kết luận hợp lý và xây dựng các hệ thống chứng minh chạy nhanh hơn bằng cách thao tác trực tiếp trên các số không và số một không? Đây chính xác là những gì Binius cố gắng thực hiện, sử dụng một số thủ thuật toán học khiến nó trở nên rất khác so với SNARK và STARK ba năm trước. Bài đăng này mô tả lý do tại sao các trường nhỏ giúp việc tạo bằng chứng hiệu quả hơn, tại sao trường nhị phân lại có sức mạnh đặc biệt và các thủ thuật mà Binius sử dụng để tạo bằng chứng trên trường nhị phân hiệu quả đến vậy.

Binius, đến cuối bài này, bạn sẽ có thể hiểu được mọi phần của sơ đồ này.

Ôn tập: trường hữu hạn

Một trong những nhiệm vụ chính của hệ thống chứng minh mật mã là hoạt động trên lượng lớn dữ liệu trong khi vẫn giữ số lượng nhỏ. Nếu bạn có thể nén một phát biểu về một chương trình lớn thành một phương trình toán học chứa một vài con số, nhưng những con số đó lớn bằng chương trình gốc thì bạn chẳng thu được gì cả.

Để thực hiện các phép tính phức tạp trong khi vẫn giữ số lượng nhỏ, các nhà mật mã học thường sử dụng số học mô-đun. Chúng tôi chọn mô đun số nguyên tố p. Toán tử % có nghĩa là lấy phần còn lại: 15% 7 = 1, 53% 10 = 3, v.v. (Lưu ý rằng đáp án luôn không âm, ví dụ -1% 10 = 9)

Bạn có thể đã thấy số học mô-đun trong bối cảnh cộng và trừ thời gian (ví dụ: 4 giờ sau 9 giờ là mấy giờ?). Nhưng ở đây, chúng ta không chỉ cộng và trừ modulo một số; chúng ta cũng có thể nhân, chia và lấy số mũ.

Chúng tôi xác định lại:

Các quy tắc trên đều tự nhất quán. Ví dụ: nếu p = 7 thì:

5 + 3 = 1 (vì 8% 7 = 1)

1-3 = 5 (vì -2% 7 = 5)

2* 5 = 3

3/5 = 2

Một thuật ngữ tổng quát hơn cho các cấu trúc như vậy là trường hữu hạn. Trường hữu hạn là một cấu trúc toán học tuân theo các định luật số học thông thường, nhưng trong đó số lượng giá trị có thể là hữu hạn, do đó mỗi giá trị có thể được biểu diễn bằng một kích thước cố định.

Số học mô-đun (hoặc trường nguyên tố) là loại trường hữu hạn phổ biến nhất, nhưng có một loại khác: trường mở rộng. Bạn có thể đã thấy một trường mở rộng: số phức. Chúng ta tưởng tượng một phần tử mới và đặt tên cho nó là i, rồi thực hiện phép toán với nó: (3i+2)*(2i+4)=6i*i+12i+4i+8=16i+2. Chúng ta có thể làm tương tự với phần mở rộng của trường nguyên tố. Khi chúng tôi bắt đầu xử lý các trường nhỏ hơn, việc mở rộng các trường nguyên tố ngày càng trở nên quan trọng đối với bảo mật và các trường nhị phân (được Binius sử dụng) hoàn toàn dựa vào phần mở rộng để có tiện ích thực tế.

Ôn tập: Số học hóa

Cách SNARK và STARK chứng minh các chương trình máy tính là thông qua số học: bạn đưa ra nhận định về chương trình bạn muốn chứng minh và biến nó thành một phương trình toán học chứa đa thức. Một nghiệm hợp lệ cho phương trình tương ứng với việc thực thi chương trình hợp lệ.

Một ví dụ đơn giản, giả sử tôi đã tính số Fibonacci thứ 100 và tôi muốn chứng minh cho bạn thấy nó là gì. Tôi tạo một đa thức F mã hóa dãy Fibonacci: vì vậy F(0)=F(1)=1, F(2)=2, F(3)=3, F(4)=5, v.v. trong 100 bước . Điều kiện tôi cần chứng minh là F(x+2)=F(x)+F(x+1) trên toàn bộ phạm vi x={0, 1…98}. Tôi có thể thuyết phục bạn bằng cách đưa ra thương số:

trong đó Z(x) = (x-0) * (x-1) * …(x-98). . Nếu tôi có thể cho rằng F và H thỏa mãn phương trình này thì F phải thỏa mãn F(x+ 2)-F(x+ 1)-F(x) trong phạm vi. Nếu tôi xác minh thêm rằng đối với F, F(0)=F(1)=1 thì F(100) thực sự phải là số Fibonacci thứ 100.

Nếu bạn muốn chứng minh điều gì đó phức tạp hơn, thì bạn thay thế mối quan hệ đơn giản F(x+2) = F(x) + F(x+1) bằng một phương trình phức tạp hơn mà về cơ bản có nội dung F(x+1) là đầu ra khởi tạo một máy ảo có trạng thái F(x) và chạy một bước tính toán. Bạn cũng có thể thay thế số 100 bằng số lớn hơn, ví dụ: 100000000, để phù hợp với nhiều bước hơn.

Tất cả SNARK và STARK đều dựa trên ý tưởng sử dụng các phương trình đơn giản trên đa thức (và đôi khi là vectơ và ma trận) để biểu diễn số lượng lớn mối quan hệ giữa các giá trị riêng lẻ. Không phải tất cả các thuật toán đều kiểm tra sự tương đương giữa các bước tính toán liền kề như trên: ví dụ: PLONK không và R1CS cũng vậy. Nhưng nhiều bước kiểm tra hiệu quả nhất lại làm như vậy, vì việc giảm thiểu chi phí sẽ dễ dàng hơn bằng cách thực hiện cùng một bước kiểm tra (hoặc một vài bước kiểm tra giống nhau) nhiều lần.

Plonky 2: Từ SNARK 256-bit và STARK đến 64-bit… chỉ STARK

Năm năm trước, một bản tóm tắt hợp lý về các loại bằng chứng không có kiến thức khác nhau như sau. Có hai loại bằng chứng: SNARK (dựa trên đường cong elip) và STARK (dựa trên hàm băm). Về mặt kỹ thuật, STARK là một loại SNARK, nhưng trên thực tế, người ta thường sử dụng “SNARK” để chỉ biến thể dựa trên đường cong elip và “STARK” để chỉ cấu trúc dựa trên hàm băm. SNARK có kích thước nhỏ nên bạn có thể xác minh chúng rất nhanh và cài đặt chúng trên chuỗi một cách dễ dàng. STARK có kích thước lớn nhưng không yêu cầu thiết lập đáng tin cậy và có khả năng chống lượng tử.

STARK hoạt động bằng cách xử lý dữ liệu dưới dạng đa thức, tính toán tính toán của đa thức đó và sử dụng gốc Merkle của dữ liệu mở rộng như một “cam kết đa thức”.

Một phần quan trọng của lịch sử ở đây là SNARK dựa trên đường cong elip được sử dụng rộng rãi đầu tiên: STARK không hoạt động đủ hiệu quả cho đến khoảng năm 2018, nhờ FRI, và lúc đó Zcash đã hoạt động được hơn một năm. SNARK dựa trên đường cong elip có một hạn chế chính: nếu bạn muốn sử dụng SNARK dựa trên đường cong elip thì phép tính trong các phương trình này phải được thực hiện theo số lượng điểm trên đường cong elip. Đây là một số lớn, thường gần bằng 2 lũy thừa 256: ví dụ: đối với đường cong bn128, nó là 21888242871839275222246405745257275088548364400416034343698204186575808495617. Nhưng điện toán thực tế sử dụng số nhỏ: về một chương trình thực tế bằng ngôn ngữ yêu thích của bạn, hầu hết mọi thứ mà nó sử dụng là bộ đếm, chỉ mục trong vòng lặp, vị trí trong chương trình, các bit đơn biểu thị Đúng hoặc Sai và những thứ khác hầu như luôn chỉ dài một vài chữ số.

Ngay cả khi dữ liệu gốc của bạn bao gồm các số nhỏ, quy trình chứng minh yêu cầu thương số tính toán, mở rộng, kết hợp tuyến tính ngẫu nhiên và các phép biến đổi dữ liệu khác sẽ dẫn đến số lượng đối tượng bằng hoặc lớn hơn có kích thước trung bình bằng kích thước đầy đủ của bạn. cánh đồng. Điều này tạo ra sự kém hiệu quả quan trọng: để chứng minh một phép tính trên n giá trị nhỏ, bạn phải thực hiện nhiều phép tính hơn nữa trên n giá trị lớn hơn nhiều. Ban đầu, STARK kế thừa thói quen SNARK sử dụng các trường 256-bit và do đó cũng gặp phải tình trạng kém hiệu quả tương tự.

Khai triển Reed-Solomon của một số đánh giá đa thức. Mặc dù giá trị ban đầu nhỏ nhưng các giá trị bổ sung sẽ được mở rộng đến kích thước đầy đủ của trường (trong trường hợp này là 2^31 – 1)

Năm 2022, Plonky 2 được phát hành. Cải tiến chính của Plonky 2 là thực hiện modulo số học cho một số nguyên tố nhỏ hơn: 2 lũy thừa 64 – 2 lũy thừa 32 + 1 = 18446744067414584321. Giờ đây, mỗi phép cộng hoặc phép nhân luôn có thể được thực hiện theo một vài hướng dẫn trên CPU và việc băm tất cả dữ liệu lại với nhau nhanh hơn 4 lần so với trước đây. Nhưng có một vấn đề: phương pháp này chỉ có tác dụng với STARK. Nếu bạn cố gắng sử dụng SNARK, các đường cong elip sẽ trở nên không an toàn đối với các đường cong elip nhỏ như vậy.

Để đảm bảo tính bảo mật, Plonky 2 cũng cần đưa vào các trường mở rộng. Một kỹ thuật quan trọng để kiểm tra các phương trình số học là lấy mẫu điểm ngẫu nhiên: nếu bạn muốn kiểm tra xem H(x) * Z(x) có bằng F(x+ 2)-F(x+ 1)-F(x) hay không, bạn có thể chọn ngẫu nhiên chọn tọa độ r, đưa ra cam kết đa thức để chứng minh H(r), Z(r), F(r), F(r+ 1) và F(r+ 2), sau đó xác minh xem H(r) * Z(r ) bằng F(r+ 2)-F(r+ 1)- F(r). Nếu kẻ tấn công có thể đoán trước tọa độ thì kẻ tấn công có thể đánh lừa hệ thống chứng minh – đây là lý do tại sao hệ thống chứng minh phải là ngẫu nhiên. Nhưng điều này cũng có nghĩa là tọa độ phải được lấy mẫu từ một tập đủ lớn để kẻ tấn công không thể đoán ngẫu nhiên. Điều này rõ ràng đúng nếu mô đun gần bằng 2 lũy thừa 256. Tuy nhiên, đối với mô đun 2^64 – 2^32 + 1, chúng ta vẫn chưa đạt được điều đó, và điều này chắc chắn không xảy ra nếu chúng ta đi xuống 2^31 – 1. Kẻ tấn công có thể cố gắng giả mạo bằng chứng hai tỷ lần cho đến khi gặp may.

Để ngăn chặn điều này, chúng tôi lấy mẫu r từ một trường mở rộng, để chẳng hạn, bạn có thể xác định y trong đó y^3 = 5 và lấy kết hợp của 1, y và y^2. Điều này đưa tổng số tọa độ lên khoảng 2^93. Hầu hết các đa thức được tính toán bởi người chứng minh không đi vào trường mở rộng này; chúng chỉ là số nguyên modulo 2^31-1, vì vậy bạn vẫn đạt được hiệu quả tối đa từ việc sử dụng một trường nhỏ. Tuy nhiên, việc kiểm tra điểm ngẫu nhiên và tính toán FRI sẽ tiếp cận được lĩnh vực lớn hơn này để có được sự bảo mật mà họ cần.

Từ số nguyên tố nhỏ đến số nhị phân

Máy tính thực hiện phép tính bằng cách biểu diễn các số lớn hơn dưới dạng chuỗi 0 và 1, đồng thời xây dựng các mạch trên các bit đó để tính toán các phép toán như cộng và nhân. Máy tính được tối ưu hóa đặc biệt cho các số nguyên 16, 32 và 64 bit. Ví dụ: 2^64 – 2^32 + 1 và 2^31 – 1 được chọn không chỉ vì chúng vừa với các giới hạn đó mà còn vì chúng vừa khít với các giới hạn đó: phép nhân modulo 2^64 – 2^32 + 1 có thể được thực hiện bằng cách thực hiện phép nhân 32 bit thông thường, dịch chuyển và sao chép đầu ra theo từng bit ở một vài vị trí; bài viết này giải thích một số thủ thuật độc đáo.

Tuy nhiên, cách tiếp cận tốt hơn nhiều là thực hiện các phép tính trực tiếp dưới dạng nhị phân. Điều gì sẽ xảy ra nếu phép cộng chỉ có thể là XOR mà không phải lo lắng về việc chuyển từ việc thêm 1 + 1 từ bit này sang bit tiếp theo? Điều gì sẽ xảy ra nếu phép nhân có thể được song song hơn theo cách tương tự? Những ưu điểm này đều dựa trên khả năng biểu thị các giá trị đúng/sai chỉ bằng một bit.

Tận dụng được những lợi ích này của việc thực hiện tính toán nhị phân trực tiếp chính xác là những gì Binius đang cố gắng thực hiện. Nhóm Binius đã chứng minh mức độ hiệu quả đạt được trong bài trình bày của họ tại zkSummit:

Mặc dù có cùng kích thước nhưng các thao tác trên trường nhị phân 32 bit yêu cầu tài nguyên tính toán ít hơn 5 lần so với các thao tác trên trường Mersenne 31 bit.

Từ đa thức đơn biến đến siêu khối

Giả sử chúng ta tin vào lý do này và muốn làm mọi thứ với bit (0 và 1). Làm thế nào chúng ta có thể biểu diễn một tỷ bit bằng một đa thức?

Ở đây chúng ta phải đối mặt với hai vấn đề thực tế:

1. Để một đa thức biểu thị một số lượng lớn các giá trị, các giá trị này cần có thể truy cập được khi đánh giá đa thức: trong ví dụ Fibonacci ở trên, F(0), F(1) … F(100) và trong một phép tính lớn hơn , số mũ sẽ lên tới hàng triệu. Các trường chúng tôi sử dụng cần chứa các số có kích thước này.

2. Việc chứng minh bất kỳ giá trị nào chúng tôi cam kết trong cây Merkle (giống như tất cả STARK) đều yêu cầu mã hóa Reed-Solomon: ví dụ: mở rộng các giá trị từ n lên 8n, sử dụng tính năng dự phòng để ngăn chặn những kẻ giả mạo độc hại gian lận bằng cách giả mạo một giá trị trong quá trình tính toán. Điều này cũng đòi hỏi phải có một trường đủ lớn: để mở rộng từ một triệu giá trị lên 8 triệu, bạn cần 8 triệu điểm khác nhau để đánh giá đa thức.

Ý tưởng chính của Binius là giải quyết hai vấn đề này một cách riêng biệt và thực hiện điều đó bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau. Đầu tiên, các đa thức. Các hệ thống như SNARK dựa trên đường cong elip, STARK thế hệ 2019, Plonky 2 và các hệ thống khác thường xử lý đa thức trên một biến: F(x). Mặt khác, Binius lấy cảm hứng từ giao thức Spartan và sử dụng đa thức đa biến: F(x 1, x 2,… xk). Trên thực tế, chúng ta biểu diễn toàn bộ quỹ đạo tính toán trên một siêu khối tính toán, trong đó mỗi xi là 0 hoặc 1. Ví dụ: nếu chúng ta muốn biểu diễn một chuỗi Fibonacci và vẫn sử dụng một trường đủ lớn để biểu diễn chúng, chúng ta có thể hãy tưởng tượng 16 chuỗi đầu tiên của họ như thế này:

Nghĩa là, F(0,0,0,0) phải là 1, F(1,0,0,0) cũng là 1, F(0,1,0,0) là 2, v.v., tất cả cho đến F(1,1,1,1) = 987. Với một siêu khối tính toán như vậy, có một đa thức tuyến tính đa biến (độ 1 trong mỗi biến) tạo ra các phép tính này. Vì vậy, chúng ta có thể coi tập hợp các giá trị này đại diện cho đa thức; chúng ta không cần tính các hệ số.

Tất nhiên, ví dụ này chỉ nhằm mục đích minh họa: trong thực tế, toàn bộ mục đích của việc đi sâu vào hypercube là để chúng ta xử lý các bit riêng lẻ. Cách riêng của Binius để tính các số Fibonacci là sử dụng khối lập phương có chiều cao hơn, lưu trữ một số cho mỗi nhóm, chẳng hạn như 16 bit. Điều này đòi hỏi một chút thông minh để thực hiện phép cộng số nguyên trên cơ sở bit, nhưng đối với Binius, nó không quá khó.

Bây giờ, hãy xem xét các mã xóa. Cách thức hoạt động của STARK là bạn lấy n giá trị, Reed-Solomon mở rộng chúng thành nhiều giá trị hơn (thường là 8n, thường là từ 2n đến 32n), sau đó chọn ngẫu nhiên một số nhánh Merkle từ bản mở rộng và thực hiện một số loại kiểm tra trên chúng. Hypercube có chiều dài 2 ở mỗi chiều. Do đó, việc mở rộng trực tiếp là không thực tế: không có đủ chỗ để lấy mẫu các nhánh Merkle từ 16 giá trị. Vậy chúng ta làm điều đó như thế nào? Giả sử hypercube là một hình vuông!

Binius đơn giản - Một ví dụ

Nhìn thấy đây để thực hiện giao thức python.

Hãy xem một ví dụ, sử dụng các số nguyên thông thường làm trường để thuận tiện (trong triển khai thực tế, chúng tôi sẽ sử dụng các phần tử trường nhị phân). Đầu tiên, chúng tôi mã hóa siêu khối mà chúng tôi muốn gửi dưới dạng hình vuông:

Bây giờ, chúng ta mở rộng hình vuông bằng phương pháp Reed-Solomon. Nghĩa là, chúng ta coi mỗi hàng là một đa thức bậc 3 được đánh giá tại x = { 0, 1, 2, 3 } và đánh giá cùng một đa thức đó tại x = { 4, 5, 6, 7 }:

Lưu ý rằng con số có thể rất lớn! Đây là lý do tại sao trong triển khai thực tế, chúng tôi luôn sử dụng các trường hữu hạn, thay vì các số nguyên thông thường: ví dụ: nếu chúng tôi sử dụng số nguyên modulo 11, thì việc mở rộng hàng đầu tiên sẽ chỉ là [3, 10, 0, 6].

Nếu bạn muốn dùng thử tiện ích mở rộng và tự xác minh các con số, bạn có thể sử dụng mã tiện ích mở rộng Reed-Solomon đơn giản của tôi tại đây.

Tiếp theo, chúng tôi coi phần mở rộng này là một cột và tạo cây Merkle của cột. Gốc rễ của cây Merkle là cam kết của chúng tôi.

Bây giờ, giả sử rằng người chứng minh muốn chứng minh tính toán của đa thức r = {r 0, r 1, r 2, r 3 } tại một thời điểm nào đó. Có một sự khác biệt nhỏ trong Binius khiến nó yếu hơn so với các sơ đồ cam kết đa thức khác: người chứng minh không nên biết hoặc không thể đoán s trước khi cam kết với gốc Merkle (nói cách khác, r phải là một giá trị giả ngẫu nhiên phụ thuộc vào gốc Merkle). Điều này làm cho lược đồ trở nên vô dụng đối với việc tra cứu cơ sở dữ liệu (ví dụ: được rồi, bạn đã đưa cho tôi gốc Merkle, bây giờ hãy chứng minh cho tôi P(0, 0, 1, 0)!). Nhưng các giao thức chứng minh không có kiến thức mà chúng tôi thực sự sử dụng thường không yêu cầu tra cứu cơ sở dữ liệu; họ chỉ yêu cầu kiểm tra đa thức tại một điểm đánh giá ngẫu nhiên. Vì vậy, hạn chế này phục vụ tốt mục đích của chúng tôi.

Giả sử chúng ta chọn r = { 1, 2, 3, 4 } (đa thức ước tính là -137; bạn có thể xác nhận điều này bằng mã này). Bây giờ, chúng ta đi đến bằng chứng. Chúng tôi chia r thành hai phần: phần đầu tiên { 1, 2 } biểu thị sự kết hợp tuyến tính của các cột trong hàng và phần thứ hai { 3, 4 } biểu thị sự kết hợp tuyến tính của các hàng. Chúng tôi tính toán tích tensor và cho các cột:

Đối với phần hàng:

Điều này có nghĩa là: danh sách tất cả các sản phẩm có thể có của một giá trị trong mỗi bộ. Trong trường hợp hàng, chúng tôi nhận được:

[( 1-r 2)*( 1-r 3), ( 1-r 3), ( 1-r 2)*r 3, r 2*r 3 ]

Với r = { 1, 2, 3, 4 } (vì vậy r 2 = 3 và r 3 = 4):

[( 1-3)*( 1-4), 3*( 1-4),( 1-3)* 4, 3* 4 ] = [ 6, -9 -8 -12 ]

Bây giờ, chúng ta tính toán một hàng t mới bằng cách lấy tổ hợp tuyến tính của các hàng hiện có. Nghĩa là, chúng tôi lấy:

Bạn có thể coi những gì đang xảy ra ở đây như một sự đánh giá từng phần. Nếu chúng ta nhân tích tensor đầy đủ với vectơ đầy đủ của tất cả các giá trị, bạn sẽ nhận được phép tính P(1, 2, 3, 4) = -137. Ở đây, chúng tôi đã nhân tích tensor từng phần chỉ bằng một nửa tọa độ đánh giá và giảm lưới các giá trị N thành một hàng có giá trị N căn bậc hai. Nếu bạn đưa hàng này cho người khác, họ có thể thực hiện phần còn lại của phép tính bằng cách sử dụng tích tensor của nửa tọa độ đánh giá còn lại.

Người chứng minh cung cấp cho người xác minh hàng mới sau: t và bằng chứng Merkle của một số cột được lấy mẫu ngẫu nhiên. Trong ví dụ minh họa của chúng tôi, chúng tôi sẽ yêu cầu người tục ngữ chỉ cung cấp cột cuối cùng; trong đời thực, người chứng minh sẽ cần cung cấp hàng tá cột để đạt được mức độ bảo mật đầy đủ.

Bây giờ chúng ta khai thác tính tuyến tính của mã Reed-Solomon. Thuộc tính quan trọng mà chúng tôi khai thác là việc lấy tổ hợp tuyến tính của các khai triển Reed-Solomon cho kết quả tương tự như lấy khai triển Reed-Solomon của tổ hợp tuyến tính. Sự độc lập tuần tự này thường xảy ra khi cả hai phép toán đều tuyến tính.

Người xác minh thực hiện chính xác điều đó. Họ tính toán t và tính toán các kết hợp tuyến tính của cùng các cột mà người chứng minh đã tính toán trước đó (nhưng chỉ các cột do người chứng minh cung cấp) và xác minh rằng hai quy trình đều đưa ra cùng một câu trả lời.

Trong trường hợp này, chúng tôi khai triển t và tính toán tổ hợp tuyến tính giống nhau ([6,-9,-8, 12]), cả hai đều cho cùng một câu trả lời: -10746. Điều này chứng tỏ rằng gốc Merkle được xây dựng một cách trung thực (hoặc ít nhất là đủ gần) và nó khớp với t: ít nhất phần lớn các cột đều tương thích với nhau.

Nhưng còn một điều nữa mà người kiểm tra cần kiểm tra: kiểm tra việc đánh giá đa thức {r 0 …r 3 }. Tất cả các bước của người xác minh cho đến nay vẫn chưa thực sự phụ thuộc vào giá trị được người chứng minh khẳng định. Đây là cách chúng tôi kiểm tra nó. Chúng tôi lấy tích tensor của “phần cột” mà chúng tôi đã đánh dấu làm điểm tính toán:

Trong trường hợp của chúng tôi, trong đó r = { 1, 2, 3, 4 } nên nửa số cột được chọn là { 1, 2 }), điều này tương đương với:

Bây giờ chúng ta lấy tổ hợp tuyến tính t này:

Điều này giống như giải trực tiếp đa thức.

Phần trên rất gần với mô tả đầy đủ về giao thức Binius đơn giản. Điều này đã có một số lợi thế thú vị: ví dụ: vì dữ liệu được tách thành hàng và cột nên bạn chỉ cần một trường có kích thước bằng một nửa. Tuy nhiên, điều này không đạt được đầy đủ lợi ích của tính toán nhị phân. Để làm được điều đó, chúng ta cần giao thức Binius đầy đủ. Nhưng trước tiên, hãy nhìn sâu hơn vào các trường nhị phân.

Trường nhị phân

Trường nhỏ nhất có thể là số học modulo 2, nhỏ đến mức chúng ta có thể viết các bảng cộng và nhân cho nó:

Chúng ta có thể nhận được các trường nhị phân lớn hơn bằng cách mở rộng: nếu chúng ta bắt đầu với F 2 (số nguyên modulo 2) và sau đó xác định x trong đó x bình phương = x + 1 , chúng ta sẽ nhận được bảng cộng và bảng nhân sau:

Hóa ra là chúng ta có thể mở rộng các trường nhị phân thành các kích thước lớn tùy ý bằng cách lặp lại cấu trúc này. Không giống như số phức trên số thực, trong đó bạn có thể thêm một phần tử mới nhưng không bao giờ thêm bất kỳ phần tử I nào nữa (các phần tư có tồn tại, nhưng chúng kỳ lạ về mặt toán học, ví dụ: ab không bằng ba), với các trường hữu hạn, bạn có thể thêm phần mở rộng mới mãi mãi. Cụ thể, định nghĩa của chúng ta về một phần tử như sau:

Và vân vân… Điều này thường được gọi là xây dựng tháp, bởi vì mỗi lần mở rộng liên tiếp có thể được coi là thêm một lớp mới vào tháp. Đây không phải là cách duy nhất để xây dựng các trường nhị phân có kích thước tùy ý, nhưng nó có một số lợi thế độc đáo mà Binius khai thác.

Chúng ta có thể biểu diễn những con số này dưới dạng danh sách các bit. Ví dụ: 1100101010001111. Bit đầu tiên biểu thị bội số của 1, bit thứ hai biểu thị bội số của x0, sau đó các bit sau biểu thị bội số của x1: x1, x1*x0, x2, x2*x0, v.v. Mã hóa này rất hay vì bạn có thể chia nhỏ nó ra:

Đây là một ký hiệu tương đối hiếm gặp, nhưng tôi thích biểu diễn các phần tử trường nhị phân dưới dạng số nguyên, với bit hiệu quả hơn ở bên phải. Nghĩa là, 1 = 1, x0 = 01 = 2, 1+x0 = 11 = 3, 1+x0+x2 = 11001000 = 19, v.v. Trong cách biểu diễn này, đó là 61779.

Phép cộng trong trường nhị phân chỉ là XOR (và phép trừ cũng vậy); lưu ý rằng điều này có nghĩa là x+x = 0 với mọi x. Để nhân hai phần tử x*y với nhau, có một thuật toán đệ quy rất đơn giản: chia mỗi số làm đôi:

Sau đó chia phép nhân:

Phần cuối cùng là phần duy nhất hơi phức tạp một chút vì bạn phải áp dụng các quy tắc đơn giản hóa. Có nhiều cách hiệu quả hơn để thực hiện phép nhân, tương tự như thuật toán Karatsubas và Biến đổi Fourier nhanh, nhưng tôi sẽ coi đó là bài tập để người đọc quan tâm tìm ra.

Phép chia trong trường nhị phân được thực hiện bằng cách kết hợp phép nhân và phép đảo ngược. Phương pháp đảo ngược đơn giản nhưng chậm là một ứng dụng của định lý nhỏ Fermat tổng quát. Ngoài ra còn có một thuật toán đảo ngược phức tạp hơn nhưng hiệu quả hơn mà bạn có thể tìm thấy ở đây. Bạn có thể sử dụng mã ở đây để chơi với phép cộng, nhân và chia các trường nhị phân.

Bên trái: Bảng cộng cho các phần tử trường nhị phân 4 bit (tức là chỉ 1, x 0, x 1, x 0x 1). Bên phải: Bảng nhân cho các phần tử trường nhị phân 4 bit.

Cái hay của loại trường nhị phân này là nó kết hợp một số phần tốt nhất của số nguyên thông thường và số học mô-đun. Giống như các số nguyên thông thường, các phần tử trường nhị phân không bị giới hạn: bạn có thể tăng kích thước theo ý muốn. Nhưng cũng giống như số học mô-đun, nếu bạn thao tác trên các giá trị trong một giới hạn kích thước nhất định, tất cả kết quả của bạn sẽ ở cùng một phạm vi. Ví dụ: nếu bạn lấy 42 lũy thừa liên tiếp, bạn sẽ nhận được:

Sau 255 bước, bạn trở về 42 với lũy thừa 255 = 1 và giống như các số nguyên dương và các phép toán mô đun, chúng tuân theo các định luật toán học thông thường: a*b=b*a, a*(b+c)= a*b+a*c và thậm chí một số luật mới kỳ lạ.

Cuối cùng, các trường nhị phân thuận tiện cho việc thao tác các bit: nếu bạn làm toán với các số vừa với 2k thì tất cả đầu ra của bạn cũng sẽ vừa với 2k bit. Điều này tránh được sự khó xử. Trong EIP-4844 của Ethereum, các khối riêng lẻ của một blob phải có số modulo 52435875175126190479447740508185965837690552500527637822603658699938581184513, do đó, việc mã hóa dữ liệu nhị phân yêu cầu loại bỏ một số khoảng trống và thực hiện kiểm tra bổ sung ở lớp ứng dụng để đảm bảo rằng giá trị được lưu trữ trong mỗi phần tử nhỏ hơn 2248. Điều này cũng có nghĩa là các hoạt động trường nhị phân cực kỳ nhanh trên máy tính – cả CPU và các thiết kế FPGA và ASIC tối ưu về mặt lý thuyết.

Tất cả điều này có nghĩa là chúng ta có thể thực hiện mã hóa Reed-Solomon như chúng ta đã làm ở trên, theo cách hoàn toàn tránh được sự bùng nổ số nguyên như chúng ta đã thấy trong ví dụ của mình và theo một cách rất nguyên bản, loại tính toán mà máy tính giỏi. Thuộc tính phân tách của các trường nhị phân – cách chúng ta có thể thực hiện 1100101010001111 = 11001010 + 10001111*x 3 và sau đó chia nhỏ nó khi chúng ta cần – cũng rất quan trọng để cho phép rất linh hoạt.

Binius hoàn chỉnh

Nhìn thấy đây để thực hiện giao thức python.

Bây giờ chúng ta có thể chuyển sang “Binius đầy đủ”, điều chỉnh “Binius đơn giản” để (i) hoạt động trên các trường nhị phân và (ii) cho phép chúng ta cam kết các bit đơn lẻ. Giao thức này khó hiểu vì nó chuyển đổi qua lại giữa các cách khác nhau để xem ma trận bit; chắc chắn tôi phải mất nhiều thời gian hơn để hiểu nó hơn là tôi thường phải mất nhiều thời gian để hiểu các giao thức mật mã. Nhưng một khi bạn hiểu được các trường nhị phân, tin tốt là “toán học khó hơn” mà Binius dựa vào không tồn tại. Đây không phải là các cặp đường cong elip, nơi có những hố thỏ hình học đại số ngày càng sâu hơn để đi xuống; ở đây, bạn chỉ có các trường nhị phân.

Hãy nhìn lại biểu đồ đầy đủ một lần nữa:

Đến bây giờ, bạn đã quen thuộc với hầu hết các thành phần. Ý tưởng làm phẳng một siêu khối thành một lưới, ý tưởng tính toán các kết hợp hàng và cột dưới dạng tích tensor của các điểm đánh giá và ý tưởng kiểm tra sự tương đương giữa khai triển Reed-Solomon sau đó tính toán kết hợp hàng và tính toán kết hợp hàng sau đó khai triển Reed-Solomon tất cả đều được thực hiện bằng Binius đơn giản.

Có gì mới trong Complete Binius? Về cơ bản ba điều:

• Các giá trị riêng lẻ trong siêu khối và hình vuông phải là bit (0 hoặc 1).

• Quá trình mở rộng mở rộng các bit thành nhiều bit hơn bằng cách nhóm chúng thành các cột và tạm thời giả định rằng chúng là các phần tử của trường lớn hơn.

• Sau bước kết hợp hàng, có một bước phân tách phần tử thành bit để chuyển đổi phần mở rộng trở lại bit.

Hãy thảo luận lần lượt cả hai trường hợp. Đầu tiên, thủ tục gia hạn mới. Mã Reed-Solomon có một hạn chế cơ bản, nếu bạn muốn mở rộng n thành k*n, bạn cần làm việc trong một trường có k*n các giá trị khác nhau có thể được sử dụng làm tọa độ. Với F 2 (còn gọi là bit), bạn không thể làm điều đó. Vì vậy, điều chúng ta làm là đóng gói các phần tử liền kề của F 2 lại với nhau để tạo thành các giá trị lớn hơn. Trong ví dụ ở đây, chúng tôi gói hai bit cùng một lúc vào các phần tử { 0 , 1 , 2 , 3 } , điều này là đủ đối với chúng tôi vì tiện ích mở rộng của chúng tôi chỉ có bốn điểm tính toán. Trong một bằng chứng thực tế, chúng ta có thể quay lại 16 bit cùng một lúc. Sau đó, chúng tôi thực thi mã Reed-Solomon trên các giá trị được đóng gói này và giải nén chúng thành từng bit một lần nữa.

Bây giờ, kết hợp hàng. Để thực hiện đánh giá tại một điểm ngẫu nhiên, kiểm tra an toàn bằng mật mã, chúng ta cần lấy mẫu điểm đó từ một không gian khá lớn (lớn hơn nhiều so với chính siêu khối). Vì vậy, trong khi điểm bên trong siêu khối là bit thì giá trị tính toán bên ngoài siêu khối sẽ lớn hơn nhiều. Trong ví dụ trên, tổ hợp hàng có kết quả là [11, 4, 6, 1].

Điều này gây ra một vấn đề: chúng ta biết cách nhóm các bit thành một giá trị lớn hơn và sau đó thực hiện phép khai triển Reed-Solomon trên giá trị đó, nhưng làm cách nào để thực hiện điều tương tự đối với các cặp giá trị lớn hơn?

Thủ thuật của Binius là thực hiện từng chút một: chúng ta xem xét từng bit của mỗi giá trị (ví dụ: đối với thứ chúng ta gắn nhãn 11, tức là [1, 1, 0, 1]), sau đó chúng ta mở rộng nó theo từng hàng. Nghĩa là, chúng ta mở rộng nó trên hàng 1 của mỗi phần tử, sau đó trên hàng x0, sau đó trên hàng x1, rồi trên hàng x0x1, v.v. (à, trong ví dụ về đồ chơi của chúng ta, chúng ta dừng ở đó, nhưng trong một thực tế việc triển khai chúng tôi có tối đa 128 hàng (hàng cuối cùng là x6*…*x0))

ôn tập:

• Chúng tôi chuyển đổi các bit trong hypercube thành lưới

• Sau đó, chúng tôi coi các nhóm bit liền kề trên mỗi hàng là các phần tử của trường lớn hơn và thực hiện các phép tính số học trên chúng để Reed-Solomon mở rộng hàng

• Sau đó, chúng tôi lấy tổ hợp hàng của từng cột bit và lấy cột bit cho mỗi hàng làm đầu ra (nhỏ hơn nhiều đối với các ô vuông lớn hơn 4 x 4)

• Sau đó, chúng ta coi đầu ra là một ma trận và các bit của nó là các hàng

Tại sao chuyện này đang xảy ra? Trong toán học thông thường, nếu bạn bắt đầu cắt một số từng bit một, khả năng (thông thường) thực hiện các phép tính tuyến tính theo bất kỳ thứ tự nào và nhận được kết quả tương tự sẽ bị hỏng. Ví dụ: nếu tôi bắt đầu bằng số 345 và nhân nó với 8, rồi nhân với 3, tôi nhận được 8280 và nếu tôi thực hiện ngược lại hai thao tác đó, tôi cũng nhận được 8280. Nhưng nếu tôi chèn một thao tác cắt bit giữa hai bước, nó bị hỏng: nếu bạn thực hiện 8x, rồi 3x, bạn sẽ nhận được:

Nhưng nếu bạn làm gấp 3 lần, rồi 8 lần, bạn sẽ nhận được:

Nhưng trong các trường nhị phân được xây dựng bằng cấu trúc tháp, phương pháp này có hiệu quả. Lý do là khả năng phân tách của chúng: nếu bạn nhân một giá trị lớn với một giá trị nhỏ thì điều gì xảy ra trên mỗi phân đoạn vẫn ở trên mỗi phân đoạn. Nếu chúng ta nhân 1100101010001111 với 11, thì kết quả này giống như phân tách đầu tiên của 1100101010001111, tức là

Sau đó nhân mỗi thành phần với 11.

Để tất cả chúng cùng nhau

Nói chung, hệ thống chứng minh không có kiến thức hoạt động bằng cách đưa ra các phát biểu về một đa thức đồng thời biểu diễn các phát biểu về đánh giá cơ bản: giống như chúng ta đã thấy trong ví dụ Fibonacci, F(X+ 2)-F(X+ 1)-F( X) = Z(X)*H(X) trong khi kiểm tra tất cả các bước tính toán Fibonacci. Chúng ta kiểm tra các phát biểu về đa thức bằng cách chứng minh đánh giá tại các điểm ngẫu nhiên. Việc kiểm tra các điểm ngẫu nhiên này thể hiện việc kiểm tra toàn bộ đa thức: nếu phương trình đa thức không khớp, có một khả năng nhỏ là nó khớp ở một tọa độ ngẫu nhiên cụ thể.

Trong thực tế, một nguyên nhân chính dẫn đến sự kém hiệu quả là trong các chương trình thực, hầu hết các con số chúng ta xử lý đều nhỏ: các chỉ số trong vòng lặp for, giá trị Đúng/Sai, bộ đếm và những thứ tương tự. Tuy nhiên, khi chúng tôi mở rộng dữ liệu bằng mã hóa Reed-Solomon để cung cấp độ dư cần thiết nhằm đảm bảo an toàn cho các hoạt động kiểm tra dựa trên Merkle-proof, hầu hết các giá trị bổ sung cuối cùng sẽ chiếm toàn bộ kích thước của trường, ngay cả khi giá trị ban đầu nhỏ.

Để khắc phục điều này, chúng tôi muốn làm cho trường này càng nhỏ càng tốt. Plonky 2 đã đưa chúng ta từ số 256 bit xuống số 64 bit, sau đó Plonky 3 lại giảm xuống còn 31 bit. Nhưng ngay cả điều đó cũng không tối ưu. Với các trường nhị phân, chúng ta có thể xử lý các bit đơn. Điều này làm cho mã hóa dày đặc: nếu dữ liệu cơ bản thực tế của bạn có n bit thì mã hóa của bạn sẽ có n bit và phần mở rộng sẽ có 8*n bit mà không cần thêm chi phí.

Bây giờ, hãy nhìn vào biểu đồ này lần thứ ba:

Trong Binius, chúng tôi làm việc trên một đa thức đa tuyến tính: một siêu khối P(x0, x1,…xk) trong đó các giá trị đơn lẻ P(0, 0, 0, 0), P(0, 0, 0, 1) cho đến P( 1, 1, 1, 1), chứa dữ liệu chúng ta quan tâm. Để chứng minh một phép tính tại một thời điểm nhất định, chúng ta diễn giải lại dữ liệu đó dưới dạng hình vuông. Sau đó, chúng tôi mở rộng từng hàng bằng cách sử dụng mã hóa Reed-Solomon để cung cấp khả năng dự phòng dữ liệu cần thiết nhằm bảo mật trước các truy vấn nhánh Merkle ngẫu nhiên. Sau đó, chúng tôi tính toán các kết hợp tuyến tính ngẫu nhiên của các hàng, thiết kế các hệ số sao cho hàng kết hợp mới thực sự chứa giá trị tính toán mà chúng tôi quan tâm. Hàng mới được tạo này (được diễn giải lại dưới dạng hàng 128 bit) và một số cột được chọn ngẫu nhiên có nhánh Merkle được chuyển đến trình xác minh.

Sau đó, trình xác minh thực hiện kết hợp hàng mở rộng (hay chính xác hơn là các cột mở rộng) và kết hợp hàng mở rộng và xác minh rằng cả hai đều khớp. Sau đó, nó tính toán tổ hợp cột và kiểm tra xem nó có trả về giá trị được người chứng minh xác nhận hay không. Đây là hệ thống chứng minh của chúng tôi (hay chính xác hơn là sơ đồ cam kết đa thức, là thành phần chính của hệ thống chứng minh).

Chúng ta chưa đề cập đến điều gì?

• Cần có một thuật toán hiệu quả để mở rộng các hàng để thực sự làm cho trình xác thực tính toán hiệu quả. Chúng tôi sử dụng Biến đổi Fourier nhanh trên các trường nhị phân, được mô tả ở đây (mặc dù cách triển khai chính xác sẽ khác, vì bài đăng này sử dụng cấu trúc kém hiệu quả hơn không dựa trên việc mở rộng đệ quy).

• Về mặt số học. Đa thức một biến rất thuận tiện vì bạn có thể thực hiện những việc như F(X+2)-F(X+1)-F(X) = Z(X)*H(X) để liên kết các bước liền kề trong phép tính. Trong hypercube, bước tiếp theo ít được giải thích rõ ràng hơn X+1. Bạn có thể thực hiện X+k, lũy thừa của k, nhưng hành vi nhảy này làm mất đi nhiều lợi thế chính của Binius. Bài báo Binius mô tả giải pháp. Xem Phần 4.3), nhưng bản thân đây là một cái hố sâu.

• Cách thực hiện kiểm tra giá trị cụ thể một cách an toàn. Ví dụ về Fibonacci yêu cầu kiểm tra các điều kiện biên chính: các giá trị của F(0)=F(1)=1 và F(100). Nhưng đối với Binius ban đầu, việc kiểm tra tại các điểm tính toán đã biết là không an toàn. Có một số cách khá đơn giản để chuyển đổi phép tính kiểm tra đã biết sang phép kiểm tra phép tính chưa biết, sử dụng cái gọi là giao thức kiểm tra tổng; nhưng chúng tôi sẽ không đề cập đến những điều đó ở đây.

• Các giao thức tra cứu, một công nghệ khác được sử dụng rộng rãi gần đây, được sử dụng để tạo ra các hệ thống chứng minh siêu hiệu quả. Binius có thể được sử dụng kết hợp với các giao thức tra cứu cho nhiều ứng dụng.

• Ngoài thời gian xác minh căn bậc hai. Căn bậc hai rất đắt: bằng chứng Binius 2^32 bit dài khoảng 11 MB. Bạn có thể bù đắp cho điều này bằng cách sử dụng các hệ thống chứng minh khác để tạo ra bằng chứng cho bằng chứng Binius, mang lại cho bạn hiệu quả của bằng chứng Binius với kích thước bằng chứng nhỏ hơn. Một tùy chọn khác là giao thức FRI-Binius phức tạp hơn, tạo ra bằng chứng về kích thước đa logarit (giống như FRI thông thường).

• Binius ảnh hưởng như thế nào đến tính thân thiện với SNARK. Tóm tắt cơ bản là nếu bạn sử dụng Binius, bạn không còn cần phải quan tâm đến việc thực hiện các phép tính thân thiện với số học: băm thông thường không còn hiệu quả hơn băm số học truyền thống, nhân modulo 2 lũy thừa 32 hoặc modulo 2 lũy thừa của 256 không còn khó khăn như phép nhân modulo 2, v.v. Nhưng đây là một chủ đề phức tạp. Rất nhiều thứ thay đổi khi mọi thứ được thực hiện ở dạng nhị phân.

Tôi hy vọng sẽ thấy nhiều cải tiến hơn trong công nghệ chứng minh dựa trên trường nhị phân trong những tháng tới.

Bài viết này có nguồn gốc từ internet: Vitalik: Binius, bằng chứng hiệu quả cho các trường nhị phân

Liên quan: Đồng BNB cho thấy các dấu hiệu phục hồi: Mức cao mới trong năm

Tóm lại, giá BNB đã bật trở lại từ $550 để tiến gần hơn đến việc phá vỡ ngưỡng kháng cự $593. Các chỉ báo giá đã lấy lại đà tăng, hỗ trợ mức tăng 8%. Tỷ lệ Sharpe ở mức 4,03 có thể sẽ thúc đẩy các nhà đầu tư mới hướng tới mã thông báo trao đổi. Tháng 3 là một tháng thuận lợi đối với BNB Coin, khi tiền điện tử này đạt được hai mức cao mới trong năm chỉ trong vài ngày trước khi trải qua đợt điều chỉnh. Sau gần hai tuần phục hồi, BNB Coin đang có dấu hiệu có khả năng đạt mức cao mới vào năm 2024. Nhưng liệu cột mốc như vậy có thể đạt được? BNB có vẻ đầy hứa hẹn Sau khi phục hồi từ mức hỗ trợ $550, giá trị của BNB Coin đã tăng lên $581 tại thời điểm phân tích này. Sự cải thiện này phản ánh sự phục hồi trong hồ sơ lợi nhuận rủi ro của altcoin,…