Merkle-puu
Merkle-puu on yksi lohkoketjujen perus periaatteista. Se on tiivisteistä koostuva puuta muistuttava datarakenne, jonka avulla voidaan tallentaa suuria määriä dataa tehokkaasti ja datan oikeellisuus voidaan varmentaa turvallisesti. Teoriassa julkisen lohkoketjun voisi luoda myös ilman Merkle-puuta, mutta tämä tarkoittaisi jättimäisen ylätunnisteen luomista. Tämä tunniste sisältäisi kaikki lohkon siirrot. Seurauksena lohkoketjut kokisivat nykyisiäkin suurempia skaalautuvuus ongelmia, kunnes lopulta vain maailman tehokkaimmat koneet pystyisivät lohkoketjuja käyttämään. Muun muassa Merkle-puun ansiosta julkiset lohkoketjut ovat nykyään käytettävissä myös pienen laskentatehon laitteilla, kuten älypuhelimilla ja jopa esineiden internetin laitteilla. Merkle-puu on saanut nimensä Ralph Merklen mukaan, joka patentoi Merkle-puun vuonna 1979.
Tiivisteparien avulla dataa saadaan tiivistettyä pienempään tilaan. Tiivisteitä luodaan alhaalta ylöspäin, jolloin ensimmäiset tiivisteet ovat yksittäisten siirtojen tiivisteitä. Näitä tiivisteitä kutsutaan lehdiksi. Kaikki myöhemmät tiivisteet luodaan yhdistämällä kaksi aikaisempaa tiivistettä. Näitä kutsutaan oksiksi. Lopulta jäljellä on vain yksi tiiviste, jota kutsutaan juuritiivisteeksi tai Merkle-juureksi.
Alla oleva kuva havainnollistaa puun rakennetta. Siinä siirroista A, B, C ja D luodaan ensiksi tiivisteet A, B, C ja D. Nämä tiivisteet ovat lehtiä. Seuraavaksi tiivisteistä A ja B luodaan tiiviste AB, sekä tiivisteistä C ja D luodaan tiiviste CD. Nämä ovat Merkle-puun oksia. Lopuksi tiivisteistä AB ja CD luodaan tiiviste ABCD, joka on Merkle-juuri.
Kuten kuvasta voidaan havaita, ovat Merkle-puut binäärisiä ja siksi ne vaativat parillisen määrän lehtiä. Jos lehtiä on pariton määrän, viimeinen tiiviste kopioidaan kertaalleen. Tuloksena on parillinen määrä lehtiä.
Merkle-puusta voidaan helposti tarkistaa, onko jokin tieto puussa. Tiedon oikeellisuus tarkistetaan kulkemalla ylhäältä alaspäin. Tätä varten koko puuta ei tarvitse ladata, kuten alhaalla olevasta kuvasta voidaan todeta. Jos Merkle-puusta muutetaan mitä tahansa tietoa, muuttuvat kaikki puun ylemmät oksat. Tämän ansiosta Merkle-puusta voidaan helposti varmentaa tiedon muuttumattomuus. Puusta onkin erittäin nopeaa ja tehokasta varmentaa tietoa, eikä se käytä paljoa tallennustilaa.
Merkle-puu hyödyttääkin sekä louhijoita, että käyttäjiä. Louhija voi laskea tiivisteitä progressiivisesti vastaanottaessaan siirtoja vertaisiltaan. Käyttäjä voi tarkistaa jokaisen yksittäisen siirron käyttäen puun oksien tiivisteitä apunaan.
Merkle-puuta käytetään lohkoketjuissa varmentamaan tiedon oikeellisuutta, koska tiedon tarkastaminen puusta on äärettömän nopeaa ja helppoa. Merkle-puun ansiosta myös tiedon hakeminen jokaisesta lohkosta on nopeaa. Merkle-puu on yksi lohkoketjujen perusteista ja auttaa datan muuttumattomuuden ylläpitämisessä.
