FBA (federated Byzantine agreement) and Algorand


#1

Il y a aussi le FBA (federated Byzantine agreement) inventé par David Mazières qui est prof d’informatique à Standford. C’est utilisé par Stellar.

Vidéo de présentation et pdf


Holochain, shared-data-integrity without proof of work (and without proof of shake too)
Holochain, shared-data-integrity without proof of work (and without proof of shake too)
#2

Super ces slides sur stellar !

Le protocole de federated bizanthine agreement a l’air particulièrement adapté à Duniter. Il faudrait vérifier le fonctionnement avec des noeuds qui sont très régulièrement down comme dans l’usage que peuvent en avoir les utilisateurs de Duniter.


#3

Je ne saurais pas me prononcer sur ce FBA. Mais, voici les points négatifs de Bitcoin vis-à-vis de Stellar et son protocole FBA :

Point par point :

  • « High latency» : peut être résolu par les Lightning Networks
  • « trust determined by computing power » : résolu par la toile de confiance

Ce qui déjà minimise les points négatifs. Il reste le dernier point « modest computational security assumes rational attackers » que je ne comprends pas. Donc bon, je ne vois pas trop l’intérêt pour Duniter.


#4

C’est la théorie des jeux utilisée par bitcoin je pense, selon laquelle un attaquant n’a d’intérêt à attaquer un réseau que selon un rapport coût/bénéfices/risques.

Dans un réseau cryptomonnaie avec une faible puissance de calcul, est ce que ça reste vrai ? C’est en tout cas l’hypothèse bitcoin…


#5

À la base, à l’époque de uCoin, j’étais parti sur ce système de vote décrit dans le FBA pour définir dans quel ordre ajouter les modifications dans la BDD commune, en bien moins sophistiqué toutefois.

Et du coup, je suis très vite tombé sur la même problématique : s’il y a des votes pour définir l’ordre des données, comment définir l’ordre des votes eux-mêmes ? Car on peut voter plusieurs fois et avec des valeurs différentes, ne pas recevoir tous les votes, avoir des votes tardifs, etc. Comment décider de façon commune dans un tel contexte ?

Le problème central me semble bien être la synchronisation. La preuve de travail, dans un contexte P2P non contrôlé, est vraiment une solution très difficile à détroner.

Je ne demande qu’à voir mieux ceci dit !


#6

Je m’auto-réponds, suite à la lecture du sujet « De la lecture sur Proof Of Stake » (Algorand).

En réalité c’est possible de définir l’ordre des votes, contrer les attaques aux multiples votes, la réception partielle ou tardive des votes. J’ai compris par l’étude d’Algorand qu’en fait il suffit de partir de quelques principes de base acceptables comme :

  • la majorité du réseau est honnête (> 2/3 par exemple)
  • chaque nœud honnête ne vote qu’une seule fois par étape
  • chaque nœud honnête ne comptabilise qu’un seul vote par émetteur et par étape
  • chaque nœud honnête suit le même processus de consensus que les autres nœuds honnêtes

Alors par un mécanisme de sélections successives, avec quorums et tirages aléatoires, il est possible d’affirmer qu’il existe un consensus légitime.

Ce problème est effectivement résolu dans Algorand par les sélections successives du bloc qui fait éventuellement consensus, il y a en gros 4 chambres successives de sélection :

  1. La chambre de proposition (très petite, de 1 à 70 participants max)
  2. La chambre de réduction (+ grande que 1., max 2.000 participants)
  3. La chambre de décision (= 2., max 2.000 participants)
  4. La chambre de confirmation (+ grande 3., max 10.000 participants)

Chaque participant = 1 nœud, tout cela est pensé pour fonctionner en contexte informatique et automatisé.

En cas d’échec dans l’une des étapes de 1. à 2., un bloc par défaut déterminé à l’avance est proposé par tous les nœuds honnêtes. De même en cas d’échec de décision d’un bloc sur l’étape 3, ce même bloc fait aussi office de solution de repli. En cas d’échec à l’étape 4., le consensus est considéré comme « tentative » et ne sera réellement officialisé qui si un bloc futur est marqué comme « définitif ».

Enfin il peut tout de même exister des forks, et cette solution de votes ne dit rien quant à la stratégie de résolution de fork. À noter que les auteurs d’Algorand prétendent que la probabilité de forks est considérée négligeable, hors attaque.


#7

ET du coup quel est l’issuer de ce bloc par défaut, ou alors la notion d’issuer n’existe plus dans ce nouveau concept ?


#8

Oui dans Algorand il n’y a pas de notion d’émetteur pour ce bloc, néanmoins on peut imaginer une clé connue de tous si un tel principe était appliqué à Duniter. Par exemple la clé d’identifiants secrets duniter // duniter, que n’importe quel nœud peut signer.