Difference between revisions of "Collective decisions"

From IridiaWiki
Jump to navigationJump to search
Line 32: Line 32:
   
 
=== Blockchain-based approach ===
 
=== Blockchain-based approach ===
* Define initial swarm (e.g., 10 trusted members)
 
   
  +
The general setting is the same as above. However, now two types of robots are explicitly considered:
* Two types of robots:
 
** Honest (working) robots: sense and disseminate as above
+
* Honest (working) robots that work according to the protocol above
** Byzantine robots: can do anything
+
* Byzantine robots: can do anything
   
 
Thanks to the blockchain, the influence of Byzantine robots is limited:
 
Thanks to the blockchain, the influence of Byzantine robots is limited:

Revision as of 23:46, 22 November 2016

Goal

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

Problems:

  • Robots can disseminate wrong color preference
  • Robots can stop disseminating at all
  • Robots can only disseminate and never sense

=> Robots will never reach consensus, reach consensus only very slowly or reach consensus but not on the right color

Blockchain-based approach

The general setting is the same as above. However, now two types of robots are explicitly considered:

  • Honest (working) robots that work according to the protocol above
  • Byzantine robots: can do anything

Thanks to the blockchain, the influence of Byzantine robots is limited:

  • They can never make up transactions using someone else's identity (since )
  • They cannot steal tokens/reputation

However, Byzantine nodes can:

  • Reverse transactions from not too long ago (and, therefore, double spend transactions)
  • Prevent transaction 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).

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, number of light clients) and 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.


  • 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