Vitalik: Binius, bằng chứng hiệu quả cho các trường nhị phân
Tuyển chọn TechFlowTuyển chọn TechFlow
Vitalik: Binius, bằng chứng hiệu quả cho các trường nhị phân
Binius là một hệ thống chứng minh dựa trên trường nhị phân, được thiết kế để nâng cao hiệu suất của các chứng minh mật mã, đặc biệt là các chứng minh liên quan đến SNARK và STARK.
Chuyên sâu báo cáo Web3Tác giả: Vitalik Buterin
Biên dịch: Kate, Mars Finance
Bài viết này chủ yếu dành cho những độc giả đã quen thuộc với mật mã học thời kỳ 2019, đặc biệt là SNARK và STARK. Nếu chưa, tôi khuyên bạn nên đọc các bài viết đó trước. Cảm ơn đặc biệt tới Justin Drake, Jim Posen, Benjamin Diamond và Radi Cojbasic vì những phản hồi và bình luận.
Trong hai năm qua, STARK đã trở thành một công nghệ then chốt và không thể thay thế để tạo ra các chứng minh mật mã hiệu quả và dễ xác minh cho những mệnh đề rất phức tạp (ví dụ như chứng minh rằng một khối Ethereum là hợp lệ). Một trong những lý do chính là kích thước trường nhỏ: SNARK dựa trên đường cong elliptic yêu cầu bạn làm việc trên các số nguyên 256 bit để đảm bảo độ an toàn, trong khi STARK cho phép sử dụng kích thước trường nhỏ hơn, hiệu quả hơn: ban đầu là trường Goldilocks (số nguyên 64 bit), sau đó là Mersenne31 và BabyBear (đều là 31 bit). Nhờ vào sự gia tăng hiệu suất này, Plonky2 sử dụng Goldilocks nhanh hàng trăm lần so với người tiền nhiệm của nó trong việc chứng minh nhiều loại tính toán khác nhau.
Một câu hỏi tự nhiên đặt ra là: liệu chúng ta có thể đưa xu hướng này đến kết luận hợp lý bằng cách xây dựng hệ thống chứng minh chạy nhanh hơn thông qua việc trực tiếp thao tác trên các bit 0 và 1? Chính xác điều này Binius đang cố gắng thực hiện, bằng cách sử dụng nhiều kỹ thuật toán học khiến nó khác biệt rõ rệt so với SNARK và STARK ba năm trước. Bài viết này giới thiệu lý do tại sao các trường nhỏ làm cho việc tạo chứng minh hiệu quả hơn, tại sao các trường nhị phân có sức mạnh đặc biệt, cũng như các thủ thuật mà Binius dùng để làm cho chứng minh trên các trường nhị phân trở nên hiệu quả đến vậy.
Binius. Cuối bài viết này, bạn sẽ hiểu được từng phần trong hình ảnh này.
Ôn tập: Các trường hữu hạn (finite fields)
Một trong những nhiệm vụ trọng tâm của hệ thống chứng minh mật mã là thao tác trên lượng lớn dữ liệu trong khi vẫn giữ các con số ở mức nhỏ. Nếu bạn có thể nén một mệnh đề về chương trình lớn thành một phương trình toán học chứa vài con số, nhưng những con số đó lại lớn ngang với chương trình gốc, thì bạn chẳng thu được lợi ích gì.
Để thực hiện các phép tính phức tạp trong khi giữ các con số nhỏ, các nhà mật mã thường dùng số học modulo (modular arithmetic). Chúng ta chọn một số nguyên tố "modulo" p. Toán tử % nghĩa là "lấy phần dư": 15%7=1, 53%10=3, v.v. (Lưu ý rằng kết quả luôn là số không âm, ví dụ -1%10=9)
Bạn có thể đã gặp số học modulo trong ngữ cảnh cộng/trừ giờ (ví dụ: 9 giờ cộng thêm 4 tiếng là mấy giờ?). Nhưng ở đây, chúng ta không chỉ thực hiện cộng trừ theo một số nào đó, mà còn có thể nhân, chia và lũy thừa.
Chúng ta định nghĩa lại:
Tất cả các quy tắc trên đều 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
Thuật ngữ tổng quát hơn cho cấu trúc nà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 quy luật số học thông thường, nhưng chỉ có số lượng giá trị hữu hạn, do đó mỗi giá trị có thể biểu diễn bằng kích thước cố định.
Số học modulo (hay trường nguyên tố) là dạng trường hữu hạn phổ biến nhất, nhưng cũng tồn tại một dạng khác: trường mở rộng. Bạn có thể đã biết một trường mở rộng: số phức. Chúng ta "tưởng tượng" ra một phần tử mới, gắn nhãn là i, rồi thực hiện toán học với nó: (3i+2)*(2i+4)=6i*i+12i+4i+8=16i+2. Tương tự, chúng ta có thể lấy mở rộng của một trường nguyên tố. Khi bắt đầu xử lý các trường nhỏ hơn, mở rộng trường nguyên tố ngày càng quan trọng để đảm bảo an toàn, còn các trường nhị phân (mà Binius sử dụng) hoàn toàn phụ thuộc vào mở rộng để có tính ứng dụng thực tế.
Ôn tập: Số học hóa (arithmeticization)
Phương pháp chứng minh chương trình máy tính của SNARK và STARK là thông qua số học: bạn chuyển đổi một mệnh đề về chương trình cần chứng minh thành một phương trình toán học chứa đa thức. Nghiệm hợp lệ của phương trình tương ứng với việc thực thi chương trình hợp lệ.
Ví dụ đơn giản, giả sử tôi đã tính số Fibonacci thứ 100 và muốn chứng minh với bạn đó là số gì. Tôi tạo một đa thức F mã hóa dãy Fibonacci: F(0)=F(1)=1, F(2)=2, F(3)=3, F(4)=5, v.v., trải qua 100 bước. Điều kiện cần chứng minh là F(x+2)=F(x)+F(x+1) trong toàn bộ phạm vi x={0,1…98}. Tôi có thể thuyết phục bạn bằng cách cung cấp thương số:
Trong đó Z(x) = (x-0) * (x-1) * …(x-98). Nếu tôi có thể cung cấp F và H thỏa mãn đẳng thức 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 kiểm tra thêm rằng 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, 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, cơ bản nói rằng "F(x+1) là đầu ra của một máy ảo được khởi tạo với trạng thái F(x)", và thực hiện một bước tính toán. Bạn cũng có thể thay số 100 bằng một số lớn hơn, ví dụ 100000000, để chứa nhiều bước hơn.
Tất cả các SNARK và STARK đều dựa trên ý tưởng này: sử dụng phương trình đơn giản trên đa thức (đôi khi là vector và ma trận) để biểu diễn mối quan hệ giữa nhiều giá trị riêng lẻ. Không phải mọi thuật toán đều kiểm tra tính tương đương giữa các bước tính toán liền kề như trên: ví dụ PLONK và R1CS không làm vậy. Nhưng nhiều phương pháp kiểm tra hiệu quả nhất lại làm như vậy, vì việc thực hiện lặp lại cùng một kiểm tra (hoặc vài kiểm tra giống nhau) giúp giảm thiểu chi phí xuống mức tối thiểu.
Plonky2: Từ SNARK và STARK 256 bit đến 64 bit... chỉ còn STARK
Năm năm trước, tóm tắt hợp lý về các loại chứng minh kiến thức không tiết lộ như sau. Có hai loại chứng minh: SNARK (dựa trên đường cong elliptic) và STARK (dựa trên hàm băm). Về mặt kỹ thuật, STARK là một dạng của SNARK, nhưng trong thực tiễn, "SNARK" thường dùng để chỉ biến thể dựa trên đường cong elliptic, còn "STARK" dùng để chỉ cấu trúc dựa trên hàm băm. SNARK nhỏ, do đó bạn có thể xác minh rất nhanh và dễ dàng đưa lên chuỗi. STARK lớn, nhưng không cần thiết lập đáng tin cậy và chống lượng tử.
STARK hoạt động bằng cách coi dữ liệu như đa thức, tính toán đánh giá đa thức đó, và dùng gốc Merkle của dữ liệu mở rộng làm "cam kết đa thức"
Một điểm lịch sử quan trọng là SNARK dựa trên đường cong elliptic được sử dụng rộng rãi trước tiên: mãi đến khoảng năm 2018, STARK mới đủ hiệu quả nhờ FRI, nhưng lúc đó Zcash đã hoạt động hơn một năm. SNARK dựa trên đường cong elliptic có một hạn chế quan trọng: nếu bạn muốn dùng SNARK dựa trên đường cong elliptic, thì các phép tính số học trong các phương trình đó phải được thực hiện theo modulo số điểm trên đường cong elliptic. Đây là một con số lớn, thường gần 2^256: ví dụ, đường cong bn128 là 21888242871839275222246405745257275088548364400416034343698204186575808495617. Nhưng các tính toán thực tế sử dụng các con số nhỏ: nếu bạn nghĩ về một chương trình "thực sự" bằng ngôn ngữ lập trình yêu thích, hầu hết thứ bạn dùng là bộ đếm, chỉ số vòng lặp for, vị trí trong chương trình, bit đơn đại diện True hoặc False, và những thứ khác hầu như luôn chỉ dài vài chữ số.
Ngay cả khi dữ liệu "gốc" của bạn gồm các số "nhỏ", quá trình chứng minh cũng cần tính toán thương số, mở rộng, tổ hợp tuyến tính ngẫu nhiên và các phép biến đổi dữ liệu khác, dẫn đến số lượng đối tượng bằng hoặc lớn hơn, với kích thước trung bình bằng toàn bộ kích thước trường của bạn. Điều này gây ra một sự kém hiệu quả nghiêm 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 trên n giá trị lớn hơn nhiều. Ban đầu, STARK kế thừa thói quen của SNARK dùng trường 256 bit, do đó cũng chịu chung sự kém hiệu quả này.
Một số đánh giá đa thức mở rộng Reed-Solomon. Mặc dù các giá trị gốc nhỏ, các giá trị bổ sung đều mở rộng đến kích thước đầy đủ của trường (trong ví dụ này là 2^31-1)
Năm 2022, Plonky2 được công bố. Đổi mới chính của Plonky2 là thực hiện số học theo modulo một số nguyên tố nhỏ hơn: 2^64 – 2^32 + 1 = 18446744067414584321. Giờ đây, mỗi phép cộng hoặc nhân luôn có thể hoàn thành trong vài lệnh CPU, và tốc độ băm tất cả dữ liệu nhanh hơn gấp 4 lần so với trước. Nhưng có một vấn đề: phương pháp này chỉ áp dụng được cho STARK. Nếu bạn thử dùng SNARK, thì với đường cong elliptic quá nhỏ như vậy, nó sẽ mất an toàn.
Để đảm bảo an toàn, Plonky2 cũng cần đưa vào trường mở rộng. Một kỹ thuật quan trọng để kiểm tra 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 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 một tọa độ r, cung cấp cam kết đa thức và chứng minh H(r), Z(r), F(r), F(r+1), F(r+2), rồi kiểm tra xem H(r) * Z(r) có bằng F(r+2)-F(r+1)-F(r) hay không. Nếu kẻ tấn công đoán trước được tọa độ, họ có thể lừa hệ thống chứng minh — đó là lý do tại sao hệ thống chứng minh phải mang tính 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 hợp đủ lớn để kẻ tấn công không thể đoán ngẫu nhiên. Nếu modulo gần 2^256, điều này hiển nhiên đúng. Nhưng với modulo là 2^64–2^32+1, chúng ta chưa đạt đến mức đó, và nếu giảm xuống 2^31–1, chắc chắn không đúng. Việc cố gắng làm giả chứng minh 2 tỷ lần cho đến khi may mắn trúng đích nằm hoàn toàn trong khả năng của kẻ tấn công.
Để ngăn chặn điều này, chúng ta lấy mẫu r từ trường mở rộng, ví dụ bạn có thể định nghĩa y sao cho y^3=5, rồi dùng tổ hợp của 1, y, y^2. Điều này sẽ làm tăng tổng số tọa độ lên khoảng 2^93. Phần lớn các đa thức mà người chứng minh tính toán không đi vào trường mở rộng này; chúng chỉ dùng số nguyên theo modulo 2^31–1, do đó bạn vẫn nhận được toàn bộ hiệu quả từ việc dùng trường nhỏ. Nhưng kiểm tra điểm ngẫu nhiên và tính toán FRI thực sự đi sâu vào trường lớn hơn này để đạt được độ an toàn cần thiết.
Từ số nguyên tố nhỏ đến số nhị phân
Máy tính thực hiện số học bằng cách biểu diễn các số lớn hơn dưới dạng dãy các bit 0 và 1, và xây dựng "mạch" trên các bit này để tính toán các phép như cộng và nhân. Máy tính được tối ưu đặ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 phù hợp với các giới hạn này, mà còn vì chúng khớp rất tốt với các giới hạn đó: phép nhân theo modulo 2^64–2^32+1 có thể thực hiện bằng cách thực hiện phép nhân 32 bit thông thường, rồi dịch chuyển bit và sao chép đầu ra ở vài vị trí; bài viết này giải thích khá tốt một số thủ thuật.
Tuy nhiên, phương pháp tốt hơn là tính toán trực tiếp bằng nhị phân. Nếu phép cộng có thể "chỉ là" XOR, mà không cần lo lắng về việc "tràn" khi cộng 1+1 từ một bit sang bit tiếp theo? Nếu phép nhân cũng có thể được song song hóa theo cách tương tự? Những lợi thế này đều dựa trên khả năng biểu diễn giá trị đúng/sai bằng một bit.
Việc tận dụng những lợi thế này của tính toán nhị phân trực tiếp chính xác là điều Binius đang cố gắng làm. Nhóm Binius đã trình bày về hiệu suất cải thiện tại zkSummit:
Mặc dù "kích thước" tương tự, nhưng thao tác trên trường nhị phân 32 bit tiêu tốn ít hơn 5 lần tài nguyên tính toán so với thao tác trên trường Mersenne 31 bit.
Từ đa thức một biến đến siêu lập phương
Giả sử chúng ta tin vào lập luận này và muốn làm mọi thứ bằng bit (0 và 1). Làm thế nào để biểu diễn một tỷ bit bằng một đa thức?
Ở đây, chúng ta đối mặt với hai vấn đề thực tế:
1. Với một đa thức biểu diễn nhiều giá trị, các giá trị này cần truy cập được khi đánh giá đa thức: trong ví dụ Fibonacci ở trên, F(0), F(1) … F(100), trong một phép tính lớn hơn, chỉ số có thể lên đến hàng triệu. Trường chúng ta dùng cần chứa các số đến kích thước này.
2. Việc chứng minh bất kỳ giá trị nào chúng ta cam kết trong cây Merkle (giống như tất cả STARK) cần mã hóa Reed-Solomon: ví dụ, mở rộng giá trị từ n lên 8n, dùng dư thừa để ngăn kẻ làm chứng gian lận bằng cách làm sai một giá trị trong quá trình tính toán. Điều này cũng cần một trường đủ lớn: để mở rộng một triệu giá trị thành 8 triệu, bạn cần 8 triệu điểm khác nhau để đánh giá đa thức.
Một ý tưởng then chốt của Binius là giải quyết riêng biệt hai vấn đề này, và đạt được điều đó bằng cách biểu diễn cùng một dữ liệu theo hai cách khác nhau. Trước tiên, chính đa thức. Các hệ thống như SNARK dựa trên đường cong elliptic, STARK thời kỳ 2019, Plonky2 thường xử lý đa thức trên một biến: F(x). Trái lại, Binius lấy cảm hứng từ giao thức Spartan và dùng đa thức đa biến: F(x1,x2,… xk). Thực tế, chúng ta biểu diễn toàn bộ hành trình tính toán trên "siêu lập phương" của phép tính, trong đó mỗi xi chỉ là 0 hoặc 1. Ví dụ, nếu chúng ta muốn biểu diễn dãy Fibonacci, và vẫn dùng một trường đủ lớn để biểu diễn chúng, chúng ta có thể hình dung 16 số đầu tiên như sau:
Tức là, F(0,0,0,0) nên là 1, F(1,0,0,0) cũng là 1, F(0,1,0,0) là 2, v.v., đến F(1,1,1,1)=987. Cho một siêu lập phương tính toán như vậy, sẽ tồn tại một đa thức đa tuyến tính (bậc 1 theo mỗi biến) sinh ra các tính toán này. Vì vậy, chúng ta có thể coi tập giá trị này là đại diện cho đa thức; chúng ta không cần tính hệ số.
Dĩ nhiên ví dụ này chỉ mang tính minh họa: trong thực tế, mục đích của việc đưa vào siêu lập phương là để chúng ta xử lý từng bit riêng lẻ. Phương pháp "nguyên bản Binius" để tính số Fibonacci là dùng một lập phương chiều cao, dùng mỗi nhóm ví dụ 16 bit để lưu trữ một số. Điều này đòi hỏi sự khéo léo để thực hiện phép cộng số nguyên trên cơ sở bit, nhưng với Binius thì không quá khó.
Bây giờ, hãy xem xét mã sửa lỗi. STARK hoạt động như sau: 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 nằm giữa 2n và 32n), sau đó chọn ngẫu nhiên một vài nhánh Merkle từ phần mở rộng, và thực hiện một kiểm tra nào đó trên chúng. Siêu lập phương có độ dài 2 theo mỗi chiều. Do đó, việc mở rộng trực tiếp là không thực tế: không đủ "không gian" để lấy mẫu các nhánh Merkle từ 16 giá trị. Vậy chúng ta phải làm gì? Chúng ta giả sử siêu lập phương là một hình vuông!
Binius đơn giản - một ví dụ
Xem tại đây để biết mã Python triển khai giao thức này.
Hãy xem một ví dụ, thuận tiện dùng các số nguyên thông thường làm trường của chúng ta (trong triển khai thực tế, sẽ dùng các phần tử trường nhị phân). Trước tiên, chúng ta mã hóa siêu lập phương muốn cam kết thành một hình vuông:
Bây giờ, chúng ta mở rộng hình vuông bằng Reed-Solomon. Tức là, 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á đa thức đó tại x ={4,5,6,7}:
Lưu ý rằng các con số tăng nhanh chóng! Đó là lý do tại sao trong triển khai thực tế, chúng ta luôn dùng trường hữu hạn chứ không dùng số nguyên thông thường: nếu dùng số nguyên modulo 11, ví dụ, phần mở rộng của hàng đầu tiên sẽ chỉ là [3,10,0,6].
Nếu bạn muốn thử mở rộng và tự kiểm tra các con số ở đây, có thể dùng mã mở rộng Reed-Solomon đơn giản của tôi.
Tiếp theo, chúng ta coi phần mở rộng này là các cột, và tạo cây Merkle từ các cột. Gốc cây Merkle là cam kết của chúng ta.
Bây giờ, giả sử người chứng minh muốn chứng minh tính toán của đa thức này tại một thời điểm r={r0,r1,r2,r3}. Trong Binius có một điểm tinh tế làm cho nó yếu hơn các sơ đồ cam kết đa thức khác: người chứng minh không nên biết hoặc đoán được s trước khi cam kết vào gốc Merkle (nói cách khác, r nên là một giá trị giả ngẫu nhiên phụ thuộc vào gốc Merkle). Điều này khiến sơ đồ vô dụng cho "tra cứu cơ sở dữ liệu" (ví dụ: "Ừ, bạn đưa tôi gốc Merkle, giờ hãy chứng minh P(0,0,1,0)!"). Nhưng các giao thức chứng minh kiến thức không tiết lộ mà chúng ta thực sự dùng thường không cần "tra cứu cơ sở dữ liệu"; chúng chỉ cần kiểm tra đa thức tại một điểm đánh giá ngẫu nhiên. Do đó, hạn chế này phù hợp với mục đích của chúng ta.
Giả sử chúng ta chọn r={1,2,3,4} (tại thời điểm này, đa thức tính ra là -137; bạn có thể dùng mã này để xác nhận). Bây giờ, chúng ta tiến vào quá trình chứng minh. Chúng ta chia r thành hai phần: phần đầu {1,2} biểu thị tổ hợp tuyến tính cột bên trong hàng, phần thứ hai {3,4} biểu thị tổ hợp tuyến tính các hàng. Chúng ta tính một "tích tenxơ", cho phần cột:
Cho phần hàng:
Điều này nghĩa là: danh sách tích của tất cả các tổ hợp có thể một giá trị từ mỗi tập. Trong trường hợp hàng, chúng ta có:
[(1-r2)*(1-r3), (1-r3), (1-r2)*r3, r2*r3]
Với r={1,2,3,4} (do đó r2=3 và r3=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 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ó. Tức là, chúng ta lấy:
Bạn có thể coi điều xảy ra ở đây là đánh giá một phần. Nếu nhân tích tenxơ đầy đủ với vector giá trị đầy đủ, bạn sẽ nhận được tính toán P(1,2,3,4) = -137. Ở đây, chúng ta nhân tích tenxơ một nửa tọa độ đánh giá với lưới N giá trị, rút gọn thành một hàng giá trị căn bậc hai N. Nếu bạn đưa hàng này cho người khác, họ có thể hoàn thành phần còn lại bằng tích tenxơ của nửa còn lại của tọa độ đánh giá.
Người chứng minh cung cấp cho người xác minh hàng t mới này cùng với một vài bằng chứng Merkle của các cột được chọn ngẫu nhiên. Trong ví dụ minh họa của chúng ta, chúng ta sẽ để người chứng minh chỉ cung cấp cột cuối cùng; trong thực tế, người chứng minh cần cung cấp vài chục cột để đạt được độ an toàn đủ.
Bây giờ, chúng ta tận dụng tính tuyến tính của mã Reed-Solomon. Thuộc tính chính chúng ta dùng là: lấy tổ hợp tuyến tính của phần mở rộng Reed-Solomon cho kết quả giống như mở rộng Reed-Solomon của tổ hợp tuyến tính. Sự "độc lập thứ 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 làm chính xác điều đó. Họ tính t, và tính tổ hợp tuyến tính của các cột giống như người chứng minh đã tính trước đó (nhưng chỉ tính các cột mà người chứng minh cung cấp), rồi kiểm tra xem hai quá trình có cho cùng kết quả hay không.
Trong ví dụ này, là mở rộng t, tính tổ hợp tuyến tính giống nhau ([6,-9,-8,12], cả hai cho cùng kết quả: -10746. Điều này chứng minh gốc Merkle được xây dựng "tử tế" (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 là tương thích lẫn nhau.
Nhưng người xác minh còn cần kiểm tra một điều nữa: kiểm tra đánh giá đa thức tại {r0…r3}. Cho đến nay, tất cả các bước của người xác minh thực tế không phụ thuộc vào giá trị mà người chứng minh tuyên bố. Chúng ta kiểm tra như sau. Chúng ta lấy tích tenxơ của "phần cột" tại điểm tính toán mà chúng ta đánh dấu:
Trong ví dụ của chúng ta, nơi r={1,2,3,4} do đó nửa chọn cột là {1,2}), điều này bằng:
Bây giờ chúng ta lấy tổ hợp tuyến tính này của t:
Điều này giống như kết quả đánh giá trực tiếp đa thức.
Nội dung trên đây rất gần với mô tả đầy đủ về giao thức Binius "đơn giản". Nó đã có một số ưu điểm thú vị: ví dụ, do dữ liệu được chia thành hàng và cột, bạn chỉ cần một trường có kích thước giảm một nửa. Nhưng nó chưa tận dụng toàn bộ lợi ích của việc tính toán nhị phân. Để làm vậy, chúng ta cần giao thức Binius đầy đủ. Nhưng trước tiên, hãy tìm hiểu sâu hơn về các trường nhị phân.
Các 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 bảng cộng và nhân của 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 bắt đầu từ F2 (số nguyên modulo 2) rồi định nghĩa x sao cho x^2=x+1, chúng ta có bảng cộng và nhân như sau:
Hóa ra, chúng ta có thể mở rộng trường nhị phân đến kích thước tùy ý bằng cách lặp lại cấu trúc này. Khác với số phức trên số thực, nơi bạn có thể thêm một phần tử mới nhưng không thể thêm nữa (quaternion thực sự 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ể liên tục thêm các mở rộng mới. Cụ thể, chúng ta định nghĩa các phần tử như sau:
V.v... Điều này thường được gọi là cấu trúc tháp, vì mỗi mở rộng liên tiếp có thể coi như thêm một tầng mới cho tháp. Đây không phải là cách duy nhất để xây dựng trường nhị phân kích thước tùy ý, nhưng nó có một số ưu điểm độc đáo mà Binius tận dụng.
Chúng ta có thể biểu diễn các số này thành danh sách bit. Ví dụ, 1100101010001111. Bit đầu tiên biểu thị bội của 1, bit thứ hai biểu thị bội của x0, rồi các bit tiếp theo biểu thị bội của các số x1 sau: x1, x1*x0, x2, x2*x0, v.v. Cách mã hóa này tốt vì bạn có thể phân tách nó:
Đây là một cách biểu diễn 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 thành số nguyên, dùng biểu diễn bit hiệu quả hơn ở bên phải. Tức là, 1=1, x0=01=2, 1+x0=11=3, 1+x0+x2=11001000 =19, v.v. Trong biểu thức này, là 61779.
Phép cộng trong trường nhị phân chỉ là XOR (nhân tiện, phép trừ cũng vậy); lưu ý rằng điều này nghĩa là x+x=0 với mọi x. Nhân hai phần tử x*y, có một thuật toán đệ quy rất đơn giản: chia mỗi số thành hai nửa:
Sau đó, chia phép nhân:
Phần cuối cùng là phần duy nhất hơi khó khăn, vì bạn phải áp dụng các quy tắc đơn giản hóa. Có những phương pháp hiệu quả hơn để thực hiện phép nhân, tương tự như thuật toán Karatsuba và biến đổi Fourier nhanh, nhưng tôi sẽ để cho độc giả quan tâm tự khám phá.
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à nghịch đảo. Phương pháp "đơn giản nhưng chậm" để nghịch đảo là áp dụng định lý Fermat nhỏ tổng quát. Có một thuật toán nghịch đảo phức tạp hơn nhưng hiệu quả hơn, bạn có thể tìm thấy ở đây. Bạn có thể dùng mã ở đây để chơi với phép cộng, nhân và chia trong trường nhị phân.
Bên trái: bảng cộng các phần tử trường nhị phân 4 bit (tức là chỉ gồm 1, x0, x1, x0x1). Bên phải: bảng nhân các phần tử trường nhị phân 4 bit.
Điều tuyệt vời của loại trường nhị phân này là nó kết hợp một số ưu điểm tốt nhất của số nguyên "thông thường" và số học modulo. Như số nguyên thông thường, các phần tử trường nhị phân là vô hạn: bạn có thể mở rộng tùy ý. Nhưng giống như số học modulo, nếu bạn thực hiện các phép toán trên các giá trị trong giới hạn kích thước nhất định, tất cả kết quả của bạn cũng sẽ giữ trong phạm vi đó. Ví dụ, nếu lấy lũy thừa liên tục của 42, bạn nhận được:
Sau 255 bước, bạn quay lại 42^255=1, giống như số nguyên thông thường và số học modulo, chúng tuân theo các quy luật toán học thông thường: a*b=b*a, a*(b+c)=a*b+a*c, thậm chí có thêm một vài quy luật kỳ lạ mới.
Cuối cùng, các trường nhị phân xử lý bit một cách thuận tiện: nếu bạn thực hiện toán học với các số phù hợp 2^k, thì tất cả đầu ra của bạn cũng sẽ phù hợp 2^k bit. Điều này tránh sự bất tiện. Trong EIP-4844 của Ethereum, các "khối" riêng lẻ của một blob phải là số modulo 52435875175126190479447740508185965837690552500527637822603658699938581184513, do đó mã hóa dữ liệu nhị phân cần bỏ đi một chút không gian, và kiểm tra thêm ở lớp ứng dụng để đảm bảo mỗi phần tử lưu giá trị nhỏ hơn 2^248. Điều này cũng có nghĩa là các phép toán trường nhị phân cực nhanh trên máy tính — cả trên CPU, lẫn thiết kế FPGA và ASIC lý tưởng về mặt lý thuyết.
Tất cả điều này nghĩa là chúng ta có thể làm những gì đã làm với mã hóa Reed-Solomon ở trên, theo cách hoàn toàn tránh được sự "bùng nổ" của số nguyên như chúng ta thấy trong ví dụ, và theo cách rất "nguyên bản", kiểu tính toán mà máy tính giỏi. Thuộc tính "phân tách" của trường nhị phân — cách chúng ta làm 1100101010001111=11001010+10001111*x3, rồi chia theo nhu cầu — cũng rất quan trọng để đạt được sự linh hoạt lớn.
Binius đầy đủ
Xem tại đây để biết mã Python triển khai giao thức này.
Bây giờ, chúng ta có thể đi đến "Binius đầy đủ", điều chỉnh "Binius đơn giản" để (i) hoạt động trên trường nhị phân, (ii) cho phép chúng ta cam kết từng bit riêng lẻ. Giao thức này khó hiểu vì nó liên tục chuyển đổi giữa các cách nhìn khác nhau về ma trận bit; chắc chắn tôi mất thời gian lâu hơn để hiểu nó so với thời gian tôi thường dùng để hiểu các giao thức mật mã. Nhưng một khi bạn hiểu trường nhị phân, tin tốt là không còn "toán học khó hơn" nào mà Binius dựa vào. Không phải cặp đôi đường cong elliptic, nơi có những hố thỏ đại số hình học ngày càng sâu để đào; ở đây, bạn chỉ cần trường nhị phân.
Hãy xem lại biểu đồ đầy đủ:
Cho đến nay, bạn đã quen thuộc với phần lớn các thành phần. Ý tưởng "làm phẳng" siêu lập phương thành lưới, ý tưởng tính tổ hợp hàng và cột như tích tenxơ của điểm đánh giá, và ý tưởng kiểm tra tính tương đương giữa "mở rộng Reed-Solomon rồi tính tổ hợp hàng" và "tính tổ hợp hàng rồi mở rộng Reed-Solomon", đều đã được thực hiện trong Binius đơn giản.
"Binius đầy đủ" có gì mới? Cơ bản có ba điều:
• Các giá trị riêng lẻ trong siêu lập phương và hình vuông phải là bit (0 hoặc 1).
• Quá trình mở rộng bằng cách nhóm các bit thành cột và tạm thời coi chúng là các phần tử trường lớn hơn, mở rộng các bit thành nhiều bit hơn
• Sau bước tổ hợp hàng, có bước "phân tách thành bit" theo từng phần tử, chuyển đổi phần mở rộng trở lại thành bit
Chúng ta sẽ thảo luận lần lượt cả hai trường hợp. Trước tiên, quy trình gia hạn mới. Mã Reed-Solomon có một giới hạn 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 giá trị khác nhau, có thể dùng làm tọa độ. Với F2 (còn gọi là bit), bạn không thể làm điều đó. Do đó, chúng ta gói các phần tử F2 liền kề "gói" lại với nhau để tạo thành các giá trị lớn hơn. Trong ví dụ ở đây, chúng ta gói hai bit mỗi lần thành các phần tử {0,1,2,3}, vì việc mở rộng của chúng ta chỉ có bốn điểm tính toán, điều này là đủ. Trong chứng minh "thực tế", chúng ta có thể gói 16 bit mỗi lần. Sau đó, chúng ta thực hiện mã Reed-Solomon trên các giá trị đã gói, rồi giải nén chúng trở lại thành bit.
Bây giờ, tổ hợp hàng. Để kiểm tra "đánh giá tại điểm ngẫu nhiên" an toàn về mặt 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 siêu lập phương). Do đó, mặc dù các điểm trong siêu lập phương là bit, các giá trị tính toán ngoài siêu lập phương sẽ lớn hơn nhiều. Trong ví dụ trên, "tổ hợp hàng" cuối cùng là [11,4,6,1].
Điều này gây ra một vấn đề: chúng ta biết cách kết hợp bit thành một giá trị lớn hơn, rồi thực hiện mở rộng Reed-Solomon trên đó, nhưng làm thế nào để làm điều tương tự với các giá trị lớn hơn?
Thủ thuật của Binius là xử lý theo bit: chúng ta xem từng bit riêng lẻ của mỗi giá trị (ví dụ: thứ chúng ta gọi là "11", tức là [1,1,0,1]), rồi mở rộng theo hàng. Thực hiện quy trình mở rộng trên các đối tượng này. Tức là, chúng ta thực hiện quy trình mở rộng trên hàng 1, rồi trên hàng x0, rồi trên hàng "x1", rồi trên hàng x0x1, v.v. (thực ra, trong ví dụ đồ chơi của chúng ta, chúng ta dừng ở đó, nhưng trong triển khai thực tế, chúng ta sẽ đạt đến 128 hàng (hàng cuối cùng là x6*…*x0))
Tóm lại:
• Chúng ta chuyển các bit trong siêu lập phương thành một lưới
• Sau đó, chúng ta coi các nhóm bit liền kề trên mỗi hàng là các phần tử trường lớn hơn, và thực hiện các phép toán số học để mở rộng Reed-Solomon các hàng
• Sau đó, chúng ta lấy tổ hợp hàng của từng cột bit, và nhận được từng cột bit của từng hàng làm đầu ra (đối với hình vuông lớn hơn 4x4, sẽ nhỏ hơn nhiều)
• Sau đó, chúng ta coi đầu ra như một ma trận, rồi coi các bit của nó như các hàng
Tại sao điều này lại hoạt động? Trong toán học "thông thường", nếu bạn bắt đầu cắt một số theo bit, khả năng thực hiện các phép toán tuyến tính theo thứ tự bất kỳ và nhận được kết quả giống nhau (thường) sẽ thất bại. Ví dụ, nếu tôi bắt đầu với số 345, nhân với 8, rồi nhân với 3, tôi nhận được 8280, nếu đảo ngược hai phép toán, tôi cũng nhận được 8280. Nhưng nếu tôi chèn một thao tác "cắt theo bit" giữa hai bước, nó sẽ sụp đổ: nếu bạn làm 8 lần, rồi làm 3 lần, bạn nhận được:
Nhưng nếu bạn làm 3 lần, rồi làm 8 lần, bạn 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 thực sự hoạt động. Lý do nằm ở tính tách rời của chúng: nếu bạn nhân một giá trị lớn với một giá trị nhỏ, những gì xảy ra trên mỗi đoạn, sẽ ở lại trên mỗi đoạn đó. Nếu chúng ta nhân 1100101010001111 với 11, điều này giống như việc đầu tiên phân tách 1100101010001111 thành
Rồi nhân từng thành phần riêng biệt với 11.
Gộp lại với nhau
Nói chung, hệ thống chứng minh kiến thức không tiết lộ hoạt động bằng cách đưa ra các mệnh đề về đa thức, đồng thời biểu thị các mệnh đề về đánh giá nền tảng: như chúng ta thấy trong ví dụ Fibonacci, F(X+2)-F(X+1)-F(X) = Z(X)*H(X) kiểm tra tất cả các bước tính toán Fibonacci. Chúng ta kiểm tra các mệnh đề về đa thức bằng cách chứng minh đánh giá tại điểm ngẫu nhiên. Kiểm tra tại điểm ngẫu nhiên này đại diện cho việc kiểm tra toàn bộ đa thức: nếu phương trình đa thức không khớp, khả năng nó khớp tại một tọa độ ngẫu nhiên cụ thể là rất
Chào mừng tham gia cộng đồng chính thức TechFlow
Nhóm Telegram:https://t.me/TechFlowDaily
Tài khoản Twitter chính thức:https://x.com/TechFlowPost
Tài khoản Twitter tiếng Anh:https://x.com/BlockFlow_News
@VitalikButerin
