BTC
$96,000
5.73%
ETH
$3,521.91
3.97%
HTX
$0.{5}2273
5.23%
SOL
$198.17
3.05%
BNB
$710
3.05%
lang
简体中文
繁體中文
English
Tiếng Việt
한국어
日本語
ภาษาไทย
Türkçe
Trang chủ
AI AI
Tin nhanh
Bài viết
Sự kiện
BlockBeats Pro
Thêm
Thông tin tài chính
Chuyên đề
Hệ sinh thái chuỗi khối
Mục nhập
Podcast
Data
OPRR
Partnered With:

Ethereum không quốc tịch: Một thử nghiệm với cây trạng thái nhị phân

Đọc bài viết này mất 19 phút
Nhiều ý tưởng đã được đề xuất nhằm giảm kích thước của dữ liệu nhân chứng, một trong những phương pháp đó là chuyển đổi cây Merkle của Ethereum từ hệ thập lục phân sang hệ nhị phân.

Tiêu đề gốc: "Ethereum không trạng thái: Thử nghiệm cây trạng thái nhị phân"
Nguồn gốc: Những người đam mê Ethereum 
Tác giả: Igor Mandrigin

Dữ liệu và tập lệnh được sử dụng trong bài viết này được đặt trong cơ sở mã github này:
https://github.com/mandrigin/ethereum-mainnet-bin-tries-data

Là gì “Ethereum không quốc tịch”?


Nếu bạn đã biết "Ethereum không quốc tịch" và "Dữ liệu nhân chứng khối" là gì, bạn có thể bỏ qua đoạn này .


Để thực hiện giao dịch và xác minh khối, các nút trong mạng Ethereum cần hiểu trạng thái hiện tại của toàn bộ chuỗi khối—tức là Số dư và lưu trữ dữ liệu cho tất cả các tài khoản và hợp đồng. Dữ liệu này thường được lưu trữ trong DB (tệp cơ sở dữ liệu) và được tải vào cây Merkle khi cần để xác minh.

Ý tưởng hoạt động của ứng dụng khách Ethereum không trạng thái hơi khác một chút. Như tên cho thấy, máy khách không trạng thái không sử dụng DB đĩa cứng để thực thi các khối (mặc dù trạng thái hoàn chỉnh có thể được duy trì trong máy khách). Ngược lại, các máy khách không trạng thái dựa vào "nhân chứng khối" - một phần dữ liệu đặc biệt được truyền đi với khối tương ứng; với dữ liệu này, máy khách có thể xây dựng lại một cây con Merkle ( ) đại diện cho trạng thái một phần đủ để thực hiện tất cả các giao dịch trong khối.

Bạn có thể đọc mô tả sâu hơn về khách hàng không quốc tịch trong bài viết này: https://blog.ethereum.org/2019 /12/30/eth1x-files-state-of-stateless-ethereum/

Tất nhiên, khối cần phải được phổ biến Chứng kiến dữ liệu có nghĩa là các máy khách không trạng thái có yêu cầu mạng cao hơn các nút thông thường.

1
-Biểu đồ đường kích thước dữ liệu chứng kiến (chiều cao khối 5 triệu đến 8,5 triệu)-

Nhiều ý tưởng đã được đề xuất để giảm kích thước dữ liệu nhân chứng: sử dụng bằng chứng tính hợp lệ/tính toàn vẹn tính toán (bao gồm nhưng không giới hạn ở bằng chứng không có kiến thức), bổ sung thêm Nhiều phương pháp nén, v.v. Một cách là chuyển đổi cây Merkle của Ethereum (cây Merkle dùng để biểu diễn Ethereum) từ hệ thập lục phân sang hệ nhị phân.
Đây chính là vấn đề mà bài viết này muốn khám phá.

Tại sao nên sử dụng cây nhị phân


Một trong những tính năng hay của cây Merkle là việc xác minh rằng giá trị gốc (là giá trị băm) là chính xác không yêu cầu bạn phải có toàn bộ Tất cả dữ liệu của cây. Chỉ cần thay thế tất cả các đường dẫn không trống bị bỏ qua bằng các giá trị băm tương ứng.


Vậy nhược điểm của việc sử dụng cây Merkle thập lục phân là gì?

Hãy tưởng tượng toàn bộ cây chứa đầy dữ liệu (nghĩa là các nút trên cây hầu như không có nút con nào bằng 0) . Để xác minh một khối, chúng tôi chỉ cần dữ liệu từ một tập hợp nhỏ các nút cây Merkle. Sau đó, chúng ta chỉ cần thay thế dữ liệu của các đường dẫn khác bằng giá trị băm (làm cho cây con này có thể kiểm chứng được).

Tuy nhiên, với mỗi giá trị băm bổ sung được thêm vào, dữ liệu chứng kiến khối sẽ lớn hơn.

