Feedback gevraagd - Byzantine Generals' Problem for dummies

[dnaleor]

Ik ben bezig met het afwerken van mijn thesis, en heb natuurlijk het moeilijkste voor het laatste gehouden. Ik moet erin slagen uit te leggen hoe bitcoin werkt aan economie-professoren. Niet eenvoudig.
Ik heb het geprobeerd via het "Byzantine Generals' Problem". feedback meer dan welkom.
(in mijn eindwerk komt hierna een uitgebreide uitleg over de blcokchain en over digital signatures, ook over mining, 51% attack enzovoort. Het gaat er hier om dat ze de basis begrijpen en ik kan terugvallen op deze tekst om iets duidelijk te maken.

Byzantine Generals' Problem


Het decentraliseren van de ledger kan beschreven worden via het Byzantine General’s Problem. Dit is een probleem uit de computerwetenschappen waarbij verschillende actoren een consensus willen bereiken via een onveilig communicatiesysteem.

In een notendop komt het hier op neer: verschillende generaals in het Byzantijnse legers behorende tot verschillende stadsstaten 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 plun,deren van Byzantium, maar ze hebben het plan opgevat de steden van de deelnemende stadsstaten 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 stadsstaten 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 Bitcoinprotocol 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 stadsstaten 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üpdatete 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 Byzantine Generals' Problem. 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 en de digitale handtekeningen is essentieel voor de werking van het Bitcoinnetwerk en zal in de volgende paragrafen verder uitgediept worden.

[Bytas]

Is het niet makkelijker om eerst uit te leggen wat het byzantine generals' problem is, daarna in een volgende paragraaf hoe dit van toepassing is op digitale proof of ownership en dan hoe satoshi dit heeft opgelost in een derde paragraaf? 

Het byzantijns generaal probleem is sowieso al niet simpel, om te vatten, als je dan ondertussen dat nog bij elke stap zelf moet gaan omzetten in iets technisch dat toepasbaar is op bitcoin wordt het erg verwarrend. :p

De uitleg met de boekjes en de vraagstukken klopt welliswaar en is een mooie analogie, maar nogal abstract om te volgen voor iemand die bitcoin niet kent denk ik. Wij denken: "geniaal!" omdat we bitcoin kennen, dummies denken waarschijnlijk: "waarom in hemelsnaam zou je een vraagstuk oplossen voor je een brief stuurt? "

Daarnaast denk ik nog dat de analogie met de vraagstukken oplossen om proof of work te genereren niet echt op gaat. Je moet de oplossing van het vraagstuk in het boekje schrijven, dus dan hoeft de aanvaller al helemaal geen oplossing meer uit te voeren, enkel de oplossing te kopieren en door te sturen.  Anders dan hashes zijn algemene vraagstukken ook even moeilijk om te verificeren (oplossen om te kijken of het zelfde is), tenzij het over vraagstukken met een checksom gaat, en dan kan je dat best vermelden.  In een systeem als dat komt de zekerheid van de zegels die niet na te maken zijn ("something you have"), in plaats van de vraagstukken.

Ik begrijp het volledig, daar niet van, maar bruikbaar voor dummies? Ben ik niet zeker van

[dnaleor]

even al een korte reactie, morgen bekijk ik het volledig:
proof of work is ervoor al uitgelegd (heb maar een stukje gekopieerd)

en in het vervolg leg ik digital signatures en de blockchain volledig uit

De uitleg met de boekjes en de vraagstukken klopt welliswaar en is een mooie analogie, maar nogal abstract om te volgen voor iemand die bitcoin niet kent denk ik. Wij denken: "geniaal!" omdat we bitcoin kennen, dummies denken waarschijnlijk: "waarom in hemelsnaam zou je een vraagstuk oplossen voor je een brief stuurt? " Cheesy

dat heb ik toch uitgelegd:

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 stadsstaten kunnen plunderen.

misschien moet ik het wat anders/duidelijker verwoorden, maar dat is de reden voor een proof of work. Als je alles instant wil laten verlopen, krijg je chaos. Dat is onmogelijk (je ziet het bvb bij altcoins waar de blocktime héél laag is, die hebben héél veel orphan blocks)


edit: mja, die vraagstukken zijn niet de beste analogie, maar ik weet geen betere. ik bedenk me nu wel net dat, aangezien ik het concepty "proof of work" ervoor al duidelijk heb uitgelegd, ik misschien de analogie kan laten vallen op dat vlak, en gewoon over "proof of work" spreek. Zal duidelijker zijn.

[Bytas]

aha, als proof of work al uitgelegd is geweest is het inderdaad wel veel duidelijker denk ik!

[Zeta0S]

Ik moest er even echt voor zitten om alles goed door te lezen.
Maar als je er voor zit is het duidelijk verhaal, nu snap ik het netwerk ineens een heel stuk beter.
Wellicht een tekening af en toe net nog eenvoudiger maar. Blockchain/mining in leger vorm.
Ik kan helaas niet tekenen, maar in blok structuur zou dit ook kunnen natuurlijk.

dnaleor als je het stuk definitief af hebt zou het leuk zijn als het ook op mijn site publiceert. Deze site wordt veel gelezen.

Zeta

[dnaleor]

Ik moest er even echt voor zitten om alles goed door te lezen.
Maar als je er voor zit is het duidelijk verhaal, nu snap ik het netwerk ineens een heel stuk beter.
Wellicht een tekening af en toe net nog eenvoudiger maar. Blockchain/mining in leger vorm.
Ik kan helaas niet tekenen, maar in blok structuur zou dit ook kunnen natuurlijk.

dnaleor als je het stuk definitief af hebt zou het leuk zijn als het ook op mijn site publiceert. Deze site wordt veel gelezen.

Zeta

mijn thesis is nogal academisch, maar zal zeker stukken herwerken tot artikels en ze je doorsturen

de tekeningen volgen nog bij de technische uitleg over digitale handtekeningen en de blockchain zelf.
Dit is een analogie waarop ik kan terugvallen als het te moeilijk wordt


thx anyway voor alle feedback

[dnaleor]

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üpdatete 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.

Ik denk dat een belangrijk punt om te vermelden is dat vanwege het feit dat de verwachte meerderheid van de generaals ,>51%, betrouwbaar is, de langste versie, de juiste aanvalstijd zal bevatten.

THX
was ik vergeten vermelden inderdaad. voor ons is dat evident natuurlijk

[argov]

Ik vind dit een bijzonder goede (academische) uitleg. Je legt de basis duidelijk uit en het is moeilijk voor de anti-bitcoin economen om dit de weerleggen. Het verhaal zit duidelijk in elkaar en de analogie is (voor mij toch) zeer duidelijk.

Nog een puntje: Misschien kan je je thesis insturen voor de Vlaamse Scriptiewedstrijd. Als je het goed doet en je wordt gekozen, wordt bitcoin eindelijk eens deftig in de mainstream media gebracht 

[Zeta0S]

Uitleggen waarom de Difficulty steeds een stapje omhoog gaan?

[dnaleor]

Uitleggen waarom de Difficulty steeds een stapje omhoog gaan?

wordt verder nog uitgelegd. Niet alles past in de analogie

[dnaleor]

Nog even hier laten weten, bedankt voor de feedback!

heb ondertussen mijn thesis verdedigd en heb 16/20 gekregen

[Zeta0S]

Nog even hier laten weten, bedankt voor de feedback!

heb ondertussen mijn thesis verdedigd en heb 16/20 gekregen

Gefeliciteerd!!!

[argov]

Proficiat!!

[Dotrego]

Nog gefeliciteerd
Wil je hem ook in zijn geheel publiceren? Recente academische bronnen rondom Bitcoin zijn schaars... (vooral Nederlandstalig).

[neoneros]

Is het niet makkelijker om eerst uit te leggen wat het byzantine generals' problem is, daarna in een volgende paragraaf hoe dit van toepassing is op digitale proof of ownership en dan hoe satoshi dit heeft opgelost in een derde paragraaf? 

Het byzantijns generaal probleem is sowieso al niet simpel, om te vatten, als je dan ondertussen dat nog bij elke stap zelf moet gaan omzetten in iets technisch dat toepasbaar is op bitcoin wordt het erg verwarrend. :p

De uitleg met de boekjes en de vraagstukken klopt welliswaar en is een mooie analogie, maar nogal abstract om te volgen voor iemand die bitcoin niet kent denk ik. Wij denken: "geniaal!" omdat we bitcoin kennen, dummies denken waarschijnlijk: "waarom in hemelsnaam zou je een vraagstuk oplossen voor je een brief stuurt? "

Daarnaast denk ik nog dat de analogie met de vraagstukken oplossen om proof of work te genereren niet echt op gaat. Je moet de oplossing van het vraagstuk in het boekje schrijven, dus dan hoeft de aanvaller al helemaal geen oplossing meer uit te voeren, enkel de oplossing te kopieren en door te sturen.  Anders dan hashes zijn algemene vraagstukken ook even moeilijk om te verificeren (oplossen om te kijken of het zelfde is), tenzij het over vraagstukken met een checksom gaat, en dan kan je dat best vermelden.  In een systeem als dat komt de zekerheid van de zegels die niet na te maken zijn ("something you have"), in plaats van de vraagstukken.

Ik begrijp het volledig, daar niet van, maar bruikbaar voor dummies? Ben ik niet zeker van

het apart vertellen van het byzantijns generaal probleem en daarna pas de vergelijking met bitcoin is inderdaad het eerste wat ook mij te binnen schoot. Het verhaal zelf wordt dan duidelijker en daarna kan je per oplossing/vergelijking met bitcoin weer terugverwijzen.

[Maharaja]

Wellicht kun je even kijken hoe ze The Byzantine Generals' problem bij http://digitalcurrency.unic.ac.cy/free-introductory-mooc (les 1 of 2 uit mijn hoofd) uitleggen. Ik vond dat ze dit heel helder uitlegden. Eerst een introductie wat het is en daarna de toepassing hiervan op crypto.