Transactions anonymes en blockchain : ring signature

Il existe des protocoles efficaces pour anonymiser les comptes et les transactions (zk-SNARKS, Lelantus Spark), mais ils sont très compliqués et obligent à adapter tout le reste : si l’approche UTXO s’y prête bien, l’approche Substrate nécessite de connaître les montants des comptes.

Le ĞMixer est une solution mais il y a beaucoup d’obstacles pratiques à son efficacité (trafic insuffisant, frais de transaction).

Je propose une solution intermédiaire, qui pourrait tenir dans une palette, permettant de faire du mixage en blockchain avec des ring signatures, sans rien changer au reste du runtime.

Soit un ensemble E de clés publiques. Une ring signature est une signature qui peut être forgée par une clé de E et dont on peut vérifier l’authenticité comme “émise par une clé de E” sans savoir laquelle.

Le protocole est comme suit :

  • Les participants publient un extrinsic (avec leur clé publique normale) pour s’inscrire au mixage.
  • À une date donnée, les inscriptions sont closes. L’ensemble E est connu.
  • Les participants publient un document (sans révéler leur clé publique) authentifié par une ring signature, contenant l’adresse de destination.
  • À une date donnée, les sommes sont prélevées sur les comptes participants et ajoutées sur les comptes destinataires. Toute somme non-assignée à un destinataire est envoyée sur la caisse commune.

Les contraintes :

  • Deux signatures d’une même clé anonyme doivent pouvoir être détectées. (signature traçable)
  • La somme transférée par compte doit être la même pour tout le monde.
  • Un même compte devrait pouvoir s’inscrire plusieurs fois pour alimenter plusieurs comptes anonymes, chacun avec le même montant. À voir comment rendre ça compatible avec les deux points précédents.
  • Il faut pouvoir publier un document gratuitement depuis la clé publique anonyme (qui ne correspond pas à un compte), soit avec une règle spéciale pour un extrinsic, soit avec une API supplémentaire et un inhérent. À creuser.
  • Les vérifications en chaîne doivent être rapides. Sinon, on peut ajouter des délais pour laisser le temps à des systèmes hors-chaîne (clients dédiés ou oracles) de dénoncer les fraudes.

Côté client :

  • L’envoi de la signature anonyme devrait être anonyme d’un point de vue réseau (utiliser Tor).
  • Le client peut calculer, à la clôture des inscriptions, le taux d’anonymat du compte destinataire. Il augmente avec le nombre d’identités différentes inscrites.
  • Plusieurs mixages peuvent être chaînés pour augmenter l’anonymat. Problème, les frais feront diminuer la somme, qui ne pourront plus être mixés avec les autres. Je ne sais pas encore comment faire.

[EDIT] Liens :

5 Likes

La crate nazgul est assez mal codée (des points de vue Rust, performance et ergonomie) mais contient assez peu de code, et est plutôt simple.

J’arrive à l’utiliser avec un cercle de N=100 clés (curve25519).

  • La signature est assez rapide (mais pourrait prendre quelques secondes sur une machine peu puissante).
  • La vérification des 100 signatures prend environ une seconde (en x86_64, ce sera plus lent dans le runtime) mais c’est à répartir sur des centaines voire milliers de blocs. Les frais ne seront pas négligeables. Une vérification est en O(N).
  • La recherche de liens (est-ce qu’une même clé a émis plusieurs signatures) se fait entre chaque paire de signatures (N*(N-1)/2) mais est très rapide.
  • La taille d’une signature est 32*(N+1) octets (sans compter la liste des clés publiques).

Il faut pouvoir traiter beaucoup de signatures même s’il y a peu de participants, car le montant devant être le même pour chaque compte de destination (sinon on pourrait relier des comptes destination entre eux, ou à un compte émetteur), le seul moyen d’anonymiser un montant arbitraire depuis un même compte est d’émettre vers plusieurs petits comptes anonymes.

Question : accepteriez-vous d’intégrer une telle fonctionnalité dans le runtime ?

Au moins pas mal de gens (c’est pas rien, c’est pas trois personnes, comme dirait l’autre) s’inquiètent de l’impossibilité pratique de comptes anonymes.

Malheureusement ce système demande une synchronisation entre les inscrits. Un moyen pas trop contraignant pourrait être de faire un mixage par semaine. On s’inscrit pendant la semaine. À la fin de la semaine, les inscriptions sont closes et on peut envoyer les signatures. À la fin de la deuxième semaine les transactions sont faites (ou au fur et à mesure, peu importe en fait). Deux sessions de mixage peuvent ainsi tourner en permanence.

1 Like

Ma réponse courte : oui.

Mais ça doit venir avec une un code clair et commenté, une bonne documentation, des tests, des benchmarks… J’insiste dessus parce que ce n’était pas vraiment le cas pour l’oracle de distance qui a demandé pas mal de travail a posteriori.

La possibilité de transaction anonymes me paraît une garantie importante de confiance dans le système, c’est donc bienvenu. (même si on trouvera toujours du monde pour dire qu’il ne faut pas donner cette possibilité).

1 Like

Je pense que je vais commencer par faire une crate inspirée de nazgul pour la crypto.

Sur les frais :

Le montant à transférer pourrait être réservé sur le compte dès l’inscription au mixage.

