เรารู้จัก Tree Structure ในเรื่องของการทำ Data Structure เป็นอย่างดี การจัดเก็บข้อมูลในรูปแบบของ Tree ในรูปแบบต่างๆ ยกตัวอย่างเช่น Binary Search Tree ช่วยให้เราสามารถเข้าถึงข้อมูลได้อย่างรวดเร็วกว่าการทำ Linear Search เป็นหลายเท่าตัวเมื่อจำนวน n หรือจำนวนข้อมูลของเราเพิ่มมากขึ้น

ในโลกของ Blockchain อย่างเช่น Bitcoin และ Ethereum ก็มีปัญหาซึ่งในปัจจุบันถูกแก้ไขด้วยการใช้ Tree Data Structure เข้ามาช่วยเหลือ โดยปัญหานั้นเกิดมาจาก Transaction ในแต่ล่ะ Block

แล้วปัญหามันอยู่ตรงไหนล่ะ

อย่างที่เรารู้กันดีอยู่แล้วว่า ระบบ Blockchain มีการจัดเก็บข้อมูล Transaction จำนวนหลาย ๆ Transaction ลงใน Block และแต่ล่ะ Block ก็จะมี Hash เป็นของตัวเอง รวมไปถึง Hash ของ Block ก่อนหน้า เพื่อสร้างการอ้างอิงถึง Block ก่อนหน้าตัวเอง และเมื่อระบบมีการสร้าง Block ใหม่เพิ่มขึ้นมาเรื่อย ๆ โดยมาการอ้างอิง Block ก่อนหน้าในทุก ๆ Block ก็จะเปิดการเชื่อมต่อกันเป็นลูกโซ่หรือ Chain ของ Block ขึ้นมา

ปัญหาของการเก็บข้อมูลจึงเกิดขึ้น เนื่องจากการที่ 1 Node ใน Blockchain จะมีข้อมูลของ Block และ Transaction ทั้งหมดนั้น มันเป็นไปได้ยากมาก เนื่องด้วยจำนวน Block และ Transaction ใน Block ที่เพิ่มขึ้นเรื่อย ๆ ย่อมมีขนาดที่มากเกินกว่าที่เก็บข้อมูลจะรับไหว รวมไปถึงการตรวจสอบ Block ใหม่ ก็ทำได้ยากด้วยเช่นกัน เพราะว่าการจะตรวจสอบ Transaction ในแต่ล่ะ Block ที่มีจำนวนกว่า 2,000 Transaction ใน 1 Block ย่อมใช้เวลาและเปลืองทรัพยากร

Merkle Tree is the way

Merkle Tree เป็น Hash-Based Data Structure โดยปกติแล้ว แต่ล่ะ Node จะประกอบไปด้วยอย่างมาก 2 Children ซึ่งคล้ายกับ Binary Tree โดย Merkle Tree จะมีลักษณะดังนี้

Leaf Node จะเก็บค่า Hash ของข้อมูลหรือ Transaction
Non-Leaf Node จะเก็บค่าที่ได้จากการ Hash ตัว children node

จากรูปเราจะเห็นได้ว่า Transaction (L1, L2, L3, L4) จะมีค่า Hash เป็นของตนเอง (Hash 0-0, Hash 0-1, ...) และค่า Hash เหล่านั้นถูกประกอบเข้ามาเป็น Tree ซึ่ง Parent Node จะเก็บค่าจากการ Hash ตัว Children Node อีกที โดยเมื่อทำแบบนี้ไปเรื่อย ๆ เราก็จะได้ Tree ที่ Root Node จะเก็บค่า Hash ค่าหนึ่งซึ่ง Represent transaction ทั้งหมด เนื่องจากถ้ามีการเปลี่ยนแปลงเกิดขึ้นใน Transaction หรือ Non-Leaf Node ใดก็ตาม ค่า Hash ที่ Root Node มี ก็จะเปลี่ยนไปแบบสิ้นเชิงด้วยคุณสมบัติของ Hash Function

เมื่อเราใช้ Merkle Tree มาช่วยจัดการการตรวจสอบ Transaction ในแต่ล่ะ Block เพียงแค่เราดูจาก Root Node และนำไปเทียบกับคนอื่น ๆ ในระบบ เราก็สามารถที่จะรู้ได้ทันทีว่า Transaction ใน Block ของเราถูกต้องหรือไม่ โดยที่เราไม่จำเป็นต้องทำการเช็คทุก ๆ Transaction และเมื่อมีความไม่ตรงกันเกิดขึ้น เราก็สามารถที่จะไล่ลงไปตาม Tree ได้ว่า Hash ตรง Node ไหนที่ไม่ตรงกับคนอื่น และไล่ไปเรื่อย ๆ จนถึง Leaf Node เราก็จะเจอกับ Transaction นั้น

นอกจากนี้เรายังสามารถทำการ Pruning บางส่วนของ Tree ออกจาก Block เก่า ๆ เพื่อประหยัดพื้นที่ในการจัดเก็บ Chain ทั้งหมด