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

Tiêu đề gốc: "Học zk-SNARK từ đầu (3) - Từ chương trình đến xây dựng đa thức"
Nguồn gốc: Phòng thí nghiệm Amby Tác giả: Maksym Petkus

Giới thiệu

even@ Anbi Lab: Bài viết trước chủ yếu giới thiệu cách xây dựng giao thức chứng minh không có kiến thức cho đa thức. Bây giờ chúng ta sẽ bắt đầu khám phá cách xây dựng một giao thức tổng quát hơn. Phần này chủ yếu nói về cách chuyển một tập chứng minh tính toán thành đa thức để chứng minh. Trọng tâm của bài viết này chủ yếu bao gồm: tính chất số học của đa thức, nội suy đa thức, v.v.

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

Trước đây chúng tôi đã đưa ra ý tưởng về một giải pháp zk-SNARK đơn giản, chứa hầu hết các cơ chế bên trong của zk- SNARK. Bây giờ, chúng tôi tiếp tục cải tiến giải pháp để nó có thể thực hiện các chương trình không có kiến thức.

Tính toán

Hãy xem một chương trình đơn giản được viết bằng mã giả



Nhìn từ góc độ cao, chương trình này không liên quan gì đến các đa thức trong giao thức của chúng tôi. Bây giờ chúng ta cần tìm cách chuyển đổi chương trình thành đa thức. Bước đầu tiên là chuyển đổi chương trình sang ngôn ngữ toán học, việc này tương đối đơn giản. Câu lệnh có thể được biểu diễn dưới dạng sau (giả sử w là 0 hoặc 1):

f(w,a,b) = w(a · b)+(1-w)(a+b)

Thực thi calc(1, 4, 2) và đánh giá f (1, 4, 2) đều cho kết quả như nhau: 8. Nếu bạn thực thi calc(0, 4, 2) và f(0,4,2), bạn cũng có thể nhận được 6. Trong thực tế, chúng ta có thể biểu diễn bất kỳ dạng chương trình hữu hạn nào theo cách này.
Tiếp theo (ví dụ trên) chúng ta cần chứng minh rằng với biểu thức f(w,a,b), đầu vào là (1, 4 , 2), đầu ra là 8. Nói cách khác, chúng ta muốn kiểm tra đa thức:
w(a · b)+(1- w )(a+b) = 8

Ghi chú

even@ Anby Lab: Để tôi đoán xem, có thể dùng chương trình nào biểu diễn được bằng đa thức để chứng minh điều đó không ?

Phép tính cơ bản duy nhất

Mặc dù chúng ta đã chuyển chương trình sang dạng tính toán tổng quát thể hiện bằng ngôn ngữ toán học nhưng chúng ta vẫn cần chuyển nó sang dạng đa thức. Trước tiên chúng ta hãy xem xét kỹ hơn bản chất của tính toán. Cốt lõi của bất kỳ phép tính nào đều được tạo thành từ các phép toán cơ bản có dạng:



Hai toán hạng ( tức là giá trị ) được kết hợp với một toán tử (tức là +, –, ×, ) để thực hiện một thao tác. Ví dụ toán hạng là 2 và 3, toán tử là phép nhân thì phép toán là 2×3 = 6. Vì bất kỳ phép tính (hoặc chương trình) phức tạp nào đều bao gồm một loạt các phép toán cơ bản như vậy, trước tiên chúng ta cần biết cách biểu diễn một phép toán đơn lẻ trong một đa thức.

Tính chất số học của đa thức

Trước tiên chúng ta hãy xem cách liên hệ các đa thức với các phép tính số học. Ví dụ: có hai đa thức f(x) và g(x), hãy nhân chúng sao cho h(x) = f(x) × g(x).Kết quả tính của h(x) tại x= bất kỳ r Cả hai đều là tích của f(r) và g(r). Xét lại hai đa thức sau f(x) = 2x2 – 9x+ 10 và g(x) = – 4x2 + 15x – 9. Được trình bày bằng đồ họa:

Khi x = 1, f(1) = 2 – 9 + 10 = 3, g(1) = – 4 + 15 – 9 = 2. Nhân hai đa thức: h(x) = f(x) × g(x) = – 8x4 + 66x3 – 193x2 + 231x– 90. Kết quả của phép nhân có thể được nhìn thấy từ hình ảnh:

