Zk-SNARKs: Dưới nắp động cơ

• tác giả: Vitalik Buterin *

• tiêu đề gốc: 《Zk-SNARKs: Under the Hood》 *

• thời gian xuất bản: Ngày 1 tháng 2 năm 2017 *

Đây là phần thứ ba trong loạt bài giải thích về công nghệ đằng sau zk-SNARKs; các bài viết trước về chương trình số bậc hai và cặp đường cong elip là những tài liệu cần đọc, bài viết này sẽ giả định kiến thức về hai khái niệm này. Cũng giả định kiến thức cơ bản về zk-SNARK là gì và chúng làm gì. Vui lòng tham khảo bài viết của Christian Reitwiessner ở đây để có một giới thiệu kỹ thuật khác.

Trong các bài viết trước, chúng tôi đã giới thiệu về chương trình số bậc hai, một phương pháp để biểu diễn bất kỳ vấn đề tính toán nào bằng các phương trình đa thức, phù hợp hơn với nhiều hình thức kỹ thuật toán học khác nhau. Chúng tôi cũng đã giới thiệu về cặp đường cong elip, cho phép một hình thức mã hóa đồng nhất một chiều rất hạn chế, cho phép bạn thực hiện kiểm tra sự bằng nhau. Bây giờ, chúng ta sẽ bắt đầu từ nơi chúng ta đã dừng lại lần trước, sử dụng cặp đường cong elip và một số kỹ thuật toán học khác để cho phép người chứng minh chứng minh rằng họ biết giải pháp cho một QAP cụ thể mà không cần tiết lộ bất kỳ thông tin nào về giải pháp thực tế.

Bài viết này sẽ tập trung vào giao thức Pinocchio (thường được gọi là PGHR13) mà Parno, Gentry, Howell và Raykova đã bắt đầu vào năm 2013; cơ chế cơ bản có một số thay đổi, vì vậy các kế hoạch zk-SNARK được triển khai trong thực tế có thể hơi khác nhau, nhưng nguyên tắc cơ bản thường vẫn giữ nguyên.

Đầu tiên, hãy để chúng ta đi vào các giả định mật mã chính đằng sau tính bảo mật của cơ chế mà chúng ta sẽ sử dụng: giả định Kiến thức mũ.

Về cơ bản, nếu bạn có một cặp điểm P và Q, trong đó P * k = Q, và bạn có một điểm C, thì trừ khi C theo cách nào đó "xuất phát" từ P, bạn không thể suy ra C * k mà bạn biết. Điều này có thể có vẻ trực quan, nhưng giả định này thực sự không thể được suy ra từ bất kỳ giả định nào khác mà chúng ta thường sử dụng khi chứng minh tính bảo mật của các giao thức dựa trên đường cong elip (ví dụ như độ khó của logarit rời rạc), do đó zk-SNARK thực sự phụ thuộc vào một nền tảng không ổn định hơn so với mật mã đường cong elip - mặc dù nó vẫn đủ mạnh để hầu hết các nhà mật mã có thể chấp nhận.

Bây giờ, hãy xem cách sử dụng nó. Giả sử có một cặp điểm (P, Q) rơi từ trên trời xuống, trong đó P * k = Q, nhưng không ai biết giá trị của k là gì. Bây giờ, giả sử tôi đưa ra một cặp điểm (R, S), trong đó R * k = S. Vậy, giả định KoE có nghĩa là tôi có thể suy ra cách duy nhất để có được cặp điểm này là lấy P và Q, và nhân cả hai với một yếu tố nào đó mà tôi biết là r. Cũng cần lưu ý rằng, nhờ vào phép cặp đường cong elip, việc kiểm tra R = k * S thực sự không cần biết k - ngược lại, bạn có thể đơn giản kiểm tra e(R, Q) = e(P, S).

Hãy làm một số điều thú vị hơn. Giả sử chúng ta có mười cặp điểm rơi từ trên trời xuống: (P1, Q1), (P2, Q2)… (P10, Q10). Trong tất cả các trường hợp, Pi * k = Qi. Giả sử tôi sau đó cung cấp cho bạn một cặp điểm (R, S), trong đó R * k = S. Bạn bây giờ biết gì? Bạn biết R là một số tổ hợp tuyến tính của P1 * i1 + P2 * i2 + … + P10 * i10, trong đó tôi biết các hệ số i1, i2 … i10. Nói cách khác, để có được một cặp điểm như vậy (R, S), cách duy nhất là lấy một số bội của P1, P2…P10 và cộng chúng lại, sau đó thực hiện phép tính tương tự với Q1, Q2…Q_10.

