Bysantinska problemet – finalen

general

Det här inlägget slutför serien om de bysantinska generalernas problem. Problemet ligger i hur de kan säkerställa att meddelandena de skickar till varandra är äkta i en miljö där kommunikationen är osäker.

 

Du kan läsa de första delarna i serien här: Del 1 och Del 2.

I förra inlägget gick jag igenom hur generalerna använde kryptografi för att säkerställa meddelandena var äkta. I korthet såg metoden ut så här:

Meddelandet + Nounce => Hash

Genom ett oerhört tids- och mannskapskrävande arbete (Proof of work) kombineras meddelandet med ett nounce som ger en hash som i vårt fall börjar med fem nollor.
Om det här verkar ofattbart rekommenderar jag verkligen att läsa del 1 och 2 i serien (länkar ovan).

 

messenger

Meddelandet sänds…

Vi har kommit till den tidpunkt i händelsekedjan där General 1 skickar en budbärare till General 2 med följande meddelande:

“Vi vill attackera på måndag. Är ni med på attacken?” 8632309354

Om du följt de tidigare inlägget vet du att kombinationen av denna text plus sifferserie kommer ge ett referensnummer som börjar med fem nollor. Detta garanterar äktheten i meddelandet. Budbäraren börjar nu sin färd som tar honom genom den fientliga staden…

Vi kan här tänka oss två alternativ. I det första alternativet är inte stadens försvarare medvetna om att meddelandet är kodat. I det andra alternativet är de fullt medvetna om att texten plus sifferserien måste generera en hash som börjar med fem nollor för att meddelandet ska uppfattas som äkta.

crossway

Alternativ 1

I det här scenariot vet som sagt staden inte om att meddelandet är kodat. De lyckas tillfångata budbäraren och ser att General 1 vill attackera på måndag. Eftersom staden bedömer att de kan vinna striden om endast en av de bysantinska generalerna anfaller, mutar/hotar de budbäraren att föra fram ett förfalskat meddelande till General 2..

Det försvararna gör (eftersom de inte vet att meddelandet är kodat) är att ändra textdelen i meddelandet till “Vi vill attackera på lördag. Är ni med på attacken?” 8632309354

Det vill säga, de ändrar texten men låter samma sifferserie (nounce) stå kvar. Försvararna vet inte om att när meddelandet hashas kommer referensnumret bli helt annorlunda på grund av att textdelen ändrats.

När budbäraren når General 2 med sitt falska meddelande är det första som händer att när generalen hashar meddelandet (vilket sker tämligen omedelbart) får han en hash som i det här exemplet ser ut så här: 9234534536

Eftersom hashen inte börjar med fem nollor vet generalen omedelbart att meddelandet inte är äkta och därefter vidtas åtgärder som inte är intressanta för det här exemplet. Det viktiga är att generalen vet att meddelandet är falskt. Ingen av de bysantiska generalerna luras till att attackera ensam vilket skulle innebära en säker död.

Alternativ 2

I det här scenariot vet staden om att det förekommer kodning samt att referensnumret som genereras måste börja med fem nollor. Även den här gången tillfångatas budbäraren med sitt meddelande. Försvararna vet att om de ändrar texten i meddelandet måste de också gissa fram en ny nounce som genererar en hash som börjar på fem nollor. De måste alltså avsätta oerhört mycket tid och arbetskraft för att gissa en nounce som passar. Det kommer ta mycket lång tid men det är alltså möjligt för försvararna att skicka vidare ett falskt meddelande.

Försvararna sätter igång omedelbart med arbetet och efter en (lång) tid hittar de en nounce som passar med texten. Följaktligen skickas budbäraren (som mutats/hotats) vidare till General 2 med följande meddelande:

“Vi vill attackera på lördag. Är ni med på attacken?” 3375939767

General 2 hashar meddelandet vilket genererar ett referensnummer som börjar med fem nollor. General 2 som bedömer att det nog ska gå bra svarar att de är med på attacken. Staden låter budbäraren passera mot General 1 utan att ändra innehållet i meddelandet. De är fullt medvetna om att de kommer vinna eftersom General 1 attackerar på måndag och general 2 på lördag.

Kontentan av detta exempel är att trots att meddelandet är kodat KAN innehållet förfalskas OM staden lyckas uppbåda så mycket tankearbete att de hinner gissa rätt nounce inom rimlig tid.

Är då denna metod oanvändbar på grund av detta faktum? Låt oss ta en titt…

useless
Är Proof of work värdelöst?

Kraften hos Proof of work

Som exemplen visar ligger styrkan hos Proof of work i att det kostar så mycket energi (tid och tankekraft) att det inte är möjligt för den som vill knäcka koden att inom rimliga tidsgränser klara av det. I alternativ 2 ovan kan staden klara av att förfalska meddelandet. För att göra det i princip omöjligt för försvararna att förfalska meddelandet väljer generalerna följande metod:

De låter varje division i sin armé skriva var sitt textmeddelande. Sedan låter generalen sätta ihop dessa texter till ett, låt oss kalla det, block av texter. Detta textblock kan teoretiskt bli flera hundra rader långt. Säg att vi har tio divisioner i varje armé, de skulle var för sig skriva ihop en text, som när den slås ihop i ett block, består av hundra rader.

Vi kan också tänka oss att man, innan kriget med staden, bestämde sig inom det bysantinska riket för att alla meddelanden ska skickas som block av textmeddelanden och att hashen ska börja med sju nollor. Det här gör det väldigt svårt för de egna generalerna att hitta en nounce som genererar rätt hash. Det gör det också i princip omöjligt för försvararna att kunna hitta rätt nounce till sin förfalskning eftersom. det kräver så många gissningar.

