[Bằng chứng không có kiến thức] zk-SNARK (5) - Giao thức Pinocchio

Tiêu đề gốc: "Học zk-SNARK từ đầu (5) - Giao thức Pinocchio"
Nguồn gốc: Ambi Labs Tác giả: Maksym Petkus

Giới thiệu

even@ Anbi Lab: Là bài viết cuối cùng trong loạt bài này, bài viết này tiếp tục cải tiến giao thức zk-SNARK và cuối cùng hình thành một giao thức zk-SNARK hoàn chỉnh.

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) - Tính chất và cách chứng minh đa thức
[Bằng chứng không có kiến thức] zk-SNARK (2) - Bằng chứng không có kiến thức không tương tác đa thức
[Bằng chứng không có kiến thức] zk-SNARK (3) - Từ chương trình đến xây dựng đa thức
[Bằng chứng không có kiến thức] zk-SNARK (4) - Ràng buộc đa thức

Các hạn chế và ý kiến đóng góp của công chúng

Các ràng buộc

Phân tích của chúng tôi tập trung vào khái niệm hoạt động. Tuy nhiên, giao thức không thực sự thực hiện "tính toán" mà kiểm tra xem giá trị đầu ra có phải là kết quả của hoạt động đúng của các toán hạng hay không. Vì vậy, chúng tôi gọi nó là một ràng buộc, tức là một trình xác minh ràng buộc trình chứng minh cung cấp các giá trị hợp lệ đối với "chương trình" được xác định trước, bất kể "chương trình" này là gì. Một hệ thống có nhiều ràng buộc được gọi là "hệ thống ràng buộc" (trong trường hợp của chúng tôi đây là hệ thống ràng buộc bậc nhất, hay R1CS).

@Maksym (tác giả): Điều này thực sự ngụ ý rằng một cách để tìm tất cả các câu trả lời đúng là thực hiện một lần cho tất cả các kết hợp có thể giá trị Brute ép nó và chỉ chọn một ràng buộc được thỏa mãn hoặc sử dụng các kỹ thuật phức tạp hơn thỏa mãn ràng buộc [con18].

Chú thích

even@ Ambi Lab: Xin lưu ý rằng ràng buộc này được xác định trên mạch số học hoặc mạch Boolean. Bởi vì bài toán thỏa mãn hai loại mạch này là bài toán NP-Complete.

Do đó, chúng ta cũng có thể sử dụng các ràng buộc để đảm bảo các mối quan hệ khác. Ví dụ: nếu muốn xác nhận rằng giá trị của biến a chỉ có thể là 0 hoặc 1 (tức là số nhị phân), chúng ta có thể thực hiện việc này bằng một ràng buộc đơn giản:



Các ràng buộc phức tạp hơn cũng có thể được thể hiện theo cách này để đảm bảo rằng các giá trị được sử dụng đáp ứng các quy tắc. Điều quan trọng cần lưu ý là 1 không thể bị ràng buộc trong cấu trúc tính toán hiện tại:



Vì giá trị 1 (và 2 trong ràng buộc trước) phải được biểu thị bằng c·vone, trong đó c có thể được cố định với khóa chứng minh, nhưng vì v được cung cấp bởi người chứng minh nên nó có thể là bất kỳ giá trị nào khác. Mặc dù chúng ta có thể buộc vone về 0 bằng cách đặt c=0, nhưng sẽ khó tìm được ràng buộc để buộc vone về 1 trong hàm tạo bị hạn chế trước đây của chúng ta. Do đó, Người xác minh cần một cách để đặt giá trị của vone.

Chú thích

even@ Anbi Lab: Mối quan hệ ràng buộc của biểu thức mà chúng tôi đã đề cập trước đó được gọi là R1CS.

Ý kiến đóng góp của công chúng và 1

Nếu người xác minh không thể được kiểm tra dựa trên đầu vào của nó thì khả năng sử dụng bằng chứng sẽ bị hạn chế. Nghĩa là, nó biết người tục nhân nhân hai giá trị nhưng không biết các giá trị đó và/hoặc kết quả của phép tính. Mặc dù có thể "mã hóa cứng" một số giá trị nhất định trong khóa chứng minh (ví dụ: kết quả của phép nhân phải là 12), nhưng điều này sẽ yêu cầu tạo một khóa riêng cho mỗi "đầu vào của trình xác minh" mong muốn. .

