Giới thiệu về cây Merkel: Nó là gì và nó hoạt động như thế nào?

Cây Merkle là cây nhị phân gồm các giá trị băm, trong đó mỗi nút lá đại diện cho một phần dữ liệu hoặc hàm băm của một phần dữ liệu. Nó được sử dụng để xác minh tính toàn vẹn của một lượng lớn dữ liệu một cách hiệu quả. Nó được phát minh bởi Ralph Merkle vào năm 1979 và được sử dụng rộng rãi trong các loại tiền điện tử như Bitcoin và Ethereum.

Hàm băm giống như một máy lấy dấu vân tay. Nó nhận bất kỳ đầu vào nào, chẳng hạn như tệp, văn bản hoặc số và tạo ra một đầu ra duy nhất, được gọi là hàm băm, ngắn hơn nhiều so với đầu vào. Băm giống như dấu vân tay của đầu vào. Thật khó để tìm thấy hai đầu vào khác nhau có cùng hàm băm. Và không thể lấy đầu vào ban đầu từ hàm băm.

Ví dụ: nếu bạn có tệp có tên " kishan.jpg " có kích thước 1 MB, bạn có thể sử dụng hàm băm để lấy hàm băm chỉ dài 64 ký tự, chẳng hạn như 0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F .

Nếu bạn thay đổi dù chỉ một pixel trong tệp, hàm băm sẽ hoàn toàn khác, chẳng hạn như C69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AF .

Vì vậy, bạn có thể sử dụng hàm băm để xác minh rằng tệp vẫn giống như trước đây.

Nhưng nếu bạn có nhiều tệp thì sao? Việc tính toán và lưu trữ hàm băm cho từng tệp riêng biệt sẽ rất tẻ nhạt. Đó là nơi cây Merkle có ích.

Cây Merkle giống như một cây gia đình băm. Bạn bắt đầu với giá trị băm của mỗi tệp dưới dạng lá của cây . Sau đó, bạn ghép các giá trị băm và kết hợp chúng để có được các giá trị băm mới. Bạn lặp lại quá trình này cho đến khi bạn đạt đến đỉnh của cây, nơi bạn chỉ còn lại một hàm băm. Hàm băm này được gọi là Merkle root .

Gốc Merkle giống như dấu vân tay của tất cả các tệp trong cây. Nếu bất kỳ tệp nào thay đổi, hàm băm của nó sẽ thay đổi và tất cả các hàm băm phía trên nó cũng vậy cho đến khi gốc Merkle thay đổi . Vì vậy, bạn có thể sử dụng gốc Merkle để xác minh rằng tất cả các tệp đều giống như trước đây.

Nhưng làm thế nào để bạn xác minh một tập tin cụ thể? Bạn không cần tải xuống và kiểm tra tất cả các tệp trong cây. Bạn chỉ cần tải xuống và kiểm tra một vài giá trị băm dọc theo đường dẫn từ tệp đến thư mục gốc Merkle. Con đường này được gọi là bằng chứng Merkle .

Ví dụ: giả sử bạn muốn xác minh xem tệp "cat.jpg" có đúng không. Bạn chỉ cần tải xuống hàm băm HA của nó là 0a6df4 , hàm băm của anh chị em của nó HB (ea12e7) , hàm băm của anh chị em của cha mẹ H CD (b582ae) và gốc Merkle H ABCD (7bd24f) .

Sau đó, bạn có thể tính H AB bằng cách kết hợp HA và HB và tính H ABCD bằng cách kết hợp H AB và H CD . Nếu H ABCD khớp với gốc Merkle, bạn có thể chắc chắn rằng." cat.jpg " là chính xác.

Bạn có thể sử dụng phép loại suy tương tự để xác minh xem giao dịch có trong khối có được kiểm duyệt hay không bằng cách xác minh gốc Merkle thay vì cat.jpg hoặc dog.txt. Nó sẽ là một loạt các giao dịch tại các nút lá.

Xin lưu ý: Tôi đã cắt bớt giá trị băm thành 6 ký tự trong ví dụ trên để làm cho sơ đồ trông rõ ràng.

Nếu tôi chỉ có ba nút lá thì sao? Tôi sẽ tạo Cây Merkle như thế nào?

Kịch bản này có thể nhanh chóng được giải quyết bằng cách sao chép một nút, do đó tạo ra tổng số nút là bốn.

Ví dụ: giả sử bạn có giao dịch. TA , TB , và TC . Bạn có thể tính toán giá trị băm của chúng. HA , HB và HC . Sau đó, bạn có thể nhân đôi HC để nhận H C' . Sau đó; bạn có thể ghép nối và kết hợp các giá trị băm để có được H AB , H CC' và H ABCC' . Gốc Merkle là H ABCC' .

Tóm lại, cây Merkle mang lại lợi ích cho chuỗi khối và các hệ thống phân tán khác, nơi nhiều máy tính phải chia sẻ và xác minh lượng lớn dữ liệu. Bằng cách sử dụng cây Merkle, họ có thể tiết kiệm băng thông, lưu trữ và thời gian tính toán.

Đây là một ví dụ Java nhanh để chỉ ra cách bạn có thể tạo cây Merkle của riêng mình:

 import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; class MerkleTree{ static class Node { String content; public Node(String content) { this.content = content; } public String getHash() throws NoSuchAlgorithmException { MessageDigest md = MessageDigest.getInstance("SHA-256"); byte[] hash = md.digest(content.getBytes(StandardCharsets.UTF_8)); StringBuilder buffer = new StringBuilder(); for (byte b : hash) { buffer.append(String.format("%02x", b)); } return buffer.toString(); } } public static void main(String[] args) throws NoSuchAlgorithmException{ Node cat = new Node("I am a cat, this is a cat file called cat.jpg"); Node dog = new Node("I am a dog, this is a dog file called dog.txt"); // we have two leaf nodes, in order to create a merkle root, // we simple need to get their individual hashes // and then combine those hashes and hash them again String HA = cat.getHash(); String HB = dog.getHash(); Node merkleRoot = new Node(HA + HB); String HAB = merkleRoot.getHash(); System.out.println("Merkle Root: " + merkleRoot.getHash()); // let's say we altered the cat file cat = new Node("I am a cat, this is a cat file called dog.jpg"); // notice we have changed the cat.jpg to dog.jpg String HA_MODIFIED = cat.getHash(); Node modifiedMerkleRoot = new Node(HA_MODIFIED + HB); String HAB_MODIFIED = modifiedMerkleRoot.getHash(); System.out.println("Merkle Root: " + HAB_MODIFIED); } }

Đầu ra:

 Merkle Root: d1da3503d679f032134b4330768d31e67813fcfe2824fceed93f8185a405bdf9 Merkle Root: 1a898c7fee0e46647e55d5f9874f090e5ed76726acf39308527a0bba22a34b3e

Tôi cảm ơn bạn đã dành thời gian để đọc bài viết của tôi. Hãy ủng hộ tôi bằng cách theo dõi tôi trên Hackernoon để bạn nhận được thông báo bất cứ khi nào tôi xuất bản một bài báo.

Cảm ơn rất nhiều.

Đi sâu vào các bài viết sâu sắc về các xu hướng hệ thống phi tập trung, Công nghệ và AI: https://www.0xkishan.com . Hãy ghé thăm để thể hiện sự hỗ trợ của bạn.

Cũng được xuất bản ở đây.