Cây Verkle là một sơ đồ cam kết hoạt động tương tự như cây Merkle, nhưng có các nhân chứng nhỏ hơn nhiều. Nó hoạt động bằng cách thay thế các hàm băm trong cây Merkle bằng một cam kết vectơ, điều này làm cho các yếu tố phân nhánh rộng hơn hiệu quả hơn.
Cảm ơn Kev vàng da Wedderburn đã phản hồi về bài đăng.
Để biết chi tiết về cách hoạt động của cây verkle, hãy xem:
Mục đích của bài đăng này là giải thích bố cục cụ thể của EIP cây verkle dự thảo. Nó nhắm đến các nhà phát triển khách hàng muốn triển khai cây verkle và đang tìm kiếm phần giới thiệu trước khi nghiên cứu sâu hơn về EIP.
Cây Verkle giới thiệu một số thay đổi đối với cấu trúc cây. Những thay đổi đáng kể nhất là:
Là sơ đồ cam kết vectơ cho cây verkle, chúng tôi sử dụng Cam kết dành cho người đi bộ . Các cam kết về Pedersen dựa trên các đường cong elip. Để được giới thiệu về các cam kết Pedersen và cách sử dụng chúng như các cam kết đa thức hoặc vectơ bằng cách sử dụng Đối số sản phẩm bên trong, hãy xem tại đây.
Đường cong chúng tôi đang sử dụng là Bandersnatch. Đường cong này được chọn vì nó có hiệu suất và cũng vì nó sẽ cho phép SNARK hiệu quả trong BLS12_381 suy luận về cây verkle trong tương lai. Điều này có thể hữu ích cho việc tổng hợp cũng như cho phép nâng cấp trong đó tất cả các nhân chứng có thể được nén vào một SNARK khi điều đó trở nên thực tế, mà không cần cập nhật cam kết thêm.
Thứ tự đường cong / kích thước trường vô hướng của bandersnatch là p =13108968793781547619861935127046491459309155893440570251786403306729687672801 , là một số nguyên tố 253 bit. Do đó, chúng tôi chỉ có thể cam kết một cách an toàn với các chuỗi bit có tối đa 252 bit, nếu không trường sẽ bị tràn. Chúng tôi đã chọn hệ số phân nhánh (chiều rộng) là 256 cho cây verkle, có nghĩa là mỗi cam kết có thể cam kết tối đa 256 giá trị, mỗi giá trị 252 bit (hoặc chính xác là số nguyên lên đến p - 1 ). Chúng tôi viết điều này là Cam kết (v₀, v₁,…, v₂₅₅) cam on danh v có chiều dài 256.
Một trong những mục tiêu thiết kế với EIP cây verkle là làm cho việc truy cập vào các vị trí lân cận (ví dụ:lưu trữ với địa chỉ gần như giống nhau hoặc các đoạn mã lân cận) rẻ để truy cập. Để thực hiện việc này, khóa bao gồm một gốc 31 byte và một hậu tố của một byte với tổng số 32 byte. Lược đồ khóa được thiết kế để các vị trí lưu trữ "đóng" được ánh xạ tới cùng một gốc và một hậu tố khác. Để biết chi tiết, vui lòng xem bản thảo EIP.
Bản thân cây verkle sau đó bao gồm hai loại nút:
Cam kết cho một nút mở rộng là một cam kết cho một vectơ 4 phần tử; các vị trí còn lại sẽ là 0. Đó là:
C₁ và C₂ là hai cam kết khác cam kết tất cả các giá trị với gốc bằng gốc . Lý do chúng ta cần cam kết là các giá trị có 32 byte, nhưng chúng ta chỉ có thể lưu trữ 252 bit cho mỗi phần tử trường. Do đó, một cam kết duy nhất sẽ không đủ để lưu trữ 256 giá trị. Vì vậy, thay vào đó, C₁ lưu trữ các giá trị cho hậu tố 0 đến 127 và C₂ lưu trữ 128 đến 255, trong đó các giá trị được chia làm hai để vừa với kích thước trường (chúng ta sẽ nói đến điều đó sau.)
Việc mở rộng cùng với các cam kết C₁ và C₂ được gọi là “cây mở rộng và hậu tố” (viết tắt là EaS).
Hình 1 Biểu diễn bước đi qua cây verkle cho khóa 0xfe0002abcd..ff04 :đường dẫn đi qua 3 nút bên trong với 256 nút con mỗi nút (254, 0, 2), một nút mở rộng đại diện cho abcd..ff và hai cam kết cây hậu tố, bao gồm giá trị cho 04 , v₄. Lưu ý rằng stem thực sự là 31 byte đầu tiên của khóa, bao gồm cả đường dẫn qua các nút bên trong.
Mỗi nút cây hậu tố và phần mở rộng chứa 256 giá trị. Bởi vì một giá trị rộng 256 bit và chúng tôi chỉ có thể lưu trữ 252 bit một cách an toàn trong một phần tử trường, nên bốn bit sẽ bị mất nếu chúng tôi chỉ cố gắng lưu trữ một giá trị trong một phần tử trường.
Để giải quyết vấn đề này, chúng tôi đã chọn phân vùng nhóm 256 giá trị thành hai nhóm 128 giá trị mỗi nhóm. Mỗi giá trị 32 byte trong một nhóm được chia thành hai giá trị 16 byte. Vì vậy, một giá trị vᵢ∈ 𝔹₃₂ được biến thành v⁽ˡᵒʷᵉʳ⁾ᵢ ∈ 𝔹₁₆ và v⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ 𝔹₁₆ sao cho v⁽ˡᵒʷᵉʳ⁾ᵢ ++ v⁽ᵘᵖᵖᵉʳ⁾ᵢ =vᵢ.
Một “điểm đánh dấu lá” được thêm vào v⁽ˡᵒʷᵉʳ⁾ᵢ, để phân biệt giữa lá chưa bao giờ được truy cập và lá đã bị ghi đè bằng các số 0. Không có giá trị nào bị xóa khỏi cây verkle . Điều này là cần thiết cho các kế hoạch sắp hết hạn của tiểu bang. Điểm đánh dấu đó được đặt ở bit thứ 129, tức là v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ =v⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸ nếu vᵢ đã được truy cập trước đó và v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ =0 nếu vᵢ chưa từng được truy cập.
Hai cam kết C₁ và C₂ sau đó được định nghĩa là
Cam kết cho một nút mở rộng bao gồm một "điểm đánh dấu mở rộng", chỉ là số 1, hai cam kết cây con C₁ và C₂ và gốc của khóa dẫn đến nút tiện ích mở rộng này.
Không giống như các nút mở rộng trong cây Merkle-Patricia, chỉ chứa phần của khóa làm cầu nối nút bên trong cha với nút bên trong con, phần thân bao gồm toàn bộ khóa cho đến thời điểm đó. Điều này là do cây verkle được thiết kế với các bằng chứng không trạng thái:nếu một khóa mới được chèn vào để "tách" phần mở rộng ra làm hai, phần mở rộng cũ hơn không cần được cập nhật, điều này cho phép một bằng chứng nhỏ hơn.
Các nút bên trong có phương pháp tính toán đơn giản hơn cho các cam kết của chúng:nút được xem như một vectơ gồm 256 giá trị, là (đại diện trường của) cam kết gốc của mỗi cây trong số 256 cây con của chúng. Cam kết cho một cây con trống là 0. Nếu cây con không trống, thì cam kết cho nút bên trong là
trong đó Cᵢ là nút con của nút bên trong và 0 nếu nút con trống.
Hình 2 là một minh họa về quá trình chèn một giá trị mới vào cây, điều này trở nên thú vị khi các thân cây va chạm vào nhau trên một số byte ban đầu.
Hình 2 Giá trị v₁₉₂ được chèn tại vị trí 0000010000 ... 0000 trong cây verkle chỉ chứa giá trị v₁₂₇ tại vị trí 0000000000 ... 0000 . Bởi vì các nhánh khác nhau ở byte thứ ba, hai nút bên trong được thêm vào cho đến khi byte khác nhau. Sau đó, một cây “phần mở rộng và hậu tố” khác được chèn vào, với gốc đầy đủ 31 byte. Nút ban đầu không bị ảnh hưởng và C²₀ có cùng giá trị với C⁰₀ trước khi chèn.
Cấu trúc cây verkle làm cho cây nông hơn, làm giảm lượng dữ liệu được lưu trữ. Tuy nhiên, sức mạnh thực sự của nó đến từ khả năng tạo ra các bằng chứng nhỏ hơn, tức là nhân chứng. Điều này sẽ được giải thích trong bài viết tiếp theo.