Thursday, April 17, 2014

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 2n čvorova, algoritam nije teško provesti do kraja. Što se događa ako je broj čvorova različit od 2n ? 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.


 

Sunday, April 13, 2014

Rudarenje bitcoina: protokol Stratum


Protokol Stratum služi za komunikaciju između rudara i bazena, a zasnovan je na JSON-RPC-u. Bazen mora učinkovito raposređivati posao među rudarima i brzo prikupljati rezultate. Bazen također mora osigurati da rudari ne dupliciraju posao te da ne rade na blokovima koji su već izrudareni.

Jedan problem predstavljaju brzi rudari kojim prolete kroz sve kombinacije noncea prije nego bazen stigne poslati novi blok. Stratum to rješava tako što rudarima omogućuje da lokalno kreiraju coinbase transakciju i prema potrebi modificiraju njezino polje extranonce (promjena coinbase transakcije automatski znači da se promijenilo i zaglavlje bloka budući da se promijenilo Merkleovo stablo transakcija).

Poruke u protokolu

 

Da bi započeo rudarenje u nekom bazenu pomoću Stratum protokola, rudar prvo mora poslati bazenu registracijsku poruku na koju mu bazen odgovori podacima za registraciju:


id
1
set_difficulty
b4b6693b72a50c7116db18d6497cac52
notify
ae6812eb4cd7735a302a8a9dd95cf71f
extranonce1
45fadd2d
extranonce2_size
4
error
null

 

Bazen javlja koja je težina rudarenja u tom bazenu, koji je hash bloka na kojem se trenutačno radi, vrijednost extranonce1 koja osigurava da svi klijenti generiraju jedinstvene blokove te duljinu polja extranonce2 koju će generirati rudar.


Rudar zatim pošalje zahtjev za početak rudarenja, a bazen mu odgovara porukom koja sadrži osnovne podatke za kreiranje bloka:

job_id
2dddaca8
prev_hash
c3a8a906d58a374d5092ba6792ab4d5e38c932f01dc4dcd6000000
0000000000
coinb1
01000000010000000000000000000000000000000000000000000
000000000000000000000ffffffff4803da8204062f503253482f0472b
b4a5308
coinb2
2e522cfabe6d6d4183475fab25720b7274cc7decea671073d97e050
abeababf0a80b44241a3bf804000000000000000000000001eccb6b
95000000001976a91480ad90d403581fa3bf46086a91b2d9d4125db
6c188ac00000000
merkle_branch
c69d0e3aed71cd90f681fa8178766ca3a234f854a0dac42e3ce4a4b1
c51e8e5f, ...
version
00000002
nbits
1900b3aa
ntime
534abb71
clean_jobs
false

 
job_id predstavlja identifikator rudara koji on mora poslati bazenu kad šalje rješenje bloka, prev_hash je hash prethodnog bloka, coinb1 i coinb2 su početni i završni dio coinbase transakcije. Merkle_branch sadrži osnovne grane potrebne za generiranje merkleovog korijena, version je verzija bloka, nbits je meta, ntime je trenutačno vrijeme, a clean_jobs zastavica čije značenje trenutačno nije bitno.

Kreiranje coinbase transakcije

 

Rudar sad ima sve podatke potrebne za generiranje coinbase transakcije: coinb1, extranonce1, extranonce2 (koji je sam generirao) i coinb2. Transakcija se dobiva konkateniranjem tih vrijednosti:


Version
01000000
Input count
01
Previous hash
0000000000000000000000000000000000000000000000000000000
000000000
Index
ffffffff
Scriptlen
0x48 (72)
Script
03da8204062f503253482f0472bb4a530845fadd2d000017e42e522cfa
be6d6d4183475fab25720b7274cc7decea671073d97e050abeababf0a8
0b44241a3bf80400000000000000
Sequence
00000000
Output count
01
Value
eccb6b9500000000
Scriptlen
19
Script
76a91480ad90d403581fa3bf46086a91b2d9d4125db6c188ac
Lock time
00000000

 

Zaglavlje bloka dobiva se na sličan način: iz podataka poslanih od bazena (verzija bloka, hash prethodnog bloka, Merkleov korijen (dobiven iz grana i coinbase transakcije), vremenska oznaka, meta i nonce.

Sunday, April 6, 2014

Rudarenje bitcoina: Pool mining


Rudarenje u grupi ili bazenu (engl. mining in a pool) olakšava rudarenje tako što raspodjeljuje posao među rudarima. Kad bazen uspješno izrudari blok, naknada se raspodjeljuje među svim rudarima tog bazena kao nagrada za obavljeni posao. Postoje razni bazeni za rudarenje te postoje razni načini dodjele nagrada rudarima.

Bazeni moraju provjeravati koliko posla obavljaju rudari. To rade tako što rudarima proslijede blok koji treba verificirati te skupljaju djelomična rješenja bloka od rudara. Svako djelomično rješenje pokazuje da rudar pokušava riješiti blok te znači da će dobiti dio nagrade ako se blok uspješno riješi.


Na primjer, potrebno je da hash počinje s 15 nula, no bazen će tražiti od rudara hasheve koji počinju s 10 nula što je mnogo lakše za pronaći. Bazen skuplja te nizove (udjele) koji počinj manjim brojem nula kao dokaz da rudari verificiraju blok. Ovisno o snazi procesora koji koriste, rudari će te jednostavnije nizove generirati nekoliko puta u sekundi ili nekoliko puta u satu. Prije ili kasnije jedno će od tih rješenja počinjati ne samo s 10 nego i s 15 nula te će blok biti uspješno verificiran, odnosno izrudaren, a bazen će rudarima podijeliti dobivenu nagradu. Ako netko izvan bazena prvi izrudari blok, bazen će jednostavno poslati novi blok rudarima te kreće nova runda verificiranja.

Vrste nagrada

 

Prop. - Proportional (proporcionalna). Dodjeljuje se rudarima proporcionalno broju udjela koji su rudari poslali bazenu.
PPS – Pay per share (plaća po udjelu). Svaki udjel poslan bazenu vrijedi određeni broj bitcoina. Verificiranje bloka zahtjeva broj udjela ovisan o trenutačnoj težini rudarenja. Tako bi cijena udjela bila <naknada_za_blok> / <trenutačna_težina>, odnosno (25 BTC) / <trenutačna_težina>.
PPLNS – Pay per last N shares (plaća prema zadnjih N udjela). Slična proporcionalnoj metodi, ali umjesto da gleda broj udjela po rundi, gleda zadnjih N udjela bez obzira na rundu.
SMPPS – Shared maximum pay per share. Kao PPS ali ne plaća više nego bazen zaradi.
PPLNSG – Pay per last N groups (or shifts) (plaća po zadnji N grupa odnosno smjena). Slična PPLNS, ali se udjeli grupiraju u "smjene" te se one isplaćuju u cijelosti.
RSMPPS – Recent shared maximum pay per share. Slično SMPPS-u, ali prioritizira novopristigle rudare.
ESMPPS – Equalized share maximum pay per share. Kao SMPPPS no izjednačava naplatu među svima koji ju trebaju primiti.
CPPSRB – Capped pay per share with recent backpay. Kad se pronađe blok, isplati se 25 BTC-a neisplaćenih udjela.
POT – Pay on target (plaća po meti). Isplaćuje više što je težina rudarenja veća.
Bodovi – metoda zasnovana na bodovanju. Slična proporcionalnoj metodi, ali koristi težinske faktore u ovisnosti o vremenu.