Merkleovo stablo

Merkleovo stablo je kriptografska stablasta struktura u kojoj je svaki čvor koji nije list, obilježen hashem labela njegove djece-čvorova. Nazvana su po Ralphu Merkleu koji je prvi predložio takav koncept.

Podaci koji se trebaju kriptirati, razbijaju se u blokove te se ti blokovi zatim hashiraju i ti hashevi predstavljaju listove stabla. Iduća se razina stabla dobiva konkateniranjem parova listova te njihovim hashiranjem. Postupak se ponavlja sve dok na kraju ne ostane samo jedan čvor, takozvani Merkleov korijen.

Slika 1

Na slici 1 podaci su razbijeni u četiri bloka. Svaki je blok hashiran (Hash1, ... , Hash4) i ti hashevi predstavljaju listove stabla. Iduća razina stabla dobiva se konkateniranjem parova listova i njihovim hashiranjem s lijeva nadesno: Hash12 = hash(Hash1 || Hash2), Hash34 = hash(Hash3 || Hash4). Zatim se postupak ponavlja: Hash1234 = hash(Hash12 || Hash34). Ovo je posljednji korak u generiranju stabla budući da je ostao samo jedan čvor Hash1234 koji se naziva korijen Merkleovog stabla.

Svaka iduća razina stabla sadrži dvostruko manje čvorova od one prethodne. Ako stablo ima 2ⁿ čvorova, algoritam nije teško provesti do kraja. Što se događa ako je broj čvorova različit od 2ⁿ ? Rješenje je da se neparni list ili čvor konkatenira sam sa sobom. Npr. hashevi blokova podataka su H1, H2, H3, H4 i H5. Algoritam izgleda ovako: H12 = hash(H1||H2), H34 = hash(H3||H4) i H55 = hash(H5||H5). Iduća je razina H1234 = hash(H12||H34) i H5555 = hash(H55||H55). Korijen = hash(H1234||H5555).

Merkleovo stablo u protokolu Bitcoin

Svaki blok u Bitcoinu sadrži Merkleov korijen dobiven na goreopisani način od transakcija prikupljenih u periodu od deset minuta. Hash funkcija koja se koristi je SHA256. Jedna razlika od gornjeg postupka je da se umjesto jednom, svi podaci hashiraju dva puta da bi se izbjegao napadproduživanjem duljine hasha.

U idućem prijeru neka su T transakcije. Merkleovo stablo od 6 transakcija je: H12 = SHA256(SHA256(T1||T2)), H34 = SHA256(SHA256(T3||T4)) i H56 = SHA256(SHA256(T5||T6)). Zatim H14 = SHA256(SHA256(H12||H34)) i H56 = SHA256(SHA256(H56||H56)). Korijen je SHA256(SHA256(H14||H56)).

Orezivanje grana Merkleovog stabla

 

Grane se u Merkleovom stablu mogu "odrezati" kako bi se uštedilo na memoriji. Grane se režu na takav način da je od preostalih moguće rekreirati ispravan Merkleov korijen.

Slika 2

 

 

Na slici 2 je primjer orezanog Merkleovog stabla. Klijentu su potrebni transakcija T1 i čvorovi Hash2 i Hash34. Korije se rekreira tako što se T1 hashira, dobiveni hash se konkatenira s Hash2 te hashira da se dobije Hash12. Taj se hash konkatenira s Hash34 i rezultat se hashira da se dobije korijen.

Orezano stablo koristi se u protokolu Stratum. Kada rudar kontaktira bazen, bazen mu šalje listu čvorova koji će rudaru biti potrebni da se dobije korijen. Na primjer, bazen ghash.io rudaru pošalje iduće čvorove:

"ea9da84d55ebf07f47def6b9b35ab30fc18b6e980fc618f262724388f2e9c591", 

"f8578e6b5900de614aabe563c9622a8f514e11d368caa78890ac2ed615a2300c", 

"1632f2b53febb0a999784c4feb1655144793c4e662226aff64b71c6837430791", 

"ad4328979dba3e30f11c2d94445731f461a25842523fcbfa53cd42b585e63fcd", 

"a904a9a41d1c8f9e860ba2b07ba13187b41aa7246f341489a730c6dc6fb42701", 

"dd7e026ac1fff0feac6bed6872b6964f5ea00bd8913a956e6b2eb7e22363dc5c", 

"2c3b18d8edff29c013394c28888c6b50ed8733760a3d4d9082c3f1f5a43afa64"

  

Rudar generira coinbase transakciju te koristeći gornje transakcije generira Merkleov korijen.

 

Recimo da je dvostruk hash coinbase transakcije koju je rudar dobio:

8300639d3ed0b31c766f4d597839f4cd49cc9bf1572c46c680121dc6bc4090c3

Sad se konkatenira taj hash 8300... i hash ea9d... te se taj rezultat hashira:

061eb6650cd2688b058b48735912279e56d26cf90a79255df707d3edfc8cbb3f

I dalje 061e...||f857... i dvostruki hash:

b05bcb7fea6b35be774fd3222c72029c0ad655bdbe836751cdf1494d8bd817f0

SHA256(SHA256(b05b...||1632...)):

711ce7c29a166c21106fbb33072891c4a04edbab3af908f7e0429e645303646d

SHA256(SHA256(711c...||ad43...)):

04aae851be411ca558eb48f0d861d5204c568c0614554eb997d6fe80a4178590

SHA256(SHA256(04aa...||a904...)):

c1f30474fac25636b9465ef17276e41a79d368dc1343455194301c2df8949103

SHA256(SHA256(c1f3...||dd71)):

7600625958076fe5243b6378bae5d977372f3ecd5cf549108ddbb626e08cde1d

SHA256(SHA256(7600...||2c3b...)):

6f7b0464b92b6f612bcea205894f77bfb952dea62fb818d639d8ff1dc602db63

To je Merkleov korijen za dobiveve čvorove i generiranu coinbase transakciju.