Sunday, December 7, 2014

Mnemonički kod za generiranje determinističkih ključeva (BIP 39)


Mnemonički kod korisit se za pretvaranje nizova znamenki u jednoznačno određene riječi engleskog jezika kako bi se olakšalo njihovo zapisivanje, pamćenje i prenošenje drugim osobama. Oni se koriste i u generiranju determinističkih novčanika.

Generiranje mnemoničkih kodova


Mnemonički kod mora enkodirati entropiju u grupama po 32 bita. Što je entropija veća, veća je i sigurnost, no rečenice su dulje. Propručena veličina entropije (ENT) je 128 do 256 bitova.


Nakon generiranja entropije, generira se zaštitna suma uzimajući prvih ENT/32 bitova od SHA256(ENT). Drugim riječima, izračuna se broj grupa od 32 bita (ENT/32) te se zatim uzme toliko bitova od SHA256 hasha entropije. Zaštitna suma doda se na kraj generiranih bitova entropije.


Ti se bitovi zatim podijele u grupe duljine 11 bitova. Svaka grupa predstavlja broj od 0 do 2047 koji predstavljaju indeks u listi riječi. Te se grupe zatim pretvaraju u riječi i to je generirani mnemonički kod.


Sljedeća tablica prikazuje odnos duljine entropije (ENT), duljine zaštitne sume (CS) te duljine generiranog mnemoničkog koda (MS) u riječima.


ENT
CS
ENT+CS
MS
128
4
132
12
160
5
165
15
192
6
198
18
224
7
231
21
256
8
264
24

 Lista riječi


Idealna lista riječi ima sljedeće karakteristike:
a) Pametan izbor riječi (dovoljno je upisati prva četiri slova riječi da bi se ona jednoznačno odedila)
b) Izbjegavaju se slične riječi
c) Sortirana lista riječi
Sve riječi moraju biti kodirane u UTF-8 formatu. Ovdje je lista takvih riječi.

 Korištenje mnemoničkog koda kao sjemena


Ako se generirani mnemonički kod želi koristit kao sjeme za hijerarhijski deterministički novčanik potrebno je koristiti funkciju PBKDF2. Mnemonički kod koristi se kao lozinka, salt je riječ “mnemonic” + lozinka, broj iteracija je 2048, a koristi se HMAC-SHA512.


Generiranje sjemena odvojeno je od generiranja koda.

Saturday, August 9, 2014

Kriptirani privatni ključevi (BIP38)


Privatne ključeve moguće je kriptirati tako da su zaštićeni lozinkom. Takav ključ može vidjti bilo tko, no samo osoba koja zna lozinku može ga dešifrirati. Takva zaštita pogodna je za kreiranje papirnatih novčanika i fizičkih bitcoina.


Postoje dva načina kriptiranja. Prvi omogućuje da se bilo koji privatni ključ zaštiti bilo kojom lozinkom. Drugi omogućuje dijeljeni ključ gdje jedna strana derivira međuključ iz lozinke, a druga strana derivira konačni ključ i adresu iz međuključa. Trošenje bitcoina moguće je jedino onome tko zna lozinku.


Uz svaki se kriptirani ključ sprema i hash rezultirajuće adrese koji služi za provjeru ispravnosti adrese.

Korištene funkcije


AES256Encrypt, AES256Decrpyt – šifriranje i dešifriranje pomoću AES šifre. Prima ključ od 256 bitova te 16 bajtova ulaza i deterministički daje 16 bajtova izlaza.
SHA256 – Algoritam za hashitanje koji uzima ulaz proizvoljne duljine te daje fiksni izlaz od 256 bitova (32 bajta).
Scrypt – Algoritam za deriviranje ključeva (engl. key derivation algorithm). Parametri: lozinka, salt, n, r, p, duljina. Kao izlaz daje niz znakova dužine parametra "duljina".
ECMultiply – množenje na krivulji secp256k1.
G, N – generator i red generatora eliptičke krivulje secp256k1.
Base58Check – alfanumerička baza 58 koja se koristi za enkodiranje bitcoin adresa.

Format kriptiranog ključa

  1. Ključ počinje prefiksom 0x0142 ili 0x0143 ovisno o tome je li korišteno množenje na eliptičkoj krivulji. Kad se na to primijeni Base58Check, korisnik će vidjeti 6P. Svaki kriptirani ključ počinje znakovima 6P. 6 zato da se razlikuje od normalnog privatnog ključa koji uvijek počinju brojem 5. Broj 6 znači da se radi o kriptiranom ključu koji se dekriptira pomoću metode P. P u ovom slučaju označuje lozinku (engl. Passphrase).
     
  2. 37 bajtova sadržaja:
    1. zastavica (1 bajt) označuje koristi li se množenje na krivulji ili ne
    2. zaštitna suma (4 bajta) SHA256(SHA256(očekivana_bitcoin_adresa))[0..3]
    3. 16 bajtova ovisno o množenju
    4. 16 bajtova AES šifrirani sadržaj (ovisi o množenju)

 Enkripcija bez množenja na eliptičkoj krivulji

 

