Tham gia lặn sâu vào cây Verkle cho Ethereum

So với Merkle Tree, Verkle Tree đã được cải thiện rất nhiều về kích thước Proof như một phần quan trọng của bản nâng cấp ETH2.0. Khi nói đến dữ liệu có kích thước một tỷ, bằng chứng Cây Merkle sẽ chiếm 1kB, trong khi bằng chứng Cây Verkle chỉ cần không quá 150 byte.

Khái niệm Cây Verkle được đề xuất vào năm 2018 (Có thể tìm thêm thông tin chi tiết tại đây .). Bài đánh giá công nghệ thứ 23 của Sin7Y sẽ chứng minh nguyên tắc của Cây Verkle.

Merkle Tree

Trước khi tìm hiểu về Verkle Tree, điều quan trọng là phải hiểu khái niệm Merkle Tree. Merkle Tree là một Accumulator phổ biến, có thể được sử dụng để chứng minh rằng một phần tử tồn tại trong Accumulator như thể hiện trong hình sau:

Để chứng minh rằng (key: value) = (06: 32) tồn tại trong Cây (được đánh dấu màu xanh lá cây), Proof phải chứa tất cả các nút được đánh dấu đỏ trong hình.

Người xác minh có thể tính toán Gốc theo phương pháp được hiển thị trong Hình 1, và sau đó so sánh nó với Gốc dự kiến (được đánh dấu màu xám).

