Bằng chứng đa giá trị cây Merkle thưa thớt là gì
Lưu ý của biên tập viên: Bài viết này là từ:Những người đam mê Ethereum (ID: ethfans)Lưu ý của biên tập viên: Bài viết này là từ:
Những người đam mê Ethereum (ID: ethfans)
, Tác giả: Jim McDonald, bản dịch & hiệu đính: Pei Qi & A Jian, được Odaily tái bản với sự cho phép.
tiêu đề cấp đầu tiên
Khoa học phổ biến | Cắt ngắn Merkel là gì
Đa bằng chứng Merkle thưa thớt (Sparse Merkle multiproofs) là một giải pháp thay thế cho việc cắt bớt cây Merkle (Merkle pollard), có thể cung cấp không gian cho việc chứng minh sự tồn tại của nhiều giá trị trên một cây Merkle bằng chứng về sự tiết kiệm. Merkle proof là gì và Merkle tree truncated thì mình đã giải thích ở bài viết trước, khuyên các bạn nên đọc và hiểu các khái niệm này trước khi đọc bài viết này. Tiếp theo, văn bản sẽ sử dụng cây Merkle trong hình bên dưới để giải thích các bằng chứng đa giá trị:
Mô tả hình ảnh
Các bằng chứng đa giá trị thưa thớt lần đầu tiên được đề xuất bởi Vitalik Buterin.
bằng chứng đa giá trị
Mô tả hình ảnh
-Hình 2, 3, 4: Chứng minh Merkel tương ứng với Chuối, Đào, Quất tương ứng-
Như có thể thấy từ hình trên, 3 bằng chứng chứa tổng cộng 9 giá trị băm của các nhánh trung gian (tức là phần được đánh dấu màu xanh lá cây): mỗi bằng chứng có 3 giá trị băm. Kết hợp ba bằng chứng này thành cấu trúc như trong hình dưới đây là một bằng chứng đa giá trị:
Mô tả hình ảnh
-Hình 5: Bằng chứng đa giá trị Merkle tương ứng với Chuối, Đào và Quất-
Bằng chứng đa giá trị thưa thớt
Mặc dù bằng chứng đa giá trị của cây Merkle tiết kiệm một số dung lượng lưu trữ, nhưng một số dữ liệu có thể được lấy theo những cách khác, do đó, việc xóa những dữ liệu này có thể tiết kiệm thêm dung lượng lưu trữ. (Ghi chú của người dịch: Dữ liệu có thể lấy được bằng các phương tiện khác không cần được lưu trữ trong bằng chứng, miễn là có thể lấy được khi cần)
Mô tả hình ảnh
-Hình 6: Các giá trị băm có thể loại bỏ trong các bằng chứng đa trị cây Merkle (xem các dấu màu vàng)-
Sau khi loại bỏ các giá trị băm này, có thể thu được bằng chứng đa giá trị thưa thớt trong cây Merkle, như thể hiện trong hình sau:
Mô tả hình ảnh
-Hình 7: Bằng chứng đa giá trị cây Merkle thưa thớt-
Bằng chứng đa giá trị Merkle thưa thớt làm giảm số lượng giá trị băm cần được đưa vào từ 9 xuống còn 3. Bằng chứng đa giá trị thưa thớt cũng hiệu quả hơn so với bằng chứng cắt ngắn Merkle, yêu cầu 6 giá trị băm, cho cùng một bằng chứng.
Sau khi người xác minh có được bằng chứng đa giá trị thưa thớt, để xác minh rằng các giá trị đó là một phần của cây Merkle, cần thực hiện các bước sau (trong cây Merkle, theo thứ tự từ trái sang phải, từ trên xuống đáy):
(Ghi chú của người dịch: "Băm một giá trị" có nghĩa là: sử dụng giá trị làm đầu vào của hàm băm và nhận một chuỗi đầu ra ngẫu nhiên)
Băm chuối để nhận bc4f...8d3f
Băm Peach để nhận 59a0…421d
Băm Kumquat để nhận 2aab…6f791
băm bc4f...8d3f và 59a0...421d để nhận 9c15...5dec
băm 2aab…6f79 và 45cf…14d9 để nhận a6e4…87df
Băm d596…66ef và 9c15…5dec để lấy c0b7…da30
băm e336…ed14 và a6e4…87df để nhận 6ff9…8e3d
băm c0b7...da30 và 6ff9...8e3d để nhận d576...ffd9
Tại thời điểm này, giá trị băm cuối cùng có thể được so sánh với giá trị băm gốc của cây Merkle, nếu cả hai nhất quán thì tất cả các giá trị được xác định là nằm trong cây Merkle.
Hình dưới đây so sánh dung lượng lưu trữ mà cây Merkle đã cắt bớt và các bằng chứng đa giá trị thưa thớt trong cây Merkle có thể tiết kiệm khi lưu trữ các bằng chứng Merkle khi số lượng giá trị và bằng chứng trong cây Merkle thay đổi:
Điều đáng chú ý là mức tiết kiệm của bằng chứng đa giá trị là gần đúng, vì mức tiết kiệm phụ thuộc vào vị trí của giá trị đã được chứng minh trong cây Merkle và số lượng băm nhánh trung gian có thể được loại bỏ.
So sánh các bằng chứng đa giá trị thưa thớt với Merkle Truncated
Như có thể thấy từ bảng trên, bằng chứng đa giá trị thưa thớt tiết kiệm nhiều không gian lưu trữ hơn so với cắt bớt cây Merkle, vậy tại sao lại sử dụng cắt bớt cây Merkle? Bởi vì các bằng chứng đa giá trị thưa thớt có một số đặc điểm khác so với cây Merkle bị cắt cụt, các điểm chính như sau:
Trong phương pháp chứng minh đa giá trị, các bằng chứng cho tất cả các giá trị được tạo và xác minh cùng nhau, trong phương pháp rút gọn, các bằng chứng cho từng giá trị được tạo và xác minh riêng biệt. và các bằng chứng liên quan là cần thiết. Đối với các bằng chứng đa giá trị, cần xác minh nhiều giá trị và cần lấy ra các bằng chứng tương ứng của nhiều giá trị)
Bằng chứng đa giá trị thưa thớt yêu cầu nhiều bộ nhớ và chu kỳ CPU hơn để tạo và xác minh bằng chứng
Bằng chứng đa giá trị thưa thớt khó tạo và xác minh song song
Các bằng chứng đa giá trị thưa thớt có kích thước thay đổi, trong khi cắt cây Merkle có kích thước bằng chứng cố định cho một cây Merkle và tổng số bằng chứng
https://github.com/Trong một số trường hợp, do các hệ thống mã hóa khác nhau được sử dụng để truyền thông tin, nó có thể khiến các bằng chứng đa giá trị thưa thớt cần nhiều không gian hơn so với việc cắt bớt cây Merkle; do đó, nên kiểm tra trước khi sử dụng