Enkripcija:
  1. Izračunati bitcoin adresu i uzeti prva četiri bajta od SHA256(SHA256(adresa)). To je hash_adrese.
  2. Derivirati ključ iz lozinke pomoću funkcije scrypt s parametrima n=16384, r=8, p=8, duljina=64. Salt je hash_adrese. Podijeliti dobivena 64 bajta na dva dijela: polovica1 i polovica2.
  3. Napraviti AES256Encrypt(privatni_ključ[0..15] xor polovica1[0..15], polovica2). Rezultat je enkriptirana_polovica1.
  4. Napraviti AES256Encrypt(privatni_ključ[16..31] xor polovica1[16..31], polovica2). Rezultat je enkriptirana_polovica2.

Konačan je rezultat: Base58Check(0x01 0x42 + zastavica + salt + enkriptirana_polovica1 + enkriptirana_polovica2).

 Dekripcija:

  1. Uzeti enkriptirani ključ i lozinku.
  2. Izračunati polovica1 i polovica2 korištenjem algoritma scrypt predajući mu lozinku i hash_adrese.
  3. Izračunati enkriptirana_polovica1 i enkriptirana_polovica2 korištenjem AES256Decrypt.
  4. Iz privatnog ključa izračunati bitcoin adresu.
  5. Hashirati bitcoin adresu i provjeriti odgovara li hash_adrese.

Enkripcija s množenjem na eliptičkoj krivulji


Ovakav način enkripcije omogućuje da se kriptirani ključ generira poznavajući samo točku na eliptičkoj krivulji i salt koji je korisnik generirao bez poznavanja lozinke. Osoba koja zna lozinku naziva se vlasnik i ona generira jedan ili više međuključeva te i predaje osobi, pisaču, koja će generirati enkriptirani privatni ključ.
Enkriptirani privatni ključ može sadržavati broj čestice i redni broj. Zajedno su duljine 32 bita. Broj čestice je duljine 20 bitova, a redni broj 12 bitova.


Algoritam kojim vlasnik generira međuključ:

  1. Generirati 4 nasumična bajta salt_vlasnika
  2. Kodirati broj čestice i redni broj u big-endian formatu: čestica * 4096 + redni_broj. Ta se četiri bajta nazivaju čestica_redni broj.
  3. Konkatenirati salt_vlasnika i čestica_redni_broj. To se naziva entropija_vlasnika. Ako se ne koriste čestica i redni broj, entropija_vlasnika = salt_vlasnika.
  4. Generirati ključ iz lozinke pomoću algoritma scrypt duljine 32 bajta. Ti se bajtovi nazivaju predfaktor. Napraviti SHA256(SHA256(predfaktor + entropija_vlasnika)). To se naziva faktor_lozinke. Ako se ne koriste čestica i redni broj, faktor_lozinke je rezultat izvođenja algoritma scrypt.
  5. Pomnožiti faktor_lozinke s generatorom eliptičke krivulje te zapisati u kompresiranom formatu (33 bajta).
  6. Proslijediti rezultat množenja i salt_vlasnika pisaču.


Nakon što dobije međuključ od vlasnika, pisač provodi algoritam:

  1. Postavi zastavicu.
  2. Generira 24 nasumična bajta zvana sjemeb te napravi SHA256(SHA256()) nad njima. Rezultat se naziva faktorb.
  3. Pomnoži točku dobivenu od vlasnika sa faktoromb. Rezltat koristit kao javni ključ iz kojeg se izvede bitcoin adresa. To se zove generirana_adresa.
  4. SHA256(SHA256(generirana_adresa))[0..3] = hash_adrese
  5. scrypt(sjemeb) duljine 64 bajta, salt je hash_adrese + entropija_vlasnika
  6. Podijeliti dobivena 64 bajta na dva dijela: polovica1 i polovica2.
  7. Napraviti AES256Encrypt(sjemeb[0..15] xor polovica1[0..15], polovica2). Rezultat je enkriptirana_polovica1.
  8. Napraviti AES256Encrypt(enkriptirana_polovica1[8..15] + sjemeb[16..23] xor polovica1[16..235], polovica2). Rezultat je enkriptirana_polovica2.

Za konačan rezultat potrebno je napraviti Base58Check od 0x01 0x43 + zastavica + hash_adrese + entropija_vlasnika + enkriptirana_polovica1[0..7] + enkriptirana_polovica2.

Dekripcija:

  1. Prikupiti enkriptirani privatni ključ i lozinku od korisnika.
  2. Dobiti faktor_lozinke pomoću algoritma scrypt koristeći salt_vlasnika i lozinku.
  3. Dobiti ključ za dekripciju za sjemeb koristeći scrypt sa hash_adrese, entropija_vlasnika i rezultatom iz prethodnog koraka.
  4. Dekriptirati enkriptirana_polovica2 pomoću AES256Decrpyt da se dobije početnih 8 bajtova sjemeb i završnih 8 bajtova za enkriptirana_polovica1.
  5. Dekriptirati enkriptirana_polovica1 da se dobije ostatak sjemeb.
  6. Iz sjemeb izvesti faktorb.
  7. Pomnožiti faktor_lozinke i faktorb da se dobije privatni ključ povezan s generirana_adresa.
  8. Iz privatnog ključa izvesti bitcoin adresu.
  9. Provjeriti odgovara li hash_adrese.











