MERKLE TREE LÀ GÌ

     

Câu chuyện về Merkle Tree bước đầu từ năm 1979 với một tuổi teen tên Ralph Merkle. Khi còn học tại trường đh Stanford, Merkle vẫn viết một bài bác báo học thuật có tên là “Chữ ký kết số được chứng nhận” “A Certified Digital Signature”. Nói biện pháp khác, anh ta đã xây đắp một quy trình xác minh dữ liệu chất nhận được máy tính thực hiện các bước của mình nhanh hơn nhiều so cùng với trước đây.

Bạn đang xem: Merkle tree là gì

Ý tưởng của Merkle, hiện nay được nghe biết với thương hiệu Merkle Tree, đã cách mạng hóa trái đất mã hóa bằng phương pháp mở rộng phương thức mà giao thức máy tính mã hóa hoạt động. Trên thực tế, Merkle Tree được nhắc tới nhiều lần trong bài viết năm 2008 của Satoshi Nakamoto để ra mắt Bitcoin với vậy giới. Chúng cũng khá được sử dụng thoáng rộng trong mã Bitcoin.

Mục đích của bài bác đăng này là hỗ trợ cái nhìn bao quát về kết cấu dữ liệu cây Merkle (Merkle Tree) cơ bản và cũng là điểm bắt đầu cho các chủ đề nâng cao hơn tương quan đến Merkle Tree.


Nội dung bài xích viết ẩn
1.Merkle Tree là gì?
2.Cách thức hoạt động
3.Độ phức tạp của Merkle Tree
4.Lợi ích của Merkle Tree
5.Mekle Tree trong Bitcoin
6.Các ứng dụng khác của Merkle tree
7.Kết luận

Merkle Tree là gì?

Cây Merkle là một cấu trúc dữ liệu dạng cây trong đó mọi nút lá được dán nhãn bởi giá trị băm của khối tài liệu và đầy đủ nút không phải là nút lá được dán nhãn bằng giá trị băm của nhãn của các nút bé của nó. Cây băm chất nhận được xác minh công dụng và an ninh nội dung của các kết cấu dữ liệu lớn. Cây băm là 1 trong dạng bao quát của list băm và chuỗi băm.

*

Khái niệm “cây” là một khái niệm phổ biến trong kỹ thuật máy tính, đề cập cho một cấu trúc bao hàm các nút thân phụ và những nút nhỏ phân nhánh từ những nút thân phụ này.

Nhìn sống trên hình ta thấy rằng nút lá Hash 0-0 cùng Hash 0-1 có nhãn là quý giá băm của nhị khối tài liệu L1 với L2, và nút không hẳn là nút lá Hash 0 tất cả nhãn là giá trị băm của Hash 0-0 và Hash 0-1.

Với dạng cây băm merkle tree này, con số phép đo lường và thống kê hàm băm xác suất với logarit của số nút là của cây. Trong lúc với các danh sách băm thì số lượng này phần trăm với con số nút của chủ yếu nó.

Chính điều này khiến cho việc đo lường và thống kê và xác minh, tìm kiếm cực hiếm băm trên khối ra mắt nhanh rộng trên những khối dữ liệu lớn.

Cây Merkle, theo phong cách hiểu 1-1 giản, lấy rất nhiều dữ liệu, nén nó thành một chuỗi cam kết tự đơn giản có thể chứng minh tính đúng đắn của tài liệu được giữ lại trong đó, nhưng mà không bật mí dữ liệu sẽ là gì. Tương tự như như một file đã được nén (.ZIP hoặc .RAR), nếu như được đặt tên đúng đắn theo một tiêu chuẩn nhất định, tín đồ dùng rất có thể nhận ra ngôn từ mà không cần phải giải nén với mở các tệp chứa. Chuỗi ký tự (tiêu đề) này được gọi là giá trị băm. Giá trị băm được tạo thành từ hàm băm là 1 trong những hàm một chiều, tức là nếu chúng ta đặt và một dữ liệu, các bạn sẽ luôn nhận ra cùng một quý giá băm, nhưng chúng ta không thể lấy giá trị băm đó cùng trích xuất ra được tài liệu gốc.

Cách thức hoạt động

Merkle tree tóm tắt tất cả các giao dịch trong một khối bằng phương pháp tạo dấu hiệu đặc trưng (giá trị băm) của toàn bộ các giao dịch, tự đó được cho phép người dùng dễ dãi xác minh coi một thanh toán có trường thọ trong một khối hay không.

