Duniter utilise la POW?

Je dirai ça la prochaine fois que j’arrive en retard à un rendez-vous! :wink:

4 Likes

@ytreza et les autre.

Voici les grande ligne du protocole qui permettrait de générer un nombre aléatoire pour changer le salt tous les mois, n’hésitez pas à me dire ce que vous en pensez!

On suppose que l’attaquant possède 50% des noeuds, le reste des noeuds étant honnette.

On se base sur une fonction F de type “one way-permutation” sur de taille n (c’est à dire une sorte de Hash sans colision qui ne prend en entrée et en sortie que des chaines de n bits). On suppose que pour ce n donnée l’attaquant et les nœuds honnêtes possèdent tout deux une puissance de calcul permettant de calculer la fonction inverse F⁻¹ en 10000 secondes. Mais on considère que l’attaquant cache peut-être une puissance de calcul 1000 fois supérieure, par mesure de sécurité.

On imagine générer un nombre aléatoire tous les mois. En début de cycle (c’est à dire un mois avant d’avoir besoin du nombre aléatoire) les validateurs des 32 derniers blocks doivent emmètre en l’espace d’un temps d’une seconde, un commit composé d’une liste de 20 nombre F(xi). S’il ne le font pas on les ignore.

La probabilité que l’attaquant possède le contrôle des 32 derniers nœuds est environs de une sur 4 milliard, si on change de salt tous les mois, il faudra attendre en moyenne 33 millions d’années pour avoir le contrôle de tous les noeuds. On considère qu’il y a donc un nœud honnête au minimum.

La probabilité que l’attaquant puisse calculer toutes les fonctions inverse du commit du noeud honnête en moins d’une seconde est inférieure à (1/10000)^20=10^-80 en temps normal et 10^-20 si l’attaquant cache une puisse de calcul d’un facteur 1000.

Suite à cette phase de commit une récompense substentielle est offerte pour la résolution des fonctions inverse de chaque commit. Au maximum la résolution par brute force de cette opération prendrait 10000s = ~3heure de calcul pour les nœuds honnêtes. Bien sur celui qui a émit le commit connaît la solution sans aucun calcul. Dans ces conditions les attaquants n’ont aucun intérêt à ne pas révéler le nombre associé à leur commit: il perdrait une belle récompense, sans pour autant être capable de cacher bien longtemps le nombre associé à leur commit.

Dés que l’intégralité des fonctions inverses de chaque commit a été révélé, pour obtenir le nombre aléatoire on fait alors la somme bit à bit des 32x20 F⁻¹(x_i) commit qui ont été émis. Il suffit alors qu’un seul de ces nombres soit réellement aléatoire et non-connu de l’attaquant au moment ou il a réalisé ses commit pour obtenir un vrai nombre aléatoire non-biaisé.

(Une version un peu plus rafinée avec un pré-commit permet de limiter les dégat dans l’optique improbable ou l’attaquant aurait d’un coup une puissance de calcul bien au delas des limites imaginées, en ne lui permettant de ne biaiser qu’un peu le resultat, sans le determiner completement).

Est-ce qu’on ne pourrait pas faire plus simple pour générer du random consensuel ?

On découpe le temps en cycles composés d’une période A et d’une période B.

Pendant la période A, toute clé publique peut publier un unique document chiffré pour une clé privée aléatoire et signée avec sa clé privée, contenant un nombre aléatoire. L’émetteur d’un tel document conserve la clé privée permettant de déchiffrer ce document.

Pendant la période B, il n’est plus possible d’émettre ces documents. Chaque clé publique ayant émis durant A peut publier la clé privée permettant de déchiffrer le document. Les nombres aléatoires deviennent alors publics. On calcule le hash de l’ensemble des nombres trouvés, ce hash devient la seed pour le cycle suivant (à partir de la fin de B).

Ça me paraît plus simple et ça évite d’avoir à bruteforcer (et on ne se pose pas la question de la puissance). Ça permet aussi d’empêcher tout contrôle sur le hash final, puisque si il y a au moins un nœud honnête, sa seed reste cachée pendant que les attaquants peuvent encore choisir la leur.

C’est cette technique que j’utilise pour choisir les commentaires des transaction servant d’identifiants uniques dans le ĞMixer : il est le hash de trois nombres, fournis respectivement par le client, l’émetteur, et le récepteur. Il est donc imprévisible et incontrôlable.

@tuxmain

Non car tu donne la possibilité à celui qui a émis un document en phase A de le réveler ou pas en phase B en fonction de ce que revèlent les autres, ce qui lui permet de gravement biaiser le résultat. En l’occurence en moyenne d’un bit pour 2 compte. (Tu peux améliorer ça en refaisant un tour avec élimination dès que quelqu’un s’abstient, mais c’est contraignant et tu as toujours un biais de log2(n)/2 bits ou n est le nombre de compte attaquant).

