O Bitcoinu

Bitcoin: A Peer-to-Peer Electronic Cash System

Vynálezce Bitcoinu: Satoshi Nakamoto, 2008


Obecně

Čistá verze elektronického hotovostního peněžního systému klient – klient by dovolovala online platby, které by mohly být zaslány jednou stranou druhé, bez využití finanční instituce. Digitální podpis by zajistil část řešení, ale hlavní benefit by byl ztracen, pokud by byla stále nutná třetí strana k zamezení dvojího použití peněz. Pro vyřešení problému dvojího použití navrhujeme použít síť klient – klient (peer-to-peer síť).

Hašováním síťových časových razítek transakcí do probíhajícího řetězce založeného na hašování vykonané práce (proof-of-work) by se vytvořil záznam, který nemůže být změněn beztoho, aniž by se vykonaná práce nevykonala znovu. Nejdelší řetěz neposkytuje jen potvrzení sekvencí jako svědek událostí, ale potvrzuje i to, že potvrzení přišlo ze skupiny s největším výkonem procesoru.

Tak dlouho, jak převážná část výkon procesorů je ovládaná uzly, které nespolupracují na útoku na síť, budou [skupiny s největším výkonem procesoru] generovat nejdelší řetěz a předstihnout útočníky. Síť samotná vyžaduje minimální strukturu. Zprávy jsou vysílané na základě nejlepšího úsilí a uzly se mohou odpojit a znovu připojit do sítě dle libosti, akceptováním nejdelšího, prací potvrzeného řetězu, čímž uzly znovu potvrdí to, co se stalo, zatímco byly odpojené.

1. Představení

Obchodování na internetu se stalo výhradně závislé na finančních institucích, které poskytujících důvěryhodnou třetí stranu pro zpracování elektronických plateb. I přesto, že [současný] systém funguje dostatečně dobře pro většinu transakcí, stále trpí vlastními slabostmi modelu založeného na důvěře. Kompletně nevratné transakce nejsou opravdu možné vzhledem k tomu, že finanční instituce nemohou vyloučit zprostředkování sporů.

Náklady zprostředkování zvyšují transakční náklady, limitují minimální praktickou velikost transakce, ořezávají možnost malých nenucených transakcí a existuje tak zjevný náklad ve ztrátě schopnosti dělat nevratné platby pro nevratnou službu. Při možností vrácení, potřeba důvěry se rozšiřuje. Obchodník se musí obávat zákazníků, otravovat je s více informacemi než by v takovém případě potřebovali. Určité procento podvodů je akceptováno jako nevyhnutelné. Tyto náklady a platby nejistot mohou být vyloučeny osobním použitím fyzických peněz, ale neexistuje žádný mechanismus, který by provedl platbu přes komunikační kanál bez důvěryhodné osoby.

Co potřebujeme je elektronický platební systém založený na kryptografickém důkazu místo důvěry, který dovolí jakýmkoliv dvěma stranám provést vzájemnou transakci přímo bez potřeby důvěryhodné třetí osoby. Transakce, které jsou výpočetně neproveditelné změnit, by měly ochránit prodávající proti podvodu a běžný majetkový mechanismus by mohl být jednoduše implementován, aby ochránil kupující.

V tomto dokumentu nabízíme řešení problému dvojitého použití [peněz], použitím klient – klient (peer-to-peer) distribuovaného serveru s časovými razítky sítě, abychom generovali výpočetní důkaz chronologického pořadí transakcí. Systém je bezpečný tak dlouho, jak poctivé uzly dohromady ovládají více výpočetního výkonu procesorů, než jakákoliv kooperující skupina útočících uzlů.

2. Transakce

Elektronickou minci definujeme jako řetězec digitálních podpisů. Každý majitel přesunuje minci dále, digitálně podepsaným hašem předchozí transakce a veřejným klíčem dalšího majitele a přidáním tohoto na konec mince. Příjemce může ověřit podpisy tím, že ověří řetězec vlastnictví.

Problem samozřejmě je, že příjemce nemůže ověřit, že jeden z majitelů nepoužil minci dvakrát. Běžné řešení je stanovit důvěryhodnou centrální autoritu nebo mincovnu, která kontroluje všechny transakce proti dvojímu použití. Po každé transakci musí být mince vrácena do mincovny, aby se vydala nová mince, a jen mince vydané přímo z mincovny jsou důvěryhodné, aby nebyly použity dvakrát.