Thursday, June 26, 2014

Hijerarhijski deterministički novčanici (BIP32)


Bitcoin novčanici mogu se podijeliti u dvije generacije. Prva generira privatne ključeve nasumično, tj. nedeterministički (npr. Bitcoin client ili Multibit). Novčanici druge generacije privatne ključeve generiraju iz jednog alfanumeričkog niza znakova, tzv. sjemena (npr. Electrum). Prednost takvih novčanika je što se ne mora raditi backup svakog ključa nego je dovoljno napraviti backup samo sjemena iz kojeg se zatim deterministički generiraju privatni i odgovarajući javni ključevi.

 Hijerarhijski deterministički novčanici

 

HD novčanici temelje se na matematici eliptičkih krivulja. Tipovi podataka koji se koriste su: cijeli brojevi (modulo red krivulje), koordinate točaka na krivulji i nizovi bajtova. Funkcije koje će se koristiti su (|| označuje konkatenaciju):


  • point (p) – vraća koordinate točke koja se dobije množenjem broja p generatorom krivulje G.
  • ser32(i) – serijalizira 32-bitni cijeli broj bez predznaka kao niz od 4 bajta, najznačajniji bajt prvi
  • ser256(p) – serijalizira cijeli broj p kao niz od 32 bajta, najznačajniji bajt prvi
  • serP(P) – serijalizira točku P kao niz bajtova koristeći SEC1 kompresirani oblik: serP(P) = (0x02 ili 0x03) || ser256(x)
  • parse256(p) – interpretira niz od 32 bajta kao 256-bitni broj, najznačajniji bajt prvi
     
U HD novčanicima koriste se tzv. prošireni ključevi. Ključevi su prošireni s dodatnih 256 bitova entropije i ta se ekstenzija naziva chain code te se označuje sa "c". Prošireni privatni ključ je tad par (k, c) gdje je k uobičajeni privatni ključ, a c je ekstenzija od 256 bitova. Javni ključ je (K, c) gdje je K uobičajeni javni ključ, K = point(k), a c je chain code koji može biti isti ili različit od roditeljskog.

Svaki prošireni ključ ima 231 normalnih potključeva (ključeva djece) i 231 ojačanih potključeva. Normalni potključevi koriste indekse od 0 do 231 – 1, a ojačani od 231 do 232 – 1. Drugačije zapisano, normalni potključevi su od (k, 0) do (k, 231 – 1), a ojačani od (k, 231) do (k, 232 – 1). Odnosno, chain code ojačanih ključeva počinje bitom 1. Vidimo da svaki prošireni ključ može imati 232 ključeva djece, odnosno 4 294 967 296 potključeva.

Derivacija ključeva djece


HD novčanik stablasta je struktura koja omogućuje da se potključevi (ključevi djeca) deriviraju iz ključeva roditelja. Iz privatnog roditeljskog ključa moguće je izvesti privatni ključ dijete, iz javnog roditeljskog ključa javni ključ dijete te iz privatnog roditeljskog ključa javni ključ dijete.

Funkcije za deriviranje temelje se na HMAC-SHA512 te koriste indeks koji se označuje s "i". HMAC prima dva parametra ključ (Key) i podatke (Data) Derivacije ovise o tome radi li se o normalnom potključu ili o ojačanom.

Privatni roditeljski ključ  → privatni ključ dijete


Funkcija CKDpriv (child key derivation) izračunava prošireni privatni potključ iz proširenog privatnog roditeljskog ključa: CKDpriv((kpar, cpar), i) → (ki, ci).

 
Algoritam:
  • Provjeri je li i ≥ 231 (želimo li derivirati normalan ili ojačani potključ)
    • Ako je, I = HMAC-SHA512(ključ = cpar, podaci = 0x00 || ser256(kpar) || ser32(i))
    • Ako nije, I = HMAC-SHA512(ključ = cpar, podaci = serP(point(kpar)) || ser32(i))
  • Podijeli I na dva dijela po 32 bita IL te IR
  • Dijete ključ je ki = parse256(IL) + kpar
  • Novi chain code je IR
  • Ako je parse256(IL) ≥ n ili ki = 0, uzmi novi i


Iz jednog proširenog roditeljskog privatnog ključa moguće je dobiti 232 privatnih ključeva djece. Polovica tih ključeva su normalni, a polovica ojačani. Iz tih se ključeva zatim može derivirati daljnih 232 ključeva itd.

Javni roditeljski ključ  javni ključ dijete

 

Ojačane ključeve djecu nemoguće je ovako derivirati. Ovaj algoritam derivira samo normalne ključeve i < 231. Algoritam CKDpub((Kpar, cpar), i):
  • I = HMAC-SHA512(ključ = cpar, podaci = serP(Kpar) || ser32(i))
  • Podijeli I na dva dijela po 32 bita IL te IR
  • Dijete ključ je Ki = point(parse256(IL)) + Kpar
  • Novi chain code je IR
  • Ako je parse256(IL) ≥ n ili je Ki točka u beskonačnosti , uzmi novi i

