Difference between revisions of "Collective decisions"

From IridiaWiki
Jump to navigationJump to search
 
(34 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Goal ==
 
== Goal ==
   
  +
* General goal: Reach consensus in a reasonable amount of time if more than 50 % of the robots are honest (secure decentralized decision making)
* Reach consensus: What is the most frequent color?
+
* 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?
 
* Method: Use the existing approach with some variations and add a security layer on top of it
 
* 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, ...)
 
* Scalability: Robots can be added to the swarm at any time (to increase accuracy, size of the explored area, ...)
* Trustlessness: The swarm members are untrusted (you don't have to know which organization or person a robot belongs to; robots don't have to authenticate themselves, you don't have to know if a robot sends right or wrong information, you don't have to identify a robot)
+
* Trustlessness: The swarm members are untrusted (robots don't have to authenticate themselves, you don't have to know if a robot sends right or wrong information, you don't have to identify a robot, you don't know if the peers further propagate your messages, you don't have to know which organization or person a robot belongs to, ...)
   
 
== Challenges ==
 
== Challenges ==
Line 11: Line 13:
 
* Asynchronicity (some robots might be in the dissemination state, some might be in the sense state)
 
* Asynchronicity (some robots might be in the dissemination state, some might be in the sense state)
 
* Absence of global information/trusted third parties -> no one collects the votes, they get propagated in a peer-to-peer manner
 
* Absence of global information/trusted third parties -> no one collects the votes, they get propagated in a peer-to-peer manner
* AND malicious intruders/failing sensors (Byzantine robots)
+
* Malicious intruders/failing sensors (Byzantine robots)
   
 
== Approaches ==
 
== Approaches ==
   
 
=== Classical non-secure approach ===
 
=== Classical non-secure approach ===
* Define initial swarm
+
* Create initial robot swarm
 
* Each robot has an initial opinion (one of the colors)
 
* Each robot has an initial opinion (one of the colors)
 
* Robots move arbitrarily in the area
 
* Robots move arbitrarily in the area
Line 36: Line 38:
 
* Create initial robot swarm (e.g., 25 robots) and provide each robot with 10 ETH in the genesis block.
 
* Create initial robot swarm (e.g., 25 robots) and provide each robot with 10 ETH in the genesis block.
   
The general setting is the same as above. However, now two types of robots are explicitly considered:
+
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:
 
* Honest (working) robots that work according to a protocol similar to the one above:
 
** Sense: same as above
 
** Disseminate: mine and send own color opinion to peers:
 
** 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
 
*** 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
*** The longer the opinion gets disseminated, the higher the chance that it will be included in the next block, since it will reach more miners (instead of increasing the dissemination time, another possibility would be to distribute a confidence value together with the opinion)
+
*** Dissemination time is based on relative frequency of that color in the sensor readings. The longer the opinion gets disseminated, the higher the chance that it will be included in the next block, since it will reach more miners (instead of increasing the dissemination time, another possibility would be to distribute a confidence value together with the opinion)
 
*** Robots further propagate the voting transactions across their peers and receive other opinions
 
*** Robots further propagate the voting transactions across their peers and receive other opinions
 
*** Additionally, they perform the proof-of-work and try to be the first to solve the mining puzzle
 
*** 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 can not be a part of the swarm anymore.
+
*** 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.
** Sense: same as above
 
 
* Byzantine robots: can do anything (see risks above)
 
* 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. Therefore, it can be in the disseminate 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). 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.
+
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. Once attackers have gathered enough ETH to vote, they will have to follow the majority opinion. A smart contract could also put limits on the amount of time a robot is allowed to disseminate its opinion. Maybe, there is also a possibility to determine, if the dissemination time is not according to the sensor inputs of a robot at all (e.g., if robots in the proximity have very different sensor readings, one could also use some form of outlier removal or the robot has to send a proof 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):
 
The influence of Byzantine nodes in a blockchain-sense is also limited (even if they have more than 50 % processing power):
* They can never make up transactions using someone else's identity (due to the private/public key + signature); therefore, they cannot steal tokens/reputation
+
* They can never make up transactions using someone else's address (due to the private/public key + signature); therefore, they cannot directly steal tokens/reputation (they can only steal tokens by reversing transactions)
   
 
However, Byzantine nodes can (if they have more than 50 % processing power):
 
However, Byzantine nodes can (if they have more than 50 % processing power):
Line 60: Line 62:
 
* Prevent transactions to be included into the blockchain
 
* 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).
+
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 ====
 
==== Proof-of-Stake Outline ====
   
I don't know enough about Proof-of-Stake yet to make this approach watertight but a rough outline could look as follows (see also https://blog.ethereum.org/2015/01/10/light-clients-proof-stake/):
+
As we already discussed, it could be that an attacker can easily perform a 51 % attack since robots are computationally rather limited. Therefore, an alternative could be to use Proof-of-Stake. I don't know enough about Proof-of-Stake yet to make this approach watertight but a rough outline could look as follows (see also https://blog.ethereum.org/2015/01/10/light-clients-proof-stake/):
   
