1. Giới thiệu

Vào ngày cuối cùng của năm 2023, Vitalik chia sẻ lộ trình của Ethereum cho năm 2023 trên Twitter, tóm tắt tiến triển của Ethereum trong năm. Phần lộ trình "The Verge" mô tả cách công nghệ Ethereum có thể xác minh trạng thái blockchain một cách đơn giản và hiệu quả hơn. Một khái niệm cốt lõi được đề cập ở đó là Verkle Trees. Vậy, Verkle Trees là gì, tại sao Ethereum cần nó, và Verkle Trees giải quyết vấn đề như thế nào? Mục tiêu của bài viết này là trả lời những câu hỏi này cho độc giả mà không đi quá sâu vào mật mã học và toán học, giúp những người hiểu biết về Ethereum một cách nhanh chóng hiểu được khái niệm của Verkle Trees.

2. Truy vấn có thể xác minh

Công nghệ truy vấn có thể xác minh được nghiên cứu rộng rãi trong lĩnh vực cơ sở dữ liệu truyền thống, chủ yếu được sử dụng để giải quyết các vấn đề tin cậy với cơ sở dữ liệu bên ngoài. Trong nhiều tình huống, chủ sở hữu dữ liệu có thể chọn không lưu trữ dữ liệu bản thân mình mà thay vào đó giao nhu cầu cơ sở dữ liệu của họ cho một bên thứ ba để cung cấp dịch vụ cơ sở dữ liệu (như cơ sở dữ liệu đám mây). Tuy nhiên, do bên thứ ba không phải lúc nào cũng đáng tin cậy, tính uy tín của kết quả truy vấn mà họ trả về cho người dùng khó mà đảm bảo. Các giải pháp truy vấn có thể xác minh hiện tại cho cơ sở dữ liệu truyền thống chủ yếu thuộc hai loại: dựa trên ADS (Cấu trúc Dữ liệu Xác minh) và dựa trên tính toán có thể xác minh.

ADS là một kỹ thuật truy vấn có thể xác minh được sử dụng rộng rãi trong các cơ sở dữ liệu truyền thống, chủ yếu dựa trên cấu trúc như Cây Merkle hoặc các cấu trúc tích lũy tương tự. Với sự tiến hóa của các công cụ mật mã, nhiều nhà nghiên cứu dần dần bắt đầu khám phá việc sử dụng các kỹ thuật tính toán có thể xác minh để giải quyết các vấn đề với các truy vấn không đáng tin cậy. Một số kế hoạch tính toán có thể xác minh dựa trên các giao thức Chứng minh Zero-Knowledge, như SNARKs, có thể ủng hộ một cách gián tiếp các truy vấn có thể xác minh cho cơ sở dữ liệu bên ngoài. Các kế hoạch này hỗ trợ một loạt các loại truy vấn và tạo ra ít thông tin xác minh hơn, nhưng chúng có chi phí tính toán cao hơn.

Hiện tại, Ethereum sử dụng Cây Merkle để thực hiện các truy vấn có thể xác minh, và Công nghệ Cây Verkle cũng dựa trên Công nghệ Cây Merkle. Do đó, hãy trước tiên giới thiệu Cây Merkle để giúp độc giả hiểu vai trò của các truy vấn có thể xác minh bằng cách sử dụng chúng như một ví dụ.

3. Cây Merkle

3.1. Định nghĩa và Đặc điểm của Cây Merkle

Cây Merkle là một cấu trúc giống như cây thường được sử dụng trong mật mã, phù hợp để giải quyết các vấn đề về tính toàn vẹn dữ liệu. Dưới đây là một cấu trúc Cây Merkle điển hình: các nút lá biểu thị dữ liệu gốc hoặc các giá trị băm của chúng, và mỗi nút không phải lá (nội tại) chứa băm kết hợp của các nút con của nó.

Cây Merkle có hai đặc điểm quan trọng:

1. Sự chống thay đổi: Cây Merkle thường được xây dựng bằng cách sử dụng các hàm băm chống va chạm, làm cho việc tìm ra hai thông điệp khác nhau tạo ra cùng một giá trị băm trở nên không thể tính toán được. Từ cấu trúc của một Cây Merkle, rõ ràng rằng bất kỳ sửa đổi nào đối với dữ liệu giao dịch trong một nút lá sẽ dẫn đến sự thay đổi của giá trị băm gốc của cây.
2. Xác minh tính toàn vẹn hiệu quả của các tập dữ liệu lớn: Người xác minh chỉ cần lưu trữ giá trị băm gốc của cây Merkle để xác minh tính toàn vẹn của bất kỳ dữ liệu nào. Điều này được đạt được mà không cần truyền toàn bộ tập dữ liệu, mà thay vào đó sử dụng các nút sibling dọc theo con đường từ lá đến gốc, được biết đến là Một Con Đường Merkle. Những nút sibling này có thể được sử dụng để tái tạo giá trị băm gốc cho mục đích xác minh.

3.2. Làm thế nào để xây dựng một chứng minh Merkle?

Trong một kịch bản truy vấn có thể xác minh thông thường, có một bên chứng minh và một bên xác minh. Bên chứng minh cần tạo ra một bằng chứng và gửi nó cho bên xác minh. Tương ứng với mạng Ethereum, một kịch bản ứng dụng điển hình là khi một nút nhẹ (một khách hàng chỉ lưu trữ tiêu đề khối) truy vấn dữ liệu giao dịch từ một nút đầy đủ hoặc một nút lưu trữ (khách hàng với tất cả dữ liệu) và nhận một bằng chứng Merkle để xác minh cục bộ xem kết quả truy vấn có đúng hay không.

Bằng chứng Merkle bao gồm ba phần sau đây:

1. Hash gốc của cây Merkle cho bộ dữ liệu đầy đủ.
2. Khối dữ liệu mà tính toàn vẹn cần phải được chứng minh.
3. Con đường Merkle, bao gồm các giá trị của tất cả các nút sibling trên con đường từ nút lá đến nút gốc.

Trong số đó, hash gốc của cây Merkle cần được gửi trước cho người xác minh thông qua một phương tiện đáng tin cậy, và người xác minh phải tin tưởng vào giá trị này. Trong Ethereum, tính đáng tin cậy của dữ liệu khối được đảm bảo bằng thuật toán đồng thuận, và hash gốc của cây Merkle được chứa trong tiêu đề khối.

Dưới đây là một ví dụ cụ thể: khi người chứng minh cần chứng minh cho người xác minh rằng "4" là một khối dữ liệu tồn tại trong tập dữ liệu, và người xác minh giữ giá trị hash gốc đáng tin cậy "1d25" của cây Merkle hoàn chỉnh của tập dữ liệu, sau đó người chứng minh chỉ cần cung cấp tất cả dữ liệu được đánh dấu màu xanh. Giả sử có n mảnh dữ liệu trong tập hợp, tối đa cần 𝘭𝘰𝘨₂(𝘯) lần tính toán hash để xác minh tính chính xác của bất kỳ khối dữ liệu nào.

Các nút nhẹ của Ethereum chỉ đồng bộ các tiêu đề khối, trong đó chứa các gốc của cây Merkle cho các tập dữ liệu khác nhau (cây trạng thái, cây giao dịch, cây biên nhận). Khi một nút nhẹ truy vấn một nút đầy đủ cho dữ liệu của một nút lá cụ thể trong cây, nút đầy đủ trả về dữ liệu ban đầu cùng với đường đi chứng minh Merkle tương ứng. Điều này cho phép nút nhẹ tin tưởng vào tính chính xác của kết quả truy vấn.

3.3. Các biến thể của Cây Merkle

Xây dựng trên nền tảng của Cây Merkle, chúng có thể được kết hợp và sửa đổi với các cấu trúc dữ liệu khác để đạt được các đặc điểm mới dựa trên các mục tiêu khác nhau. Để phục vụ cho các kịch bản truy vấn có thể xác minh khác nhau, Cây Merkle có thể được mở rộng thành các cấu trúc dữ liệu được lập chỉ mục khác nhau, chẳng hạn như Cây Merkle-B (MBT). Để thực hiện hiệu quả các hoạt động như chèn, xóa và truy vấn, nhóm Ethereum đã đề xuất Cây Merkle Patricia (MPT).

