Collective decisions - Revision history

VolkerStrobel: /* Goal */

2016-11-24T13:08:43Z

Goal

VolkerStrobel: Undo revision 7798 by VolkerStrobel (talk)

2016-11-23T23:49:31Z

Undo revision 7798 by VolkerStrobel (talk)

VolkerStrobel: /* Classical non-secure approach */

2016-11-23T23:49:02Z

Classical non-secure approach

VolkerStrobel: /* Goal */

2016-11-23T17:26:28Z

Goal

VolkerStrobel: /* FAQ */

2016-11-23T15:48:44Z

FAQ

VolkerStrobel: /* Blockchain-based approach */

2016-11-23T15:14:59Z

Blockchain-based approach

VolkerStrobel: /* Blockchain-based approach */

2016-11-23T14:38:30Z

Blockchain-based approach

VolkerStrobel: /* Blockchain-based approach */

2016-11-23T14:37:46Z

Blockchain-based approach

VolkerStrobel: /* Experiments */

2016-11-23T14:30:42Z

Experiments

VolkerStrobel: /* Proof-of-Stake Outline */

2016-11-23T14:28:23Z

Proof-of-Stake Outline

@@ Line 1: / Line 1: @@
 == Goal ==
-* General goal: Reach consensus in a reasonable amount of time if more than 50 % of the robots are honest
+* General goal: Reach consensus in a reasonable amount of time if more than 50 % of the robots are honest (secure decentralized decision making)
 * Task: What is the most frequent color in an area?
 * Motivational example: What if there are 100 robots, two colors (red: 52 %, green 48 %) but five robots always send green?

@@ Line 21: / Line 21: @@
 * Each robot has an initial opinion (one of the colors)
 * Robots move arbitrarily in the area
-* Robots have two states: (1) sense color, (2) disseminate/receive color opinion
+* Robots have two states: (1) sense color, (2) disseminate/receive color opinion (robots change preference based on majority voting)
 * Robots only sense the relative frequency of their current color preference and ignore all other colors
 * Dissemination time is a function of the relative frequency of that color (change from sense state to disseminate state is based on time)

@@ Line 21: / Line 21: @@
 * Each robot has an initial opinion (one of the colors)
 * Robots move arbitrarily in the area
-* Robots have two states: (1) sense color, (2) disseminate/receive color opinion (robots change preference based on majority voting)
+* Robots have two states: (1) sense color, (2) disseminate/receive color opinion
 * Robots only sense the relative frequency of their current color preference and ignore all other colors
 * Dissemination time is a function of the relative frequency of that color (change from sense state to disseminate state is based on time)

@@ Line 3: / Line 3: @@
 * General goal: Reach consensus in a reasonable amount of time if more than 50 % of the robots are honest
 * Task: What is the most frequent color in an area?
 * Method: Use the existing approach with some variations and add a security layer on top of it
 * Scalability: Robots can be added to the swarm at any time (to increase accuracy, size of the explored area, ...)

← Older revision		Revision as of 15:48, 23 November 2016
Line 83:		Line 83:
	* Compare performance (e.g., time to reach consensus) and resistance to attacks (e.g., maximum number of tolerated Byzantine robots) between the classical setup and the blockchain-based variant		* Compare performance (e.g., time to reach consensus) and resistance to attacks (e.g., maximum number of tolerated Byzantine robots) between the classical setup and the blockchain-based variant
	* Compare different settings in the blockchain-based variant (e.g., block time, design of light clients, ...) and their influence on the performance		* Compare different settings in the blockchain-based variant (e.g., block time, design of light clients, ...) and their influence on the performance