Khi x = 1, hãy tính f(x) × g(x ) Kết quả là: h(1) = – 8 + 66 – 193 + 231 – 90 = 6, nghĩa là khi x = 1 thì h(x) là kết quả của phép nhân f(x) và g(x ), Điều tương tự cũng đúng khi x nhận các giá trị khác.
Tương tự như vậy nếu chúng ta cộng f(x) và g(x), kết quả của x=1 là 5.

Lưu ý: Ở các giá trị xs khác, kết quả tính toán của phép cộng đa thức cũng là cộng giá trị của hai đa thức để Các kết quả cùng nhau, chẳng hạn bạn có thể kiểm chứng kết quả tại x=2, x=3.

Nếu chúng ta có thể biểu thị giá trị của toán hạng dưới dạng Đa thức (thực sự chúng ta có thể làm được điều này), sau đó sử dụng các tính chất số học, chúng ta có thể nhận được kết quả tính toán của toán hạng.

Chú thích

even@ Anbi Experiment Shi: Hãy nhớ lại rằng trong bài viết đầu tiên của loạt bài này - Tính chất và chứng minh của đa thức, chúng tôi đã từng nói rằng "kết quả tính toán của bất kỳ đa thức nào tại bất kỳ điểm nào cũng có thể được coi là biểu thức nhận dạng duy nhất của nó."

Ngược lại, khi biết một đa thức nào đó thì có nghĩa là ta biết giá trị của một điểm nào đó trên đa thức đó phải không? . Đây là cơ sở để hoàn thành chứng minh với sự trợ giúp của đa thức.

Các thao tác bị giới hạn

Nếu người chứng minh khẳng định tích của hai số thì người xác minh xác minh nó như thế nào? Để chứng minh tính đúng đắn của một phép tính đơn lẻ, trước tiên chúng ta phải đảm bảo rằng đầu ra (kết quả) của các toán hạng được cung cấp là chính xác. Chúng ta hãy xem hình thức của phép toán:

Đầu ra toán hạng bên phải của toán tử bên trái

Tương tự, chúng ta cũng có thể biểu diễn nó dưới dạng đa thức số học

l(x) toán tử r(x) = o(x)

Thao tác ở một số giá trị đã chọn a:

l(x)—biểu thị (kết quả của thao tác là) bên trái toán hạng

r(x)—biểu thị (kết quả của phép toán là) toán hạng bên phải

o(x)—biểu thị kết quả hoạt động (đầu ra)

Do đó, trong quá trình tính toán, nếu cả toán hạng và kết quả đều có thể được biểu diễn chính xác ở dạng đa thức thì có thể thiết lập được toán tử l(a) r(a) = o(a). Nghĩa là, nếu giá trị biểu thị bằng đa thức đầu ra o(x) là kết quả đúng thu được bằng phép nhân của toán tử trên các đa thức toán hạng l(x) và r(x), thì ta đặt đa thức đầu ra o (x) Đặt nó ở vế trái của phương trình và bạn nhận được: toán tử l(a) r(a) – o(a) = 0, điều này cũng cho thấy rằng khi giá trị là a, toán tử l(x) đa thức r(x) – o (x) có giá trị bằng 0. Khi đó, miễn là đa thức hợp lệ thì đa thức số học phải có nghiệm a. Do đó, theo cơ sở trước thì đa thức này phải chứa thừa số (x-a) (xem phần phân tích nhân tử), đây chính là đa thức đích ta muốn chứng minh, tức là t(x) = x – a.

Ví dụ: hãy xem xét một phép toán: 3×2=6

Nó có thể được biểu diễn bằng một đa thức đơn giản: l(x) = 3x, r(x) = 2x, o(x) = 6x, lấy a=1 để tính, nghĩa là: l(1 ) = 3; r(1) = 2; o(1) = 6.

Đa thức số học này trở thành:

l(x) × r(x) = o(x)

3x × 2x =6x span>

6x² -6x =0

tại The hình được biểu diễn dưới dạng:



Lưu ý rằng đa thức này có thừa số (x = 1):

span>

6x² -6x = 6x(x-1)

Vậy nếu người tục ngữ thay p(x) bằng các đa thức như l(x), r(x), o(x), vì chúng vẫn chia hết cho t(x) , người xác minh có thể coi chúng là hợp lệ. Ngược lại, nếu người kiểm chứng cố gắng sử dụng 4 thay vì giá trị đầu ra để đánh lừa người kiểm chứng, tức là o(x) = 4x, thì đa thức số học sẽ trở thành 6x2 – 4x= 0:



