Cách thiết kế mạch ZKVM

Cổng tùy chỉnh

Khi thiết kế mạch zkvm, do nhiều cổng tùy chỉnh được xác định, nên có rất nhiều bộ chọn nhị phân được giới thiệu.

Lấy cổng phân chia (trường) làm ví dụ, chúng tôi dự định thiết kế một cổng để xác minh rằng mối quan hệ q = x / y hoạt động giữa ba phần tử q, x, y.

Để thuận tiện, chúng tôi sẽ không thực hiện hoạt động phân chia trường ở cấp độ mạch, thay vào đó, chúng tôi sẽ thực hiện nó bằng cách xác minh mối quan hệ logic sau:

x * inv_y = q

inv_y ∗ y = 1 // đảm bảo y ≠ 0

Giữa hai yếu tố có mối quan hệ bình đẳng. Do đó, chúng ta có bảng Trace sau:

Xác định đa thức w_0 (x), w_1 (x), w_2 (x), w_3 (x) cho các cột w_0, w_1, w_2, w_3 thì các hàng tương ứng với phép toán chia phải thỏa mãn ：

w_0 (x). w_3 (x) - w_2 (x) = 0 w_1 (x). w_3 (x) - 1 = 0

Để đảm bảo rằng mối quan hệ trên có thể được thỏa mãn trong hàng tương ứng, cần có bộ chọn để thực hiện phép chia tương ứng để hạn chế xác minh.

Do đó, chúng tôi đã giới thiệu một cột mới s_ {div} = {0,0, ... 1, ... 0} $. Khi nó được biến đổi thành đa thức s_ {div} (x), phương trình trên sẽ là:

s_ {div} (x) ⋅ (w_0 (x) ⋅ w_3 (x) - w_2 (x)) = 0

s_ {div} (x) ⋅ (w_1 (x) ⋅ w_3 (x) - 1) = 0

Bộ chọn kết hợp

Từ ví dụ trên, chúng ta có thể thấy rằng khi chúng ta xác định một cổng tùy chỉnh mới, một cột bộ chọn s * cần được giới thiệu để tương ứng với cổng.

Nếu chúng ta biểu diễn đa thức ràng buộc tương ứng của cổng với t ∗ (x), cuối cùng chúng ta có thể thu được các ràng buộc sau:

s_ {add} (x) ⋅ t_ {add} (x) = 0

s_ {div} (x) ⋅ t_ {add} (x) = 0

s_ {khối lập phương} (x) ⋅ t_ {khối lập phương} (x) = 0

s_ {sqrt} (x) ⋅ t_ {sqrt} (x) = 0

...

Vì câu tục ngữ cần thực hiện các cam kết với tất cả các đa thức trong quá trình tạo bằng chứng, các đa thức bộ chọn quá nhiều được đưa vào sẽ làm tăng khối lượng công việc của câu tục ngữ và trình xác minh.

Do đó, cần phải tối ưu hóa số bộ chọn đồng thời phải thỏa mãn hai điều kiện sau:

1. Không có gì mất đi ý nghĩa của đa thức bộ chọn, tức là chỉ có thể sử dụng các cổng cụ thể;

   
   

2. Đa thức bộ chọn ít hơn

Trong “Plonky2: Đối số đệ quy nhanh với PLONK và FRI” ( https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf ), có một phương pháp tối ưu hóa “Bộ chọn dựa trên cây nhị phân” , làm giảm số lượng đa thức được chọn thành log (k) và k là số lượng cổng tùy chỉnh.

Trong bài báo Halo2, nhóm zcash đã đưa ra một phương pháp tối ưu hóa mới, có thể nhận ra một số lượng nhỏ hơn đa thức (tương quan với đa thức ràng buộc t ∗ (x) và các tham số được đặt cho đa thức ràng buộc max_degree).

Để dễ hiểu hơn, chúng ta hãy lấy một ví dụ đơn giản (đối với một thuật toán cụ thể, vui lòng tham khảo Bộ chọn kết hợp - Sách halo2 )

Chúng ta có thể thấy rằng chúng ta đã thiết lập 4 cột bộ chọn cho 4 loại cổng tùy chỉnh, không phải như những gì chúng ta muốn giống như đã nói ở trên.

Vì vậy, điều này sẽ làm tăng khối lượng công việc của người đăng báo và người xác minh. Ở đây chúng tôi xác định một cột q mới, thỏa mãn:

Nếu chúng ta xác định một tập hợp {s_ {add}, s_ {div}, s_ {cube}, s_ {sqrt}} (được gọi là rời rạc, nghĩa là không có điểm chung giữa các hàng có thể có) cho bộ chọn s_ {add} , s_ {div}, s_ {cube}, s_ {sqrt} thì dựa vào định nghĩa của cột q, ta có:

Ở đây, xác định một dạng đa thức bộ chọn mới dựa trên cột q và đối với đa thức bộ chọn số k, chúng ta có:

Ví dụ, đối với ràng buộc: s_add ⋅ t_add (x) = 0, có thể được viết lại thành:

Công thức trên có thể được mở rộng thành:

Bộ

Sau đó, con số giá trị thực thu được:

Có thể thấy rằng nó làm tương tự như bộ chọn ban đầu. Do đó, đối với các ràng buộc:

s_ {add} (x) ⋅ t_ {add} (x) = 0

s_ {div} (x) ⋅ t_ {add} (x) = 0

s_ {khối lập phương} (x) ⋅ t_ {khối lập phương} (x) = 0

s_ {sqrt} (x) ⋅ t_ {sqrt} (x) = 0

...

Chúng ta có thể viết lại các ràng buộc thành:

Đối với các ràng buộc ở trên, chúng ta chỉ cần tiến hành cam kết với đa thức q (x). Nhưng điều đáng chú ý là, phương pháp này cũng đã làm tăng mức độ ràng buộc.

Cho đến nay, chúng tôi đã đạt được hai điểm nêu trên:

1. Không có gì mất đi ý nghĩa của đa thức bộ chọn, nghĩa là chỉ có thể sử dụng các cổng cụ thể;

   
   

2. Đa thức bộ chọn ít hơn

Tất nhiên, có những giới hạn đối với Mức bị ràng buộc trong giao thức, do đó, số bộ chọn tham gia kết hợp bị giới hạn, tức là số bộ chọn kết hợp đơn lẻ phụ thuộc vào giá trị biên của Mức độ và max_degree của đa thức ràng buộc t ∗ (x).

Do đó, cần có nhiều cột kết hợp hơn, và dù sao, con số vẫn nhỏ hơn nhiều so với cột ban đầu.

Để biết thêm các trường hợp xử lý và chi tiết thuật toán, vui lòng tham khảo Bộ chọn kết hợp - Sách halo2 .

Người giới thiệu

1. "Cuốn sách hào quang",

   https://zcash.github.io/halo2/design/implementation/selector-comosystem.html

   
   

2. Polygon Zero Team, “Plonky2: Đối số đệ quy nhanh với PLONK và FRI”, https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf , truy cập: 2022-02-06