Mục tiêu cấp cao: cây Verkle (cây Merkle sử dụng cam kết vectơ đại số ở mỗi cấp thay vì băm) với độ sâu đ nơi tôi có thể chứng minh sự tồn tại của N cặp khóa/giá trị trong cây. Giả sử người xác minh đã có cam kết gốc cây cũng như các cặp khóa/giá trị, tôi muốn kích thước bằng chứng bổ sung là tuyến tính phụ trong cả hai đ hoặc N, hoặc lý tưởng là cả hai. Kiến thức không là không cần thiết.
Tôi đã xem xét các bài đăng của Vitalik và Dankrad về đối số sản phẩm bên trong kiểu Bulletproofs và phân lô cam kết đa thức KZG tại https://vitalik.ca/General/2021/06/18/verkle.html và https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html.
Nếu tôi hiểu đúng thì để chứng minh n quan hệ dạng f_i(x_i) = y_i, giả sử người xác minh đã có từng x_i/y_i, bằng chứng bao gồm một cam kết cho từng đa thức f_i, cũng như bằng chứng hàng loạt có kích thước không đổi (đối với n). Cam kết trên mỗi nút là chi phí chính ở đây và có nghĩa là chúng tôi chỉ có thể đạt được sự cải thiện khoảng (độ sâu của cây merkle / độ sâu của cây verkle ~= 8x) về băng thông.
Lưu ý rằng đối với mỗi đường dẫn, các mối quan hệ này có thuộc tính f_i(x_i) = F_{i+1}, ở đâu F tượng trưng cho sự cam kết. Điều này có vẻ như có thể giúp nén bằng chứng cho từng đường dẫn, nhưng tôi không có bất kỳ ý tưởng cụ thể nào.
Bất kỳ tài liệu tham khảo/giấy tờ liên quan sẽ hữu ích. Cảm ơn!