3.3.1. Cây Merkle-B

Cây Merkle-B (MBT) được sử dụng chủ yếu để xử lý các truy vấn phạm vi có thể xác minh. Hãy để 𝑓 là số lượng nút con cho mỗi nút của MBT (số lượng nút con cho mỗi nút). Dựa trên cấu trúc cây B+, mỗi nút nội của MBT, ngoài việc lưu trữ 𝑓 — 1 chỉ số và con trỏ tới 𝑓 nút con, cũng duy trì các giá trị băm của tất cả các nút con của mình dưới dạng tóm tắt. Dưới đây là biểu diễn của cấu trúc các nút lá và nút nội trong một MBT.

Khi cần chứng minh rằng dữ liệu trả về từ truy vấn phạm vi cụ thể tuân thủ phạm vi đã chỉ định, máy chủ tính Toán Đối tượng Xác minh (VO) phải thực hiện trước hai hoạt động tìm kiếm từ trên xuống để tìm ra các ranh giới bên trái và bên phải. Nó cũng phải trả về tất cả dữ liệu trong phạm vi này cũng như các băm của tất cả các nhánh cần thiết để xây dựng đường dẫn đến băm gốc.

Một hạn chế của cấu trúc dữ liệu này là VO được trả về chỉ có thể chứng minh rằng kết quả truy vấn nằm trong phạm vi truy vấn yêu cầu, nhưng không thể chứng minh rằng kết quả trả về là hoàn toàn đầy đủ.

3.3.2. Cây Merkle Patricia

Nếu một cây Merkle ngây thơ được sử dụng để cung cấp các truy vấn có thể xác minh, quá trình tốn thời gian để tạo lại gốc cây Merkle sau mỗi lần chèn hoặc xóa dữ liệu có thể trở nên đáng kể. Ngoài ra, nó đòi hỏi việc duy trì các cây tìm kiếm dữ liệu bổ sung cho việc lưu trữ. Cây Merkle Patricia (MPT) kết hợp các đặc tính của một Cây Radix (cây tiền tố gọn gàng) và một Cây Merkle, cho phép nó thực hiện việc chèn, xóa và truy vấn trong thời gian O(log(N)). Để hiểu rõ về MPT, độc giả có thể tham khảo các bài viết kỹ thuật chi tiết về chủ đề. Bài viết này chỉ giới thiệu một số định nghĩa cơ bản và cung cấp ví dụ để giúp độc giả hiểu về MPT một cách nhanh chóng.

Cấu trúc cơ bản của Ethereum sử dụng cơ sở dữ liệu khóa-giá trị để lưu trữ, có nghĩa dữ liệu được lưu trữ dưới dạng cặp khóa-giá trị. MPT cũng được phân rã thành các cặp khóa-giá trị để lưu trữ. Chúng ta xác định cấu trúc logic của các nút MPT như sau:

• chỉ số
• đường
• dữ liệu

Trong ngữ cảnh của Cây Merkle Patricia (MPT), “index” đề cập đến khóa của cặp khóa-giá trị, trong khi “path” kết hợp với “data” tạo thành giá trị của cặp khóa-giá trị. Chính xác, index lưu trữ băm của nút cây Merkle, và path tương ứng với chuỗi đường dẫn được sử dụng trong cây tiền tố để tìm nút mục tiêu. Ethereum sử dụng chuỗi thập lục phân dưới dạng chuỗi đường dẫn, và do đó chiều rộng của MPT là 16. Dữ liệu là dữ liệu mục tiêu tương ứng với đường dẫn.

Dưới đây là một ví dụ về MPT đã được tối ưu hóa với các tiền tố nén, lưu trữ dữ liệu cặp khóa-giá trị sau:

{

‘cab8’: ‘chó’,

'cabe': 'cat',

‘39’: ‘chicken’,

'395': 'vịt',

‘56f0’: ‘horse’

}

Để tìm dữ liệu “duck” bằng đường dẫn “395,” bạn sẽ bắt đầu tại root hash và tiến qua hashA, hashC, và hashD để cuối cùng đến được dữ liệu cần tìm. Dưới đây là hướng dẫn từng bước:

