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. 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.

Felhasználási esetek

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 (az adatromlás ellensúlyozására);
• Dat protokoll;
• Apache Wave protokoll;
• 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;
• 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.

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.

Áttekintés

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 hashfa 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 hashelé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.

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.

Második preimage támadás

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.

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.

Tigrisfa hash

A Tiger tree hash a hash-fa egy széles körben használt formája. Bináris hashfá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.

Tiger tree hash-eket használnak a Gnutella, Gnutella2 és Direct Connect P2P fájlmegosztó protokollokban, valamint olyan fájlmegosztó alkalmazásokban, mint a Phex, BearShare, LimeWire, Shareaza, DC++ és gtk-gnutella.