Merkle tree là gì

Việc xúc tiến Merkle Tree vào blockchain có khá nhiều hiệu ứng. Nó được cho phép blockchain mở rộng quy tế bào đồng thời hỗ trợ kiến ​​trúc dựa vào hàm băm để gia hạn tính toàn diện dữ liệu với một cách thông thường để xác minh tính toàn diện của dữ liệu. Hàm băm mã hóa là công nghệ cơ phiên bản cho phép Merkle Tree hoạt động, vì chưng vậy trước tiên, điều đặc trưng là bắt buộc hiểu hàm băm mã hóa là gì.

Hàm băm mã hóa

Hàm băm (hash) là ngẫu nhiên hàm như thế nào được thực hiện để ánh xạ tài liệu có size tùy ý (đầu vào) thành đầu ra có size cố định. Một thuật toán băm được vận dụng cho đầu vào tài liệu và kết quả đầu ra gồm độ dài cố định và thắt chặt được điện thoại tư vấn là hàm băm. Nhiều thuật toán băm được công khai minh bạch rộng rãi và hoàn toàn có thể được chọn lựa dựa trên nhu yếu của bạn.

Kết trái băm từ đầu vào tùy ý không chỉ cố định về chiều dài, nó cũng trọn vẹn duy nhất. Nghĩa là, mặc dù bạn gồm chạy hàm trên cùng một nguồn vào bao nhiêu lần thì đầu ra output sẽ luôn giống nhau. Ví dụ, nếu như bạn có những bộ dữ liệu sau đây làm đầu vào, thì tác dụng đầu ra là duy nhất cho từng đầu vào. Xem xét trong những ví dụ sản phẩm công nghệ hai và thứ ba, tuy nhiên sự biệt lập của những đầu vào chỉ là 1 từ, các công dụng đầu ra hoàn toàn khác nhau. Điều này rất đặc biệt vì nó được cho phép “lưu lốt vân tay” (“fingerprinting”) của dữ liệu.

Hàm băm mã hóa

Merkle Tree & Merkle Root

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

Ý tưởng của Merkle, hiện nay được biết đến với thương hiệu Merkle Tree, đã phương pháp mạng hóa quả đât mã hóa bằng cách mở rộng phương thức mà giao thức máy tính mã hóa hoạt động. Bên 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ắt giới. Chúng cũng khá được sử dụng rộng rãi trong mã Bitcoin.

Vậy, Merkle Tree là gì? gọi một cách đối chọi giản, Merkle Tree là một cách thức cấu trúc dữ liệu cho phép một cân nặng lớn tin tức được xác minh tính đúng mực cực kỳ mau lẹ và hiệu quả.

Bây tiếng ta xem xét nó bên trên blockchain. Đầu tiên, điều đặc trưng cần chú ý là mỗi thanh toán trên một blockchain gồm ID giao dịch thanh toán là duy nhất. Với phần đông các blockchain, mỗi ID giao dịch là 1 mã 64 cam kết tự chiếm phần 256 bit (32 byte) cỗ nhớ.

Các blockchain thường được sinh sản thành từ hàng nghìn nghìn khối, mỗi khối chứa tới vài nghìn giao dịch, chúng ta có thể tưởng tượng không gian bộ lưu trữ trở thành vấn đề như vậy nào. Vị đó, nó tối ưu hóa để thực hiện càng ít dữ liệu càng tốt khi xử trí và xác minh giao dịch. Điều này giảm thiểu thời hạn xử lý CPU đồng thời đảm bảo mức độ bảo mật cao nhất.

Đó đúng là những gì Merkle Tree làm. Một cách đơn giản, Merkle Tree lấy một vài lượng khủng ID thanh toán và chuyển chúng sang 1 quy trình toán học dẫn cho một mã 64 cam kết tự.

Mã này cực kỳ quan trọng vày nó đến phép bất kỳ máy tính nào nhanh chóng xác minh rằng một giao dịch xác định đã diễn ra trên một khối cụ thể một cách công dụng nhất tất cả thể. Mã này được gọi là Merkle Root (Rễ Merkle).