Iz ovog je vidljivo da je moguće generirati javne podključeve bez generiranja privatnih ključeva. Odgovarajuće privatne ključeve moguće je generirati naknadno.

Privatni roditeljski ključ  javni ključ dijete



Iz proširenog se privatnog ključa dobiva prošireni javni ključ na sljedeći način:
  • N(k, c) = (point(k), c) gdje je c chain code iz privatnog ključa


Za dobivanje javnog ključa djeteta iz privatnog roditeljskog ključa primjenjuje se jedna od dvije funkcije:


  • N(CKDpriv(kpar, cpar), i) za sve ključeve
  • CKDpub(N(kpar, cpar), i) samo za normalne ključeve


Kod korištenja ključeva u aplikaciji, chain code se zanemaruje.





Friday, May 23, 2014

Standardne transakcije


U Bitcoinu (verziji klijenta 0.9) postoji pet vrsta standardnih transakcija koje se razvrstavaju prema formatu izalza. Tih pet vrsta su: plaćanje na javni ključ (pay to public key, P2PK), plaćanje na hash javnog ključa (pay to publick key hash, P2PKH), plaćanje na hash skripte (pay to script hash, P2SH), višepotpisna transakcija te null transakcija

Plaćanje na javni ključ (P2PK)


Ovakav se način plaćanja izbjagava jer nije siguran. Koristi se jedino u coinbase transakcijama kad rudaru treba isplatiti nagradu za točno riješen blok.

scriptSig: <sig>
scriptPubKey: <pubKey> OP_CHECKSIG

Plaćanje na hash javnog ključa (P2PKH)


Ovo je najčešći način plaćanja. Ne koristi se direktno javni ključ nego bitcoin adresa (hash javnog ključa).

scriptSig: <sig> <pubKey>
scriptPubKey: OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG


Plaćanje na hash skripte (P2SH)

Ovo je kompleksniji način plaćanja od gornja dva. Umjesto hash javnog ključa u skripti se nalazi hash druge skripte. Onaj tko hoće potrošiti bitcoine iz takve tranaskcije, mora umjesto javnog ključa dati skriptu koja kad se hashira, odgovara hashu iz potpisa.

scriptSig: <sig><redeemscript>
scriptPubKey: OP_HASH160 <redeemscripthash> OP_EQUAL

Višepotpisna transakcija (multisig)

Transakcije za koje je potrebno m od n potpisa da bi ih se moglo potrošiti.

scriptSig: <sig1> <sig2>
scriptPubKey: OP_2 <pubKey1> <pubKey2> <pubKey3> OP_3 OP_CHECKMULTISIG

Null transakcija

Tranaskcija koja se ne može potrošit inego je označana kao nevaljala. U nju je moguće dodati malu količinu podataka koju određeni klijenti mogu interpretirati. Tako rade protokoli izgrađeni na bitcoinu, npr. Colored coins.

scriptSig: OP_RETURN <data>


Sve su ostale transakcije nestandardne. To znači da ako izlaz nije u jednom od pet gorenabrojenih formata, rudari neće prihvaćati niti rudariti takve transakcije.

 

 

 



Saturday, May 17, 2014

Naprednije Bitcoin skripte

Transakcija s više potpisa



Transakcije s više potpisa (engl. multisignature/multisig) zathijevaju više od jednog ključa (potpisa) da se pristupi bitcoinima, npr. dva od tri.


Primjer 2-od-3: scriptSig: <sig1> <sig2>
scriptPubKey: OP_2 <pubKey1> <pubKey2> <pubKey3> OP_3 OP_CHECKMULTISIG


Za ovu je transakciju potrebno dva od tri potpisa. Prva transakcija ima dva potpisa koji su potrebni za otključavanje sredstava na adresi. Za transakciju s više potpisa scriptPubKey dio ima posebnu konstrukciju. Prvo se navodi koliko je potpisa potrebno za otključavanje, zatim javni ključevi (ne hashevi kao kod standardnih), koliko tih ključeva ima te na kraju naredba za provjeru potpisa.


Stog
Naredba
Opis
<sig2>
<sig1>

Potpisi se stavljaju na stog.
<2>
<sig2>
<sig1>

Dodaje se broj potpisa potreban za otključavanje.
<pubKey3>
<pubKey2>
<pubKey1>
<2>
<sig2>
<sig1>

Dodaju se javni ključevi pomoću koji se verificiraju potpisi. Potpisi i ključevi verificiraju se u parovima.
<3>
<pubKey3>
<pubKey2>
<pubKey1>
<2>
<sig2>
<sig1>
OP_CHECKMULTISIG
Dodaje se broj javnih ključeva. Sad su na stogu svi potrebni ulazi za provjeru transakcije.
<1>

Na stogu je rezulat izvršavanja OP_CHECKMULTISIG naredbe

 
Tehnički gledano, OP_CHECKMULTISIG zbog buga uzima jedan parametar previše te se u scriptSig prije potpisa dodaje OP_0 kao lažni parametar.

Odd/Event Bet



