Achtergrond: Byzantine Consensus

Onderstaand artikel verscheen voor het eerst op op bitcoin.nl op 11 april 2017.

Let op: dit is een theoretisch artikel, om achtergrond te bieden voor de geïnteresseerde lezer. Dit artikel is eerder gepubliceerd in MCA met introductietekst.

Het Byzantine Generals probleem

Het Byzantine Generals probleem is een voorbeeld van een gedachte-experiment waarbij communicatie en kennis een belangrijke rol spelen. De hoofdvraag in dit probleem is of unanimiteit bereikt kan worden in een gedistribueerd systeem. Dit artikel gaat in op hoe proof-of-work, wat we van Bitcoin kennen, een oplossing is voor dit probleem.

Het klassieke probleem

Computernetwerken moeten om kunnen gaan met conflicterende informatie om de juiste beslissingen te maken. Verschillende verzoeken naar een server kunnen conflicten in de processen veroorzaken. Het probleem van het ontvangen van verschillende, conflicterende, verzoeken van computers of mensen is vergelijkbaar met het scenario uit het originele Byzantine Generals probleem waar een een groep generaals samen wil werken. De klassieke versie van dit probleem is toepasbaar op verschillende systemen.

De klassieke versie van het Byzantine Generals probleem is als volgt:

Verschillende eenheden van het Byzantijns leger zijn gestationeerd buiten een vijandelijke stad. Elke eenheid wordt aangestuurd door een aparte generaal. De generaals hebben het bevel om de stad met een meerderheid van de eenheden tegelijkertijd aan te vallen, omdat de kans dat een aanval slaagt met een beperkt aantal eenheden te klein is. De generaals moeten tot overeenstemming komen over of zij gaan aanvallen, of zich terugtrekken.

Er is echter onzekerheid in de communicatie: wat als een van de generaals een verrader is met kwade bedoelingen? Om tot een goede oplossing voor dit probleem te komen moet de oplossing aan twee voorwaarden voldoen:

1. Alle loyale generaals moeten tot hetzelfde plan van actie komen én, omdat het plan ook een redelijk plan moet zijn,

2. een klein aantal verraders mag niet in staat zijn ervoor te zorgen dat de generaals een slecht plan kiezen.

Aan deze voorwaarden kan worden voldaan als alle generaals de vijand observeren en hun observaties communiceren naar de andere generaals. Op basis van de informatie die vergaard is door andere generaals kan elke generaal bepalen wat het beste plan is en een stem uitbrengen voor dat plan.

We bekijken deze voorwaarden vanuit een versimpelde variant waar er twee verschillende plannen mogelijk zijn: aanvallen of terugtrekken. De oplossing is dan dat het officiële plan bepaald wordt op basis van welke optie de meeste stemmen heeft gekregen. In dit scenario kan een klein aantal verraders de uitkomst alleen beïnvloeden als de generaals allemaal evenredig verdeeld zijn in hun keuze. Er zijn geen slechte plannen, zolang de loyale generaals tot hetzelfde plan van actie komen. Stemmen biedt dus een oplossing voor het probleem die aan beide voorwaarden voldoet.

Het probleem herformuleren

Het Byzantine Generals probleem kan algemener gesteld worden als een beslissingsprobleem met meerdere actoren. Meerdere actoren zijn onzeker over de informatie die zij van anderen ontvangen en moeten daarom in staat zijn de informatie te verifiëren om zeker te zijn dat de informatie waar is. Een voorbeeld van waar dit probleem voorkomt is het peer-to-peer netwerk van Bitcoin.

Satoshi Nakamoto heeft het klassieke probleem opnieuw geformuleerd zodat deze van toepassing is op moderne computernetwerken. We bekijken het probleem nu vanuit deze situatie waarin de generaals in staat zijn met elkaar te communiceren via een computernetwerk:

Alle generaals in het Byzantijns leger hebben een computer en het bevel om de wi-fi van de koning aan te vallen, door het wachtwoord van de wi-fi te brute forcen. Zodra de aanval wordt ingezet is er maar beperkt tijd om het wachtwoord te kraken en sporen uit te wissen, voordat de aanval ontdekt wordt. De generaals hebben alleen genoeg rekenkracht als de meerderheid van de generaals tegelijkertijd aanvalt. Het maakt de generaals niet uit wat de exacte tijd is van de aanval, als de meerderheid maar tegelijkertijd aanvalt.

