Giới thiệu

Trong bài đăng trước, chúng tôi đã giới thiệu khái niệm về SNARK và các thuộc tính cơ bản cần có. Với mục tiêu chính của loạt bài đăng này, cụ thể là: cách xây dựng zk-SNARK cho bất kỳ phép tính nào, chúng tôi giới thiệu trong bài đăng này cách tạo SNARK để chứng minh kiến ​​thức về đa thức. Chúng tôi sẽ thực hiện từng bước một, bắt đầu từ một công trình không đáp ứng tất cả các yêu cầu và kết thúc một giao thức sẽ là một SNARK không có kiến ​​thức “đầy đủ”.

ZK-SNARK cho đa thức

Chúng tôi sẽ từng bước xây dựng zk-SNARK, bắt đầu từ một công trình đơn giản hơn không phải là SNARK, sau đó cải tiến nó bằng các kỹ thuật mới cho đến khi chúng tôi đạt được mục tiêu của mình.

Bước đầu tiên: bổ đề Schwartz — Zippel

Chúng tôi muốn tạo một giao thức cho phép người chứng minh P thuyết phục người xác minh V về kiến ​​thức của một đa thức bậc n cụ thể với các hệ số trong trường hữu hạn F. Nói cách khác, P muốn thuyết phục V rằng anh ta biết một đa thức có dạng

Giả sử rằng a_1, a_2, … , a_n ∈ F là n nghiệm của đa thức này, do đó p(x) có thể viết là

Giả sử rằng V biết d < n nghiệm của đa thức p(x).

Sau đó, chúng ta có thể trình bày lại bài toán của mình: bây giờ P muốn chứng minh với V rằng anh ta biết một đa thức h(x) sao cho

Đa thức t(x) sẽ được gọi là đa thức đích. Quan sát rằng nó có dạng

Phiên bản đầu tiên của zk-SNARK của chúng tôi dựa trên bổ đề Schwartz — Zippel: cho F là một trường và f: F^m → F là đa thức nhiều biến bậc n. Khi đó, với mọi tập hữu hạn S ⊆ F:

Bổ đề chỉ ra rằng nếu chúng ta lấy u ∈ Sm đều một cách ngẫu nhiên, xác suất để u là một tập nghiệm của f nhiều nhất là n / |S|. Quan sát rằng xác suất này là rất nhỏ nếu chúng ta coi S là trường hữu hạn F. Kích thước trường sẽ rất lớn so với n.

Nó có vẻ mâu thuẫn nhưng bổ đề này cho phép chúng ta chứng minh tri thức về một đa thức f. Chúng ta không cần chứng minh rằng mình biết tất cả các hệ số của p mà chỉ cần biết cách tính cặp (s, f(s)) cho bất kỳ s ∈ Fm. Bổ đề Schwartz — Zippel cung cấp hiệu quả cần thiết trong zk-SNARK của chúng ta.

giao thức đầu tiên

Ta nhớ lại rằng P biết đa thức p(x) và V biết d < n nghiệm của p(x) hoặc tương đương, V biết đa thức đích t(x). P cũng biết t(x).

Cách tiếp cận đầu tiên của chúng tôi như sau:

1. V lấy một giá trị ngẫu nhiên s và tính t = t(s). V gửi s cho P.
2. P tính đa thức

4. V kiểm tra xem đẳng thức p = t · h.

Giao thức này đúng vì nếu P biết đa thức p(x), anh ta có thể tính h(x) và do đó P cũng có thể tính các giá trị h và p sao cho p = h · t. Mặt khác, giao thức này cũng hiệu quả do bổ đề Schwartz — Zippel.

Tuy nhiên, giao thức này không mạnh vì người chứng minh có thể tính toán t = t(s) bằng cách sử dụng đa thức đích, ngay cả khi P không biết p(x),. Anh ta có thể lấy h ngẫu nhiên và tính toán p = h · t và gửi cặp (h, p) cho V, người sẽ chấp nhận cặp đó là hợp lệ.

Chúng tôi quan sát thấy rằng điểm quan trọng cho phép P đánh lừa V là P biết điểm đánh giá s. Thủ thuật này sẽ không thể thực hiện được nếu P có thể đánh giá p mà không biết điểm đánh giá s. Điều này dẫn chúng ta đến bước thứ hai: che giấu đồng hình hoặc che giấu đồng hình.

