Sunday, February 19, 2017

Verificiranje potpisa transakcija za programe svjedočanstva verzije 0 (BIP143)


Originalni način hashiranja transakcije za potpisivanje ima složenost O(n2). Prosječno vrijeme verificiranja transakcija u bloku veličine 1MB je 2sekunde, dok u nekim slučajevima to vrijeme doseže 25 sekundi. Cilj novog algoritma je smanjiti složenost na O(n) uvođenjem međustanja koja su ista za sve ulaze transakcije.

Novi algoritam za hashiranje transakcije za potpisivanje je dvostruki SHA256 vrijednosti:
  1. nVersion
  2. hashPrevouts
  3. hashSequence
  4. outpoint
  5. scriptCode ulaza
  6. vrijednost izlaza koju ovaj ulaz troši
  7. nSequence ulaza
  8. hashOutputs
  9. nLocktime
  10. sighash
1, 4, 7, 9 i 10 imaju isto značenje kao i do sad.
Broj 5:
  • U slučaju P2WPKH scriptCode je 0x19761914{20 bajtova hasha javnog ključa}88ac
  • U slučaju P2WSH scriptCode je redeemScript.
Broj 6 je 8 bajtova koji predstavljaju iznos koji ovaj ulaz troši.
hashPrevouts:
  • Ako zastavica ANYONECANPAY nije postavljena, hashPrevouts je dvostruki SHA256 serijaliziranih outpointova u ulazima.
  • U suprotnom je vrijednost ovog polja 0x000…000 (256-bitova 0).
hashSequence:
  • Ako zastavica ANYONECANPAY, SINGLE ili NONE nije postavljena, hashSequence je dvostruki SHA256 serijalizacije nSequence polja svih ulaza.
  • U suprotnom je vrijednost ovog polja 0x000…000 (256-bitova 0).
 
hashOutputs:
  • Ako zastavice SINGLE ili NONE nije postavljena, hashOutputs je dvostruki SHA256 serijalizacije svih izlaza (iznos + scriptPubKey).
  • Ako je zastavica SINGLE postavljena, a indeks ulaza je manji od broja izlaza, hashOutputs je dvostruki SHA256 iznosa izlaza + scriptPubKey odgovarajućeg izlaza.
  • U suprotnom je vrijednost ovog polja 0x000…000 (256-bitova 0).
Polje hashPrevouts, hashSequence i hashOutputs mogu se ponovno koristiti za sve ulaze te ih je dovoljno računati samo jednom. Kompleksnost postupka se tako smanjuje s O(n2) na O(n).
Za P2WPKH i P2WSH koriste se samo kompresirani javni ključevi.

Primjer

P2WPKH