Merkle tree được tạo bằng cách liên tục băm các cặp nút cho tới khi chỉ với lại một quý giá băm (giá trị băm này được hotline là Hash Root hoặc Merkle Root). Các giá trị băm được xem từ bên dưới lên, ban đầu từ các giao dịch chưa có người yêu (được điện thoại tư vấn là những ID giao dịch).

Mỗi nút lá là một trong giá trị băm của dữ liệu giao dịch và từng nút không phải là nút lá là 1 giá trị băm của các giá trị băm tức thời trước đó.

Đa phần những Merkle tree là các cây nhị phân, có nghĩa là mỗi nút thân phụ có thể gồm tối đa hai nhánh con. Về mặt kỹ thuật, bạn cũng có thể tăng tăng số nút con của cây lên, và sinh sản thành gần như dạng cây Merkle chưa hẳn dạng nhị phân. Mặc dù trên thực tế cây nhị phân vẫn được sử dụng phổ biến nhất. Cùng với Merkle tree nhị phân yêu cầu số nút lá chẵn. Nếu số lượng giao dịch là số lẻ, hàm băm ở đầu cuối sẽ được nhân đôi một lần để chế tạo số nút chẵn.

Chúng ta trở về ví dụ ở trong phần trên. Khối dữ liệu ở đây chứa bốn thanh toán giao dịch là: L1, L2, L3 cùng L4. Merkle tree khi đó được tạo như sau:

Các giao dịch thanh toán L1, L2, L3, L4 được băm và cực hiếm băm được lưu lại trữ trong những nút lá H 0-0, H 0-1, H 1-0, H 1-1.Các nút lá tiếp nối được nắm tắt vào một nút cha bằng cách băm H 0-0 và H 0-1, tạo ra thành Hash 0 với H 1-0 với H đối chọi tạo thành H 1.Hai cực hiếm băm (Hash 0 với Hash 1) tiếp đến được băm một lần tiếp nữa để tạo thành Hash Root (Merkle Root) là giá bán trị đại diện cho tính trọn vẹn của cục bộ các thanh toán giao dịch bên trong.

Quá trình này diễn ra tương từ bỏ trên các khối tài liệu lớn hơn: các khối liên tiếp có thể được băm cho tới khi chỉ gồm một nút sót lại ở bên trên cùng.

Merkle Root tóm tắt toàn bộ dữ liệu trong những giao dịch tương quan và được lưu trữ trong tiêu đề khối. Nó bảo trì tính trọn vẹn của dữ liệu. Ví như một đưa ra tiết nhỏ nhất trong ngẫu nhiên giao dịch hoặc tất cả sự biến hóa nào đó trong thứ tự giao dịch, thì Merkle Root cũng biến thành thay đổi. Vì thế sử dụng Merkle tree sẽ mang đến phép chúng ta kiểm tra một cách lập cập và đơn giản xem liệu một giao dịch cụ thể có phía bên trong một khối hay không.

Sau khi được xây dựng, cây Merkle hoàn toàn có thể cho phép họ kiểm tra tính trọn vẹn của tài liệu chỉ bằng cách duyệt cây Merkle tự Hash Root với độ tinh vi logarit (quá trình này còn gọi là Bằng bệnh Merkle). Vật chứng Merkle hoạt động bằng cách tạo lại nhánh đựng đoạn tài liệu từ gốc đến đoạn dữ liệu cần phải kiểm chứng. Trong ví dụ như trên, nếu chúng ta muốn kiểm bệnh khối tài liệu L3, bọn họ xuất phát từ Hash root, và yêu cầu được hỗ trợ các quý giá H đối chọi và H0. Họ sẽ băm L3 để lấy giá trị H 1-0, sau đó ghép cùng băm H đối kháng với H 1-0 để chế tạo ra thành H1, kế tiếp ghép với băm công dụng của điều đó với H 0. Nếu tác dụng là cùng một chuỗi với cái giá trị trên Hash root, điều đó tức là L3 thực thụ là một trong những phần của dữ liệu trong Cây Merkle và không xẩy ra thay đổi.