De generaals zijn het eens dat de eerst voorgestelde tijd de officiële tijd van de aanval is. Het maakt namelijk niet uit of de voorgestelde tijd van een verrader komt die het plan probeert te saboteren, want zo lang de meerderheid het eens is over het moment van de aanval zijn er geen slechte plannen in dit scenario.

Het probleem in dit scenario is dat er altijd enige vertraging zit in communicatie over een netwerk; een bericht wordt niet onmiddellijk ontvangen en de mate van vertraging verschilt per locatie. Dit heeft als gevolg dat, wanneer meerdere generaals rond hetzelfde moment een voorstel uitsturen, de generaals de berichten in verschillende volgordes kunnen ontvangen.

We kunnen nu de twee voorwaarden uit het klassieke probleem aanpassen zodat deze toepasbaar zijn op de computernetwerk versie van het probleem. De voorwaarden zijn als volgt:

1. Alle processen moeten het unaniem eens zijn over een bepaalde waarde, ondanks een minderheid van foutieve processen die willekeurig afwijken van het protocol

2. De generaals moeten in staat zijn om te controleren dat zij samen genoeg rekenkracht hebben om een succesvolle aanval uit te voeren op het voorgestelde tijdstip.

Aan deze twee voorwaarden kan worden voldaan door een complexer stemsysteem te gebruiken, vergelijkbaar met het stemsysteem dat in de klassieke variant van het probleem wordt gebruikt

Bitcoin

Het consensusmechanisme in Bitcoin moet ervoor zorgen dat de deelnemers in het netwerk het unaniem eens zijn over welke bitcoins van wie zijn (i.e. welke bitcoins bij welke public keys horen). Het probleem dat naar voren komt is dat het netwerk in staat moet zijn om te verifiëren dat de bitcoins in een transactie niet al eerder zijn uitgegeven in een andere transactie. Net als in het Byzantine Generals probleem is er bij Bitcoin geen centrale autoriteit die kan verifiëren dat transacties (of berichten, in het geval van de computernetwerk versie van het Byzantine Generals probleem) geldig zijn. Hiervoor is dus een oplossing nodig zonder één enkele vertrouwde partij: decentraal.

Het probleem kan opgelost worden door alle transacties publiek aan te kondigen en als regel aan te houden dat de transactie die het eerst gezien is geldig is. Elke node in het netwerk controleert dan of de bitcoins in een specifieke transactie niet al eerder zijn uitgegeven. Echter is ook in dit voorstel nog onzekerheid aanwezig: door de vertraging in het netwerk kan het zijn dat niet alle transacties overal tegelijk aankomen. Dit heeft als gevolg dat de set van nieuwe transacties misschien niet consistent is bij alle nodes.

Om dit probleem op te lossen en consensus te bereiken over de volgorde van transacties worden de transacties opgenomen in een proof-of-work block met daarbij ook een timestamp. Dit zorgt ervoor dat men het eens kan zijn over de volgorde van transacties: de hash van het block omvat een verwijzing naar het vorige block, nieuwe transacties en een timestamp en bewijst zo dat de data in een block op dat moment in de tijd bestond. De data zoals in het block had immers niet opgenomen kunnen worden in de hash als het op dat moment in de tijd niet bestond.

Proof-of-Work

Voor het timestampen en hashen van transactiedata gebruikt Bitcoin proof-of-work. Elke miner in het netwerk werkt aan het oplossen van een tamelijk ingewikkelde cryptografische puzzel om te voldoen aan de voorwaarden van een geldig proof-of-work block. De oplossing voor elke puzzel is een SHA-256 hash van alla data in een block. De puzzels zijn zo ontworpen dat er gemiddeld elke tien minuten een oplossing gevonden wordt.

Zodra er een oplossing gevonden is wordt de hash van het block gepubliceerd op het netwerk. De hoeveelheid rekenkracht die besteed is aan het vinden van een oplossing werkt als een proof-of-work: een block kan niet aangepast worden zonder het werk opnieuw te doen (elke aanpassing aan de data leidt immers tot een andere oplossing). Tevens, door in elk block een verwijzing naar het vorige block op te nemen, worden de blocks aan elkaar gekoppeld in volgorde (dit geeft ons de blockchain). Het aanpassen van de data en opnieuw aanmaken van een block betekent dus ook dat alle blocks die daarna komen opnieuw gedaan moeten worden. Het netwerk ziet de langste chain als geldige chain, omdat de aanname is dat de meerderheid van het netwerk belang heeft bij goedaardig handelen.

Dit proces kan ook gezien worden als een stemproces, waarbij elk toegevoegd block telt als een stem voor die specifieke transactiegeschiedenis en alle eerlijke nodes werken aan het uitbreiden van de langste chain.

