Last update: 26-09-2018

Waarom is het probleem van een stel generaals van een byzantijns leger het probleem van de blockchain? Wat hebben de proof of work en proof of stake er mee te maken? Daarvoor moeten we bij het begin beginnen.

In 1975 werd het probleem van twee generaals gepubliceerd. Het beschrijft het probleem van twee generaals die ieder aan een kant van een stad die ze willen innemen gelegerd liggen. De eerste generaal is de leider en de ander de volger. Om de stad in te nemen moeten ze op exact dezelfde tijd aanvallen, doen ze dit niet dan volgt er een onherroepelijk en pijnlijk verlies. Dit lijkt een simpel op te lossen probleem ware het niet dat mobiel bereik in dat tijdperk niet al te best was en de enige mogelijkheid van communicatie een geschreven bericht per boodschapper was. De boodschapper moet om het bericht af te leveren door de vijandelijke stad. Hierbij kan de boodschapper omgekocht of gevangen worden waardoor het bericht niet wordt afgeleverd of wordt vervalst. Dit zou betekenen dat de eerste generaal aanvalt maar de tweede generaal in zijn kamp blijft of op het verkeerde moment aanvalt wat tot een verlies zal leiden.

Zelfs als het bericht van de eerste generaal naar de tweede generaal goed doorkomt moet er nog een bericht terug naar de eerste generaal waarin de tweede generaal toestemt met het gekozen moment van aanval. Ook hierbij kan de boodschapper weer gevangen worden. Dit patroon zorgt er voor dat er een oneindige reeks van "bericht ontvangen" nodig is voor de twee generaals zeker weten dat beide zullen aanvallen op het juiste moment. Dit houdt dus in dat in praktijk de generaals niet overeen kunnen komen wanneer ze zullen aanvallen.

In 1982 beschreven Leslie Lamport, Robert Shostak en Marshall Pease een generieke versie van het probleem waarin een groep generaals, ieder bevelhebber van een deel van het byzantijnse leger, om de stad gelegerd liggen. Om de stad in te kunnen nemen moeten ze wederom allemaal tegelijk aanvallen maar dit keer kunnen er ook generaals verraders zijn wat inhoudt dat elke generaal kan liegen over zijn keuze en in plaats van aan te vallen op het gekozen tijdstip dit niet te doen.

Om overeenkomst te bereiken in het probleem van de byzantijnse generaals gaat een enkele generaal ervan uit dat de meerderheid van de keuzes van andere generaals die hij ziet waar is. Dus als ze afspreken om op maandag om 11.00 aan te vallen en 2/3 van de berichten die een generaal krijgt beamen dit dan zal hij aanvallen.

Dit houdt dus in dat zo lang minder dan 1/3 van de generaals een verrader is ze de stad in kunnen nemen, ervan uitgaande dat 2/3 van de totale aanvalsmacht voldoende is om de stad in te nemen.

Blockchain, Proof of Work en Proof of State

Leuk, maar wat heeft dit met de blockchain te maken? De blockchain, de onderliggende techniek achter bijvoorbeeld bitcoin, is een gedistribueerd ledger. Dit laatste klinkt spannend maar in simpele vorm is het een netwerk van 'nodes' die samen bepalen wat de waarheid is. Er is geen centrale autoriteit die alles bijhoudt en de controle heeft. Met betrekking tot bitcoin bepalen de collectie van nodes dus wie er hoeveel bitcoin heeft, niet een centrale bank. Je kan de 'nodes' zien als de generaals van ons byzantijnse leger.

Als er niemand de centrale controle heeft kan elke node in het netwerk een 'verrader' zijn zoals bij ons probleem van de byzantijnse generaals. In plaats van niet aan te vallen kan een node liegen over een transactie en dus over hoeveel (bit)coins iemand heeft. Dat is problematisch voor de betrouwbaarheid van het systeem. Hoe kunnen we dit oplossen?

Proof of Work