1. Root Hash: Đây là điểm nhập của cây Merkle Patricia (MPT), và bạn sẽ sử dụng nó để tìm nút đầu tiên.
2. hashA: Dựa vào root hash, bạn sẽ lấy lại nút hoặc nội dung được xác định bởi hashA. Vì đường dẫn là “395,” bạn đang tìm phần của cây sẽ dẫn bạn đến “3”.
3. hashC: Sau khi truy cập nội dung của hashA, bạn tiếp tục theo đường dẫn. Đoạn tiếp theo, “9”, đưa bạn đến hashC.
4. hashD: Cuối cùng, tiếp tục đi xuống con đường, đoạn cuối cùng “5” đưa bạn đến hashD, chứa giá trị “duck”.

Tại mỗi bước trên con đường, MPT tận dụng các đặc tính của cả Cây Radix, để tìm đường đúng dựa trên khóa, và Cây Merkle, để đảm bảo tính toàn vẹn của dữ liệu thông qua liên kết băm. Các “đường dẫn” trong cây thường được đại diện bằng mã hóa thập lục phân, tương ứng với hệ số phân nhánh của cây là 16. Mỗi nút trong đường dẫn bao gồm đủ con trỏ băm (tới các nút con) và giá trị để xác minh tính toàn vẹn của dữ liệu và điều hướng qua cây.

Vui lòng lưu ý rằng trong một MPT thực tế, các đường dẫn và dữ liệu sẽ được mã hóa và lưu trữ theo một định dạng cụ thể, và các loại nút bổ sung (như các nút mở rộng và nút lá) giúp tối ưu hóa cấu trúc để hiệu quả trong các tình huống khác nhau.

4. Vector Commitment

Các kế hoạch cam kết[1] là các nguyên tắc mật mã đảm bảo sự riêng tư và tính toàn vẹn dữ liệu. Chúng được sử dụng rộng rãi trong các kịch bản như chứng minh không biết và tính toán đa bên an toàn. Một kế hoạch cam kết cơ bản được chia thành hai giai đoạn: giai đoạn cam kết và giai đoạn tiết lộ (hoặc mở).

1. Pha Cam kết: Trong giai đoạn này, người cam kết sử dụng một thuật toán mật mã để liên kết một thông điệp với một giá trị cam kết và gửi giá trị cam kết này cho người nhận. Ở giai đoạn này, cam kết có hai tính chất: ẩn và ràng buộc. Tính chất ẩn đảm bảo rằng nội dung của thông điệp cam kết không được biết đến bởi ai ngoại trừ người cam kết. Tính chất ràng buộc đảm bảo rằng một khi đã có cam kết, nó không thể bị thay đổi bởi bất kỳ ai, kể cả người cam kết.
2. Pha Tiết lộ (Mở): Trong giai đoạn này, người cam kết có thể chứng minh cho người nhận rằng giá trị cam kết họ nhận được là một cam kết hợp lệ đối với thông điệp gốc. Cam kết có tính chính xác, có nghĩa là nếu cả người cam kết và người nhận đều tuân theo giao thức đúng cách, người nhận sẽ tin tưởng rằng giá trị cam kết họ nhận được trong giai đoạn cam kết là một cam kết hợp lệ đối với thông điệp gốc.

Vector Commitment là một loại hình cam kết đặc biệt được đề xuất bởi Catalano et al. [2] cho phép người cam kết thực hiện cam kết đối với một tập hợp được sắp xếp các tin nhắn 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ và để tiết lộ (mở) tại bất kỳ vị trí cụ thể nào để chứng minh rằng tin nhắn 𝑚𝑖 là tin nhắn được cam kết thứ i. Trong cam kết vector, việc ràng buộc có nghĩa là không ai có thể mở cùng một vị trí để tiết lộ các tin nhắn khác nhau.

Một hệ thống cam kết vector thông thường bao gồm các thuật toán sau:

5. Cây Verkle

5.1. Định nghĩa và Đặc điểm của Cây Verkle

Định nghĩa: Cây Verkle = Cam kết Vector + Cây Merkle。

