Merkle Patricia Tree
tree ที่ proof เร็วกว่า และ insert เร็วกว่า merkle binary tree
ก่อนจะไปดู Merkle Paricia Tree มาดู Trie กันก่อน
โดย Trie คือ data structure รูปแบบ key value ที่จะเก็บ prefix ของ key ที่ซ้ำกัน ไว้ใน node เดียวกัน ตามภาพ
เช่น
to = 7
tea = 3
โดยถ้าเราเอา trie มาผสมกับ Merkle tree จะกลายเป็น Merkle Patricia Tree
โดยจะหน้าตาประมาณนี้
จากรูป จะเป็นการเก็บข้อมูล key value 4 record ในรูปแบบที่อิงจาก trie
แต่ตอนนี้เราสามารถใช้ตัว root ของ tree ในการทำ merkle proof ได้ด้วย
โดยวิธีการอ่านรูปนี้ให้ออกมาเป็น record คือ
leaf node = node ที่เก็บ value
extension node = node ที่เก็บ prefix ของ key ที่ซ้ำกัน
branch node = node ที่ใช้เป็นทางแยก prefix ของ key โดยจะต่อจาก extension node
nibble = key ที่ node นั้นๆ
โดยการใช้ Merkle Patricia Tree แบบนี้ มีข้อที่ได้เปรียบ Merkle binary tree คือ
- การ insert ข้อมูลทำได้เร็วกว่า
เพราะไม่ต้อง hash parent node เพื่อไปเชื่อมกับ root node เหมือน merkle binary tree แต่สามารถเอา node ใหม่มาต่อในชั้นล่างๆได้เลย
โดยเข้าใจว่าเมื่อก่อน ethereum ใช้ merkle binary tree ในการเก็บ proof ของ state ซึ่งไม่เหมาะ เพราะ state มีการเปลี่ยนรัวๆ และ การเปลี่ยน state ไม่ได้ขึ้นกับ order tx เสมอไป (merkle binary tree ถ้าไม่ได้ sort leaf … order ของ leaf จะมีผลกับค่า root)
แต่เข้าใจว่า ต่อมา ethereum node เปลี่ยนมาใช้ Merkle Patricia Tree เก็บ state แทน
แต่ก็ไม่มั่นใจว่าตอนนี้เปลี่ยนมาเป็น verkle tree แล้วยังนะ
2. การ proof ทำได้เร็วกว่า
เพราะ tree จะมีขนาดเตี้ยลง เมื่อเทียบกับ merkle binary tree ตามรูป นี่ทำให้การ proof มี hash step ที่น้อยลง ทำให้เร็วขึ้น
นอกจากนี้ Merkle Patricia Tree ยังคงคุณสมบัติในการป้องกันการ spam ชั้น tree ได้
ถ้าเรามาเทียบกับ trie ธรรมดา เราจะพบว่า ถ้า prefix ไม่ซ้ำกันเลยเราสามารถสร้าง tree ที่สูงมากๆได้
แต่พอเป็น Merkle Patricia Tree แล้ว การทำแบบนี้จะได้ tree ที่เตี้ย เพราะ leaf node สามารถเก็บ key ยาวๆได้แล้วนั่นเอง
