Vitalik Buterin thông qua Blog Vitalik Buterin

Đây là sự phản ánh của bài viết tại https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

Đây là phần thứ ba của loạt bài viết giải thích cách hoạt động của công nghệ đằng sau zk-SNARK; các bài viết trước về chương trình số học bậc hai và cặp đường cong elip đều được yêu cầu đọc và bài viết này sẽ giả định kiến ​​thức về cả hai khái niệm. Kiến thức cơ bản về zk-SNARK là gì và chúng làm gì cũng được giả định. Xem thêm Bài viết của Christian Reitwiessner tại đây để 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 chương trình số học bậc hai, một cách biểu diễn bất kỳ bài toán tính toán nào bằng một phương trình đa thức phù hợp hơn nhiều với các dạng thủ thuật toán học khác nhau. Chúng tôi cũng đã giới thiệu các cặp đường cong elip, cho phép một dạng mã hóa đồng cấu 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 và sử dụng các cặp đường cong elip, cùng với một số thủ 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 tiết lộ bất kỳ điều gì khác về giải pháp thực tế.

Bài viết này sẽ tập trung vào Giao thức Pinocchio của Parno, Gentry, Howell và Raykova từ năm 2013 (thường được gọi là PGHR13); có một vài biến thể về cơ chế cơ bản, do đó sơ đồ zk-SNARK được triển khai trong thực tế có thể hoạt động hơi khác một chút, nhưng các nguyên tắc cơ bản nói chung sẽ giữ nguyên.

Để bắt đầu, chúng ta hãy đi vào giả định mật mã quan trọng làm cơ sở cho tính bảo mật của cơ chế mà chúng ta sẽ sử dụng: *kiến thức về số mũ* giả thiết.

Về cơ bản, nếu bạn nhận được một cặp điểm � và �, trong đó �⋅�=�, và bạn nhận được một điểm �, thì không thể nghĩ ra �⋅� trừ khi � "có nguồn gốc" từ � theo một cách nào đó mà bạn biết. Điều này có vẻ hiển nhiên về mặt trực giác, nhưng giả định này thực sự không thể bắt nguồn từ bất kỳ giả định nào khác (ví dụ: độ cứng log rời rạc) mà chúng tôi 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à do đó, zk-SNARK trên thực tế dựa trên một phần nào đó. nền tảng dễ lung lay hơn so với mật mã đường cong elip nói chung - mặc dù nó vẫn đủ vững chắc để hầu hết các nhà mật mã đều hài lòng với nó.

Bây giờ chúng ta hãy đi vào cách sử dụng tính năng này. Giả sử có một cặp điểm (�,�) từ trên trời rơi xuống, trong đó �⋅�=�, nhưng không ai biết giá trị của � là bao nhiêu. Bây giờ, giả sử tôi nghĩ ra một cặp điểm (�,�) trong đó �⋅�=�. Khi đó, giả định KoE ngụ ý rằng cách duy nhất tôi có thể tạo ra cặp điểm đó là lấy � và � rồi nhân cả hai với hệ số r nào đó. mà cá nhân tôi biết. Cũng lưu ý rằng nhờ sự kỳ diệu của các cặp đường cong elip, kiểm tra rằng �=�⋅� thực ra không cần phải biết � – thay vào đó, bạn chỉ cần kiểm tra xem có hay không �(�,�)=�(�,�).

Hãy làm điều gì đó thú vị hơn. Giả sử chúng ta có mười cặp điểm từ trên trời rơi xuống: (�1,�1),(�2,�2)…(�10,�10). Trong mọi trường hợp, ��⋅�=��. Giả sử sau đó tôi cung cấp cho bạn một cặp điểm (�,�) trong đó �⋅�=�. Bây giờ bạn biết gì? Bạn biết rằng � là một tổ hợp tuyến tính nào đó �1⋅�1+�2⋅�2+…+�10⋅�10, trong đó tôi biết các hệ số �1,�2…�10. Nghĩa là, cách duy nhất để có được một cặp điểm (�,�) như vậy là lấy bội số của �1,�2...�10 rồi cộng chúng lại với nhau rồi thực hiện phép tính tương tự với �1,�2… �10.

