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.