#### The LiquidFeedback Blockchain #### by Jan Behrens, Axel Kistner, Andreas Nitsche, and Björn Swierczek, Berlin, July 27, 2018 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. Figure 1 “Nodes and persons”: Five nodes of which each is connected to the other four. Each node has some persons around it: * Node A: 3 persons, * Node B: 3 persons, * Node C: 4 persons, * Node D: 4 persons, * Node E: 1 person. End of Figure 1. 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. Figure 2 “Fully centralized application”: Twelve persons around a single node labeled ‘Single Node’. End of Figure 2. Figure 3 “Completely decentralized application”: Three nodes, labeled ‘Node A’, ‘Node B’, and ‘Node C’, which are all connected to each other, forming a triangle. Each node has one person associated with it. End of Figure 3. 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. Figure 4 “Example of a block in the LiquidFeedback Blockchain”: { "index": 3284, "interval": 600, "previous_hash": "33b55d628a62d086084894dbc43f3a1368ce90227c15f99adb6bde66a88dd0bc", "timeindex": 25480150, "transactions": { "1bd0e00bc2605e193cd939186e10dfcaeae3756dc59331e96642523dc9bd0057": { "data": { "decision": "yes", "identification": "Jon Doe", "intent": "accredit", "person_id": "10a5d0f2b71fe83db8021c4472532e047fce84d43193fa7a0082637be9f2c506" }, "module": "person", "person_id": "10a5d0f2b71fe83db8021c4472532e047fce84d43193fa7a0082637be9f2c506", "signature": "kqM/FlUHGfddRwczbzq4xYgQItA2CE/XyKqcGxruU1utsYg18HeQ0R9t2mDrNSRy\n yojZ0zqNiz/xOw2pw+69YXXNkbnrV1SCXfgMs09nSHcWDtWlziffvf4Lje8i6Br/\nI tZGHjm6vKT1v5KNrAxOSaHisku3GP0eJno1YvYccqfWWKzugBI0YpjKCHbpMQL+\noO x571/7SBmYNxqcRJPttN75JoRQK7AdTs82LLLyWwHCJG2+vg0FPVG+aiDiDGsZ\nQ5N 7CWeaW1AKPiQ2FfD8H1ACNoClLe4ZNIXp88XCEdwFGOEp0CKK4R93VV7/Fnlh\nRREB Mqgk0c/UisHTJ41aow==\n" } "33b55d628a62d086084894dbc43f3a1368ce90227c15f99adb6bde66a88dd0bc": { "data": { "decision": "yes", "initiative_id": "f33ddf23044ed5c0dcbc858015645ae25196a1f1b55397bf2b610b07451 b1964", "intent": "vote" }, "module": "demo01", "person_id": "10a5d0f2b71fe83db8021c4472532e047fce84d43193fa7a0082637be9f2c506", "signature": "IdO7BXd95twQwnb/BWthIhEMFD4PEk/doMY8d8e3mZ3bj+B41bT+LJH0DcqljSbU\n gXAn1q3iVpFI19eCVhenT7inDJTMZBgmjY0TOkz0zyh235HBk/9J/Z2GsK7T9ctk\nK Gp9BVDayFJy/Z9diW/VaWl6GoDL40mQ1m27MEd92iFnr4CVc2QCdcNS/ml1ohPT\nBa IswWXP16yVrnQSXjrUpQtCmpkuU1iGs1NASHK5dCiQ7/VAAkYhW4Ur89xaRapb\nwji uFVA/MsFShCkiDZBl0PDzdc9BbK9jGSUL0U0NUpwzP+0PRwumzPZaF8NmxwLA\nwixd XaB8ZFUVZfHrW+nVQw==\n" } } } End of Figure 4. 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. Figure 5 “Node E picks random persons”: Five nodes of which each is connected to the other four. Each node has some persons around it: * Node A: 3 persons, * Node B: 3 persons, * Node C: 4 persons, * Node D: 4 persons, * Node E: 1 person. Node E is highlighted. One person associated with Node A, two persons associated with Node C, and two persons associated with Node D are marked with a circle. End of Figure 5. 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. Figure 6 “Node E pulls blockchains from other nodes”: Five nodes of which each has some persons around it: * Node A: 3 persons, * Node B: 3 persons, * Node C: 4 persons, * Node D: 4 persons, * Node E: 1 person. Node E is highlighted. One person associated with Node A, two persons associated with Node C, and two persons associated with Node D are marked with a circle. Node E has connections to three other nodes: * connection between Node E and Node A labeled with ‘weight 1’, * connection between Node E and Node C labeled with ‘weight 2’, * connection between Node E and Node D labeled with ‘weight 2’. End of Figure 6. 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. Figure 7 “Mergings blockchains based on majorities while preserving all transactions”: On the left side, a tree is shown. The first (root) block contains the following transaction IDs: * 36667e23... The root node has one descendant block, which contains the following transaction IDs: * 1b3bc02f... * 59231dbd... That block has one descendant block, which contains the following transaction IDs: * cc57c7dc... * 45a319c8... That block has three descendant blocks (I, II, III). Block I contains the following transaction IDs: * 3971ee75... * 9a66b318... * dceac5ff... Block I has a single descendant, which is only shown as a dashed outline and empty. The empty block has another single descendant, which is also only shown as a dashed outline and empty, and has yet another empty descendant depicted in the same style. Block II contains the following transaction IDs: * 9a66b318... * b031f3fa... That block (Block II) has a single descendant, which contains the following transaction IDs: * 04605f08... * 99c6530b... * a5d37a77... That block has a single descendant, which contains the following transaction IDs: * 668d2945... That block has a single descendant, which contains the following transaction IDs: * 654d7329... Block III contains the following transaction IDs: * b031f3fa... * dceac5ff... That block (Block III) has a single descendant, which contains the following transaction IDs: * 04605f08... * a5d37a77... That block has a single descendant, which contains the following transaction IDs: * 668d2945... That block has a single descendant, which is only shown as a dashed outline and empty. During blockchain merge, the first three (common) blocks are preserved and the three branches (I, II, III) are merged as follows: The first merged block contains the following transaction IDs: * 9a66b318... * b031f3fa... * dceac5ff... That block (the first merged block) has a single descendant, which contains the following transaction IDs: * 04605f08... * a5d37a77... That block has a single descendant, which contains the following transaction IDs: * 668d2945... That block has a single descendant, which is only shown as a dashed outline and empty. That (empty) block has a single descendant, which contains the following transaction IDs: * 3971ee75... * 654d7329... * 99c6530b... End of Figure 7. 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). Figure 8 “Network split attack step 1 – Blocking a majority of nodes (A to C) to convince node E of node D's point of view”: The five nodes of Figure 1 are shown with the same numbers of persons associated to each of them: * Node A: 3 persons, * Node B: 3 persons, * Node C: 4 persons, * Node D: 4 persons, * Node E: 1 person. However, Node D and Node E are separated from Node A, Node B, and Node C. Node A, Node B, and Node C are all connected with one another. Node D and Node E are connected with each other. Node D (with 4 persons) is highlighted strongly (black). Node E (with 1 person) is highlighted lightly (gray). End of Figure 8. Figure 9 “Network split attack step 2 – Using a majority of node D and E to convince node C (and thus gaining a majority within the whole network)”: The five nodes of Figure 1 are shown with the same numbers of persons associated to each of them: * Node A: 3 persons, * Node B: 3 persons, * Node C: 4 persons, * Node D: 4 persons, * Node E: 1 person. Now Node C, Node D, and Node E are separated from Node A and Node B. Node A and Node B are connected with each other. Node C, Node D, and Node E are all connected with one another. Node D (with 4 persons) is highlighted strongly (black). Node E (with 1 person) is also highlighted strongly (black). Node C (with 4 persons) is highlighted lightly (gray). End of Figure 9. 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. Figure 10 “Freezing threshold”: A chain of blocks is shown. Somewhere in the chain an arrow points between two connected blocks. The arrow is labeled ‘dynamic threshold’ and has two arrows which point up and down (indicating that the dynamic threshold can move up and down). End of Figure 10. == 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/ References: [GoD] Jan Behrens: “Game of Democracy”. In “The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems”, Issue 2, October 7, 2014, pp. 11-22. ISSN 2198-9532. Published by Interaktive Demokratie e. V., available at http://www.liquid-democracy-journal.org/issue/2/The_Liquid_Democracy_Journal-Issue002-02-Game_of_Democracy.html [PLF] Behrens, Kistner, Nitsche, Swierczek: “The Principles of LiquidFeedback”. ISBN 978-3-00-044795-2. Published January 2014 by Interaktive Demokratie e. V., available at http://principles.liquidfeedback.org/ [Practical] Jan Behrens: “Practical Consequences of Arrow's Theorem for Open Electronic Voting”. In “The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems”, Issue 6, July 27, 2018, pp. 34-37. ISSN 2198-9532. Published by Interaktive Demokratie e. V. [Roadmap] Andreas Nitsche: “Roadmap to a decentralized LiquidFeedback”. In “The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems”, Issue 6, July 27, 2018, pp. 13-17. ISSN 2198-9532. Published by Interaktive Demokratie e. V. ============================================================================= This file is part of: The Liquid Democracy Journal on electronic participation, collective moderation, and voting systems Issue 6, Berlin 2018-07-27 (electronic version 2019-02-23, rev2 2019-02-24) The full issue is available at: http://www.liquid-democracy-journal.org/issue/6/ All rights reserved Copyright © 2018, 2019 Interaktive Demokratie e. V., Berlin, Germany http://www.interaktive-demokratie.org/ Published by: Interaktive Demokratie e. V., Berlin, Germany Edited by: Jan Behrens, Axel Kistner, Andreas Nitsche, Björn Swierczek Imprint and contact: http://www.liquid-democracy-journal.org/imprint Subscription and archive: http://www.liquid-democracy-journal.org/ ISSN-L: 2198-9532 ISSN print version: 2198-9532 ISSN electronic version: 2199-1758 Filename: The_Liquid_Democracy_Journal-Issue006-04-The_LiquidFeedback_Blockchain.txt Encoding: UTF-8