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! 
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é ?
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.
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…
Comment tu prouves à tous qu’il n’est pas de la bonne longueur et que tu as bien fais les calculs pour en être sur, juste à partir du hash, très compliqué. Si tu prend une fonction de type “one way permutation”, ça résout le problème.
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…
Ça aurait été 32 par mois pour tous le réseau, je pense que ça aurai été soutenable.
Au début on ne se préoccupe pas de sa taille puisqu’elle est inconnue. On ne peut pas prouver qu’il est invalide, seulement qu’il est valide. La seule chose qui fait que le nombre est pris en compte, c’est qu’un membre le trouve. Si aucun ne le trouve, il est juste considéré invalide.
Là je montre seulement que ça peut fonctionner en utilisant du SHA, mais je suis d’accord sur le fait qu’utiliser la permutation permet d’éviter de perdre son temps à essayer avec des commits invalides.
La taille maximale des blocs est évolutive :
Le nombre de tx par seconde aussi, par conséquent.
Il faut que je vous partage ce magnifique billet explicatif relatif au problème de la synchronisation dans un système distribué. C’est une vraie mine d’or, très bien vulgarisé ! (attention, requiert un certain niveau technique quand même).
De quoi bien baliser le terrain pour éviter de partir sur une fausse route 
je l’aurais eu à mes débuts, j’aurais éviter de perdre 2 semaines sur mes histoires d’amendements, où au final j’ai fini par reprendre la solution PoW.
Très inspirant.
Je voudrai rajouter un point que j’ai découvert récemment ( dans une présentation de Ourobouros ) pour générer les hasard de manière distribué et fiable:
Il est possible d’utiliser une technique de “publicly verifyable secret sharing” ( Publicly Verifiable Secret Sharing - Wikipedia ), qui permet à quelqu’un d’envoyer au réseau de manière chiffré un message qu’il a généré (en l’occurence une chaine aléatoire), et d’envoyer aux différent noeuds du réseau des bouts d’information, de telle manière que la majorité d’entre-eux s’ils s’assemblent puissent retrouver le secret original, mais qu’une minorité ne puisse en déduire aucune information.
Cela permet à une majorité de générer du hasard sans qu’une minorité ne puisse le biaiser. Car chaque participant crée un commit, sans qu’une minorité ne puisse connaître le résultat correspondant. Et on est assuré que si la majorité est honnête et coopérative, on disposera de tous les reveals à la fin d’un processus de génération aléatoire distribué: si celui qui a généré le commit ne veut pas faire le reveal, la majorité des nœuds peut le faire à sa place.
Cela parait nettement plus valable et moins tiré par les cheuveux que l’histoire du brutforce inverse des Hash de type “One way permutation” que j’avais proposé au post 83.
Ce protocole n’est valable que dans le cas d’une majorité honnête, contrairement à l’article que j’ai posté plus haut ( https://eprint.iacr.org/2012/643.pdf ), qui a l’avantage de fonctionner avec une majorité non-honnette, mais parait nettement plus complexe à mettre en oeuvre.
Je pense qu’une telle technique pourrait être assez facilement adapté à Duniter pour générer du hasard qui ne puisse pas être biaisé, à partir du moment ou tous les acteurs de la blockchain sont des membres bien identifiés, dont la majorité sont supposé honnêtes.