Đa thức trong hình không có nghiệm cho x=1, nên l(x) × r(x) – o( x) không thể giải bằng t(x) Tính chia hết:

Do đó người xác minh không thể chấp nhận kết quả tính toán không nhất quán này (như được mô tả trong phân tích nhân tử chương)

Chú thích

even@ Anbi Experiment Chamber: Trong giao thức trước, đa thức chúng ta muốn chứng minh là p(x) = t(x)h(x), ở đây chúng ta sửa đổi p(x) sao cho p(x) = l(x)r(x) -con bò đực). Ở đây t(x) nghiệm của đa thức đích là các giá trị của x tương ứng với biểu thức toán học có thể tính được.

Trong ví dụ trên, giá trị đặc biệt x=1 được sử dụng làm vị trí của mã hóa phép toán. Tất nhiên, 1 ở đây có thể được thay thế bằng bất kỳ giá trị nào khác, chẳng hạn như x=2, 3 hoặc 101, v.v. Trong các bài báo [GGPR] và [PHGR], giá trị này là một giá trị ngẫu nhiên được gọi là "root".

Bằng chứng hoạt động

Bây giờ, hãy sửa đổi giao thức mới nhất để hỗ trợ chứng minh phép tính nhân đơn. Quay lại chương SNARK trước về đa thức, chúng ta đã chứng minh được kiến thức về đa thức p(x), nhưng bây giờ chúng ta cần tính kiến thức về ba đa thức l(x), r(x), o(x). Chúng ta có thể định nghĩa p(x) = l(x) × r(x) – o(x), nhưng có hai điểm gây tranh cãi ở đây. Trước hết, trong giao thức của chúng tôi, giai đoạn chứng minh không thể thực hiện các phép tính nhân giá trị được mã hóa (tức là l(s) × r(s)), vì việc ghép nối chỉ có thể được sử dụng một lần và điều này phải được sử dụng để kiểm tra các ràng buộc của đa thức. Thứ hai, điều này tạo cơ hội cho người chứng minh sửa đổi cấu trúc đa thức nhưng vẫn giữ lại thừa số t(x) hợp lệ, ví dụ: đặt p(x) = l(x) hoặc p(x) = l(x) – r (x) hoặc thậm chí p(x) = l(x) × r(x) + o(x), miễn là p(x) ở đây vẫn giữ nguyên a. Sự sửa đổi này về cơ bản làm thay đổi nội dung của bằng chứng sang một tuyên bố khác, vì vậy điều này không được chấp nhận.

Vì vậy người chứng minh phải đưa ra bằng chứng về giá trị của các đa thức l(s), r(s), o(s) tương ứng, tức là sự phù hợp Kiến thức về đa thức cần chứng minh phải được sửa đổi. Những gì người xác minh xác minh trong không gian mật mã là l(s) × r(s) – o(s) = t(s)h(s). trình xác minh có thể sử dụng ghép nối mật mã để thực hiện phép nhân, nhưng có một vấn đề nhỏ là việc tính toán phép trừ (– o(x)) rất tốn kém (điều này đòi hỏi phải tìm một phép biến đổi nghịch đảo của gᵒ⁽ˢ⁾), ở đây chúng ta có thể đặt Move o (x) sang vế phải của phương trình: l(x)r(x) = t(x)h(x) + o(x). Trong không gian mã hóa, việc xác minh của người xác minh có thể được chuyển đổi thành:

e(gl(s), gr(s)) = e (gt(s),gh(s)) · e(go(s),g)

e(g,g ) l(s)r(s) =e(g,g)t(s)h(s) ·e(g,g)o(s)

e(g,g)l(s)r(s) =e(g,g)t(s)h(s)+o(s)

Lưu ý: Hãy nhớ rằng kết quả ghép nối được mã hóa hỗ trợ việc cộng các giá trị được mã hóa thông qua phép nhân, xem chương về phép nhân các giá trị được mã hóa

Giữ nguyên giai đoạn thiết lập và cập nhật giao thức thành:

Giao thức này có thể chứng minh rằng kết quả tính toán nhân hai giá trị ​là chính xác.

Bạn có thể nhận thấy rằng trong giao thức mới này, chúng tôi đã từ bỏ phần không có kiến thức. Điều này được thực hiện để đơn giản hóa các thay đổi giao thức. Trong các chương sau chúng ta sẽ trở lại kiến thức bằng không.