# Each robot is a potential blockmaker/signer; they put down a security deposit recorded in a smart contract; to receive enough ETH for the security deposit in the beginning, they have to do something useful first: for example, some physical proof-of-work (provide other members with electricity to charge their batteries, collect commodities, take images of an area, perform classical hash-based proof-of-work, ...)
+
# To become a potential blockmaker/signer; robots have to put down a security deposit (recorded in a smart contract); to receive enough ETH for the security deposit in the beginning, they have to do something useful first: for example, some physical proof-of-work (provide other members with electricity to charge their batteries, collect commodities, take images of an area, perform classical hash-based proof-of-work, ...)
 
# For each block (block time is based on fixed timing and not determined by the difficulty of a mining puzzle): a function generates a random number R (in a deterministic manner based on information in the blockchain); based on this number, the blockmaker and signers are selected (e.g., 1 blockmaker + 15 signers) relative to their deposit amount
 
# For each block (block time is based on fixed timing and not determined by the difficulty of a mining puzzle): a function generates a random number R (in a deterministic manner based on information in the blockchain); based on this number, the blockmaker and signers are selected (e.g., 1 blockmaker + 15 signers) relative to their deposit amount
 
# Blockmaker and signers potentially sign the block
 
# Blockmaker and signers potentially sign the block
Line 73: Line 75:
 
## list of signatures from the blockmaker and the signers
 
## list of signatures from the blockmaker and the signers
 
## Merkle root
 
## Merkle root
# A block is valid if it is signed by the blockmaker and m out of n signers (e.g., 15 out of 25). The problem here could be that the potential signers are not reachable. Therefore it is maybe enough if only 10 out of 25 signers sign a block.
+
# 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
 
# 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
 
# 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
  +
# The blockchain with a combination of the most signatures/votes is considered the true blockchain
   
 
== Experiments ==
 
== 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
 
* 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?
 

Latest revision as of 14:08, 24 November 2016

Goal

  • 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?
  • 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, ...)
  • Trustlessness: The swarm members are untrusted (robots don't have to authenticate themselves, you don't have to know if a robot sends right or wrong information, you don't have to identify a robot, you don't know if the peers further propagate your messages, you don't have to know which organization or person a robot belongs to, ...)

Challenges

  • Noise (of sensors, actuators, communication channel)
  • Asynchronicity (some robots might be in the dissemination state, some might be in the sense state)
  • Absence of global information/trusted third parties -> no one collects the votes, they get propagated in a peer-to-peer manner
  • Malicious intruders/failing sensors (Byzantine robots)

Approaches

Classical non-secure approach

  • Create initial robot swarm
  • 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 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)

Risks

  • Robots can disseminate wrong color preference
  • Robots can stop disseminating at all
  • Robots can only disseminate and never sense
  • New members are just included without any security check

=> In the case of (many) Byzantine robots, they will never reach consensus, reach consensus only very slowly or reach consensus but not on the right color

Blockchain-based approach

  • Create initial robot swarm (e.g., 25 robots) and provide each robot with 10 ETH in the genesis block.

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:
    • Sense: same as 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
      • Dissemination time is based on relative frequency of that color in the sensor readings. The longer the opinion gets disseminated, the higher the chance that it will be included in the next block, since it will reach more miners (instead of increasing the dissemination time, another possibility would be to distribute a confidence value together with the opinion)
      • Robots further propagate the voting transactions across their peers and receive other opinions
      • 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)

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.

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):

  • They can never make up transactions using someone else's address (due to the private/public key + signature); therefore, they cannot directly steal tokens/reputation (they can only steal tokens by reversing transactions)

However, Byzantine nodes can (if they have more than 50 % processing power):

  • Reverse transactions from not too long ago (and, therefore, double spend transactions: vote on red and green)
  • 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). 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

As we already discussed, it could be that an attacker can easily perform a 51 % attack since robots are computationally rather limited. Therefore, an alternative could be to use Proof-of-Stake. I don't know enough about Proof-of-Stake yet to make this approach watertight but a rough outline could look as follows (see also https://blog.ethereum.org/2015/01/10/light-clients-proof-stake/):

  1. To become a potential blockmaker/signer; robots have to put down a security deposit (recorded in a smart contract); to receive enough ETH for the security deposit in the beginning, they have to do something useful first: for example, some physical proof-of-work (provide other members with electricity to charge their batteries, collect commodities, take images of an area, perform classical hash-based proof-of-work, ...)
  2. For each block (block time is based on fixed timing and not determined by the difficulty of a mining puzzle): a function generates a random number R (in a deterministic manner based on information in the blockchain); based on this number, the blockmaker and signers are selected (e.g., 1 blockmaker + 15 signers) relative to their deposit amount
  3. Blockmaker and signers potentially sign the block
  4. Block header consists of:
    1. hash of the previous block
    2. list of signatures from the blockmaker and the signers
    3. Merkle root
  5. 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.
  6. Blockmaker and signers get a small signing reward
  7. 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
  8. The blockchain with a combination of the most signatures/votes is considered the true blockchain

Experiments

  • 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