Problém tohoto řešení je, že celý osud peněžního systému závisí na těžební firmě s každou transakcí procházející přes ni, jako v bance.  Potřebujeme najít způsob pro příjemce, aby věděli, že předchozí vlastník nepodepsal nějaké transakce dříve. Pro naše účely, nejdřívější transakce je první, která se počítá a tak se nemusíme starat o pozdější pokusy dvojitého použití.

Jediný způsob jak potvrdit neexistenci transakce je být si vědom všech transakcí. Na modelu založeném na těžení, těžba si byla vědoma všech transakcí a rozhodla, která přišla jako první. Dosáhnout tohoto bez důvěryhodné strany, transakce musí být zveřejňované [1] a pro účastníky potřebujeme systém, kde souhlasí s každou historií v pořadí, v které byly obdrženy. Příjemci potřebují důkaz, že čas každé transakce, s kterou souhlasila majorita uzlů, byla ta, která byla přijata jako první.

3. Server s časovým razítkem

Řešení, které navrhujeme je založené na serveru s časovými razítky. Server s časovými razítky pracuje tak, že vezme haš bloku s položkami, které mají být opatřeny časovým razítkem a veřejně publikuje haš, jako v novinách nebo na Usenet poště [2-5]. Časové razítko potvrdí, že data musela existovat zjevně v takovém čase, aby mohla být do haše zařazena. Každé časové razítko obsahuje předchozí časové razítko v jeho haši, formující tak řetěz, kde s každým dalším časovým razítkem se posilují předchozí.

4. Potvrzení prací (Proof-of-Work)

Abychom implementovali distribuovaný server s časovým razítkem na bázi klient – klient, bude potřeba použít systém potvrzení prací (proof-of-work) podobný „Hashcash“ [6] systému Adama Backa, více než novinám nebo Usenet poště. Systém založený na potvrzení prací (proof-of-work) znamená hledání hodnoty, která, v případě, že je hašována, třeba funkcí SHA-256, její první bity začínají číslem nula. Průměrná práce pro nalezení nulových bitů v požadovaném čísle exponencionálně vzrůstá, avšak může být ověřena provedením jednoduchého haše.

Pro naši síť s časovými razítky implementujeme systém potvrzení prací (proof-of-work) zvýšením nonce v bloku dokud není nalezena hodnota, která dává haš bloku s požadovanými nulovými bity. Jakmile výkon procesorů naroste, aby bylo potvrzení prací dostatečné velké, blok nemůže být změněn beztoho, aniž by se práce nevykonala znovu. Jak jsou poté bloky zřetězeny, práce pro změnu bloku bude zahrnovat i následnou změnu všech bloků.

Systém potvrzení prací (proof-of-work) rovněž řeší problém stanovení zastoupení tam, kde se rozhoduje většinově. Jestliže většina by byla založena na systému jedna IP adresa je jeden hlas, toto by mohlo být podkopáno kýmkoliv, kdo by byl schopen přidělit mnoho IP adres. Systém potvrzení prací (proof-of-work) je v podstatě jeden procesor, jeden hlas. Rozhodnutí většiny je reprezentováno nejdelším řetězcem, do kterého bylo investováno největší, prací potvrzené, úsilí.

Jestliže je většina výkonu procesorů ovládána poctivými uzly, poctivý řetězec bude růst rychleji a předstihne jakékoliv konkurenční řetězce. Modifikovat poslední blok, útočník by musel znovu vykonat práci bloku a všech následných bloků a poté dohnat a překonat práci poctivých uzlů. Ukážeme později, že pravděpodobnost pomalého útočníka dohnat se exponenciálně zmenšuje s tím, jak jsou následně přidávány bloky.

Abychom mohli kompenzovat zvyšování rychlosti hardwaru a měnícího se zájmu provozovat uzly v průběhu času, obtížnost systému založeného na potvrzení prací (proof-of-work) je determinováno změnou průměrného cíle, kterým je průměrný počet bloků za hodinu. Jestliže jsou generovány příliš rychle, obtížnost se zvýší.

5. Síť

Kroky při běhu sítě jsou následující:

1) Nové transakce jsou rozeslány všem uzlům
2) Každý uzel sbírá nové transakce do bloku
3) Každý uzel pracuje na nalezení „proof-of-work“ pro svůj blok
4) Jakmile uzel nalezne „proof-of-work“, rozešle blok všem uzlům
5) Uzly akceptují blok jen tehdy, pokud všechny obsažené transakce jsou platné a nejsou již jednou použité
6) Uzly vyjádří svoji akceptaci bloku tím, že zapracují vytvořený blok do řetězce bloků tím, že zahašují akceptovaný bloku jako u předchozího haše

