LearnBN on Nostr: Merkle Tree Merkle Tree เป็น hash-based data structure ...
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))) ดังรูปที่แสดงข้างล่างนี้
เมื่อเราใช้ Merkle Tree มาช่วยจัดการการตรวจสอบธุรกรรมบนบิตคอยน์ ทำให้เราไม่จำเป็นต้องตรวจสอบทุกธุรกรรมในบล๊อก เนื่องจากเราสามารถเช็คเพียงแค่ root hash ว่าตรงกับคนอื่นมั้ย ถ้าตรงก็แปลว่าข้อมูลที่เรารับมาถูกต้อง ในทางกลับกันหากไม่ตรงเราสามารถไล่เช็คตามลำดับของ tree เพื่อตามหาธุรกรรมเจ้าปัญหาได้ง่ายกว่าการไล่เช็คทั้งหมด การนำ merkle tree มาใช้ช่วยให้ การตรวจสอบบล๊อกนั้นทำได้ง่ายขึ้นและใช้พื้นที่ในการเก็บข้อมูลน้อยลง
#siamstr
Published at
2024-07-14 04:34:05Event JSON
{
"id": "a0665a91a846a4fb901b447c0f62ad049ab136b09f9d25d8976e0ebb0f61c2ea",
"pubkey": "79008e781adec767cc8e239b533edcb19ea2e260f9281a9125e93425dfac9395",
"created_at": 1720924445,
"kind": 1,
"tags": [
[
"t",
"siamstr"
]
],
"content": "Merkle Tree\n\nMerkle Tree เป็น hash-based data structure เหมือนกับ binary tree แต่แตกต่างกันตรงที่ leaf node จะทำการเก็บเพียงแค่ค่า hash ของข้อมูลธุรกรรม ส่วน node ที่ไม่ใช่ leaf node จะเก็บค่าจากการ hash ที่ได้จาก children node หากจะให้เห็นภาพมากขึ้นลองมาดูตัวอย่างตามนี้กันครับ\nสมมุติให้มี transaction ทั้งหมด 4 transaction: t1, t2, t3, t4 ก็แปลว่า hash ของทั้ง 4 transaction ก็จะเป็น leaf node ดังนี้\nH(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))) ดังรูปที่แสดงข้างล่างนี้\n https://image.nostr.build/fc973bc4a3c9dd9330fdd754461ac0f45c6cf031509a0815ddba10764a9588fd.png\n\nเมื่อเราใช้ Merkle Tree มาช่วยจัดการการตรวจสอบธุรกรรมบนบิตคอยน์ ทำให้เราไม่จำเป็นต้องตรวจสอบทุกธุรกรรมในบล๊อก เนื่องจากเราสามารถเช็คเพียงแค่ root hash ว่าตรงกับคนอื่นมั้ย ถ้าตรงก็แปลว่าข้อมูลที่เรารับมาถูกต้อง ในทางกลับกันหากไม่ตรงเราสามารถไล่เช็คตามลำดับของ tree เพื่อตามหาธุรกรรมเจ้าปัญหาได้ง่ายกว่าการไล่เช็คทั้งหมด การนำ merkle tree มาใช้ช่วยให้ การตรวจสอบบล๊อกนั้นทำได้ง่ายขึ้นและใช้พื้นที่ในการเก็บข้อมูลน้อยลง\n\n#siamstr",
"sig": "d3adace34eb54cb8332eceb794d222fde40ab2d8ee71117472f01c041bf7f0b2ffda986329c192ab886e49b985cbf9bc8dc1d01eacea7068706302f8e00addc1"
}