Bước thứ hai: xáo trộn đồng hình

Để làm cho giao thức của chúng tôi trở nên mạnh mẽ, chúng tôi cần có khả năng đánh giá một đa thức trên một điểm mà không cần biết điểm đó.

Chúng tôi sẽ làm như vậy dựa trên độ khó của vấn đề logarit rời rạc. Đối với một máy tính cổ điển, bài toán logarit rời rạc là không khả thi về mặt tính toán: trong một nhóm tuần hoàn G, cấp p và được tạo bởi một phần tử g, xác định một phần tử a sao cho = ga (mod p) với đã biết.

Vì vậy, giả sử độ cứng của đa thức logarit rời rạc, chúng ta có thể làm xáo trộn giá trị a bằng cách tính = ga (mod p). Một người nhận một mình không thể học được giá trị a. Điểm thú vị của kỹ thuật này là phép lũy thừa có một số tính chất đồng cấu:

Tích của hai giá trị bị xáo trộn cũng giống như phép xáo trộn của phép cộng các giá trị liên quan một cách rõ ràng.

Nếu chúng ta muốn đánh giá một đa thức

trên một điểm x = s mà không cho người đánh giá biết điểm chính xác, chúng ta cần xáo trộn toàn bộ đa thức:

Chúng ta cũng cần tính lũy thừa, từ 1 đến bậc của đa thức, của tất cả các giá trị bị xáo trộn đối với x = r, nghĩa là:

Quan sát rằng với tất cả các yếu tố này, bây giờ chúng ta có thể tính toán đánh giá khó hiểu của đa thức p trên một điểm x = r. Thực vậy:

Ví dụ về ẩn đồng cấu

Hãy coi trường hữu hạn F = ℤ127 và g = 3 là một máy phát. Giả sử rằng P biết đa thức p(x) = 4x2 + 3x + 1 và V muốn P đánh giá đa thức ở điểm x = 2 mà không cho P biết điểm đó. Chúng ta có thể làm điều đó thông qua các bước sau:

1. V tính tất cả các lũy thừa của x = 2 từ 0 đến bậc của đa thức, n = 2:

1.b. 32 (chế độ 127) = 9

1.c. 34 (chế độ 127) = 81

và gửi cặp (9, 81) cho P.

2. P có thể tính toán đánh giá của p(x) trên x = 2 mà không cần biết giá trị của x, trên thực tế, bằng cách sử dụng thông tin nhận được từ V, anh ấy có thể tính toán:

giao thức thứ hai

Bây giờ chúng ta đã biết cách làm xáo trộn các điểm để người chứng minh có thể đánh giá đa thức trên điểm đã làm xáo trộn đó, chúng ta sẽ cải thiện giao thức đầu tiên. Ta nhớ lại rằng P biết đa thức p(x) và V biết d < n nghiệm của p(x) hoặc tương đương, V biết đa thức đích t(x). P cũng biết t(x).

Giao thức thứ hai của chúng tôi như sau:

1. V lấy một giá trị ngẫu nhiên s và tính t = t(s).
2. V tính toán và gửi cho P các lũy thừa sau:

4. Sử dụng các giá trị , P tính toán g^p = g^{p(s)} và g^h = g*{h(s)} bằng cách sử dụng hướng dẫn của ví dụ trước.

5. P gửi g^p và g^h cho V.

6. V kiểm tra xem đẳng thức sau có đúng không: g^p = (g^h)^t

Quan sát rằng lỗ hổng được phát hiện trong giao thức đầu tiên đã được sửa đổi, nhưng giao thức thứ hai này vẫn chưa mạnh mẽ. Thật vậy, P vẫn có thể sử dụng các giá trị zp và zh sao cho z_p = (z_h)^t và gửi chúng tới V như thể chúng là g^p và g^h. P có thể làm như vậy bằng cách lấy một r ngẫu nhiên, tính toán z_h = g^r và đặt z_p = (g^t)^r. Giá trị z_p có thể được tính bằng cách sử dụng các quyền hạn bị xáo trộn do V gửi.

Để tránh tình trạng này, chúng ta cần đảm bảo rằng g^p và g^h được tính chỉ bằng cách sử dụng các lũy thừa bị xáo trộn do V gửi.

