Các bài toán cần chứng minh-Mạch số học-R1CS-Đa thức
**Tại sao cuối cùng chuyển đổi thành đa thức? **
Do các đặc điểm của đa thức, thời gian xác minh được rút ngắn một cách hiệu quả và đạt được sự đơn giản.
** Làm thế nào để đạt được kiến thức bằng không? **
Nói một cách đơn giản, trong quá trình rút ra đa thức, hai số ngẫu nhiên khác được chọn, để đa thức dẫn xuất có thể ngăn người xác minh lấy các hệ số của đa thức ban đầu, tức là đầu vào bí mật của người chứng minh, vì vậy để nhận ra ZK.
**Làm thế nào để không tương tác? **
Trước khi bắt đầu bằng chứng, một bên thứ ba được giới thiệu, nghĩa là cài đặt đáng tin cậy, giao cho người xác minh ban đầu nhiệm vụ chọn các số ngẫu nhiên cho cài đặt đáng tin cậy, do đó nhận ra sự không tương tác giữa người xác minh và người chứng minh.
Công nghệ ZK đã thu hút nhiều sự chú ý trong lĩnh vực Web3 trong hai năm qua. Bắt đầu từ Rollup, ngày càng có nhiều dự án trên các tuyến đường khác nhau đang cố gắng sử dụng công nghệ ZK. Trong số đó, SNARK và STARK là hai thuật ngữ được nghe nhiều nhất, để hiểu rõ hơn về ứng dụng của công nghệ ZK trong giai đoạn sau, ** bài viết này sẽ đơn giản hóa logic chứng minh của SNARK từ góc độ phi kỹ thuật, sau đó sử dụng * * Bản tổng hợp zk của Scroll ** được sử dụng làm ví dụ để minh họa hoạt động của hệ thống bằng chứng zk. **
Mục đích của bài viết là giải thích logic cơ bản, dễ đọc, sẽ cố gắng tránh sử dụng thuật ngữ và sẽ không đi sâu vào chi tiết như các phép biến đổi toán học.
Vào tháng 1 năm 2012, Alessandro Chiesa, giáo sư tại Đại học California, Berkeley, đồng tác giả một bài báo về SNARK và đề xuất thuật ngữ zk-SNARK.
zk-SNARK, tên đầy đủ là Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, là một hệ thống bằng chứng sử dụng công nghệ ZK. ** Cần lưu ý rằng SNARK là tên của một lớp lược đồ và có nhiều phương pháp kết hợp khác nhau có thể triển khai SNARK. **
Zero-Knowledge: Những gì chỉ có người châm ngôn biết sẽ bị ẩn đi, và không ai khác có thể nhìn thấy nó ngoại trừ người châm ngôn.
Ngắn gọn (Succinct): Bằng chứng được tạo ra ít và thời gian xác minh nhanh.
Không tương tác (Non-Interactive): Có rất ít hoặc không có sự tương tác giữa người chứng minh và người chứng minh.
Lập luận: Việc xác minh của người xác minh chỉ có giá trị đối với người chứng minh có khả năng tính toán hạn chế, bởi vì người chứng minh có khả năng tính toán siêu phàm có thể giả mạo bằng chứng, tức là hệ thống có độ tin cậy về mặt tính toán.
Kiến thức: Người chứng minh chỉ có thể tính toán chứng minh nếu biết một số thông tin mà người chứng minh không biết.
Điều zk-SNARK cần giải quyết là "vấn đề xác minh tính toán", nghĩa là liệu người xác minh có thể xác minh hiệu quả kết quả tính toán mà không cần biết quyền riêng tư của người xác minh hay không.
Phần sau đây sẽ sử dụng quy trình xây dựng đơn giản hóa của zk-SNARK để minh họa cách hệ thống kết hợp kiến thức bằng không để đạt được xác minh hiệu quả. **
Xây dựng Zk-SNARK
Biến bài toán cần chứng minh thành đa thức
Nói một cách đơn giản, ý tưởng của SNARK là chuyển đổi bằng chứng về việc mệnh đề có đúng hay không thành bằng chứng về việc đẳng thức đa thức có đúng hay không.
Toàn bộ quá trình chuyển đổi: các bài toán cần kiểm tra ➡ mạch số học ➡ R1CS ➡ đa thức ➡ chuyển đổi giữa các đa thức
Câu hỏi cần kiểm chứng ➡Mạch số học
Để chứng minh một câu hỏi có đúng thông qua tính toán hay không, trước tiên câu hỏi cần chứng minh phải được chuyển thành một bài toán tính toán và bất kỳ phép tính nào cũng có thể được mô tả như một mạch số học.
Các mạch số học thường bao gồm các hằng số, "cổng cộng" và "cổng nhân" Thông qua sự chồng chất của các cổng, chúng ta có thể xây dựng các đa thức phức tạp.
Đa thức được xây dựng bởi mạch số học trong hình trên là: (Inp1+Inp2)*(-1) = Đầu ra
Bài toán trong thực tế vô cùng phức tạp để biến thành một mạch số học, có thể hiểu đơn giản là: nhập vào một nội dung nào đó, nội dung đó được mạch biến đổi và cuối cùng cho ra kết quả. Ngay lập tức:
Dựa vào khái niệm mạch số học, ta xây dựng mạch số học sinh chứng minh, đó là:
Mạch chứa hai bộ đầu vào, đầu vào công khai x và đầu vào bí mật w. Đầu vào công khai x có nghĩa là nội dung là một giá trị cố định của vấn đề cần chứng minh, được biết bởi cả người xác minh và người chứng minh, và đầu vào bí mật w có nghĩa là nội dung chỉ được biết bởi người chứng minh.
Mạch số học mà chúng tôi xây dựng là C( x, w ) = 0, nghĩa là nhập x và w qua mạch và kết quả đầu ra cuối cùng là 0. Khi người chứng minh và người xác minh biết rằng đầu ra của mạch là 0 và đầu vào công khai là x, thì người chứng minh cần chứng minh rằng mình biết đầu vào bí mật w.
Mạch số học ➡R1CS
Cuối cùng, chúng ta cần một đa thức, nhưng mạch số học không thể được chuyển đổi trực tiếp thành đa thức và R1CS cần thiết làm trung gian giữa hai loại, vì vậy mạch số học được chuyển đổi thành R1CS trước.
R1CS, tên đầy đủ là Rank-1 Constraints (hệ thống ràng buộc bậc nhất), là một ngôn ngữ để mô tả các mạch, về cơ bản là một phương trình ma trận-vectơ. Cụ thể, R1CS là một dãy gồm ba vectơ (a,b,c) và nghiệm của R1CS là một vectơ s, trong đó s phải thỏa mãn phương trình:
Trong số đó, đại diện cho hoạt động sản phẩm bên trong.
Chuyển đổi toán học cụ thể ở đây có thể được tìm thấy trong Vatalik: Chương trình số học bậc hai: từ Zero đến Hero
Chúng ta chỉ cần biết rằng vai trò của **R1CS là giới hạn mô tả của từng cổng trong mạch số học, sao cho các vectơ giữa mỗi cổng thỏa mãn mối quan hệ trên. **
R1CS➡Đa thức
Sau khi nhận được phương tiện của R1CS, chúng ta có thể chuyển đổi nó thành một đa thức tương đương.
Chuyển đổi tương đương giữa ma trận và đa thức có thể được thực hiện như trong hình sau:
đa thức
chuyển đổi sang ma trận
Theo tính chất của phép biến đổi tương đương trên, đối với một ma trận thỏa mãn R1CS, ta có thể sử dụng phương pháp nội suy Lagrange để khôi phục lại từng hệ số của đa thức, dựa vào mối quan hệ này ta suy ra ma trận R1CS dưới dạng một quan hệ đa thức, đó là:
Lưu ý: A, B, C tương ứng là một đa thức
Một đa thức tương ứng với một ràng buộc ma trận R1CS tương ứng với bài toán ta muốn chứng minh Qua phép biến đổi trên ta biết được nếu các đa thức thỏa mãn quan hệ trên thì nghĩa là ma trận R1CS của ta đúng, chứng tỏ chứng minh trong mạch số học.Đầu vào bí mật cho cũng đúng.
Cho đến thời điểm này, vấn đề của chúng ta được đơn giản hóa thành: người xác minh chọn ngẫu nhiên một số x và yêu cầu người xác nhận chứng minh rằng A(x) * B(x)=C(x) là đúng. có nghĩa là đầu vào bí mật của người xác nhận là chính xác.
Chuyển đổi giữa các đa thức
Trong các mạch số học phức tạp, có hàng chục nghìn cổng và chúng ta cần xác minh xem mỗi cổng có thỏa mãn ràng buộc R1CS hay không. Nói cách khác, chúng ta cần xác minh sự bằng nhau của A(x) * B(x)=C(x) nhiều lần, nhưng hiệu quả của việc xác minh riêng lẻ từng cái một là quá thấp. hạn chế cửa khẩu tại một thời điểm quan hệ tình dục?
Để dễ hiểu, ta giới thiệu P(x), đặt P(x) = A(x) * B(x) – C(x)
Ta biết rằng bất kỳ đa thức nào cũng có thể phân tích thành đa thức tuyến tính miễn là nó có nghiệm. Vì vậy, chúng tôi chia P(x) thành F(x) và H(x), cụ thể là:
Khi đó F(x) là công khai, có nghĩa là có H(x) = P(x)/F(x), vì vậy đa thức mà chúng ta muốn kiểm chứng cuối cùng biến thành:
A(x) * B(x) – C(x): Chứa các hệ số của đa thức, chỉ người chứng minh biết, tức là đầu vào bí mật.
F(x): Một đa thức công khai được cả người xác minh và người chứng minh biết đến, tức là đầu vào công khai.
H(x): Người chứng minh biết điều đó thông qua tính toán, nhưng người xác minh không thể biết được.
**Bài toán cuối cùng cần chứng minh là: phương trình đa thức A(x) * B(x) – C(x) = F(x) * H(x), đúng với mọi x. **
Bây giờ chỉ cần xác minh đa thức một lần để xác minh rằng tất cả các ràng buộc đều thỏa mãn các quan hệ ma trận.
** Đến đây ta đã hoàn thành việc biến bài toán cần chứng minh thành đa thức chỉ cần nghiệm một lần, nhận thấy tính đơn giản của hệ thức. **
Nhưng cái đơn giản của cách thực hiện này là rút ngắn thời gian xác minh của người xác minh, vậy còn kích thước bằng chứng thì sao?
**Nói một cách đơn giản, trong giao thức chứng minh, cấu trúc cây Merkle được sử dụng, giúp giảm kích thước của bằng chứng một cách hiệu quả. **
Sau khi toàn bộ quá trình chuyển đổi hoàn tất, hai vấn đề sẽ tự nhiên phát sinh:
Tại sao chuyển thành đa thức?
Bởi vì đa thức cho phép chứng minh đơn giản. Vấn đề của bằng chứng không kiến thức là xác minh rằng các phép tính thỏa mãn nhiều ràng buộc và các đa thức có thể xác minh nhiều ràng buộc tại một điểm. Nói cách khác, người xác minh phải xác minh n lần để xác nhận vấn đề, nhưng bây giờ chỉ cần xác minh một lần để xác nhận tính đúng đắn của bằng chứng với xác suất cao.
Tại sao hai đa thức A(x) * B(x) – C(x )= F(x) * H(x) có thể lập được bằng cách chứng minh một điểm trên đa thức?
Điều này được xác định bởi các đặc điểm của đa thức, nghĩa là kết quả tính toán của một đa thức tại bất kỳ điểm nào có thể được coi là biểu diễn của danh tính duy nhất của nó. Đối với hai đa thức, chúng sẽ chỉ cắt nhau tại một số điểm hữu hạn.
Đối với hai đa thức bậc d trên: A(x) * B(x) – C(x) và F(x) * H(x) nếu không bằng nhau thì chỉ có nhiều nhất d điểm Cắt nhau, tức là các nghiệm tại d điểm bằng nhau.
Sau khi hoàn thành việc chuyển đổi đa thức, chúng ta sẽ bước sang giai đoạn chứng minh đa thức.
Chứng minh rằng đa thức đúng
Để minh họa, chúng ta sử dụng đa thức P(x) = F(x) * H(x).
Bây giờ, vấn đề mà câu tục ngữ muốn chứng minh là: với mọi x thì P(x) = F(x) * H(x).
Quá trình kiểm chứng của đa thức trên bởi người chứng minh và người kiểm chứng như sau:
Người xác minh chọn một điểm thử thách ngẫu nhiên x, giả sử x = s;
Sau khi người chứng thực nhận được s, hãy tính P(s) và H(s) rồi đưa hai giá trị này cho người chứng minh;
Người xác minh trước tiên tính F(s), sau đó tính F(s) * H(s) và đánh giá xem F(s) * H(s) = P(s) có đúng hay không và nếu đúng, xác minh được thông qua.
Nhưng nếu suy nghĩ kỹ, chúng ta sẽ thấy rằng có một số vấn đề trong quá trình trên:
Người chứng minh có thể biết được thông tin của cả phương trình, nếu nhận được một điểm s ngẫu nhiên, anh ta có thể tính được F(s), rồi dựng một cặp giả P(x) và H(x), sao cho P(s) ) = F(s) * H(s) để đánh lừa người xác minh.
Người chứng minh không dùng s do người chứng minh đưa ra để tính F(s) và H(s) mà tính toán với giá trị khác để đánh lừa người chứng minh.
Giá trị mà người xác minh nhận được được tính toán bởi đầu vào công khai và đầu vào riêng tư của người minh chứng, nếu người xác minh có sức mạnh tính toán lớn, nó có thể bẻ khóa đầu vào riêng tư của người minh chứng.
Để giải quyết các vấn đề trên, chúng tôi thực hiện các tối ưu hóa sau:
Sau khi trình xác minh chọn một điểm ngẫu nhiên s, nó sẽ thực hiện mã hóa đồng cấu trên s. Mã hóa đồng cấu có nghĩa là nghiệm được tính sau khi mã hóa = nghiệm được mã hóa sau khi tính toán, ở dạng mã hóa này, người chứng thực có thể tính toán nghiệm, nhưng không thể xây dựng sai P(x) và H(x).
Khi người xác minh chọn điểm thử thách s, một tham số ngẫu nhiên khác λ được chọn để tạo mối quan hệ tuyến tính bổ sung giữa s và λ. Người xác minh gửi cả s và λ sau khi mã hóa đồng hình cho người xác minh. Người chứng minh gửi lại bằng chứng và người xác minh cần xác minh mối quan hệ giữa tham số ngẫu nhiên λ và s ngoài việc xác minh xem bằng chứng có đúng hay không.
**Nhằm giải quyết vấn đề người xác minh có thể bẻ khóa đầu vào bí mật, chúng tôi có thể giới thiệu ZK. ** Xem xét toàn bộ chứng minh, ta thấy trong quá trình kiểm chứng, người chứng minh chỉ gửi giá trị đa thức đã tính được cho người kiểm chứng, và người kiểm chứng có thể suy ra hệ số của đa thức thông qua giá trị, là dữ liệu nhập bí mật của tục ngữ. Để ngăn trình xác minh đẩy lùi, chúng ta có thể chọn thêm hai số ngẫu nhiên và thêm một bộ giá trị khi lấy đa thức A, B và C từ R1CS, để đa thức được khôi phục nhiều hơn một bậc so với đa thức ban đầu , do đó việc xác minh Người đọc không thể lấy thông tin của đa thức ban đầu từ đa thức được mã hóa để nhận ra ZK.
Sau khi tối ưu hóa, chúng tôi nhận thấy hệ thống chứng minh vẫn cần có sự tương tác giữa người chứng minh và người chứng minh.
Triển khai không tương tác
**Để đạt được trạng thái không tương tác, SNARK giới thiệu cài đặt đáng tin cậy (Thiết lập). **
Nói cách khác, trước khi bắt đầu bằng chứng, quyền chọn điểm thử thách ngẫu nhiên của người xác minh được chuyển giao cho bên thứ ba đáng tin cậy. Sau khi bên thứ ba chọn tham số ngẫu nhiên λ, họ sẽ đặt λ đã mã hóa vào mạch R1CS. Trong trường hợp này CRS (Chuỗi tham chiếu chung, chuỗi tham chiếu chung) được tạo. Trình xác minh có thể lấy Sv của chính nó từ CRS và người xác thực có thể lấy Sp của chính nó từ CRS.
Cần lưu ý rằng λ cần bị hủy sau khi tạo Sv và Sp. Nếu λ bị rò rỉ, nó có thể được sử dụng để giả mạo giao dịch thông qua xác minh sai.
Quy trình làm việc zk-SNARK
Sau khi hiểu quy trình xây dựng SNARK, dựa trên mạch số học mà chúng tôi đã xây dựng có thể tạo ra bằng chứng, quy trình chứng minh của zk-SNARK như sau:
Cách lập:(C mạch, λ)= (Sv, Sp)
Thông qua mạch C và tham số ngẫu nhiên λ, các tham số ngẫu nhiên Sv và Sp được sử dụng bởi người chứng minh và người xác minh tiếp theo được tạo ra.
Chứng minh(Sp,x,w) = Π
Người châm ngôn tính toán bằng chứng Π thông qua tham số ngẫu nhiên Sp, đầu vào công khai x và đầu vào bí mật w.
Xác minh(Sv,x,Π) == (∃ w st C(x,w))
Trình xác minh xác minh xem C(x,w)=0 có tồn tại hay không thông qua tham số ngẫu nhiên Sv, đầu vào công khai x và bằng chứng Π. Đồng thời, xác minh xem chứng minh có tính toán theo mạch C hay không.
Đến đây, chúng ta đã hoàn thành phần giải thích về toàn bộ zk-SNARK, hãy xem xét trường hợp ứng dụng thực tế.
Trường hợp: Lấy zk Rollup của Scroll làm ví dụ
Vai trò của hệ thống bằng chứng là cho phép người chứng minh thuyết phục người xác minh tin vào một điều;
Đối với hệ thống bằng chứng zk, người xác minh cần phải tin rằng Bằng chứng không kiến thức (bằng chứng không kiến thức) được tính toán bởi thuật toán zk là đúng.
Chúng tôi lấy Rollup zk của Scroll làm ví dụ để minh họa hoạt động của hệ thống bằng chứng zk.
Tổng số đề cập đến tính toán ngoài chuỗi và xác minh trên chuỗi. Đối với zk Rollup, sau khi giao dịch được thực hiện ngoài chuỗi, trình chứng minh cần tạo chứng chỉ zk cho gốc trạng thái mới được tạo sau khi giao dịch được thực hiện, sau đó chuyển chứng chỉ cho hợp đồng L1 Rollup để xác minh trên chuỗi.
Cần lưu ý rằng có hai loại khối trong zk Rollup:
Khối tổng hợp L1: khối được gửi tới Ethereum
Khối L2: một khối bao gồm các giao dịch được gửi bởi người dùng trên L2
Sau đây là quy trình làm việc của Scroll's zk Rollup:
Người dùng bắt đầu giao dịch trong L2, Trình sắp xếp chuỗi truy xuất giao dịch, thực hiện giao dịch ngoài chuỗi và tạo khối L2 và gốc trạng thái mới; đồng thời, gửi dữ liệu giao dịch và gốc trạng thái mới cho hợp đồng Rollup trên Ethereum (gửi dữ liệu giao dịch là để có sẵn dữ liệu);
Khi khối L2 được tạo, Điều phối viên sẽ nhận rãnh thực thi của khối từ Trình sắp xếp chuỗi, sau đó gán ngẫu nhiên rãnh đó cho bất kỳ Con lăn nào;
Con lăn chuyển đổi rãnh thực thi nhận được thành các mạch và tạo chứng chỉ hợp lệ cho từng mạch, sau đó gửi chứng chỉ trở lại Điều phối viên;
Mỗi khi k khối L2 được tạo, Điều phối viên sẽ gửi một tác vụ tổng hợp đến một Con lăn khác để tổng hợp các bằng chứng của k khối thành một bằng chứng tổng hợp duy nhất;
Điều phối viên gửi một bằng chứng tổng hợp duy nhất cho hợp đồng Rollup và hợp đồng Rollup xác minh bằng chứng tổng hợp kết hợp với dữ liệu giao dịch và gốc trạng thái đã gửi trước đó. Nếu quá trình xác minh vượt qua, khối tương ứng được coi là đã hoàn thành trên Scroll.
Như có thể thấy từ quy trình trên, Con lăn là người chứng minh trong hệ thống và hợp đồng Rollup là người xác minh. Con lăn tạo bằng chứng zk cho các giao dịch được thực hiện ngoài chuỗi; hợp đồng Rollup xác minh bằng chứng và nếu quá trình xác minh vượt qua, hợp đồng Rollup sẽ trực tiếp sử dụng gốc trạng thái đã gửi làm gốc trạng thái mới.
Xem bản gốc
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Cấu trúc và trường hợp của zk-SNARK
TL;DR
Các bài toán cần chứng minh-Mạch số học-R1CS-Đa thức
Do các đặc điểm của đa thức, thời gian xác minh được rút ngắn một cách hiệu quả và đạt được sự đơn giản.
Nói một cách đơn giản, trong quá trình rút ra đa thức, hai số ngẫu nhiên khác được chọn, để đa thức dẫn xuất có thể ngăn người xác minh lấy các hệ số của đa thức ban đầu, tức là đầu vào bí mật của người chứng minh, vì vậy để nhận ra ZK.
Trước khi bắt đầu bằng chứng, một bên thứ ba được giới thiệu, nghĩa là cài đặt đáng tin cậy, giao cho người xác minh ban đầu nhiệm vụ chọn các số ngẫu nhiên cho cài đặt đáng tin cậy, do đó nhận ra sự không tương tác giữa người xác minh và người chứng minh.
Công nghệ ZK đã thu hút nhiều sự chú ý trong lĩnh vực Web3 trong hai năm qua. Bắt đầu từ Rollup, ngày càng có nhiều dự án trên các tuyến đường khác nhau đang cố gắng sử dụng công nghệ ZK. Trong số đó, SNARK và STARK là hai thuật ngữ được nghe nhiều nhất, để hiểu rõ hơn về ứng dụng của công nghệ ZK trong giai đoạn sau, ** bài viết này sẽ đơn giản hóa logic chứng minh của SNARK từ góc độ phi kỹ thuật, sau đó sử dụng * * Bản tổng hợp zk của Scroll ** được sử dụng làm ví dụ để minh họa hoạt động của hệ thống bằng chứng zk. **
Mục đích của bài viết là giải thích logic cơ bản, dễ đọc, sẽ cố gắng tránh sử dụng thuật ngữ và sẽ không đi sâu vào chi tiết như các phép biến đổi toán học.
Vào tháng 1 năm 2012, Alessandro Chiesa, giáo sư tại Đại học California, Berkeley, đồng tác giả một bài báo về SNARK và đề xuất thuật ngữ zk-SNARK.
zk-SNARK, tên đầy đủ là Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, là một hệ thống bằng chứng sử dụng công nghệ ZK. ** Cần lưu ý rằng SNARK là tên của một lớp lược đồ và có nhiều phương pháp kết hợp khác nhau có thể triển khai SNARK. **
Điều zk-SNARK cần giải quyết là "vấn đề xác minh tính toán", nghĩa là liệu người xác minh có thể xác minh hiệu quả kết quả tính toán mà không cần biết quyền riêng tư của người xác minh hay không.
Phần sau đây sẽ sử dụng quy trình xây dựng đơn giản hóa của zk-SNARK để minh họa cách hệ thống kết hợp kiến thức bằng không để đạt được xác minh hiệu quả. **
Xây dựng Zk-SNARK
Biến bài toán cần chứng minh thành đa thức
Nói một cách đơn giản, ý tưởng của SNARK là chuyển đổi bằng chứng về việc mệnh đề có đúng hay không thành bằng chứng về việc đẳng thức đa thức có đúng hay không.
Toàn bộ quá trình chuyển đổi: các bài toán cần kiểm tra ➡ mạch số học ➡ R1CS ➡ đa thức ➡ chuyển đổi giữa các đa thức
Câu hỏi cần kiểm chứng ➡Mạch số học
Để chứng minh một câu hỏi có đúng thông qua tính toán hay không, trước tiên câu hỏi cần chứng minh phải được chuyển thành một bài toán tính toán và bất kỳ phép tính nào cũng có thể được mô tả như một mạch số học.
Các mạch số học thường bao gồm các hằng số, "cổng cộng" và "cổng nhân" Thông qua sự chồng chất của các cổng, chúng ta có thể xây dựng các đa thức phức tạp.
Đa thức được xây dựng bởi mạch số học trong hình trên là: (Inp1+Inp2)*(-1) = Đầu ra
Bài toán trong thực tế vô cùng phức tạp để biến thành một mạch số học, có thể hiểu đơn giản là: nhập vào một nội dung nào đó, nội dung đó được mạch biến đổi và cuối cùng cho ra kết quả. Ngay lập tức:
Dựa vào khái niệm mạch số học, ta xây dựng mạch số học sinh chứng minh, đó là:
Mạch chứa hai bộ đầu vào, đầu vào công khai x và đầu vào bí mật w. Đầu vào công khai x có nghĩa là nội dung là một giá trị cố định của vấn đề cần chứng minh, được biết bởi cả người xác minh và người chứng minh, và đầu vào bí mật w có nghĩa là nội dung chỉ được biết bởi người chứng minh.
Mạch số học mà chúng tôi xây dựng là C( x, w ) = 0, nghĩa là nhập x và w qua mạch và kết quả đầu ra cuối cùng là 0. Khi người chứng minh và người xác minh biết rằng đầu ra của mạch là 0 và đầu vào công khai là x, thì người chứng minh cần chứng minh rằng mình biết đầu vào bí mật w.
Mạch số học ➡R1CS
Cuối cùng, chúng ta cần một đa thức, nhưng mạch số học không thể được chuyển đổi trực tiếp thành đa thức và R1CS cần thiết làm trung gian giữa hai loại, vì vậy mạch số học được chuyển đổi thành R1CS trước.
R1CS, tên đầy đủ là Rank-1 Constraints (hệ thống ràng buộc bậc nhất), là một ngôn ngữ để mô tả các mạch, về cơ bản là một phương trình ma trận-vectơ. Cụ thể, R1CS là một dãy gồm ba vectơ (a,b,c) và nghiệm của R1CS là một vectơ s, trong đó s phải thỏa mãn phương trình:
Trong số đó, đại diện cho hoạt động sản phẩm bên trong.
Chuyển đổi toán học cụ thể ở đây có thể được tìm thấy trong Vatalik: Chương trình số học bậc hai: từ Zero đến Hero
Chúng ta chỉ cần biết rằng vai trò của **R1CS là giới hạn mô tả của từng cổng trong mạch số học, sao cho các vectơ giữa mỗi cổng thỏa mãn mối quan hệ trên. **
R1CS➡Đa thức
Sau khi nhận được phương tiện của R1CS, chúng ta có thể chuyển đổi nó thành một đa thức tương đương.
Chuyển đổi tương đương giữa ma trận và đa thức có thể được thực hiện như trong hình sau:
đa thức
chuyển đổi sang ma trận
Theo tính chất của phép biến đổi tương đương trên, đối với một ma trận thỏa mãn R1CS, ta có thể sử dụng phương pháp nội suy Lagrange để khôi phục lại từng hệ số của đa thức, dựa vào mối quan hệ này ta suy ra ma trận R1CS dưới dạng một quan hệ đa thức, đó là:
Lưu ý: A, B, C tương ứng là một đa thức
Một đa thức tương ứng với một ràng buộc ma trận R1CS tương ứng với bài toán ta muốn chứng minh Qua phép biến đổi trên ta biết được nếu các đa thức thỏa mãn quan hệ trên thì nghĩa là ma trận R1CS của ta đúng, chứng tỏ chứng minh trong mạch số học.Đầu vào bí mật cho cũng đúng.
Cho đến thời điểm này, vấn đề của chúng ta được đơn giản hóa thành: người xác minh chọn ngẫu nhiên một số x và yêu cầu người xác nhận chứng minh rằng A(x) * B(x)=C(x) là đúng. có nghĩa là đầu vào bí mật của người xác nhận là chính xác.
Chuyển đổi giữa các đa thức
Trong các mạch số học phức tạp, có hàng chục nghìn cổng và chúng ta cần xác minh xem mỗi cổng có thỏa mãn ràng buộc R1CS hay không. Nói cách khác, chúng ta cần xác minh sự bằng nhau của A(x) * B(x)=C(x) nhiều lần, nhưng hiệu quả của việc xác minh riêng lẻ từng cái một là quá thấp. hạn chế cửa khẩu tại một thời điểm quan hệ tình dục?
Để dễ hiểu, ta giới thiệu P(x), đặt P(x) = A(x) * B(x) – C(x)
Ta biết rằng bất kỳ đa thức nào cũng có thể phân tích thành đa thức tuyến tính miễn là nó có nghiệm. Vì vậy, chúng tôi chia P(x) thành F(x) và H(x), cụ thể là:
Khi đó F(x) là công khai, có nghĩa là có H(x) = P(x)/F(x), vì vậy đa thức mà chúng ta muốn kiểm chứng cuối cùng biến thành:
A(x) * B(x) – C(x): Chứa các hệ số của đa thức, chỉ người chứng minh biết, tức là đầu vào bí mật.
F(x): Một đa thức công khai được cả người xác minh và người chứng minh biết đến, tức là đầu vào công khai.
H(x): Người chứng minh biết điều đó thông qua tính toán, nhưng người xác minh không thể biết được.
**Bài toán cuối cùng cần chứng minh là: phương trình đa thức A(x) * B(x) – C(x) = F(x) * H(x), đúng với mọi x. **
Bây giờ chỉ cần xác minh đa thức một lần để xác minh rằng tất cả các ràng buộc đều thỏa mãn các quan hệ ma trận.
** Đến đây ta đã hoàn thành việc biến bài toán cần chứng minh thành đa thức chỉ cần nghiệm một lần, nhận thấy tính đơn giản của hệ thức. **
Nhưng cái đơn giản của cách thực hiện này là rút ngắn thời gian xác minh của người xác minh, vậy còn kích thước bằng chứng thì sao?
**Nói một cách đơn giản, trong giao thức chứng minh, cấu trúc cây Merkle được sử dụng, giúp giảm kích thước của bằng chứng một cách hiệu quả. **
Sau khi toàn bộ quá trình chuyển đổi hoàn tất, hai vấn đề sẽ tự nhiên phát sinh:
Bởi vì đa thức cho phép chứng minh đơn giản. Vấn đề của bằng chứng không kiến thức là xác minh rằng các phép tính thỏa mãn nhiều ràng buộc và các đa thức có thể xác minh nhiều ràng buộc tại một điểm. Nói cách khác, người xác minh phải xác minh n lần để xác nhận vấn đề, nhưng bây giờ chỉ cần xác minh một lần để xác nhận tính đúng đắn của bằng chứng với xác suất cao.
Điều này được xác định bởi các đặc điểm của đa thức, nghĩa là kết quả tính toán của một đa thức tại bất kỳ điểm nào có thể được coi là biểu diễn của danh tính duy nhất của nó. Đối với hai đa thức, chúng sẽ chỉ cắt nhau tại một số điểm hữu hạn.
Đối với hai đa thức bậc d trên: A(x) * B(x) – C(x) và F(x) * H(x) nếu không bằng nhau thì chỉ có nhiều nhất d điểm Cắt nhau, tức là các nghiệm tại d điểm bằng nhau.
Sau khi hoàn thành việc chuyển đổi đa thức, chúng ta sẽ bước sang giai đoạn chứng minh đa thức.
Chứng minh rằng đa thức đúng
Để minh họa, chúng ta sử dụng đa thức P(x) = F(x) * H(x).
Bây giờ, vấn đề mà câu tục ngữ muốn chứng minh là: với mọi x thì P(x) = F(x) * H(x).
Quá trình kiểm chứng của đa thức trên bởi người chứng minh và người kiểm chứng như sau:
Nhưng nếu suy nghĩ kỹ, chúng ta sẽ thấy rằng có một số vấn đề trong quá trình trên:
Để giải quyết các vấn đề trên, chúng tôi thực hiện các tối ưu hóa sau:
Sau khi tối ưu hóa, chúng tôi nhận thấy hệ thống chứng minh vẫn cần có sự tương tác giữa người chứng minh và người chứng minh.
Triển khai không tương tác
**Để đạt được trạng thái không tương tác, SNARK giới thiệu cài đặt đáng tin cậy (Thiết lập). **
Nói cách khác, trước khi bắt đầu bằng chứng, quyền chọn điểm thử thách ngẫu nhiên của người xác minh được chuyển giao cho bên thứ ba đáng tin cậy. Sau khi bên thứ ba chọn tham số ngẫu nhiên λ, họ sẽ đặt λ đã mã hóa vào mạch R1CS. Trong trường hợp này CRS (Chuỗi tham chiếu chung, chuỗi tham chiếu chung) được tạo. Trình xác minh có thể lấy Sv của chính nó từ CRS và người xác thực có thể lấy Sp của chính nó từ CRS.
Cần lưu ý rằng λ cần bị hủy sau khi tạo Sv và Sp. Nếu λ bị rò rỉ, nó có thể được sử dụng để giả mạo giao dịch thông qua xác minh sai.
Quy trình làm việc zk-SNARK
Sau khi hiểu quy trình xây dựng SNARK, dựa trên mạch số học mà chúng tôi đã xây dựng có thể tạo ra bằng chứng, quy trình chứng minh của zk-SNARK như sau:
Thông qua mạch C và tham số ngẫu nhiên λ, các tham số ngẫu nhiên Sv và Sp được sử dụng bởi người chứng minh và người xác minh tiếp theo được tạo ra.
Người châm ngôn tính toán bằng chứng Π thông qua tham số ngẫu nhiên Sp, đầu vào công khai x và đầu vào bí mật w.
Trình xác minh xác minh xem C(x,w)=0 có tồn tại hay không thông qua tham số ngẫu nhiên Sv, đầu vào công khai x và bằng chứng Π. Đồng thời, xác minh xem chứng minh có tính toán theo mạch C hay không.
Đến đây, chúng ta đã hoàn thành phần giải thích về toàn bộ zk-SNARK, hãy xem xét trường hợp ứng dụng thực tế.
Trường hợp: Lấy zk Rollup của Scroll làm ví dụ
Vai trò của hệ thống bằng chứng là cho phép người chứng minh thuyết phục người xác minh tin vào một điều;
Đối với hệ thống bằng chứng zk, người xác minh cần phải tin rằng Bằng chứng không kiến thức (bằng chứng không kiến thức) được tính toán bởi thuật toán zk là đúng.
Chúng tôi lấy Rollup zk của Scroll làm ví dụ để minh họa hoạt động của hệ thống bằng chứng zk.
Tổng số đề cập đến tính toán ngoài chuỗi và xác minh trên chuỗi. Đối với zk Rollup, sau khi giao dịch được thực hiện ngoài chuỗi, trình chứng minh cần tạo chứng chỉ zk cho gốc trạng thái mới được tạo sau khi giao dịch được thực hiện, sau đó chuyển chứng chỉ cho hợp đồng L1 Rollup để xác minh trên chuỗi.
Cần lưu ý rằng có hai loại khối trong zk Rollup:
Sau đây là quy trình làm việc của Scroll's zk Rollup:
Như có thể thấy từ quy trình trên, Con lăn là người chứng minh trong hệ thống và hợp đồng Rollup là người xác minh. Con lăn tạo bằng chứng zk cho các giao dịch được thực hiện ngoài chuỗi; hợp đồng Rollup xác minh bằng chứng và nếu quá trình xác minh vượt qua, hợp đồng Rollup sẽ trực tiếp sử dụng gốc trạng thái đã gửi làm gốc trạng thái mới.