Consensus protocols are the core of modern blockchain systems, such as the Bitcoin, Ethereum, and Algorand networks. Thanks to these protocols, participants in a blockchain network can reach consensus on which blocks to add to a blockchain, to have a consistent chain of blocks in the whole network. Blocks are typically collections of transactions, e.g., transferring currency between participants, but can contain other data depending on the use case. Consensus protocols are difficult to design, test, and implement. Problems may only manifest in rare cases but can have disastrous consequences. Formal protocol models allow exhaustive analysis and formal verification. However, formal verification is only as good as the specification of the protocol. For example, specification properties could be vacuously true, or the specification may omit to mention liveness properties that are crucial for progress in a system implementation. This thesis describes the practical validation of a formal specification of Giskard, a consensus protocol used in the PlatON network. We translated key aspects of a formal model of Giskard in the Coq proof assistant to executable Python code, and integrated them into the Sawtooth blockchain framework. Then, we ran simulations of a blockchain network executing Giskard using Sawtooth, checking network node state properties of Giskard as well as its global safety properties. Automated clients from the Sawtooth network provided randomly generated transactions as input for the network. The implementation with the test results are available for reproducibility. Both consensus safety and liveness issues were found in the formal specification of Giskard during the simulations. Based on the previous informal English specification of Giskard, we propose a new formal specification which was validated to reach consensus on blocks in the simulated blockchain network and uphold the protocol’s crash and Byzantine failure tolerance to a certain degree. The improved formal model can serve as a new basis for verifying and implementing Giskard in the future. / Konsensusprotokoll utgör kärnan i moderna blockkedjesystem som Bitcoin-, Ethereum- och Algorandnätverken. Tack vare dessa protokoll kan deltagare i blockkedjenätverk nå konsensus om vilka block som ska läggas till, för att få en konsekvent blockkedja i hela nätverket. Block är vanligen samlingar av transaktioner, till exempel överföringar av valuta mellan deltagare, men kan också innehålla annan data beroende på användningsområdet. Konsensusprotokoll är svåra att designa, testa och implementera. Problem kanske bara visar sig i sällsynta fall, men kan ha katastrofala konsekvenser. Formella protokollmodeller tillåter uttömmande analys och formell verifiering. Men formell verifiering ger bara så goda resultat som protokollspecifikationen tillåter. Till exempel kan specfikationsegenskaper vara sanna innehållslöst eller så kan specifikationen underlåta att nämna framstegsegenskaper som är viktiga för att en systemimplementation inte ska låsa sig. Denna avhandling beskriver den praktiska valideringen av en formell specifikation av Giskard, ett konsensusprotokoll som används i PlatONnätverket. Vi översatte nyckelaspekter av en formell modell i bevisassistenten Coq till körbar Python-kod och integrerade koden i blockkedjeramverket Sawtooth. Sedan körde vi simuleringar av ett blockkedjenätverk som använder Giskard med hjälp av Sawtooth och undersökte Giskards tillståndsegenskaper för nätverksnoder och även dess globala säkerhetsegenskaper. Automatiserade klienter från Sawtooth-nätverket tillhandhöll slumpgenererade transaktioner som indata för nätverket. Implementeringen med testresultaten är tillgängliga för reproducerbarhet. Både säkerhets- och framstegsproblem hittades i den formella specifikationen av Giskard under simuleringarna. Baserat på en tidigare informell specifikation av Giskard på engelska föreslår vi en ny formell specifikation som validerades att nå konsensus på block i det simulerade blockkedjenätverket och att till en viss grad tolerera krascher och byzantinska fel. Den förbättrade formella modellen kan användas som en ny bas för att verifiera och implementera Giskard i framtiden.
Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-343000 |
Date | January 2023 |
Creators | Sandner, Leon |
Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
Source Sets | DiVA Archive at Upsalla University |
Language | English |
Detected Language | Swedish |
Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
Format | application/pdf |
Rights | info:eu-repo/semantics/openAccess |
Relation | TRITA-EECS-EX ; 2023:829 |
Page generated in 0.0094 seconds