Hier komt proof of work om de hoek kijken. Als we even terug stappen naar het eerste probleem van onze twee generaals dan kunnen zij een proof of work methode gebruiken om zeker te weten dat als ze het bericht ontvangen het niet vervalst is. Proof of work berust op de veronderstelling dat als een deelnemer veel werk 'doneert' om deel te nemen hij zeer waarschijnlijk te vertrouwen is. Ook rust het op het gegeven dat het door de benodigde uitgave aan werk het niet rendabel is om te frauderen.

Onze twee generaals realizeerden proof of work door een zeer moeilijk na te maken wassen zegel op de berichten te drukken. Het namaken van het zegel in de was duurde zo lang dat het bericht veel te laat aan kwam om nog door te gaan als niet vervalst. Op deze manier wisten de generaals dat als zij een bericht kregen dit onvervalst was.

Het generiekere probleem van de byzantijnse generaals ligt dichter bij wat de blockchain is. Bij dit probleem gaat het niet om de communicatie maar om het feit of de afzender van het bericht (een generaal) een verrader is of niet en bewust een onjuist bericht verspreid voor eigen gewin.

Om het nog toepasselijker te maken voor de blockchain kunnen we het probleem van de byzantijnse generaals herformuleren naar een versie waar de generaals geen stad aanvallen maar besluiten dat ze de Wi-Fi van de koning willen aanvallen door het wachtwoord bruut te forceren. De generaals moeten het wachtwoord kraken en logboeken wissen om de aanval te verbergen voordat de aanval wordt gedetecteerd. Elke individuele generaal heeft onvoldoende CPU-vermogen om de wachtwoorden alleen te forceren binnen de tijd om detectie te voorkomen. Daarom moeten meerdere generaals tegelijkertijd aanvallen om voldoende CPU-kracht te hebben om de Wi-Fi van de koning bruut te forceren voordat de aanval wordt gedetecteerd. De generaals geven niet noodzakelijkerwijs om de tijd van de aanval, alleen dat ze tegelijkertijd aanvallen. De generaals zijn het erover eens dat de eerste voorgestelde tijd van aanval die wordt verzonden de officiële tijd van de aanval zal zijn. Het maakt niet uit of de voorgestelde tijd van aanval komt van een verrader die opzettelijk probeert het plan te saboteren, omdat er geen slechte plannen zijn in dit probleem. Het probleem is dat het netwerk niet onmiddellijk is. Als meerdere generaals tegelijkertijd een aanvalsperiode uitzenden, ontvangen de andere generaals de berichten mogelijk in een andere volgorde. Wie was de eerste?

De oplossing die bitcoin hanteert is om publiekelijk aan te kondigen wat de volgende 'tijd' is, waar tijd in bitcoin terminologie een blok (verzameling transacties) is. Diegene die deze als eerste aankondigt wint en wordt gezien als de waarheid. Echter om het volgende blok (of de volgende tijd voor onze generaals) aan te kondigen moet er wel eerst een oplossing gevonden voor een zeer lastig wiskundig probleem. De oplossing voor dit probleem garandeert dat het blok transacties de opvolger is van het vorige blok. De oplossing is zeer lastig om te vinden maar makkelijk te verifiëren. Dit is de proof of work en wordt mining van een blok genoemd. Een blok bevat een sleutel tot het vorige blok, die van de transacties in het huidige blok en een tijdsnotatie. De publiek aangekondigde oplossing voor het wiskundig probleem garandeert dat op de tijd vermeld in het blok de twee sleutels en de tijd zo waren als vermeld in het blok. Na de publieke aankondiging kan iedereen zeer makkelijk verifiëren of de oplossing correct is en of de verwijzing naar het vorige blok (en dus transacties) juist is. Het netwerk accepteert nu het publiek aangekondigde blok als het laatste blok in de blockchain, of voor onze generaals, als de tijd om aan te vallen.