Mã duy nhất mà Merkle Tree tạo thành được điện thoại tư vấn là Merkle Root. Từng khối vào một blockchain gồm duy nhất có một Merkle Root. Merkle Root là một phần dữ liệu quan trọng vì nó chất nhận được các laptop xác minh tin tức với vận tốc và kết quả đáng tởm ngạc.

Tìm đọc sâu hơn một chút để gọi Merkle Root được tạo ra ra như thế nào? Bước trước tiên là tổ chức tất cả các tài liệu đầu vào.

Merkle Tree, theo thiết kế, luôn nhóm toàn bộ các nguồn vào thành cặp. Ví như có một trong những lượng nguồn vào lẻ, đầu vào cuối cùng được xào nấu và kế tiếp được ghép nối với thiết yếu nó. Điều này đúng với toàn bộ các ID thanh toán giao dịch được viết bên trên một khối của blockchain.

Chẳng hạn, mang sử rằng một khối duy nhất cất tổng số 512 giao dịch. Merkle Tree sẽ ban đầu bằng biện pháp nhóm 512 ID thanh toán đó thành 256 cặp. Sau đó, 256 cặp ID thanh toán giao dịch đó đang trải qua 1 quá trình toán học, được hotline là băm hoặc thuật toán băm, sẽ khởi tạo ra 256 mã chữ với số 64 ký tự mới.

Quá trình đúng chuẩn tương trường đoản cú sẽ xẩy ra một lần nữa. 256 mã bắt đầu đó sẽ tiến hành ghép nối và trở thành 128 mã. Quá trình sẽ được lặp lại, cắt sút một nửa số mã mỗi lần, cho đến khi chỉ với lại một mã. Mã duy nhất chính là Merkle Root (Merkle Root).

Một lấy ví dụ về Merkle Tree

Để hình dung khái niệm này rõ ràng, họ hãy nhìn vào một ví dụ rất dễ dàng và đơn giản về Merkle Tree. Hãy tưởng tượng rằng bao gồm 8 thanh toán giao dịch được triển khai trên một khối cụ thể với 8 ID không giống nhau. Trên thực tế, ID giao dịch thanh toán dài 64 ký kết tự (bao có số với chữ), nhưng mà để đối chọi giản, hãy nhận định rằng chúng chỉ nhiều năm 8 ký kết tự. Để việc phân tích và lý giải trở nên đơn giản dễ dàng hơn, ta chỉ sử dụng các số (và quăng quật qua các chữ cái).

Vì vậy, trong lấy một ví dụ này, tám ID thanh toán giao dịch của họ sẽ là:

Merkle Tree của chúng ta sẽ trông y hệt như sau:

Rừng Merkle

Bây giờ, giả sử phương thức để băm ID giao dịch là lấy các chữ số đầu tiên, thiết bị ba, thứ năm và thứ bảy trường đoản cú mỗi nhị ID được kết hợp, sau đó chỉ việc ghép những số đó lại với nhau để chế tạo ra thành một mã bắt đầu 8 chữ số.

Tất nhiên, trong thực tế, toán học tập đằng sau những thuật toán băm phức tạp hơn các so với điều này. Nhưng đối với giải thích dễ dàng và đơn giản này, hệ thống cơ phiên bản này là đủ.

Hiệu quả với tốc độ: những lợi ích của Merkle Tree

Giả sử rằng họ muốn tuyệt đối ID thanh toán giao dịch trong ví dụ hiện tại tại. Bob bảo rằng anh ta đang trả mang lại Alice một khoản Bitcoin nhất mực và nói với chúng ta rằng ID thanh toán là 88888888. Anh ta cũng gởi cho bọn họ 3 băm: 77777777, 55556666 với 11223344. Đó là tất cả thông tin cần phải gửi hoặc dìm để xác minh giao dịch của Bob cho Alice.

Ba quý giá băm này, cùng rất ID thanh toán giao dịch được nhắc (Merkle Root của khối ví dụ này) đó là dữ liệu chỉ việc để xác minh giao dịch thanh toán Bob cho Alice. Đây là dữ liệu thấp hơn nhiều so với đầy đủ gì sẽ được yêu cầu để xác minh toàn thể Merkle Tree. Bởi vì đó, quy trình xác minh cấp tốc hơn và hiệu quả hơn nhiều so với mọi người.