Chú thích

even@ Ambi Labs: Điều này sẽ hạn chế nghiêm trọng tính thực tế và mạch cần hỗ trợ các thông số.

Do đó, bằng chứng có thể trở nên tổng quát hơn nếu một số giá trị (đầu vào hoặc đầu ra) có thể được chỉ định cho việc tính toán bởi người xác minh thay vì người chứng minh.

Đầu tiên, chúng ta hãy xem xét các giá trị gL(s), gR(s), gO(s) để được chứng minh. Bởi vì mã hóa đồng cấu được sử dụng ở đây nên chúng ta có thể tăng các giá trị này, chẳng hạn, chúng ta có thể thêm nó vào một đa thức được mã hóa khác sao cho giá trị là gL(s) · glv(s) =gL(s)+lv(s).

Theo cách này, nếu chúng ta có thể loại trừ thuật ngữ cần thiết trong đa thức biến được cung cấp cho người chứng minh, người xác minh có thể biến A đa thức đặt giá trị riêng của nó và việc kiểm tra vẫn đạt.

Bởi vì người kiểm tra đã có thể giới hạn sự lựa chọn đa thức của người chứng minh bằng cách thêm phép biến đổi α, nên dễ dàng nhận được kết quả kiểm tra này . Do đó, khi các số hạng tương ứng với tổng kiểm tra α và β của nó bị loại bỏ, các đa thức biến đổi này có thể được chuyển từ khóa chứng minh sang khóa xác minh.

Các bản cập nhật giao thức cần thiết là:

LƯU Ý: Theo giao thức (phần toán hạng biến đơn polynomial ), giá trị 1 được biểu thị bằng đa thức l0(x), r0(x), o0(x) đã có giá trị phù hợp trong phép toán tương ứng nên không cần gán giá trị.

Người xác minh sẽ phải thực hiện thêm công việc trong bước xác minh để làm cho các biến được chỉ định tỷ lệ thuận.

Điều này thực sự loại bỏ một số biến số khỏi tầm tay của người chứng minh Hãy vào tay người xác minh trong khi vẫn giữ phương trình bằng nhau. Do đó, việc kiểm tra tính hợp lệ chỉ có hiệu lực nếu các giá trị giống nhau được sử dụng trong đầu vào của người chứng minh và người xác minh.

1 Giá trị này rất quan trọng vì nó có thể được tạo bằng cách nhân nó với bất kỳ số hạng không đổi nào (từ trường hữu hạn đã chọn), ví dụ: Nhân a với 123:

Chú thích

even@ Anbi Lab: Ở đây, một số biến ban đầu do người xác minh gán được thay đổi để được người xác minh chỉ định, do đó người chứng minh phải duy trì cùng một thông tin đầu vào như người xác minh. Điều này không chỉ giải quyết vấn đề đầu vào tham số của Trình xác minh mà còn gián tiếp giải quyết vấn đề gán hằng số.

Điện toán không có kiến thức

Bằng chứng tính toán không có kiến thức

Kể từ khi giới thiệu các giao thức tính toán chung (chương Bằng chứng tính toán), chúng tôi đã loại bỏ tính chất không có kiến thức để cải thiện giao thức dễ dàng hơn. Tại thời điểm này, chúng tôi đã xây dựng một giao thức tính toán có thể kiểm chứng được.

Trước đây chúng tôi đã sử dụng phép biến đổi delta số ngẫu nhiên để xây dựng các chứng minh "không có kiến thức" về đa thức. Phương pháp này cho phép Chứng minh rằng chúng không thể phân biệt được với các số ngẫu nhiên (chương không có kiến thức):

Qua tính toán chúng tôi đã chứng minh:

Nhưng vấn đề là sử dụng Identical δ sẽ cản trở tính bảo mật vì chúng tôi đã sử dụng các giá trị này một cách riêng biệt trong bằng chứng:

Người khác có thể dễ dàng xác định xem hai giá trị đa thức khác nhau có giống nhau hay không để thu được một số kiến thức, cụ thể là: gδL(s)= gδR(s)