Nếu chúng ta chuyển đổi sang cây Merkle nhị phân, vấn đề này có thể được giảm bớt - vì mỗi phần tử trong cây Merkle Mỗi nút chỉ có hai trẻ em, do đó, tối đa một byte cần được thay thế bằng giá trị băm. (Nói cách khác, chúng ta có thể bắt đầu "cắt" đường đi của cây Merkle sớm hơn vì độ chi tiết của chúng ta là 1 bit thay vì 4 bit ở dạng hex.)

Làm như vậy có thể làm giảm đáng kể kích thước của dữ liệu nhân chứng.

Hãy lấy một ví dụ khác.

Giả sử rằng việc thực thi một khối nhất định sẽ chỉ ảnh hưởng đến một tài khoản: Acc1 theo đường dẫn 3B (0011 1011 ở dạng nhị phân). Toàn bộ cây đã đầy (không có nút nào trong cây có 0 nút con).

2

3

-So sánh cây trạng thái nhị phân và cây trạng thái thập lục phân -

Nếu cây trạng thái nhị phân trông hơi đáng sợ thì đó chỉ là do tôi đã vẽ toàn bộ cây nhị phân mà không vẽ phần hex Tất cả các nút của cây được vẽ với các giá trị băm của chúng được thay thế.
Đếm các số:

Để tạo To tạo cây trạng thái nhị phân, dữ liệu nhân chứng cần chứa 8 giá trị băm, 7 nút nhánh và 1 nút tài khoản. Tức là có 16 yếu tố trong dữ liệu nhân chứng.
Để tạo cây trạng thái hex, chúng ta chỉ cần 1 nút nhánh, 1 nút tài khoản nhưng cần tới 30 giá trị băm. Tức là có 32 phần tử.


Vì vậy, giả sử rằng giá trị băm và nút nhánh chiếm cùng một không gian trong dữ liệu chứng kiến khối (thực tế giá trị băm chiếm không gian lớn hơn một chút ), trong trường hợp của chúng tôi, kích thước dữ liệu nhân chứng được yêu cầu khi sử dụng cây nhị phân chỉ bằng một nửa kích thước của cây thập lục phân. Có vẻ tốt.


Đó là lý thuyết.

Hãy xem tình hình thực tế ra sao. Chúng ta hãy xem trực tiếp dữ liệu từ mạng chính Ethereum.

Bắt đầu thử nghiệm


Trước tiên hãy nói về điều quan trọng nhất: Làm sao chúng ta biết rằng dữ liệu chứng kiến khối mà chúng ta xây dựng là hữu ích?


Phương pháp thử nghiệm như sau: chúng tôi sử dụng dữ liệu nhân chứng khối để tạo cây con Merkle và chạy Tất cả các giao dịch tương ứng trong chặn và sau đó xác minh rằng kết quả phù hợp với những gì chúng tôi biết. Chỉ cần các giao dịch được thực hiện thành công (gas là đủ, dấu vết giống nhau (có dấu vết giống nhau), v.v.), chúng ta có thể kết luận rằng nhân chứng là đủ.

4

-Phương pháp thử nghiệm: 1. Thực thi khối; 2. Trích xuất dữ liệu chứng kiến từ cây trạng thái ;3. Xây dựng cây con bằng dữ liệu nhân chứng 4. Vô hiệu hóa quyền truy cập DB và sử dụng cây con để thực thi các khối (xem github để biết chi tiết)-


Thứ hai, chúng tôi cần một số dữ liệu điểm chuẩn (để so sánh). Do đó, chúng tôi cũng tạo dữ liệu nhân chứng ở chế độ cây Merkle hex bằng cách sử dụng các khối có chiều cao từ 5 triệu đến 8,5 triệu và lưu trữ số liệu thống kê về kích thước nhân chứng trong một tệp csv siêu lớn.


Bước đầu tiên chúng tôi thử là tập hợp một cây thập lục phân sau khi thực thi một khối, sau đó Chuyển đổi nó thành cây nhị phân, sau đó trích xuất dữ liệu nhân chứng từ cây nhị phân này.

Phương pháp này có một số lợi ích: dễ thực hiện và việc xác minh việc chuyển đổi từ hệ thập lục phân sang nhị phân cũng đơn giản.

Tuy nhiên, chúng tôi gặp phải hai vấn đề và một trong số đó khá nhỏ.

Đầu tiên, như chúng tôi đã chứng minh ở trên, cây thập lục phân chứa nhiều nút tài khoản hơn cây nhị phân , nếu trước tiên chúng ta tạo cây thập lục phân và sau đó chuyển đổi, kết quả sẽ khác với dữ liệu chứng kiến thu được bằng cách tạo trực tiếp ở chế độ cây nhị phân.

Tại sao?