Lưu ý: Vitalik Buterin, người đồng sáng lập Ethereum, đã blogbài đăng đặc biệt dành riêng cho việc giới thiệu cây Verkle. Chương này bổ sung một số kiến ​​thức nền và toán học dựa trên blog của anh ấy. Một số dữ liệu và minh họa trong văn bản tiếp theo được dẫn xuất từ blog của anh ấy.

Cây Verkle (VTs) được đặc trưng bởi việc cung cấp bằng chứng nhỏ hơn so với Merkle Trees. Đối với dữ liệu ở quy mô hàng tỷ bản ghi, một cây Merkle có thể tạo ra bằng chứng khoảng 1KB, trong khi bằng chứng cây Verkle có thể nhỏ hơn 150 byte. Kích thước bằng chứng gọn nhẹ này có lợi thế cho việc triển khaikhách hàng không trạng thái

Cấu trúc của một cây Verkle khá tương tự như cây Merkle Patricia Tree (MPT). Dưới đây là một ví dụ về cấu trúc của nó. Các nút của một cây Verkle có thể là: (i) Rỗng, (ii) Nút lá chứa một khóa và giá trị tương ứng của nó, hoặc (iii) Nút nội bộ với một số lượng cố định các nút con. Số lượng nút con này cũng được gọi là “độ rộng” của cây.

Sự khác biệt giữa VT (Cây Verkle) và MPT (Cây Merkle Patricia) chủ yếu nằm ở cách mà chiều rộng của cây (hoặc fan-out, đề cập đến số lượng nút con mà một nút trong cây có) ảnh hưởng đến hiệu suất của chúng. Trong trường hợp của MPT, nếu chiều rộng lớn hơn, nó có tend to be less efficient vì chiều rộng lớn hơn có nghĩa là có nhiều nút anh em hơn, điều này có thể dẫn đến thời gian cập nhật lâu hơn cho MPT và kích thước chứng minh lớn hơn. Ngược lại, với VT, một chiều rộng cây rộng hơn dẫn đến chứng minh nhỏ hơn. Hạn chế duy nhất là nếu chiều rộng quá cao, thời gian để tạo ra chứng minh có thể trở nên lâu hơn.

Trong Ethereum’s@vbuterin/verkle_tree_eip">Các đề xuất thiết kế cho VTs, đề xuất một độ rộng của 256, đây là một con số đáng kể lớn hơn so với 16 hiện tại của MPT. Một độ rộng lớn như vậy là khả thi trong VTs vì việc sử dụng các kỹ thuật mật mã tiên tiến, như cam kết vector, cho phép chứng minh gọn nhẹ bất kể độ rộng của cây. Kỹ thuật nén này cho phép cây Verkle mở rộng hiệu quả hơn về kích thước chứng minh. Văn bản tiếp theo sẽ giải thích chi tiết các tính năng được đề cập ở trên.

5.2. Cam kết và Chứng minh của Cây Verkle

Hãy xem cách chứng minh được tạo ra trong một MPT: Chứng minh cần bao gồm các giá trị hash của tất cả các nút bên (hoặc các nút chị em) trên đường đi từ nút gốc đến nút lá mục tiêu. Lấy “4ce” làm ví dụ, các phần được đánh dấu màu đỏ trong sơ đồ dưới đây là các nút cần phải được bao gồm trong chứng minh được trả về.

Trong cây Verkle, bạn không cần cung cấp các nút anh em; thay vào đó, bạn chỉ cần cung cấp đường dẫn cùng với một số dữ liệu bổ sung như bằng chứng.

Vậy làm thế nào để tạo cam kết cho một VT? Hàm băm được sử dụng cho việc tính toán không phải là hàm băm thông thường mà sử dụng cam kết vector.

Sau khi thay thế hàm băm bằng một thuật toán tạo cam kết từ cam kết vector, hash gốc được gọi là cam kết gốc. Nếu dữ liệu của bất kỳ nút nào bị can thiệp, cuối cùng sẽ ảnh hưởng đến cam kết gốc.

