on electronic participation, collective moderation, and voting systems Issue 6
2018-07-27
The LiquidFeedback Blockchain
In this article, we present the LiquidFeedback Blockchain, an alternative approach to the blockchain. Unlike proof-of-work schemes, which require mining, or many proof-of-stake schemes, which require special consideration of the nothing-at-stake problem where nodes might take advantage from working against a consensus, our scheme does not require energy-costly mining and, at the same time, does not just cope with multiple heads on the blockchain but even utilizes them to find a consensus. Our consensus-finding algorithm is inspired by swarm behavior commonly found in the animal kingdom.
Our approach isn't just all theory, but along with the publication of this article, we present a working prototype that is implementing the most important aspects described here. Where appropriate, this article will describe further possible enhancements. Our prototype isn't limited to the bare handling of the blockchain but provides a module framework which allows different applications to be run decentralized. One such demo application demonstrates the principle of a decentralized accreditation, and another demo application is a simple voting app to complete our proof-of-concept. [Note: This application doesn't incorporate the LiquidFeedback proposition development and decision making process yet but simply allows voting on binary decisions. It is thus only suitable for demonstration purposes.]
For a closer look regarding the motivation, refer also to [Roadmap].
Players on the field
In the remainder of this article and within the source code of the prototype implementation, we distinguish between nodes and persons.
A node is an instance of the LiquidFeedback Blockchain client software that runs on a computer connected to the internet (or any other network), while a person is a human who wants to use the LiquidFeedback Blockchain and trusts a particular node.
Nodes are responsible for engaging in a peer-to-peer communication to exchange new information and agree on a common state. Accredited persons are necessary to empower peers to have their point of view taken into consideration by the other nodes. The more persons trust a node, the higher the influence is of that node within the network.
Unlike traditional peer-to-peer systems, the presented prototype supports:
- centralized application (a single node used by all persons),
- completely decentralized application (each person runs his or her own node),
- or any combinations in between, e.g. some persons have their own node, while other persons share nodes.
In the current implementation, nodes as well as persons are technically identified through their public key. A node that handles a person's account is currently required to retrieve that person's private key. Other (potentially more secure) schemes of empowering a node are thinkable.
A deterministic blockchain
The main purpose of our blockchain is to find a common understanding which transactions (e.g. cast votes) have been submitted to the system at a certain time or time interval. Each block in the blockchain will represent a quantized amount of time. For periods without transactions, each block contains an integer for storing the time interval such that it is possible to skip a big number of time intervals without enlarging the blockchain.
As usual, the hash of each block is computed by hashing a concatenation of the hash of the previous block with the payload of the current block in order to ensure integrity over all previous blocks with a single hash value at the end of the chain. Our approach, however, differs from usual blockchains as follows:
- Each block contains an unordered non-empty set of transactions. This is implemented through a deterministic order (lexicographical sorting of transaction hashes) of all transactions within a block.
- The calculation of the hash of the block is deterministic and there is deliberately no nonce used. Thus equal sets of transactions (at the same time interval) create the same hash, as long as the preceding chain is the same.
Gossiping
The exchange of data between all nodes is implemented through a so-called “gossip” protocol, where nodes randomly connect to each other and exchange data. Eventually every node will have received all information.
In our case, however, the selection of nodes for exchanging new parts of the blockchain must not be arbitrary. Each node that wants to pull information from other nodes randomly selects a number of accredited persons. The corresponding nodes are contacted for a pull-only exchange of their current merged state of the blockchain. (Merging will be described in the next section.) In order to determine the portion of the blockchain that needs to be retrieved from each node, a binary search is conducted to determine a common trunk, after which the remaining blocks are transferred from the corresponding node.
By performing multiple pull-only transfers from a number of nodes (by randomly selecting accredited persons), a node collects a set of different blockchains which can be represented as a tree by combining the common parts. If multiple persons were selected who are associated with the same node, a corresponding weight greater than one is stored for these retrieved blockchains. For authorization, the hash of the head of the exchanged blockchain is signed by the sending peer.
In addition to these pull-only transfers, any two nodes which connect to each other additionally perform a full push and pull exchange of the following data:
- host/port announcements from nodes (to inform other nodes how to contact that node),
- node trust announcements from persons (i.e. statements which node is the trusted node of a person).
These additional announcements are secured by a signature of corresponding node or person, respectively, and contain a serial number to allow overriding previous announcements. An announcement with a lower serial is always superseded by an announcement with a higher serial (assuming a valid signature), in which case the older announcement is discarded and does no longer propagate through the network.
Merging
After a configurable number of persons have been randomly selected and their corresponding merged blockchains have been pulled, a merge algorithm is executed. This is where the LiquidFeedback Blockchain differs from other blockchains: alternative branches of the chain aren't cut off (discarded), but due to the deterministic calculation of hashes (that only depend on the sets of transactions per time interval), it is possible to merge a set of branches into a new blockchain that has a single head.
In order to mitigate attacks when a number of nodes is offline (e.g. due to denial-of-service attacks), there needs to be an adaptive “freezing threshold” on how many time intervals may be changed in a node's own blockchain due to merging other blockchain branches. The adaptive threshold will be described later in this article. All other blocks are allowed to change during the merge process.
Blocks for all time intervals after the freezing threshold are reconstructed sequentially. For each time interval after the frozen part, it is determined which remaining transactions (that are not contained in frozen blocks) are contained in a majority of the pulled (yet unmerged) branches at the given time interval (while taking the weight into account that may be greater than one if multiple persons with the same node have been selected during the random selection process). [Note: A better approach would be to also take those branches into account where the transaction is contained in the current time interval or any previous time interval, but this hasn't been implemented in the prototype yet.] Those transactions with a majority greater than 50% (considering all pulled branches since the last merge as 100%) are accepted for the current time interval. A block with all accepted transactions is appended and a new hash is calculated.
The process described above is repeated until reaching the current time interval based on the system clock of the node. All transactions which have not been incorporated into the merged blockchain earlier end up in the block for the current time interval.
Swarm behavior
The mechanisms described above mimic a behavior similar to swarms: regarding whether to consider a transaction to have been executed during a particular time interval, the node contacts its neighbors (in this case random nodes using a person's trust) and asks for their point of view. Each node will follow a majority point of view of its peers. This leads to an equillibrium where eventually all (or most) nodes will have the same point of view whether a transaction belongs to a particular block or not.
Freezing (and unfreezing) history
In order to mitigate certain kinds of attacks on the network, further security mechanisms have to be implemented. If a majority of nodes is offline, it is easier to maliciously create a wrong majority point of view among the remaining nodes. This could be abused in such way to first isolate some nodes (e.g. through a denial-of-service attack), convince them of an alternative state, and then incrementally allow connections of further nodes to these convinced nodes (e.g. by lifting the denial-of-service attack successively). This way, it may be possible to rewrite history without having to control more than half of the nodes (other than blocking them).
To mitigate this attack, changing history should be limited by freezing the past. Each node would have a threshold index which indicates which blocks are allowed to be modified during the merge process. Any blocks with a time index lower than the threshold index must not be modified during merging, and all blocks with higher time indices must not incorporate transactions contained already in the frozen part of history during merging. The threshold time index can adaptively change. For example, if during a certain time X the merging algorithm would have changed history if it wasn't frozen, the threshold can be slowly adjusted towards the past, eventually allowing a change of the frozen past. The older the blocks are, the more stable they become. If during the time X no part of the frozen history would have been changed if it wasn't frozen, the threshold can be adjusted towards the future (e.g. twice as fast as moving it to the past otherwise). This way, an equilibrium would be reached that is usually close to the present, and denial-of-service attacks would need to be long-lasting in order to change a larger portion of history.
Flood protection
Another possible attack vector is to flood the system with transactions. To mitigate these kinds of attacks, a quota is necessary that limits each person from injecting more than a certain amount of data per time into the system. Any transactions that would violate this limit could easily be removed from the system during merge.
The application layer
The prototype created along with this article comes with a module framework which allows different applications to be run decentralized. Each application runs in a sandbox and provides hooks to process exchanged transactions and modify an application specific state. The framework assists by rolling back the state accordingly after a merge with history change.
A meta-application is thinkable, which would allow to vote on application code. Applications which receive a majority of votes could be automatically incorporated into the system or updated, respectively.
Adopting the full LiquidFeedback proposition development and decision making process for this framework (as one of many possible applications) is a complex task, which will be commented on in the following section.
Adopting the LiquidFeedback process to the LiquidFeedback Blockchain
Adopting the LiquidFeedback process to the LiquidFeedback Blockchain would require a complete reimplementation even though most algorithms (apart from their implementation) could be used. One of the biggest problems is to temporarily hide cast ballots in order to avoid tactical voting. On one hand, votes must be propagated through the network. On the other hand, they need to be kept secret. [GoD] The most promising solution to this problem is a threshold cryptosystem where a majority of nodes may decrypt all cast ballots, which shall not happen until the voting phase has ended and some additional time has passed for history to become frozen.
Another big obstacle is correctability of the system when votes have been recorded wrongly (e.g. due to a hacked node). The article, “Practical Consequences of Arrow's Theorem for Open Electronic Voting” [Practical], also published in this Issue #6 of The Liquid Democracy Journal, covers this issue in depth and reveals some problems that are inherent to all forms of electronic voting.
Availability of code
A working prototype (without the freezing threshold and flood protection) has been published and is available at the official homepage of “The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems” at: http://www.liquid-democracy-journal.org/