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

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

แนวคิดของต้นไม้แฮชได้รับการตั้งชื่อตามRalph Merkleผู้จดสิทธิบัตรในปี 1979 ^{[ 3 ] [ 4 ]}

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

โครงสร้างข้อมูลแบบแฮชทรีถูกนำไปใช้ใน:

• การเข้ารหัสแบบใช้แฮช
• ระบบไฟล์ระหว่างดาวเคราะห์ (IPFS)
• บิตทอร์เรนต์
• แฮชทรี^{[ 5 ]}
• ระบบไฟล์ZFS ^{[ 6 ]} (เพื่อป้องกันการเสื่อมสภาพของข้อมูล^{[ 7 ]} );
• โปรโตคอล ข้อมูล ;
• โปรโตคอลApache Wave ; ^{[ 8 ]}
• GitและMercurialเป็นระบบควบคุมเวอร์ชันแบบกระจาย (แม้ว่าในทางเทคนิคแล้ว พวกมันใช้กราฟแบบไม่มีวงจรทิศทางไม่ใช่ต้นไม้)
• ระบบสำรองข้อมูล Tahoe -LAFS ;
• เซโรเน็ต ;
• OpenZFS ^{[ 9 ]}
• เครือข่ายแบบ peer-to-peer ของBitcoinและEthereum ; ^{[ 10 ]}
• กรอบ ความโปร่งใสของใบรับรอง;
• ใบรับรอง Merkle Tree; ^{[ 11 ]}
• ตัวจัดการแพ็กเกจ Nixและตัวสืบทอดเช่นGNU Guix ; ^{[ 12 ]}
• ระบบ NoSQLจำนวนมากเช่น^Apache Cassandra , RiakและDynamo ^{[ 13} ]

มีการเสนอแนะให้ใช้ต้นไม้แฮชในระบบคอมพิวเตอร์ที่เชื่อถือได้^{[ 14 ]}

ต้นไม้แฮช (Hash tree) คือต้นไม้ของค่าแฮชโดยที่ใบ (เช่น โหนดใบ บางครั้งเรียกว่า "ใบ") คือค่าแฮชของบล็อก ข้อมูล เช่น ในไฟล์หรือชุดไฟล์ โหนดที่อยู่สูงขึ้นไปในต้นไม้คือค่าแฮชของโหนดลูกของมัน ตัวอย่างเช่น ในภาพด้านบนค่าแฮช 0คือผลลัพธ์ของการแฮชค่าแฮช0-0และค่าแฮช 0-1 ที่ต่อกัน นั่นคือค่าแฮช 0 = ค่าแฮช ( ค่าแฮช 0-0 + ค่าแฮช 0-1 ) โดยที่ "+" หมายถึงการต่อกัน

โดยส่วนใหญ่แล้วโครงสร้างแฮชทรีจะเป็นแบบไบนารี (มีโหนดลูกสองโหนดภายใต้แต่ละโหนด) แต่ก็สามารถใช้โหนดลูกจำนวนมากกว่านั้นภายใต้แต่ละโหนดได้เช่นกัน

โดยปกติแล้ว จะใช้ ฟังก์ชันแฮชเข้ารหัสลับเช่นSHA-2ในการสร้างแฮช หากโครงสร้างแฮชทรีต้องการเพียงแค่ป้องกันความเสียหายที่ไม่ได้ตั้งใจ ก็สามารถใช้ ค่าตรวจสอบ ที่ไม่ใช่การเข้ารหัสลับ เช่นCRC ได้

ในส่วนบนสุดของโครงสร้างแฮชจะมีแฮชบนสุด (หรือแฮชรากหรือแฮชหลัก ) ก่อนที่จะดาวน์โหลดไฟล์บนเครือข่าย P2Pในกรณีส่วนใหญ่ แฮชบนสุดจะได้รับจากแหล่งที่เชื่อถือได้ เช่น เพื่อนหรือเว็บไซต์ที่ทราบกันดีว่ามีคำแนะนำไฟล์ที่น่าดาวน์โหลดมากมาย เมื่อมีแฮชบนสุดแล้ว โครงสร้างแฮชสามารถรับได้จากแหล่งที่ไม่น่าเชื่อถือใดๆ เช่น พีร์ใดๆ ในเครือข่าย P2P จากนั้น โครงสร้างแฮชที่ได้รับจะถูกตรวจสอบกับแฮชบนสุดที่เชื่อถือได้ และหากโครงสร้างแฮชเสียหายหรือเป็นของปลอม โครงสร้างแฮชอื่นจากแหล่งอื่นจะถูกลองใช้จนกว่าโปรแกรมจะพบโครงสร้างที่ตรงกับแฮชบนสุด^{[ 15 ]}

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

