Byzantijnse generaalsprobleem
Byzantijnse generaalsprobleem
Het distribueren van het grootboek van de Bitcoin kan begrepen worden via het Byzantijns generaal probleem. Satoshi Nakamoto heeft als eerste in de geschiedenis van de mensheid een technologische doorbraak op het gebied van cryptografie en de computerwetenschappen bereikt. Het Bitcoin protocol biedt een oplossing voor het onmogelijk geachte Byzantijns generaalsprobleem.
Wat is het Byzantijnse generaalsprobleem?
Dit is een probleem uit de computerwetenschappen waarbij verschillende actoren een consensus willen bereiken via een onveilig communicatiesysteem. In het volgende artikel wordt het probleem uitgelegd en toegepast op de werking van Bitcoin.
In een notendop komt het hier op neer: verschillende generaals in het Byzantijnse legers behorende tot verschillende stadstaten willen plannen maken om de rijke hoofdstad Byzantium aan te vallen met als doel deze stad te plunderen. De stad is omsingeld en de enige manier waarop gecommuniceerd kan worden is via briefwisseling die doorgegeven wordt via bode’s. De generaals hebben niet de mogelijkheid samen te komen om een aanvalsplan te bespreken, dat zou te gevaarlijk zijn.
De aanval zal pas slagen als minstens 51% van de legers tegelijk de aanval uitvoert. Als er minder dan de helft van de legers de stad aanvalt, zullen de legers afgeslacht worden. Er bevinden zich echter enkele verraders onder de generaals: deze generaals plannen om te doen alsof ze zullen deelnemen aan het plunderen van Byzantium, maar ze hebben het plan opgevat de steden van de deelnemende stadstaten te plunderen. Immers, als er minder dan de helft van de legers deelnemen aan het aanvalsplan, zullen de legers verslagen worden en hebben de verraders de kans om de naburige stadstaten te plunderen. Het merendeel van de generaals is echter ter goeder trouw. De generaals moeten onderling afspreken wanneer ze tezamen Byzantium zullen aanvallen. Slagen ze er niet in om allemaal tegelijkertijd aan te vallen, zullen de legers verslagen worden.
Er moet dus een consensus gevonden worden in een netwerk waar geen vertrouwen is tussen de generaals onderling. Immers, als een generaal die ter goeder trouw is afspreekt met een andere generaal die een verrader is om op een ander tijdstip aan te vallen dan de rest, zullen de legers de veldslag verliezen. Het is dus van belang dat het plan van de generaals die ter goeder trouw zijn, uitgevoerd wordt.
Dit probleem is moeilijk op te lossen omdat berichten door de verraders kunnen vervalst worden. Stel dat een generaal voorstelt om de dag erna om middernacht aan te vallen, en dit bericht naar iedereen stuurt, is het mogelijk dat de berichten worden onderschept en de verraders de uren aanpassen zodat er legers al ’s middags aanvallen. Bovendien is het ook mogelijk dat berichten van generaals die willen bevestigen dat ze het bericht ontvangen hebben ook kunnen aangepast en onderschept worden.
Het eerste wat nodig is om dit probleem op te lossen is een unieke digitale handtekening. Dit wordt in het Bitcoin protocol opgelost via private/public key encryptie (zie verder). In dit voorbeeld lost dat reeds een deel van het probleem op: de berichten kunnen niet meer aangepast worden. We stellen de digitale handtekening in dit voorbeeld voor als een wassen zegel.
Maar er is nog een bijkomend probleem: hoe komt men tot een consensus over het aanvalsuur? De ene generaal kan naar iedereen een bericht sturen dat hij om 08:00 zal aanvallen terwijl een andere om 12:00 wil aanvallen. Bovendien zullen de verraders een consensus proberen tegen te houden en steeds een ander aanvalsuur voorstellen zodat er verwarring ontstaat.
Als alle generaals naar alle andere generaals voorstellen sturen om op een bepaald moment aan te vallen, is het onmogelijk om snel een consensus te bereiken. Bovendien zullen de verraders onder de generaals verschillende aanvalsplannen overeenkomen zodat de kans bestaat dat de generaals in verspreide slagorde naar het front trekken, waardoor ze de veldslag met Byzantium zullen verliezen en zij de naburige stadstaten kunnen plunderen. Het tweede onderdeel van de oplossing is een stemmechanisme waar de generaals kunnen stemmen voor een plan dat uitgevoerd zal worden als het de meerderheid van de handtekeningen achter zich krijgt. De oplossing voor dit probleem is een gedecentraliseerde timestamp server, de blockchain (zie verder).
De oplossing bestaat erin dat een willekeurige generaal een bericht schrijft in een notitieboekje waarin hij het uur vermeldt waarop hij voorstelt de aanval te plannen. In het bericht staat ook dat, om het aanvalsplan te bevestigen, men een bepaald vraagstuk dient op te lossen op basis van het laatst ontvangen bericht (Proof of Work). Vervolgens ondertekent hij dit bericht met zijn zegel, wordt het notitieboekje gekopieerd en vervolgens naar de andere generaals doorgestuurd.
Wanneer een generaal de oplossing heeft gevonden, schrijft hij een tweede bericht in het notitieboekje (“ik bevestig het overeengekomen aanvalsuur”), voegt hij de oplossing van de berekening toe, voegt een nieuw vraagstuk toe en ondertekent hij dit bericht met zijn zegel. Vervolgens stuurt hij dit aangevuld notitieboekje weer door naar alle generaals. Vervolgens zullen de generaals opnieuw proberen het vraagstuk op te lossen.
Het is mogelijk dat een generaal op een bepaald moment twee verschillende notitieboekjes ontvangt omdat er twee generaals toevallig op hetzelfde moment de oplossing van een vraagstuk gevonden hebben. Vervolgens zijn deze boekjes doorgestuurd naar alle andere generaals en sommigen hebben ervoor gekozen verder te werken met versie A, terwijl anderen voor versie B kozen (Generaal A heeft immers een andere zegel dan generaal B, bovendien heeft generaal A een ander vraagstuk verzonnen dan generaal B.) Stel dat iemand die verder werkte op basis van versie A als eerste de nieuwe oplossing vindt en het geüpdatet notitieboekje weer naar iedereen verstuurt, dan bezitten alle generaals twee boekjes: het boekje met het onopgeloste vraagstuk van versie B en versie A waar een nieuw bericht in staat. Er staan meer berichten in versie A dan in versie B en de generaals zullen nu kiezen om verder te werken met versie A omdat hier meer generaals een consensus bereikt hebben over het aanvalsuur. Versie B zal genegeerd worden.
Laten we er nu van uit gaan dat de vraagstukken zo gekozen worden dat het gemiddeld 10 minuten duurt om op te lossen. Zo zal het notitieboekje dat door iedereen gebruikt wordt na één uur 6 berichten bevatten. Dit systeem zorgt ervoor dat de verraders onder de generaals het aanvalsuur niet kunnen veranderen, zolang de verraders niet in de meerderheid zijn. Immers, als ze een ander aanvalsuur willen voorstellen, moeten ze erin slagen om, met een kleiner aantal generaals, de vraagstukken sneller op te lossen dan de generaals die ter goeder trouw zijn.
Aangezien het steeds gemiddeld 10 minuten duurt om een probleem op te lossen is dit onmogelijk. Stel dat 25% van de generaals verraders zijn en dat iedereen de mogelijkheid heeft even snel het vraagstuk op te lossen, dan is de kans dat de verraders 6 berichten op rij in het notitiebokje kunnen neerpennen slechts (0.25)^6 = 0.024%. Zelfs in het geval 49% van de generaals verraders zijn, is de kans slechts (0.49)^6 = 1.384%. Hieruit blijkt dat als de generaals na één uur nog steeds een consensus hebben over het aanvalsuur, er voldoende zekerheid is dat de meerderheid van de generaals tot een consensus is gekomen om samen aan te vallen op het overeengekomen aanvalsuur.
Dit is de oplossing van het Byzantijnse Generaalsprobleem. De generaals kunnen tot een consensus komen zonder op voorhand te weten of ze communiceren met een verrader of een generaal die ter goeder trouw is over een onveilig netwerk. De combinatie van de gedecentraliseerde timestamp server, de digitale handtekeningen en PoW algortime is essentieel voor de werking van het Bitcoin netwerk.
- Bronvermelding: Bitcoin Talk – thread
Video’s over het Byzantijnse Generaal probleem:
- Video van Mike Maloney:
Video van Ivan on Tech:
Voor meer informatie: