ต้นไม้ Merkle: ความถูกต้องของธุรกรรมในระดับใหญ่

บล็อกบิตคอยน์หนึ่งบล็อกมีธุรกรรมประมาณ 2,000 รายการ หากต้องการพิสูจน์ว่าธุรกรรม T ถูกรวมอยู่ในบล็อกโดยไม่ดาวน์โหลดธุรกรรมทั้ง 2,000 รายการ เราจำเป็นต้องมีหลักฐานขนาดกะทัดรัด ต้นไม้เมอร์เคิลช่วยแก้ปัญหานี้ โดยหลักฐานมีขนาด O(log n) แฮช แทนที่จะเป็นธุรกรรม O(n) รายการ

ใบ: SHA256d (SHA-256 สองรอบ) ของแต่ละธุรกรรม โหนดแม่: SHA256d(left_child_hash || right_child_hash) ทำซ้ำจนเหลือแฮชรากเพียงหนึ่งค่า หากมีโหนดเป็นจำนวนคี่ ให้ทำสำเนาโหนดสุดท้าย รากนี้คือรากเมอร์เคิลที่จัดเก็บไว้ในส่วนหัวบล็อก (32 ไบต์)

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

เพื่อพิสูจน์ว่าธุรกรรม T อยู่ที่ตำแหน่ง i ให้ส่งแฮชของโหนดพี่น้องในแต่ละระดับ ตั้งแต่ใบของ T ไปจนถึงราก (แฮช O(log n) ค่า) ผู้ตรวจสอบจะคำนวณรากใหม่จาก T และเส้นทางของโหนดพี่น้อง หากรากที่คำนวณได้ตรงกับรากเมอร์เคิลในส่วนหัวบล็อก ก็พิสูจน์ได้ว่า T ถูกรวมอยู่ในบล็อก

ธุรกรรม 1024 รายการ → หลักฐานเมอร์เคิล = 10 แฮช = 320 ไบต์ บล็อกเต็ม = ~1 MB ไคลเอ็นต์ SPV ดาวน์โหลดเฉพาะส่วนหัวขนาด 80 ไบต์และหลักฐานเมอร์เคิลขนาด 320 ไบต์สำหรับธุรกรรมที่ต้องการตรวจสอบแต่ละรายการ ซึ่งประหยัดแบนด์วิดท์ได้ 99.97% เมื่อเทียบกับการดาวน์โหลดบล็อกเต็ม

หากธุรกรรมใดในต้นไม้เปลี่ยนแปลง แฮชของใบนั้นจะเปลี่ยนและส่งผลต่อเนื่องขึ้นไปจนทำให้รากเมอร์เคิลเปลี่ยนไปด้วย รากที่ถูกแก้ไขจะไม่ตรงกับส่วนหัวบล็อก ซึ่งมีการผนึกด้วยการพิสูจน์การทำงาน การแก้ไขใดก็ตามจึงตรวจพบได้ด้วยการคำนวณรากจากธุรกรรม

อีเธอเรียมขยายต้นไม้เมอร์เคิลด้วยไทร (ไทรเมอร์เคิลแบบ Patricia): ไทรฐานรากที่เข้ารหัสด้วยคำนำหน้าเลขฐานสิบหก โดยแต่ละโหนดถูกแฮชด้วยเมอร์เคิล ใช้สำหรับ: ไทรสถานะ (ยอดคงเหลือของบัญชี) ไทธุรกรรม และไทรใบเสร็จรับเงิน ช่วยให้พิสูจน์สถานะบัญชีได้อย่างมีประสิทธิภาพโดยไม่ต้องมีข้อมูลจากโหนดเต็มรูปแบบ

โครงสร้างภูเขาเมอร์เคิล (MMR) คือโครงสร้างเมอร์เคิลแบบเพิ่มข้อมูลได้อย่างเดียวสำหรับข้อมูลลักษณะบันทึก รายการใหม่จะถูกเพิ่มต่อท้าย และจะรักษายอดเขาไว้ ซึ่งเป็นรากของต้นไม้ย่อยที่มีขนาดเป็นกำลังของ 2 โครงสร้างนี้ใช้ใน Grin/MimbleWimble และ ZCash เพื่อสร้างหลักฐานขนาดกะทัดรัดที่มีประสิทธิภาพสำหรับบันทึกแบบเพิ่มข้อมูลได้อย่างเดียว

ต้นไม้ Verkle จะเข้ามาแทนต้นไม้เมอร์เคิลในแผนงานของอีเธอเรียม (EIP-6800) โดยใช้การผูกมัดเวกเตอร์ (การผูกมัดพหุนาม KZG) แทนแฮช ขนาดหลักฐานคือ O(1) เทียบกับ O(log n) สำหรับต้นไม้เมอร์เคิล ทำให้ไคลเอ็นต์ไร้สถานะสามารถตรวจสอบสถานะได้โดยไม่ต้องจัดเก็บไทรทั้งหมด

ความโปร่งใสของใบรับรอง (RFC 6962) ใช้บันทึกเมอร์เคิลแบบเพิ่มข้อมูลได้อย่างเดียว โดยใบรับรองแต่ละใบที่ CA ออกให้เป็นใบหนึ่งรายการ หลักฐานการรวมอยู่ใช้ตรวจสอบว่าใบรับรองถูกบันทึกแล้ว ส่วนหลักฐานความสอดคล้องใช้ตรวจสอบว่าบันทึกเพิ่มข้อมูลได้อย่างเดียวจริง ไม่มีการลบหรือแทรกข้อมูล ผู้ให้บริการเบราว์เซอร์ตรวจสอบ SCT ผ่านบันทึกนี้

ต้นไม้ของ Git (ภาพสถานะไดเรกทอรี) คือต้นไม้เมอร์เคิล โดยแต่ละโหนดต้นไม้จะแฮชข้อมูลไบนารีของไฟล์และต้นไม้ย่อย แฮชคอมมิตจะระบุสถานะของฐานโค้ดทั้งหมดได้อย่างไม่ซ้ำกัน นี่คือเหตุผลที่ git checkout ให้ไฟล์ชุดเดิมทุกครั้ง

หลักฐานเมอร์เคิลต้องใช้กี่แฮชเพื่อพิสูจน์การรวมอยู่ในต้นไม้ที่มีใบ 1024 ใบ

ต้นไม้เมอร์เคิลช่วยให้สร้างหลักฐานการรวมอยู่ขนาด O(log n) บิตคอยน์จัดเก็บรากเมอร์เคิลไว้ในส่วนหัวบล็อก และไคลเอ็นต์ SPV ใช้หลักฐานเหล่านี้ อีเธอเรียมขยายแนวคิดนี้เป็นไทรเมอร์เคิลแบบ Patricia ต้นไม้ Verkle จะเข้ามาแทนต้นไม้เมอร์เคิลเพื่อให้ได้หลักฐานขนาด O(1) บทถัดไป: การขุดด้วยการพิสูจน์การทำงานและความยาก