Xem xét giải pháp thức buổi giao lưu của nó. Chúng ta đã gồm khối Merkle Root, vì vậy Bob không cần phải gửi cho chúng ta thông tin đó. Anh ấy giữ hộ cho chúng ta ID thanh toán của anh ấy cùng 3 băm bổ sung cập nhật mà họ đã liệt kê ngơi nghỉ trên. Anh ta cũng gởi một chút thông tin về vật dụng tự và vị trí để sử dụng băm. Bây giờ, toàn bộ những gì bọn họ phải có tác dụng là chạy thuật toán băm bên trên tập tài liệu mà Bob cung cấp.

Xác thực giao dịch thanh toán của Bob và Alice

Chúng ta bước đầu bằng giải pháp băm mã thứ nhất 77777777 cùng với ID giao dịch 88888888, cho họ kết quả 77778888. Bob đã không gửi cho chúng ta mã này (77778888) mà lại không phải thiết cũng chính vì chúng ta thực hiện thuật toán băm y hệt như anh ấy. Vị đó, bọn họ nhận được kết quả đúng chuẩn như nhau.

Sau đó, chúng ta lấy mã lắp thêm hai cơ mà Bob vẫn gửi cho việc đó ta, 55556666 với băm nó với mã new 77778888 mà chúng ta vừa dìm được. Điều này, tất nhiên, tạo nên số 55667788.

Cuối cùng, chúng ta băm mã thứ ba mà Bob đã cung cấp cho chúng ta, 11223344, với mã new khác mà chúng ta đã dấn được, 55667788, và họ kết thúc với Merkle Root thiết yếu xác: 12345678.

Lưu ý rằng bọn họ chỉ đề xuất 3 mã từ Bob với chỉ đề nghị chạy thuật toán băm ba lần để xem rằng giao dịch Bob là hòa hợp lệ. Điều đó có nghĩa là máy tính của bọn họ đã triển khai chưa mang lại một nửa công việc được yêu mong để xác minh toàn bộ Merkle Tree. Sơ đồ Merkle Tree ban sơ có 15 số với thuật toán băm cần được chạy 7 lần. Nhưng hơn một phần số cây kia không quan trọng để xác minh giao dịch thanh toán của Bob!

Quy trình này đủ nhằm xác minh rằng bên trên thực tế, Bob đã trả đến Alice số chi phí Bitcoin nhất mực vì chúng ta đã mang được các số mà khi được băm thuộc với các mã không giống Bob vẫn gửi cho cái đó ta, đã tạo ra cùng một Merkle Root mà bọn họ đã biết là đúng khối đặc trưng này.

Bob rất có thể giả mạo một thanh toán giao dịch vì điều ấy sẽ yêu mong tìm ID thanh toán giả và một cỗ mã giả ngã sung, khi được chuyển vào chức năng băm, sẽ khởi tạo ra Merkle Root thực sự. Cơ hội của việc này xẩy ra rất nhỏ dại đến mức chúng ta cũng có thể tự tin nói rằng điều đó là ko thể.

Trong ví dụ dễ dàng này, sự tiết kiệm chi phí sức mạnh thống kê giám sát có vẻ không xứng đáng kể. Mặc dù nhiên, khi bạn xem xét các khối vào một blockchain rất có thể chứa vài nghìn giao dịch, thật thuận lợi để thấy Merkle Tree tăng tác dụng đáng kể như thế nào.

Xem thêm: Tổng Hợp Tìm M Để Hàm Số Có Cực Đại Cực Tiểu Thỏa Điều Kiện, Tìm M Để Hàm Số Có Cực Đại Và Cực Tiểu

Nói bắt lại, đó là tác dụng chính của Merkle Tree. Nó có thể chấp nhận được các máy vi tính xác minh tin tức cực kỳ tác dụng với dữ liệu thấp hơn nhiều so với các gì được yêu ước nếu không có Merkle Tree.