Slijedi prijmjer kompleksne skripte koja nasumično izvršava podskripte. Može se, na primjer, koristiti za nasumično određivanje koji korisnik plaća naknadu na transakciju.


Naredba OP_2DUP duplira dva elementa s vrha stoga. OP_SWAP zamijeni dva elementa s vrha stoga. OP_LEFT zadrži samo n lijevih znakova. OP_ADD zbraja dva elementa s vrha stoga. OP_MOD je ostatak pri dijeljenju gornja dva elementa stoga.


Primjer: scriptSig: <Sig><pubKey>
scripPubKey: <7bb...><5aa...> OP_2DUP OP_HASH160 <aHash> OP_EQUALVERIFY OP_HASH160 <bHASH> OP_EQUALVERIFY OP_1 OP_LEFT OP_SWAP OP_1 OP_LEFT OP_ADD OP_2
OP_SWAP OP_MOD
OP_IF
     OP_DUP OP_HASH160 <pubKeyAHash> OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
     OP_DUP OP_HASH160 <pubKeyBHash> OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

 
Stog
Naredba
Opis
<5aa...>
<7bb...>
<pubKey>
<sig>
OP_2DUP
Na stog se prvo stavljaju svi elementi i gornja se dva dupliraju.
<5aa...>
<7bb...>
<5aa...>
<7bb...>
<pubKey>
<sig>
OP_HASH160
Hashiranje vrha stoga
<aHash>
<aHash>
<7bb...>
<5aa...>
<7bb...>
<pubKey>
<sig>
OP_EQUALVERIFY
Dodavanje hasha i provjera jesu li jednaki
<7bb...>
<5aa...>
<7bb...>
<pubKey>
<sig>
OP_HASH160
Hashiranje vrha stoga
<bHash>
<5aa...>
<7bb...>
<pubKey>
<sig>

Dodavanja hasha na stog
<bHash>
<bHash>
<5aa...>
<7bb...>
<pubKey>
<sig>
OP_EQUALVERIFY
Provjera jesu li jednaki
<5aa...>
<7bb...>
<pubKey>
<sig>

Dodaje se 1 na stog
<1>
<5aa...>
<7bb...>
<pubKey>
<sig>
OP_LEFT
Uzima se <1> znak hash <5aa...>
<5>
<7bb...>
<pubKey>
<sig>
OP_SWAP
Zamijena dva gornja elementa
<7bb...>
<5>
<pubKey>
<sig>

Na stog se dodaje <1>
<1>
<7bb...>
<5>
<pubKey>
<sig>
OP_LEFT
Uzima se <1> znak hash <7bb...>
<7>
<5>
<pubKey>
<sig>
OP_ADD
Gornja se dva elementa zbrajaju
<12>
<pubKey>
<sig>

Dodaje se 2
<2>
<12>
<pubKey>
<sig>
OP_SWAP
Zamjena
<12>
<2>
<pubKey>
<sig>
OP_MOD
Ostatak pri dijeljenju <12> s <2>
<0>
<pubKey>
<sig>
OP_IF
Ako je na vrhu element isitni != 0 izvrši sljedeću naredbu
<pubKey>
<sig>
OP_ELSE
Ako nije (=0)
<pubKey>
<sig>
OP_DUP OP_HASH160 <pubKeyBHash> OP_EQUALVERIFY OP_CHECKSIG
Izvrši ovo

 
Ova skripta ne može se zapravo izvršiti budući da su naredbe OP_LEFT i OP_MOD onemogućene. Ovdje je stavljena samo kao primjer kompleksne skripte.

Thursday, May 15, 2014

Matematika ključeva


Javni i privatni ključevi u Bitcoin protokolu generiraju se pomoću eliptičke krivulje. To su specijalne krivulje trećeg stupnja definirane nad nekim poljem i najčešći im je oblik:

(1)  y2 = x3 + ax + b


Gdje su a, b, x, y elementi nekog polja (realnih brojeva, kompleksnih brojeva, racionalnih brojeva itd.). Za potrebe kriptografije eliptičke se krivulje definiraju nad konačnim poljima Fp. To su polja koja za razliku od prije navedenih imaju konačan broj elemenata p. U kriptografiji p je najčešće neparan prost broj. Tako se jednadžba (1) pretvara u:

(2)  (y2 = x3 + ax + b) mod p

Eliptička krivulja koja se koristi u protokolu Bitcoin ima službeni naziv secp256k1 te 
ima jednadžbu:

(3)  (y2 = x3 + 7) mod p

Parametri krivulje šest su elemenata T = (p, a, b, G, n, h).

p je veličina konačnog polja nad kojim je krivulja definirana. U ovom je slučaju p = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 odnosno u heksadecimalnom obliku p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
a i b su već opisani koeficijenti jednadžbe: a = 0, b = 7.

