A formal analysis of hashgraph and its accountability properties

Abstract

The Hashgraph algorithm is a distributed ledger technology (DLT) consensus algorithm that is an alternative to conventional blockchains. Generally, a distributed ledger can be seen as a database of transactions that is replicated across serveral locations, typically run by multiple parties. In order to reach an agreement on the validity and order of transactions, DLTs typically rely on consensus protocols as a key component. Participants of the Hashgraph algorithm locally manage a hashgraph. This is a directed acyclic graph of events. All events include, among other (meta)data, mainly transactions that were submitted by clients. In order to reach a consens, Hashgraph utilizes so-called virtual voting so that parties with different hashgraphs assign all events the same position in the total order of events. We call this desirable property consistency, which allows different participants to calculate and agree on the same order of transactions. Accountability is a well-known concept in distributed systems and cryptography but new to blockchains and DLTs in general. With this concept, misbehaving parties violating predefined security goals can be identified and held accountable with undeniable cryptographic evidence to incentivize participants to behave honestly. In this work, we put forward a rigorous proof that Hashgraph does achieve accountability w.r.t. consistency. That is, participants that misbehave by calculating a different order of transactions, by not following the Hashgraph protocol, can always be identified and rightfully blamed. To achieve this, we construct an iUC model of the hashgraph protocol with the necessary additions to hold dishonest participants accountable. In particular, we prove under relatively mild assumptions that honest participants, following the Hashgraph algorithm, will always assign events in their hashgraph the same order. That is, honest participants can reach a consens on the total order of events and transactions. Due to the real-world applications of Hashgraph, we believe this result is of independent interest.

Der Hashgraph Algorithmus ist ein Distributed-Ledger-Technologie (DLT) Konsensus Algorithmus, der häufig als Alternative zu klassischen Blockchains angesehen wird. Im Allgemeinen kann ein Distributed-Ledger als eine Datenbank an Transaktionen angesehen werden, die an verschiedenen Orten repliziert wird, wobei diese typischerweise von verschiedenen Parteien betrieben werden. Um einen Konsens bei der Ordnung und Gültigkeit von Transaktionen zu erzielen, benötigen Distributed-Ledger-Technologien typischerweise ein Konsensus Protokoll als zentralen Bestandteil. Teilnehmer des Hashgraph Algorithmus verwalten lokal einen Hashgraph. Dies ist ein gerichteter azyklischer Graph an Events; diese Events beinhalten neben anderen Metadaten hauptsächlich Transaktionen, die zuvor von Clients eingereicht wurden. Um einen Konsens zu erzielen, verwendet der Hashgraph Algorithmus sogenanntes Virtual-Voting, welches verschiedenen Parteien, mit unterschiedlichen Hashgraphen erlaubt, sich auf eine gemeinsame Ordnung von Events zu einigen. Wir bezeichnen diese Eigenschaft, die es verschiedenen Teilnehmern ermöglicht, die gleiche Reihenfolge der Transaktionen zu berechnen und zu vereinbaren, als Consistency. Accountability ist ein bekanntes Konzept in verteilten Systemen und der Kryp­to­gra­fie, allerdings noch neu in der Anwendung für Blockchains und Distributed-Ledger-Technologien. Mithilfe diesem Konzept können Parteien, die vorgeschriebene Sicherheitseigenschaften verletzen, zweifelsfrei identifiziert und zur Rechenschaft gezogen werden, mittels unbestreitbaren kryptografischen Beweisen. Dies soll Parteien dazu ermutigen, sich ehrlich zu verhalten. In dieser Arbeit zeigen wir das Hashgraph Accountability bezüglich Consistency erfüllt. Das bedeutet, Teilnehmer die sich fehlverhalten, indem diese eine abweichende Ordnung an Transaktionen berechnen, aufgrund des Nichtbefolgen des Hashgraph Algorithmus, können immer eindeutig bestimmmt werden. Um dies zu erreichen, konstruieren wir ein iUC-Modell des Hashgraph Algorithmus mit den notwendigen Änderungen, um unehrliche Teilnehmer auszumachen. Insbesondere beweisen wir unter vergleichsweise schwachen Anforderungen, dass ehrliche Teilnehmer, die den Algorithmus befolgen, Events immer dieselbe Ordnung zuweisen. Somit erzielen ehrliche Teilnehmer immer ein Konsens für die gesamte Ordnung an Events und Transaktionen. Aufgrund der realen Anwendungsfälle für Hashgraph glauben wir, dass dieses Resultat von unabhängigem Interesse ist.