Lưu ý rằng, với bất kỳ tập hợp cụ thể nào gồm �1…�10 điểm mà bạn có thể muốn kiểm tra các kết hợp tuyến tính, bạn thực sự không thể tạo �1…�10 điểm đi kèm mà không biết � là gì, và nếu bạn biết điều gì � là sau đó bạn có thể tạo một cặp (�,�) trong đó �⋅�=� cho bất cứ thứ gì � bạn muốn mà không cần bận tâm đến việc tạo một tổ hợp tuyến tính. Do đó, để điều này có hiệu quả, điều bắt buộc là người tạo ra những điểm đó phải đáng tin cậy và thực sự xóa � một khi họ đã tạo ra mười điểm. Đây là nơi xuất phát khái niệm “thiết lập đáng tin cậy”.

Hãy nhớ rằng nghiệm của QAP là một tập hợp các đa thức (�,�,�) sao cho �(�)⋅�(�)−�(�)=�(�)⋅�(�), trong đó:

• � là tổ hợp tuyến tính của tập đa thức {�1…��}
• � là tổ hợp tuyến tính của {�1…��} có cùng hệ số
• � là tổ hợp tuyến tính của {�1…��} có cùng hệ số

Các tập {�1…��},{�1…��} và {�1…��} và đa thức � là một phần của phát biểu bài toán.

Tuy nhiên, trong hầu hết các trường hợp thực tế, �,� và � đều cực kỳ lớn; đối với một cái gì đó có hàng nghìn cổng mạch như hàm băm, các đa thức (và các thừa số của tổ hợp tuyến tính) có thể có hàng nghìn số hạng. Do đó, thay vì yêu cầu người chứng minh cung cấp trực tiếp các kết hợp tuyến tính, chúng ta sẽ sử dụng thủ thuật mà chúng tôi đã giới thiệu ở trên để người chứng minh chứng minh rằng họ đang cung cấp thứ gì đó 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 thủ thuật trên hoạt động trên các điểm trên đường cong elip chứ không phải trên đa thức. Do đó, điều thực sự xảy ra là chúng tôi thêm các giá trị sau vào thiết lập đáng tin cậy:

• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...

Bạn có thể coi t là một “điểm bí mật” mà tại đó đa thức được tính toán. � là một "máy phát điện" (một số điểm đường cong elip ngẫu nhiên được chỉ định như một phần của giao thức) và �,��,�� và �� là "chất thải độc hại", những con số nhất thiết phải bị xóa bằng mọi giá, nếu không bất cứ ai có chúng sẽ có thể làm bằng chứng giả. Bây giờ, nếu ai đó cho bạn một cặp điểm �, � sao cho �⋅��=� (nhắc nhở: chúng ta không cần �� để kiểm tra điều này, vì chúng ta có thể thực hiện kiểm tra ghép nối), thì bạn biết rằng họ đang cho bạn một tổ hợp tuyến tính của �� đa thức được đánh giá tại �.

Do đó, cho đến nay người chứng minh phải đưa ra:

• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��

Lưu ý rằng người chứng minh thực sự không cần biết (và không nên biết!) �,��,�� hoặc �� để tính những giá trị này; đúng hơn, người chứng minh sẽ có thể tính toán các giá trị này chỉ từ những điểm mà chúng tôi đang thêm vào thiết lập đáng tin cậy.

Bước tiếp theo là đảm bảo rằng cả ba tổ hợp tuyến tính đều có cùng hệ số. Chúng ta có thể thực hiện điều này bằng cách thêm một tập hợp giá trị khác vào thiết lập đáng tin cậy: �⋅(��(�)+��(�)+��(�))⋅�, trong đó � là một số khác nên được coi là "độc hại" lãng phí” và bị loại bỏ ngay sau khi quá trình thiết lập đáng tin cậy hoàn tất. Sau đó, chúng ta có thể yêu cầu người chứng minh tạo một tổ hợp tuyến tính với các giá trị này có cùng hệ số và sử dụng thủ thuật ghép nối tương tự như trên để xác minh rằng giá trị này khớp với �+�+� được cung cấp.

Cuối cùng, chúng ta cần chứng minh rằng �⋅�−�=�⋅�. Chúng tôi thực hiện việc này một lần nữa bằng cách kiểm tra ghép nối:

�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))

Trong đó �ℎ=�⋅�(�). Nếu mối liên hệ giữa phương trình này và �⋅�−�=�⋅� không có ý nghĩa với bạn, hãy quay lại và đọc phần bài viết về cặp đôi.

