Tóm tắt cập nhật Block : Bằng chứng thành viên không cần cây trạng thái toàn cầu
Tác giả: Cody Littley, Alejandro Ranchal-Pedrosa ( @alranpe ), Omar Garcia — Sei Labs
Tóm lại: BUD là một lược đồ chứng minh tư cách thành viên có khả năng mở rộng theo khối lượng giao dịch ghi trên mỗi khối chứ không phải kích thước trạng thái tổng thể, mà không yêu cầu cây trạng thái toàn cục trên đường dẫn quan trọng.
Động lực
Bằng chứng thành viên (hay còn gọi là bằng chứng trạng thái, như được cung cấp bởi eth_getProof ) cho phép các bên quan sát ngoài chuỗi xác minh mật mã các giá trị trên chuỗi mà không cần tin tưởng bên thứ ba. Phương pháp tiêu chuẩn xây dựng một cây trie Merkle trên toàn bộ trạng thái, sao cho chữ ký trên Hash gốc, cùng với đường dẫn Merkle, chứng minh sự bao gồm hoặc loại trừ bất kỳ khóa nào.
Chi phí của phương pháp này tỷ lệ thuận với kích thước trạng thái tổng thể: mỗi Block phải cập nhật một cây có các lá trải rộng trên hàng triệu tài khoản và vị trí lưu trữ. Đối với các chuỗi tương đương EVM có thông lượng cao, chi phí phát sinh trở thành một nút thắt cổ chai không thể chấp nhận được, cả về khả năng tính toán thô lẫn bố cục cơ sở dữ liệu mà nó buộc phải có. Ngay cả Ethereum L1 cũng mang lại sự phức tạp đáng kể và chi phí I/O từ việc duy trì cây trạng thái toàn cục.
Chúng tôi đề xuất Block Update Digests (BUDs) , một cấu trúc dữ liệu xác thực gia tăng giúp tách rời chi phí cam kết trạng thái khỏi tổng kích thước trạng thái, thay vào đó mở rộng quy mô dựa trên khối lượng giao dịch cập nhật trên mỗi khối. BUDs kết hợp với một lớp tóm tắt phân cấp mà chúng tôi gọi là SuperBUDs và với các giao dịch chạm theo yêu cầu để đáp ứng đầy đủ các yêu cầu về độ trễ, kích thước bằng chứng và chi phí.
Sự khác biệt giữa cây trạng thái nhị phân và cây Verkle
Lộ trình L1 của Ethereum đã hội tụ về cây trạng thái nhị phân (Đề xuất cải tiến Ethereum (EIP)-7864) như cơ chế cam kết trạng thái dài hạn, với lộ trình hướng tới xác minh SNARK O(1) O ( 1 ) của bằng chứng trạng thái. Đối với các chuỗi cam kết duy trì cấu trúc dữ liệu được xác thực toàn cầu trên đường dẫn quan trọng của sự đồng thuận, các đề xuất này thể hiện sự cải thiện rõ rệt so với MPT hiện tại. BUD giải quyết một câu hỏi hoàn toàn khác và mang tính bổ sung, chứ không phải cạnh tranh.
BUD giải quyết một câu hỏi kiến trúc khác: liệu cấu trúc dữ liệu được xác thực có nên nằm trên đường dẫn quan trọng của sự đồng thuận hay không?
Một cây trạng thái toàn cục, bất kể được triển khai hiệu quả đến mức nào (MPT, nhị phân, Verkle), đều yêu cầu mỗi trình xác thực phải duy trì và cập nhật cấu trúc dữ liệu dạng cây trie trong quá trình thực thi Block . Cây trie hạn chế bố cục cơ sở dữ liệu, gây ra sự khuếch đại I/O tỷ lệ thuận với độ sâu của cây trên mỗi lần ghi và làm rối loạn Xuất lượng lượng thực thi với chi phí cam kết trạng thái. Ngay cả một cây trie nhị phân hoàn hảo với O(\log n) O ( log n ) đường dẫn áp đặt O(w \cdot \log n) O ( w ⋅ log n ) các phép tính Hash trên mỗi Block cho w lần ghi trạng thái, và cơ sở dữ liệu phải lưu trữ các nút trung gian theo bố cục thân thiện với cây trie.
Các lập luận BUD cho rằng đối với môi trường thực thi thông lượng cao, cấu trúc trie là sự trừu tượng không phù hợp để đặt trên đường dẫn quan trọng của trình xác thực. Thay vào đó, các trình xác thực tạo ra một bản tóm tắt nhẹ cho mỗi khối (chi phí tỷ lệ thuận với tập hợp ghi, không phụ thuộc vào kích thước trạng thái tổng thể) và cơ sở hạ tầng bằng chứng đầy đủ được ủy thác cho các nút lưu trữ. Bản thân trạng thái có thể nằm trong bất kỳ bố cục lưu trữ khóa-giá trị phẳng nào tối ưu cho tốc độ thực thi thô, mà không có các ràng buộc I/O dạng trie.
Đây là một lựa chọn về kiến trúc, chứ không phải là một giải pháp tạm thời. Các chuỗi áp dụng BUD không phải là "đang chờ đợi để chuyển sang một cấu trúc trie tốt hơn"; mà là họ đang lựa chọn không duy trì cấu trúc trie toàn cục trên đường dẫn quan trọng.
Lưu ý rằng lập luận xác minh SNARK mang tính đối xứng: bằng chứng Merkle BUD cũng có thể được xác minh bằng SNARK, và mạch đơn giản hơn vì cây BUD nhỏ hơn (tỷ lệ thuận với tập hợp ghi Block , chứ không phải toàn bộ trạng thái). Nếu mục tiêu cuối cùng là các bằng chứng trạng thái được xác minh bằng SNARK cho Cầu nối liên mạng (Cross-Chain Bridges) và các máy khách nhẹ, cả hai phương pháp đều đạt được mục tiêu đó; vấn đề chỉ đơn thuần là chi phí mà các trình xác thực phải chịu trong quá trình tạo Block .
Ý tưởng cốt lõi
BUDs
BUD là một cây Merkle nhỏ được xây dựng dựa trên những thay đổi được tạo ra bởi một Block duy nhất (hoặc, nói chung hơn, bởi bất kỳ cửa sổ liền kề nào gồm k khối). Mỗi lá ghi lại:
- chìa khóa,
- giá trị mới của nó,
- số Block hiện tại và
- Số Block trước đó mà khóa được sửa đổi lần cuối.
Trường (4) là phần bổ sung quan trọng: nó Threads một chuỗi sửa đổi trên mỗi khóa qua chuỗi BUD, để hai mục BUD liền kề cho cùng một khóa có thể chứng thực rằng không có gì thay đổi ở giữa. Để hỗ trợ điều này, mỗi mục trong kho lưu trữ khóa-giá trị mang thêm 8 byte siêu dữ liệu ghi lại Block Height của lần sửa đổi cuối cùng của nó (cộng thêm 1 byte cho trường phiên bản tuần tự hóa).
Hình 1: Cấu trúc của cây Merkle BUD. Mỗi lá ghi lại (khóa, giá trị mới, số Block hiện tại, Block trước đó được sửa đổi). Hash BUD được ký bởi các trình xác thực với Stake tối thiểu > (n+f)/2.
Các trình xác thực ký băm BUD và tổng hợp chữ ký theo cách thông thường (đa số > (n+f)/2 > ( n + f ) / 2 Stake, trong đó tối đa f f là đối thủ). Sau đó, BUD được truyền đến các nút lưu trữ để lưu trữ dài hạn và phục vụ bằng chứng.
Vì cây chỉ được xây dựng trên các khóa được truy cập trong một Block, chi phí xây dựng của nó tỷ lệ thuận với tập hợp các thao tác ghi của khối đó, chứ không phải với kích thước trạng thái toàn cục. Một Block sửa đổi 10.000 khóa sẽ xây dựng một cây trên 10.000 lá bất kể trạng thái tổng thể có chứa 100 triệu mục hay không.
SuperBUDs
Một BUD duy nhất chứng minh giá trị của khóa tại Block nơi nó được sửa đổi, nhưng một máy khách nhẹ truy vấn giá trị hiện tại của một khóa được ghi lần cuối cách đây d khối sẽ cần phải kiểm tra d khối BUD để loại trừ một cách đơn giản. SuperBUD nén quá trình quét tuyến tính này thành một quá trình quét logarit.
Một SuperBUD cấp độ \ell ℓ trải rộng e^\ell e ℓ khối (với cơ sở có thể cấu hình e e ; chúng ta sử dụng e = 2 e = 2 làm ví dụ cụ thể) và được tạo ra ở độ cao Block là bội số của e^\ell e ℓ . Bên trong, một SuperBUD là một cây trie Merkle ánh xạ mỗi khóa được chạm vào trong phạm vi của nó đến số Block gần nhất mà nó được sửa đổi. Hai SuperBUD liền kề ở cùng cấp độ có thể được hợp nhất thành một SuperBUD duy nhất ở cấp độ tiếp theo bằng cách lấy hợp của các tập hợp khóa của chúng và, đối với các khóa xuất hiện trong cả hai, chỉ giữ lại số Block gần đây hơn. Việc hợp nhất này là một phép duyệt phối hợp O( n ) duy nhất của hai cây trie đã được sắp xếp.
Bằng chứng SuperBUD cho một khóa nhất định cho thấy hoặc (a) Block cao nhất trong khoảng thời gian mà khóa đã được sửa đổi, hoặc (b) khóa không được sửa đổi trong khoảng thời gian đó. Kết hợp với bằng chứng BUD tại Block được xác định, điều này tạo ra bằng chứng thành viên đầy đủ.
Hình 2: Hệ thống phân cấp SuperBUD trên các khối B0–B11 với cơ sở e=2 e = 2 . SuperBUD cấp 1 trải rộng trên 2 khối, cấp 2 trải rộng trên 4 khối, cấp 3 trải rộng trên 8 khối. Các SuperBUD liền kề ở cùng cấp độ hợp nhất thành cấp độ tiếp theo thông qua một lần duyệt O(n) O ( n ) .
Độ trễ và kích thước bằng chứng. Nếu lần sửa đổi cuối cùng là d khối trước đó, máy khách cần một SuperBUD ở cấp độ \lceil \log_e d \rceil ⌈ log e d ⌉ . Trong trường hợp xấu nhất, khách hàng phải chờ tới e^{\lceil \log_e d \rceil} e ⌈ log e d ⌉ khối chờ cửa sổ được căn chỉnh tiếp theo ở cấp độ đó đóng lại. Do đó, thời gian chờ đợi trong trường hợp xấu nhất là tuyến tính theo độ lỗi thời, nhưng điều mà hệ thống phân cấp mang lại là tính gọn nhẹ của bằng chứng : một số lượng tra cứu tóm tắt theo logarit và một số lượng đường dẫn Merkle không đổi, thay vì một chuỗi tính các bằng chứng loại trừ trên mỗi khối.
Giao dịch chạm
Trong khi SuperBUDs đánh đổi độ trễ để có được bằng chứng gọn nhẹ mà không tốn chi phí on-chain , các giao dịch chạm lại đưa ra sự đánh đổi ngược lại: trả một khoản phí nhỏ on-chain để nhận được bằng chứng BUD ngay lập tức tại Block hiện tại, bất kể khóa đó đã cũ đến mức nào.
Giao dịch chạm không sửa đổi giá trị của khóa; nó chỉ cập nhật siêu dữ liệu "lần sửa đổi cuối cùng" và tạo một mục nhập trong BUD của khối hiện tại. Điều này tương tự như lệnh touch trong shell Unix: làm mới dấu thời gian mà không thay đổi nội dung. Giao dịch chạm được tính phí theo cơ chế đo lường tài nguyên hiện có của chuỗi (mỗi đơn vị truy cập trạng thái và ghi siêu dữ liệu), vì vậy chúng không tạo ra bề mặt tấn công DoS mới nào ngoài những gì biểu phí đã tính đến.
Cả SuperBUDs và giao dịch cảm ứng đều bao trùm toàn bộ không gian thiết kế độ trễ/chi phí: người dùng nhạy cảm với chi phí sẽ chờ SuperBUDs; người dùng nhạy cảm với độ trễ sẽ sử dụng giao dịch cảm ứng.
Chiến lược chứng minh
BUDs và SuperBUDs được dùng để cấu thành nhiều chiến lược chứng minh khác nhau, mỗi chiến lược đều có những sự đánh đổi riêng.
Chỉ cần một lần kiểm tra BUD. Nếu Block Height được truy vấn trùng khớp với vị trí sửa đổi (hoặc chạm), chỉ cần một lần kiểm tra BUD là đủ. Cực kỳ nhỏ gọn, nhưng chỉ khả dụng tại các điểm sửa đổi.
Bằng chứng BUD kép. Hai bằng chứng BUD liên tiếp cho cùng một khóa, trong đó trường " Block đã được sửa đổi trước đó" của bằng chứng thứ hai trỏ đến bằng chứng đầu tiên, chứng minh giá trị tại bất kỳ Block nào ở giữa. Chuỗi sửa đổi trên mỗi khóa đảm bảo không bỏ sót bất kỳ thay đổi trung gian nào.
BUD + SuperBUD. Một bằng chứng BUD tại lần sửa đổi cuối cùng được kết hợp với một SuperBUD có phạm vi bao phủ cả lần sửa đổi đó và Block mục tiêu. SuperBUD xác nhận rằng không có sửa đổi nào sau đó tồn tại trong phạm vi của nó. Nhỏ gọn và tiết kiệm chi phí, nhưng có độ trễ vừa phải đối với các mục được sửa đổi gần đây và độ trễ cao hơn đối với các mục cũ.
Hình 3: Chiến lược BUD + SuperBUD. Bằng chứng BUD tại Block B2 kết hợp với SuperBUD trải dài từ A đến C chứng minh giá trị của khóa K tại bất kỳ Block cho đến giới hạn trên của SuperBUD, mà không cần giao dịch chạm.
BUD + nhiều SuperBUD. Để giảm độ trễ mà không cần giao dịch chạm, chuỗi nhiều SuperBUD liền kề để lấp đầy khoảng trống. Ít gọn hơn (kích thước bằng chứng tăng theo độ lỗi thời) nhưng tránh được chi phí on-chain .
Bằng chứng sửa đổi đầu tiên. Nếu một mục BUD có “ Block trước đó đã được sửa đổi” bằng -1 − 1 , điều đó chứng thực rằng khóa không tồn tại trước Block đó (quay trở lại một ngưỡng bằng chứng có thể cấu hình). Hữu ích cho các bằng chứng loại trừ và cho các khóa được tạo gần đây.
Lựa chọn thiết kế và tính linh hoạt
Công trình được xây dựng theo kiểu mô-đun một cách có chủ ý. Chúng tôi nhấn mạnh các trục linh hoạt chính:
Độ chi tiết của BUD. Chúng tôi trình bày trường hợp 1:1 (một BUD cho mỗi Block) làm mặc định, nhưng BUD cũng có thể được tạo ra cứ sau k khối trong cửa sổ trước đó. Điều này giúp giảm thiểu chi phí ký kết với chi phí là bằng chứng sẽ thô hơn một chút.
Cấu trúc và lịch trình của SuperBUD. Cơ sở e của hệ thống phân cấp kiểm soát hệ số phân nhánh. Với e = 2, số cấp tăng gấp đôi về phạm vi (2, 4, 8, 16, …) và độ sâu hợp nhất tối đa L xác định tuổi bằng chứng tối đa : hệ thống hỗ trợ bằng chứng cho bất kỳ Block trong e^L e L khối cuối cùng. e lớn hơn sẽ giảm số cấp nhưng tăng thời gian chờ đợi trong trường hợp xấu nhất. Lịch trình sản xuất (được căn chỉnh theo bội số của e^\ell e ℓ ) có thể được bù trừ hoặc sắp xếp so le nếu nhịp độ Tính chất cuối cùng của chuỗi khiến một số ranh giới trở nên tự nhiên hơn.
Tuổi thọ tối đa của bằng chứng và các bản ghi xóa. Việc xóa một khóa không được phá hủy chuỗi sửa đổi của nó. Thay vì xóa mục nhập, trạng thái sẽ ghi một bản ghi xóa (giá trị rỗng, siêu dữ liệu "lần sửa đổi cuối cùng" được bảo toàn). Tuổi thọ tối đa của bằng chứng có thể cấu hình (ví dụ: ngày hoặc tháng của các khối) giới hạn thời gian tồn tại của các bản ghi xóa: khi một bản ghi xóa cũ hơn thời gian giới hạn, nó sẽ bị thu gom rác. Các bằng chứng được tạo trước thời gian giới hạn vẫn hợp lệ và có thể xác minh vô thời hạn; điều hết hạn là khả năng tạo bằng chứng mới cho các khối rất cũ.
Bằng chứng loại trừ. Bản thân SuperBUD không thể chứng minh sự loại trừ vì chúng không khẳng định bất cứ điều gì về trạng thái hiện có của một khóa. Một bằng chứng loại trừ đầy đủ yêu cầu một mục nhập BUD (có thể được tạo thông qua một giao dịch chạm trên một khóa không tồn tại, tạo ra một bản ghi xóa). Đây là một sự đánh đổi có chủ ý trong thiết kế: trường hợp ngoại lệ của việc chứng minh sự vắng mặt của một khóa chưa từng tồn tại và không có bản ghi xóa là đủ hiếm gặp để việc yêu cầu một giao dịch chạm là có thể chấp nhận được.
So sánh với cây trạng thái toàn cầu
| Kích thước | Trie trạng thái toàn cầu (bao gồm nhị phân/Verkle) | BUDs + SuperBUDs |
|---|---|---|
| Vị trí kiến trúc | Trên con đường then chốt đồng thuận | Đã chuyển sang cơ sở hạ tầng lưu trữ |
| Chi phí cam kết trên mỗi khối | O(w \cdot \log n) O ( w ⋅ log n ) băm ( w w ghi, n n mục trạng thái) | O(w \cdot \log w) O ( w ⋅ log w ) băm ( w w chỉ ghi) |
| Bố cục cơ sở dữ liệu | Cần có điều kiện lưu trữ thuận lợi cho việc thử nghiệm. | Lưu trữ cặp khóa-giá trị phẳng, thêm 9 byte siêu dữ liệu cho mỗi mục nhập |
| Tạo bằng chứng cho trạng thái hiện tại | Ngay lập tức (đường dẫn Merkle đơn từ cây trie) | Kích hoạt ngay lập tức bằng thao tác chạm; nếu không, hãy chờ SuperBUD. |
| Kích thước bằng chứng | O(\log n) O ( log N ) | O(\log w) O ( log w ) mỗi BUD + O(\log s) O ( log s ) mỗi SuperBUD |
| Thân thiện với SNARK | Có thể chứng minh; mạch trên O(\log n) O ( log n ) đường đi | Có thể chứng minh; mạch trên O(\log w) O ( log w ) đường dẫn (nhỏ hơn) |
| gánh nặng lưu trữ của trình xác thực | Cây trie đầy đủ (các nút trung gian + nút lá) | Trạng thái hiện tại + 9 byte siêu dữ liệu |
| Ai cung cấp bằng chứng? | Trình xác thực hoặc các nút đầy đủ | Các nút lưu trữ (cơ sở hạ tầng chuyên dụng) |
Sự đánh đổi cốt lõi: cây trie toàn cục cung cấp bằng chứng tức thì cho bất kỳ khóa nào tại bất kỳ Block gần đây nào, với cái giá là sự ràng buộc giữa quá trình thực thi và việc duy trì cây trie. BUD chỉ cung cấp bằng chứng tức thì tại các điểm sửa đổi (hoặc theo yêu cầu thông qua thao tác chạm), nhưng giải phóng lớp thực thi khỏi bất kỳ ràng buộc nào có hình dạng cây trie.
Mục tiêu và các bước tiếp theo
BUD là một giải pháp kiến trúc thay thế lâu dài cho việc duy trì cây trạng thái toàn cục trên đường dẫn quan trọng của sự đồng thuận. Chúng không phải là một cơ chế chuyển tiếp cho các chuỗi đang chờ đợi để áp dụng một cấu trúc trie tốt hơn, cũng không phải là một lớp bổ sung được thêm vào trên một cấu trúc trie hiện có. Thay vào đó, BUD được thiết kế cho các chuỗi chọn không duy trì cấu trúc dữ liệu được xác thực toàn cục trong đường dẫn quan trọng của trình xác thực, ủy thác cơ sở hạ tầng bằng chứng cho các nút lưu trữ để đổi Xuất lượng thực thi không bị hạn chế.
Đối tượng chính là các máy chủ L1 và rollup có thông lượng cao, tương đương với EVM, nơi việc duy trì cây trạng thái đã hoặc đang trở thành nút thắt cổ chai trong quá trình thực thi. Đối với Ethereum L1, nơi quá trình chuyển đổi sang cây nhị phân (Đề xuất cải tiến Ethereum (EIP)-7864) đang được tiến hành, BUD không phải là lựa chọn phù hợp. Đối với các chuỗi đang thiết kế chiến lược cam kết trạng thái từ đầu, hoặc xem xét lại chiến lược này khi trạng thái phát triển, BUD cung cấp một lộ trình mở rộng hoàn toàn khác biệt.
Chúng tôi đang chuẩn bị một Đề xuất cải tiến Ethereum (EIP) mang tính thông tin để chính thức hóa quá trình xây dựng. Chúng tôi hoan nghênh thảo luận về thiết kế, lựa chọn thông số và các lộ trình áp dụng tiềm năng.
Bản RFC đầy đủ hiện có sẵn để xem xét; chúng tôi sẽ LINK (Chainlink) nó sau khi bản dự thảo Đề xuất cải tiến Ethereum (EIP) được công bố.
Câu hỏi mở
Chúng tôi hoan nghênh thảo luận về các vấn đề sau:
- Lựa chọn tham số: Giá trị nào của e cơ sở và tuổi bằng chứng tối đa là phù hợp cho các chuỗi có thông lượng cao trong thực tế ? Liệu e= 2 có phải là giá trị mặc định đúng, hay hệ số phân nhánh lớn hơn sẽ phù hợp hơn với phân bố tuổi khóa điển hình?
- Các trường hợp ngoại lệ cần chứng minh bằng chứng loại trừ: Yêu cầu giao dịch chạm phải chứng minh sự vắng mặt của một khóa chưa từng tồn tại là một sự đánh đổi có chủ ý. Điều này có thể chấp nhận được trong thực tế hay cần một giải pháp khác?
- Cơ chế khuyến khích nút lưu trữ: BUD ủy thác hoàn toàn việc cung cấp bằng chứng cho các nút lưu trữ. Cơ chế khuyến khích nào đảm bảo các nút lưu trữ vẫn hoạt động và trung thực trong thời gian dài?
- Lộ trình áp dụng: Đối với các chuỗi khối đã sử dụng kiến trúc trie trạng thái toàn cục, lộ trình chuyển đổi nào ít gây gián đoạn nhất sang BUD?