Vì dữ liệu cây thập lục phân luôn tăng với tốc độ 1/2 byte, trong khi cây nhị phân luôn tăng với tốc độ 1 tốc độ tăng trưởng bit, do đó độ dài khóa có thể là số bit lẻ.

Trên thực tế, dữ liệu nhân chứng cũng chứa một số nút mở rộng bổ sung (nút EXTENSION), lớn hơn một chút. Tuy nhiên, ngay cả đối với các khối có nội dung lớn (khối chứa khoảng 5.000 giao dịch), sự khác biệt về kích thước dữ liệu chứng kiến là rất nhỏ (dưới 5%).

Điều quan trọng là hiệu suất. Khi kích thước của cây lớn lên, quá trình biến đổi ngày càng chậm hơn.

Để diễn đạt điều này thành những con số cụ thể hơn: Trên máy ảo Google Computer Engine của chúng tôi, tốc độ xử lý là khoảng 0,16 khối mỗi giây, tức là , xử lý ít hơn 10 khối mỗi phút và sẽ mất hơn 3 tháng để xử lý 1 triệu khối!

Vì vậy, chúng tôi quyết định thực hiện một cách tiếp cận phức tạp hơn và phát triển một nhánh thử nghiệm vốn sử dụng cây Merkle nhị phân. Nói cách khác, chúng ta cần thay thế tất cả các cây trạng thái thập lục phân trong cơ sở mã turbo-geth bằng cây nhị phân, sau đó các khối được thực thi dựa trên cây nhị phân.

Nhược điểm của phương pháp này là chỉ có thể bỏ qua việc xác minh một phần giá trị băm (chặn hàm băm gốc, Đôi khi tài khoản lưu trữ băm gốc vì cơ chế chụp nhanh blockchain của chúng tôi còn thiếu).

Nhưng cơ chế xác minh chính vẫn giống nhau: chúng ta cần có khả năng sử dụng cây nhị phân để thực thi khối và tạo mặc định từ dữ liệu nhân chứng.

Hãy nói lại về phím.