G je točka generator eliptičke krivulje, slično generatoru cikličke grupe. Ciklička grupa je grupa koju je moguće generirati iz jednog njezinog elementa. Takav element naziva se generator grupe i označava s g. Ostali se elementi generiraju potenciranjem generatora: gn, n Є [0, p - 1] gdje je p broj elemenata u grupi (veličina polja). Za secp256k1:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Analogno cikličkoj grupi, sve se točke mogu izvesti iz generatora eliptičke krivulje. Mogu se prikazati u dva oblika, kompresiranom i nekompresiranom. To se prepoznaje prema broju na početku generatora. Ako je broj 0x04 kao u gornjem primjeru znači da je format nekompresiran, a ako je broj 0x02 ili 0x03 radi se o kompresiji. U gornjem je primjeru x koordinata točke generatora 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798, a y
483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8.

n je red generatora, odnosno broj koji zadovoljava jednadžbu:

(4) n ∙ G = 0 (mod p)

U ovom je primjeru n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.

Parametar h je kofaktor, omjer broja točaka na eliptičkoj krivulji i reda generatora te iznosi h = 1.

Generiranje ključeva



Privatni ključ d koji se koristi za pristup sredstvima na adresi je slučajno odabrani element iz intervala [1, n – 1] gdje je n red generatora:

(5) d Є [0, FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364140]

Javni ključ Q dobiva se iz privatnog ključa d pomoću generatorske točke na krivulji:

(6) Q = d ∙ G (mod p)

Dakle javni ključ Q je zapravo točka na krivulji dobivena matematičkom operacijom množenja. Glavna karakteristika ovakvog množenja je da je ono ireverzibilno. Poznajući Q i G nemoguće je dobiti privatni ključ d.

Jednadžba (6) preciznije napisana je:

(7)  Q = d ∙ (xG, yG) = (xQ, yQ)

Koordinate ključa veličine su 32 bajta. U protokolu Bitcoin te se koordinate konkateniraju i dobiva se javni ključ veličina 64 bajta. On se zatim hashiranjem pretvara u adresu na koju se primaju bitcoini.

Sunday, May 11, 2014

Osnove Bitcoin skripti


Transakcije u Bitcoin protokolu temelje se na skriptama. Skripte su niz instrukcija pisanih u Bitcoinovom skriptnom jeziku Script. Script je modeliran prema programskom jeziku Forth. Temelji se na stogu i izvršava s lijeva nadesno. To znači da se svaki podatak, ulaz ili izlaz, stavlja na stog. Script ne podržava petlje.

Skripte opisuju kako osoba na koju se prenose bitcoini može tim bitcoinima pristupiti. Osoba koja želi potrošiti bitcoine mora osigurati dvije stvari: javni ključ koji kad se hashira podudara s adresom odredišta u skripti i potpis kojim dokazuje privatni ključ koji je vezan uz tu adresu.

Transakcija je ispravna ako se skripta uspješno izvrši i vrijednost na vrhu stoga je različita od nule (istinita). Osoba koja šalje bitcoine određuje uvjete pod kojima se oni prenose primatelju. Primatelj mora dati ulaze pošiljateljevoj skripti kako bi ona nakon izvršavanja dala istinit rezultat.


Primjeri skripti


 
Script sadrži nekoliko desetaka različitih naredbi. Ovdje će biti opisane samo one najčešće korištene.

Primjer transakcije:

{
  "hash":"7c40250...",
  "ver":1,
  "vin_sz":1,
  "vout_sz":1,
  "lock_time":0,
  "size":224,
  "in":[
   {
     "prev_out":{
       "hash":"2007aec...",
       "n":0
     },
   "scriptSig":"signature"
  }
],
"out":[
  {
   "value":"0.31900000",
   "scriptPubKey":"script"
   }
  ]
}


Detalji transakcije opisani su ovdje i ovdje. U ovom će se postu opisivati boldani dijelovi.

Skripta se sastoji od dva dijela: scriptSig i scriptPubKey. scriptSig najčešće prima dva parametra <sig> i <pubKey>, odnosno javni ključ (ne adresu) novog vlasnika i ECDSA potpis hasha prethodne transakcije od koje je sadašnji vlasnik dobio bitcoine. scriptPubKey sadrži instrukcije kako tim bitcoinima pristupiti.

 Nepotrošiva transakcija



Najjednostavniji primjer transakcije je nepotrošiva transakcija ili nul-transakcija.


Primjer: scriptSig: OP_RETURN
             scriptPubKey: .....
 
Stog
Naredba
Opis
Prazan
OP_RETURN
Neispravna transakcija

Naredba OP_RETURN označuje transakciju kao neispravnu i što god se nalazilo u scriptPubKey dijelu neće se moći izvršiti. Ovakav oblik transakcije koristi se često ako se u lanac blokova samo želi pohraniti neki podatak. Nakon naredbe OP_RETURN u polje se mogu zapisati podaci koji neće imati nikakvo značenje za bitcoin klijente. Takve se transakcije koriste npr. u platformi Counterparty.

Bilotko može potrošiti


Primjer: scriptSig: (prazno)
             scriptPubKey: OP_TRUE


Stog
Naredba
Opis
Prazan
OP_TRUE
Stavlja 1 na stog
1

Transakcija ispravna

 
Ako transakcija nema javni ključ primatelja, bilo tko je može potrošiti. OP_TRUE označuje logičku istinu. Točnije na stog se stavlja broj 1. Budući da su u Scriptu sve vrijednosti istina osim nule, ovo označuje da je rezultat izvršavanja transakcije istinit te da se bitcoini smiju prebaciti novom vlasniku.