J’avais pensé à ca au début, je ne suis pas allé réfléchir à ce genre de solution par bruteforce pour le plaisir! :wink: Note que en pratique le brute-force ne devrait être que rarement nécessaire, car personne n’a intéret à ne pas réveler de lui-même le nombre correspondant à son commit dans mon système.

C’est le schéma commit/reveal, par exemple utilisé dans Tezos.

Et s’ils le font à 0.9 sec, à 0.99, à 1.01, qu’est-ce qu’il se passe ?
Qui décide s’ils doivent être ignoré ?
Ah mon avis ça va donner le même pb que dans le commit/reveal quand un noeud ne reveal pas.

Je vais décrire plus en détails le protocole un peu plus tard et rédiger un ensemble cohérent.

Ah mon avis ça va donner le même pb que dans le commit/reveal quand un noeud ne reveal pas.

Pourquoi? Dans ce protocole là il sera obligé de reveal, de grés ou de brute force! :wink: Et c’est la toute la différence. (Quelqu’un ne peut pas influancer le résultat en s’abstenant de commit à un moment ou il n’a aucune info sur le reveal des autres).

En effet (par contre je ne comprends pas bien ton calcul de proba, pour moi à le groupe d’attaquants à n complices peut choisir le hash final parmi 2^n possibilités).

On peut rendre cette attaque plus difficile en ne comptant pas les derniers d % reveals. Puisqu’il faut révéler en dernier pour choisir le hash final, l’attaquant doit parier sur le moment où il doit révéler. C’est d’autant plus dur qu’il y a de membres (et 2 attaques en compétition auront encore plus de chance d’échouer).

Ton système est intéressant aussi, en fait pour simplifier c’est le même mais en remplaçant la phase révélation par du bruteforce distribué, c’est bien ça ?

Ce système ne permettant pas de difficulté personnalisée, il me semble dangereux de récompenser le bruteforce. Ou alors on peut limiter le nombre de découvertes par nœud.

Oui donc n bits. Cela dit pour modifier un bits il faut en moyenne 2 comptes ( si tu as juste un tu as une chance sur deux que ça donne le même bit en bloquant le reveal si tu raisonne sur un seul bit). Enfin bref on est d’accord.

On peut rendre cette attaque plus difficile en ne comptant pas les derniers d % reveals

Ca ne fait que déplacer le problème. L’attaquant prendra en compte cela et deplacera son attaque juste avant que 100-d% ont été reveal.

Ton système est intéressant aussi, en fait pour simplifier c’est le même mais en remplaçant la phase >révélation par du bruteforce distribué, c’est bien ça ?

Oui du bruteforce si l’attaquant refuse de reveal contre une récompense ce qui est débile car il sait que son reveal va être bruteforcé et qu’il va perdre sa récompense pour rien. Le but n’est pas de récompenser le brutforce. Le bruteforce est juste un outils de dissuasion de telle manière qu’il n’y en ai pas besoin, et que chacun fasse son reveal.

Ok, l’idée est intéressante!
Cependant, il faut vérifier que ça ne donne pas d’autres possibilités d’attaques, et qu’il existe bien des paramètres qui font que ça fonctionne.
Par exemple, je supposerai plutot que l’attaquant a au plus un million de fois la puissance de calcul des noeuds honnetes.

On est d’accord qu’un “noeud” correspond à un membre calculant de la toile de confiance ?

Que ce passe-t-il si 10% des membres sont malhonnetes, et possèdent 10^6 fois la puisssance de calcul des membres honnetes ? Si aucun d’entre eux ne reveal, est-ce que les honnetes sont obligés de calculer toutes les 10% de seeds par bruteforce ? Est-ce que ça peut bloquer la chaine pendant des mois selon le paramètre de sécurité ?

1 Like

Si on suppose qu’il faille que l’attaquant au pire du pire puisse résoudre le problème en 10s (la proba qu’il resolve les 20 en 1s est alors < 10^-20) , si ça prend un million de fois plus pour les noeuds honnetes ça fait 110 jours environs. Le problème c’est que les nouveux membre doivent attendre le changement de SALT pour participer au consensus. Sinon il peuvent choisir leur clef publique pour tricher.

On est d’accord qu’un “noeud” correspond à un membre calculant de la toile de confiance ?

Non quand je disais 1000 fois plus c’est par rapport à la somme de toute la puissance dont peut disposer l’integralité des noeuds honetes y compris en la louant juste au besoin.

Est-ce que ça peut bloquer la chaine pendant des mois selon le paramètre de sécurité ?

A mon avis il faut que ça ne bloque que le changement de salt pas la chaine. Et que la récompense pour trouver le reveal augmente avec le temps, de telle manière qu’il y ai de plus en plus d’incitation à trouver de la puissance de calcul pour résoudre le problème.

il faut vérifier que ça ne donne pas d’autres possibilités d’attaques

Si tu ajoutes un pre-commit (une annonce d’un hash de la concatenation des 20 nombres aléatoires du commit) l’attaquant qui aurait une puissance de calcul inatendue pourrait au mieux biaiser le résultat de la meme manière que le système phase A phase B decrit plus haut.