Merkle tree không giống với danh sách băm ở chỗ, cùng với Merkle tree, chúng ta có thể xem xét từng nhánh trên cây tại một thời điểm và vì chưng đó có thể xác minh tính trọn vẹn của từng nhánh tức thì lập tức, trong cả khi không để ý đến phần còn lại của cây. Các tệp hoàn toàn có thể được chia thành các khối tài liệu rất nhỏ, vì vậy chỉ những khối nhỏ tuổi cần được cài xuống lại nhằm xác minh giả dụ phiên phiên bản gốc bị hỏng. Như chúng ta thấy ở ví dụ trên, nhằm xác minh L3, chúng ta chỉ nên biết H 0 và H 1 mà không nên biết các giá trị băm dưới tạo nên nó là gì.

Xem thêm: Bị Bệnh Bướu Cổ Basedow Là Gì, Bệnh Bướu Cổ, Basedow Có Nguy Hiểm Không

Độ tinh vi của Merkle Tree

Chúng ta chu đáo độ tinh vi của một số làm việc cơ bạn dạng đối với kết cấu dữ liệu để xem được lợi thế của Merkle tree về tốc độ:

Thao tácĐộ phức tạp tính toán
Không gian lưu trữO(n)
Tìm kiếmO(logn)
Duyệt câyO(n)
Thêm nútO(logn)
Xóa nútO(logn)
Đồng cỗ hóaO(logn)

trong đó, n là số nút của cây hay số lượng dữ liệu vào khối.

Lợi ích của Merkle Tree

Việc sử dụng cấu tạo Merkle tree rất có thể làm sút đáng nhắc lượng dữ liệu quan trọng phải duy trì cho mục đích xác minh thanh toán giao dịch hoặc chăm chú tính toàn vẹn của từng ngôn từ trong dữ liệu. Cây Merkle hoàn toàn có thể được lưu lại trữ toàn bộ hoặc trên các khối hệ thống phân tán.

Merkle tree bao gồm ba ích lợi chính:

Merkle tree hỗ trợ một phương tiện để chứng tỏ tính toàn vẹn và hòa hợp lệ của dữ liệu. Kết cấu của cây có thể chấp nhận được xác định những biến hóa dù là nhỏ tuổi nhất đối với dữ liệu một giải pháp dễ dàng.Đòi hỏi ít bộ nhớ lưu trữ hoặc dung lượng ổ đĩa vị các vật chứng được tính toán thuận lợi và nhanh chóng. Nếu họ muốn biết sự thay đổi dữ liệu đang xảy ra chỗ nào thì bạn có thể kiểm tra xem tài liệu có cân xứng với Hash Root hay là không và triển khai duyệt cây theo chiều rộng lớn là hoàn toàn có thể xác định được đều vị trí mà dữ liệu bị rứa đổi.Chỉ yêu cầu một lượng nhỏ thông tin được truyền cài qua những mạng.

Cấu trúc của cây chất nhận được biểu diễn hiệu quả lượng tài liệu lớn tùy ý và chất nhận được dễ dàng xác xác định trí xảy ra đổi khác trong tài liệu đó. Điều này chất nhận được bất kỳ ai cũng có thân xác minh rằng câu hỏi băm dữ liệu là đồng nhất và đúng chuẩn mà không cần phải thực sự coi xét cục bộ cây.

Trên các mạng ngang hàng Torrent, khi chúng ta tải xuống một torrent, bạn sẽ nhận được những tệp từ những người dân khác bên trên mạng, tuy nhiên làm cố kỉnh nào bạn có thể chắc chắn rằng những tệp đó thực sự là 1 phần của những gì bạn có nhu cầu tải xuống và chưa hẳn là rác tốt các ứng dụng độc hại? Cây Merkle hoàn toàn có thể xác thực tài liệu nhận được trong trường hòa hợp này.

Tương tự, trong các loại tiền điện tử như Bitcoin cùng Ethereum: trường hợp ai kia tuyên tía rằng trong một số giao dịch làm sao đó, họ nhận được tiền xuất phát từ một ai đó, thì làm thế nào những nút bên trên mạng hoàn toàn có thể xác minh rằng thanh toán giao dịch đó đích thực xảy ra?

