Hashgraph - Blockchainless consensus


#1

C’est sorti aujourd’hui, techniquement ça a l’air intéressant ( https://squawker.org/technology/blockchain-just-became-obsolete-the-future-is-hashgraph/ ).

Ca s’appuie sur des votes (algo Bizantine) + un gossip of gossip. Je cite les développeurs :

Note that we are our own consensus algorithm. While Ethereum is looking at PoS with Casper, our algorithm uses something called Virtual Voting – its a voting system – without having to do the votes. Hashgraph uses a protocol called “Gossip about Gossip” to achieve consensus. Gossip is a well known computer science term, which can be defined as calling any random node and telling that node everything you know, that it does not know. In distributed ledger technology the “baseline” or minimum bandwidth required is that the transactions go to every node. Gossip about Gossip refers to attaching a small additional amount of information to this Gossip, which contains the last person we talked to, hence, we are gossiping about the information we gossiped. Using this information, we can build the Hashgraph. Once we have the Hashgraph, it is extremely easy to know what a node would vote, because we know what each node knows, and when they knew it. We now can use the data from the Hashgraph as an input to 30 year old voting algorithms, and achieve consensus essentially for free. These 30 year old voting algorithms have strong math proofs- they are Asynchronous Byzantine Fault Tolerant, which means we know when we will achieve consensus, guaranteed, and our math proofs make no assumptions about the speed of the internet, due to firewalls, ddos attacks, viruses or botnets. In addition, because of gossip about gossip, Hashgraph is extremely fast, (250,000 transactions/sec), and we also get fair ordering and time stamping on every event.

Par contre, pour l’instant :

  • Ya un brevet déposé sur la technologie
  • Ya juste un SDK
  • Code non libre

Bref, pour l’instant ça a surtout l’air très marketé. Mais c’est un peu curieux de lancer le truc sous une forme privatrice pour quelque chose qui est censé remplacer la blockchain…

Le concept est intéressant, affaire à suivre pour notre R&D de consensus sans proof-of-work. Je laisse le lien vers leurs whitepapers : http://www.swirlds.com/whitepapers/


Connaissez-vous la technologie hashgraph ?
#2

Sur le principe c’est la solution qui me séduit le plus car elle évite à la fois le coût CPU de la PoW grâce au vote Byzantin, tout en évitant le coût réseau du vote Byzantin « fortement synchronisé ».

Car oui, le coût réseau est tout autant un problème que le coût CPU car on transforme un problème de CPU en un problème de ressource réseau : le système dépend très largement de la qualité de celui-ci.

Par exemple dans Algorand que nous évoquions l’autre fois, il y a véritablement besoin d’une stabilité du réseau pour que ça fonctionne correctement, avec une forte contrainte de synchronisation d’horloge pour que l’on parle tous en même temps de la même chose. Ce qui est quand même pas évident à gérer.

Donc ici en gros c’est arbre de Merkle à fond, avec vote Byzantin sur des pans de l’arbre.

C’est vrai qu’il y a moyen de faire hyper efficace en termes de transmission réseau, en envoyant que des diffs et en votant sur des résumés. Et on n’a plus a priori de problème de CPU non plus.

Bon ceci dit, pour l’instant je n’ai rien lu de leurs papiers, je spécule.


#3

Sur l’algorithme ? Est-il seulement possible ?

Si c’est sur l’idée d’utiliser un arbre de hachage, Bitcoin était présent avant, et même hashcash… qu’en penses-tu ?


#4

Oui, c’est surprenant. En fouillant un peu, on trouve d’autres boites qui ont repris le principe de hashgraph ( http://prisma.pw/announcements/press_release_20171016.pdf ) . Ils vont réaliser un algo qu’ils appellent “cryptograph” mais qui renvoie pour le moment à un 404 ( http://prisma.pw/cryptograph.html )

throughout this process, we have realized that there are several academic papers and implementations similar to Swirld’s proprietary Hashgraph. We will therefore develop our own unique leaderless byzantine fault tolerant consensus protocol based on a directed acyclic graph

Ou une implémentation en Go : https://github.com/hashgraph/babble . Cette implémentation précise bien :

The algorithm is protected by patents in the USA. Therefore, anyone intending to use this software in the USA should obtain a license from the patent holders.

C’est le fameux “brevet logiciel”… Il faudrait regarder des alternatives suffisamment proche sur le principe. Avec la WoT, on doit pouvoir se distinguer suffisamment de ce qui est brevetisé ici.

Ils discutent ici sur comment contourner le brevet ( https://lists.hyperledger.org/pipermail/hyperledger-tsc/2017-June/000879.html )

Tout ça est encore très récent, je pense qu’il faut suivre l’affaire, s’y intéresser, voir ce qui est récupérable ou non.


#5

À mon humble avis, swirlds (l’algo en question basé sur leur structure de hash-graph) ça ne mènera à rien du tout. J’avais bidouillé avec il y a un petit moment (https://github.com/lapin0t/py-swirld) et la conclusion a été que ce n’était pas très solide. Déjà les démos (et les définitions) étaient bancales au début, j’ai eu un échange avec lui où je lui ai montré le problème. Il a réussi à debugger les définitions pour que ça marche, mais ça donne un mauvais feeling au truc – j’aurais espéré d’un chercheur (qui est assez confiant pour en faire une startup) qu’il n’y ai pas d’erreur de ce niveau (ça veut à peu près dire qu’il n’a pas du tout fait de peer-review).

Au-delà de ça, l’algo n’a que peu d’intérêt: il scale très mal. Pour suivre l’état d’avancement du consensus (chose qu’il faut faire un nb de fois proportionel au nombre de transactions) il faut maintenir des invariants assez couteux (genre O(n^2) avec n le nombre de noeuds, je me rappelle plus exactement mais c’est au moins ça, probablement plus). Donc c’est rédhibitoire si on veut à terme utiliser ça pour une monnaie ou pour n’importe quelle autre base de donnée qui a vocation à avoir vraiment beaucoup de participants.

Le clou dans le cercueil c’est que tout est basé sur le fait que l’ensemble des participants est fixe et connu de tous (ou sous réserve de trafiquer des trucs, que ce soit géré de manière extérieur et que tout le monde soit d’accord dessus). Or je ne sais pas comment c’est actuellement fait sur duniter, mais j’imagine que la définition des membres est incluse dans le réseau (avec des blocs spéciaux pour émettre des certifications). Concrètement, ça veut dire que la distinction entre membre et non membre est faite au niveau applicatif, c’est-à-dire que le protocol est effectivement utilisable par n’importe qui (n’importe qui peut allumer son ordi et commencer à parler à des noeuds). Or c’est exactement ça qui n’est pas permis par swirlds: il faut un deuxième protocol pour obtenir ou modifier la liste des membres. Sur leur site ils en parlent mais ils sont évasifs (tout simplement parce que c’est ça le coeur du problème et qu’ils ne l’ont pas du tout traité): on peut faire du proof-of-stake sur une autre monnaie mais aucun intérêt puisque on est dépendant ou on peut l’utiliser dans un structure déjà existante (interne à une entreprise…), ok mais c’est pas ce qu’on cherche. Ils sous-entendent qu’on pourrait hard-coder initialement les membres (leur poids dans les votes) et rajouter des transactions spéciales qui permettent à un membre de donner un peu de son poids à un autre, mais franchement c’est pas simple et d’une part c’est pas une solution idéale et d’autre part je ne pense pas que ce soit faisable proprement.


#6

Les membres dans Duniter sont définis au fur et à mesure dans les blocs, qui peuvent contenir autre chose que des transactions.

Pour le peu que j’ai vu de Swirlds, ça pe parait tout pareil. On peut y définir les membres au fur et à mesure.

Enfin bon pour le moment, on ne part aucunement sur ce protocole de hashgraph. Je persiste à penser que notre PoW personnalisée est la solution avec le meilleur compromis qu’on ai sous la main actuellement.


#7

J’en ai revé pendant pres de 6 mois de cette algo. je voulais désesperement en faire la preuve mais j’en étais pas capable et puis mes profs me balancait FLP / Paxos au visage comme si j’etais un idéaliste bisounours avant de découvrir que quelqu’un l’avait fait à peine 6 mois plus tot

SI un jour une équipe se forme pour travailler sur un truc du genre, et tombe sur ce message ajoutez bertrandbenj@gmail.com à la mailing list :wink: !

Si j’ai bien compris hashgrash execute un “bon vieil” algo de consensus en “gossip about gossip” pour trier les messages et simuler le vote. moi je vois ca comme “si tout les membres d’un groupe disent d’ou il tirent leurs opinions quand ils le donne, alors personne n’as besoin de voter car on connaitrais déja les résultats du vote”.
La simple existance de ce protocole me fais sourire… et pleurer !

1 - Y’a t’il un autre “bon vieil” algorithme des années 80 qui, propagé en gossip about gossip, integrerais des notions utilisateurs?

Je penses en effet qu’hasgraph en l’etat est destiné a faire du “trusted decentralized” mais l’idée reste à creuser pour le future