Tìm hiểu về Đối số tra cứu trong một bài viết

特邀专栏作者

2022-12-22 09:44

Bài viết này có khoảng 2848 từ, đọc toàn bộ bài viết mất khoảng 5 phút

Bài viết này sẽ tập trung vào đối số Tra cứu, một trong những công cụ giúp OlaVM đạt hiệu suất cao.

TL;DR

Như đã đề cập trong bài viết trước Xin chào, OlaVM!, tầm nhìn của OlaVM là xây dựng một ZKVM hiệu suất cao. Bài viết này sẽ tập trung vào một trong những công cụ cho phép OlaVM đạt được hiệu suất cao, đối số Tra cứu. Đối số tra cứu đóng vai trò quan trọng trong việc giảm kích thước mạch nhằm nâng cao hiệu suất của ZK, được sử dụng rộng rãi trong thiết kế mạch của ZKVM, qua bài viết này các bạn có thể tìm hiểu:

1. Đối số Tra cứu sẽ đóng vai trò gì trong ZKVM?

2. Nguyên tắc giao thức Plookup.

3. Nguyên tắc giao thức đối số Tra cứu của Halo 2.

tiêu đề cấp đầu tiên

The roles in ZKVM

Cái gọi là ZKVM trên thực tế sử dụng ZK để hạn chế tất cả quá trình thực thi của VM, quá trình thực thi của VM nói chung có thể được chia thành: thực thi lệnh, truy cập bộ nhớ, thực thi chức năng tích hợp, v.v. Có vẻ hơi không thực tế khi triển khai các ràng buộc đối với các hoạt động này trong một dấu vết. Đầu tiên, các ràng buộc của các loại hoạt động khác nhau tương ứng với các độ rộng theo dõi khác nhau. Nếu độ rộng theo dõi tương ứng với một trong các ràng buộc là đặc biệt lớn, nó sẽ gây ra các ràng buộc còn lại để tương ứng với độ rộng vết.lãng phí; sau đó, nếu có quá nhiều loại hoạt động khác nhau trong một vết, nhiều bộ chọn hơn sẽ được đưa vào, điều này sẽ không chỉ làm tăng số lượng đa thức mà còn tăng thứ tự của các ràng buộc; cuối cùng, do giới hạn thứ tự của nhóm, dòng theo dõi Số lượng không thể vượt quá thứ tự của nhóm này, do đó, nên giảm thiểu số lượng dòng theo dõi bị chiếm bởi một số loại hoạt động.

Vì vậy, để đơn giản, chúng ta cần:

a. Chia các loại hoạt động khác nhau thành nhiều dấu vết phụ, sau đó chứng minh một cách riêng biệt rằng cần có đối số Tra cứu giữa dấu vết chính và dấu vết phụ để đảm bảo tính nhất quán của dữ liệu.

B. Đối với một số tính toán không thân thiện với ZK, chúng tôi có thể giảm kích thước của dấu vết thông qua công nghệ đối số Tra cứu, chẳng hạn như các phép toán bit.

tiêu đề phụ

Lookup between trace tables

Mô tả hình ảnh

Hình 1. Tra cứu giữa các dấu vết

tiêu đề phụ

Lookup for ZK-unfriendly operations

Như đã đề cập trước đó, bằng chứng của mỗi dấu vết phụ là độc lập, do đó, việc có được một dấu vết càng nhỏ càng tốt sẽ nâng cao hiệu quả của phép chứng minh. Lấy bitwise làm ví dụ, các thao tác bitwise bao gồm AND, XOR, NOT ba thao tác. Nếu bạn chỉ muốn thực hiện các ràng buộc đối với các hoạt động theo bit thông qua các mạch, điều bạn cần làm có thể là chia mỗi op thành nhiều nhánh nhị phân.Nếu các op này rộng 3 2 bit, chúng sẽ được chia thành 32 nhánh. Sau đó, bạn cần phải hạn chế:

Tổng cộng có 3 + 32 * 3 = 99 ô theo dõi được sử dụng và số ràng buộc là 3 kiểm tra tổng + 32 theo bit = 35.

Mô tả hình ảnh

Hình 2. Tra cứu trong Phép tính số học

tiêu đề cấp đầu tiên

tiêu đề phụ

tiêu đề cấp đầu tiên

tiêu đề phụ

tiêu đề cấp đầu tiên

Extend - 1 : Vector Lookup

Extend - 2 : Multi-tables

Links between Plookup and Lookup

Cả giao thức Plookup và giao thức tra cứu Halo 2 đều có thể chứng minh f⊂t, nhưng ý tưởng của hai giao thức là khác nhau và sự khác biệt như sau:

Plookup cần sử dụng f và t để xây dựng một dãy mới s, các phần tử trong f và t xuất hiện ít nhất một lần trong s, sau đó chứng minh rằng s⊂t bằng cách so sánh các tập hợp khoảng cách khác 0 của các phần tử trong s và t bằng nhau , và cuối cùng f⊂s⊂t→f⊂t.

Tra cứu của Halo 2 chứng minh trực tiếp f⊂t mà không cần xây dựng một chuỗi mới, ngắn gọn hơn so với tra cứu.

tiêu đề cấp đầu tiên