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]

A kivonatfák bármilyen, számítógépen tárolt, kezelt és számítógépek között továbbított adat ellenőrzésére használhatók. Segítségükkel biztosítható, hogy a peer-to-peer hálózatban a többi egyenrangú féltől kapott adatblokkok sértetlenül és változatlanul érkezzenek, sőt, azt is ellenőrizni lehet, hogy a többi egyenrangú fél nem hazudik-e és nem küld-e hamis blokkokat.

A kivonatfákat a következőkben használják

• hash-alapú kriptográfia;
• Interplanetáris fájlrendszer (IPFS);
• Btrfs és ZFS fájlrendszerek^[4] (az adatromlás ellensúlyozására^[5]);
• Dat protokoll;
• Apache Wave protokoll;^[6]
• Git és Mercurial elosztott revízióvezérlő rendszerek;
• a Tahoe-LAFS biztonsági mentési rendszer;
• Zeronet;
• a Bitcoin és Ethereum peer-to-peer hálózatok;^[7]
• a Certificate Transparency keretrendszer;
• a Nix csomagkezelő és leszármazottai, mint például a GNU Guix;
• számos NoSQL rendszer, például az Apache Cassandra, a Riak és a Dynamo.^[8]

Javaslatok születtek a hash-fák használatára a megbízható számítástechnikai rendszerekben.

A Merkle-fák Satoshi Nakamoto által készített kezdeti bitcoin-implementációja túlzott mértékben alkalmazza a hash-funkció tömörítési lépését, amit a Fast Merkle Trees alkalmazásával enyhítenek.^[9]

A hash-fa egy hash-ekből álló fa, amelynek levelei (azaz a levélcsomópontok, néha "levelek" is) például egy fájl vagy fájlcsoport adatblokkjainak hash-jei. A fában feljebb lévő csomópontok a megfelelő gyermekeik hash-jai. Például a 0. hash a 0-0. és a 0-1. hash hash-ok összekapcsolásának eredménye. Vagyis hash 0 = hash( hash 0-0 + hash 0-1 ), ahol a "+" az összekapcsolást jelenti.

A legtöbb hash-fa implementáció bináris (minden csomópont alatt két gyermekcsomópont), de ugyanúgy használhatnak sokkal több gyermekcsomópontot is minden csomópont alatt.

A hash-eléshez általában egy kriptográfiai hash-függvényt, például SHA-2-t használnak. Ha a hash-fának csak a nem szándékos sérülések ellen kell védelmet nyújtania, használhatók nem biztonságos ellenőrző összegek, például CRC-k.

A hash-fa tetején van egy top hash (vagy gyökérhash vagy master hash). Mielőtt egy fájlt letöltünk egy P2P-hálózaton, a legtöbb esetben a legfelső hash-t egy megbízható forrásból szerezzük be, például egy barátunktól vagy egy olyan webhelyről, amelyről ismert, hogy jó ajánlásokat ad a letölthető fájlokra vonatkozóan. Ha a legfelső hash rendelkezésre áll, a hash-fa bármely nem megbízható forrásból, például a P2P-hálózat bármelyik társától megkapható. Ezután a kapott hash-fát a program ellenőrzi a megbízható top hash-hez képest, és ha a hash-fa sérült vagy hamis, akkor egy másik forrásból származó másik hash-fával próbálkozik, amíg a program nem talál olyan hash-fát, amely megfelel a top hash-nek.^[10]

A fő különbség a hash-listához képest az, hogy a hash-fának egyszerre csak egy ága tölthető le, és az egyes ágak sértetlensége azonnal ellenőrizhető, még akkor is, ha a teljes fa még nem áll rendelkezésre. Például az L2 adatblokk sértetlensége azonnal ellenőrizhető, ha a fa már tartalmazza a 0-0 és az 1 hash-t. Ehhez az adatblokk hash-elését kell elvégezni, és az eredményt iteratívan kombinálni a 0-0, majd az 1 hash-sel, végül pedig az eredményt a legfelső hash-sel kell összehasonlítani. Hasonlóképpen, az L3 adatblokk sértetlensége ellenőrizhető, ha a fa már tartalmaz 1-1 és 0 hash-t. Ez előnyös lehet, mivel hatékony a fájlok nagyon kis adatblokkokra való felosztása, így sérülés esetén csak kis blokkokat kell újra letölteni. Ha a hashelt fájl nagy, egy ilyen hash-lista vagy hash-lánc meglehetősen nagy lesz. De ha ez egy fa, akkor egy kis ágat gyorsan le lehet tölteni, ellenőrizni lehet az ág sértetlenségét, és utána kezdődhet az adatblokkok letöltése.

A Merkle-hash-gyökere nem jelzi a fa mélységét, ami lehetővé teszi a második preimage támadást, amelynek során a támadó az eredetitől eltérő dokumentumot hoz létre, amelynek ugyanaz a Merkle-hash-gyökere van. A fenti példa esetében a támadó létrehozhat egy új dokumentumot, amely két adatblokkot tartalmaz, ahol az első hash 0-0 + hash 0-1, a második pedig hash 1-0 + hash 1-1.^[11][12]

Egy egyszerű javítás a Certificate Transparency című könyvben található: a levélcsomópontok hash-jének kiszámításakor a hash-adatokhoz egy 0x00 bájtot, míg a belső csomópontok hash-jének kiszámításakor 0x01 bájtot kell előretenni. A hash-fa méretének korlátozása néhány formális biztonsági bizonyítás előfeltétele, és segít néhány bizonyítás szigorításában. Egyes implementációk a hash-fa mélységét a hash-fa mélységének előtagjaival korlátozzák a hash-ok előtt, így bármely kivont hash-lánc csak akkor tekinthető érvényesnek, ha az előtag minden lépésnél csökken, és a levél elérésekor még mindig pozitív.

A Tiger hash-fa a hash-fa egy széles körben használt formája. Bináris hash-fát használ (minden csomópont alatt két gyermekcsomópont), általában 1024 bájtos adatblokkmérettel rendelkezik, és a Tiger hash-t használja.^[13]

Tiger hash-fákat használnak a Gnutella,^[14] Gnutella2 és Direct Connect P2P fájlmegosztó protokollokban,^[15] valamint olyan fájlmegosztó alkalmazásokban, mint a Phex,^[16] BearShare, LimeWire, Shareaza, DC++^[17] és gtk-gnutella.^[18]

• Patent US4309569: Method of providing digital signatures.
• Efficient Use of Merkle Trees (in web archive)