Transakcija koju treba potpisati:
nVersion: 01000000
txin: 02
fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f
00000000 00 eeffffff
ef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a
01000000 00 ffffffff
txout: 02 202cb20600000000
1976a9148280b37df378db99f66f85c95a783a76ac7a6d5988ac
9093510d00000000
1976a9143bde42dbee7e4dbe6a21b2d50ce2f0167faa815988ac
nLockTime: 11000000
Prvi ulaz pripada P2PK transakciji:
scriptPubKey: 2103c9f4836b9a4f77fc0d81f7bcb01b7f1b35916864b9476c241ce9fc198bd25432ac vrijednost: 6.25
privatni ključ: bbc27228ddcb9209d7fd6f36b02f7dfa6252af40bb2f1cbc7a557da8027ff866
Drugi ulaz pripada P2WPKH transakciji:
scriptPubKey: 00141d0f172a0ecb48aee1be1f2687d2963ae33f71a1 value: 6
privatni ključ: 619c335025c7f4012e556c2a58b2506e30b8511b53ade95ea316fd8c3286feb9
javni ključ: 025476c2e83188368da1ff3e292e7acafcdb3566bb0ad253f62fc70f07aeee6357
Algoritam se provodi za svaki ulaz transakcije. Potpisivat će se sa SIGHASH_ALL zastavicom.
hashPrevouts: dSHA256(fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad9
69f00000000ef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b
90ec68a01000000) =
96b827c8483d4e9b96712b6713a7b68d6e8003a781feba36c31143470b4efd37
hashSequence:
dSHA256(eeffffffffffffff) = 52b0a642eea2fb7ae638c36f6252b6750293dbe574a806984b8e4d8548339a3b
hashOutputs:
dSHA256(202cb206000000001976a9148280b37df378db99f66f85c95a783a76ac7
a6d5988ac9093510d000000001976a9143bde42dbee7e4dbe6a21b2d50ce2f0167f
aa815988ac) =
863ef3e1a92afbfdb97f31ad0fc7683ee943e9abcf2501590ff8f6551f47e5e5
Prethodne se tri vrijednosti izračunavaju samo jednom i koriste u svim ulazima.
Za prvi ulaz transakcija koja će se hashirati da bi se potpisala izgleda ovako:
nVersion: 01000000
hashPrevouts: 96b827c8483d4e9b96712b6713a7b68d6e8003a781feba36c31143470b4efd37
hashSequence: 52b0a642eea2fb7ae638c36f6252b6750293dbe574a806984b8e4d8548339a3b
outpoint: fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f00000000
scriptCode: 197614dcea56a687796f1038e2598cc256b627f49f823b88ac
amount: 40be402500000000
nSequence: eeffffff
hashOutputs: 863ef3e1a92afbfdb97f31ad0fc7683ee943e9abcf2501590ff8f6551f47e5e5
nLockTime: 11000000
nHashType: 01000000
outpoint je hash prethodne transakcije i indeks izlaza na koju se ovaj ulaz referencira.
Scriptcode sadrži HASH160 javnog ključa P2PK transakcije.
Amount je heksadecimalni little-endian iznosa 6.25 kojeg taj ulaz troši.
Potpis te transakcije je 30450221008b9d1dc26ba6a9cb62127b02742fa9d754cd3bebf337f7a55d114c8e5
cdd30be022040529b194ba3f9281a99f2b1c0a19c0489bc22ede944ccf4ecbab4cc6
18ef3ed
Za drugi ulaz:
nVersion: 01000000
hashPrevouts: 96b827c8483d4e9b96712b6713a7b68d6e8003a781feba36c31143470b4efd37
hashSequence: 52b0a642eea2fb7ae638c36f6252b6750293dbe574a806984b8e4d8548339a3b
outpoint: ef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a01000000
scriptCode: 1976a9141d0f172a0ecb48aee1be1f2687d2963ae33f71a188ac
amount: 0046c32300000000
nSequence: ffffffff
hashOutputs: 863ef3e1a92afbfdb97f31ad0fc7683ee943e9abcf2501590ff8f6551f47e5e5
nLockTime: 11000000
nHashType: 01000000
Hash te transakcije je c37af31116d1b27caf68aae9e3ac82f1477929014d5b917657d0eb49478cb670,
A potpis 304402203609e17b84f6a7d30c80bfa610b5b4542f32a8a0d5447a12fb1366d7f01
cc44a0220573a954c4518331561406f90300e8f3358f51928d43c212a8caed02de6
7eebee.
Konačna transakcija:
nVersion: 01000000
marker: 00
flag: 01
txin: 02 fff7f7881a8099afa6940d42d1e7f6362bec38171ea3edf433541db4e4ad969f 00000000 494830450221008b9d1dc26ba6a9cb62127b02742fa9d754cd3bebf337f7a55d11
4c8e5cdd30be022040529b194ba3f9281a99f2b1c0a19c0489bc22ede944ccf4ecb
ab4cc618ef3ed01 eeffffff
      ef51e1b804cc89d182d279655c3aa89e815b1b309fe287d9b2b55d57b90ec68a 01000000 00 ffffffff
txout: 02 202cb20600000000 1976a9148280b37df378db99f66f85c95a783a76ac7a6d5988ac
       9093510d00000000 1976a9143bde42dbee7e4dbe6a21b2d50ce2f0167faa815988ac
witness: 00
                02 47304402203609e17b84f6a7d30c80bfa610b5b4542f32a8a0d5447a12fb1366d7f