Xin lưu ý rằng, với bất kỳ tập hợp điểm P1…P10 cụ thể nào mà bạn có thể muốn kiểm tra tổ hợp tuyến tính, bạn thực sự không thể tạo ra các điểm Q1…Q10 kèm theo mà không biết k là gì, nếu bạn thực sự biết k là gì, thì bạn có thể tạo ra một cặp (R, S), trong đó R * k = S cho bất kỳ R nào bạn muốn, mà không cần tạo ra tổ hợp tuyến tính. Do đó, để nó hoạt động, phải đảm bảo rằng người tạo ra những điểm này là đáng tin cậy và thực sự xóa k sau khi tạo ra mười điểm. Đây là nguồn gốc của khái niệm "cài đặt đáng tin cậy".

Hãy nhớ rằng, giải pháp của QAP là một tập hợp các đa thức (A, B, C) sao cho A(x) * B(x) - C(x) = H(x) * Z(x), trong đó:

• A là một tổ hợp tuyến tính của một tập hợp các đa thức {A1…Am}
• B là một tổ hợp tuyến tính của {B1…Bm} với cùng hệ số
• C là một tổ hợp tuyến tính của {C1…Cm} với cùng hệ số

Tập hợp {A1…Am}, {B1…Bm} và {C1…Cm} cùng với đa thức Z là một phần của tuyên bố vấn đề.

Tuy nhiên, trong hầu hết các trường hợp thực tế, A, B và C đều rất lớn; đối với những thứ như hàm băm có hàng ngàn cổng mạch, các đa thức (và các yếu tố của tổ hợp tuyến tính) có thể có hàng ngàn mục. Do đó, chúng tôi không yêu cầu người chứng minh cung cấp trực tiếp tổ hợp tuyến tính, mà sử dụng các kỹ thuật mà chúng tôi đã giới thiệu ở trên để cho phép người chứng minh chứng minh rằng những gì họ cung cấp là tổ hợp tuyến tính, nhưng không tiết lộ bất kỳ điều gì khác.

Bạn có thể đã nhận thấy rằng, các kỹ thuật ở trên áp dụng cho các điểm đường cong elip, chứ không phải cho các đa thức. Do đó, điều thực sự xảy ra là chúng tôi sẽ thêm các giá trị sau vào cài đặt đáng tin cậy:

G * A1(t), G * A1(t) * ka G * A2(t), G * A2(t) * ka
…
G * B1(t), G * B1(t) * kb G * B2(t), G * B2(t) * kb
…
G * C1(t), G * C1(t) * kc G * C2(t), G * C2(t) * kc
…
Bạn có thể coi t là "điểm bí mật" để tính toán đa thức. G là một "bộ sinh" (một số điểm đường cong elip ngẫu nhiên, được chỉ định là một phần của giao thức), t, ka, kb và kc là các "chất thải độc hại", mà phải được xóa bằng mọi giá, hoặc người sở hữu chúng sẽ có thể tạo ra chứng minh giả. Bây giờ, nếu ai đó cung cấp cho bạn một cặp điểm P, Q sao cho P * ka = Q (nhắc nhở: chúng ta không cần ka để kiểm tra điều này, vì chúng ta có thể thực hiện kiểm tra cặp), thì bạn biết họ đã cung cấp cho bạn một tổ hợp tuyến tính của các đa thức Ai mà bạn đang đánh giá tại t.

Do đó, cho đến nay, người chứng minh phải cung cấp:

πa = G * A(t), π'a = G * A(t) * ka πb = G * B(t), π'b = G * B(t) * kb
πc = G * C(t), π'c = G * C(t) * k_c

Xin lưu ý rằng, người chứng minh thực sự không cần biết (cũng không nên biết!) t, ka, kb hoặc k_c để tính toán các giá trị này; ngược lại, người chứng minh nên có thể tính toán các giá trị này chỉ dựa trên các điểm mà chúng tôi đã thêm vào cài đặt đáng tin cậy.

Bước tiếp theo là đảm bảo rằng tất cả ba tổ hợp tuyến tính có cùng hệ số. Chúng tôi có thể làm điều này bằng cách thêm một tập hợp giá trị khác vào cài đặt đáng tin cậy: G * (Ai(t) + Bi(t) + C_i(t)) * b, trong đó b là một số khác cũng nên được coi là "chất thải độc hại" và ngay lập tức bị loại bỏ sau khi cài đặt đáng tin cậy hoàn tất. Sau đó, chúng tôi có thể yêu cầu người chứng minh sử dụng các giá trị này có cùng hệ số để tạo ra một tổ hợp tuyến tính và sử dụng kỹ thuật cặp tương tự như trên để xác minh rằng giá trị đó khớp với A + B + C đã cung cấp.