Goed, nu hebben we een manier om te garanderen dat het aangekondigde bericht echt is, in bitcoin termen een blok transacties niet vervalst is. Maar we missen nog het stukje waar we zeiden dat niet iedere generaal het bericht op dezelfde tijd kreeg. Dit is als volgt opgelost. Iedere generaal werkt tegelijkertijd aan het bepalen van een tijd, in bitcoin dus aan het vinden van een oplossing voor het wiskundige probleem (proof of work, mining). Zodra een generaal een nieuw bericht binnenkrijgt past hij zijn plan aan aan de tijd van het bericht. Ze gaan dan verder met werken aan het volgende blok. Op deze manier komt er een ketting van oplossingen, dit is de blockchain. Indien een generaal nog aan een ander plan werkt dan die ontvangen in het laatste publieke bericht dan zullen zij switchen naar de langste ketting van oplossingen. Dit is de ketting waar het laatste bericht aan toegevoegd is. Op deze manier werkt de meeste CPU kracht altijd aan de langste ketting.

Nu hebben we het hele plaatje.

1. De generaals verifiëren publiek aangekondigde berichten op vervalsing door de oplossing van een zeer moeilijk wiskundig probleem te testen tegen de inhoud van het bericht. De eigenschappen van het wiskundige algoritme zorgen er voor dat de oplossing alleen kan kloppen als deze overeenkomt met de inhoud van het bericht op moment van de tijd vermeld in het bericht. Een bericht bevat de huidige transacties, een verwijzing naar het vorige bericht en een tijdsnotatie.
2. De generaals werken afzonderlijk aan het oplossen van de problemen, het minen van blockchain blokken. Indien zij een publiek bericht ontvangen controleren zij of deze niet vervalst is volgens methode in (1) en indien correct controleren zij of de ketting waar het bericht aan toegevoegd is langer is dan de ketting waar zij momenteel aan werken. Zo ja dan laten zij hun huidige probleem los en beginnen zij aan het volgende probleem van de langste ketting.

Proof of Stake

Proof of stake hebben we al is uitgelegd in een eerder bericht. In het verhaal van de twee generaals zou je proof of stake als volgt uit kunnen leggen. In plaats dat de boodschappers berichten met een wassen zegel dragen (waar het zegel de proof of work was) dragen zij berichten en een grote zak geld. Indien zij het bericht afleveren bij de ontvangende generaal zegt de zak geld iets over hoe betrouwbaar de boodschapper is. Indien een boodschapper met een kleine zak geld het bericht afgeeft zegt dat niet veel, het stelen van dit geld weegt niet op tegen het bericht niet afleveren. Echter, indien een boodschapper met een grote zak geld een bericht aflevert dan zegt dit wel iets over zijn betrouwbaarheid. Hij had ook al dat geld kunnen houden en in de vijandelijke stad een mooie villa kunnen kopen om de rest van zijn dagen te slijten. 

Dit is waarom proof of stake is gebaseerd. Proof of stake gaat er van uit dat diegenen die een grote hoeveelheid valuta geinvesteerd hebben in het systeem veel te verliezen hebben bij de ondergang van dat system. Op basis van dit gegeven krijgen diegenen met veel coins meer rechten, of mining kracht dan diegenen zonder of met minder coins.

Fraude

Proof of work gecombineerd met de link naar de vorige transacties en daarmee de volledige blockchain beschermt ook tegen fraude. Het volgende plaatje legt dit uit.

Zeg dat iedereen aan blok 91 werkt van de blockchain, dit is het laatste, nog te minen, blok. Nu wil een fraudeur een eerdere transactie veranderen in blok 74. Echter blok 75 bevat een verwijzing naar blok 74. Deze verwijzing is de unieke oplossing voor blok 74 waarvan we al gezegd hadden dat dit uniek beschreef wat er in blok 74 stond. Als de fraudeur blok 74 aanpast klopt de oplossing niet meer en verwijst blok 75 dus niet meer naar blok 74. Nu moet de fraudeur dus ook blok 75 frauderen maar dan klopt 76 niet meer, enzovoort. Om een blok aan te passen moet een fraudeur dus dat blok en alle opvolgende blokken aanpassen. Een blok kostte al een enorme hoeveelheid rekenkracht om de oplossing voor het wiskundige probleem te vinden. Alle blokken vergt een buitensporige hoeveelheid rekenkracht. Zelfs als dit al bij een entiteit kon bestaan moet de fraudeur het ook nog eens doen voordat blok 91 wordt gemined. Dit is praktisch onmogelijk en daarmee is het netwerk beveiligd tegen fraude.

KUNNEN WIJ JE VERDER HELPEN?