Các mối quan hệ nhỏ tiềm tàng giữa các giá trị khác nhau của L(s) và R(s) có thể được phân biệt bằng lực mạnh, ví dụ: nếu L(s) = 5R(s), Bạn có thể kiểm tra nhiều lần gL(s) =(gR(s))i cho giá trị của i ∈ {1…N} và chỉ cần thực hiện 5 bước để tiết lộ mối quan hệ chênh lệch 5 lần giữa hai giá trị. Cuộc tấn công vũ phu tương tự cũng có thể được sử dụng để bẻ khóa hoạt động bổ sung của các giá trị được mã hóa, chẳng hạn như: gL(s) = gR(s)+5

Các mối quan hệ khác giữa các yếu tố chứng minh cũng có thể được phát hiện, chẳng hạn , Nếu e(gδL(s),gδR(s)) = e(gδ2O(s),g), thì nó cũng có nghĩa là L(x) ⋅ R(x) = O(x).

Lưu ý: Việc tối ưu hóa kiểm tra tính nhất quán khiến việc khai thác các mối quan hệ dữ liệu trở nên khó khăn hơn, nhưng một số mối quan hệ vẫn có thể được phát hiện, chưa kể rằng người xác minh có thể chọn ρl, ρr cụ thể để tạo điều kiện tiết lộ kiến thức (miễn là điều này không phải là một thiết lập đa dạng).

Cuối cùng, chúng ta cần sử dụng các số ngẫu nhiên (δs) khác nhau cho mỗi giá trị đa thức, ví dụ: span>

δlL(s) ·δrR(s) - δoO(s) =t(s)·(△?⃝h ( s))

Để giải bài toán bất đẳng thức ở vế phải của phương trình, ta không phải thay đổi giao thức, chỉ cần sửa đổi giá trị của bằng chứng h(s) là đủ. Ở đây Delta (Δ) biểu thị quá trình xử lý được thực hiện đối với h(s) để cân bằng tính ngẫu nhiên ở vế bên kia của phương trình và ?⃝ biểu thị phép nhân hoặc phép cộng (điều này cũng bao gồm phép chia và phép trừ). Nếu chúng ta chọn sử dụng phép nhân (?⃝ = ×) để tính Δ, điều đó có nghĩa là khó có khả năng tìm thấy Δ lớn vì tính ngẫu nhiên:





Điều này không chỉ ẩn giá trị được mã hóa mà còn cho phép phương trình vượt qua bước kiểm tra để tính toán hiệu quả.



Thật kỳ lạ khi giao thức Pinocchio ban đầu [Par+13] chủ yếu tập trung vào tính toán có thể kiểm chứng, Và nó liên quan đến ít thuộc tính không có kiến thức hơn. Trên thực tế, nó chỉ yêu cầu một chút sửa đổi, gần như không mất phí.

Chú thích

even@ Ambi Lab: Khác với giải pháp không có kiến thức ở bài viết trước, ở đây, không có kiến thức về kiến thức của người chứng minh được đảm bảo bằng phép cộng chứ không phải phép nhân.

Giao thức Pinocchio là một cải tiến trên bài báo GGPR. Phần 3.1 cũng đề cập rằng để đạt được kiến thức bằng 0, bạn chỉ cần làm theo phương pháp của bài báo GGPR. Đây không phải là phần đóng góp của bài báo này. Ngoài ra, tài liệu giao thức Pinocchio tập trung vào thực hành kỹ thuật, vào năm 2013, bằng chứng không có kiến thức vẫn chưa được áp dụng. Ứng dụng thực sự đã có từ đồng tiền riêng tư ZCash.

Giao thức zk-SNARK

Sau quá trình cải tiến từng bước này, chúng tôi đã có phiên bản cuối cùng của giao thức zkSNARK, còn được gọi là Pinocchio [Par + 13] (phần không có kiến thức là tùy chọn và được đánh dấu bằng các màu khác nhau), trong đó là :




Kết luận

Cuối cùng chúng tôi đã hoàn thành một giao thức hiệu quả cho phép tính toán bằng chứng:

Ngắn gọn - không phụ thuộc vào lượng tính toán, bằng chứng không đổi, kích thước nhỏ

Không tương tác - bằng chứng có thể được xác minh sau khi tính toán mà không cần tương tác trực tiếp với người chứng minh. tiền đề của sự tương tác

Kiến thức có thể chứng minh được (với Luận cứ về kiến thức) - có một xác suất không thể bỏ qua rằng phát biểu đó là đúng, tức là không thể xây dựng được bằng chứng sai; và người chứng minh biết giá trị tương ứng (tức là : bằng chứng) của phát biểu đúng. Ví dụ: nếu phát biểu là "B là kết quả của sha256(a)" thì điều đó có nghĩa là người chứng minh biết một giá trị a nào đó có thể làm cho B = sha256(a) đúng, bởi vì B có thể chỉ đậu a Tính kiến thức của a, nói cách khác là không thể tính ngược a đến B (giả sử entropy của a là đủ).

Tuyên bố có xác suất đúng không thể bỏ qua (thậm chí@ Ambi Labs: ở đây đề cập đến độ tin cậy của Sự chắc chắn), nghĩa là không thể xây dựng bằng chứng sai

Không có kiến thức ( không có kiến thức ) - thật "khó" để rút ra bất kỳ kiến thức nào từ bằng chứng, tức là không thể phân biệt được nó với các số ngẫu nhiên.

Chú thích

even@ Anbi Lab: Cái gọi là Luận cứ khác với Chứng minh. Giao thức Pinocchio là Đối số chứ không phải Bằng chứng. Điều này là do độ tin cậy của Pinocchio là Độ đúng tính toán, ZK thống kê và loại hệ thống chứng minh này được gọi là Đối số. Cái gọi là Độ tin cậy tính toán ngụ ý thực tế là Prover có thể phá hủy độ tin cậy nếu nó đủ mạnh về mặt tính toán.

Giao thức này dựa trên các tính chất đặc biệt của đa thức, số học mô-đun, mã hóa đồng cấu, mật mã đường cong elip, ghép cặp mật mã và sự khéo léo của nhà phát minh. .

Giao thức này chứng minh việc tính toán một cơ chế thực thi giới hạn đặc biệt, tức là hầu như bất kỳ số lượng biến nào đều được thêm vào cùng nhau nhưng chỉ có thể thực hiện một phép nhân, do đó có cơ hội tối ưu hóa chương trình để tận dụng đặc tính này một cách hiệu quả đồng thời giảm thiểu số lượng tính toán sử dụng cấu trúc này.

Để xác minh một bằng chứng, người xác minh không cần phải biết tất cả các thông tin dữ liệu bí mật. Điều quan trọng là điều này cho phép mọi người xuất bản và sử dụng khóa xác minh được xây dựng phù hợp theo cách không tương tác. Điều này trái ngược với sơ đồ "người xác minh được chỉ định" trong đó chỉ một người tham gia có thể bị thuyết phục về bằng chứng và do đó niềm tin của người đó là không thể chuyển nhượng. Trong zkSNARK, thuộc tính này có thể được triển khai nếu cặp khóa không đáng tin cậy hoặc được tạo bởi một bên.

Lĩnh vực xây dựng bằng chứng không có kiến thức không ngừng phát triển, bao gồm cả việc giới thiệu các tính năng tối ưu hóa ([BCTV13, Gro16, GM17]), các cải tiến như khóa chứng minh và khóa xác minh có thể cập nhật ([Gro+18]) và các phương pháp xây dựng mới (Chống đạn [Bün+17], ZK-STARK [Ben+18], Sonic [Mal+19]).

Chú thích

even@ Anbi Lab: Đến đây phần giới thiệu của loạt bài này đã kết thúc. Bạn đã rất quen thuộc với giao thức zkSNARK (giao thức Pinocchio) ? Trên thực tế, bất kỳ giao thức phức tạp nào cũng có thể được rút gọn thành ý tưởng cốt lõi và làm cho nó dễ hiểu.