Ở trên chúng ta đã thấy cách chuyển đổi �,� và � thành các điểm trên đường cong elip; � chỉ là bộ tạo (tức là điểm đường cong elip tương đương với số một). Chúng ta có thể thêm �⋅�(�) vào thiết lập đáng tin cậy. � khó hơn; � chỉ là một đa thức và chúng tôi dự đoán trước rất ít về hệ số của nó đối với từng nghiệm QAP riêng lẻ. Do đó, chúng ta cần thêm nhiều dữ liệu hơn vào thiết lập đáng tin cậy; cụ thể là trình tự:

�,�⋅�,�⋅�2,�⋅�3,�⋅�4….

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

Còn một chi tiết nữa mà chúng ta cần bàn tới. Hầu hết chúng ta không chỉ muốn chứng minh một cách trừu tượng rằng có giải pháp nào đó cho một số vấn đề cụ thể; thay vào đó, chúng tôi muốn chứng minh tính đúng đắn của một số giải pháp cụ thể (ví dụ: chứng minh rằng nếu bạn lấy từ “bò” và băm SHA3 nó một triệu lần thì kết quả cuối cùng bắt đầu bằng 0x73064fe5) hoặc giải pháp đó tồn tại nếu bạn hạn chế một số thông số. Ví dụ: trong quá trình khởi tạo tiền điện tử trong đó 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 sao cho:

1. decrypt(old_balance, k) >= decrypt(tx_value, k)
2. decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)

Được mã hóa old_balance, tx_value và new_balance phải được chỉ định công khai vì đó là những giá trị cụ thể mà chúng tôi đang tìm cách xác minh tại thời điểm cụ thể đó; chỉ nên ẩn khóa giải mã. Cần có một số sửa đổi nhỏ đối với giao thức để tạo “khóa xác minh tùy chỉnh” tương ứng với một số hạn chế cụ thể đối với thông tin đầu vào.

Bây giờ chúng ta hãy lùi lại một chút. Trước hết, đây là toàn bộ thuật toán xác minh, nhờ sự hỗ trợ của ben Sasson, Tromer, Virza và Chiesa:

Dòng đầu tiên đề cập đến tham số hóa; về cơ bản, bạn có thể coi chức năng của nó là tạo “khóa xác minh tùy chỉnh” cho trường hợp cụ thể của vấn đề trong đó một số đối số được chỉ định. Dòng thứ hai là kiểm tra tổ hợp tuyến tính cho �,� và �; dòng thứ ba là kiểm tra xem các kết hợp tuyến tính có cùng hệ số hay không và dòng thứ tư là kiểm tra tích �⋅�−�=�⋅�.

Nhìn chung, quy trình xác minh bao gồm một số phép nhân đường cong elip (một phép nhân cho mỗi biến đầu vào “công khai”) và năm phép kiểm tra ghép nối, một trong số đó bao gồm phép nhân ghép nối bổ sung. Chứng minh chứa tám điểm trên đường cong elip: mỗi cặp một cặp điểm cho �(�),�(�) và �(�), một điểm �� cho �⋅(�(�)+�(�)+�(� )) và một điểm �ℎ cho �(�). Bảy trong số các điểm này nằm trên đường cong �� (mỗi điểm 32 byte, vì bạn có thể nén tọa độ � thành một bit duy nhất) và trong quá trình triển khai Zcash, một điểm (��) nằm trên đường cong xoắn trong ��2 (64 byte), vì vậy tổng kích thước của bằng chứng là ~ 288 byte.

Hai phần khó nhất về mặt tính toán trong việc tạo ra một bằng chứng là:

• Chia (�⋅�−�)/� được � (thuật toán dựa trên Biến đổi Fourier nhanh có thể làm điều này trong thời gian dưới bậc hai, nhưng nó vẫn khá nặng về mặt tính toán)
• Thực hiện các phép nhân và phép cộng của đường cong elip để tạo ra các giá trị �(�),�(�),�(�) và �(�) và các cặp tương ứng của chúng

