1. Giới thiệu
ZK-SNARK là một hệ thống chứng minh mật mã cho phép một thực thể chứng minh điều gì đó là đúng mà không tiết lộ thông tin khác.
ZK-SNARK rất hữu ích trong nhiều ứng dụng và lĩnh vực, chẳng hạn như blockchain và điện toán có thể kiểm chứng. Một ứng dụng blockchain đáng chú ý được sử dụng trong ZK-Rollups.
ZK-Rollups là các chuỗi khối lớp thứ hai được xây dựng dựa trên các chuỗi khối khác (chẳng hạn như Ethereum) sử dụng ZK-SNARK (hoặc các hệ thống chứng minh mật mã khác) để chứng minh tính hợp lệ của các chuyển đổi trạng thái. Nghĩa là, mỗi khi thực hiện cập nhật mạng mới (một loạt giao dịch mới được thêm vào), trạng thái mạng mới sẽ được tính toán và bằng chứng về tính hợp lệ của trạng thái này sẽ được tạo ra. Vấn đề là, chỉ cần một thực thể để tạo ra bằng chứng này và sau đó bất kỳ ai cũng có thể tin tưởng vào tính hợp lệ của nó.
Các thuộc tính mong muốn do ZK-Rollups cung cấp thường là (i) khả năng mở rộng và/hoặc (ii) bảo vệ quyền riêng tư. ZK-Rollups đôi khi được gọi là Rollup hiệu quả khi chỉ cần khả năng mở rộng.
Để tính toán bằng chứng trong ZK-Rollups được thiết kế để mở rộng EVM của Ethereum, có thể sử dụng ZK-EVM. Được định nghĩa chặt chẽ, ZK-EVM là một tập hợp các chương trình (mạch) mật mã chịu trách nhiệm tạo ra bằng chứng không có kiến thức (ZKP), mặc dù đôi khi theo cách thông tục, nó cũng đề cập đến toàn bộ ZK-Rollup phổ quát có khả năng EVM.
Định nghĩa 2.ZK-SNARK
SNARK là bằng chứng ngắn gọn cho thấy một tuyên bố nào đó là đúng. Về mặt hình thức, nó thể hiện kiến thức về dấu vết thực thi của thuật toán nhằm tạo ra giải pháp chính xác cho một vấn đề nhất định. Đúng hơn, nó thể hiện kiến thức về các giá trị không công khai và không cố định thực hiện theo dõi. Những giá trị này nói chung thường được gọi là nhân chứng. Các phần tử chứng thực, tức là các phần đầu vào của thuật toán, tạo thành các phần tử chứng thực độc lập vì chúng tồn tại trước khi thực hiện thuật toán và không được xác định bởi các phần tử khác của dấu vết thực thi. Giá trị công khai không cố định của dấu vết thực thi, chỉ định trường hợp vấn đề mà thuật toán giải quyết, được gọi là câu lệnh công khai.
ZK-SNARK là viết tắt của Đối số kiến thức không tương tác ngắn gọn không có kiến thức.
S - Đơn giản
Đơn giản - bằng chứng “ngắn” và thời gian xác minh “nhanh”:
Bằng chứng "ngắn" có nghĩa là quy mô của bằng chứng là cận tuyến tính, so với quy mô của nhân chứng.
Thời gian xác minh "nhanh" có nghĩa là thời gian thực hiện của người xác minh phải (i) tuyến tính theo quy mô của nhân chứng và (ii) tuyến tính trong yêu cầu công khai.
Nhưng trên thực tế, chúng tôi muốn nó không chỉ "ngắn gọn" mà còn "log mức đa thức".
Điều này có nghĩa là quy mô bằng chứng và thời gian xác minh hầu như không phụ thuộc vào quy mô của nhân chứng.
Chứng minh rằng kích thước của π không được tăng nhanh hơn một số lần hằng số bình phương logarit của kích thước của nhân chứng w (với w đủ lớn):
Kích thước của bằng chứng phụ thuộc vào giao thức ZK-SNARK cụ thể. Đối với Plonky2, đó là O(log^2(|w|)), nhưng đó là trường hợp "xấu nhất". Ví dụ: đối với PLONK và Groth16 cổ điển, kích thước của bằng chứng là O(1), là một hằng số.
Thời gian xác minh t_v không được vượt quá một số lần hằng số bình phương logarit của nhân chứng w và tuyến tính theo kích thước của khai báo công khai x (x và w đủ lớn khi chỉ một trong số chúng thay đổi kích thước).
N - Không tương tác - Việc tạo bằng chứng diễn ra mà không nhận được bất kỳ dữ liệu nào từ người xác minh.
ARK - Bằng chứng tri thức - Tương tự như các bằng chứng thông thường, nhưng âm thanh chỉ áp dụng cho các bằng chứng có giới hạn đa thức, trong khi trong bằng chứng, âm thanh có tác dụng đối với các bằng chứng không bị giới hạn về mặt tính toán. Chúng ta sẽ thảo luận về khái niệm âm thanh trong phần tiếp theo.
ZK - Không có kiến thức - Không tiết lộ nhân chứng.
3. Thuộc tính của ZK-SNARK
ZK-SNARK có ba thuộc tính chính như được mô tả bên dưới:
Tính đầy đủ: Nếu người chứng minh biết quỹ đạo thực hiện chính xác của thuật toán thì người xác minh phải tin rằng người chứng minh có kiến thức này.
Tính đúng đắn của kiến thức: Trừ khi người chứng minh thực sự biết quỹ đạo thực hiện chính xác, người chứng minh không thể thuyết phục người xác minh rằng họ biết điều đó, nhưng có một số xác suất rất nhỏ.
Không có kiến thức: Người xác minh không biết gì về quỹ đạo thực hiện ngoại trừ việc nó đúng.
4. Hệ thống chứng minh ZK-SNARK PLONKish
4.1 Giới thiệu về PLONKish ZK-SNARK và chức năng của chúng
Để áp dụng được cho một thuật toán nhất định, hệ chứng minh ZK-SNARK cần biết hệ phương trình trên trường hữu hạn. Các phương trình này mô tả mối quan hệ giữa các giá trị trong bảng quỹ đạo thực hiện của thuật toán (các cấu trúc dữ liệu lưu trữ quỹ đạo thực hiện) để đảm bảo rằng phép tính là Tính toàn vẹn. Ngôn ngữ dùng để biểu diễn hệ phương trình này (còn gọi là hệ các ràng buộc) được gọi là số học.
Hệ thống chứng minh PLONKish ZK-SNARK sử dụng số học với khả năng biểu đạt cao hơn các hệ thống chứng minh cũ. Cách thứ nhất cho phép chúng ta sử dụng các phương trình hệ ràng buộc có dạng đa thức tùy ý trên các biến ràng buộc, trong khi đối với các hệ chứng minh cũ hơn (tức là các hệ dựa trên R1CS), các phương trình này có dạng đa thức tuyến tính và bậc hai. Tính năng này làm cho hệ thống chứng minh PLONKish ZK-SNARK có tác động tích cực đến hiệu quả tính toán của người chứng minh và giúp áp dụng dễ dàng hơn cho các thuật toán khác nhau. Do đó, nhiều hệ thống chứng minh PLONKish ZK-SNARK đã xuất hiện trong những năm gần đây, chẳng hạn như PLONK cổ điển, Halo2, Kimchi, Plonky2, HyperPlonk, v.v.
Trong Taiko, chúng tôi sử dụng một biến thể của hệ thống chứng minh Halo2 dựa trên sơ đồ cam kết đa thức KZG.
Hệ thống chứng minh PLONKish ZK-SNARK bao gồm ba thành phần:
4.2 Kế hoạch cam kết
Lược đồ hứa hẹn cho phép người cam kết xuất bản một giá trị, được gọi là lời hứa, giá trị này ràng buộc người cam kết với một thông điệp mà không tiết lộ chính thông điệp đó. Sau đó, người cam kết có thể mở cam kết và hiển thị thông báo đã cam kết hoặc một phần trong đó cho người xác minh, người có thể kiểm tra xem thông tin được tiết lộ có phù hợp với cam kết hay không.
Các tác giả khác nhau mô tả số lượng thuật toán khác nhau tạo nên một kế hoạch cam kết. Tuy nhiên, chúng ta nên đề cập đến ít nhất bốn thuật toán sau:
Thiết lập: lấy một số tham số ban đầu làm đầu vào và tạo các tham số thiết lập. Cài đặt chỉ định (i) những gì chúng tôi cam kết (ví dụ: đối với sơ đồ cam kết đa thức đơn phương, chúng tôi chỉ định miền hệ số và mức độ tối đa của đa thức mà chúng tôi cam kết) và (ii) mức bảo mật tính bằng bit. Chúng ta có thể xác định mức độ bảo mật một cách đơn giản như sau: Nếu mất O(2^n) thời gian để phá vỡ một hệ thống mã hóa thì hệ thống mã hóa có mức độ bảo mật là n bit.
Lời hứa: Lời hứa tạo thông báo dựa trên các tham số đã đặt.
Mở một phần: Tạo bằng chứng mở một phần cụ thể cho một phần được chọn của thông báo (ví dụ: giá trị của đa thức đơn nhất đã cam kết cho một số tham số), cũng như cài đặt các tham số.
Xác thực: Sử dụng xác thực mở một phần và đặt tham số để kiểm tra xem thông tin mà người chứng minh đưa ra có phải là phần được chỉ định của thông báo tương ứng với cam kết đã chỉ định hay không.
*Đối với một số sơ đồ cam kết, thuật toán "thiết lập" và "mở" có thể không tồn tại (ví dụ: khi sử dụng hàm băm để cam kết các giá trị lớn).
Kế hoạch cam kết cần có những đặc điểm sau:
Ràng buộc: Sau khi người chứng minh cam kết với một thông điệp cụ thể, nó sẽ bị ràng buộc với thông điệp mà nó đã cam kết;
Ẩn: Lời hứa không tiết lộ bất kỳ thông tin nào về tin nhắn. Việc ẩn có thể hoàn hảo, tức là bằng chứng mở một phần không tiết lộ bất kỳ thông tin nào về phần không được truy vấn của tin nhắn (ví dụ: cam kết KZG) hoặc không hoàn hảo, tức là bằng chứng mở một phần tiết lộ một phần thông tin nói trên (ví dụ: dựa trên FRI cam kết đa thức).
Các kế hoạch cam kết có thể được chia thành nhiều loại dựa trên đối tượng mục tiêu: cam kết một phần tử; cam kết vectơ đa thức;
Sơ đồ cam kết đa thức là loại duy nhất được sử dụng trực tiếp trong hệ thống chứng minh PLONKish ZK-SNARK. Đối với các hệ thống chứng minh trên (như PLONK cổ điển, Halo2, Kimchi, Plonky2, v.v.), sơ đồ cam kết đa thức đơn biến là rất quan trọng. Tuy nhiên, hiện nay có một số phương pháp PLONKish ZK-SNARK mới dựa trên sơ đồ cam kết đa thức đa tuyến tính (ví dụ: HyperPlonk).
4.3 Bằng chứng tương tác của Oracle
Bằng chứng tiên tri tương tác là bằng chứng tương tác trong đó người xác minh có "quyền truy cập vào lời tiên tri" để lấy thông điệp của người chứng minh, có thể truy vấn chúng theo cách xác suất và không cần đọc toàn bộ thông báo của người chứng minh.
4.4 Phương pháp phỏng đoán Fiat-Shamir
Phương pháp phỏng đoán Fiat-Shamir cung cấp một cách để chuyển đổi các đối số tương tác (đồng xu công khai) thành các đối số không tương tác. Theo trực giác, ý tưởng là thay thế thử thách ngẫu nhiên của người xác thực bằng hàm băm của thông báo trước đó, nhưng thông tin cụ thể thường không được chỉ định.
*Giao thức tiền xu công cộng là giao thức trong đó người xác thực chỉ gửi các phần tử ngẫu nhiên.
4.5 Nguyên lý làm việc của hệ thống chứng minh ZK-SNARK kiểu PLONK
Trong hệ thống chứng minh ZK-SNARK, phương pháp chứng minh Oracle tương tác đã được sửa đổi được sử dụng để chứng minh kiến thức của nhân chứng, sử dụng các cam kết đa thức để cung cấp cho Oracle quyền truy cập vào thông điệp của người chứng minh và làm cho nó không có tính tương tác thông qua phương pháp phỏng đoán Fiat-Shamir. Trong phần này, chúng tôi sẽ giải thích chi tiết về hàm tạo đã cho.
Hãy nhớ lại rằng việc áp dụng hệ thống chứng minh ZK-SNARK cho một thuật toán đòi hỏi phải xây dựng một hệ thống ràng buộc tương ứng. Để có thể xây dựng nó, chúng ta xác định cấu trúc bảng theo dõi thực thi của thuật toán và các giá trị không đổi trong đó. Chúng tôi sử dụng thuật ngữ "mạch" để chỉ cấu trúc phức tạp của bảng theo dõi thực thi chỉ chứa các hằng số và hệ thống ràng buộc tương ứng. Để tạo bằng chứng ZK-SNARK cho một phiên bản thực thi của thuật toán, chúng ta cần tổng hợp một phiên bản mạch cho nó là phiên bản tương ứng của bảng theo dõi thực thi và mạch của thuật toán (tức là một bảng chỉ định các hằng số, nhân chứng, và giá trị khai báo công khai) kết hợp.
Chúng ta hãy xem xét cấu trúc của bảng theo dõi được sử dụng bởi hệ thống chứng minh ZK-SNARK kiểu PLONK. Tất cả các cột trong bảng như vậy thuộc về một trong ba loại, chúng tôi đặt tên theo thuật ngữ được sử dụng trong Halo2 và mô tả như sau:
Các cột cố định - các ô của chúng chứa các hằng số từ bảng theo dõi thực thi;
Cột instance - dùng để lưu trữ các giá trị khai báo công khai;
Cột gợi ý - nơi lưu trữ toàn bộ dữ liệu nhân chứng (bao gồm các giá trị nhân chứng độc lập và kết quả bí mật được tính toán).
Để tóm tắt, chúng tôi lưu ý những điều sau:
Bảng theo dõi thực thi (loại PLONKish) = cột cố định + cột đối tượng + cột gợi ý; mạch = bảng theo dõi thực thi chỉ chứa các hằng số + hệ thống ràng buộc; mạch + nhân chứng trong bảng của nó + các khai báo công khai trong bảng của nó; tuyên bố công khai, giá trị chứng kiến độc lập) → Ví dụ mạch; Áp dụng hệ thống chứng minh ZK-SNARK cho một thuật toán nhất định = mô tả mạch + xác định quy trình tổng hợp.
Tại sao thuật ngữ "mạch" được sử dụng rộng rãi trong bối cảnh này? Ban đầu, khi chỉ có sẵn các hệ thống chứng minh ZK-SNARK dựa trên R1CS, thật thuận tiện khi biểu diễn hệ thống ràng buộc dưới dạng mạch số học, đầu ra của mạch này phải bằng 0. Chúng tôi tin rằng trong bối cảnh PLONKish SNARK, thuật ngữ "mạch" được sử dụng vì lý do lịch sử. Dù sao, chúng ta hãy xem xét ngắn gọn mạch số học được sử dụng cho các phiên bản ZK-SNARK cũ hơn.
Mạch số học cho SNARK dựa trên R1CS xác định đa thức n biến trên trường hữu hạn và có sơ đồ đánh giá. Ban đầu, nó được biểu diễn dưới dạng biểu đồ chu kỳ có hướng (DAG):
nó bao gồm:
Đầu vào công khai x, dùng để xác định giá trị khai báo công khai;
Đầu vào bí mật w, được sử dụng để chỉ định giá trị chứng kiến độc lập;
Cổng số học được sử dụng để xác định phép cộng và phép nhân trên các trường hữu hạn.
Chúng ta hãy xem một ví dụ về mạch số học trên trường số hữu tỷ.
Chúng tôi bắt đầu từ dưới cùng và làm việc với các cổng thấp nhất trong sơ đồ, tức là (2 x 4 = 8) và (4 + 11 = 15), lưu các giá trị này làm giá trị trung gian;
Sau đó, chúng ta di chuyển lên một hàng (đến hàng thứ hai) và tính tổng của hai giá trị trung gian (mà chúng ta thu được ở bước trước), đó là (8 + 15 = 23);
Vì chúng ta chỉ có ba cổng và chúng ta đã đi qua tất cả nên 23 là kết quả cuối cùng của chúng ta.
Sau khi hệ thống chứng minh PLONKish ZK-SNARK tổng hợp phiên bản mạch, các cột của mỗi bảng theo dõi thực thi phiên bản được mã hóa dưới dạng đa thức trên các trường hữu hạn theo cách sau. Giả sử C_j(x) là cột mô tả đa thức j và ω là gốc nguyên thủy 2^k-th, trong đó k được chọn sao cho 2^k lớn hơn một chút so với chiều cao ban đầu của thể hiện bảng. Phiên bản bảng được điền với các hàng ngẫu nhiên (chỉ với các ô khác 0 trong các cột được đề xuất) để chứa 2^k hàng và C_j(ω^i) được đặt thành giá trị của hàng thứ i của thứ j cột của thể hiện bảng đã cho. Vai trò của phần đệm cho các thuộc tính không có kiến thức sẽ được giải thích sau.
Câu lệnh "ω là nghiệm nguyên thủy 2^k-th" có nghĩa là ω^(2^k) = 1, và chúng ta có ω^t ≠ 1 với mọi số nguyên dương t nhỏ hơn 2^k.
Hệ thống các ràng buộc được chuyển đổi thành dạng phương trình đa thức bằng cách thay thế các biến trong đó bằng các đa thức tương ứng thu được từ các đa thức cột, bằng cách thay thế "x nhân ω nâng lên lũy thừa nào đó" vào vị trí của x.
Ví dụ, chúng ta hãy xem xét phương trình hệ ràng buộc s(i) * (a(i) * b(i) - c(i+1)) = 0. Điều đó có nghĩa là nếu s(i) khác 0 thì a(i) * b(i) phải bằng c(i+1). Ở đây a, b và c là các cột gợi ý, s là cột cố định và i là số hàng hiện tại.
Ràng buộc này có thể được áp dụng cho tất cả 2^k hàng như sau. Cho S(x), A(x), B(x) và C(x) lần lượt là các đa thức ở cột a, b, c và s. Vì vậy, chúng tôi hy vọng:
Điều này có nghĩa là tất cả các phần tử trong tập hợp này phải là nghiệm của S(x) * (A(x) * B(x) - C(x * ω)). Do đó, đa thức này phải chia hết cho:
Bởi vì ω là một nghiệm nguyên thủy cấp 2^k.
Z(x) = x^(2^k) - 1 được gọi là "đa thức triệt tiêu" vì nó bằng 0 với mọi x là các phần tử của nhóm nhân tuần hoàn được tạo bởi ω. Do đó, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 có nghĩa là các ràng buộc trên đúng cho tất cả 2^k hàng.
Giả sử P_0(x), P_1(x), ... , P_m(x) là các ràng buộc được áp dụng cho tất cả 2^k hàng và nhất quán với đa thức S(x) * (A(x) * B(x) được xem xét ở trên ) - C(x * ω)) có dạng tương tự. Nếu α được người xác minh chọn ngẫu nhiên từ trường hữu hạn thì
Điều này có nghĩa là với xác suất cực cao, tất cả các ràng buộc này đều được thỏa mãn cho tất cả 2^k hàng. Phương trình này có nghĩa là chúng ta có thể tìm được đa thức thương T(x) sao cho
Do đó, để người kiểm chứng tin rằng người chứng minh biết nội dung của bảng theo dõi thực thi thỏa mãn tất cả m ràng buộc với xác suất rất cao thì chỉ cần chứng minh rằng đối với một α được chọn ngẫu nhiên, người chứng minh có các lần xuất hiện P_0 (x), P_1(x ),..., các đa thức cột gợi ý và đa thức thương T(x) trong P_m(x) thỏa mãn phương trình đa thức này. Người xác minh có thể thực hiện điều này bằng cách yêu cầu người chứng minh tìm giá trị của đa thức đã cho tại một điểm ngẫu nhiên được người xác minh chọn trong số các điểm không phải gốc ζ của Z(x) và đánh giá cả hai vế của phương trình đó tại điểm đó ζ. Tôi tin rằng người chứng minh có thể biết những đa thức này. Phương pháp này có thể được chứng minh bằng bổ đề Schwartz-Zippel.
Để làm cho việc tạo bằng chứng không tương tác, tất cả các giá trị ngẫu nhiên do trình xác minh tạo ra trong phiên bản tương tác phải được lấy bằng cách sử dụng phương pháp phỏng đoán Fiat-Shamir.
Để ràng buộc người chứng minh với đa thức đề xuất của nó và đa thức thương T(x), một sơ đồ cam kết đa thức được sử dụng. Người chứng minh đưa ra các cam kết đối với các đa thức này, mở các cam kết này tại ζ (hoặc trên ζ * ω^q nếu một số ràng buộc nào đó ảnh hưởng đến các hàng i và i + q), và tạo ra một bằng chứng bao gồm (I) các cam kết này, (II) Giá trị của đa thức tại ζ (hoặc trên ζ * ω^q nếu cần) và (III) chứng minh mở tương ứng. Trên thực tế, để làm cho chứng minh ngắn hơn, hãy sử dụng phép mở nhiều lần, tức là tạo ra một chứng minh nhỏ cho giá trị của tất cả các điểm đa thức. Do đó, bằng chứng là ngắn gọn.
Để đáp ứng thuộc tính không có kiến thức, các hàng được người chứng minh chọn ngẫu nhiên sẽ được thêm vào phiên bản của bảng theo dõi thực thi, làm cho chiều cao của nó là 2^k hàng. Các hàng này chỉ có các ô khác 0 trong cột gợi ý vì chỉ có cột gợi ý mới chứa dữ liệu chúng ta muốn ẩn. Thực hiện việc này trước khi xây dựng các đa thức cột đề xuất sao cho số cặp "giá trị tham số" được tiết lộ trong khoảng thời gian mở cam kết nhỏ hơn số cặp được thêm ngẫu nhiên cho mỗi đa thức. Do đó, đối với mỗi đa thức cột đề xuất, lượng thông tin cần thiết để khôi phục nó sau khi mở cam kết sẽ lớn hơn lượng thông tin của người làm chứng. Tình huống này dẫn đến kiến thức bằng không.
Trong giai đoạn tiền xử lý, tất cả các phiên bản của mạch thực thi đều thực hiện một số tính toán giống nhau, bao gồm thiết lập và tính toán các đa thức cột cố định cũng như các cam kết của chúng đối với sơ đồ cam kết đa thức. Phần dữ liệu được tạo ra bởi các phép tính này được người xác minh sử dụng và thường được gọi là khóa xác minh. Tương tự, khái niệm về khóa chứng minh có thể được định nghĩa. Lược đồ cam kết đa thức cơ bản xác định xem cài đặt tin cậy có được thực hiện trong giai đoạn tiền xử lý hay không.