Aanval op het netwerk

Wanneer een aanvaller probeert een zogenaamde double-spend (i.e. het twee keer uitgeven van dezelfde bitcoins) probeert te doen, zal de aanvaller het block waarin de transactie is opgenomen opnieuw moeten maken. Niet alleen dat block, maar ook alle blocks die daarna zijn gekomen moeten opnieuw gedaan worden om een langere chain te produceren dan de huidige 'eerlijke' chain. De aanval is immers alleen succesvol als de meerderheid van het netwerk overgaat op de vervalste chain. Met elk toegevoegd block neemt de kans af dat een transactie in een block vervalst gaat worden: met elk toegevoegd block moet er meer werk opnieuw gedaan worden. De kans dat een aanvaller met gelimiteerde rekenkracht de eerlijke chain kan inhalen is na zes tot acht blocks erg klein en wordt daarna snel verwaarloosbaar.

Byzantine Consensus door Proof-of-Work

Bitcoin's proof-of-work dient als oplossing voor de computernetwerk versie van het Byzantine Generals probleem. Waar het Bitcoinnetwerk consensus bereikt over de volgorde van transacties, zouden de generaals in staat moeten zijn consensus te bereiken over de aanvalstijd. Ter herhaling: de generaals van het Byzantijnse leger willen de wi-fi van de koning brute forcen en elke generaal mag een tijd om aan te vallen voorstellen. Het eerste plan dat wordt ontvangen wordt het officiële aanvalsplan. Het probleem, zoals we eerder schreven, is dat twee of meer generaals een verschillend plan kunnen versturen op ongeveer hetzelfde moment. Dit probleem kan opgelost worden door een versimpelde versie van proof-of-work. In plaats van proof-of-work toepassen om transacties bij te houden, kan proof-of-work worden toegepast om te zorgen dat de generaals consensus bereiken over het plan.

Elke generaal beschouwt het eerste plan voor een aanvalstijd dat ontvangen wordt als het officiële plan en begint met het werken aan een oplossing voor een proof-of-work puzzel. Wederom is elke puzzel zo moeilijk dat er gemiddeld elke tien minuten een oplossing wordt gevonden, maar alleen als alle generaals aan dezelfde puzzel werken. Zodra een van de generaals een oplossing vindt, publiceert deze generaal zijn oplossing op het netwerk samen met het plan.

Wanneer de andere generaals de oplossing samen met het plan ontvangen, passen zij het plan waar ze aan werken aan naar het ontvangen plan. De generaals gaan nu verder met het oplossen van de volgende proof-of-work puzzel, zodat deze gekoppeld kan worden aan de eerst ontvangen oplossing. Wederom geldt de regel dat de langste chain gevolgd wordt, omdat de aanname is dat de meerderheid van de generaals goedaardig handelt. Als er na een aantal oplossingen nog generaals aan een ander plan werken, zullen zij zich nu ook richten op de langste chain. Hierdoor is aan de eerste voorwaarde voldaan: alle generaals zijn het eens over de tijd van aanvallen.

Aan de tweede voorwaarde kan worden voldaan door nog een tijd door te gaan met het vinden van proof-of-work oplossingen. Nadat alle generaals aan dezelfde chain werken, zullen er na een uur gemiddeld zes oplossingen toegevoegd zijn aan de langste chain. De generaals kunnen nu verifiëren dat zij genoeg rekenkracht hebben om de aanval uit te voeren op basis van het aantal oplossingen dat gevonden wordt binnen een bepaalde tijd. De generaals kunnen nu de conclusie trekken dat de meerderheid aan hetzelfde aanvalsplan werkt en zij genoeg rekenkracht hebben om de aanval veilig uit te voeren.

Conclusie

Het consensus protocol van Bitcoin kan functioneren als vervanging van vertrouwde partijen door het opzetten van een peer-to-peer netwerk waar geen centrale autoriteit aanwezig is. Het consensus protocol van Bitcoin, proof-of-work, lost de afwezigheid van een centrale autoriteit in het Byzantine Generals probleem op. Naast dat de generaals consensus bereiken over de tijd van de aanval, kunnen de generaals ook de kans van slagen inschatten gebaseerd op de hoeveelheid rekenkracht die aan hetzelfde plan werkt. Het zorgt ervoor dat de onzekerheid over verschillende aanvalsplannen door vertraging in het netwerk wordt weggenomen en maakt het risico op sabotage verwaarloosbaar.