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.

Lämna ett svar

E-postadressen publiceras inte.