Pour ne pas être bloqué dans le cas d’un commit trop difficile, on peut ajouter un timeout : quand un nœud estime avoir passé trop longtemps sur un commit sans le réussir, et que personne d’autre ne l’a réussi, il le dit. Si tous les commits non résolus sont consensuellement trop difficiles, on les abandonne et on fait avec ce qu’on a.

@pparent76 remarque importante concernant le récompense dont tu parle : qui la financerai ?

Si c’est hors-protocole comme remuniter alors ça ne vaut rien. Et si c’est dans le protocole alors d’ou tire tu la monnaie de cette récompense :

  • Si c’est par création ce n’est plus une monnaie libre car sa création n’est pas symétrique dans l’espace et dans le temps. Toute récompense basée sur la création monétaire est prohibée et sera strictement refusée par tout développeur ayant compris ce qu’est une monnaie libre: c’est donc impossommesible dans le cadre de la G1.

  • Si c’est par ponction des DU ou sources de Ğ1 existantes cela pose un problème concernant de consentement.

La seule solution que je vois :

faire payer les membres forgeron, une somme fixe ou variable pour chaque bloc forgé (ce qui dés-incite a forger beaucoup de blocs donc c’est bien). Les sommes récoltées financerais une caisse commune gérée par le protocole et qui donnerai automatiquement la récompense dont tu parle dans ta proposition.
L’avantage de cette solution de financement c’est que si tu change le salt tout les N blocs tu est certain de la somme récoltée en N blocs donc certain du montant de la récompense.

1 Like

Pour l’instant j’ai pas trop pensé à ça, car ce protocole auquel je réfléchit peut s’adapter à plusieurs type de monaies.

Mais est-ce que les frais de transaction son inenvisageable dans la Ğ1? La question se pose d’autant plus dans le cas actuel de la POW.

Si c’est protocolaire c’est contraire au concept de monnaie libre et notamment contraire aux 2èmes et 3èmes libertés économiques : Appendice 1 : Commentaires sur les quatre libertés économiques — Théorie Relative de la Monnaie v2.718

C’est pourquoi je n’ai même pas émis l’idée, la contribution doit être volontaire, l’acte de forger un bloc est volontaire, ce n’est pas une obligation au niveau individuel (même si c’est une obligation collective). Alors que pouvoir réaliser des transactions est une obligation au niveau individuel (tout humain a besoin d’échanger, je considère le cas théorique on l’on aurait une zone économique avec une monnaie libre comme seule monnaie, car si ce cas théorique idéal mène a des privations de libertés non nécessaires alors autant arrêter tout de suite ce qu’on fait).

En revanche, j’ai déjà expliqué en privé a certains qu’il y aura très probablement des frais de transactions hors-protocole tôt ou tard, car tout membre est libre de modifier son nœud pour n’accepter que les transactions qui donne des frais a telle adresse, on ne peut pas l’en empêcher, mais c’est hors-protocole donc ça ne s’impose pas a tous. Il y aura toujours des noeuds sans frais quittent a n’accepter que les transactions des membres de leur groupe local.

J’ai fait un petit programme pour tester ce générateur de hasard en local (sans la gestion du réseau et sans vérifier vraiment la sécurité), ça fonctionne bien. Tous les nœuds ont bien le même hash final à tout moment.

Je pourrais essayer de lui ajouter rapidement la couche réseau ainsi que les vérifications complètes.

Tu as utilisé quelle fonction de “one way permutation”?

Du coup, si on imagine que le réseau va grandir, à un moment il n’y aura plus de place dans les blocks, donc chaque membre qui crée un block ne va laisser passer que les transactions de ses amis, et si le réseau grandit encore, seuls ceux qui auront beaucoup de chance pour créer un block, ou auront des très bons amis vont pouvoir faire des transactions ?

Au fait, vous avez une idée du nombre de transactions par seconde maximum dans Duniter ?

Pour passer du nombre aléatoire au hash du commit c’est SHA256, pareil pour passer des nombres révélés au hash final, le SHA256 de la concaténation de tous les nombres triés. J’ai fait simple, est-ce qu’il y a besoin d’un type de hash particulier ?

Oui il faut impérativement un hash qui soit une permutation, sinon tu n’es pas à l’abris que l’attaquant prenne un nombre qui n’est pas du tout de longeur n.

Sinon si on avait une fonction de captcha F, inversable facilement seulement pour un humain (donc en forcement plus que 1 seconde), ça résoudrait pas mal de problèmes. Malheuresement je crois que de nos jour ça n’existe plus trop de manière fiable…

Il suffit de refuser tout nombre qui n’est pas de la bonne longueur. Plus on passe de temps à bruteforcer un hash, plus la longueur probable du nombre augmente, donc quand il devient trop improbable qu’il soit assez court, on arrête et on ne le prend pas en compte.

Oui pour la captcha je me suis penché dessus, c’est impossible aujourd’hui. En plus, on n’a pas envie de résoudre des captchas en permanence pour faire tourner la monnaie…