Chú thích

even@ Anby Lab: Trong ví dụ trên, giá trị đặc biệt x=1 được sử dụng làm vị trí của mã hóa phép toán. Tất nhiên, 1 ở đây có thể được thay thế bằng bất kỳ giá trị nào khác, chẳng hạn như x=2, 3 hoặc 101, v.v. Trong các bài báo [GGPR] và [PHGR], giá trị này là một giá trị ngẫu nhiên được gọi là "root".

Nhiều thao tác

Bây giờ chúng ta có thể chứng minh một phép tính số học, làm cách nào để mở rộng nó thành nhiều phép tính (đó là mục tiêu cuối cùng của chúng ta)? Hãy thử thêm một thao tác cơ bản. Hãy xem xét nhu cầu tính tích của a × b × c. Trong mô hình phần tử, điều này thể hiện hai phép toán:

a × b = r1

r1 × c = r2

Trong phần thảo luận trước, chúng ta đã tính giá trị tương ứng cho đa thức toán tử ở bất kỳ giá trị x nào, chẳng hạn như 1, để biểu thị một toán hạng hoặc kết quả. Các đa thức có thuộc tính này không ràng buộc chúng ta sử dụng đa thức để biểu diễn các giá trị khác ở các giá trị khác nhau của x. Chẳng hạn như 2 trong ví dụ, đó là:



Tính độc lập này cho phép chúng ta thực hiện hai thao tác tại cùng một lúc Và cả hai sẽ không nhầm lẫn, tức là sẽ không cản trở nhau. Kết quả của phép tính đa thức này trở thành:



Có thể thấy đa thức này có hai nghiệm x = 1 và x=2. Do đó, cả hai phép tính đều được thực hiện chính xác.

Chú thích

even@ Anbi Experiment Phòng: Để dễ hiểu, hai vị trí x=1 và x=2 được chọn trong ví dụ ở đây. Hãy nhớ rằng trong sơ đồ zkSNARK hoàn chỉnh, các giá trị "gốc" này phải là số ngẫu nhiên trong một miền giới hạn, nếu không các lỗ hổng bảo mật sẽ xuất hiện.
Hãy xem ví dụ về ba phép nhân 2 × 1 × 3 × 2, được thực hiện theo các bước sau:

2 × 1 = 2
2 × 3 = 6
6 × 2 = 12

Chúng tôi muốn biểu diễn chúng dưới dạng đa thức toán hạng. Đối với phép tính được biểu thị bằng x ∈ {1, 2, 3}, l(x) phải bằng 2, 2 và 6 tương ứng. Nghĩa là, qua các điểm (1, 2), (2, 2), (3, 6) cùng r(x) ∋ (1, 1), (2, 3), (3, 2), o (x) ∋ (1, 2), (2, 6), (3, 12).

Nhưng làm thế nào để tìm được đa thức đi qua những điểm này? Đối với bất kỳ ví dụ nào có nhiều hơn một điểm, phải sử dụng các phương pháp toán học cụ thể.

Nội suy đa thức

Để xây dựng các toán hạng và đa thức đầu ra, chúng ta cần một cách sử dụng một tập hợp các điểm cho trước để xây dựng một đa thức cong đi qua tất cả các điểm này. Điều này được gọi là phép nội suy. Có một số cách khác nhau để tìm đa thức này:
Một tập hợp các phương trình chưa biết

Đa thức Newton

Thuật toán Neville

Đa thức Lagrange

Biến đổi Fourier nhanh

Hãy lấy phương pháp đầu tiên làm ví dụ. Ý tưởng của phương pháp này là tồn tại một đa thức cụ thể p(x) với các hệ số và bậc không xác định nhiều nhất là n có thể đi qua n+1 điểm cho trước. Với mỗi điểm {(xᵢ, yᵢ)}, i ∈ [ n +1] thì kết quả của đa thức tại xᵢ bằng yᵢ, tức là với mọi i, p(xᵢ) = yᵢ. Trong ví dụ của chúng ta, ba điểm chuyển thành đa thức bậc 2 được biểu thị dưới dạng: ax2 + bx +c =y.

Chúng ta cho đa thức bên trái (được đánh dấu màu xanh lá cây) bằng kết quả đa thức tại mọi điểm, sau đó biểu thị từng hệ số theo các số hạng khác. sau đó tính phương trình:

Vậy đa thức toán hạng bên trái là:
l(x) = 2x2-6x+6

Giống nhau như sau Hình ảnh tương ứng với:

Chúng ta tính r(x) và o(x) theo cách tương tự:

Đa thức có nhiều phép toán

Bây giờ chúng ta đã có các đa thức toán hạng biểu thị ba phép tính, chúng ta hãy xem xét kỹ hơn cách xác minh tính đúng đắn của mỗi phép tính. Quay lại quá trình người kiểm tra tìm phương trình l(x) · r(x) – o(x) = t(x)h(x). Trong ví dụ này, vì phép tính được biểu thị tại các điểm x ∈ {1, 2, 3} nên đa thức đích phải có giá trị bằng 0 tại các điểm xs này, nói cách khác, nghiệm của t(x) phải bằng 1, 2 và 3. Dạng cơ bản của nó là:



Bước đầu tiên là thay đổi l( Multiply x) và r(x) để nhận kết quả:

Bước 2: Từ l(x) × Trừ o(x) từ kết quả của r(x):

Bạn đã có thể xem từng toán hạng ở đây Phép nhân tất cả tương ứng với kết quả đúng. Chứng minh bước cuối cùng là tính hệ số hợp lệ:

Nó có thể được tính bằng phép chia dài:

Thay h(x) = – 3x+ 4a, verifer tính được t(x)h(x):

Bây giờ rõ ràng l(x) × r(x) – o(x) = t(x)h(x), đó là điều ta muốn chứng minh.

Chú thích

even@ Anbi Lab: Ở đây ta chỉ cần một tập đa thức l(x), r(x), o(x) để kết hợp tất cả các phép tính mối quan hệ ràng buộc được thể hiện và một số phép tính tương ứng với số lượng nghiệm của đa thức đích t(x).

Giao thức hiện tại dường như có một số sai sót. Đa thức chỉ có thể chứng minh rằng người chứng minh có một tập hợp đa thức l(x ), r(x), o(x), tại các giá trị của một số nghiệm của t(x) l(x)·r(x) = o(x), không thể chứng minh được tập đa thức này thỏa mãn đối với biểu thức toán học mà chúng ta muốn chứng minh. ：
1) Nhiều mối quan hệ tính toán cũng được thể hiện riêng biệt và không thể hạn chế mối quan hệ giữa các công thức tính toán này .
2) Do phép chứng minh do Prover tạo ra chỉ chứa kết quả tính toán nên toán hạng bên trái, toán hạng bên phải và kết quả đầu ra sẽ không bị phát hiện nếu chúng được trộn lẫn trong phép tính
3) Vì toán hạng bên trái, toán hạng bên phải và đầu ra được biểu thị riêng biệt nên mối quan hệ giữa chúng không thể bị ràng buộc .

Đa thức biến

Với phương pháp đã giới thiệu ở trên để giải bài toán chứng minh nhiều đa thức tính toán, chúng ta có thể chứng minh nhiều phép tính (chẳng hạn như hàng triệu hoặc nhiều hơn) cùng một lúc, tuy nhiên giải pháp này có một nhược điểm chính.

Nếu "chương trình" được thực thi trong bằng chứng sử dụng cùng các biến như toán hạng hoặc kết quả đầu ra trong các phép toán khác nhau, ví dụ: span>

a × b = r1

a × c = r2

Ở đây a đại diện cho đa thức toán tử bên trái trong hai phép toán, chẳng hạn như:

Tuy nhiên, vì giao thức của chúng tôi cho phép người chứng minh đặt bất kỳ hệ số nào cho đa thức nên anh ta không bị hạn chế đối với các phép tính khác nhau (tức là sử dụng một số x biểu thức Đa thức) được đặt các giá trị khác nhau cho a, cụ thể là:



Sự tự do này phá vỡ tính nhất quán , vẫn có chỗ cho phép người chứng minh phải chứng minh một số việc thực thi chương trình không liên quan khác mà người xác minh không quan tâm. Vì vậy, chúng ta phải đảm bảo rằng mỗi biến chỉ có một giá trị ở bất kỳ nơi nào nó xuất hiện trong tất cả các thao tác.

Lưu ý: Các biến trong bài viết này khác với định nghĩa về các biến trong khoa học máy tính thông thường. Các biến ở đây là bất biến và phải được thực hiện mỗi lần Chúng chỉ được chỉ định một lần.