Eftersom det handlar om gissningar (det går inte att räkna ut vilken nounce som är rätt) KAN fortfarande staden ha turen att gissa rätt. Men då pratar vi om en chans på flera miljarder. Eller en på tusentals miljarder beroende på hur komplicerad kryptografi man använder.

Det är nedlagt arbete som gör att kommunikation är säker och kan hållas äkta. Hela Proof of workkonceptet bygger på detta. Det kostar så mycket arbete att säkra upp att meddelandena är oförfalskade att det måste vara värt det. Endast värdefulla meddelanden kan skickas så här. Obetydliga meddelanden är helt enkelt inte värt det som du förstår…


bitcoin

Och kopplingen till Bitcoin slutligen

Hela den här serien som beskriver de bysantinska generalernas problem är egentligen en analogi till Bitcoin! Det är nämligen Proof of work och den höga eneriåtgången i form av el som gör Bitcoinnätverket säkert. Det kommer jag skriva mer om i ett senare inlägg!

Bysantinska problemet – del två

I den första delen av den här bloggserien tog jag upp de bysantinska generalernas problem. Du hittar det inlägget här.

Kort sagt handlar det om hur generalerna kan avgöra om meddelanden de skickar mellan varandra är äkta i en miljö där de inte kan lita på någon annan…
Resonemanget är något förenklat för att det ska vara lättare att förstå.



Bakgrund

Först tittar vi på vad ett meddelande innehåller. I generalernas fall kan det exempelvis stå: “Vi vill attackera på måndag. Är ni med på attacken?”

Detta meddelande består av text och det är enkelt att ändra en text. Mottagaren vet helt enkelt inte om texten som står är autentisk eller falsifierad. Det krävs en metod för att validera äktheten på meddelandet. Frågan är hur detta ska göras?

true false

Lösningen

Sättet för generalerna att säkerställa att meddelandet inte ändras är vad som på engelska kallas “Proof of work”. En någorlunda acceptabel översättning skulle kunna vara “Validering genom arbete”.

Lösningen består av att använda sig av kryptografi. Målet med kryptografi är att två parter på ett säkert sätt ska kunna utväxla meddelanden.
Så här kan en kryptografisk metod se ut:

Meddelandet + En sifferserie => Ett referensnummer

En av förutsättningarna för denna lösning är att det är väldigt enkelt och snabbt att räkna fram ett referensnummer. Referensnumret är unikt och beror på vad som står i meddelandet och sifferserien. Men det är oerhört tidskrävande att gissa vilka tecken och siffror som meddelandet och sifferserien ska bestå av för att få fram ett BESTÄMT referensnummer.

Exempel:
Vet man att meddelandet lyder Hejsan och att sifferserien är 9032535448 så kan man tämligen omedelbart få fram att referensnumret är 0000073636.
Att addera meddelande och sifferserie till ett referensnummer kallas på engelska “hashing”. Referensnumret 0000073636 är en hash.

Vidare kallas sifferserien 9032535448 för nounce.

Låt oss ändra lite i exemplet:
Vi använder oss fortfarande av meddelandet Hejsan men ändrar sifferserien (nounce) lite grann till 9032535449. Referensnumret (hash) blir istället 3003377321.

Hela idén med att använda sig av kryptografiska lösningar är att det inte går att räkna ut vilket nounce man ska sätta in för att få en given hash. Det enda sättet att få fram en given hash är att prova en nounce i taget tillsammans med meddelandet tills man får fram önskad hash.

Generalernas tillvägagångssätt

Låt oss då se hur de bysantinska generalerna kan använda sig av kryptografi för att validera äktheten hos meddelandena. Innan det här fiktiva kriget bröt ut beslutade man i det bysantinska riket att alla meddelanden som skickades där kommunikationen inte var säker (såsom i vårt exempel där försvararna i staden kunde ändra meddelandena) var tvungna att generera en hash (referensnummer) som började med fem nollor!
Det vill säga, om inte texten plus nounce den mottagande generalen fick genererade en hash där de fem första siffrorna var nollor, skulle meddelandet anses vara falskt.



Så här agerar generalerna:
General 1 som vill skicka texten: “Vi vill attackera på måndag. Är ni med på attacken?” provar att lägga till en serie siffror som när texten och sifferserien hashas genererar ett referensnummer som börjar med fem nollor. Siffrorna efter de första fem nollorna kan vara vad som helst.

Det kan exempelvis se ut så här:
“Vi vill attackera på måndag. Är ni med på attacken?” och 0000000001.
Hashen blir 9394646823 vilket är fel.

Sedan provas:
“Vi vill attackera på måndag. Är ni med på attacken?” och 0000000002.
Hashen blir 1004883364 vilket också är fel.

Det enda sättet är att fortsätta gissa på siffror tills man hittar en nounce som genererar en hash där de första fem siffrorna när nollor.


Som du förstår är det oerhört tids- och arbetskrävande att göra detta. General 1 ger därför hela sin armé uppgiften att prova olika nounce tills de kommer fram till rätt hash. När så småningom någon gissat rätt är det på grund av att en enorm arbetsinsats gjorts. Vi kan säga att den nounce som fungerar är 8632309354.
Denna arbetsinsats som möjliggör att man till slut hittar en sifferserie som ger rätt hash är Proof of work.

true

I nästa blogginlägg går jag igenom hur stadens försvarare agerar och hur situationen utvecklas.