Deo zbornika Učimo blockchain

Binarno hash stablo

Svaki blok lanca u zaglavlju sadrži polje pod nazivom korijen binarnog hash stabla, koji omogućuje sažet prikaz svih zapisa u bloku ali i jednostavnu provjeru integriteta velikog skupa podataka.

Binarno stablo je konačan skup podataka istog tipa, koje zovemo čvorovi. Pri tome vrijedi:

  • T je prazan skup (prazno stablo), ili
  • postoji istaknuti čvor r koji zovemo korijen od T, a ostali čvorovi grade uređeni par (TL, TR) disjunktnih binarnih stabala.

Binarno hash stablo je binarno stablo u kojem su listovi, odnosno čvorovi bez djece, hash vrijednosti nekih podataka, a ostali čvorovi su nastali konkatenacijom hash-eva svoje djece te primjenom iste hash funkcije na taj podatak.

U Bitcoin sustavu listovi binarnog hash stabla su hash-evi svake pojedine transakcije u bloku. Kao hash funkcija koristi se SHA-256 primijenjena dva puta.

Pohranjivanjem korijena binarnog hash stabla u zaglavlje bloka dobivamo sažeti prikaz svih zapisa u bloku. Nadalje, poznavajući taj sažeti prikaz lako je odrediti pripada li neki zapis bloku, bez da imamo uvid u cijeli skup zapisa.

Izgradnja hash stabla

binarno-hash-stablo

Slika prikazuje izgradnju hash stabla u slučaju da bi u bloku bile zapisane četiri transakcije, nazovimo ih a, b, c i d. Prema strukturi binarnog hash stabla logično je da izgradnja tog stabla kreće od dna prema vrhu. Bitcoin sustav, kao i svaki drugi sustav koji koristi blockchain tehnologiju, ima strogo definiran format podataka koji se upisuju u blockchain. No, u hash stablo nisu zapisani ti podaci već hash-evi tih podataka. Pa tako Ha dobivamo na sljedeći način:

H a = SHA-256(SHA-256(a))

Listove stabla H b , H c , i H d izračunavamo analogno. Sljedeći korak je generiranje čvorova roditelja listova:

H ab = SHA-256(SHA-256(H a + H b )) i H cd = SHA-256(SHA-256(H c + H d ))

gdje operator + predstavlja konkatenaciju stringova. Nakon toga možemo izračunati hash koji zapisujemo u korijen stabla:

H abcd = SHA-256(SHA-256(H ab + H cd ))

Identičan algoritam izgradnje binarnog hash stabla koristi se za bilo koji parni broj transakcija zapisanih u bloku. Ako je u bloku zapisan neparan broj transakcija tada jednostavno dupliciramo zadnju transakciju kao što slika prikazuje:

Također, napomenimo da je veličina podataka zapisanih u korijenu stabla uvijek 32 bajta bez obzira na broj čvorova. Kasnije ćemo vidjeti da postoje čvorovi u sustavu koji lokalno ne pohranjuju čitav blockchain, već samo zaglavlja svih blokova. Hashiranje i primjena binarnih hash stabala ima dvojaku ulogu. Omogućuje provjeru pripadnosti zapisa bloku i lako identificiranje promjene nad podacima.

Čvor, koji nema pristup cijelom blockchainu, može odrediti sadrži li određeni blok neki zapis poznavajući samo taj zapis, odnosno njegov hash i korijen binarnog hash stabla. To određivanje se provodi pomoću autentikacijskog puta u binarnom hash stablu. Za svaki čvor binarnog stabla možemo odrediti njegovu razinu. Razina se određuje iz definicije koja kaže da je korijen razine 1, a da su razine djece nekog čvora razine n jednake n+1.

Autentikacijski put

Autentikacijski put je konačan skup A čvorova binarnog hash stabla B za koje vrijedi:

  • za svaku razinu stabla B, osim za prvu, postoji točno jedan čvor a koji pripada skupu A
  • uz poznavanje još jednog lista stabla B koji ne pripada skupu A moguće je odrediti korijen binarnog hash stabla B.

Binarna hash stabla pomenutim čvorovima omogućuju provjeru integriteta podataka u bloku. Pogledajmo hash stablo sa slike i zamislimo da napadač iz nekog razloga želi promijeniti transakciju b. To bi utjecalo na izgled hasheva H b , H ab i H abcd. Ostali pouzdani čvorovi koji čuvaju kopiju blockchaina ili samo zaglavlja svih blokova mogu lako utvrditi da je došlo do promijene nad podacima u blockchainu.

Izvor: Domina Hozjan, Blockchain (diplomski rad), Prirodoslovno–matematički fakultet, Zagreb, 2017.