Collective decisions

From IridiaWiki
Jump to navigationJump to search

Goal

  • Reach consensus: What is the most frequent color?
  • 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 (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)

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
  • AND malicious intruders/failing sensors (Byzantine robots)

Approaches

Classical non-secure approach

  • Define initial 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 general setting is the same as above. 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
      • 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
      • Honest nodes further promote this transaction across the network
      • Robots also receive incoming transactions
      • Additionally, they perform the proof-of-work and try to be the first to solve the mining puzzle
      • As an interesting additionally study topic, robots have an incentive to move around as much as possible distribute their mined block, get it included in the strongest chain, and receive the mining reward (this is something specific to blockchain-based robot swarms)
    • Sense: same as above
  • Byzantine robots: can do anything (see risks above)

In each block, the blockchain will determine the majority opinion using a smart contract (the smart contract just adds the votes together. Additionally, the robots that voted for this opinion will get a reward (from the 1 ETH that everyone had to send for making a transaction), the others will get nothing. 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). After a block has some confirmations, the robots will adopt the majority opinion (a smart contract can even enforce this, for example, they could just lose all their ETH if they don't do so). 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 loca robotl 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) is 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, it will have some ETH to take part in the voting process.

The setup also prevents attacks on the swarm: 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 or the robot has to send a proof to the blockchain: for example, a picture of the floor).

The influence of Byzantine nodes in a blockchain-sense is also limited:

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

However, Byzantine nodes can:

  • 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). 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).

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 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.


  • 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?