Làm thế nào để tạo ra một bằng chứng? Như thể hiện trong sơ đồ dưới đây, bạn chỉ cần cung cấp ba bằng chứng phụ, mỗi bằng chứng có thể chứng minh rằng một nút trên đường đi tồn tại ở một vị trí cụ thể trong nút cha của nó. Càng rộng, càng ít lớp, và do đó, càng ít bằng chứng phụ được yêu cầu.

Trong thực tế, các cam kết đa thức được sử dụng (có thể được triển khai một cách đơn giản và hiệu quả cho các cam kết vector), cho phép cam kết đến một đa thức. Hai hệ thống cam kết đa thức thân thiện với người dùng nhất là “Cam kết KZG” và “cam kết đa thức theo kiểu bảo mật chắc chắn (cái trước có kích thước cam kết là 48 byte, trong khi cái sau là 32 byte).

Nếu bạn sử dụng cam kết và bằng chứng KZG, bằng chứng cho mỗi nút trung gian chỉ là 96 byte, đại diện cho việc tiết kiệm không gian gần ba lần so với cây Merkle cơ bản (giả sử chiều rộng là 256).

Độ phức tạp thời gian lý thuyết cho các hoạt động trên cây Merkle và cây Verkle như sau:

Hệ thống chứng minh Verkle được giới thiệu cho đến nay khá cơ bản; thực tế, còn có các chiến lược tối ưu tiên tiến khác sẵn có.

5.3. Tối ưu hóa: Hợp nhất các chứng minh

5.3.1. ý tưởng

So với việc tạo ra một bằng chứng cho mỗi lớp cam kết trên một đường đi, đặc điểm của các cam kết đa thức có thể được sử dụng để đạt được “chứng minh mối quan hệ cha-con giữa tất cả các cam kết trên đường đi với một bằng chứng có kích thước cố định, có thể bao gồm một số lượng không giới hạn các yếu tố.” Để hiểu cụ thể cách thức này được thực hiện, cần phải giới thiệu một số kiến thức toán học để giải thích. Bài viết này sẽ liên quan đến một số công thức toán học nhưng không bao gồm phần mật mã học của bằng chứng theo nguyên lý. Đối với phương pháp cụ thể, vui lòng tham khảo chương trình thực thi đa bằng cách đánh giá ngẫu nhiên.

5.3.2. Phép suy luận toán học

Đầu tiên, hãy giới thiệu một số khái niệm cơ bản về đa thức trong toán học: làm thế nào chúng ta thực hiện việc giảm đa thức, còn được biết đến là giảm bậc của một đa thức?

Giả sử chúng ta biết một đa thức 𝑃(𝑥) và giá trị 𝑦₁ tại 𝑥₁, tức là 𝑃(𝑥₁) = 𝑦₁.

Bây giờ, hãy xem xét một đa thức mới 𝑃(𝑥) - 𝑦₁, có giá trị bằng không tại (𝑥 = 𝑥₁), vì 𝑃(𝑥₁) - 𝑦₁ = 𝑦₁ - 𝑦₁ = 0.

Do đó, Đa thức 𝑃(𝑥) - 𝑦₁ có một nghiệm tại 𝑥 = 𝑥₁, điều đó có nghĩa là (𝑥 - 𝑥₁) là một thừa số của 𝑃(𝑥) - 𝑦₁.

Nói cách khác, chúng ta có thể diễn tả nó dưới dạng sau: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) là một đa thức khác có bậc nhỏ hơn một đơn vị so với 𝑃(𝑥). Điều này là vì (𝑥 -𝑥₁ ) là một yếu tố bậc một, làm giảm tổng bậc của đa thức.

Làm thế nào để sử dụng KZG để chứng minh một giá trị duy nhất trong một vector?

Ví dụ về cam kết KZG10, đối với đa thức 𝑃(𝑥), giả sử cam kết đa thức của nó là [ 𝑃(𝑠) ]₁.

Như đã giải thích trước đó, đối với đa thức 𝑃(𝑥), nếu 𝑃(𝑧) = 𝑦, thì chúng ta có 𝑄(𝑥) = (𝑃(𝑥) - 𝑦)/(𝑥 - 𝑧)

