Merkle-puu on tietorakenne, jota käytetään tietoteknisissä sovelluksissa. Bitcoinissa ja muissa kryptovaluutoissa Merkle-puiden tehtävänä on koodata blockchain-tiedot tehokkaammin ja turvallisemmin.
Niitä kutsutaan myös "binaarisiksi hash-puiksi".
Merkle-puun murtaminen
Bitcoinin lohkoketjussa transaktiolohko suoritetaan algoritmin avulla, jotta saadaan hash, joka on numero- ja kirjainmerkkijono, jota voidaan käyttää varmentamaan, että annettu tietojoukko on sama kuin alkuperäinen tapahtumaryhmä, mutta olla hankkimatta alkuperäistä tapahtumaryhmää. Bitcoin-ohjelmisto ei kuitenkaan suorita koko tapahtumatietolohkoa - joka edustaa keskimäärin 10 minuutin arvosta tapahtumia - hash-toiminnon kautta kerrallaan. Pikemminkin jokainen tapahtuma on hajautettu, sitten jokainen tapahtumapari yhdistetään ja hajautetaan yhteen, ja niin edelleen, kunnes koko lohkolle on yksi tiiviste. (Jos tapahtumia on pariton määrä, yksi tapahtuma kaksinkertaistetaan ja sen tiivistelmä yhdistetään itsensä kanssa.)
Tämä rakenne muistuttaa puuta. Seuraavassa kaaviossa "T" merkitsee tapahtumaa, "H" tiivistettä. Huomaa, että kuva on yksinkertaistettu; keskimääräinen lohko sisältää yli 500 tapahtumaa, ei kahdeksan.
Alarivin hashille viitataan nimellä "lehdet", väliteräksiksi "oksat" ja yläosassa olevaan hashiin "juuri". Tietyn lohkon Merkle-juuri tallennetaan otsikkoon: esimerkiksi lohkon # 482819 Merkle-juuri on e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Juuri yhdistetään muihin tietoihin (ohjelmistoversio, edellisen lohkon tiivistelmä, aikaleima, vaikeuskohde ja nonse) ja suoritetaan sitten hash-toiminnon läpi lohkon ainutlaatuisen hajotuksen tuottamiseksi: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089582828. Tätä hashia ei itse asiassa sisällytetä vastaavaan lohkoon, mutta seuraavaan; se eroaa Merklen juuresta.
Merkle-puu on hyödyllinen, koska sen avulla käyttäjät voivat tarkistaa tietyn tapahtuman lataamatta koko lohkoketjua (yli 130 gigatavua elokuun lopussa 2017). Sano esimerkiksi, että halusit varmistaa, että tapahtuma TD sisältyy yllä olevan kaavion lohkoon. Jos sinulla on juurihajautus (H ABCDEFGH), prosessi on kuin sudoku-peli: kysyt verkolta tietoja H D: stä, ja se tuottaa H C, H AB ja H EFGH. Merkle-puun avulla voit tarkistaa, että kaikki otetaan huomioon kolmella hashilla: annettu H AB, H C, H EFGH ja juuren H ABCDEFGH, H D (ainoan puuttuvan hash) on oltava läsnä tiedoissa.
Merklepuut on nimetty Ralph Merklen mukaan, joka ehdotti niitä vuonna 1987 julkaisussa "Digitaalinen allekirjoitus, joka perustuu perinteiseen salaustoimintoon". Merkle keksi myös salaushajautuksen.