01cc44a0220573a954c4518331561406f90300e8f3358f51928d43c212a8caed02de
67eebee01 21025476c2e83188368da1ff3e292e7acafcdb3566bb0ad253f62fc70f07aeee6357
nLockTime: 11000000

Wednesday, January 18, 2017

Izdvojeno svjedočanstvo (segregated witness)


Izdvojeno svjedočanstvo (engl. segregated witness) struktura je koja se zapisuje u blok izvan Merkleovog stabla transakcija (svjedočanstva se zapisuju u poseban dio transakcije, a ulazi se referenciraju na njih). Sadrži podatke potrebne za provjeru ispravnosti transakcije, no ne i za provjeru rezultata transakcije. Točnije, sadrži skripte i potpise. Svjedočanstvo se zapisuje stablo koje se ugnježđuje u postojeće Merkleovo stablo preko coinbase transakcije.
Ovakav način strukturiranja transakcije omogućuje nekoliko stvari:
  1. Nema više promjenjivosti transakcije. Budući da potpis više nije dio hasha transakcije (jer je u izdvojenom svjedočanstvu), više nije moguće promijeniti potpis transakcije.
  2. SPV klijenti više ne moraju primati potpise transakcija, ako im je cilj samo provjeriti postoji li transakcija.
  3. Hashiranje transakcija kod potpisivanja više ne ovisi o kvadratu veličine bloka.
  4. Povećava se broj transakcija u bloku zbog mjesta koje je oslobođeno izdvajanjem potpisa.

 ID transakcije


Uvođenjem podatkovne strukture svjedočanstva (engl. witness) transakcija će imati dva identifikatora. Standardni txid koji je dvostruki SHA256 serijalizirane transakcije:
[nVersion][txins][txouts][nLockTime]
I novi wtxid koji je dvostruki SHA256 novog formata serijalizirane transakcije:
[nVersion][marker][flag][txins][txouts][witness][nLockTIme]
Marker je veličine jednog bajta i uvijek nula: 0x00.
Flag je veličine jednog bajta te ima vrijednost različitu od nule. Trenutačno: 0x01.
Witness je serijalizacija svih svjedočanstava transakcije. Svaki ulaz transakcije, txin, povezan je s poljem svjedočanstva. Svako polje svjedočanstva počinje var_int tipom podatka koji prikazuje broj podataka koji se stavljaju na stog za pojedini ulaz. Zatim slijede sami podaci od koji svaki opet počinje tipom podatka var_int koji opisuje duljinu podatka. Svjedočanstvo nije skripta.
Ako je transakciju kreirao stariji klijent koji ne podržava svjedočanstva, ulazi u transakciju moraju imati prazno witness polje: 0x00. U tom je slučaju wtxid = txid.

Zapis svjedočanstva

Svi wtxid-ovi moraju se zapisati. Wtxid coinbase transakcije je 0x0000…0000.
Vršni hash svjedočanstava izračunava se iz svih wtxid-ova u bloku, slično korijenu Merkleovog stabla. Taj se hash zapisuje u scriptPubKey coinbase transakcije. Zapis je minimalne duljine 38 bajtova, s time da je prvih šest 0x6a24aa21a9ed:
1 bajt – OP_RETURN (0x6a)
1 bajt – Stavi sljedećih 36 bajtova (0x24) na stog
4 bajta – zaglavlje zapisa (0xaa21a9ed)
32 bajta – hash zapisa – dvostruki SHA356(vršni hash svjedočanstava | rezervirana vrijednost)
scriptPubKey polje sadrži i 32-bitnu rezerviranu vrijednost. Ako postoji više izlaza takve strukture, onaj s najvećim indeksom smatra se zapisom hasha svjedočanstva. Rezervirana vrijednost zasad nema nikakvog značenja

Program svjedočanstva (witness program)