Coinbase transakcija



Ovo je pojednostavljeni primjer općenite transakcije. Coinbase transakcija donosi nagradu rudaru koji je uspješno izrudario prethodni blok.


Primjer: scriptSig: <sig>
             scriptPubKey: <pubkey> OP_CHECKSIG


Stog
Naredba
Opis
<pubKey>
<sig>
OP_CHECKSIG
Provjerava ispravnost potpisa koristeći javni ključ novog vlasnika
1

Potpis ispravan


Na stog se stavljaju digitalni potpis hasha transakcije koja prenosi bitcoine rudaru i njegov javni ključ. Ako naredba OP_CHECKSIG vrati istinu, transakcija je uspješno izvršena te rudar može preuzeti nagradu.

Osnovna transakcija



Ovo je primjer transakcije s jednim ulazom i jednim izlazom.


Primjer: scriptSig: <sig><pubKey>
             scriptPubKey: OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG


scriptSig dio sadrži već poznati potpis i javni ključ novog vlasnika. scriptPubKey je nešto složeniji i sastoji se od nekoliko koraka. OP_DUP kopira element s vrha stoga. OP_HASH160 hashira element s vrha stoga dva puta, prvo sa SHA256, a zatim s RIPEMD160. OP_EQUALVERIFY su dvije naredbe u jednoj: OP_EQUAL pa zatim OP_VERIFY. Prva vraća 1 (istinu) ako su najgornja dva elementa na stogu jednaka. Druga verificira rezultat, tj. označuje transakciju kao neispravnu ako gornji element nije istinit.


Stog
Naredba
Opis
<pubKey>
<sig>
OP_DUP
Kopira element s vrha stoga.
<pubKey>
<pubKey>
<sig>
OP_HASH160
RIPEMD160(SHA256(pubKey))
<pubKeyHash>
<pubKeyHash2>
<pubKey>
<sig>

Na stog se stavlja bitcoin adresa na koju se šalje (hash javnog ključa)

<pubKeyHash>
<pubKeyHash2>
<pubKey>
<sig>
OP_EQUALVERIFY
Provjerava jesu li hash javnog ključa iz ulaza i bitcoin adresa isti
<pubKey>
<sig>
OP_CHECKSIG
Provjerava potpis pomoću javnog ključa
OP_TRUE

Transakcija je ispravna

 
Za transakciju iz prethodnog primjera parametri su:


scriptSig: <304502205014856cdf89da70ad9a4f223bac4e5477da5c6cb69ef2
b9f8b5f8548e21307e0221009bfe2698f1eb1c561f41981d8e78c11d9e685a70
e682f144ee6c8ab5ecb0497c01> <042b2d8def903dd62d0c4161ed8d4ccfa5967e11a28e65cb141235b7c27d8e
f6aa3bd63be077323cf3d7e0e8895b264b94feb4b40478b431da6f45dfc8e1004f62>
  
scriptPubKey: OP_DUP OP_HASH160 a7db6ff121871c65a8924b8e40f160d385515ad7 OP_EQUALVERIFY OP_CHECKSIG

 Blok geneze



Skripta za genesis blok: scriptSig: prazno
                                      scripPubKey: OP_HASH256 <hash> OP_EQUAL


Da bi se transakcija potrošila potrebno je naći niz znakova koji kad se dva puta hashiraju daju određeni hash (6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000).


Stog
Naredba
Opis
Prazan

Na stog je potrebno staviti podatke koji će zadovoljiti hash
<data>
OP_HASH256
Podaci se dva puta hashiraju
<hash>
<data_hash>

Na stogu su generirani hash i hash koji je potrebno izračunati (6fe...)
<hash>
<data_hash>
OP_EQUAL
Provjeri zadovoljava li generirani hash zadani hash
OP_TRUE

Transakcija ispravna

 
Detaljan popis Script naredbi nalazi se ovdje.

Thursday, May 1, 2014

Anonimnost u protokolu Bitcoin


Ponekad se može pročitati da je bitcoin anonimna valuta, odnosno anoniman sustav za plaćanje. Koliko je zapravo Bitcoin anoniman? Osnovna karakteristika Bitcoina je da su sve transakcije u sustavu vidljive svima. S druge strane, sudionici sustava ne moraju odavati svoj identitet ostalima kako bi mogli sudjelovati u sustavu. Koliko se može zaključiti o sudionicima sustava analizirajući transakcije i block chain?


Fergal Reid i Martin Harrigan objavili su prvo istraživanje anonimnosti u sustavu Bitcoin [1]. Istraživali su navodnu krađu 25.000 bitcoina objavljenu na forumu BitcoinTalk. Prije istraživanja Reid i Harrigan smatrali su da će biti vrlo teško ili čak nemoguće pratiti kretanje određene svote novca kroz sustav jer su pretpostavljali da će se transakcije vrlo brzo izgubiti u mreži. Istraživanje je pokazalo da je u detalje moguće pratit kretanje određenog iznosa bitcoina između korisnika u mreži.