Lý do cơ bản tại sao việc tạo bằng chứng lại khó đến vậy là vì một cổng logic nhị phân duy nhất trong tính toán ban đầu biến thành một phép toán phải được xử lý bằng mật mã thông qua các phép toán đường cong elip nếu chúng ta tạo ra bằng chứng không có kiến ​​thức từ nó . Thực tế này, cùng với tính siêu tuyến tính của các phép biến đổi Fourier nhanh, có nghĩa là việc tạo bằng chứng mất khoảng 20–40 giây cho một giao dịch Zcash.

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 thiết lập đáng tin cậy… ít đòi hỏi sự tin cậy hơn không? Thật không may, chúng tôi không thể làm cho nó hoàn toàn không cần sự tin cậy; bản thân giả định KoE đã ngăn cản việc tạo ra các cặp độc lập (��,��⋅�) mà không biết � là gì. Tuy nhiên, chúng tôi có thể tăng cường bảo mật đáng kể bằng cách sử dụng tính toán nhiều bên �-of-� - nghĩa là xây dựng thiết lập đáng tin cậy giữa � các bên theo cách miễn là ít nhất một trong số những người tham gia đã xóa chất thải độc hại của họ thì bạn vẫn ổn .

Để hiểu một chút về cách bạn thực hiện việc này, đây là một thuật toán đơn giản để lấy một tập hợp hiện có (�,�⋅�,�⋅�2,�⋅�3…) và “thêm vào” bí mật của riêng bạn do đó bạn cần cả bí mật của mình và bí mật trước đó (hoặc bộ bí mật trước đó) để gian lận.

Bộ đầu ra chỉ đơn giản là:

�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…

Lưu ý rằng bạn có thể tạo ra bộ này chỉ biết bộ ban đầu và s, còn bộ mới hoạt động theo cách tương tự như bộ cũ, ngoại trừ việc bây giờ sử dụng �⋅� làm "chất thải độc hại" thay vì �. Chỉ cần bạn và người (hoặc những người) tạo ra bộ trước đó không xóa chất thải độc hại của bạn và sau đó thông đồng với nhau thì bộ đó là “an toàn”.

Thực hiện việc này để thiết lập đáng tin cậy hoàn chỉnh khó hơn một chút vì có một số giá trị liên quan và thuật toán phải được thực hiện giữa các bên trong nhiều vòng. Đây là một lĩnh vực đang được nghiên cứu tích cực để xem liệu thuật toán tính toán nhiều bên có thể được đơn giản hóa hơn nữa và được thực hiện để yêu cầu ít vòng hơn hoặc có khả năng song song hóa cao hơn hay không, vì bạn càng làm được nhiều việc thì càng có nhiều bên tham gia vào quy trình thiết lập đáng tin cậy. . Thật hợp lý khi hiểu tại sao một thiết lập đáng tin cậy giữa sáu người tham gia đều biết và làm việc với nhau có thể khiến một số người không thoải mái, nhưng một thiết lập đáng tin cậy với hàng nghìn người tham gia sẽ gần như không thể phân biệt được với việc không có chút tin cậy nào – và nếu bạn thực sự hoang tưởng , bạn có thể tự mình tham gia và tham gia vào quy trình thiết lập và đảm bảo rằng chính bạn đã xóa giá trị của mình.

Một lĩnh vực nghiên cứu tích cực khác là sử dụng các phương pháp tiếp cận khác không sử dụng cặp đôi và cùng một mô hình thiết lập đáng tin cậy để đạt được cùng một mục tiêu; nhìn thấy Bài thuyết trình gần đây của Eli ben Sasson cho một giải pháp thay thế (mặc dù được cảnh báo, ít nhất nó cũng phức tạp về mặt toán học như SNARK!)

Đặc biệt cảm ơn Ariel Gabizon và Christian Reitwiessner đã đánh giá.

• Phân phối nội dung và PR được hỗ trợ bởi SEO. Được khuếch đại ngay hôm nay.
• PlatoData.Network Vertical Generative Ai. Trao quyền cho chính mình. Truy cập Tại đây.
• PlatoAiStream. Thông minh Web3. Kiến thức khuếch đại. Truy cập Tại đây.
• Trung tâmESG. Than đá, công nghệ sạch, Năng lượng, Môi trường Hệ mặt trời, Quản lý chất thải. Truy cập Tại đây.
• PlatoSức khỏe. Tình báo thử nghiệm lâm sàng và công nghệ sinh học. Truy cập Tại đây.
• BlockOffsets. Hiện đại hóa quyền sở hữu bù đắp môi trường. Truy cập Tại đây.
• nguồn: Trí thông minh dữ liệu Plato.