Trong quá trình xây dựng hệ thống chứng minh Placeholder cho =nil; Foundation, chúng tôi sử dụng một đối số tra cứu dựa trên bài báo Plookup của các nhà nghiên cứu Aztec. Chúng tôi lấy kỹ thuật Plookup làm điểm khởi đầu và sau đó thực hiện một số cải tiến thực tế để viết các mạch PLONK lớn với logic phức tạp.
Đối số tra cứu cho phép người chứng minh chứng minh rằng một số bảng trên trường nguyên tố (sau đây gọi là bảng gán) thỏa mãn các ràng buộc cụ thể: một số ô được tính toán từ bảng gán (đầu vào tra cứu) thuộc về danh sách các giá trị cũng được tính toán từ bảng gán (bảng tra cứu).
Thuật toán nối và tách
Cốt lõi của kỹ thuật Plookup là thuật toán sắp xếp. Chúng tôi gọi nó là join-and-split vì nó bao gồm hai bước:
- nối — các cột trong bảng tra cứu được nối với các cột đầu vào thành một vectơ lớn duy nhất bằng thuật toán sắp xếp lại đặc biệt.
- chia tách — vector được xây dựng lại được chia thành các phần có kích thước ban đầu.
Trường hợp với bảng tra cứu đơn và cột đầu vào đơn được mô tả chi tiết trong bài báo Plookup. Nhưng nó không đủ cho các trường hợp sử dụng của chúng tôi. Chúng tôi cần nhiều bảng tra cứu được đóng gói hiệu quả và các ràng buộc tra cứu được áp dụng cho các hàng và cột tùy ý, và chúng tôi không muốn lặp lại đối số tra cứu cho mỗi cặp (input, table) .
Vì vậy, chúng tôi đã sửa đổi thuật toán join-and-split để có thể nối nhiều hơn hai cột. Nó cho phép chúng tôi sử dụng nhiều ràng buộc tra cứu ngay cả khi chúng được áp dụng trên cùng một hàng và sử dụng một bảng tra cứu lớn, ngay cả khi kích thước của nó lớn hơn toàn bộ số lượng hàng của bảng phân công bằng cách thêm các cột vào bảng phân công thay vì các hàng. Sự cân bằng giữa số lượng hàng và cột của bảng phân công giúp tìm ra sự cân bằng hoàn hảo cho hiệu suất và chi phí xác minh tốt nhất.
Cột chọn
Bài viết gốc có chứa kỹ thuật tra cứu các bộ giá trị được đặt trong cùng một hàng hoặc hàng lân cận. Nó xây dựng các tổ hợp tuyến tính của các cột với một yếu tố ngẫu nhiên. Kết hợp cách tiếp cận này với việc sử dụng biểu thức đa thức cho các bảng tra cứu và các cột đầu vào, chúng tôi đã đạt được sự hỗ trợ đầy đủ cho các cột bộ chọn. Trình thiết kế mạch hiện có thể quản lý chính xác các hàng nào bị ràng buộc và các hàng nào được dành riêng để lưu trữ các bảng tra cứu.
Bài báo Plookup cũng mô tả kỹ thuật hỗ trợ nhiều bảng tra cứu. Họ đề xuất liên kết mỗi bảng tra cứu với mã định danh duy nhất của nó và điền cột thẻ để đánh dấu những hàng nào chứa bảng tra cứu với mã định danh nào. Cột thẻ cho đầu vào giúp đánh dấu những ràng buộc nào được áp dụng cho hàng được đánh dấu. Cột thẻ phải là một phần của tổ hợp tuyến tính ngẫu nhiên được xây dựng cho bảng tra cứu và cột đầu vào tương ứng. Cách tiếp cận này rõ ràng là có hạn chế. Tổng kích thước của các bảng tra cứu phải nhỏ hơn tổng số lượng hàng của bảng.
Chúng tôi đã kết hợp việc sử dụng định danh bảng tra cứu với cấu trúc cột bộ chọn và thuật toán của chúng tôi cho các bảng tra cứu lớn. Những sửa đổi này cho phép lưu trữ và sử dụng các bảng tra cứu mà không cần quan tâm đến các hạn chế đối số tra cứu, nhưng theo thiết kế mạch tốt nhất. Nó biến đối số tra cứu của chúng tôi thành một công cụ linh hoạt và phổ biến.
Bạn có thể tìm thấy mô tả chi tiết về các sửa đổi của chúng tôi trên trang HackMD của chúng tôi. Hãy thoải mái chia sẻ bình luận của bạn!