Chú thích

even@ Anbi Lab: Hãy chú ý đến định nghĩa của "biến", là một biến trong chương trình, nhưng không thể thay đổi. Điều này có mâu thuẫn không? Trên thực tế, các biến ở đây đề cập đến các biến trong mã giả mẫu ở đầu bài viết này sẽ không được sửa đổi. Trong bài báo zkSNARK, "biến" này thực sự có một danh từ tương ứng gọi là phép gán, là "sự gán" của một mạch số học. Tất cả các bài tập đều là lời giải cho bài toán thỏa mãn của mạch số học, bao gồm các giá trị đầu vào của mạch số học và các giá trị kết quả trung gian đầu ra trong quá trình hoạt động của mạch.

toán hạng đa thức của một biến duy nhất

Hãy xem một ví dụ đơn giản (ví dụ hiện tại). Trong số tất cả các toán hạng bên trái được biểu thị bằng đa thức toán tử bên trái l(x), chỉ Chứa a biến (tức là a). Chúng tôi muốn tìm hiểu xem có cách nào để đảm bảo rằng a giống nhau trong mọi phép toán của đa thức này hay không. Người chứng minh có thể đặt các giá trị khác nhau vì nó có thể tùy ý điều khiển các hệ số lũy thừa của x. Vì vậy, nếu các hệ số này cố định thì bài toán có thể được giải quyết.

Chúng ta hãy xem xét kỹ hơn các đa thức chứa các giá trị bằng nhau. Ví dụ: kiểm tra hai đa thức sau, mỗi đa thức biểu thị các phép toán tương ứng với hai giá trị bằng nhau (nghĩa là tại x=1 và x=2). Giá trị của đa thức thứ nhất ở đây là 1 và giá trị của đa thức thứ hai đa thức là 1. là 2:

Lưu ý rằng các hệ số tương ứng trong mỗi đa thức tỷ lệ thuận với nhau, tức là hệ số của đa thức thứ hai là Đa thức thứ nhất lớn gấp đôi, đó là:

2x2-6x+6=2×(x2 -3x+ 3) span>

Rồi do tính chất số học của đa thức nên nếu chúng ta muốn thay đổi tất cả các giá trị trong đa thức đồng thời chúng ta cần thay đổi tỷ lệ của nó. Nếu chúng ta nhân một đa thức với một số và kết quả ở mọi x có thể phải được nhân với cùng một số (tức là được biến đổi theo tỷ lệ). Để kiểm tra điều này, hãy thử nhân đa thức đầu tiên với 3 hoặc một số số khác.

Do đó, nếu người xác minh cần buộc người chứng minh đặt cùng một giá trị trong tất cả các phép tính, điều đó sẽ hạn chế người chứng minh chỉ sửa đổi thang đo thay vì hệ số đơn.

Vậy làm thế nào để giữ tỷ lệ hệ số không thay đổi? Đối với câu hỏi này, trước tiên chúng ta có thể nghĩ về cách chứng minh chúng ta đưa ra trong phép toán đa thức bên trái. là giá trị được mã hóa của l(x) tại một số giá trị bí mật s: gl(s), tức là một số được mã hóa. Chúng ta đã biết từ phần Hạn chế đa thức cách sử dụng phép biến đổi α để hạn chế người chứng minh chỉ sử dụng lũy thừa của s do người xác minh cung cấp để thực hiện các phép tính, sao cho một thao tác đơn lẻ có thể thỏa mãn phép nhân đồng cấu.

Tương tự như việc giới hạn một giá trị lũy thừa, người xác minh có thể giới hạn một đa thức hoàn chỉnh cùng một lúc. Thay vì chỉ cung cấp các mã hóa riêng lẻ và các dịch chuyển α gs1,gs2,…,gsd,gαs1,gαs2,…,gαsd của chúng.

Sau đó, quy trình thỏa thuận là:



prover cần trả về cùng một mối quan hệ chuyển đổi α, vì không thể khôi phục α từ khóa chứng minh, nên cách duy nhất để duy trì phép chuyển đổi này là nhân hai giá trị được mã hóa có cùng giá trị: gl(s) và gαl(s). Chứng thức này không thể sửa đổi một hệ số duy nhất của l(x). Ví dụ: nếu đa thức là l(x) = ax2 + bx+ c, chứng thức chỉ có thể sử dụng một giá trị v để sửa đổi toàn bộ đa thức: v⋅(ax2 + bx+ c) = v ⋅ax2 + v⋅bx+ v⋅c. Việc ghép nối làm cho không thể nhân với một đa thức khác, do đó nó không thể cung cấp một phép biến đổi lũy thừa α của s. Người chứng minh không thể thực hiện phép cộng hoặc phép trừ vì:



Ở đây cũng cần có kiến thức về α không được mã hóa.

Bây giờ chúng ta đã có giao thức này, làm thế nào để xây dựng đa thức toán hạng l(x)? Vì bất kỳ số nguyên nào cũng có thể nhân với 1 nên mọi phép tính tương ứng trong đa thức sẽ cho kết quả là 1, nghĩa là:



Sau đó để người tục ngữ gán "giá trị a trên đó:

Ghi chú 4.1 Vì khóa xác minh chứa α được mã hóa, bạn có thể sử dụng đa thức để cộng (hoặc trừ) bất kỳ giá trị v' nào, đó là:



Do đó, có thể sửa đổi đa thức ngoài những gì người xác minh mong đợi và chứng minh một tuyên bố khác. Chúng ta sẽ giải quyết vấn đề này trong chương sau.

Chú thích

even@ Anbi Lab: Phần này nhằm giải quyết vấn đề một dây đầu vào hoặc dây đầu ra trong mạch số học có thể đóng vai trò là nhiều cổng cùng một lúc .. Nhập dây, câu hỏi làm thế nào để đảm bảo rằng các dây công cộng này bị hạn chế.

Vì các biểu thức toán học cần chứng minh là công khai nên các mối quan hệ ràng buộc giữa các phép tính khác nhau cũng được công khai. , nên chúng ta có thể giao công việc xây dựng đa thức cho link setup, để người chứng minh chỉ cần điền các giá trị tương ứng.

Phương pháp trên giới hạn việc sử dụng cùng một đa thức toán hạng trong các công thức tính toán khác nhau. Một ràng buộc về một giá trị; tương tự nếu nhiều giá trị được sử dụng trong đa thức toán hạng, tất cả chúng có thể được cộng lại với nhau, như mô tả bên dưới.

Đa thức toán hạng nhiều biến

Bởi vì chúng ta chỉ có thể đặt giá trị khi tất cả toán hạng bên trái sử dụng cùng một biến. Nhưng phải làm gì nếu có một giá trị d khác trong toán hạng bên trái:

Nếu vẫn sử dụng cùng một phương pháp, chúng tôi không thể Bạn phải đặt giá trị riêng cho từng biến và nhân chúng lại với nhau. Nói cách khác, đa thức hạn chế này chỉ có thể hỗ trợ một biến. Chúng ta có thể chia đa thức toán hạng l(x) thành đa thức biến đổi của toán hạng



Đây là giống như phần trước Phương thức của phần giống nhau, các biến a và b có thể được gán và ràng buộc riêng biệt, sau đó được cộng lại với nhau để biểu diễn tất cả các biến toán hạng bên trái. Vì chúng ta cộng các đa thức biến đổi của các toán hạng với nhau nên chúng ta cần có khả năng đảm bảo rằng kết quả của phép cộng chỉ đại diện cho một trong tất cả các đa thức toán tử trong mỗi phép tính.

Với thuộc tính số học này, chúng ta có thể xây dựng từng đa thức biến toán hạng, sao cho nếu đa thức biến được sử dụng theo cách tương ứng hoạt động Là một toán hạng, mục này được đặt thành 1, nếu không thì được đặt thành 0. Kết quả của việc nhân 0 và bất kỳ giá trị nào bằng 0 và mục này có thể bị bỏ qua khi cộng chúng lại với nhau. Trong ví dụ của chúng tôi, các đa thức biến đổi này phải thỏa mãn các phép tính sau:

la(1) =1, la(2)=1, la (3)=0

ld(x)=0, ld(2)=0, ld(3)=1

Được thể hiện trong hình:



Vì vậy, chúng ta có thể đặt giá trị của từng biến riêng biệt, sau đó cộng chúng lại với nhau để tính đa thức toán hạng, ví dụ khi a = 3 và d= 2:

Lưu ý: Chúng tôi sử dụng chỉ số dưới sau một giá trị để biểu thị biến mà nó đại diện. Ví dụ: 3a là một biến được khởi tạo bằng 3.

