Merkle Pollard là gì?

星球君的朋友们

Odaily资深作者

2019-04-13 11:08 (UTC+8)

Bài viết này có khoảng 2552 từ, đọc toàn bộ bài viết mất khoảng 4 phút

Nguyên tắc Merkle Tree là một phần của stark.

Tóm tắt AI

Nguyên tắc Merkle Tree là một phần của stark.

, được in lại bởi Odaily với sự cho phép.medium, được in lại bởi Odaily với sự cho phép.

tiêu đề phụ

hàm băm

Mô tả hình ảnh

-băm-

cây thủy sinh

Cây Merkle đề cập đến sự kết hợp của nhiều giá trị đầu vào và giá trị băm của chúng để nén thành một giá trị có độ dài cố định.

Mô tả hình ảnh

-Cây Merkel-

Cây Merkle hiển thị ở trên có 8 giá trị đầu vào và được chia thành 4 lớp. Nút gốc là 0xd576...ffd9 ở cuối.

Mô tả hình ảnh

-Hiệu ứng của sự thay đổi trên toàn bộ cây Merkle (như thể hiện trong phần tô màu xám)-

tiêu đề phụ

con đường Merkel

Mô tả hình ảnh

-"Peach"tiêu đề phụ

bằng chứng Merkel

Mô tả hình ảnh

-Bằng chứng Merkel-

Bằng chứng Merkle yêu cầu ba điều: giá trị đầu vào (được đánh dấu màu đỏ), hàm băm nhánh trung gian (được đánh dấu màu xanh lá cây) và nút gốc Merkle (được đánh dấu màu xanh lam). Tập hợp các giá trị băm nhánh trung gian tương ứng với mỗi giá trị đầu vào là khác nhau.

Các hệ thống chuỗi khối thường sử dụng bằng chứng Merkle để chứng minh rằng một giá trị đầu vào nhất định tồn tại trong một tập dữ liệu, do đó toàn bộ tập dữ liệu không cần phải được lưu trữ trên chuỗi khối. Giả sử rằng có một danh sách danh sách trắng trong hợp đồng Ethereum và chỉ những tài khoản trong danh sách mới được phép mua Ethereum. Nếu thông tin của từng tài khoản trong danh sách trắng được lưu trữ trên chuỗi khối, nó nhất định phải trả chi phí cao. Trong trường hợp này, chỉ cần tạo một cây Merkle và lưu trữ nút gốc trên chuỗi khối.

Ví dụ: nếu nút gốc được lưu trữ trên hợp đồng thông minh, hợp đồng thông minh có thể dễ dàng chứng minh rằng tài khoản được đưa vào danh sách trắng: tài khoản cần cung cấp hàm băm nhánh trung gian (được cung cấp bởi chủ sở hữu hợp đồng thông qua một số phương tiện ngoại tuyến). ) cho chủ tài khoản), hợp đồng thông minh lần lượt thực hiện tính toán hàm băm trên giá trị băm của tài khoản này và giá trị băm của nhánh trung gian. Nếu kết quả cuối cùng phù hợp với nút gốc Merkel, điều đó chứng tỏ rằng tài khoản thực sự nằm trong danh sách trắng.

Lưu ý mối quan hệ giữa đường dẫn Merkle và hàm băm của bằng chứng Merkle trong hai hình cuối. Trong cùng một cấp độ của cùng một cây, giá trị băm của bằng chứng Merkle tương quan với giá trị băm của đường dẫn Merkle. Từ đó, có thể thấy rằng bằng chứng Merkle có thể định hình lại đường dẫn Merkle của giá trị đầu vào, đó là lý do tại sao kết quả cuối cùng là nút gốc Merkle.

Cho đến nay, có thể thấy rằng bằng chứng Merkle có những đặc điểm sau:

Lưu trữ bằng chứng Merkle trên chuỗi cần ít không gian hơn nhiều so với lưu trữ trực tiếp các giá trị đầu vào
Lưu trữ công khai bằng chứng Merkle trên chuỗi cũng không hiển thị toàn bộ tập hợp giá trị đầu vào
tiêu đề phụ

bằng chứng trùng lặp

Trong ví dụ trên, mỗi tài khoản chỉ cần gửi chứng chỉ Merkle để xác minh xem nó có nằm trong danh sách trắng hay không.

Ngoài ra, cây Merkle cũng có thể được sử dụng làm bằng chứng xác suất về tri thức (thường được gọi là STARK), mỗi bằng chứng về tri thức có thể khiến chúng ta (tức là “người xác minh, người thách thức”) bị thuyết phục hơn: người tạo ra cây Merkle (tức là “người chứng minh”) ) biết tất cả các giá trị hợp thành. Trong trường hợp này, người chứng minh thường tạo ra hàng trăm bằng chứng dựa trên cây Merkle chứa hàng chục hoặc thậm chí hàng trăm giá trị đầu vào. Những bằng chứng này được gửi đến trình xác thực cùng với các nút gốc Merkle để xác minh tính hợp lệ của chúng.

Mô tả hình ảnh

-Bằng chứng trùng lặp về cùng một gốc Merkle-

Có thể thấy rằng có tổng cộng một nút gốc Merkle và ba chứng chỉ được gửi, cộng lại tổng cộng 10 giá trị băm: một cho nút gốc và ba cho mỗi trong số ba chứng chỉ còn lại.

Mô tả hình ảnh

-Bằng chứng trùng lặp về nút gốc Merkle mở rộng-

tiêu đề phụ