Để đơn giản, cách chúng tôi mã hóa khóa rất kém hiệu quả: 1 byte mỗi nibble; mỗi bit của một khóa Nó sẽ chiếm 1 byte. Điều này giúp đơn giản hóa đáng kể các thay đổi cấp mã, nhưng phần "khóa" trong dữ liệu nhân chứng khối sẽ lớn hơn 8 lần so với khi chúng tôi sử dụng bitset (để hiểu dữ liệu nhân chứng khối bao gồm dữ liệu gì, vui lòng xem Nghiên cứu sơ bộ "Khách hàng không quốc tịch"" ) (Ghi chú của biên tập viên: Xem siêu liên kết ở cuối bài viết để biết bản dịch tiếng Trung).

Do đó, khi phân tích sâu hơn, tôi sẽ cho rằng khóa Phương thức mã hóa là tối ưu (dùng 1 bit để mã hóa 1 bit thông tin).

Hex so với Bin: Kết quả


Phân tích của tôi được chia thành hai phần, phân tích tổng cộng 2 triệu khối trên mạng chính Ethereum.


Chiều cao khối 5 triệu đến 6,5 triệu
Tôi cung cấp một dòng lệnh để lặp lại thử nghiệm này bằng cách sử dụng tập lệnh python trong kho lưu trữ github này: https://github.com/mandrigin/ethereum-mainnet-bin-tries-data

Trước tiên, hãy phân tích tập dữ liệu.

python Percentile.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 điều chỉnh

5

-Một ô hộp, hộp hiển thị dữ liệu giữa tứ phân vị trên và tứ phân vị dưới, Các đường kéo dài sang trái và bên phải hiển thị dữ liệu giữa 1% trên và 1% dưới (nghĩa là không bao gồm dữ liệu 1% cực lớn và cực nhỏ)



Bây giờ chúng ta có thể tạo một số biểu đồ thú vị!

python xy-scatter-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 điều chỉnh

6

- Biểu đồ phân tán XY (giả sử rằng khóa được mã hóa tối ưu) (trục ngang là The size của dữ liệu nhân chứng dưới dạng Hex, trục tung là kích thước của dữ liệu nhân chứng trong Bin) -

Có thể thấy rằng kích thước của dữ liệu nhân chứng nhị phân luôn tốt hơn dữ liệu nhân chứng dưới cây hex.
Hãy thêm một tham số khác và chia kích thước dữ liệu nhân chứng nhị phân cho kích thước dữ liệu nhân chứng thập lục phân để xem chúng tôi nhận được loại cải tiến nào .

python size-improvements-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 điều chỉnh

7

-kích thước của dữ liệu chứng thực nhị phân/kích thước của dữ liệu chứng thực thập lục phân (giá trị càng nhỏ Càng tốt ) -

Để hiểu rõ hơn về biểu đồ này, chúng tôi cũng đưa ra giá trị trung bình và giá trị phần trăm.
Trung bình = 0,51 (trung bình tiết kiệm được 49% dung lượng)
P95 = 0,58 (sắp xếp theo mức độ tiết kiệm, đối với 95% dữ liệu đầu tiên, ít nhất 42% dung lượng được tiết kiệm)
P99 = 0,61 (sắp xếp theo thứ tự lưu, đối với 99% dữ liệu, ít nhất 39% dung lượng được lưu)

Trong kịch bản thực tế, điều này có nghĩa là gì?

Đối với 99% khối, kích thước của dữ liệu nhân chứng có thể giảm ít nhất 39%.

Đối với 95% khối, kích thước của dữ liệu nhân chứng có thể giảm ít nhất 42%.

Trung bình, dữ liệu nhân chứng tiết kiệm được 49%.

Chúng ta cũng cần xem xét giá trị tuyệt đối của kích thước dữ liệu nhân chứng. Để làm cho dữ liệu có thể đọc được, chúng tôi lấy trung bình trượt sau mỗi 1024 khối.

python tuyệt đối-giá trị-plot.py hex-witness-raw.csv bin-stats-5m-6.5m.csv 5000000 6500000 điều chỉnh

8

-biểu đồ đường kích thước dữ liệu nhân chứng được vẽ theo thứ tự thời gian, đơn vị trục tung là MB-

Hãy cùng xem khối mới nhất.
Chiều cao khối 8 triệu đến 8,5 triệu
phân vị python . py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 điều chỉnh

9

-Biểu đồ hình hộp, hộp biểu thị dữ liệu nằm trong phần tư trên và phần tư dưới, còn đường thẳng thể hiện dữ liệu trong phần tư trên và dưới 1%-




- 8 triệu đến 8,5 triệu Phần trăm phân tích số khối-

Ngoài ra còn có biểu đồ phân tán XY.
python xy-scatter-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 điều chỉnh

10

Ngoài ra còn có sự tiết kiệm về quy mô.

python size-improvements-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 điều chỉnh

11

- Biểu đồ phân tán XY (giả sử rằng khóa được mã hóa tối ưu) (trục hoành là Hex The kích thước của dữ liệu nhân chứng trong Thùng, trục tung là kích thước dữ liệu nhân chứng trong Thùng) -
Trung bình = 0,53 (trung bình, 47% không gian được tiết kiệm)
P95 = 0,61 (sắp xếp theo mức độ tiết kiệm, đối với 95% dữ liệu đầu tiên, ít nhất 37% dữ liệu đã tiết kiệm được dung lượng)
P99 = 0,66 (sắp xếp theo thứ tự tiết kiệm, đối với 99% dữ liệu, ít nhất 34% dung lượng được tiết kiệm)

Cuối cùng, hãy xem kích thước tuyệt đối của dữ liệu nhân chứng.

python tuyệt đối-giá trị-plot.py hex-witness-raw.csv bin-stats-8m-9m.csv 8000000 8500000 điều chỉnh

12

-biểu đồ đường kích thước dữ liệu nhân chứng được vẽ theo thứ tự thời gian, đơn vị trục tung là MB-

span>


Kết luận


Sau khi thử nghiệm với dữ liệu mạng chính Ethereum, chúng tôi có thể thấy rằng việc chuyển sang chế độ cây nhị phân có thể cải thiện đáng kể hiệu quả tạo dữ liệu nhân chứng (kích thước của dữ liệu nhân chứng giảm đi một lượng trung bình 47 -49%).


Một kết luận khác là sự cải thiện này không đáng kể bằng về mặt lý thuyết. Nguyên nhân có thể nằm ở dữ liệu thực tế của khối mainnet (phức tạp hơn tưởng tượng).

Có lẽ, bằng cách phân tích một số trường hợp ngoại lệ (tức là các trường hợp cây nhị phân đạt được ít cải thiện nhất), chúng ta có thể biết thêm về tối ưu hóa chứng kiến cách tiếp cận quy mô dữ liệu.

Hãy thử sử dụng dữ liệu thô khác để chạy tập lệnh trong GitHub: https://github.com/mandrigin/ethereum -mainnet- bin-tries-data

(End)

Liên kết gốc: https://medium.com/@ mandrigin/stateless-ethereum-binary-tries-experiment-b2c035497768
Liên kết nguồn: https://ethfans.org/posts /stateless- ethereum-binary-thử-thử nghiệm



Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia

举报 Báo lỗi/Báo cáo
Chọn thư viện
Thêm mới thư viện
Hủy
Hoàn thành
Thêm mới thư viện
Chỉ mình tôi có thể nhìn thấy
Công khai
Lưu
Báo lỗi/Báo cáo
Gửi