(Yet) Another byzantine agreement algorithm

[Lapin0t]

Hi,
not long ago I stumbled over swirlds which is a startup based on a new consensus algorithm which aims to replace some of the bitcoin/blockchain software stack. The white paper is available here.

The global idea is to separate the two different problems the blockchain is trying to solve: consensus (byzantine agreement) and identity providing. Swirld only addresses the first one and there are solutions for the second one: use a proof-of-(work|stake|whatever) systems, use an existing more or less centralized identity provider (like a state, a foundation or a corporate identity), have a web-of-thrust (like the duniter crypto-currency is working on or like webofthrust.info which was referenced in #103) or actually anything that comes to your imagination. The thing is, it solves the consensus problem well: every transaction ordering eventually reachs agreement and this ordering is fair in several ways. Moreover it doesn't suffer the sybill attack which is an attack on the identity system.

---

I really encourage you to read the white paper but if you don't have the time I will try to explain here the main concepts (correct me if you didn't understood the same things, it's new to me too).

First of all, consensus algorithm can be achieved in non-byzantine settings with voting algorithms to answer yes/no questions like was this transaction emitted before this other? (more infos in this paper: Byzantine Consensus in Asynchronous Message-Passing Systems: a Survey).

The main idea of swirld is to do meta-broadcasting: you broadcast what you know about the transactions but also from whom and since when you know them (they call it gossip about gossip), so what we will call transaction is just a sync from one party to another (and possibly a payload). The transactions form a directed acyclic graph where each network node is a graph branch, it's called the hash-graph.

But if you know what everyone else know (or knew at some time) than you can locally simulate a voting algorithm (and deterministically know what a node in that state would have voted). This virtual voting enable to get a bit rid of evil nodes since they can't cheat on what you know they would vote knowing their state. The whole thing is now to provide a mean to be sure that eventually every loyal node will have the same answer when they do a virtual voting. This is possible by defining the seeing and strongly-seeing relations: a transaction A sees B if B is among her ancestors in the hash-graph and A strongly-sees B if A can see transactions of 2/3 of the network nodes, each of which can see B. This way it can be shown that eventually every transaction will be strongly seen by everyone and they will all decide the same.

Actually it's a bit more complicated but you get the general idea :) ... Any thoughts?

Edit: I am toying a bit with this algorithm and I have a prototype implementation in python here if some of you prefer to read code.

[Lapin0t]

Hey! Some updates: my python prototype seems to fully work and I added some interactive visualization to see it working. But most importantly, I implemented a slightly different version of the algorithm right on top of IPFS objects (as what is called a merkle DAG in IPFS is quite the same as what is called hashgraph in Swirld) (it lives in the ipfs branch). Some benefits are:

• I don't have to bother with crypto AND networking.
• Syncing is much more efficient since there is deduplication (syncing with a remote node now only means to check what it's head is with an IPNS query).

To sum up, if I didn't make any bug, this is an implementation of a distributed transaction-based database which is consistent and partition tolerant but still quite available (some local testing showed quite acceptable consensus delays although I had to run every node on my computer) on top of IPFS.

I did quite some testing of the vanilla (non-IPFS) version so the algorithm seems to be right, but I have trouble setting up a testing environment for the IPFS version: is there a simple way to run multiple daemons with different identities locally (like maybe specifying the config file location)?