Cuối cùng, chúng tôi cần chứng minh A * B - C = H * Z. Chúng tôi thực hiện điều này một lần nữa bằng cách kiểm tra cặp:

e( πa, πb) / e( πc, G) ?= e( πh, G * Z(t))

Trong đó π_h = G * H(t). Nếu mối liên hệ giữa phương trình này và A * B - C = H * Z không có ý nghĩa với bạn, hãy quay lại đọc bài viết về phép cặp.

Chúng tôi đã thấy ở trên cách chuyển đổi A, B và C thành các điểm đường cong elip; G chỉ là bộ sinh (tức là điểm đường cong elip tương đương với số một). Chúng tôi có thể thêm G * Z(t) vào cài đặt đáng tin cậy. H thì khó hơn; H chỉ là một đa thức, và chúng tôi hiếm khi dự đoán trước hệ số của mỗi giải pháp QAP riêng lẻ. Do đó, chúng tôi cần thêm nhiều dữ liệu hơn vào cài đặt đáng tin cậy; thứ tự cụ thể:

G, G * t, G * t², G * t³, G * t⁴ …。

Trong cài đặt đáng tin cậy của Zcash, chuỗi ở đây lên tới khoảng 2 triệu; đây là số lần bạn cần lấy lũy thừa để đảm bảo luôn có thể tính toán H(t), ít nhất là đối với các trường hợp QAP cụ thể mà họ quan tâm. Như vậy, người chứng minh có thể cung cấp cho người xác minh tất cả thông tin cần thiết để thực hiện kiểm tra cuối cùng.

Còn một chi tiết nữa cần chúng ta thảo luận. Hầu hết thời gian, chúng ta không chỉ muốn chứng minh một cách trừu tượng rằng giải pháp cho một số vấn đề cụ thể tồn tại; ngược lại, chúng ta muốn chứng minh tính chính xác của một giải pháp cụ thể (ví dụ, chứng minh rằng nếu bạn sử dụng từ "cow" và băm nó bằng SHA3 một triệu lần, kết quả cuối cùng bắt đầu bằng 0x73064fe5), hoặc nếu bạn hạn chế giải pháp tồn tại một số tham số. Ví dụ, trong các trường hợp tiền điện tử mà số tiền giao dịch và số dư tài khoản được mã hóa, bạn muốn chứng minh rằng bạn biết một số khóa giải mã k, như thế này:

Số dư cũ được mã hóa, giá trị giao dịch và số dư mới nên được công khai chỉ định, vì đây là những giá trị cụ thể mà chúng tôi muốn xác minh tại một thời điểm cụ thể; chỉ có khóa giải mã nên được ẩn. Cần thực hiện một số điều chỉnh tinh tế đối với giao thức để tạo ra "khóa xác minh tùy chỉnh" tương ứng với một số hạn chế cụ thể của đầu vào.

Bây giờ, hãy để chúng ta lùi lại một bước. Đầu tiên, đây là thuật toán xác minh hoàn chỉnh, được cung cấp bởi ben Sasson, Tromer, Virza và Chiesa:

Dòng đầu tiên xử lý tham số hóa; về bản chất, bạn có thể coi chức năng của nó như việc tạo ra "khóa xác minh tùy chỉnh" cho một trường hợp cụ thể của vấn đề đã chỉ định một số tham số. Dòng thứ hai là kiểm tra tổ hợp tuyến tính của A, B, C; dòng thứ ba là kiểm tra xem các tổ hợp tuyến tính có cùng hệ số hay không, dòng thứ tư là kiểm tra tích A * B - C = H * Z.

Tóm lại, quy trình xác minh là một số phép nhân đường cong elip (mỗi biến đầu vào "công cộng" một) và năm lần kiểm tra cặp, trong đó một lần bao gồm phép nhân cặp bổ sung. Chứng minh bao gồm tám điểm đường cong elip: A(t), B(t) và C(t) mỗi điểm có một cặp, b * (A(t) + B(t) + C(t)) có một điểm πk), và một điểm πh cho H(t). Bảy điểm trong đường cong Fp (mỗi điểm 32 byte, vì bạn có thể nén tọa độ y thành một bit), trong khi trong triển khai Zcash, một điểm (πb) nằm trên đường cong xoắn F_p² (64 byte), vì vậy kích thước tổng thể của chứng minh khoảng 288 byte.

