Merkle Tree

Merkle Tree เป็น hash-based data structure เหมือนกับ binary tree แต่แตกต่างกันตรงที่ leaf node จะทำการเก็บเพียงแค่ค่า hash ของข้อมูลธุรกรรม ส่วน node ที่ไม่ใช่ leaf node จะเก็บค่าจากการ hash ที่ได้จาก children node หากจะให้เห็นภาพมากขึ้นลองมาดูตัวอย่างตามนี้กันครับ
สมมุติให้มี transaction ทั้งหมด 4 transaction: t1, t2, t3, t4 ก็แปลว่า hash ของทั้ง 4 transaction ก็จะเป็น leaf node ดังนี้
H(1), H(2), H(3), H(4) และเนื่องจาก 1 node จะมี 2 children แปลว่า ก็จำเป็นต้องมี 2 node ที่เก็บ hash ของ H(1), H(2), H(3), H(4) ดังนั้นในชั้นที่ 2 ของ tree แต่ละ node จะต้องเก็บข้อมูลเป็น H(H(1)+H(2)), และ H(H(3)+H(4)) ตามลำดับ และดังที่กล่าวไว้ข้างต้น เนื่องจาก 1 node จะมี 2 children แปลว่า ก็จำเป็นต้องมี 1 node ที่เก็บค่า H(H(H(1)+H(2)) + H(H(3)+H(4))) ดังรูปที่แสดงข้างล่างนี้
 https://image.nostr.build/fc973bc4a3c9dd9330fdd754461ac0f45c6cf031509a0815ddba10764a9588fd.png

เมื่อเราใช้ Merkle Tree มาช่วยจัดการการตรวจสอบธุรกรรมบนบิตคอยน์ ทำให้เราไม่จำเป็นต้องตรวจสอบทุกธุรกรรมในบล๊อก เนื่องจากเราสามารถเช็คเพียงแค่ root hash ว่าตรงกับคนอื่นมั้ย ถ้าตรงก็แปลว่าข้อมูลที่เรารับมาถูกต้อง ในทางกลับกันหากไม่ตรงเราสามารถไล่เช็คตามลำดับของ tree เพื่อตามหาธุรกรรมเจ้าปัญหาได้ง่ายกว่าการไล่เช็คทั้งหมด การนำ merkle tree มาใช้ช่วยให้ การตรวจสอบบล๊อกนั้นทำได้ง่ายขึ้นและใช้พื้นที่ในการเก็บข้อมูลน้อยลง

#siamstr