รากแฮช Merkle ไม่ได้ระบุความลึกของต้นไม้ ทำให้เกิดการโจมตีแบบภาพก่อนหน้าครั้งที่สองซึ่งผู้โจมตีสร้างเอกสารอื่นที่ไม่ใช่เอกสารต้นฉบับที่มีรากแฮช Merkle เดียวกัน สำหรับตัวอย่างข้างต้น ผู้โจมตีสามารถสร้างเอกสารใหม่ที่มีบล็อกข้อมูลสองบล็อก โดยบล็อกแรกคือแฮช 0-0 + แฮช 0-1และบล็อกที่สองคือแฮช 1-0 + แฮ ช1-1 ^{[ 16 ] [ 17 ]}

การแก้ไขง่ายๆ อย่างหนึ่งถูกกำหนดไว้ในCertificate Transparency : เมื่อคำนวณแฮชของโหนดใบ จะมีการเพิ่มไบต์ 0x00 ไว้ข้างหน้าข้อมูลแฮช ในขณะที่ 0x01 จะถูกเพิ่มไว้ข้างหน้าเมื่อคำนวณแฮชของโหนดภายใน^{[ 15 ]} การจำกัดขนาดของต้นไม้แฮชเป็นข้อกำหนดเบื้องต้นของการพิสูจน์ความปลอดภัยอย่างเป็นทางการ บางอย่าง และช่วยทำให้การพิสูจน์บางอย่างมีความแน่นหนามากขึ้น การใช้งานบางอย่างจำกัดความลึกของต้นไม้โดยใช้คำนำหน้าความลึกของต้นไม้แฮชก่อนแฮช ดังนั้นห่วงโซ่แฮชที่ดึงออกมาใดๆ จะถือว่าถูกต้องก็ต่อเมื่อคำนำหน้าลดลงในแต่ละขั้นตอนและยังคงเป็นค่าบวกเมื่อถึงใบ

แฮชต้นไม้ไทเกอร์เป็นรูปแบบหนึ่งของต้นไม้แฮชที่ใช้กันอย่างแพร่หลาย โดยใช้ต้นไม้แฮชแบบไบนารี (มีโหนดลูกสองโหนดภายใต้แต่ละโหนด) โดยปกติจะมีขนาดบล็อกข้อมูล 1024 ไบต์และใช้แฮชไทเกอร์^{[ 18 ]}

แฮชต้นไม้เสือถูกใช้ในโปรโตคอลการแชร์ไฟล์P2P ^ของ Gnutella [ ^{19 ]} Gnutella2และDirect Connect ^{[ 20 ]}และใน แอปพลิเคชัน การแชร์ไฟล์เช่นPhex [ ^{21 ]} BearShare , LimeWire , Shareaza , DC++ ^{[ 22 ]}และgtk ^- gnutella ^{[ 23 ]}

• ต้นไม้ไบนารี
• บล็อกเชน
• ตารางแฮชแบบกระจาย
• ตารางแฮช
• แฮชไทร
• การประทับเวลาที่เชื่อมโยง
• ต้นไม้ราก

• สิทธิบัตร Merkle tree หมายเลข 4,309,569  – อธิบายทั้งโครงสร้างของต้นไม้แฮชและการใช้งานเพื่อจัดการลายเซ็นแบบใช้ครั้งเดียวจำนวนมาก
• รูปแบบการแลกเปลี่ยนแฮชต้นไม้ (THEX)  – คำอธิบายโดยละเอียดของต้นไม้ Tiger

• การใช้งาน AC ของโครงสร้างแฮช SHA-256 แบบไบนารีที่ปรับขนาดได้แบบไดนามิก (โครงสร้างเมอร์เคิล)
• การใช้งาน Merkle tree ในภาษา Java
• ซอร์สโค้ดของ Tiger Tree Hash (TTH) ในภาษา C#โดย Gil Schmidt
• การใช้งาน Tiger Tree Hash (TTH) ในภาษา C และ Java
• RHashเป็นเครื่องมือโอเพนซอร์สแบบบรรทัดคำสั่ง ที่สามารถคำนวณ TTH และลิงก์แม่เหล็กด้วย TTH ได้