Bây giờ, bên chứng minh có thể tạo ra một bằng chứng rằng đa thức 𝑃(𝑥) thỏa mãn 𝑃(𝑧) = 𝑦 : tính toán [ 𝑄(𝑠) ]₁ và gửi nó cho bên xác minh.

Người xác minh cần xác minh 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .

Làm thế nào để sử dụng KZG để chứng minh nhiều giá trị trong một vector?

Chúng tôi có thể xây dựng một bằng chứng để chứng minh nhiều giá trị trong một vector như sau:

Bằng cách sử dụng phương pháp này, bất kể số lượng điểm dữ liệu trong cùng một vector cần được xác minh, chỉ cần một bằng chứng có kích thước cố định.

Bây giờ hãy xem xét kế hoạch cây Verkle mà không tối ưu hóa từ quan điểm của thuật toán cam kết KZG.

Sử dụng phương pháp xây dựng từ phần “Cách sử dụng KZG để chứng minh một giá trị duy nhất trong một vector,” người xác thực có thể xây dựng cam kết cho các đa thức gốc và thương của mỗi đa thức 𝑓ᵢ(𝑥) , dẫn đến tổng cộng 𝟐﹡𝑚 cam kết KZG. Người xác thực gửi tất cả các cam kết này như là bằng chứng cho việc xác minh.

Tuy nhiên, như đã đề cập trước đó, phương pháp này yêu cầu tạo ra nhiều bằng chứng, và người xác minh cũng cần thực hiện nhiều tính toán xác minh. Chúng ta cần tìm cách nén nhiều bằng chứng cam kết.

Kết hợp các bằng chứng

Người chứng minh gửi bằng chứng [ 𝑞( 𝑠 )]₁ cho người xác minh để xác minh.

Bằng chứng được tạo ra bởi kế hoạch này bao gồm một cam kết, hai bằng chứng và một giá trị, với kích thước dữ liệu không đổi. Cuối cùng, sau quá trình tối ưu hóa hợp nhất chứng minh trong cây Verkle, đối tượng dữ liệu có thể xác minh được gửi đến bên xác minh bao gồm các phần sau:

1. Bằng chứng kích thước không đổi
2. Dữ liệu của các lá cần được chứng minh (cặp key-value)
3. Các giá trị cam kết của tất cả các nút trên đường đi từ lá đến gốc (giả sử chiều rộng của cây là 256 với 2³² nút, sau đó độ sâu trung bình là 4, chỉ cần 3 giá trị cam kết)

Lưu ý rằng 𝑥ᵢ và 𝑦ᵢ không cần phải được cung cấp một cách rõ ràng; chúng có thể được tính toán tất cả.

5.3.3. hiệu suất

Về kế hoạch gộp chứng minh cho cây Verkle, kích thước cụ thể của chứng minh được tạo ra như sau（Đơn vị của hàng là tỷ.）:

Dữ liệu trên giả định việc sử dụng một cây có chiều rộng 256, sử dụng hệ thống cam kết KZG (với kích thước cam kết là 48 byte), và tối đa hóa việc sử dụng của cây. Trong thực tế, đối với phân phối thông tin hoàn toàn ngẫu nhiên, độ sâu của cây sẽ tăng khoảng 60%, và kích thước của mỗi phần tử sẽ tăng thêm 30 byte. Nếu sử dụng hệ thống bulletproof, thì kích thước cam kết sẽ là 32 byte.

5.4. Tải Trọng Tính Toán Của Bên Chứng Minh Và Bên Xác Minh

1. Tạo chứng minh: Chi phí tạo ra chứng minh bởi người chứng minh liên quan đến chiều rộng của cây, nhưng mỗi hoạt động nguyên tử đòi hỏi chi phí tính toán tương đối thấp, vì vậy cây Verkle với chiều rộng từ 256 đến 1024 hoạt động tốt về mặt thuật toán.
2. Xác minh Chứng cứ: Vitalik đã chỉ ra rằng thuật toán xác minh rất nhanh và thường có thể hoàn thành trong vòng 100ms, ngay cả khi có hàng nghìn giá trị cần xác minh.
3. Khi cập nhật cây Verkle: Việc cập nhật cây đòi hỏi việc tính toán lại tất cả các giá trị cam kết trung gian trên con đường do thay đổi giá trị hoặc cấu trúc. Tuy nhiên, Vitalik đã đề cập rằng, nhờ một số tính chất của thuật toán cam kết đa thức, có thể thiết kế một phương pháp để tính toán trước các giá trị cam kết thay thế và lưu trữ chúng, từ đó giảm thiểu chi phí thời gian tính toán trong quá trình cập nhật, điều này về cơ bản là trao đổi không gian lưu trữ để tiết kiệm thời gian.

