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 .). 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. tại đây 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à , trong khi đối với nhánh-k, là . log_2 (n) (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ừ ban đầu thành . log_2 (n) (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 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 . (k-1) logk (n) Nếu chúng ta đặt , việc chứng minh sẽ giảm đi . k = 1024 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 cho thấy tồn tại trong cam kết và là bằng chứng cho lập luận này. π (H (k, v), π_03) H (k, v) C_0 π_03 Tương tự, có nghĩa là tồn tại trong cam kết và là bằng chứng cho lập luận này. (C_0, π_0) C_0 C_Root π_0 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à . 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 ) sẽ nhận được trong khi độ phức tạp của Construct Proof và của cập nhật Proof là tương ứng. cam kết Vector O (1 O (n ^ 2), O (n) 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à tương ứng. O (kn), O (klogk n ), O (logk n) 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 độ và tập giá trị , bạn có thể xây dựng một đa thức ( ), thỏa mãn , và tiến hành cam kết với đa thức này. (c_0, c_1, ...., c_n) (y_1, y_2, ...., y_n) nội suy Lagrange P (c_i ) = y_i và 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). KZG10 IPA Nền tảng KZG cho Điểm đơn Lấy KZG10 làm ví dụ. Đối với đa thức , chúng ta sử dụng để biểu diễn cam kết của đa thức. P (x) [P (s)] _ 1 Như chúng ta đã biết, với , nếu , thì Nghĩa là, nếu chúng ta đặt thì là một đa thức. P (x) P (z) = y (x − z) | (P (x) −y) Q (x) = (P (x) −y) / (x − z) Q (x) 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 trên tương ứng là . Do đó, chúng ta cần xác định hai đa thức: P (x) (z0, z1, ...., zk − 1) (y1, y2, ...., yk − 1) Theo mô tả đã đề cập ở trên, chúng ta cần thỏa mãn . Tức là tồn tại một đa thức , thỏa mãn: V (x) | (P (x) −I (x)) Q (x) Do đó, Prover cần cung cấp các cam kết cho và , đồng thời gửi các cam kết cho người xác minh. [P (s)] _ 1, [Q (s)] _ 1 P (x) Q (x) Trình xác minh tính toán cục bộ và xác minh phương trình: [I (s)] _ 1, [V (s)] _ 2 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 , thì Verkle Tree đã có một cải tiến lớn về kích thước chứng minh. O (log_2n) 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: 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. 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. 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 để 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 tương ứng. C_0 (InnernodeB), C_1 (InnernodeA), C_2 (Root) f_i (x) 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 để đại diện cho chỉ mục. z_i Câu tục ngữ cần chứng minh rằng đối với tập đa thức thỏa mãn các điều kiện sau tại các điểm , 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: f_0 (x), f_1 (x), ...., f_m − 1 (x) z_0, z_1, ...., z_m− 1 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 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 là một đa thức thì sẽ là một đa thức (Xác suất để các phân số giữa ) bù chính xác là rất thấp vì là số ngẫu nhiên). r_0, r_1, ...., r_m − 1 q_i (x) g (x) q_i (x Câu tục ngữ tiến hành cam kết với đa thức và gửi tới trình xác minh. g (x) [g (s)] _ 1 Tiếp theo, để người xác minh tin rằng là cam kết của đa thức . [g (s)] _ 1 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 và gửi nó đến người xác minh. π = [q (s)] _ 1 = [(h (s) −g (s) −y) / (s − t)] _ 1, Người xác minh thực hiện xác minh sau: Tính toán Kiểm chứng Thuộc tính chính 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 .) π Giá trị của 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. y_i Giá trị của không cần phải được cung cấp rõ ràng vì nó có thể được đánh giá từ Key. x_i 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 Dankrad Feist, “PCS multiproofs sử dụng đánh giá ngẫu nhiên”, , truy cập: 2022-05-10. https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html Vitalik Buterin, “Verkle tree”, , truy cập: 2022-05-10. https://vitalik.ca/general/2021/06/18/verkle.html John Kuszmaul, “Verkle Trees,” , truy cập: 2022-05-10. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf

Ethereum

Twitter

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Nghe bài viết này bằng Tiếng Anh, đọc bởi robot thông minh của HackerNoon

dài quá đọc không nổi

Making security fun one episode at a time

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

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

dài quá đọc không nổi

People Mentioned

Company Mentioned

Coin Mentioned

Sin7Y

About Author

chuyên mục

Languages

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI...

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

dài quá đọc không nổi

People Mentioned

Company Mentioned

Coin Mentioned

Sin7Y

About Author

chuyên mục

Languages

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI...

NHỮNG BÀI VIẾT LIÊN QUAN