Merkle-fa

A kriptográfiában és a számítástechnikában a hash-fa vagy Merkle-fa egy olyan fa, amelyben minden "levél" (csomópont) egy adatblokk kriptográfiai hash-kódjával van ellátva, és minden olyan csomópont, amely nem levél (ág, belső csomópont vagy inode) a gyermekcsomópontjai címkéinek kriptográfiai hash-kódjával van ellátva. A hash-fa lehetővé teszi egy nagy adatszerkezet tartalmának hatékony és biztonságos ellenőrzését. A hash-fa a hash-lista és a hash-lánc általánosítása.

Annak bizonyítása, hogy egy levélcsomópont egy adott bináris hash-fa része, a fa levélcsomópontjai számának logaritmusával arányos számú hash kiszámítását igényli.^[1] Ezzel szemben egy hash-listában ez a szám arányos a levélcsomópontok számával. A Merkle-fa ezért hatékony példája a kriptográfiai elkötelezettségi rendszernek, amelyben a fa gyökere egy elkötelezettségnek tekinthető, a levélcsomópontok pedig felfedhetők és bizonyíthatóan az eredeti elkötelezettség részét képezik.

A hash-fa fogalmát Ralph Merkle-ről nevezték el, aki 1979-ben szabadalmaztatta.^[2][3]

1. ↑ Wayback Machine. web.archive.org. [2014. december 22-i dátummal az eredetiből archiválva]. (Hozzáférés: 2024. március 1.)
2. ↑ Espacenet - Bibliographic data. worldwide.espacenet.com. (Hozzáférés: 2024. március 1.)
3. ↑ Merkle, Ralph C. (1988. február 6.). „A Digital Signature Based on a Conventional Encryption Function” (angol nyelven). Advances in Cryptology — CRYPTO ’87, Berlin, Heidelberg, 369–378. o, Kiadó: Springer. DOI:10.1007/3-540-48184-2_32.