Découvrez les spécifications techniques du vote anonyme de Vocdoni et les raisons qui nous ont conduits à cette conception.
Ferran
· 16 min de lecture
Avant d'entrer dans les spécifications techniques, il convient de préciser ce que nous entendons par vote anonyme, et pourquoi nous avons retenu cette conception. Dans l'article d'annonce du produit, nous présentons deux formes d'anonymat : le masquage des bulletins et l'anonymat de l'électeur.
Le masquage des bulletins désigne l'anonymat obtenu en cachant le contenu de chaque vote, tandis que l'anonymat de l'électeur rompt le lien entre chaque électeur et son vote, sans dissimuler les votes eux-mêmes. Notre implémentation du vote anonyme repose sur l'anonymat de l'électeur. Pourquoi ce choix ?
Tout d'abord, le masquage des bulletins implique des compromis importants. Pour qu'un processus de vote soit vérifiable de bout en bout, les électeurs doivent pouvoir suivre et examiner le contenu des bulletins qu'ils ont déposés. Si l'anonymat repose sur le masquage des bulletins, la vérifiabilité disparaît : impossible de vérifier que votre vote a été comptabilisé ni d'auditer l'intégrité du scrutin si le contenu de chaque vote est caché.
Autre inconvénient : le masquage des bulletins est difficile à mettre en œuvre dans un système de vote numérique. Une des techniques possibles est le chiffrement homomorphe, qui a été proposé pour apporter un anonymat cryptographique aux systèmes de vote traditionnels. Le chiffrement homomorphe permet d'effectuer des calculs sur des valeurs chiffrées : on peut ainsi obtenir le décompte des votes sans examiner le contenu d'un seul bulletin. Solide en théorie, le chiffrement homomorphe présente néanmoins de nombreux inconvénients qui en font une base peu souhaitable pour une technologie de vote.
Surtout, cette méthode ne permet que des calculs élémentaires sur les bulletins chiffrés, ce qui rend des modes de scrutin comme le vote quadratique ou par classement plus difficiles à mettre en œuvre. De plus, si le chiffrement homomorphe garantit le calcul des résultats, il ne garantit pas la vérification de bout en bout du bulletin d'un électeur. Ce schéma ne fournit aucune preuve cryptographique attestant que le bulletin d'un électeur a bien été inclus et correctement représenté dans les résultats. Nous estimons également que la validation de la preuve homomorphe d'un processus de vote exigerait des ressources de calcul considérables, qui croissent avec la taille du scrutin. Cela pourrait annuler les bénéfices d'un système universellement vérifiable, la vérification ne pouvant être effectuée que sur des machines puissantes et coûteuses, sur une durée prohibitive.
L'anonymat de l'électeur présente plusieurs avantages par rapport au chiffrement homomorphe. D'abord, il permet un degré de vérifiabilité de bout en bout bien plus élevé. Si le lien entre un électeur et son bulletin doit rester opaque pour tout observateur tiers, l'électeur lui-même peut toujours identifier son bulletin. Les bulletins étant visibles, chacun peut suivre son vote depuis le moment où il est déposé jusqu'à son inclusion dans les résultats. Les tiers peuvent en outre vérifier que chaque bulletin appartient à un électeur légitime et que son contenu a été correctement décompté.
L'anonymat de l'électeur permet aussi des conceptions bien plus efficaces sur le plan du calcul. Les systèmes fondés sur l'anonymat de l'électeur n'appliquent le masquage qu'une seule fois, sur la preuve associée au bulletin de chaque électeur, plutôt que sur l'ensemble des résultats à chaque nouveau bulletin déposé. Aucune étape de calcul lourde n'est nécessaire pour rendre les résultats largement accessibles. Les résultats peuvent même être publiés pendant le processus de vote sans compromettre l'anonymat (à condition d'avoir paré les attaques par corrélation temporelle).
C'est pourquoi nous avons intégré l'anonymat de l'électeur à notre mécanisme de preuve de recensement.
Le point de départ du mécanisme de recensement des votants est un arbre de Merkle de recensement. Il s'agit d'une structure de clés publiques hachées, dont chacune représente un électeur éligible du recensement. L'arbre de Merkle permet à tout électeur légitime de prouver qu'il détient une censusKey appartenant au recensement, sans connaître les clés des autres électeurs. L'électeur soumet ensuite cette preuve avec son bulletin. À cette enveloppe de vote est également joint un nullifier : une donnée dérivée de la censusKey de l'utilisateur et de l'electionID, qui correspond de manière unique à son vote.
Utilisée seule, cette preuve permettrait à l'organisateur d'un processus de corréler chaque enveloppe de vote, via son nullifier, avec la censusKey d'un électeur, et donc de désanonymiser le vote. Pour y remédier, Vocdoni utilise des zk-SNARKs afin de garantir l'anonymat du vote.
zk-SNARK signifie zero-knowledge Succinct Non-interactive ARgument of Knowledge, soit « argument de connaissance succinct et non interactif à divulgation nulle ». Un zk-SNARK permet à un utilisateur de prouver à un tiers qu'il possède une certaine information, sans révéler l'information elle-même.
Dans notre cas, les zk-SNARKs permettent aux électeurs de prouver leur appartenance au recensement sans révéler leur secretKey. Concrètement, cela passe par un zk-Circuit, un circuit logiciel conçu pour générer une preuve à divulgation nulle de connaissance (ZKP, Zero-Knowledge Proof).
Nous avons conçu un circuit qui permet aux utilisateurs de générer une ZKP de leur appartenance au recensement sans révéler leur secretKey. Le circuit reçoit des entrées privées et publiques ; les données susceptibles de révéler l'identité de l'électeur restent privées. Les entrées publiques sont transmises dans l'enveloppe de vote afin que les validateurs puissent les confronter à la preuve et s'assurer que l'utilisateur n'a pas voté deux fois.
Le circuit peut servir à tout processus dont le recensement est de taille comparable, et il ne doit être généré qu'une seule fois par taille. Plus précisément, un circuit généré peut être réutilisé pour tout arbre de Merkle de recensement de même hauteur. Comme nous utilisons un arbre binaire, il faut un circuit pour chaque valeur n telle que la taille cible du recensement tient dans 2^n (par ex. 128, 256, ..., 8192, 16384, etc.).
La génération du circuit repose sur une cérémonie de configuration de confiance (trusted setup). Il s'agit d'un processus de génération des clés de preuve et de vérification du circuit ; on parle de « confiance » car, si une seule partie contrôlait l'intégralité de la génération de ces clés, elle pourrait produire de fausses preuves. Une « cérémonie » décentralisée est donc nécessaire pour garantir la fiabilité du circuit. Lors d'une telle cérémonie, plusieurs parties aux intérêts divergents, situées en des lieux différents, effectuent chacune une étape de la génération des clés. Il suffit qu'une seule d'entre elles reste intègre pour qu'il soit impossible de générer une fausse preuve.
La franchise proof est générée en exécutant le circuit zk-SNARK.
index, secretKey, census Merkle-proofcensus Merkle-root, nullifier, election ID, votefranchise proof
Avant d'entrer dans les spécifications techniques, il convient de préciser ce que nous entendons par vote anonyme, et pourquoi nous avons retenu cette conception. Dans l'article d'annonce du produit, nous présentons deux formes d'anonymat : le masquage des bulletins et l'anonymat de l'électeur.
Le masquage des bulletins désigne l'anonymat obtenu en cachant le contenu de chaque vote, tandis que l'anonymat de l'électeur rompt le lien entre chaque électeur et son vote, sans dissimuler les votes eux-mêmes. Notre implémentation du vote anonyme repose sur l'anonymat de l'électeur. Pourquoi ce choix ?
Tout d'abord, le masquage des bulletins implique des compromis importants. Pour qu'un processus de vote soit vérifiable de bout en bout, les électeurs doivent pouvoir suivre et examiner le contenu des bulletins qu'ils ont déposés. Si l'anonymat repose sur le masquage des bulletins, la vérifiabilité disparaît : impossible de vérifier que votre vote a été comptabilisé ni d'auditer l'intégrité du scrutin si le contenu de chaque vote est caché.
Autre inconvénient : le masquage des bulletins est difficile à mettre en œuvre dans un système de vote numérique. Une des techniques possibles est le chiffrement homomorphe, qui a été proposé pour apporter un anonymat cryptographique aux systèmes de vote traditionnels. Le chiffrement homomorphe permet d'effectuer des calculs sur des valeurs chiffrées : on peut ainsi obtenir le décompte des votes sans examiner le contenu d'un seul bulletin. Solide en théorie, le chiffrement homomorphe présente néanmoins de nombreux inconvénients qui en font une base peu souhaitable pour une technologie de vote.
Surtout, cette méthode ne permet que des calculs élémentaires sur les bulletins chiffrés, ce qui rend des modes de scrutin comme le vote quadratique ou par classement plus difficiles à mettre en œuvre. De plus, si le chiffrement homomorphe garantit le calcul des résultats, il ne garantit pas la vérification de bout en bout du bulletin d'un électeur. Ce schéma ne fournit aucune preuve cryptographique attestant que le bulletin d'un électeur a bien été inclus et correctement représenté dans les résultats. Nous estimons également que la validation de la preuve homomorphe d'un processus de vote exigerait des ressources de calcul considérables, qui croissent avec la taille du scrutin. Cela pourrait annuler les bénéfices d'un système universellement vérifiable, la vérification ne pouvant être effectuée que sur des machines puissantes et coûteuses, sur une durée prohibitive.
L'anonymat de l'électeur présente plusieurs avantages par rapport au chiffrement homomorphe. D'abord, il permet un degré de vérifiabilité de bout en bout bien plus élevé. Si le lien entre un électeur et son bulletin doit rester opaque pour tout observateur tiers, l'électeur lui-même peut toujours identifier son bulletin. Les bulletins étant visibles, chacun peut suivre son vote depuis le moment où il est déposé jusqu'à son inclusion dans les résultats. Les tiers peuvent en outre vérifier que chaque bulletin appartient à un électeur légitime et que son contenu a été correctement décompté.
L'anonymat de l'électeur permet aussi des conceptions bien plus efficaces sur le plan du calcul. Les systèmes fondés sur l'anonymat de l'électeur n'appliquent le masquage qu'une seule fois, sur la preuve associée au bulletin de chaque électeur, plutôt que sur l'ensemble des résultats à chaque nouveau bulletin déposé. Aucune étape de calcul lourde n'est nécessaire pour rendre les résultats largement accessibles. Les résultats peuvent même être publiés pendant le processus de vote sans compromettre l'anonymat (à condition d'avoir paré les attaques par corrélation temporelle).
C'est pourquoi nous avons intégré l'anonymat de l'électeur à notre mécanisme de preuve de recensement.
Le point de départ du mécanisme de recensement des votants est un arbre de Merkle de recensement. Il s'agit d'une structure de clés publiques hachées, dont chacune représente un électeur éligible du recensement. L'arbre de Merkle permet à tout électeur légitime de prouver qu'il détient une censusKey appartenant au recensement, sans connaître les clés des autres électeurs. L'électeur soumet ensuite cette preuve avec son bulletin. À cette enveloppe de vote est également joint un nullifier : une donnée dérivée de la censusKey de l'utilisateur et de l'electionID, qui correspond de manière unique à son vote.
Utilisée seule, cette preuve permettrait à l'organisateur d'un processus de corréler chaque enveloppe de vote, via son nullifier, avec la censusKey d'un électeur, et donc de désanonymiser le vote. Pour y remédier, Vocdoni utilise des zk-SNARKs afin de garantir l'anonymat du vote.
zk-SNARK signifie zero-knowledge Succinct Non-interactive ARgument of Knowledge, soit « argument de connaissance succinct et non interactif à divulgation nulle ». Un zk-SNARK permet à un utilisateur de prouver à un tiers qu'il possède une certaine information, sans révéler l'information elle-même.
Dans notre cas, les zk-SNARKs permettent aux électeurs de prouver leur appartenance au recensement sans révéler leur secretKey. Concrètement, cela passe par un zk-Circuit, un circuit logiciel conçu pour générer une preuve à divulgation nulle de connaissance (ZKP, Zero-Knowledge Proof).
Nous avons conçu un circuit qui permet aux utilisateurs de générer une ZKP de leur appartenance au recensement sans révéler leur secretKey. Le circuit reçoit des entrées privées et publiques ; les données susceptibles de révéler l'identité de l'électeur restent privées. Les entrées publiques sont transmises dans l'enveloppe de vote afin que les validateurs puissent les confronter à la preuve et s'assurer que l'utilisateur n'a pas voté deux fois.
Le circuit peut servir à tout processus dont le recensement est de taille comparable, et il ne doit être généré qu'une seule fois par taille. Plus précisément, un circuit généré peut être réutilisé pour tout arbre de Merkle de recensement de même hauteur. Comme nous utilisons un arbre binaire, il faut un circuit pour chaque valeur n telle que la taille cible du recensement tient dans 2^n (par ex. 128, 256, ..., 8192, 16384, etc.).
La génération du circuit repose sur une cérémonie de configuration de confiance (trusted setup). Il s'agit d'un processus de génération des clés de preuve et de vérification du circuit ; on parle de « confiance » car, si une seule partie contrôlait l'intégralité de la génération de ces clés, elle pourrait produire de fausses preuves. Une « cérémonie » décentralisée est donc nécessaire pour garantir la fiabilité du circuit. Lors d'une telle cérémonie, plusieurs parties aux intérêts divergents, situées en des lieux différents, effectuent chacune une étape de la génération des clés. Il suffit qu'une seule d'entre elles reste intègre pour qu'il soit impossible de générer une fausse preuve.
La franchise proof est générée en exécutant le circuit zk-SNARK.
index, secretKey, census Merkle-proofcensus Merkle-root, nullifier, election ID, votefranchise proof
Sans révéler la secretKey ni la preuve de Merkle du recensement, ce circuit est en mesure de démontrer que :
secretKey correspondant à une certaine zkCensusKey.zkCensusKey de l'électeur figure dans l'arbre de Merkle du recensement.nullifier fourni par l'électeur correspond de manière unique à sa secretKey et à l'election ID d'un processus de vote donné.Bien que le calcul soit gourmand en processeur et en mémoire, les ZKP peuvent être générées depuis le client de l'utilisateur, sur du matériel modeste. Dans le protocole Vocdoni, la preuve est validée par les nœuds de la Vochain, les mineurs et tout tiers qui surveille le processus.
Le circuit est réduit et optimisé à son strict minimum afin de rester accessible à tout type de matériel client. C'est la raison pour laquelle nous n'utilisons pas de vérification de signature, mais une approche fondée sur une secretKey.
L'arbre de Merkle utilisé pour construire le recensement anonyme doit être une implémentation compatible avec les zk-SNARKs. Comme nous utilisons actuellement le compilateur Circom pour les circuits zk-SNARK, il nous faut un arbre compatible avec l'implémentation d'arbre de Merkle de circomlib. Une spécification de cet arbre de Merkle est disponible ici.
La Vochain utilise arbo, une implémentation d'arbre de Merkle en Go compatible avec la conception Circom. L'arbre de Merkle emploie le hachage Poseidon, une fonction de hachage adaptée aux SNARKs qui peut ensuite être prouvée dans un circuit sans exiger trop de contraintes. Le diagramme suivant représente la structure des données des feuilles de l'arbre de Merkle utilisé dans le schéma de la zk-census-proof.
La valeur index est déterminée par le constructeur de l'arbre de recensement, qui maintient une valeur index pour chaque arbre de recensement. Cette valeur s'incrémente à l'ajout de chaque nouvelle feuille. Les feuilles sont structurées ainsi pour exploiter les arbres de Merkle plus efficacement : davantage de clés d'utilisateurs tiennent dans un arbre plus petit, ce qui réduit la taille du zk-Circuit. En effet, la value de la key d'une feuille détermine la position de cette feuille dans l'arbre.
Si la clé d'une feuille était déterminée par la zkCensusKey plutôt que par un index incrémental, chaque nouvelle feuille présenterait un risque de collision significatif avant que toutes les positions de feuilles disponibles ne soient occupées pour une hauteur donnée. Les arbres seraient donc moins équilibrés et exigeraient des circuits plus grands pour une même taille de recensement, en raison d'une utilisation inefficace de l'espace de l'arbre. Avec l'approche par index incrémental, en revanche, toutes les positions de feuilles peuvent être remplies sans la moindre collision. On obtient ainsi des circuits bien plus petits pour le même nombre d'utilisateurs.
{
"censusRoot": "51642541620950251760298704744678482162425252475654827255045491135352807540162",
"censusSiblings": ["0","0","0","0"],
"index": "30",
"secretKey": "6190793965647866647574058687473278714480561351424348391693421151024369116465",
"voteValue": ["100964581237483263846637432502620436451", "278307331411790712608582894981321409946"],
"electionId": "10",
"nullifier": "1938187656076799017313903315498318464349291455761501098436114043715056719301",
}
Origine de chaque paramètre zk-Input :
Tous les paramètres sont des string ou des []string qui représentent des bigInt ou des []bigInt.
censusRoot : calculé par l'autorité de recensement à partir de l'arbre de recensement.censusSiblings : calculé par l'autorité de recensement ; il s'agit de la preuve de MerklecensusSiblings dépend du zk-Circuit :nLevels du circuit est fixe, si bien que siblings.length doit l'être aussi.siblings.length dépend du zk-Circuit utilisé, plus précisément de son paramètre nLevelswhile (siblings.length < this.levels) siblings.push(BigInt(0));index : déterminé par la Vochain lors de l'ajout de la zkCensusKey de l'utilisateur dans l'arbre de recensementsecretKey : générée par l'utilisateurvoteValue : valeur hachée du vote de l'utilisateur, composée de deux grands entiers.sha256(vote_bytes). La sortie du hachage sha256 étant légèrement plus grande que le corps utilisé dans les SNARKs, nous découpons cette sortie (32 octets) en 2 tableaux de 16 octets, que nous interprétons comme des entiers (en petit-boutiste) avant de les utiliser comme entrées du circuit.sha256 est utilisé car, si nécessaire à l'avenir, il peut être vérifié à l'intérieur du circuit. Cet usage présente deux caractéristiques à garder à l'esprit : sha256 coûte deux fois plus cher que keccak256 en gaz sur l'EVM, mais il est implémenté en circom et peut donc être contrôlé dans un circuit ; vérifier sha256 à l'intérieur d'un circuit circom reste coûteux en nombre de contraintes (dans la version actuelle de cette spécification, ce contrôle n'est pas effectué dans le circuit).h := sha256.Sum256(voteBytes) // voteBytes can be the votes array converted to bytes, or the encrypted votes
b1 := new(big.Int).SetBytes(swapEndianness(h[:16])) // swap endianness, as golang big int package works in big-endian, and we use little-endian
b2 := new(big.Int).SetBytes(swapEndianness(h[16:]))
Et l'entrée JSON voteValue pour le circuit serait : "voteValue": [b1, b2]
electionID : l'identifiant de l'élection à laquelle l'utilisateur participenullifier : calculé par l'utilisateur nullifier = poseidon.Hash(sk, electionID)Pour répondre à la question « comment cette technologie peut-elle servir au vote des DAO sur Ethereum ? », un peu de contexte s'impose :
Voici comment Vocdoni peut aujourd'hui permettre le vote anonyme au sein des DAO :
secretKey temporaire et envoient une transaction à la blockchain Vocdoni prouvant qu'ils sont des électeurs éligibles (au moyen de la preuve de stockage). Cette transaction inclut la secretKey hachée, qui est ajoutée à un rolling Census calculé en interne par la logique de la blockchain Vocdoni. Cette étape s'appelle le pré-enregistrement de clé.secretKey
Vocdoni a développé un nouveau protocole DKG : non interactif par conception, opérationnellement asynchrone en pratique et construit à partir de primitives cryptographiques standard.
Jordi Pinyana
7 min de lecture
Ces dernières années, Vocdoni a fait fonctionner le vote sur Vochain, notre blockchain L1 conçue spécifiquement pour le vote. Comme toute blockchain, elle nous offrait un atout puissant :…
Pau Escrich
5 min de lecture
Nous avons levé avec succès 1 million de dollars en pré-amorçage auprès d'investisseurs providentiels pour développer DAVINCI. DAVINCI dépasse les limites des systèmes de vote existants en offrant, pour la gouvernance numérique, une solution résistante à la censure et à l'achat de votes, sans frais de gaz, évolutive et anonyme.
Pau Escrich
6 min de lecture