Merkle Trees

แปลโดย : Claude 3 Opus (Pro)

Merkle Trees

In the years after completing his internship with Martin Hellman, Ralph Merkle had gone on to make a name for himself as one of the preeminent cryptographers of his generation. Among other innovations, he’d designed a new one-way function, introduced a faster encryption protocol, proposed his own signature algorithm, and although he technically didn’t coauthor the paper, many cryptographers had come to regard Merkle as the third inventor of the Diffie-Hellman key exchange.

But perhaps most notable of all, Merkle had in 1979 invented the Merkle Tree. Originally designed as part of a system for producing authentication certificates for a public key directory, Merkle Trees offer a compact and secure check on the contents of all sorts of data sets by combining hashes in a clever mathematical structure.

Specifically, a Merkle Tree cryptographically aggregates different pieces of data using a few simple steps. First, all the different pieces of data are hashed individually, so each piece of data has its own unique hash. Next, all these hashes are paired in groups of two. Each pair of hashes is then hashed together, which produces one new hash per pair. All the new hashes are then paired again, and these pairs are again hashed together. This process repeats until there is only one hash left, called the Merkle Root. (Visualized, the resulting data structure looks something like a family tree, but for large numbers instead of people.)

Merkle Trees facilitate checks to see whether the hash of a specific piece of data is included in the tree. Importantly, this can be done without needing to see any of the other data that was hashed, nor even most of the other hashes. All that’s needed is a Merkle proof, consisting of the relevant “branches” of the tree: this essentially serves as a compact set of “directions” to find the path from the Merkle Root to the hash of the specific piece of data.

Meanwhile, it’s strictly impossible to edit or remove anything from a tree without changing the entire tree, or, more precisely, without changing the Merkle Root. If a piece of data is altered or removed, the corresponding hash would change as well, which in turn necessarily affects what its “child” hash looks like, which of course affects the next hash, and so on, all the way down to the Merkle Root. Not unlike hash chains, Merkle Trees unequivocally show whether data was altered, but in a much more compact format.

It would prove to be a valuable property in the battle against digital fraud.

ต้นไม้แบบเมอร์เคิล (Merkle Trees)

ในช่วงหลายปีหลังจากเสร็จสิ้นการฝึกงานกับมาร์ติน เฮลแมน ราล์ฟ เมอร์เคิลก็สร้างชื่อให้ตัวเองในฐานะหนึ่งในนักเข้ารหัสลับชั้นนำของยุคสมัย นอกเหนือจากนวัตกรรมอื่นๆ แล้ว เขายังออกแบบฟังก์ชันทางเดียวแบบใหม่ แนะนำโปรโตคอลการเข้ารหัสที่เร็วขึ้น เสนออัลกอริทึมลายเซ็นของตัวเอง และแม้ว่าในทางเทคนิคเขาจะไม่ได้เป็นผู้เขียนบทความร่วม แต่นักเข้ารหัสลับหลายคนก็ถือว่าเมอร์เคิลเป็นผู้ประดิษฐ์คนที่สามของการแลกเปลี่ยนกุญแจแบบดิฟฟี่-เฮลแมน

แต่สิ่งที่น่าสังเกตที่สุดคือ เมอร์เคิลได้ประดิษฐ์ต้นไม้แบบเมอร์เคิล (Merkle Tree) ขึ้นในปี 1979 ซึ่งเดิมทีออกแบบมาเพื่อเป็นส่วนหนึ่งของระบบการออกใบรับรองการพิสูจน์ตัวตนสำหรับไดเรกทอรีกุญแจสาธารณะ ต้นไม้แบบเมอร์เคิลนำเสนอการตรวจสอบเนื้อหาของชุดข้อมูลประเภทต่าง ๆ อย่างกระชับและปลอดภัย โดยการรวมแฮชในโครงสร้างทางคณิตศาสตร์ที่ชาญฉลาด

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

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

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

มันจะพิสูจน์ให้เห็นถึงคุณสมบัติที่มีค่าในการต่อสู้กับการฉ้อโกงทางดิจิทัล