Có thể dự đoán rằng với chiều sâu và chiều rộng của Cây lớn hơn, kích thước Proof cũng sẽ lớn hơn (đối với nhánh-2, độ phức tạp là log_2 (n) , trong khi đối với nhánh-k, là (k-1) log_k (n) .

Ngoài ra, trình xác minh cần phải thực hiện một số lượng lớn các phép tính Hash từ cấp độ cơ bản đến cấp độ cao hơn. Do đó, việc tăng chiều sâu và chiều rộng của Cây dẫn đến khối lượng công việc của người xác minh tăng lên là điều không thể chấp nhận được.

Verkle Tree - Khái niệm

Chỉ cần tăng chiều rộng của Cây có thể làm giảm độ sâu của nó, nhưng kích thước bằng chứng sẽ không giảm vì kích thước bằng chứng thay đổi từ log_2 (n) ban đầu thành (k-1) log_k (n) .

Có nghĩa là, đối với mỗi lớp, câu tục ngữ cần cung cấp (k-1) thông tin về nút bổ sung. Trong bài báo Verkle Tree, John Kuszmaul đã đề cập đến một sơ đồ để giảm độ phức tạp của chứng minh thành logk (n) .

Nếu chúng ta đặt k = 1024 , việc chứng minh sẽ giảm đi log_2 (k) = 10 lần .

Thiết kế của Verkle Tree được hiển thị như sau:

Đối với mỗi nút, có hai phần thông tin: (1) giá trị; (2) chứng minh tồn tại π . Ví dụ, dấu màu xanh lá cây (H (k, v), π_03) cho thấy H (k, v) tồn tại trong cam kết C_0 và π_03 là bằng chứng cho lập luận này.

Tương tự, (C_0, π_0) có nghĩa là C_0 tồn tại trong cam kết C_Root và π_0 là bằng chứng cho lập luận này.

Trong bài báo Verkle Tree, phương pháp cam kết tồn tại như vậy được gọi là cam kết Vector . Nếu lược đồ cam kết Vector được sử dụng để thực hiện cam kết tồn tại cho dữ liệu gốc, độ phức tạp của Proof with O (1 ) sẽ nhận được trong khi độ phức tạp của Construct Proof và của cập nhật Proof là O (n ^ 2), O (n) tương ứng.

Do đó, để đạt được sự cân bằng, lược đồ K-ary Verkle Tree được sử dụng trong Verkle Tree trên giấy (như thể hiện trong Hình 2) để làm cho độ phức tạp của việc xây dựng Proof, cập nhật Proof và Proof là O (kn), O (klogk n ), O (logk n) tương ứng.

So sánh hiệu suất cụ thể được thể hiện trong Bảng 1:

Trong bài viết này, chúng tôi không có ý định cung cấp giới thiệu chi tiết về một số lược đồ cam kết vectơ cụ thể, mà John Kuszmaul đã giải thích rõ trong bài báo của mình.

May mắn thay, so với cam kết vectơ, chúng ta có một công cụ hiệu quả hơn được gọi là cam kết đa thức.

Cho một nhóm gồm tập tọa độ (c_0, c_1, ...., c_n) và tập giá trị (y_1, y_2, ...., y_n) , bạn có thể xây dựng một đa thức ( nội suy Lagrange ), thỏa mãn P (c_i ) = y_i , và tiến hành cam kết với đa thức này.

KZG10 và IPA là các lược đồ cam kết đa thức phổ biến (Tại thời điểm này, cam kết là một điểm trên đường cong elliptic, thường có kích thước từ 32 đến 48 byte).

Nền tảng

KZG cho Điểm đơn

Lấy KZG10 làm ví dụ. Đối với đa thức P (x) , chúng ta sử dụng [P (s)] _ 1 để biểu diễn cam kết của đa thức.

Như chúng ta đã biết, với P (x) , nếu P (z) = y , thì (x − z) | (P (x) −y) Nghĩa là, nếu chúng ta đặt Q (x) = (P (x) −y) / (x − z) thì Q (x) là một đa thức.

Bây giờ, chúng ta tạo ra một chứng minh cho P (x) P (x) thỏa mãn P (z) = yP (z) = y. Tức là, tính toán [Q (s)] 1 [Q (s)] 1 và gửi nó đến người xác minh, người cần xác minh:

Vì s là điểm được chọn ngẫu nhiên trong miền hữu hạn F nên xác suất của hành vi xấu xa thành công của câu tục ngữ là bậc (Q) / P ( bổ đề Schwartz – Zippel ).

KZG cho nhiều điểm

Bây giờ, chúng ta muốn chứng minh rằng các giá trị của đa thức P (x) trên (z0, z1, ...., zk − 1) tương ứng là (y1, y2, ...., yk − 1) . Do đó, chúng ta cần xác định hai đa thức:

Theo mô tả đã đề cập ở trên, chúng ta cần thỏa mãn V (x) | (P (x) −I (x)) . Tức là tồn tại một đa thức Q (x) , thỏa mãn:

Do đó, Prover cần cung cấp các cam kết [P (s)] _ 1, [Q (s)] _ 1 cho P (x) và Q (x) , đồng thời gửi các cam kết cho người xác minh.

Trình xác minh tính toán cục bộ [I (s)] _ 1, [V (s)] _ 2 và xác minh phương trình:

Rõ ràng là kích thước bằng chứng là không đổi cho dù có bao nhiêu Điểm. Nếu chúng ta chọn đường cong BLS12-381, kích thước Proof chỉ là 48 byte, rất hiệu quả.

Cây Verkle - ETH

So với Merkle Tree, trong đó để chứng minh sự tồn tại của một phần tử, câu tục ngữ vẫn cần cung cấp kích thước chứng minh với kích thước O (log_2n) , thì Verkle Tree đã có một cải tiến lớn về kích thước chứng minh.

Hãy xem một ví dụ đơn giản về Verkle Tree.

Có thể thấy rằng, tương tự như cấu trúc Merkle Patricia Tree, các nút có thể được chia thành ba loại - nút rỗng, nút trong và nút lá.

Chiều rộng của mỗi cây nút bên trong là 16 (0000-> 1111 trong hệ thập lục phân). Để chứng minh rằng trạng thái của nút lá là (0101 0111 1010 1111 -> 1213), chúng ta cần tiến hành cam kết với nút Bên trong A và nút Bên trong B:

1. Chứng minh rằng giá trị của cam kết bên trong nút B là băm (0101 0111 1010 1111, 1213) tại chỉ số 1010.

   
   

2. Chứng minh rằng giá trị của cam kết bên trong nút A là băm (cm_B) tại chỉ mục 0111.

   
   

3. Chứng minh rằng giá trị của cam kết của nút Root là băm (cm_A) tại chỉ mục 0101;

Sử dụng C_0 (InnernodeB), C_1 (InnernodeA), C_2 (Root) để biểu diễn các cam kết được đề cập ở trên và tương ứng chúng với đa thức f_i (x) tương ứng.

Do đó, Prover cần chứng minh:

Nén cho nhiều Polys

Để làm cho nó dễ dàng, chúng tôi sẽ sử dụng z_i để đại diện cho chỉ mục.

Câu tục ngữ cần chứng minh rằng đối với tập đa thức f_0 (x), f_1 (x), ...., f_m − 1 (x) thỏa mãn các điều kiện sau tại các điểm z_0, z_1, ...., z_m− 1 , tương ứng:
Theo mô tả trước (KZG cho Điểm đơn), đối với mỗi đa thức, tồn tại một đa thức thương thỏa mãn:
Prover cần thực hiện cam kết đối với đa thức ban đầu và đa thức thương, và gửi nó đến Người xác minh:

Người xác minh thực hiện xác minh:
Rõ ràng là chúng tôi không muốn trình xác minh thực hiện nhiều thao tác ghép nối như vậy (nó tốn kém). Do đó, chúng ta cần thực hiện một Compress như sau.

Tạo một số ngẫu nhiên r_0, r_1, ...., r_m − 1 và tập hợp các đa thức thương ở trên lại với nhau:
Giả sử rằng nếu và chỉ khi mỗi q_i (x) là một đa thức thì g (x) sẽ là một đa thức (Xác suất để các phân số giữa q_i (x ) bù chính xác là rất thấp vì là số ngẫu nhiên).

Câu tục ngữ tiến hành cam kết với đa thức g (x) và gửi [g (s)] _ 1 tới trình xác minh.

Tiếp theo, để người xác minh tin rằng [g (s)] _ 1 là cam kết của đa thức g (x) .

Quan sát dạng của đa thức g (x) g (x), ta có thể viết thành:

Chọn một giá trị tt ngẫu nhiên và có:

Xác định đa thức:

Cam kết của nó có thể được tính theo phương pháp sau:

Khi đó giá trị của đa thức h (x) −g (x) h (x) −g (x) tại điểm tt là:

Tính đa thức thương q (x) = (h (x) −g (x) −y) / (x − z) .

Tính cam kết π = [q (s)] _ 1 = [(h (s) −g (s) −y) / (s − t)] _ 1, và gửi nó đến người xác minh.

Người xác minh thực hiện xác minh sau:

1. Tính toán

   

2. Kiểm chứng

   

Thuộc tính chính

1. Bất kỳ số điểm nào có thể được chứng minh bằng cách sử dụng lược đồ này mà không thay đổi kích thước Bằng chứng. (Đối với mỗi cam kết, có một bằng chứng π .)

   
   

2. Giá trị của y_i không cần được cung cấp rõ ràng vì nó là giá trị băm của giá trị lớp tiếp theo.

   
   

3. Giá trị của x_i không cần phải được cung cấp rõ ràng vì nó có thể được đánh giá từ Key.

   
   

4. Thông tin công khai được sử dụng bao gồm cặp khóa / giá trị cần chứng minh và các cam kết tương ứng từ cấp cơ bản đến cấp trên.

Người giới thiệu

1. Dankrad Feist, “PCS multiproofs sử dụng đánh giá ngẫu nhiên”, https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html , truy cập: 2022-05-10.

   
   

2. Vitalik Buterin, “Verkle tree”, https://vitalik.ca/general/2021/06/18/verkle.html , truy cập: 2022-05-10.

   
   

3. John Kuszmaul, “Verkle Trees,” https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf , truy cập: 2022-05-10.