[Chứng minh không có kiến thức] zk-SNARK (4) - Ràng buộc đa thức

Tiêu đề gốc: "Học zk-SNARK từ đầu (4) - Ràng buộc đa thức"
Nguồn gốc: Phòng thí nghiệm Amby Tác giả: Maksym Petkus

Giới thiệu

even@ Ambi Lab: Trong bài viết trước chúng ta đã học cách chuyển đổi chương trình thành đa thức để chứng minh. Lúc này có vẻ hơi choáng váng, bài viết này sẽ triển khai thêm các ràng buộc về giao thức và tối ưu hóa giao thức.

Tác giả: Maksym Petkus
Dịch và chú thích: Even@ Secbit Lab (even@secbit.io)
Hiệu đính : valuka@ Phòng thí nghiệm Anbi
Loạt bài này đã được tác giả cho phép dịch sang tiếng Trung.

Đánh giá

[Bằng chứng không có kiến thức] zk-SNARK (1) - Thuộc tính đa thức và bằng chứng

[Bằng chứng không có kiến thức] zk-SNARK (2) - Đa thức Non -bằng chứng không có kiến thức tương tác

[Bằng chứng không có kiến thức] zk-SNARK (3) - từ Chương trình xây dựng đa thức

Thuộc tính cấu trúc

Những sửa đổi trên còn mang lại một số thuộc tính hữu ích khác.

Hệ số tĩnh

Bật trong Khi xây dựng bài viết, chúng ta thu được 0 hoặc 1 bằng cách tính đa thức của biến chưa được gán để cho biết liệu biến này có nên được sử dụng trong phép tính hay không. Đương nhiên, chúng ta cũng có thể sử dụng các giá trị hệ số khác, bao gồm các giá trị âm, vì chúng ta có thể nội suy đa thức thông qua bất kỳ điểm cần thiết nào (với điều kiện là không có hai phép tính nào sử dụng cùng một x). Sau đây là một số ví dụ về thao tác này:



trong đó các chỉ số dưới l, r và o đại diện cho các biến vào vị trí trong hoạt động.

Lưu ý: Hệ số hằng số của cùng một biến có thể khác nhau trong các phép toán và toán hạng/đầu ra khác nhau.

Bổ sung miễn phí

Đang tìm kiếm Ở cấu trúc mới này, rõ ràng trong biểu diễn đa thức, toán hạng được biểu thị bởi mỗi x khác nhau là tổng của tất cả các đa thức biến toán hạng, trong đó chỉ có một trong số đó được sử dụng là khác 0 và các toán hạng còn lại là 0, hình sau đây thể hiện ý nghĩa này rất rõ:



Chúng ta có thể sử dụng cấu trúc này để thêm bất kỳ số lượng biến cần thiết nào vào toán tử /đầu ra của mỗi hoạt động. Ví dụ: trong thao tác đầu tiên, trước tiên chúng ta có thể cộng a+c, sau đó chỉ cần nhân nó với các toán hạng khác, tức là (a+ c) × b = r, có thể được biểu thị như hình sau:



Do đó, bạn cũng có thể nhân bất kỳ biến nào trong số này với bất kỳ hệ số nào rồi cộng chúng lại với nhau thành một toán hạng để xây dựng một giá trị toán hạng theo nhu cầu của chương trình tương ứng. Tính năng này thực tế cho phép thay đổi cấu trúc hoạt động thành:



Lưu ý: toán hạng của mỗi hoạt động có tập hệ số riêng c.

Chú thích

even@ Anby Lab: Phép nhân là chìa khóa và các phép tính cộng có thể được kết hợp thành một phép nhân lớn hơn.

Cộng, trừ và chia

Cho đến nay chúng ta đã tập trung vào các phép tính nhân. Nhưng để có thể thực hiện các phép tính tổng quát, các chương trình trong thế giới thực cũng cần có phép cộng, phép chia.

Bổ sung Trong chương trước, chúng ta đã xác định rằng các biến có thể được thêm vào trong nội dung của một toán hạng đơn lẻ và sau đó được thêm cùng với một toán hạng khác Một toán hạng được nhân, tức là (3a + b) × d = r, nhưng nếu chúng ta chỉ muốn thực hiện phép cộng mà không nhân, chẳng hạn, một chương trình cần thực hiện phép tính a + b, chúng ta có thể biểu diễn nó như sau cách: ( a+b) × 1 = r