Từ bây giờ chúng ta sử dụng chữ in hoa để biểu diễn đa thức toán tử phức tạp này, đó là

L(x) = ala(x) + dld(x)

Tính toán Kết quả là L, tức là L=L(s). Kết quả chỉ hợp lệ nếu đa thức biến đổi của mỗi toán hạng bị hạn chế bởi trình xác minh. Sự tương tác liên quan đến đa thức bên trái phải được thay đổi tương ứng:



Lưu ý: L(s) và αL(s) đại diện cho tất cả các đa thức biến đổi và vì α chỉ được sử dụng để tính các đa thức biến đổi nên người chứng minh không có lựa chọn nào khác ngoài việc cung cấp nó trong phần thiết lập. giá trị mã hóa ban đầu và giá trị mã hóa chuyển đổi được gán cùng hệ số để tính toán.

Kết quả, người chứng minh:

Ngoài việc "gán" các giá trị, không thể sửa đổi các hệ số của chúng và từ đó sửa đổi các đa thức biến đổi được nữa, bởi vì người chứng minh chỉ nhận được các giá trị được mã hóa của các đa thức này và vì các giá trị được mã hóa của s thành sức mạnh cần thiết không thể được sử dụng cùng với các giá trị biến đổi α của chúng

Không thể cung cấp kết quả bằng cách thêm một đa thức khác vì khi đó mối quan hệ tỷ lệ alpha sẽ bị phá hủy

Không thể sửa đổi đa thức toán hạng bằng cách nhân nó với một số đa thức u(x) khác, điều này có thể làm cho giá trị được sửa đổi không cân xứng do ghép nối trước Phép nhân được mã hóa không thể được thực hiện trong không gian

Lưu ý: Nếu chúng ta cộng (hoặc trừ) một đa thức, chẳng hạn như la(x), nó trở thành một đa thức khác, đó là

l'd(x) = cd·ld (x)+c'a·la( x)

Đây không phải là một biến thể của đa thức ld(x), mà là một thay đổi hệ số thu được của la(x), vì cuối cùng chúng sẽ được cộng lại với nhau:

L(x)=ca·la (x)+l'd(x) =(ca +c'a)·la(x)+cd·ld(x)

Tuy nhiên, mặc dù người chứng minh bị hạn chế sử dụng đa thức, Anh ta cũng có một số mức độ tự do trong phạm vi cho phép:

Khi người chứng minh quyết định không thêm một số đa thức biến lᵢ(x) vào cấu trúc. Toán tử đa thức L(x) vẫn được chấp nhận vì điều này giống như gán cho nó giá trị 0:

gala(x) = gala(x)+0ld(x)

Đó là cũng có thể chấp nhận được nếu người chứng minh thêm cùng một biến đa thức nhiều lần Bởi vì điều này cũng giống như việc gán tổng của nhiều giá trị cùng một lúc:

gala(x) · gala(x) · gala(x )= g3ala(x)

Các phương thức này cũng hoạt động ở bên phải toán hạng và toán hạng đầu ra R(x), O(x) Áp dụng tương tự.

Chú thích

even@ Ambi Lab: Tóm tắt ý tưởng chung của giao thức chứng minh trong bài viết này:
Chuyển đổi chương trình cần chứng minh thành một dạng biểu thức ngôn ngữ toán học (tức là các phép tính cộng, trừ, nhân và chia)
Sử dụng giá trị của đa thức ở đâu đó để thực hiện các phép tính nhằm biểu thị các phép tính toán học rồi chứng minh span>
Sử dụng các giá trị của đa thức ở nhiều nơi để thực hiện các phép tính nhằm biểu diễn nhiều phép toán, sau đó chứng minh chúng
Các ràng buộc trên cùng một biến được sử dụng bởi "chương trình" đã được chứng minh trong các phép tính khác nhau
Chỉ hạn chế giao thức hiện tại Một số vấn đề đã được giải quyết nhưng vẫn còn nhiều lĩnh vực cần cải thiện. Trong phần tiếp theo, chúng ta sẽ thảo luận về những cải tiến này và tối ưu hóa giao thức chứng minh.

Liên kết gốc
https://arxiv.org/pdf/1906.07221.pdf
https://medium.com/@imolfar/why-and-how-zk-snark-works-4-general-Purpose-computation-dcdc8081ee42
https: //medium.com/@imolfar/why-and-how-zk-snark-works-5-variable-polynomials-3b4e06859e30

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