Hai phần tính toán khó khăn nhất trong việc tạo ra chứng minh là:

Chia (A * B - C) / Z để có được H (thuật toán dựa trên biến đổi Fourier nhanh có thể hoàn thành điều này trong thời gian bậc hai, nhưng khối lượng tính toán vẫn rất lớn)
Thực hiện các phép nhân và cộng đường cong elip để tạo ra các giá trị A(t), B(t), C(t) và H(t) cùng với các cặp tương ứng
Lý do cơ bản khiến việc tạo ra chứng minh trở nên khó khăn như vậy là nếu chúng ta muốn tạo ra chứng minh không có kiến thức từ đó, một cổng logic nhị phân đơn lẻ trong tính toán gốc đã biến thành các phép toán phải được xử lý bằng các phép toán đường cong elip. Thực tế này, cộng với biến đổi Fourier nhanh, có nghĩa là việc tạo ra chứng minh cho giao dịch Zcash mất khoảng 20-40 giây.

Một câu hỏi rất quan trọng khác là: liệu chúng ta có thể cố gắng làm cho cài đặt đáng tin cậy ít cần tin tưởng hơn một chút…? Thật không may, chúng ta không thể làm cho nó hoàn toàn không tin cậy; giả định KoE tự nó loại trừ việc tạo ra các cặp độc lập (Pi, Pi * k) mà không biết k là gì. Tuy nhiên, chúng ta có thể cải thiện tính bảo mật đáng kể bằng cách sử dụng tính toán đa bên N-of-N - tức là, xây dựng cài đặt đáng tin cậy giữa N bên, miễn là ít nhất một người tham gia xóa chất thải độc hại của họ, thì bạn đã ổn.

Để có một cái nhìn tổng quan về cách thực hiện điều này, đây là một thuật toán đơn giản để lấy một tập hợp hiện có (G, G * t, G * t², G * t³…), và "thêm" bí mật của riêng bạn, để bạn cần bí mật của bạn và bí mật trước đó (hoặc một tập hợp bí mật trước đó) để gian lận.

Tập hợp đầu ra rất đơn giản:

G, (G * t) * s, (G * t²) * s², (G * t³) * s³…

Xin lưu ý rằng, bạn chỉ cần biết tập hợp gốc và s để tạo ra tập hợp này, và chức năng của tập hợp mới tương đương với tập hợp cũ, chỉ là bây giờ sử dụng t*s làm "chất thải độc hại" thay vì t. Miễn là bạn và người tạo ra tập hợp trước đó (hoặc nhiều người) không xóa chất thải độc hại của bạn và sau đó thông đồng, thì tập hợp đó là "an toàn".

Việc thực hiện điều này cho cài đặt đáng tin cậy hoàn chỉnh khó khăn hơn nhiều, vì có nhiều giá trị liên quan và thuật toán phải được hoàn thành qua nhiều vòng giữa các bên. Đây là một lĩnh vực nghiên cứu tích cực, xem liệu có thể đơn giản hóa hơn nữa các thuật toán tính toán đa bên và làm cho chúng cần ít vòng hơn hoặc có thể song song hóa hơn, vì càng nhiều việc bạn có thể làm, càng nhiều bên tham gia vào quá trình cài đặt đáng tin cậy. Có lý do để thấy tại sao một cài đặt đáng tin cậy giữa sáu người tham gia quen biết và làm việc cùng nhau có thể khiến một số người cảm thấy không thoải mái, nhưng một cài đặt đáng tin cậy với hàng ngàn người tham gia thì gần như không khác gì so với hoàn toàn không tin tưởng - và nếu bạn thực sự rất nghi ngờ, bạn có thể tự mình tham gia vào quá trình cài đặt và đảm bảo rằng bạn đã xóa giá trị của mình.

Một lĩnh vực nghiên cứu khác đang hoạt động là sử dụng các phương pháp khác không sử dụng phép cặp và cùng một mẫu cài đặt đáng tin cậy để đạt được cùng một mục tiêu. Vui lòng tham khảo bài thuyết trình gần đây của Eli ben Sasson để biết một lựa chọn khác (mặc dù hãy lưu ý rằng nó ít nhất về mặt toán học cũng phức tạp như SNARK!).

Đặc biệt cảm ơn Ariel Gabizon và Christian Reitwiessner đã xem xét.