U [2] su Dorit Ron i Adi Shamir objavili analizu block chaina iz svibnja 2012. Zanimalo ih je kretanje bitcoina kroz mrežu te procjena broja bitcoin korisnika. Analiza je pokazala da je broj korisnika oko dva i pol milijuna. Pokazano je i da se kroz mrežu većinom prenose mali iznosi bitcoina, no i da postoji oko 300 tranaskcija s >50 000 bitcoina (od kojih je većina potekla od jedne transakcije od 90 000 BTC-a). Identificirane su adrese koje pripadaju velikim mjenjačnicama te je oktriveno da većina bitcoina, 75%, ne napušta adresu jednom kad stigne na nju. Koristili su se dvjema metodama: prva je da su pretpostavili da ako transakcija prebacuje sredstva s dvaju (ili više) adresa na novu adresu, te adrese moraju biti u vlasništvu iste osobe (rafinirali su metodu koju su koristili Reid i Harrigan). Druga je da su pokušali otkriti change adrese, adrese na koje se vraća ostatak bitcoina nakon transfera, a koje nisu uvijek iste polaznoj adresi no pripadaju istom vlasniku.


Elli Androulaki et al. proveli su istraživanje početkom 2013. u dva dijela [3]. Prvi dio je bio gotovo identičan goreopisanim analizama. U drugom su dijelu konstruirali složene modele i simulator za koji tvrde da vjerno simulira kako korisnici upotrebljavaju bitcoin u stvarnom životu. Rezultati simulatora pokazuju da je moguće utvrditi geografsku povezanost korisnika (npr. korištenje bitcoina u fizičkim dućanima).


Zaključak ovih istraživanja je da iako istraživači nisu uspjeli otkriti identitet niti jednog pojedinca, uspjeli su detaljno pratit kretanja bitcoina kroz mrežu, otkriti koji skupovi adresa pripadaju kojim mjenjačnicama te su čak uspjeli (barem teoretski) geografski povezati korisnike protokola Bitcoin. Čini se da je Bitcoin ipak dovoljno anoniman, no može li se ta anonimnost još poboljšati?


Već je sam Satoshi u svom radu predložio da se radi povećanja anonimnosti za svaku transakciju generira nova adresa i pripadajući tajni ključ. To može sakriti podatak tko šalje bitcoine, ali se još uvijek može vidjeti kome ti bitcoini idu. Problem skrivanja kome se šalju bitcoini može se riješiti korištenjem tzv. mixing services. Te usluge dozvoljavaju da im korisnici pošalju bitcoine i adresu na koju žele da ti bitcoini stignu. Usluga će zatim od svakog korisnika uzeti malo bitcoina (sve do iznosa koji korisnik želi poslati nekome) te ukupan iznos poslati na odabranu adresu. To omogućuje skrivanje relacije između adresa koje šalju bitcoine i adresa koje primaju bitcoine. Nedostatak je u tome što korisnik mora vjerovati centraliziranoj usluzi da će dobro i pošteno izmiješati bitcoine. Problem je i u tome što suluga mora imati dovoljan broj korisnika da bi mogla uspješno pomiješati bitcoine inače ih je moguće pratiti [4][5]. Također, ako se pošalje velik iznos bitcoina, vjerojatno je da se oni neće dobro izmiješati te će ih opet biti moguće pratiti kroz mrežu.


Uz nabrojene mogućnosti postoje i ZeroCoin i ZeroCash sustavi koji koriste tzv. zero knowledge dokaze te pružaju mogućnost distribuiranog "pranja novca" unutar samog Bitcoin protokola. Takvi sustavi mogu značajno poboljšati anonimnost transakcija, no još su u razvoju te se ne zna kakva će im biti budućnost.

Zaključak

 

Napravljeno je nekoliko istraživanja na temu anonimnosti protokola Bitcoin. Iako niti u jednom slučaju istraživačni nisu identificirali pojedince koji slali bitcoine, pokazali su da je poznavaljem makar jednog identiteta moguće detaljno pratiti njegove transakcije i otkriti koje adrese su u njegovom vlasništvu. Za Bitcoin korisnike koji žele više anonimnosti nego što sustav pruža po defaultu, preporučljivo je za svaku transakciju generirati nove adrese i korsitit pouzdane mixing usluge.

Literatura

 

[1] Fergal Reid and Martin Harrigan, An Analisys of Anonymity in the Bitcoin System. arXiv:1107.4524v2 [physics.soc-ph], 2012 http://arxiv.org/abs/1107.4524

[2] Dorit Ron and Adi Shamir, Quantitative Analysis of the Full Bitcoin Transaction Graph. 2012

[3] Elli Androulaki , Ghassan O. Karame , Marc Roeschlin, Tobias Scherer i Srđan Capkun, Evaluating User Privacy in Bitcoin. 2013

[4] Malte Möser, Anonymity of Bitcoin Transactions: An Analysis of Mixing Services, 2013

[5] Malte Möser, Rainer Böhme, Dominic Breuker , An Inquiry Into Money Loundering Tools in the Bitcoin Network, 2013