Bước thứ ba: giả định kiến ​​thức về số mũ

Có một giả định phổ biến khi định nghĩa một SNARK: chúng ta hãy xem xét một số nguyên tố q sao cho 2q + 1 cũng là một số nguyên tố. Chúng ta hãy xem xét trình tạo ga của ℤ_{2q + 1}. Cho q, g và g' = g^, chúng ta muốn tìm một cặp (x, y) sao cho x ≠ g, y ≠ g' và y = x^. Giả định tri thức về số mũ (KEA) nói rằng cách duy nhất để tìm cặp (x, y) là lấy một giá trị c ∈ ℤ_q, trước tiên tính x = g^c rồi lấy y = (g')^ c.

KEA có nghĩa là nếu một người muốn lấy cặp (x, y), cách duy nhất để làm điều đó là biết một số mũ c sao cho x = g^c. Nói cách khác, chúng ta chỉ có thể nhận được cặp (x, y) với thuộc tính KEA bằng cách sử dụng lũy ​​thừa của g.

Sử dụng KEA, giao thức bên dưới đảm bảo rằng P trả về một lũy thừa cụ thể của g, một trình tạo nhóm con cấp số nhân, được phân phối bởi V:

1. V lấy một giá trị ngẫu nhiên và tính g' = g^ (mod 2q + 1).
2. V gửi cặp (g, g') cho P và yêu cầu một cặp (b, b') sao cho (b, b') = (g, g').
3. P lấy một giá trị c và tính b = g^c (mod 2q + 1), b' = (g')^c (mod 2q + 1) và gửi cặp (b, b') đến V.
4. V kiểm tra xem b' = b^ (mod 2q + 1) hay không.

P đã sử dụng cùng một công suất c cho cả g và g' và anh ta chỉ có thể sử dụng các giá trị do V cung cấp.

giao thức thứ ba

Chúng tôi đã sẵn sàng xây dựng một giao thức phù hợp để đảm bảo rằng trình tự P sẽ tạo ra các lũy thừa của giá trị s trên miền bị xáo trộn.

1. V lấy một giá trị ngẫu nhiên s và tính t = t(s).
2. V lấy một giá trị ngẫu nhiên và tính t( · s).
3. V tính toán chuỗi các giá trị bị xáo trộn sau đây và gửi chúng cho P.
4. V tính toán chuỗi giá trị bị xáo trộn sau đây

5. P tính đa thức h(x).

6. Sử dụng , P tính toán p(s) và h(s) cùng với g^p = g^{p(s)} và g^h = g^{h(s)}.

7. Sử dụng , P tính p(s) và h(s) cùng với g^{p'} = g^{p( · s)}.

8. P gửi g^p, g^h và g^{p'} cho V.

9. V kiểm tra xem P có thực hiện tính toán các giá trị bị xáo trộn chỉ bằng cách sử dụng thông tin mà anh ta đã gửi cho mình hay không. Để làm như vậy, V kiểm tra xem g^p = g^{p'}.

10. V kiểm tra xem đẳng thức sau có tồn tại hay không: g^p = (g^h)^{t(s)}.

Giao thức này hiện đáp ứng các thuộc tính mà SNARK yêu cầu: chính xác, mạnh mẽ và hiệu quả. Các phần tiếp theo sẽ giải quyết vấn đề không tương tác và không có kiến ​​thức.

Nhận xét: Bước 6 và 7 trong giao thức trên được thực hiện theo ví dụ về ẩn đồng cấu.

kiến thức không

Trong giao thức mà chúng ta đã trình bày cho đến nay, các hệ số ci của đa thức mà P đã biết là rất cụ thể và V có thể cố gắng tìm hiểu một số thông tin về chúng bằng cách sử dụng gp, gh và gp' đến từ P. Do đó, để đảm bảo P chắc chắn rằng V sẽ không học được gì, P cần ẩn các giá trị này.

Chiến lược ẩn các giá trị được gửi bởi P tuân theo các bước đã sử dụng trước đó: P lấy ngẫu nhiên và sử dụng nó để ẩn các giá trị được gửi trong giao tiếp với V. Nói chính xác, thay vì gửi g^p, g^h và g ^{p'}, P tính toán và gửi (g^p)^, (g^h)^ và (g^{p'})^. Sau đó, V chạy xác minh trên các giá trị ẩn bên dưới .

Thực tế, quy trình xác minh mà V cần chạy vẫn hợp lệ với việc ẩn này:

Vì vậy, để làm cho giao thức thứ ba không có kiến ​​thức, người ta thay thế bước 8 để P có thể gửi các giá trị bị xáo trộn.

không tương tác

Các giao thức khác nhau mà chúng tôi đã trình bày yêu cầu sự tương tác giữa người chứng thực và người xác minh, và điều này là do tính chính xác của các giao thức phụ thuộc vào các giá trị bí mật s và do người xác minh chọn.

Nếu chúng ta muốn lặp lại bất kỳ giao thức nào ở trên với một trình xác minh khác V', V' sẽ cần chọn các giá trị mới s' và '. Việc sử dụng các giá trị do V tạo ra có thể cho phép P gian lận nếu anh ta thông đồng với V và V tiết lộ các giá trị s và cho P.

Để tránh tình huống trên, chúng tôi cần giao thức của mình không tương tác và chúng tôi có thể đạt được điều đó bằng cách sử dụng các tham số công khai, đáng tin cậy và có thể tái sử dụng. Điều này có thể được thực hiện bằng cách làm xáo trộn các tham số này bằng trình tạo g. Tuy nhiên, ngay cả khi các kỹ thuật che giấu được sử dụng là đồng hình, chúng chỉ cho phép thêm các thông báo rõ ràng bằng cách sử dụng tích của các giá trị ẩn, nhưng chúng không cho phép thực hiện tích các giá trị rõ ràng trong miền bị xáo trộn và bước này rất quan trọng khi xác minh tính đúng đắn của đa thức và nghiệm của nó.

Chúng tôi sẽ giới thiệu các cặp để giải quyết vấn đề này. Hãy nhớ lại rằng một cặp có thuộc tính sau:

Thuộc tính này cho phép kiểm tra sự bằng nhau của các sản phẩm trong miền bị xáo trộn.

Vì vậy, để làm cho các giao thức của chúng ta không tương tác, bước đầu tiên là lấy các giá trị ngẫu nhiên bí mật s và và làm xáo trộn chúng: g^, và .

Sau khi chúng tôi tính toán các lũy thừa này, chúng tôi có thể loại bỏ các giá trị bí mật s và và phát các giá trị bị xáo trộn của chúng, được gọi là Chuỗi tham chiếu chung (CRS). Các giá trị CRS thường được lưu trữ dưới dạng:

1. Khóa đánh giá: (, ).
2. Khóa xác minh: (g^, g^{t(s)}).

Giao thức cuối cùng: zk-SNARK cho kiến ​​thức về đa thức

Bây giờ chúng ta định nghĩa một zk-SNARK để chứng minh kiến ​​thức về đa thức p(x) bậc n với đa thức đích t(x).

Cài đặt tham số

1. Mỗi bên lấy ngẫu nhiên hai giá trị bí mật s và .
2. Mỗi bên tính g, và .
3. Các giá trị s và bị hủy.
4. Một quảng bá khóa đánh giá ( và ).
5. Một quảng bá khóa xác minh g^, g^{t(s)}.

1. Giả sử P biết p(x), P tính đa thức h(x).
2. P đánh giá p(x) và h(x) và tính toán gp(s) và gh(s) bằng cách sử dụng các giá trị có trong khoá đánh giá.
3. P tính toán giá trị g^{p( · s)} bằng cách sử dụng khóa đánh giá.
4. P lấy ngẫu nhiên một giá trị .
5. P công bố bằng chứng π = (g^{ · p(s)}, g^{ · h(s)}, g^{ · p( · s)}) = (g^{ · p }, g^{ · h}, g^{ · p'}).

Giả sử rằng V có quyền truy cập vào π = (g^{ · p}, g^{ · h}, g^{ · p'}), nó sẽ kiểm tra xem

Chúng tôi đã quản lý để thiết lập một giao thức đáp ứng tất cả các thuộc tính cần thiết trong định nghĩa của zk-SNARK: ngắn gọn (vì bằng chứng chỉ kiểm tra đa thức tại một điểm), không cần biết và không tương tác (vì nó sử dụng CRS ).

Thế hệ của CRS

Zk-SNARK có thể được tạo thành không tương tác bằng cách sử dụng một tập hợp các giá trị ẩn, được gọi là Chuỗi tham chiếu chung (CRS). Các giá trị ẩn này, trong trường hợp của chúng ta có dạng và , xuất phát từ các giá trị bí mật, s và , các giá trị này phải bị hủy sau khi các giá trị ẩn đã được lấy. Quan sát rằng việc tạo CRS là rất quan trọng vì nếu một người ủy thác việc tạo ra nó cho người tham gia thứ ba, mọi người cần tin tưởng rằng người tham gia sẽ hủy các giá trị s và . Bên thứ ba đại diện cho một điểm thất bại duy nhất.

Nếu chúng ta muốn tránh điểm thất bại duy nhất, chúng ta cần một cách phân tán để tạo CRS trong đó một người tham gia trung thực duy nhất đủ để đảm bảo rằng các giá trị s và không thể được phục hồi.

Hãy sử dụng CRS cho SNARK mà chúng ta đã tạo trong ví dụ trước. Chúng tôi nhớ lại rằng sử dụng s và làm bí mật, chúng tôi cần tính toán các giá trị ẩn và lũy thừa g^, và .

Trong giao thức mới của chúng tôi, chúng tôi sẽ thay thế các giá trị s và do một bên thứ ba tạo ra bằng các giá trị s_{ABC} và _{ABC} được tạo bởi ba người dùng A, B và C. Việc mở rộng cơ chế cho n người dùng rất đơn giản .

Giao thức sau:

1. Người dùng A tạo cặp (sA, A), tính toán và phát:

3. Chương trình phát sóng B:

4. C lấy ngẫu nhiên một cặp (sC, C), tính toán và phát:

Giao thức này tạo ra các giá trị ẩn cho s_{ABC} = s_A · s_B · s_C và _{ABC} = _A · _B · _C mà không có người tham gia nào biết cặp giá trị này.

Tuy nhiên, chúng tôi cần một giao thức cho phép những người tham gia kiểm tra xem các giá trị ẩn đó đã được tính toán chính xác chưa. Chúng ta cần đảm bảo rằng các giá trị được tạo bởi mỗi người dùng đáp ứng các yêu cầu, đó là tập hợp các giá trị là lũy thừa của gs, đối với giá trị s của mỗi người dùng và tập hợp đã được tính toán chính xác. Để làm như vậy, chúng tôi kiểm tra xem mỗi (g^s)^i có thực sự là lũy thừa thứ i của gs hay không. Điều này có thể được thực hiện bằng cách kiểm tra xem các đẳng thức sau có đúng không. Việc kiểm tra này được thực hiện bởi mỗi bên tham gia đối với tất cả các giá trị sU và U được liên kết với mỗi bên tham gia U:

Đây không phải là yêu cầu xác minh duy nhất. Chúng tôi cũng cần kiểm tra xem mỗi người tham gia có sử dụng đúng giá trị từ người tham gia trước đó không. Để làm điều đó, mỗi người tham gia sẽ sử dụng các tham số công khai ẩn từ một người dùng kết hợp với kết quả đầu ra của một người tham gia khác. Ví dụ: C có thể kiểm tra các giá trị trung gian của CRS do B tạo ra, sử dụng thông tin CRS từ A, bằng cách xác minh như sau:

Phần kết luận

Cho đến giờ, chúng ta đã học cách tạo một SNARK, từ đầu và với đầy đủ chi tiết, để chứng minh kiến ​​thức về một đa thức. Trong bài tiếp theo của chúng tôi, bài cuối cùng, chúng tôi sẽ mở rộng cấu trúc trên cho bất kỳ tính toán nào. Để làm như vậy, chúng tôi sẽ giới thiệu hai khái niệm chính: chương trình số học bậc hai, QAP và hệ thống ràng buộc hạng 1, R1CS, mặc dù khái niệm sau sẽ không được giới thiệu cụ thể (nó sẽ xuất hiện dưới dạng thông báo tiềm thức).

Người giới thiệu

Jordi Herrera Joancomartí, Cristina Pérez Solà, Criptografia avançada. Ghi chú bài giảng. Đại học Mở Catalonia, 2022.