Uzly vždy potvrdí nejdelší řetězec jako ten, který je správný a i nadále budou pracovat na jeho prodloužení. Jestliže dva uzly vyšlou rozdílnou verzi dalšího bloku současně, některé uzly mohou přijmout jeden nebo ostatní jako první. V tomto případě pracují s prvním, který přijmou, ale uloží ostatní větev v případě, že se stane delší. Vazba bude přerušena, když další „potvrzení prací“ je nalezeno a jedna větev se stane delší; uzly, které pracovaly na jiné větvi přejdou na delší.

Rozeslání nových transakcí nezbytně nepotřebuje to, aby transakce dosáhly všech uzlů. Pokud dosáhnou mnoha uzlů, budou zakomponávny do bloku zanedlouho. Rozeslání bloků je rovněž tolerantní k jeho nedoručení. Jestliže uzel nepřijme blok, požádá o něj, když přijme další blok a uvědomí si, že jeden postrádal.

6. Odměna

Dle pravidel, první transakce v bloku je speciální transakce, která startuje novou mincí, kterou vlastní ten, kdo blok vytvoří. To přidává stimul pro uzly, které podporují síť a zajištují způsob jak poprvé rozdělit mince do oběhu, protože neexistuje centrální autorita k jejich vydání. Pravidelné přidávání konstantního množství nových mincí je analogií těžařům zlata, kteří vynakládají zdroje, aby přidali zlato do oběhu. V našem případě, je to čas procesoru a elektřina, která je vynaložená.

Odměna může být rovněž financována z transakčních poplatků. Jestliže hodnota transakce na konci je menší než na začátku, rozdíl je transakční poplatek, který je přidán jako odměna bloku obsahující transakci. Jakmile jednou předem známý počet mincí se dostane do oběhu, stimul se může přesunout zcela do transakčních poplatků a bude zcela neinflační.

Odměna může pomoci pobvzbudit uzly, aby zůstaly poctivé. Jestliže nenažraný útočník je schopen sestrojit více výkonu procesoru než všechny poctivé uzly, musí si vybrat mezi tím, zda výkon použije k ošizení lidí krádeží jejich plateb nebo výkon použije, aby vygeneroval nové mince. Měl by shledat, že hra podle pravidel je více zisková, než pravidla, která mu umožňují získat více nových mincí než všem ostatním dohromady podkopáním systému a legálnosti jeho vlastního majetku.

7. Získání diskového prostoru

Jakmile je jednou poslední transakce s mincí schována pod dostatečným množstvím bloků, transakce použité před tím mohou být vyřazeny, aby se ušetřil diskový prostor. Aby to bylo možné usnadnit bez přerušení haše bloku, transakce jsou hašovány do Merkle stromu [7][2][5] jen s kořenem, který je zahrnut do bloku haše. Staré bloky potom mohou být stlačeny uříznutím větví stromu. Vnitřní haše nepotřebují být uloženy.

Hlavička bloku bez transakcí bude zhruba 80 bytů. Jestliže předpokládáme, že bloky jsou generovány každých 10 minut, 80 bytů *6 *24 *365 = 4,2 MB za rok. Počítač, který je zpravidla prodáván s 2GB RAM v roce 2008 a Moorovým zákonem předpokládajícím současný růst 1,2GB za rok, uložiště by nemělo být problém i kdyby třeba hlavička bloků musela být držena v paměti.

8. Zjednodušené ověřování transakcí

Je možné ověřit transakci bez provozování plného síťového uzlu. Uživatel jen potřebuje držet kopii hlaviček bloku nejdelšího, prací potvrzeného řetězu, který může získat dotazováním uzlů v síti, dokud není přesvědčen, že získal nejdelší řetězec a získal Merkle větev spojující transakce bloku s jeho časovým razítkem.

Ověřování je spolehlivé tak dlouho, jak poctivé uzly ovládají síť, ale je více zranitelné, jestliže je síť přetížena útočníkem. Zatímco uzly sítě mohou ověřovat transakce pro sebe, zjednodušený postup může oklamat uměle vykonstruované útočníkovi transakce po tak dlouhou dobu, jak útočník může pokračovat v přetěžování sítě.

Jedna ze strategií, jak se proti tomu ochránit je akceptovat výstrahy z uzlů v síti, pokud zjistí nesprávný blok tím, že vybídnou uživatelův program, aby si stáhl celý blok a u podezřelých transakcí si ověřil jejich rozporuplnost. Obchody, které budou přijímat časté platby, budou pravděpodobně chtít provozovat jejich vlastní uzly pro větší nezávislou bezpečnost a rychlé ověření.