−
−	== FAQ ==
−
−	* Q: Why would the robots keep the blockchain running?
−	** While the incentive to keep the blockchain running among human participants is getting new valuable tokens and guaranteeing the security of existing tokens, the incentive in a blockchain based on robotic participants is more indirect:
−	*** the robots perform a mission that is useful for someone (probably the initiators of the mission)
−	*** the robots belong to a person or organization that benefits from the token
−	Therefore, we can assume that at least some of the robots are programmed to do the right thing and follow the blockchain protocol (state update via generation of valid blocks). In the end, no matter which algorithm you are using, no robot will care if it is dead or alive except if it is programmed to do so. If robots do not follow the protocol, they will have 0 ETH in the end, and will not take part in the voting process, therefore, only the honest nodes will survive (as long as they have some majority).
−
−
−	* Q: Why don't you use an authentification system to include trusted members only?
−	** A classical authentification system can be easily compromised (e.g., once the password is revealed, the entire system breaks down)
−	** The swarm is more flexible without an authentification system: everyone can join at any time
−
−	* Q: How would it work with Proof-of-Stake?
−	The problem here is the inclusion of new members: How does a robot receive some ETH for voting?

@@ Line 48: / Line 48: @@
 * Byzantine robots: can do anything (see risks above)
-In each block, the blockchain will collect votes using a smart contract. Robots that voted for the majority opinion will get a reward (distributed from the 1 ETH that everyone had to send for making a transaction). Robots that never correctly voted for the majority opinion will soon not be able to vote anymore (however, they can prove their usefulness again by mining new ETH). The voting strategy can be implemented in the robots but smart contracts can put constraints on it (e.g., determine when robots can change their opinion). During the experiment, the blockchain will possibly consist of many forks, since information often will not be spread out in the entire network but only in some local robot clusters. However, these forks can be solved once the clusters are reunited and the strongest chain (e.g., the one with the most votes and the most hash power) will be considered as the truth.
+In each block, the blockchain will collect votes using a smart contract. Robots that voted for the majority opinion will get a reward (distributed from the 1 ETH that everyone had to send for making a transaction). Robots that never correctly voted for the majority opinion will soon not be able to vote anymore (however, they can prove their usefulness again by mining new ETH). The voting strategy can be implemented in the robots but smart contracts can put constraints on it (e.g., determine when robots can change their opinion or how often a robot is allowed to vote). During the experiment, the blockchain will possibly consist of many forks, since information often will not be spread out in the entire network but only in some local robot clusters. However, these forks can be solved once the clusters are reunited and the strongest chain (e.g., the one with the most votes and the most hash power) will be considered as the truth.
 Now, let's say a new robot wants to join the swarm, for example, because the experimenter wants to increase the accuracy of the experiment. However, the swarm is autonomous and cannot trust the new member nor the experimenter (in a real-world setting, the swarm might work in a remote area and it might be possible that an attacker sends malicious robots). Initially, the new robot has 0 ETH in this blockchain and cannot vote. However, it can prove its usefulness by mining (or use one of the physical proof-of-work methods mentioned below). Therefore, it can be in the dissemination state, randomly explore the area, collect transactions from the other robots, perform the proof-of-work, and hope that it wins the mining puzzle (the mining reward could also be an interesting parameter: if it consists only of transaction fees, malicious robots have to include many (honest) transactions to actually be able to vote, and, therefore, support the network and the consensus process). After getting the mining reward, the robots can distribute the created block among the network and if it's included in the longest chain, they will have some ETH to take part in the voting process.

@@ Line 39: / Line 39: @@
 The goal is again to determine the most frequent color. However, now two types of robots are explicitly considered:
 * Honest (working) robots that work according to a protocol similar to the one above:
 ** Disseminate: mine and send own color opinion to peers:
 *** Sign transaction "Vote for color x", add 1 ETH (as proof that you are allowed to vote but also as "bet" with the hope to receive back more) and distribute it to the neighbors
@@ Line 45: / Line 46: @@
 *** Additionally, they perform the proof-of-work and try to be the first to solve the mining puzzle
 *** Robots have an incentive to move around as much as possible to distribute their transactions and their mined blocks, get it included in the strongest chain, and receive the mining reward (this is something quite specific to swarm robots)--otherwise, they cannot be a part of the swarm anymore after some time because they will have 0 ETH.
 * Byzantine robots: can do anything (see risks above)

