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 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.
Tổng quan
Để biết chi tiết về cách cây verkle hoạt động, 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 dự thảo cây verkle EIP. 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à:
- chuyển đổi từ khóa 20 byte sang khóa 32 byte (không nên nhầm lẫn với địa chỉ 32 byte, đây là một thay đổi riêng biệt);
- sự hợp nhất của tài khoản và bộ nhớ cố gắng; và cuối cùng
- Sự ra đời của bản thân bộ trie verkle, sử dụng các cam kết vectơ thay vì các hàm băm.
Là lược đồ cam kết vectơ cho cây verkle, chúng tôi sử dụng Đẩy mạnh cam kết. 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 nơ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 = 13108968793781547619861935127046491459309155893440570251786403306729687672801là một số nguyên tố 253 bit. Do đó, chúng tôi chỉ có thể cam kết 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 lên đến 256 giá trị của mỗi giá trị 252 bit (hoặc nói chính xác là các số nguyên lên đến p – 1). Chúng tôi viết cái này là Cam kết (v₀, v₁, …, v₂₅₅) cam kết với danh sách v có chiều dài 256.
Bố cục của cây verkle
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 đến 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. Để làm điều này, một khóa bao gồm thân cây 31 byte và a 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 Dự thảo EIP.
Bản thân cây verkle sau đó bao gồm hai loại nút:
- Các nút mở rộngđại diện cho 256 giá trị có cùng gốc nhưng các hậu tố khác nhau
- Các nút bên trongcó tối đa 256 nút con, có thể là các nút bên trong khác hoặc các nút mở rộng.
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ị có gốc bằng thân cây. 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).
Phần 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 của việc đi bộ qua một cây verkle cho chìa 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 abcd..ff và hai cam kết cây hậu tố, bao gồm giá trị cho 04v₄. Lưu ý rằng thân cây 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.
Cam kết với các giá trị của các nút lá
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 ta chỉ có thể lưu trữ 252 bit một cách an toàn trong một phần tử trường, bốn bit sẽ bị mất nếu chúng ta 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 bao giờ được truy cập.
Hai cam kết C₁ và C₂ sau đó được định nghĩa là
Cam kết của các nút mở rộng
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à thân cây của khóa dẫn đến nút 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, thì 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.
Cam kết của các nút nội bộ
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.
Chèn vào cây
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 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 một 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ây bóng mát, bằng chứng nhỏ hơ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à các nhân chứng. Điều này sẽ được giải thích trong bài viết tiếp theo.