Skripta scriptPubKey koja se sastoji od bajta [OP_0..OP_16] nakon kojeg slijedi 2 do 40 bajtova dobiva novo značenje. Prvi bajt naziva se bajt verzije. Ostali bajtovi predstavljaju program svjedočanstva.
Dva slučaja u kojima se svjedočanstvo verificira su:
  1. Ako se scriptPubKey sastoji od bajta verzije i programa svjedočanstva. U tom slučaju scriptSig mora biti prazan jer je u suprotnom transakcija neispravna.
  2. Ako je scriptPubKey P2SH skripta. U tom je slučaju redeemScript skripta u polju scriptSig bajt verzije plus program svjedočanstva. Ako u polju scriptSig nije BIP16 redeemScript, transakcija nije ispravna.
 
Ako je bajt verzije 0, a program svjedočanstva je duljine 20 bajtova:
  • Interpretira se kao pay-to-witness-public-key-hash (P2WPKH) program.
  • Svjedočanstvo se sastoji od 2 elementa (oba manja od 520 bajtova). Prvi je potpis, a drugi javni ključ.
  • HASH160 javnog ključa mora odgovarati programu svjedočanstva.
  • Nakon verifikacije skripte, potpis se verificira pomoću javnog ključa korištenjem naredbe CHECKSIG.
Ako je bajt verzije 0, a program svjedočanstva je duljine 32 bajta:
  • Interpretira se kao pay-to-witness-script-hash (P2WSH) program.
  • Svjedočanstvo se sastoji od elemenata koji su ulaz skripti te serijalizirane skripte (witnessScript < 10000 bajtova).
  • SHA256 skripte witnessScript mora odgovarati programu svjedočanstva.
  • witnessScript se deserijalizira i izvršava.


Ako je bajt verzije 0, a program svjedočanstva nije duljine 20 niti 32 bajta, skripta nije ispravna. Ako je verzija veća od nule, program svjedočanstva se ne interpretira.

Parametri i semantika

Težina bloka računa se kao veličina bloka (1 MB) plus ukupna veličina svjedočanstava (3 MB).
Broj potpisa po bloku povećava se s 20.000 na 80.000.
Uvode se tri nova pravila za rudarenje:
  1. Za P2WPKH i P2WSH prihvaćaju se samo komprimirani javni ključevi.
  2. Argumenti za OP_IF i OP_NOTIF moraju biti prazan vektor (neistina) ili 0x01 (istina).
  3. Ako OP_CHECKSIG ili OP_CHECKMULTISIG ne uspiju, potpis mora biti nul-vektor.

Primjeri

P2WPKH


Slijedi primjer verzije 0 P2WPKH:
scriptPubKey: 0 <20 bajtova hasha javnog ključa>
(0x0014{20 bajtova hasha})
scriptSig: (prazno)
svjedočanstvo: <potpis><javni ključ>
Ponašanje je vrlo slično dosadašnjem. Skripta scriptPubKey u izlazu transakcije šalje bitcoine na hash javnog ključa (adresu). Transakcija koja želi te bitcoine potrošiti daje javni ključ koji odgovara hashu u izlazu transakcije koja je bitcoin poslala i potpis transakcije. Umjesto da se potpis i javni ključ nalaze u polju scriptSig, nalaze se u polju svjedočanstva.
U skripti scriptPubKey 0 označuje verziju witness programa. Duljina programa kaže da se radi o vrsti P2WPKH. Potpis se verificira s: <signature><pubkey> CHECKSIG. U usporedbi s P2PKH, P2WPKH koristi tri bajta manje u scriptPubKey.

P2WSH

Slijedi primjer 1 od 2 višepotpisne transakcije verzije 0 P2WSH:
scriptPubKey: 0 <32 bajta hasha skripte svjedočanstva>
(0x0020{32 bajta hasha})
scriptSig: (prazno)
svjedočanstvo: 0 <potpis1> <1 <javni1> <javni2> 2 CHECKMULTISIG>
U skripti scriptPubKey 0 označuje verziju witness programa. Duljina programa kaže da se radi o vrsti P2WSH. Posljednji element u svjedočanstvu (witnessScript) hashira se pomoću SHA256 te se hash uspoređuje s 32-bajtnom vrijednošću u polju scriptSig. Ako odgovaraju, skripta se izvršava. P2WSH povećava veličinu skripte s dosadašnjih 520 bajtova na 10.000.