ต้นไม้แฮช

บทความนี้มีชื่อเป็นภาษาอื่น หรือใช้อักษรในภาษาอื่น เนื่องจากต้องการคงไว้ตามต้นฉบับ หรือไม่มีชื่อภาษาไทยที่เหมาะสม

Hash tree หรือ Merkle tree เป็นโครงสร้างข้อมูลชนิดหนึ่งซึ่งประกอบไปด้วยต้นไม้ของข้อมูลที่ถูกสรุปแล้ว ซึ่งข้อมูลเหล่านี้เกี่ยวกับชิ้นส่วนขนาดใหญ่ของข้อมูล เช่น ไฟล์ ซึ่งมันจะถูกใช้ตรวจสอบหาเนื้อหาของข้อมูล Hash trees เป็นคลาสลูกของ Hash lists ซึ่งทั้งสองคลาสก็ยังเป็นคลาสลูกของคลาส hashing อีกที Hash tree มี Hash function ที่สำคัญคือ Tiger ซึ่งบ่อยครั้งอาจจะเรียกว่า Tiger tree หรือ Tiger tree hashes

A binary hash tree

การใช้งาน

Hash tree สามารถใช้ป้องกันข้อมูลที่ถูกเก็บได้หลากหลายชนิดซึ่งจะคอยควบคุมและส่งข้อมูลทั้งในตัวเครื่องคอมพิวเตอร์และระหว่างเครื่องด้วยเช่นกัน ปัจจุบัน hash tree จะถูกใช้เพื่อทำให้แน่ใจว่าก้อนข้อมูลที่ได้รับจากคนอื่น ในเครือข่าย peer-to-peer network นั้นไม่ได้รับความเสียหายหรือถูกเปลี่ยนแปลง และยังเช็คอีกด้วยว่าคนที่ส่งข้อมูลมาให้เรานั้นไม่ได้หลอกหรือส่งข้อมูลปลอมมาให้ คำแนะนำหลายๆครั้งแนะนำว่าควรจะใช้ hash tree ในระบบการคำนวณที่เชื่อถือได้ Sun Microsystems ได้ใช้ Hash Trees ใน the ZFS file system นอกจากนี้ Hash Trees ยังถูกใช้อยู่ในโพรโทคอลของ Google Wave และในระบบสำรองข้อมูล

Hash trees ถูกคิดขึ้นในปี ค.ศ. 1979 โดย Ralph Merkle จุดประสงค์เดิมของมันคือใช้เพื่อจัดการกับ Lamport one-time signatures ให้ได้อย่างมีประสิทธิภาพ Lamport signatures ยังเชื่อว่าจะยังคงมีความปลอดภัยในกรณีที่ quantum computer เกิดขึ้นจริง แต่น่าเสียดายที่แต่ละ Lamport key นั้นสามารถใช้ได้เพียงเพื่อเซ็นข้อความเดียวเท่านั้นแต่เมื่อรวมกับ hash trees แล้วมันจะสามารถใช้งานสำหรับข้อความหลายข้อความได้ จากนั้นก็กลายมาเป็น fairly efficient digital signature scheme

วิธีการทำงานของ Hash trees

Hash tree เป็นต้นไม้ของ hashes ซึ่งใบของมันคือค่า hash ของก้อนข้อมูล เช่น ไฟล์หรือกลุ่มของข้อมูล ซึ่ง Nodes ที่ถูกเพิ่มเข้ามาในต้นไม้คือ hash ของ Node ลูกของตัว Node นั้นเอง เช่น ในรูป hash 0 เป็นผลลัพธ์ของการ hashing hash 0-0 กับ hash 0-1 นั่นคือ hash 0 = hash( hash 0-0 + hash 0-1 ) ซึ่ง + หมายถึงการเชื่อมต่อกันของ Node

การใช้งาน hash tree ส่วนใหญ่คือ binary (แต่ละ Node มีลูกสองตัว) แต่จริงๆแล้วมันสามารถมี Node ลูกได้มากกว่านั้น

บ่อยครั้งที่ cryptographic hash function เช่น SHA-1, Whirlpool, หรือ Tiger ใช้สำหรับการ hashing ถ้า hash tree ต้องป้องกันความเสียหายที่อาจคาดไม่ถึง มันจะทำให้ผลการตรวจสอบความปลอดภัยมีประสิทธิภาพลดลง เช่น CRCs ที่สามารถถูกใช้ได้

ในด้านบนสุดของ hash tree คือ top hash (root hash หรือ master hash) ก่อนดาวน์โหลดไฟล์บน p2p network ในกรณีส่วนใหญ่ top hash ที่ได้มาจากแหล่งที่เชื่อถือได้ ยกตัวอย่างเช่น เว็บไซต์ที่เป็นที่รู้จักมีข้อเสนอแนะที่ดีสำหรับไฟล์ที่จะดาวน์โหลด เมื่อ top hash สามารถใช้ได้ hash tree สามารถได้รับจากแหล่งข้อมูลที่เชื่อถือไม่ได้ เหมือน peer อื่นๆใน p2p network จากนั้นนำ hash tree ที่ได้รับมาไปตรวจสอบด้วย top hash ที่เชื่อถือได้ และถ้า hash tree ได้รับความเสียหายหรือเป็นถูกปลอมแปลง hash tree จากแหล่งอื่นๆจะพยายามจนกระทั่งพบ hash tree ที่เข้ากันได้กับ top hash

ความแตกต่างที่สำคัญจาก hash list คือ กิ่งหนึ่งของ hash tree ที่สามารถดาวน์โหลดได้ทันทีและความสมบูรณ์ของแต่ละกิ่งสามารถตรวจสอบได้ทันทีถึงแม้ว่าต้นไม้ทั้งหมดจะยังไม่สามารถใช้ได้นี้จะเป็นประโยชน์ตั้งแต่มันมีประสิทธิภาพในการแยกไฟล์ขนาดเล็กมากเพื่อที่จะดาวน์โหลดข้อมูลเพียงก้อนเล็กๆ ถ้าหากมันได้รับความเสียหาย

ถ้าไฟล์ที่ถูก hash มีขนาดใหญ่มาก hash tree หรือ hash list จะมีขนาดใหญ่ตามไปด้วย แต่มันเป็นต้นไม้ กิ่งเล็กๆหนึ่งกิ่งจะสามารถดาวน์โหลดได้เร็วและเมื่อนำแต่ละกิ่งมารวมกันเราก็จะสามารถตวรจสอบได้ และจากนั้นการดาวน์โหลดของก้อนข้อมูลก็สามารถเริ่มขึ้นได้

Tiger tree hash

Tiger tree hash เป็นรูปแบบของ hash tree ที่ใช้กันอย่างแพร่หลาย โดยใช้ binary hash tree ส่วนใหญ่จะมีขนาดของกลุ่มข้อมูลเท่ากับ 1024 ไบต์ และใช้ป้องกัน Tiger hash Tiger tree hash ถูกใช้ใน Gnutella, Gnutella2, and Direct Connect P2P ซึ่งเป็นโพรโทคอลสำหรับแชร์ไฟล์ และ โปรแกรมแชร์ไฟล์ เช่น Phex, BearShare, LimeWire, Shareaza, DC++ and Valknut

อ้างอิง

• Merkle tree patent 4,309,569 – Explains both the hash tree structure and the use of it to handle many one-time signatures.
• – A detailed description of Tiger trees.
• Efficient Use of Merkle Trees 2006-12-06 ที่ เวย์แบ็กแมชชีน – RSA labs explanation of the original purpose of Merkle trees: To handle many Lamport one-time signatures.