Để xác minh điều này, những nút hoàn toàn có thể lưu trữ toàn thể lịch sử của mọi thanh toán đã từng xảy ra. Mặc dù nhiên, mỗi khối chứa hàng nghìn thậm trí hàng vạn giao dịch. Vì vậy sẽ rất lâu để lưu giữ trữ toàn bộ dữ liệu bên trong mỗi khối dưới dạng một chuỗi đầy đủ. Làm vì thế sẽ làm cho cho việc đào bới tìm kiếm kiếm ngẫu nhiên giao dịch cụ thể nào vô cùng to kềnh và tốn thời gian. Cây Merkle cung ứng một phương án giúp ngày tiết kiệm thời hạn và không khí cho những nút trên mạng. Bằng cách tạo Cây Merkle từ dữ liệu giao dịch trong mỗi khối, các giao dịch hoàn toàn có thể được khám nghiệm với độ phức hợp thời gian logarit núm vì thời gian tuyến tính. Ngoại trừ ra, nó góp cho một số trong những nút ngang hàng rất có thể tiết kiệm dung lượng bằng cách chỉ lưu trữ Merkle root mà không cần lưu trữ mọi giao dịch đã từng xảy ra trong định kỳ sử!

Mekle Tree trong Bitcoin

Hàm băm mật mã được áp dụng trong Bitcoin là thuật toán băm SHA-256. Đây là viết tắt của Thuật toán băm bảo mật, có cổng đầu ra là 256 bit vắt định. Tính năng cơ bản của Merkle tree trong Bitcoin là tàng trữ và sau cùng cắt tỉa các giao dịch trong mỗi khối.

Như đã đề cập trước đó, các khối trong một blockchain được kết nối với nhau trải qua các cực hiếm băm của khối trước đó. Vào Bitcoin, mỗi khối chứa toàn bộ các thanh toán giao dịch trong khối đó cũng giống như tiêu đề khối bao gồm:

Số phiên phiên bản khốiGiá trị băm của khối trướcDấu thời hạn (time stamp)Độ cực nhọc của kim chỉ nam dùng trong quá trình khai thácGiá trị tự nhiên Nonce là giải thuật của vấn đề Proof of WorkMerkle Root

Hình ảnh dưới phía trên được đem từ whitepaper của Bitcoin với minh họa kết cấu Merkle tree cùng với từng khối.

*

Các thanh toán giao dịch được thêm vào trong các khối bởi các thợ mỏ cùng được băm như một trong những phần của Merkle tree, ở đầu cuối các quý giá băm này được xây đắp thành cây Merkle hoàn hảo với Merkle root được tàng trữ trong title khối. Kiến tạo này tạo nên một số công dụng riêng biệt.

Đầu tiên, nó cho phép tồn tại những nút Xác minh thanh toán đơn giản và dễ dàng (SPV), còn gọi là các vận dụng khách hạng nhẹ. Các nút này chưa phải tải xuống cục bộ blockchain Bitcoin, mà chỉ cần tải về những tiêu đề khối của chuỗi dài nhất. Điều này giúp tiết kiệm ngân sách và chi phí đáng kể quy trình xác thực và tàng trữ blockchain bởi khối lượng dữ liệu của blockchain được xem với cuối tháng 8 năm 2017 sẽ là 130GB. Các nút SPV đang truy vấn đến những nút cùng cấp của chúng cho tới khi xác minh được rằng các tiêu đề khối được lưu trữ mà bọn chúng đang vận động là một trong những phần của chuỗi dài nhất. Sau đó, một nút SPV rất có thể xác định tinh thần của giao dịch bằng cách sử dụng minh chứng Merkle nhằm ánh xạ thanh toán đến một cây Merkle rõ ràng với Merkle root khớp ứng trong tiêu đề khối là một trong những phần của chuỗi dài nhất.

Ngoài ra, cây Merkle vào Bitcoin còn có thể chấp nhận được cắt xén chuỗi khối để tiết kiệm không khí lưu trữ. Điều này là vì chỉ tất cả hash root được tàng trữ trong tiêu đề khối, vị đó, những khối cũ hoàn toàn có thể được giảm tỉa bằng phương pháp loại bỏ các nhánh không cần thiết của cây Merkle trong những khi chỉ giữ lại đầy đủ thứ cần thiết cho minh chứng Merkle.

Các áp dụng khác của Merkle tree

Mặc cho dù Bitcoin là blockchain đầu tiên triển khai cây Merkle, nhưng nhiều blockchain khác cũng có thể có các kết cấu cây Merkle tựa như hoặc những phiên bạn dạng thậm chí phức tạp hơn. Hơn nữa, ứng dụng của cây Merkle không chỉ là giới hạn ở các chuỗi khối hơn nữa được áp dụng cho nhiều khối hệ thống khác.