Vẫn còn một chặng đường dài để học cách chứng minh không có kiến thức. Bài viết này chỉ là tài liệu giới thiệu, như bài báo Như đã đề cập ở trên, lĩnh vực xây dựng bằng chứng không có kiến thức không ngừng phát triển và những đột phá nghiên cứu mới liên tục được trình bày cho chúng ta. Đây là một lĩnh vực rất thú vị và chúng tôi hoan nghênh bạn bè tiếp tục học tập và nghiên cứu công nghệ chứng minh không có kiến thức cùng chúng tôi.

Một lần nữa xin cảm ơn Maksym Petkus vì đã chia sẻ và cho phép. Bản dịch của bài viết có những thiếu sót, mong được sửa chữa, bổ sung và hướng dẫn.

Nếu bạn có bất kỳ câu hỏi nào về bài viết, vui lòng nhập vòng kết nối WeChat "Zero Knowledge Proof" để để lại tin nhắn Nếu bạn quan tâm đến bằng chứng kiến thức bằng không, bạn bè có thể tham gia nhóm thảo luận Abby Lab để thảo luận.

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

https:/ /medium.com/@imolfar/why-and-how-zk-snark-works-7-constraints-and-public-inputs-e95f6596dd1c

https://medium.com/@imolfar/why- and-how-zk-snark-works-8-zero-know-computation-f120339c2c55


Tài liệu tham khảo
[ con18]—Cộng tác viên Wikipedia. Sự hài lòng về giới hạn. Wikipedia, Bách khoa toàn thư miễn phí. 2018.
[Gen+12]—Rosario Gennaro, Craig Gentry, Bryan Parno và Mariana Raykova. Chương trình bậc hai và NIZK ngắn gọn không có PCP. Mật mã học ePrint Lưu trữ, Báo cáo 2012/215. https://eprint.iacr.org/2012/215.2012.
[Par+13]—Bryan Parno, Craig Gentry, Jon Howell và Mariana Raykova.Pinocchio: Gần như có thể kiểm chứng thực tế Tính toán. Lưu trữ ePrint mật mã, Báo cáo 2013/279. https://eprint.iacr.org/2013/279. 2013.
[BCTV13]—Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza. Succinct Non -Không có kiến thức tương tác cho kiến trúc von Neumann. Lưu trữ ePrint mật mã, Báo cáo 2013/879. https://eprint.iacr.org/2013/879. 2013.
[Gro10]—Jens Groth. 「Dựa trên ghép nối ngắn lập luận không có kiến thức không tương tác". Trong: Hội nghị quốc tế về lý thuyết và ứng dụng mật mã và bảo mật thông tin. Springer. 2010, trang 321–340.
[GM17]—Jens Groth, Mary Maller. Chữ ký Snarky : Chữ ký kiến thức tối thiểu từ SNARK mô phỏng-có thể trích xuất.Kho lưu trữ ePrint mật mã, Báo cáo 2017/540.https://eprint.iacr.org/2017/540.2017.
[Gro+18]—Jens Groth, Markulf Kohlweiss , Mary Maller, Sarah Meiklejohn và Ian Miers. Chuỗi tham chiếu phổ biến và có thể cập nhật với các ứng dụng cho zk-SNARK. Lưu trữ ePrint mật mã, Báo cáo 2018/280. https://eprint.iacr.org/2018/280. 2018.
[Bün+17]—Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille và Greg Maxwell. Chống đạn: Bằng chứng ngắn cho các giao dịch bí mật và hơn thế nữa. Lưu trữ ePrint mật mã học, Báo cáo 2017/1066. https:// eprint .iacr.org/2017/1066. 2017.
[Ben+18]—Eli Ben-Sasson, Iddo Bentov, Yinon Horesh và Michael Riabzev. Tính toàn vẹn tính toán an toàn sau lượng tử, có thể mở rộng và minh bạch. , Báo cáo 2018/046. https://eprint.iacr.org/2018/046.2018.
[Mal+19]—Mary Maller, Sean Bowe, Markulf Kohlweiss và Sarah Meiklejohn. Sonic: SNARKs không kiến thức từ Chuỗi tham chiếu có cấu trúc phổ biến có kích thước tuyến tính và có thể cập nhật. Kho lưu trữ ePrint mật mã, Báo cáo 2019/099. https://eprint.iacr.org/2019/099. 2019.

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