@Maksym (tác giả): Bởi vì trong cấu trúc cho mỗi toán hạng, chúng ta cần cả hai Các hệ số không đổi cũng yêu cầu các biến (c ⋅ v). Giá trị 1 có thể được biểu thị dưới dạng c₁ ⋅ v₁, trong đó c₁ = 1 có thể được "mã hóa cứng" thành đa thức tương ứng. v₁ là một biến có thể được gán bất kỳ giá trị nào, khi đó chúng ta Cần giới hạn giá trị của v₁ thông qua một số ràng buộc, điều này sẽ được thảo luận trong các chương sau.

Phép trừ Phép trừ gần giống như phép cộng, điểm khác biệt duy nhất là hệ số âm a-b, đó là:



@Maksym (tác giả): Cấu trúc của các phép toán còn gọi là "ràng buộc", vì các phép toán được biểu diễn bằng cấu trúc đa thức không phải để tính toán kết quả, nhưng khi người chứng minh đã biết phép gán biến, nó sẽ kiểm tra xem quy trình thao tác có đúng hay không. Nói cách khác, bộ chứng minh ràng buộc phải cung cấp các giá trị nhất quán, bất kể các giá trị đó là gì.
Tất cả các phép tính số học (cộng, trừ, nhân và chia) đều đã có sẵn nên cấu trúc thao tác không cần phải sửa đổi nữa.

Chú thích

even@ Anbi Lab: Có một mối tương quan nhất định giữa các ràng buộc và hoạt động. Mục đích của mạch số học là đạt được "xác minh tính toán" chứ không phải là "quá trình tính toán".

Ở bài trước chúng tôi đã đề xuất một phương pháp: cứ để công việc xây dựng đa thức cho link thiết lập, người chứng minh chỉ cần điền vào Giá trị tương ứng là đủ. Phương pháp này không chỉ giải quyết vấn đề không nhất quán trong các toán tử có cùng toán hạng mà còn mang lại sự thuận tiện hơn nữa:

1) Cho phép hệ số tĩnh được đưa vào các biểu thức thực hiện các phép tính.

2) Mặc dù chỉ có phép nhân trong mối quan hệ l(x)·r(x)=o(x), hãy sử dụng cái này phương pháp Bạn cũng có thể dễ dàng thực hiện các phép tính cộng, nhờ đó giải được các bài toán trừ và chia.

Ví dụ tính toán

Với một tập hợp các cấu trúc phép toán chung, chúng ta có thể chuyển đổi chương trình ban đầu của mình (ví dụ ở bài viết trước) thành một tập hợp các phép toán rồi sang dạng đa thức. Trước tiên, chúng ta hãy nghĩ về dạng toán học của thuật toán (sử dụng biến v để biểu thị kết quả phép toán):



Để hiểu Tại sao w chỉ có thể là 0 hoặc 1? Chúng ta có thể biểu diễn phương trình dưới dạng w² – w = 0, nghĩa là (w – 0)(w – 1) = 0 trong đó 0 và 1 là nghiệm duy nhất.

Hiện có tổng cộng 5 biến, cũng như 2 toán tử bên trái, 4 toán tử bên phải và 5 kết quả đầu ra. Đa thức toán tử là:



Cốt truyện là:



Chúng ta sẽ chứng minh phép tính thông qua đa thức. Đầu tiên, chọn giá trị đầu vào của hàm, ví dụ: w = 1, a = 3, b= 2. Thứ hai, giá trị biến trung gian trong quá trình tính toán là:

m=a × b =6

v = w(m-a-b)+a+b=6

Sau đó, chúng tôi cộng tất cả các kết quả tính toán. giá trị cho đa thức biến, sau đó cộng nó để có dạng toán hạng hoặc đa thức đầu ra:



Trong hình, nó được biểu thị dưới dạng:



Thêm chúng để tạo thành toán hạng và xuất ra phép toán tương ứng Giá trị:



Ta cần chứng minh L(x) × R(x) – O (x) = t(x)h(x), vì vậy trước tiên chúng ta tìm h(x):



Biểu diễn dưới dạng đồ thị:



Ở đây rõ ràng là đa thức L(x ) × R(x) – Các nghiệm của O(x) là x= 1, x= 2 và x= 3 nên t(x) là thừa số của nó, trường hợp này không xảy ra nếu sử dụng các giá trị biến không nhất quán.

Đây là cách chứng minh một tập hợp các giá trị biến có thể tính toán chính xác ở cấp độ đa thức. Tiếp theo, người chứng minh sẽ tiếp tục xử lý phần mật mã của giao thức.

Giao thức điện toán có thể xác minh được

Chúng tôi đã thực hiện nhiều thay đổi quan trọng dựa trên giao thức kiến thức đa thức trước đó để làm cho nó linh hoạt hơn. Chúng ta hãy xem định nghĩa hiện tại của nó. Giả sử hàm f(*) là kết quả tính toán của bài toán cần chứng minh, trong đó số toán hạng là d, số biến là n và hệ số tương ứng là:

Với i ∈ {1, …, n} mọi đa thức biến đổi {lᵢ(x), rᵢ(x), oᵢ(x)} và đa thức đích t( Cài đặt của x) được gọi là chương trình số học nhị phân (QAP, được giới thiệu trong [Gen+12[1]]).

Mặc dù giao thức này đủ mạnh để xác minh phép tính thông thường nhưng vẫn có hai vấn đề cần cân nhắc về bảo mật cần được giải quyết.

Tính không giao hoán của toán hạng và kết quả đầu ra

Bởi vì chúng tôi sử dụng cùng một giá trị α trên tất cả các toán hạng trong kiểm tra ràng buộc đa thức biến đổi, nên không có cách nào ngăn chặn người chứng thực thực hiện hành vi gian lận sau:

Sử dụng đa thức biến đổi trong các toán hạng khác, nghĩa là L′(s) = o₁(s) + r₁(s) + r₁(s) + …

Hoàn thành phép toán trao đổi đa thức số, nghĩa là thay thế O(s) và L(s) bằng O(s) × R(s) = L(s)

Sử dụng lại cùng một đa thức toán hạng, tức là L(s) × L( s) = O(s)

Khả năng hoán đổi có nghĩa là người chứng minh có thể sửa đổi quá trình tính toán và chứng minh một cách hiệu quả một số kết quả tính toán không liên quan khác. Một cách rõ ràng để ngăn chặn hành vi này là sử dụng các α khác nhau trên các toán hạng khác nhau. Bạn có thể sửa đổi giao thức cụ thể thành:





Ghi chú

even@ Anbi Lab: Tại đây, bằng cách ghép cặp l(x), r(x) và o(x ) thực hiện các kiểm tra KEA riêng biệt , giải quyết lỗ hổng thứ hai được nêu trong bài viết trước - vì bằng chứng do Prover tạo ra chỉ chứa kết quả tính toán, toán hạng bên trái và toán hạng bên phải nên việc sử dụng hỗn hợp các kết quả đầu ra trong phép tính sẽ không bị phát hiện. .

Tương tự, phần sau cũng giải quyết lỗ hổng thứ ba được nêu trong bài viết trước - vì toán hạng bên trái, toán hạng bên phải và đầu ra được biểu diễn riêng biệt nên mối quan hệ giữa chúng không thể bị ràng buộc.

Tính nhất quán của biến trong các toán hạng

Đối với bất kỳ biến vᵢ nào, chúng ta phải gán giá trị của nó đến một đa thức biến tương ứng trong mỗi toán hạng tương ứng, cụ thể là:





Chú thích

even@ Anbi Lab: Hãy nhớ lại rằng ở trên chúng tôi đã đề xuất thiết lập các ràng buộc của biểu thức toán học trong giai đoạn thiết lập để giải quyết một số vấn đề, nhưng dường như có một vấn đề được đưa ra ở đây: Điều gì sẽ xảy ra nếu bằng chứng do người chứng minh xây dựng đảm bảo được tính toán bằng cách tuân theo các ràng buộc này?

KEA thực sự đã giải quyết được vấn đề này, nhưng có vẻ như nó chưa hoàn hảo. Đây là vấn đề về tính linh hoạt có thể thay đổi mà chúng ta sẽ thảo luận dưới đây.

Tính đa thức không thể mở rộng thay đổi và tính nhất quán thay đổi

Khả năng mở rộng của đa thức biến đổi

Để đưa ra ví dụ liên quan đến nhận xét 4.1, hãy xem hai thao tác sau:

Chú thích

even@ Ambi Labs: Khả năng này có thể gây nguy hiểm cho độ tin cậy của giao thức. Rõ ràng, các β được mã hóa sẽ không hiển thị với Prover.

Không dẻo

Một cách để giải quyết vấn đề về khả năng mở rộng là nhân mục βs được mã hóa trong khóa xác minh với giá trị bí mật ngẫu nhiên γ(gamma) trong giai đoạn thiết lập để làm cho nó không tương thích với giá trị Z được mã hóa:



Chúng ta cũng có thể giải bài toán tính dẻo của các đa thức biến đổi bằng cách sửa đổi số hạng αs. Nhưng điều này là không cần thiết, bởi vì bất kỳ sửa đổi nào đối với đa thức biến đổi cần phải được ánh xạ tới đa thức nhất quán của biến và không thể sửa đổi đa thức nhất quán.

Tối ưu hóa kiểm tra tính nhất quán của giá trị biến

Kiểm tra tính nhất quán của giá trị biến hiện đã hoạt động, nhưng tính năng này bổ sung thêm 4 thao tác ghép nối tốn kém và 4 mục mới trong khóa xác minh. Giao thức Pinocchio trong tài liệu [Par+13[2]] sử dụng một phương pháp rất thông minh để tối ưu hóa, bằng cách chọn các bộ tạo g khác nhau, từ đó "dịch chuyển" từng toán hạng:



Việc ngẫu nhiên hóa các trình tạo này làm tăng thêm tính bảo mật, làm mất hiệu lực tính linh hoạt của đa thức biến đổi như được mô tả trong nhận xét 4.1. Bởi vì để sửa đổi có chủ ý, nó phải là bội số của giá trị ban đầu của ρl, ρr hoặc ρo hoặc một giá trị được mã hóa không thể sử dụng trực tiếp (giả sử, như đã đề cập ở trên, rằng chúng ta không xử lý khả năng tái tạo bậc 0 có thể làm lộ ra giá trị được mã hóa) đa thức biến đổi).

Việc tối ưu hóa này làm giảm khóa xác minh đi hai mục và loại bỏ hai thao tác ghép nối trong bước xác minh.

Lưu ý: Có những cải tiến hơn nữa trong bài báo năm 2016 của Jens Groth [Gro16[3]].

Chú thích

even@ Anby Lab: Tại thời điểm này, việc xây dựng giao thức zk-SNARK chung gần như đã hoàn thành.

Điều này Bài viết có thể tóm tắt như sau:

Cách cộng các hệ số biến và cách thực hiện các phép tính cộng, trừ, nhân, chia trong giao thức

Giao thức đảm bảo tính không thể thay thế của toán hạng và kết quả đầu ra

Cách giao thức đảm bảo tính nhất quán của các biến trong các toán hạng

Cách giao thức xử lý các biến và biến không thể điều chỉnh được tính nhất quán

Tối ưu hóa kiểm tra tính nhất quán của các giá trị biến trong giao thức

Liên kết gốc
https://arxiv.org/pdf/1906.07221.pdf

https://medium.com/@imolfar/why-and-how- zk-snark-works-5-variable -polynomials-3b4e06859e30

https://medium.com/@imolfar/why-and-how-zk-snark-works-6-ver thể-computation-protocol- 1aa19f95a5cc

Tài liệu tham khảo
[Par+13]—Bryan Parno, Craig Gentry, Jon Howell và Mariana Raykova. Pinocchio: Tính toán gần như có thể kiểm chứng thực tế. Lưu trữ ePrint mật mã, Báo cáo 2013/279. https:// eprint.iacr.org/2013/ 279. 2013.
[Gen+12]—Rosario Gennaro, Craig Gentry, Bryan Parno và Mariana Raykova. Chương trình nhịp bậc hai và NIZK ngắn gọn không có PCP. Lưu trữ ePrint mật mã, Báo cáo 2012/ 215. https://eprint.iacr.org/2012/215. 2012.
[Gro16]—Jens Groth. Về kích thước của các đối số không tương tác dựa trên ghép nối. Lưu trữ ePrint mật mã, Báo cáo 2016/260. https ://eprint.iacr.org /2016/260.2016.

Liên kết nguồn:weixin.qq.com

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia