pienoiskuva|Esimerkki binäärisestä tiivistepuusta, jossa tietolohkojen (L1..4) tiivisteet ovat säilöttynä. Merkle-puu eli tiivistepuu on tietorakenne, joka sisältää kryptografisia tiivisteitä. Tiivistepuussa jokainen välisolmu on tiiviste sen alisolmuista ja lopullinen lehtisolmu on tiiviste alkuperäisestä tiedosta. Yksittäinen tiiviste koskee vain pientä osaa tiedosta.
Ralph C. Merkle käytti menetelmää digitaalisten allekirjoituksien menetelmässään, jossa yhdellä avaimella allekirjoitetaan useita viestejä, ja patentoi menetelmän. Patentti myönnettiin vuonna 1982 ja se vanheni vuonna 1999.
Käyttökohteita
Merkle-puuta käytetään muun muassa fs-verity -mekanismissa. Tavalliseen tiivisteeseen verrattuna puurakenne on tehokkaampi kun tiedosto on suuri ja siitä käytetään vain pientä osaa.
Ehdotettu X.509:n uusi muoto Merkle Tree Certificates perustuu Merkle-puun käyttöön.
Merkle-puun käyttäjiä ovat muun muassa lohkoketjut kryptovaluutoissa. Myös BitTorrent käyttää tiivistepuuta tiedostojen osien tarkistamiseen.
Lähteet
Luokka:Tietorakenteet