Le problème est d’éviter le spam sur les signatures : si elles étaient toutes valides il suffirait de payer leurs frais d’avance lors de l’inscription. Mais on peut spammer des signatures invalides.

La signature (publiée en unsigned extrinsic) doit donc être vérifiée avant d’entrer en piscine. Une signature invalide dans un bloc signifie alors que le forgeron est corrompu, et ce problème peut être réglé humainement par les forgerons. On peut maintenant supposer que les signatures en bloc sont valides. La question des frais est réglée.

Sur les montants autorisés : peut-être qu’on peut autoriser tous les montants. Les utilisateurs auront intérêt à se mettre d’accord pour préserver leur anonymat, et choisir un montant non-conventionnel nuit plus à soi-même qu’aux autres. Si les clients encouragent à mixer plusieurs fois d’affilée pour améliorer l’anonymat, il y aura assez de mixages avec les mêmes montants (diminués d’un multiple des frais).

Il fallait le dire lors de la revue de MR.

:+1:

Dans la MR sur l’oracle, j’ai demandé le minimum en terme de documentation, cf :

parce que c’était assez central, et j’ai eu beaucoup d’occasions de repasser dessus. Là pour les transactions anonymes, il est peu probable que je puisse bosser dessus côté client avant un moment, donc c’est d’autant plus important que d’autres personnes puissent facilement s’approprier ce que tu auras produit. C’est pour ça que j’insiste. Je suis désolé si tu as mal pris ma remarque, c’est juste que je pré-juge de tes productions futures à partir des productions passées.

Les transactions anonymes sont à la fois un challenge en terme d’implémentation et en terme d’adoption. Si je trouve intéressant l’existence d’une pallet de ring signature, ça me semblerait dommage que ce soit juste un bout de runtime dont trop peu de personnes ne se servent pour que les transactions soient suffisamment anonymes. Et ma réponse à ça, c’est :

  • documentation développeurs cœur
  • documentation développeurs de client
  • documentation utilisateur
  • des UI adaptées pour le grand public

Ceci n’existe pas encore pour les oneshot accounts. Même s’ils sont dans le runtime, peu de développeurs de client ont prévu d’implémenter leur utilisation. Ce serait dommage qu’il en aille de même pour les transactions anonymes.

3 Likes

Ok. De toute façon je ne mergerai pas sans l’accord de quelqu’un après relecture. Sur la partie crypto par contre ça va être compliqué de trouver quelqu’un, je verrai s’il est possible de rester fidèle au whitepaper de Monero ou à une implémentation experte existante pour qu’une relecture ne demande pas d’étudier les maths sous-jacentes.

Les oneshot accounts étaient avant tout destinés au ĞMixer à cause des frais de création de compte, mais si ces frais ne sont pas réintroduits et que les (hash/cid de) commentaires en blockchain sont implémentés et que les signatures en anneau fonctionnent, alors les oneshot n’ont plus de raison d’être et autant les supprimer. Je voulais attendre avant de le proposer, peut-être qu’il faudra rétablir les frais si des clients veulent avoir des identicons sécurisés (via le random id)… Tout ça est un jeu de taquin.

UI grand public : tu veux dire des bibliothèques utilisables par les devs de clients ? De toute façon il y aura une crate Rust pour la crypto et une implémentation dans Ğcli. Ça vaudrait le coup de faire une crate genre “duniter-wallet” pour ça mais aussi pour les autres fonctionnalités non-triviales (révocation, changeOwnerKey) que subxt et PolkadotJS ne permettent pas directement. Et oui il faudra aussi que je fasse des libs natives JS et Python (ou contribue à celles existantes).

4 Likes

Oui et Dart aussi stp.
Et Cobol.

En fait les comptes oneshot sont des UTXO…

1 Like

J’ai recodé entièrement la signature/vérification bLSAG à partir du document Zero to Monero (page 29), ça marche. (dépôt sur le GitLab)

Pour vérifier qu’une même clé n’a pas émis deux signatures, pas besoin de faire O(N²) vérifications. Il suffit d’indexer les signatures dans une hashmap dans le storage, avec pour clé le hash de la clé privée qui est fourni dans la signature (et qui ne peut être altéré sans invalider la signature). Si la clé est déjà présente, on a détecté une tentative de double dépense.

Je ne sais pas encore s’il est possible de trouver spécifiquement quelle clé publique a émis une signature de trop. Si oui, on peut lui appliquer des frais. Sinon, on peut soit conserver la première signature et ignorer les suivantes, soit invalider définitivement la première, en guise de frais (la monnaie réservée pour le transfert anonyme sera prélevée et non remboursée).

2 Likes

Je pense que la crate de signature peut être publiée sur crates.io indépendamment de Duniter. Le compte GitHub de Duniter (si c’est possible, sinon quelqu’un ici) pourra en être copropriétaire, au cas où.

Est-ce que quelqu’un voudra relire le code ? Peut-être plus sur l’aspect ergonomie que sur la crypto, à moins qu’il y ait un·e expert·e en crypto ici. Il suit bien le document Zero to Monero et nazgul. Je prépare un résumé plus clair des algos et des preuves. Après cette fonctionnalité n’est pas critique et on peut la livrer comme expérimentale. Le code du runtime devrait aussi empêcher qu’une faille cryptographique permette une double dépense, donc on ne prend pas trop de risque à introduire cette crypto non-auditée.