6. Kết luận

Dưới đây là những từ nguyên bản trong blog của Vitalik, chúng tôi đã thêm một đoạn ở cuối như một bổ sung.

Cây Verkle là một bản nâng cấp mạnh mẽ cho chứng minh Merkle cho phép kích thước chứng minh nhỏ hơn nhiều. Thay vì cần cung cấp tất cả các “nút chị em” ở mỗi cấp độ, người chứng minh chỉ cần cung cấp một chứng minh duy nhất chứng minh tất cả các mối quan hệ cha con giữa tất cả các cam kết dọc theo các đường dẫn từ mỗi nút lá đến gốc. Điều này cho phép kích thước chứng minh giảm đi một cách đáng kể so với cây Merkle lý tưởng, và giảm đi một cách đáng kể hơn so với cây Patricia hexary mà Ethereum sử dụng ngày nay (!!).

Họ yêu cầu việc mật mã phức tạp hơn để triển khai, nhưng chúng cung cấp cơ hội cho sự tăng cường về khả năng mở rộng. Trong trung hạn, SNARKs có thể cải thiện thêm: chúng ta có thể sử dụng SNARK cho bộ chứng minh Verkle hiệu quả từ trước để giảm kích thước bằng chứng gần như về không, hoặc chuyển sang các chứng minh Merkle đã được SNARK nếu/khi SNARKs trở nên tốt hơn nhiều (ví dụ thông qua GKR, hoặc các hàm băm rất thân thiện với SNARK, hoặc ASIC). Xuống đường, sự phát triển của máy tính lượng tử sẽ buộc chúng ta phải chuyển sang chứng minh Merkle STARKed với các hàm băm khiến cho các đồng cơ tuyến tính mà cây Verkle phụ thuộc trở nên không an toàn. Nhưng hiện tại, chúng cung cấp cho chúng ta những lợi ích về khả năng mở rộng giống như chúng ta sẽ nhận được với các công nghệ tiên tiến hơn, và chúng ta đã có tất cả các công cụ mà chúng ta cần để triển khai chúng một cách hiệu quả.

Hiện nay, nhiều khách hàng Ethereum đã cung cấp việc triển khai cây Verkle và các mạng thử nghiệm liên quan. Cộng đồng vẫn đang thảo luận về thời điểm cây Verkle sẽ được triển khai trên mạng chính. Có khả năng sẽ được triển khai trong một bản nâng cấp hard fork vào năm 2024 hoặc 2025. Để biết thông tin chi tiết về cây Verkle trên Ethereum, vui lòng xem https://verkle.info/ .

7. Tham khảo

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Chứng minh tối thiểu về kiến thức[J]. Tạp chí khoa học máy tính và hệ thống, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. Vector commitments and their applications[C]//Public-KeyCryptography–PKC 2013: 16th International Conference on Practice and Theory in Public- Key Cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings 16. Springer, 2013: 55–72.

Tuyên bố:

1. Bài viết này được in lại từ [ZAN], Tất cả bản quyền thuộc về tác giả gốc [AntChain Open Labs và ZAN]. Nếu có ý kiến ​​phản đối về việc tái in này, vui lòng liên hệ với Cổng Họcđội của họ sẽ xử lý ngay lập tức.
2. Chú Ý Trách Nhiệm: Các quan điểm và ý kiến được thể hiện trong bài viết này chỉ là của tác giả và không đại diện cho bất kỳ lời khuyên đầu tư nào.
3. Các bản dịch của bài viết sang các ngôn ngữ khác được thực hiện bởi nhóm Gate Learn. Trừ khi được nêu, việc sao chép, phân phối hoặc việc đạo văn các bài viết dịch là cấm.