Bitcoin, sattuma ja satunnaisuus
Hugo Nguyenin essee Bitcoinin perusteista
Satunnaisuus muodostaa Bitcoinin työntodisteen (engl. Proof-of-Work, PoW) kulmakiven. Mutta miten päädyimme tähän?
Lyhyt historia satunnaisuuden tutkimuksen historiaan [1]
Satunnaisuus on aina ollut olennainen osa elämää. Monet muinaiset ennustusrituaalit perustuivat sattumaan: kreikkalaiset heittivät astragaaleja (eläinten nilkkaluita), kiinalaisten Kau Cim -tikut, länsiafrikkalaisten Opele-ketju jne. Noppien kaltaisten esineiden käyttö peleissä ja uhkapeleissä juontaa juurensa tuhansien vuosien taakse.
Silti vasta 1500-luvulla alettiin hankkia tarvittavia työkaluja ja kieltä todella ymmärtääksemme sattumaa ja satunnaisuutta. Näitä työkaluja ovat muun muassa aritmeettiset käsitteet, kuten fraktiot ja numero nolla (0).
Sattuman ja satunnaisuuden tutkimus alkoi tosissaan vasta Gerolamo Cardanosta [2]. Italiassa vuonna 1501 syntynyt Cardano oli yleisnero ja yksi vaikutusvaltaisimmista renessanssiajan matemaatikoista. Hän oli myös pahamaineinen uhkapelaaja. Uhkapeliongelmansa vuoksi Cardano vajosi köyhyyteen ja unholaan. Hänen kokemuksensa uhkapeleistä saivat hänet kuitenkin kirjoittamaan teoksen Liber de ludo aleae (“Onnenpelien kirja”), joka oli ensimmäinen kattava ja systemaattinen teos sattumasta ja satunnaisuudesta. Mielenkiintoisesti Cardano halusi pitkää kirjan salaisuudet itsellään. Kirja julkaistiin vasta sata vuotta sen kirjoittamisen jälkeen, kauan Cardanon kuoleman jälkeen.
Cardanon tärkein panos sattuman ja satunnaisuuden ymmärtämiseksi oli otos- tai tapahtuma-avaruuden käsite. Alkeellisimmalla tasolla tapahtuman todennäköisyyden laskeminen on yksinkertaisesti sitä, että lasketaan niiden alkeistapausten lukumäärä, jotka voivat johtaa tiettyyn tapahtumaan ja jaetaan se sitten kaikkien mahdollisten alkeistapausten määrällä (“otosavaruus”) olettaen, että kaikki alkeistapaukset ovat yhtä todennäköisiä. Tämä oletus pätee vain nopanheiton kaltaisiin tapauksiin, mutta se oli hyvä alku.
Cardanon jalan jalanjäljissä kulkivat Galileo Galilei ja Blaise Pascal. Galileo oli tuon ajan älyllisen kapinahengen täydellinen ruumiillistuma: hän asettui voimakasta katolista kirkkoa vastaan ja julisti, että maapallo ei ole maailmankaikkeuden keskus. Galileo teki monia tärkeitä löydöksiä. Eräässä ei niin kovin hyvin tunnetussa kirjoituksessaan Sopra le Scoperte dei Dadi (“Ajatuksia noppapeleistä”) Galilei tarkasteli samoja aiheita kuin Cardano.
Pascal, joka oli Pierre de Fermatin ja René Descartesin aikalainen, meni paljon pidemmälle kuin Cardano ja Galileo. Hän löysi sen, mitä kutsumme nykyään Pascalin kolmioksi. Vaikka muiden sivilisaatioiden matemaatikot (esimerkiksi iranilaiset, kiinalaiset ja intialaiset) olivat löytäneet saman kolmion vuosisatoja ennen Pascalia, Pascalin työ oli aikanaan kattavin ja toi mukanaan uusia sovelluksia etenkin todennäköisyysteorian alueella. Pascal esitteli myös Pascalin vaakana tunnetun argumentin Jumalan olemassaolon puolesta ja matemaattisen odotusarvon käsitteet.
Cardanon, Galileon ja Pascalin istuttamasta siemenestä ymmärryksemme sattumasta ja satunnaisuudesta kasvoivat vähitellen aiempaa kehittyneimmiksi ja hienostuneimmiksi. Tämä oli renessanssiajan yleinen kehityskulku: muutamat perustavanlaatuiset läpimurrot — kuten tähtitiede, newtonilainen fysiikka, laskenta ja empirismi — loivat perustan tieteelliselle ajattelulle, jotka loivat uusia tietämyksen alueita ja merkittäviä teknologisia innovaatioita, jotka lopulta johtivat teolliseen vallankumoukseen.
Luettelo merkittävistä virstanpylväistä matkallamme sattuman ja satunnaisuuden ymmärtämiseksi:
- Otosavaruus
- Permutaatiot ja kombinaatiot
- Pascalin kolmio
- Suurten lukujen laki
- Pienten lukujen laki
- Bayesin teoreema — ehdollinen todennäköisyys
- Kellokäyrä ja keskihajonta
- Palautuminen kohti keskiarvoa
- Satunnaiskulku
- Monte Carlo -simulointi
- Näennäissatunnaisuus
Kaksi merkittävää kehityskulkua erottuu: Monte Carlo -simulaatio ja näennäissatunnaisuus. Erityisesti siksi, että ne ovat erittäin merkittäviä nykymaailmassa.
Tietokoneen keksiminen avasi oven aivan uusille satunnaisuuden sovelluksille: tietokonesimulaatioille. Ensimmäistä kertaa historiassa meillä oli keino “ennustaa” tulevaisuutta tai paljastaa piilotettuja totuuksia suorittamalla halpoja kokeita yhä uudelleen ja uudelleen. Koneilla ajettavien simulaatioiden valtaisaa määrää oli aiemmin mahdotonta edes kuvitella.
Monte Carlo -simuloinnin keksiminen 1900-luvun alkupuolella merkitsi suurta käännekohtaa ihmiskunnan historiassa. Ennen renessanssia ihmiset usein pelkäsivät satunnaisuutta ja epävarmuutta. 1900-luvulle saavuttaessa olemme vähitellen ymmärtäneet satunnaisuutta entistä paremmin, mutta silti annoimme satunnaisuuden määritellä monia eri asioita. Monte Carlo -simuloinnin avulla saimme otteen satunnaisuudesta omaksi eduksemme. Kisällistä oli tullut mestari.
Merkittäviä varhaisia Monte Carlo -menetelmän soveltajia olivat John von Neumann ja Alan Turing, kaksi modernin tietokoneen kummisetää.
Nykyään Monte Carlo -menetelmällä on lukuisia sovelluksia: nestemekaniikka, liiketaloustiede, rahoitus ja tekoäly, vain muutamia mainitakseni. Äskettäinen AlphaGo:n tapaus on täydellinen esimerkki siitä, miten Monte Carlo -simulointi (yhdistettyinä muihin tekniikoihin) avaa uusia polkuja: AlphaGo löi parhaat ihmispelaajat siirroin, jotka ylittävät ihmisen mielikuvituksen ja valtaisan ammattimaisen Go-kirjallisuuden. AlphaGo haastaa ajatuksen siitä, että koneet eivät voi olla luovia, ja pakottaa meidät pohtimaan uudelleen sitä, mitä “luovuus” todella tarkoittaa.
Monte Carlo -menetelmien kasvava suosio vauhditti “näennäissatunnaisuuden” kehittämistä (näennäissatunnainen prosessi on prosessi, joka näyttää olevan satunnainen, mutta ei ole sitä), koska hyvän simuloinnin on kyettävä heijastelemaan mahdollisimman hyvin todellisuuden satunnaista luonnetta. Tällaisen prosessin luomat luvut ovat deterministisiä, mutta ne läpäisevät tilastolliset testit, joilla “satunnaisuus” määritellään. Näennäissatunnaisuudesta on puolestaan tullut nykyajan tietokoneajan aivan uudenlaisen tieteenalan rakennuspalikka: modernin salaustekniikan.
Tämä vie meidät Bitcoiniin.
Satunnaisuuden rooli Bitcoinissa
Eräs Bitcoinin tärkeimmistä innovaatioista on työntodisteen käyttö hajautetun konsensuksen eli yksimielisyyden saavuttamiseksi. PoW on puolueeton mittatikku, johon Bitcoin-verkkoon osallistuvat tahot voivat luottaa yksimielisyyden saavuttamisessa luottamatta kehenkään verkossa olevaan tahoon. Tämä poikkeaa varantotodisteesta, joka perustuu subjektiiviseen tulkintaan konsensuksesta. Tässä osiossa oletan, että PoW on ainoa turvallinen tapa lohkoketjun toteuttamiseksi. (Voit palauttaa mieleen PoW:in perusteet lukemalla aiemman artikkelini työntodisteen anatomiasta.)
Työntodisteen “työ” tarkoittaa sellaisen hashin eli tarkisteen (tai tiivisteen) löytämistä, jossa on pienin mahdollinen määrä nollia alussa. (Hash-syötteessä on joitakin rajoituksia, kuten muotoilu, aikaleima jne.)
Bitcoin PoW-järjestelmä käyttää kryptografista tiivistefunktiota, joka tunnetaan nimellä SHA256 (tiivisteen pituus on 256 bittiä). Kryptografisten tiivistefunktioiden tärkeä toiminto on se, että ne tuottavat yksisuuntaisia ja ainutkertaisia tiivisteitä. Tämä tarkoittaa sitä, että tiivistesyötettä ei voi päätellä vain tarkastelemalla tiivistetulostetta. Syy siihen, että ne ovat yksisuuntaisia, johtuu suurelta osin siitä, kuinka satunnainen tiivistetuloste on.
Tämä osoittautuu äärimmäisen tärkeäksi, koska jos tiivistefunktio ei tuota riittävän satunnaista (“näennäissatunnaista” tulostetta, voidaan aloittaa halutusta tiivistesyötteestä, toisin sanoen merkkijonosta, jossa on tietty määrä nollia alussa ja päätellä siitä taaksepäin. Tämä tekisi todistuksesta parhaimmillaan vähemmän luotettavan ja pahimmassa tapauksessa hyödyttömän.
Yksinkertaisesti sanoen se, mitä tyypillinen PoW-järjestelmä tekee, on (a) se esittää ongelman, jonka ratkaisu löytyy uskomattoman suuresta ratkaisuavaruudesta, (b) oikotietä ei ole ja © ainoa tapa päästä ratkaisuun on väsytyshyökkäys ja etsimällä ratkaisua satunnaisesti suuresta ratkaisuavaruudesta. Tämä muistuttaa neulan etsimistä jättimäisestä heinäsuovasta. (Virallinen tietojenkäsittelykäsitteen termi tälle on “rajaamaton probabilistinen iteratiivinen toimenpide” (engl. unbounded probabilistic iterative procedure) — melkoinen makupala.)
Joten hajautusfunktion sattumanvaraisuus määrittelee sen, kuinka vahva todiste on.
Hajautus (tarjoaa) → Satunnaisuus (takaa) → Työntodiste (tehty etsintätyö)
“Hyvä arvoitus antaa jokaiselle louhijalle mahdollisuuden voittaa seuraavan arvoituksen ratkaisun suhteessa heidän panostamaansa laskentatehon. Kuvittele heittäväsi tikkaa satunnaisesti. Tikkataulun erikokoiset alueet vastaavat eri louhijoiden hallussaan pitämää laskentatehoa.”
— Arvind Narayanan [3]
Ei ole muodollista todistusta sille, että satunnaisuus on pakollista työntodisteelle, mutta empiirisesti tämä näyttää olevan totta. Yksinkertaisesti sanottuna sellaisen ongelman, jonka ratkaisu ei ole sattumanvarainen, ratkaisun tarkistaminen ja ratkaisun tuottaminen vaativat yleensä yhtä paljon työtä. Mitä tahansa tällaista järjestelmää on vaikea skaalata (muista, että Bitcoinia on uskomattoman vaikea skaalata sellaisenaan). Se suosi myös suhteettomasti nopeinta louhijaa — siihen pisteeseen, jossa hieman hitaammat louhijat eivät ansaitse mitään.
Toinen satunnaisuuteen perustuvan työntodisteen etu on se, että louhimiseen liittyminen on hyvin avointa: louhijat voivat tulla ja mennä milloin vain haluavat. Ei ole väliä, liittyvätkö louhijat heti lohkon löytämisen jälkeen vai viiden minuutin kuluttua, sillä heidän mahdollisuutensa voittaa seuraava palkinto ei muutu.
Entä hajauttaminen? Onko se ainoa tapa saada satunnaisuutta? Luultavasti ei. On olemassa myös tunnettuja tapoja simuloida satunnaista hakua hajauttamisen lisäksi, kuten kokonaisluvun tekijöihin jakaminen tai diskreetti logaritmi.
Joten on erittäin todennäköistä, että hajauttaminen ei ole ainoa keino satunnaisuuden saavuttamiseksi, kun taas satunnaisuus on välttämätön edellytys digitaalisen työntodisteen luomiselle.
PoW-järjestelmät jakautuvat kahteen pääluokkaan:
- Laskentasidottu, jossa satunnaishaku on sidottu prosessorin nopeuteen
- Muistisidottu, jossa satunnaishaku on sidottu muistin määrään
Jää nähtäväksi, onko toinen PoW-järjestelmien tyypeistä olennaisesti toista parempi (mielestäni muistisidottu työntodiste on huonompi [4]), mutta taustalla oleva mekanismi on sama: probabilistinen, satunnaishaku valtavassa ratkaisuavaruudessa ja mikä tahansa ratkaisu voidaan varmistaa edullisesti.
Yhteenvetona voidaan todeta, että niin kauan kuin ihmiset ovat olleet olemassa, olemme kamppailleet satunnaisuuden ja epävarmuuden kanssa. Modernin tietokoneen ja Monte Carlo -simuloinnin keksiminen 1900-luvulla ovat antaneet meille ensimmäistä kertaa keinot kääntää satunnaisuus eduksemme. Satunnaisuuden käyttäminen Bitcoinissa merkitsi toista virstanpylvästä tällä pitkällä matkalla. Lyhyesti sanottuna satunnaisuus on mikä takaa “todisteen” työntodistuksessa. Ilman satunnaisuutta tai todella hyvää näennäissatunnaisuutta, työntodiste ei toimisi.
Jos Bitcoin onnistuu olemaan tulevaisuudessa rahaa, se edustaisi toistaiseksi merkittävintä ja suurimman mittakaavan sovellusta satunnaisuudelle.
Kiitos Steve Lee ja Nic Carter arvokkaasta palautteestanne.
Kirjoittajan huomioita
[1] Jos olet kiinnostunut ymmärtämään satunnaisuuden historiaa yksityiskohtaisemmin, lue Leonard Mlodinowin teos The Drunkard’s Walk: How Randomness Rules Our Lives.
[2] Älä sekoita tätä kryptovaluutta Cardanoon, joka ironisesti perustuu varantotodisteeseen.
[3] Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller ja Steven Goldfeder (2016). Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton, NJ: Princeton University Press [vedosversio]
[4] Muutamia mahdollisia ongelmia, jotka liittyvä muistisidonnaisiin PoW-järjestelmiin:
- Muistiin sidottu PoW edellyttää edelleen laskentaa, mutta se perustuu oletukseen siitä, että muistiteknologian kehitys on tasaantunut, mikä tekee muistista louhinnan ensisijaisen pullonkaulan. Mutta jos tämä oletus ei pidä paikkaansa, keskittymistä tapahtuu yhden rintaman (ASIC) sijaan kahdella rintamalla (ASIC ja muisti).
- Muistiin sidotussa PoW:issa käytettävä muisti on todennäköisesti uudelleenkäytettävissä louhinnan ulkopuolella. Tällä saattaa olla kielteisiä vaikutuksia verkon turvallisuuteen, koska se avaa hyökkääjälle mahdollisuuden vuokrata muistia muilta (koska mitä tahansa uudelle käytettävissä olevaa olisi todennäköisesti runsaasti tarjolla ja satunnaisesti liikatarjontaakin), mikä alentaa enemmistöhyökkäyksen kustannuksia. Laitteiston uudelleenkäytettävyys ei yleisesti ottaen ole toivottavaa Bitcoinin turvallisuuden kannalta.
Suomennos Hugo Nguyenin (Twitter) kirjoittamasta artikkelista “Bitcoin, Chance and Randomness”. Artikkeli on julkaistu alun perin Mediumissa 25.8.2018.
Hugo Nguyen on työskennellyt Litecoinin kehittämisen parissa Litecoin Foundationissa. Hänellä on yli 10 vuotta kokemusta ohjelmistokehitystä. Hän vietti yli seitsemän vuotta vanhempana ohjelmistokehittäjänä. Nykyisin hän työskentelee mobiilikehittäjänä YCombinatorista ponnistaneen Scribdin palveluksessa.
Kirjoituksen on suomentanut Thomas Brand (Twitter).