@@ Line 52: / Line 52: @@
 Now, let's say a new robot wants to join the swarm, for example, because the experimenter wants to increase the accuracy of the experiment. However, the swarm is autonomous and cannot trust the new member nor the experimenter (in a real-world setting, the swarm might work in a remote area and it might be possible that an attacker sends malicious robots). Initially, the new robot has 0 ETH in this blockchain and cannot vote. However, it can prove its usefulness by mining (or use one of the physical proof-of-work methods mentioned below). Therefore, it can be in the dissemination state, randomly explore the area, collect transactions from the other robots, perform the proof-of-work, and hope that it wins the mining puzzle (the mining reward could also be an interesting parameter: if it consists only of transaction fees, malicious robots have to include many (honest) transactions to actually be able to vote, and, therefore, support the network and the consensus process). After getting the mining reward, the robots can distribute the created block among the network and if it's included in the longest chain, they will have some ETH to take part in the voting process.
-The setup also prevents malicious intruders: say someone sends 20 malicious robots to the swarm. In the beginning, they cannot do anything, since they do not own any ETH. Therefore, they have to mine first. However, the mining process will help the consensus: transactions get collected and spread across the network in the mined blocks. After some time, attackers have gathered enough ETH to vote. As long as malicious robots are in a minority, it could be that they do not influence the consensus process to a large extent. Additionally, there could be possibilities to determine if votes are Byzantine and not according to the sensor inputs of a robot at all (e.g., by comparing the votes to robots in the proximity, by using some form of outlier removal or Bayesian approach, or by sending proofs of the sensor inputs to the blockchain: for example, a picture of the floor).
+This setup also makes it hard for malicious intruders to join the swarm. As long as malicious robots are in a minority, it could be that they do not influence the consensus process to a large extent. Additionally, there could be possibilities to determine if votes are Byzantine and not according to the sensor inputs of a robot at all (e.g., by comparing the votes to robots in the proximity, by using some form of outlier removal or Bayesian approach, or by sending proofs of the sensor inputs to the blockchain: for example, a picture of the floor).
 The influence of Byzantine nodes in a blockchain-sense is also limited (even if they have more than 50 % processing power):
@@ Line 61: / Line 61: @@
 * Prevent transactions to be included into the blockchain
-To perform an attack, the dishonest nodes have to collaborate to gain more than 50% of the mining power (proof-of-work) or of the tokens (proof-of-stake). There could be also proof-of-stake mechanisms for including new members: e.g., robots could vouch for new members or one could use a hybrid PoS/PoW approach (e.g., difficulty of mining puzzle proportional to the amount of ETH a robot owns). The amount of ETH of a robot could be also used as reputation to weight votes (e.g., color x confidence x reputation).
+To perform an attack, the dishonest nodes have to collaborate to gain more than 50% of the mining power (proof-of-work) or of the tokens (proof-of-stake). The amount of ETH of a robot could be also used as reputation to weight votes (e.g., color x confidence x reputation).
 ==== Proof-of-Stake Outline ====

@@ Line 81: / Line 81: @@
 == Experiments ==
-* Compare performance (e.g., time to reach consensus, maximum number of tolerated Byzantine robots, ...) between the classical setup and the blockchain-based variant
+* Compare performance (e.g., time to reach consensus) and resistance to attacks (e.g., maximum number of tolerated Byzantine robots) between the classical setup and the blockchain-based variant
 * Compare different settings in the blockchain-based variant (e.g., block time, design of light clients, ...) and their influence on the performance

@@ Line 74: / Line 74: @@
 ## list of signatures from the blockmaker and the signers
 ## Merkle root
-# A block is valid if it is signed by the blockmaker and m out of n signers (e.g., 3 out of 5). The problem here could be that the potential signers are not reachable but that could be part of the analysis.
+# A block is valid if it is signed by the blockmaker and m out of n signers (e.g., 3 out of 5). The problem here could be that the potential signers are not reachable since they are too far away but that could be part of the analysis.
 # Blockmaker and signers get a small signing reward
 # If blockmakers or signers try to sign blocks in multiple forks of the blockchain they get explicitly punished and lose their security deposit (and can, therefore, not be part of the swarm anymore until they perform new physical proof-of-work); the robot that provides evidence that a signer tried to sign blocks in multiple forks gets a portion of the security deposit as reward