9. Spojení a rozdělení hodnoty

Ačkoliv by bylo možné zacházet s mincemi jednotlivě, bylo by nepraktické dělat zvláštní transakci pro každý halíř při zasílání. Umožnit rozdělení a spojení hodnoty, transakce tak může obsahovat mnoho vstupů a výstupů. Normálně bude buď jeden vstup z velké předchozí transakce, nebo několik vstupů spojujících malé množství a maximálně dva výstupy: jeden pro placení a jeden, který vrací zbytek, jestli nějaký, zpět odesílateli.

Mělo by být zmíněno, že vějířovíté rozprostření, kde transakce zavisí na několika dalších transakcích a tyto transakace závisí na mnoha dalších, zde není problém. Nikdy není potřeba získat kompletní samostanou kopii transakční historie.

10. Soukromí

Tradiční bankovní model dosáhl úrovně soukromí limitováním přístupu k informacím jen zúčastněným a důvěryhodným třetím stranám. Potřeba zveřejnit všechny transakace veřejně, zabraňuje tomuto postupu, ale soukromí může být stále udržováno znemožněním toku informací na jiné místo: anonymním držením veřejného klíče. Veřejnost může vidět, že někdo posílá nějaký obnos někumu dalšímu, ale bez informace propojení transakce na kohokoliv. Toto je podobné úrovni informací uvolněné burzou, kde čas a velikost jednotlivého obchodu, tzn. záznam, je proveden veřejně, ale bez sdělení, kdo byly jednotlivé strany.

Jako další ochrana před nežádoucími průniky do systému, nový pár klíčů by měl být použit pro každou transakci, abychom běžného vlastníka udrželi stranou od možnosti být s ní spojen. Některá spojení jsou stále nevyhnutelná u transakací s více vstupy, která nezbytně prozradí, že její vstupy byly vlastněné stejným majitelem. Riziko je, že jestliže majitel kliče je odhalen, spojení mohou odhalit ostatní transakce, které patří stejnému vlastníkovi.

11. Kalkulace

Zvažme scénář, že útočník zkusí generovat alternativní řetěz rychleji, než poctivý řetěz. I kdyby to bylo dokonáno, neuvrhne to systém do stavu, kde by se otevřel svévolným změnám, jako vytvoření hodnoty z řídkého vzduchu nebo že by bylo možné vzít peníze, které nikdy nepatřili útočníkovi. Uzly rozhodně nebudou akceptovat neplatné transakce jako platbu a poctivé uzly nikdy nebudou akceptovat bloky, které je obsahují. Útočník může jen zkusit změnit jednu z jeho transakcí, aby peníze, které nedávno použil, si vzal zpět.

Závod mezi poctivými a útočníkovými řetězy může být charakterizován jako dvojznačná náhodná chůze. Úspěšná událost je, že poctivý řetěz bude prodlužován o jeden blok, zvýšením jeho vedení o +1 a chybná událost je, že útočníkův řetěz bude prodloužen o jeden blok, zmenšením mezery o -1.

Pravděpodobnost, že útočník dohoní z uvedeného rozdílu je analogický problému zruinovaného gamblera. Předpokládejme gamblera s nelimitovaným kreditem začínajícího s deficitem a potencionálně hrajícího s neomezeným počtem pokusů aby dosáhl hranici rentability. Můžeme spočítat, že pravděpodobnost, že někdy dosáhne hranici rentability nebo, že útočník někdy dohoní poctivé řetězy následovně [8]:

p=pravděpodobnost, že poctivý uzel najde další blok

q= pravděpodobnost, že útočník najde další blok

qz=pravděpodonost, že útočník někdy dohoní ze z bloků nazpět

Při daném předpokladu, že p > q, pravděpodobnost se sníží exponencionálně, jak počet bloků, které útočník musí dohonit, se zvýší. S tím, jak je vše proti němu, jestliže neudělá brzký šťastný skok dopředu, jeho šance se stanou mizivě malé, jak bude stále více zaostávat.

Nyní se podíváme na to, jak dlouho příjemce nové transakce musí čekat, než si může být dostatečně jist, že odesílatel nemůže změnit transakci. Předpokládejme, že odesílatel je útočník, který chce příjemce přesvědčit, že mu zaplatil, ale po nějakém čase převede platbu k sobě. Příjemce bude upozorněn, když se toto stane, ale odesílatel doufá, že už je příliš pozdě.