Ethereum, là các loại tiền điện tử phổ cập khác, cũng sử dụng Merkle tree nhằm tăng hiệu quả xác nhận giao dịch. Do Ethereum được thành lập như một căn cơ để triển khai những ứng dụng phức tạp hơn nhiều, do vậy nó áp dụng một phiên phiên bản phức tạp rộng của cây Merkle có tên là Merkle Patricia Tree. Cấu trúc này thực ra là sự kết hợp của 3 cây Merkle đơn lẻ được sử dụng cho bố loại đối tượng người tiêu dùng khác nhau trong những nền tảng Ethereum. Từng khối bao gồm ba Merkle root đặc trưng tương ứng mang đến 3 cây con khác biệt này:

stateRoot: đại diện thay mặt cho trạng thái của khối, được cập nhật theo thời gian.ReceiptsRoot: chứa các biên lai giao dịch thanh toán trong khối.Transaction Root chứa toàn bộ các giao dịch.

Ngoài ra StorageRoot chứa toàn thể các tài liệu về hợp đồng. Mỗi tài khoản có một cây lưu trữ storage riêng biệt biệt.

Cây Merkle là công cụ mạnh khỏe và luôn luôn phải có trên blockchain. Chúng cực kỳ mạnh mẽ và là trung trung tâm của một trong những mạng đồng cấp như BitTorrent, Git, Bitcoin cùng Ethereum.

Nó còn là một thành phần đặc trưng của những hệ thống kiểm soát phiên bản phân tán như Git và Mercurial; xuất xắc các hệ thống tệp tin như IPFS, Btrfs và ZFS giúp đảm bảo an toàn tính trọn vẹn và chống mất đuối sửa đổi tài liệu cho các khối hệ thống này. Bởi vì tính thuận lợi trong việc áp dụng để bảo vệ và xác minh tính toàn diện của dữ liệu được chia sẻ giữa các máy tính ở format P2P khiến cho chúng trở đề nghị vô giá so với các hệ thống này. Nó được áp dụng trong Giao thức Dat; Giao thức Apache Wave; hệ thống dự trữ Tahoe-LAFS; Zeronet; cùng một số hệ thống NoQuery như Apache Cassandra, Riak và Dynamo DB.

Ngoài blockchain và torrent, Merkle Tree còn hoàn toàn có thể sử dụng trong ngẫu nhiên hệ thống nào nên phát hiện tại sự không đồng hóa về dữ liệu một cách công dụng chẳng hạn như:

Cơ quan cấp chứng từ (CA) thực hiện Cây Merkle làm phương tiện để minh bạch bệnh chỉ. Ở đây, những cặp khóa công khai và khóa riêng rẽ được coi là lá của Merkle tree. Đây là một trong những cơ chế mà CA áp dụng để ngăn chặn các tình huống trong đó một CA hoàn toàn có thể đi lừa đảo và chiếm đoạt tài sản và nỗ lực chứng dìm một tên miền mà không hẳn là chủ download của tên miền đó.Chữ ký kết số sửa chữa cho RSA. Trong trường thích hợp này, nơi bắt đầu của Cây Merkle hoạt động như một khóa phổ biến và các nút biệt lập được áp dụng làm chữ ký một lần. Sát đây, một trong những nghiên cứu vãn khác sẽ được tiến hành để cách tân các chuyên môn này vị nó được chứng tỏ lý thuyết là bao gồm tiềm năng chống lại những cuộc tấn công dựa trên các thuật toán thám mã lượng tử (không hệt như RSA).

Xem thêm: Cách Tải Ch Play Cho Huawei Bị Mất Ch Play? Cách Tải Ch Play Cho Huawei Không Cần Máy Tính

Kết luận

Cây Merkle là 1 thành phần luôn luôn phải có của blockchain. Merkle tree có thể chấp nhận được blockchain chuyển động hiệu quả trong việc bảo đảm tính không bao giờ thay đổi và minh chứng tính toàn diện của giao dịch. Gọi được phương châm của chúng trong những mạng phân tán và công nghệ cơ phiên bản của những hàm băm mật mã là rất đặc biệt để nắm bắt các tư tưởng cơ bản trong tiền năng lượng điện tử tốt blockchain. Bây giờ các kiến trúc cây Merkle vẫn đang tiếp tục được cải cách và phát triển thành các hệ thống lớn rộng và tinh vi hơn, tương tự như được ứng dụng nhiều hơn trong các hệ thống blockchain trong thực tế.