Příjemce generuje nový pár klíčů a předá veřejný klíč odesílateli krátce před podpisem. Toto zabrání odesílateli připravit řetězec bloků předem a to tak, že bude na něm nepřetržitě pracovat, dokud nemá dostatečné štěstí, aby se dostal dostatečně kupředu a v ten moment provedl transakci. Jakmile je jednou transakce poslána, nepoctivý odesílatel začne v tajnosti pracovat na paralelním řetězci obsahující alternativní verzi transakce.

Příjemce čeká, dokud nebude transakce přidána do bloku a dokud z bloků nebude spojeno. Neví přesnou velikost postupu kupředu, kterou útočník udělal, ale předpokládá, že poctivé bloky si vezmou průměrný očekávaný čas na blok, útočníkův potencionální postup kupředu bude Poissonovo rozdělení s očekávanou hodnotou.

Abychom dostali pravděpodobnost toho, jestli nás útočník stále může dohnat, násobíme Poissonovu hustotu pro každou velikost postupu, kterou mohl udělat, pravděpodobností toho, jestli nás může dohnat z toho místa:

Upravíme, abychom vyloučili nekonečno v uvedeném rozdělení:

Přepsáním do C kódu:

Po výpočtu můžeme vidět, že pravděpodobnost klesá exponencionálně se z

q=0.1

z=0 P=1.0000000

z=1 P=0.2045873

z=2 P=0.0509779

z=3 P=0.0131722

z=4 P=0.0034552

z=5 P=0.0009137

z=6 P=0.0002428

z=7 P=0.0000647

z=8 P=0.0000173

z=9 P=0.0000046

z=10 P=0.0000012

q=0.3

z=0 P=1.0000000

z=5 P=0.1773523

z=10 P=0.0416605

z=15 P=0.0101008

z=20 P=0.0024804

z=25 P=0.0006132

z=30 P=0.0001522

z=35 P=0.0000379

z=40 P=0.0000095

z=45 P=0.0000024

z=50 P=0.0000006

Řešení pro P menší jak 0,1%

P < 0.001

q=0.10 z=5

q=0.15 z=8

q=0.20 z=11

q=0.25 z=15

q=0.30 z=24

q=0.35 z=41

q=0.40 z=89

q=0.45 z=340

12. Závěr

Navrhli jsme systém elektronických transakcí, který se nespoléhá na důvěru třetí strany. Začali jsme s běžnou konstrukcí mincí vytvořené z digitálních podpisů, která poskytuje silnou kontrolu vlastnictví, ale je nekompletní bez způsobu jak zabránit dvojímu použití. Jako řešení jsme navrhli síť klient-klient za použití prací potvrzeným záznamem jako veřejné historie transakcí, která se rychle stane výpočetně nepraktickou pro útočníka, aby ji změnil, jestliže poctivé uzly kontrolují převážnou část výpočetního výkonu procesorů.

Síť je robustní v její nestrukturované jednoduchosti. Uzly pracují najednou s malou koordinací. Nepotřebují být identifikovány, vzhledem k tomu, že zprávy nejsou zasílány na nějaká konkrétní místa a jen potřebují být doručena s nejlepším úsilím. Uzly se mohou odpojit a znovu se připojit do sítě dle jejich vůle tím, že akceptují prací potvrzený řetěz jako doklad toho co se stalo, zatímco byly odpojené. Hlasují svým výpočetním výkonem procesoru, vyjadřujícím tak akceptaci prací potvrzených bloků na jejich prodloužení a odmítnutím neplatných bloků zamítnutím práce na nich. Jakákoliv potřebná pravidla a odměny mohou být prosazena tímto mechanismem shody.

Zdroje:

[1] W. Dai, „b-money,“ http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massias, X.S. Avila, and J.-J. Quisquater, „Design of a secure timestamping service with minimal trust requirements,“ In 20th Symposium on Information Theory in the Benelux, May 1999.
[3] S. Haber, W.S. Stornetta, „How to time-stamp a digital document,“ In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, „Improving the efficiency and reliability of digital time-stamping,“ In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
[5] S. Haber, W.S. Stornetta, „Secure names for bit-strings,“ In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
[6] A. Back, „Hashcash – a denial of service counter-measure,“ http://www.hashcash.org/papers/hashcash.pdf, 2002.
[7] R.C. Merkle, „Protocols for public key cryptosystems,“ In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
[8] W. Feller, „An introduction to probability theory and its applications,“ 1957.

Zjednodušený rozbor naleznete na stránce Škola Bitcoinu.

Zobrazit Aktuální graf LIVE
Zobrazit Aktuální ceny LIVE