Descobreix les especificacions tècniques del vot anònim de Vocdoni i com vam arribar a aquest disseny.
Ferran
· 16 min de lectura
Abans d'entrar en les especificacions tècniques, val la pena explicar com definim el vot anònim i per què vam arribar a aquest disseny. A l'article d'anunci del producte presentem dos tipus d'anonimat: l'ofuscació de la papereta i l'anonimat del votant.
L'ofuscació de la papereta és l'anonimat que s'obté amagant el contingut de cada vot, mentre que l'anonimat del votant trenca el vincle entre cada votant i el seu vot, sense amagar els vots en si. La nostra implementació del vot anònim fa servir l'anonimat del votant. Per què?
En primer lloc, l'ofuscació de la papereta comporta contrapartides importants. Perquè un procés de votació sigui verificable d'extrem a extrem, els votants han de poder seguir i examinar el contingut de les paperetes que han emès. Si garantim l'anonimat ofuscant les paperetes, perdem la verificabilitat: és impossible verificar que el teu vot s'ha comptat i auditar la integritat de la votació si el contingut de cada vot està amagat.
Un altre inconvenient de l'ofuscació de la papereta és que és difícil d'implementar en un sistema de votació digital. Una de les tècniques d'ofuscació és el xifratge homomòrfic, que s'ha proposat per aportar anonimat criptogràfic als sistemes de votació tradicionals. El xifratge homomòrfic permet fer càlculs sobre valors xifrats, de manera que es pot calcular el recompte de vots sense examinar el contingut de cap papereta. Tot i ser sòlid en teoria, el xifratge homomòrfic té molts inconvenients que el fan poc desitjable com a base d'una tecnologia de votació.
El més destacable és que aquest mètode només permet càlculs bàsics sobre les paperetes xifrades, cosa que fa més difícil d'implementar esquemes com el vot quadràtic o el preferencial. A més, tot i que el càlcul dels resultats està garantit amb el xifratge homomòrfic, la verificació d'extrem a extrem de la papereta d'un votant no ho està. Aquest esquema no ofereix cap prova criptogràfica que garanteixi que la papereta d'un votant s'ha inclòs i representat correctament al conjunt de resultats. També estimem que la validació de la prova homomòrfica d'un procés de votació exigiria recursos computacionals significatius, que a més creixen amb la mida del procés. Això podria anul·lar els avantatges d'un sistema universalment verificable, perquè la verificació només es podria fer en màquines potents i cares, en un termini prohibitivament llarg.
L'anonimat del votant té diversos avantatges respecte del xifratge homomòrfic. Primer, permet un grau molt més alt de verificabilitat d'extrem a extrem. Tot i que el vincle entre un votant i la seva papereta ha de ser opac per a qualsevol observador extern, els votants sí que poden identificar la seva papereta. Com que les paperetes són visibles, qualsevol usuari pot seguir el seu vot des del moment que l'emet fins a la seva inclusió en els resultats. A més, els tercers poden comprovar que cada papereta pertany a un votant vàlid i que el seu contingut s'ha comptat correctament.
L'anonimat del votant també tendeix a permetre dissenys molt més eficients computacionalment. Els sistemes amb anonimat del votant apliquen l'ofuscació un sol cop, sobre la prova de la papereta de cada votant, en lloc de fer-ho sobre tot el conjunt de resultats cada vegada que s'emet una nova papereta. No cal cap pas computacional important per fer els resultats àmpliament accessibles. Fins i tot es poden publicar resultats durant el procés de votació sense comprometre l'anonimat (sempre que s'hagin mitigat els atacs de correlació temporal).
Per tot això, hem decidit incorporar l'anonimat del votant al nostre mecanisme de prova de cens.
El punt de partida del mecanisme de cens de votants és un arbre de Merkle de cens. Es tracta d'una estructura de claus públiques amb hash, cadascuna de les quals representa un votant elegible del cens. L'ús d'un arbre de Merkle permet que qualsevol votant vàlid demostri que té una censusKey que pertany al cens, sense conèixer les claus de cap altre votant. El votant envia aquesta prova com a part de la seva papereta. A aquest sobre de vot també s'hi adjunta un nullifier: una dada derivada de la censusKey de l'usuari i de l'electionID que correspon de manera única al seu vot.
Si es fes servir només aquesta prova, l'organitzador d'un procés podria correlacionar cada sobre de vot, a través del seu nullifier, amb la censusKey d'un votant, i desanonimitzar la votació. Per evitar-ho, Vocdoni fa servir zk-SNARKs per garantir l'anonimat del vot.
zk-SNARK són les sigles de zero-knowledge Succinct Non-interactive ARgument of Knowledge. Un zk-SNARK permet que un usuari demostri a un tercer que posseeix una determinada informació, sense revelar la informació en si.
En el nostre cas, els zk-SNARKs permeten als votants demostrar que pertanyen al cens sense revelar la seva secretKey. En concret, això es fa amb un zk-Circuit, un circuit de programari dissenyat per generar una prova de coneixement zero (ZKP).
Hem dissenyat un circuit que permet als usuaris generar una ZKP de la seva pertinença al cens sense revelar la seva secretKey. El circuit rep entrades privades i públiques, i les dades que podrien revelar la identitat del votant es mantenen privades. Les entrades públiques s'envien dins del sobre de vot perquè els validadors les puguin contrastar amb la prova i assegurar-se que l'usuari no ha votat dues vegades.
El circuit es pot fer servir per a qualsevol procés amb un cens de mida similar, i només cal generar-lo un cop per a cada mida. Més concretament, un circuit es pot generar i reutilitzar per a qualsevol arbre de Merkle de cens amb la mateixa alçada d'arbre. Com que fem servir un arbre binari, això vol dir que cal un circuit per a cada valor n tal que la mida del cens objectiu estigui dins del rang de 2^n (p. ex. 128, 256, ..., 8192, 16384, etc.).
La generació del circuit depèn d'una cerimònia de configuració de confiança (trusted setup). És el procés que genera les claus de provador i de verificador del circuit, i es diu «de confiança» perquè, si una sola part controlés tota la generació d'aquestes claus, podria generar proves falses. Per això cal una «cerimònia» descentralitzada que asseguri la fiabilitat del circuit. En una cerimònia així, diverses parts amb interessos contraposats i en ubicacions diferents fan cadascuna un pas de la generació de claus. Si només una d'aquestes parts manté la integritat, serà impossible generar una prova falsa.
La franchise proof es genera executant el circuit zk-SNARK.
index, secretKey, census Merkle-proofcensus Merkle-root, nullifier, election ID, votefranchise proof
Abans d'entrar en les especificacions tècniques, val la pena explicar com definim el vot anònim i per què vam arribar a aquest disseny. A l'article d'anunci del producte presentem dos tipus d'anonimat: l'ofuscació de la papereta i l'anonimat del votant.
L'ofuscació de la papereta és l'anonimat que s'obté amagant el contingut de cada vot, mentre que l'anonimat del votant trenca el vincle entre cada votant i el seu vot, sense amagar els vots en si. La nostra implementació del vot anònim fa servir l'anonimat del votant. Per què?
En primer lloc, l'ofuscació de la papereta comporta contrapartides importants. Perquè un procés de votació sigui verificable d'extrem a extrem, els votants han de poder seguir i examinar el contingut de les paperetes que han emès. Si garantim l'anonimat ofuscant les paperetes, perdem la verificabilitat: és impossible verificar que el teu vot s'ha comptat i auditar la integritat de la votació si el contingut de cada vot està amagat.
Un altre inconvenient de l'ofuscació de la papereta és que és difícil d'implementar en un sistema de votació digital. Una de les tècniques d'ofuscació és el xifratge homomòrfic, que s'ha proposat per aportar anonimat criptogràfic als sistemes de votació tradicionals. El xifratge homomòrfic permet fer càlculs sobre valors xifrats, de manera que es pot calcular el recompte de vots sense examinar el contingut de cap papereta. Tot i ser sòlid en teoria, el xifratge homomòrfic té molts inconvenients que el fan poc desitjable com a base d'una tecnologia de votació.
El més destacable és que aquest mètode només permet càlculs bàsics sobre les paperetes xifrades, cosa que fa més difícil d'implementar esquemes com el vot quadràtic o el preferencial. A més, tot i que el càlcul dels resultats està garantit amb el xifratge homomòrfic, la verificació d'extrem a extrem de la papereta d'un votant no ho està. Aquest esquema no ofereix cap prova criptogràfica que garanteixi que la papereta d'un votant s'ha inclòs i representat correctament al conjunt de resultats. També estimem que la validació de la prova homomòrfica d'un procés de votació exigiria recursos computacionals significatius, que a més creixen amb la mida del procés. Això podria anul·lar els avantatges d'un sistema universalment verificable, perquè la verificació només es podria fer en màquines potents i cares, en un termini prohibitivament llarg.
L'anonimat del votant té diversos avantatges respecte del xifratge homomòrfic. Primer, permet un grau molt més alt de verificabilitat d'extrem a extrem. Tot i que el vincle entre un votant i la seva papereta ha de ser opac per a qualsevol observador extern, els votants sí que poden identificar la seva papereta. Com que les paperetes són visibles, qualsevol usuari pot seguir el seu vot des del moment que l'emet fins a la seva inclusió en els resultats. A més, els tercers poden comprovar que cada papereta pertany a un votant vàlid i que el seu contingut s'ha comptat correctament.
L'anonimat del votant també tendeix a permetre dissenys molt més eficients computacionalment. Els sistemes amb anonimat del votant apliquen l'ofuscació un sol cop, sobre la prova de la papereta de cada votant, en lloc de fer-ho sobre tot el conjunt de resultats cada vegada que s'emet una nova papereta. No cal cap pas computacional important per fer els resultats àmpliament accessibles. Fins i tot es poden publicar resultats durant el procés de votació sense comprometre l'anonimat (sempre que s'hagin mitigat els atacs de correlació temporal).
Per tot això, hem decidit incorporar l'anonimat del votant al nostre mecanisme de prova de cens.
El punt de partida del mecanisme de cens de votants és un arbre de Merkle de cens. Es tracta d'una estructura de claus públiques amb hash, cadascuna de les quals representa un votant elegible del cens. L'ús d'un arbre de Merkle permet que qualsevol votant vàlid demostri que té una censusKey que pertany al cens, sense conèixer les claus de cap altre votant. El votant envia aquesta prova com a part de la seva papereta. A aquest sobre de vot també s'hi adjunta un nullifier: una dada derivada de la censusKey de l'usuari i de l'electionID que correspon de manera única al seu vot.
Si es fes servir només aquesta prova, l'organitzador d'un procés podria correlacionar cada sobre de vot, a través del seu nullifier, amb la censusKey d'un votant, i desanonimitzar la votació. Per evitar-ho, Vocdoni fa servir zk-SNARKs per garantir l'anonimat del vot.
zk-SNARK són les sigles de zero-knowledge Succinct Non-interactive ARgument of Knowledge. Un zk-SNARK permet que un usuari demostri a un tercer que posseeix una determinada informació, sense revelar la informació en si.
En el nostre cas, els zk-SNARKs permeten als votants demostrar que pertanyen al cens sense revelar la seva secretKey. En concret, això es fa amb un zk-Circuit, un circuit de programari dissenyat per generar una prova de coneixement zero (ZKP).
Hem dissenyat un circuit que permet als usuaris generar una ZKP de la seva pertinença al cens sense revelar la seva secretKey. El circuit rep entrades privades i públiques, i les dades que podrien revelar la identitat del votant es mantenen privades. Les entrades públiques s'envien dins del sobre de vot perquè els validadors les puguin contrastar amb la prova i assegurar-se que l'usuari no ha votat dues vegades.
El circuit es pot fer servir per a qualsevol procés amb un cens de mida similar, i només cal generar-lo un cop per a cada mida. Més concretament, un circuit es pot generar i reutilitzar per a qualsevol arbre de Merkle de cens amb la mateixa alçada d'arbre. Com que fem servir un arbre binari, això vol dir que cal un circuit per a cada valor n tal que la mida del cens objectiu estigui dins del rang de 2^n (p. ex. 128, 256, ..., 8192, 16384, etc.).
La generació del circuit depèn d'una cerimònia de configuració de confiança (trusted setup). És el procés que genera les claus de provador i de verificador del circuit, i es diu «de confiança» perquè, si una sola part controlés tota la generació d'aquestes claus, podria generar proves falses. Per això cal una «cerimònia» descentralitzada que asseguri la fiabilitat del circuit. En una cerimònia així, diverses parts amb interessos contraposats i en ubicacions diferents fan cadascuna un pas de la generació de claus. Si només una d'aquestes parts manté la integritat, serà impossible generar una prova falsa.
La franchise proof es genera executant el circuit zk-SNARK.
index, secretKey, census Merkle-proofcensus Merkle-root, nullifier, election ID, votefranchise proof
Sense revelar la secretKey ni la prova de Merkle del cens, aquest circuit és capaç de demostrar que:
secretKey corresponent a una determinada zkCensusKey.zkCensusKey del votant està inclosa a l'arbre de Merkle del cens.nullifier que aporta el votant correspon de manera única a la seva secretKey i a l'election ID d'un procés de votació concret.Tot i que el càlcul és intensiu en CPU i memòria, les ZKP es poden generar des del client de l'usuari, en maquinari modest. Al protocol de Vocdoni, la prova la validen els nodes de la Vochain, els miners i qualsevol tercer que monitori el procés.
El circuit està minimitzat i optimitzat fins als seus requisits mínims per fer-lo accessible a qualsevol tipus de maquinari de client. Aquesta és la raó per la qual no fem servir verificació de signatura sinó un enfocament basat en secretKey.
L'arbre de Merkle que es fa servir per construir el cens anònim ha de ser una implementació compatible amb zk-SNARKs. Com que actualment fem servir el compilador Circom per als circuits zk-SNARK, necessitem un arbre compatible amb la implementació d'arbre de Merkle de circomlib. Aquí pots trobar una especificació d'aquest arbre de Merkle.
La Vochain fa servir l'arbre de Merkle arbo, una implementació en Go compatible amb el disseny de Circom. L'arbre de Merkle fa servir el hash Poseidon, una funció de hash «amigable amb SNARKs» que després es pot provar dins d'un circuit sense requerir massa restriccions. El diagrama següent és una representació visual de l'estructura de dades de les fulles de l'arbre de Merkle que es fa servir en l'esquema de la zk-census-proof.
El valor index el determina el constructor de l'arbre del cens, que té un valor index per a cada arbre de cens. Aquest valor s'incrementa amb l'addició de cada nova fulla. Les fulles s'estructuren així per fer servir els arbres de Merkle de manera més eficient, fent cabre les claus de més usuaris dins d'un arbre més petit i reduint així la mida del zk-Circuit. Això és perquè el value de la key de qualsevol fulla determina la posició d'aquesta fulla a l'arbre.
Si la clau de la fulla la determinés la zkCensusKey, en lloc d'un index incremental, cada nova fulla tindria una probabilitat significativa de col·lisió abans d'omplir totes les posicions de fulla disponibles per a una alçada donada. Els arbres serien, per tant, menys equilibrats i requeririen circuits més grans per a la mateixa mida de cens, per un ús ineficient de l'espai de l'arbre. Amb l'enfocament de l'índex incremental, en canvi, es poden omplir totes les posicions de fulla sense ni una sola col·lisió. Això produeix circuits molt més petits per al mateix nombre d'usuaris.
{
"censusRoot": "51642541620950251760298704744678482162425252475654827255045491135352807540162",
"censusSiblings": ["0","0","0","0"],
"index": "30",
"secretKey": "6190793965647866647574058687473278714480561351424348391693421151024369116465",
"voteValue": ["100964581237483263846637432502620436451", "278307331411790712608582894981321409946"],
"electionId": "10",
"nullifier": "1938187656076799017313903315498318464349291455761501098436114043715056719301",
}
Origen de cada paràmetre de zk-Input:
Tots els paràmetres són string o []string que representen bigInt o []bigInt.
censusRoot: el calcula l'autoritat del cens a partir de l'arbre del cens.censusSiblings: els calcula l'autoritat del cens; és la prova de MerklecensusSiblings dependrà del zk-Circuit:nLevels del circuit és fix, així que siblings.length també ha de ser fix.siblings.length dependrà del zk-Circuit que es faci servir, concretament del paràmetre nLevels del circuitwhile (siblings.length < this.levels) siblings.push(BigInt(0));index: el determina la Vochain en afegir la zkCensusKey de l'usuari a l'arbre del censsecretKey: la genera l'usuarivoteValue: valor amb hash del vot de l'usuari, format per dos enters grans.sha256(vote_bytes). La sortida del hash sha256 és lleugerament més gran que el camp que es fa servir en SNARKS, així que dividim la sortida del hash (32 bytes) en 2 arrays de 16 bytes, els prenem com a enters (en little-endian) i els fem servir com a entrades del circuit.sha256 perquè, si en el futur calgués, es pot verificar dins del circuit. Aquest ús té dues característiques a tenir en compte: sha256 és el doble de car que keccak256 en termes de gas a l'EVM, però està implementat en circom, de manera que es pot comprovar dins d'un circuit; comprovar el sha256 dins d'un circuit de circom és car en termes de nombre de restriccions (en la versió actual d'aquesta especificació, això no es comprova dins del 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:]))
I l'entrada json del voteValue per al circuit seria: "voteValue": [b1, b2]
electionID: l'ID de l'elecció en què participa l'usuarinullifier: el calcula l'usuari: nullifier = poseidon.Hash(sk, electionID)Per respondre la pregunta «com es pot fer servir aquesta tecnologia per a les votacions de DAOs a Ethereum», cal afegir una mica de context:
La manera com Vocdoni pot suportar actualment el vot anònim en DAOs és seguint aquests passos:
secretKey temporal i envien una transacció a la blockchain de Vocdoni per demostrar que són votants elegibles (fent servir la prova d'emmagatzematge). Aquesta transacció inclou la secretKey amb hash, que s'afegeix a un rolling Census que la lògica de la blockchain de Vocdoni calcula internament. Aquest pas s'anomena preregistre de claus.secretKey
Vocdoni ha desenvolupat un nou protocol DKG que és no interactiu per disseny, operativament asíncron a la pràctica i construït a partir de primitives criptogràfiques estàndard.
Jordi Pinyana
6 min de lectura
Durant els darrers anys, Vocdoni ha executat les votacions a Vochain, la nostra blockchain L1 dissenyada específicament per votar. Com qualsevol blockchain, ens donava una cosa potent:…
Pau Escrich
4 min de lectura
Hem tancat amb èxit una ronda pre-seed d'1 milió de dòlars amb inversors àngel per desenvolupar DAVINCI. DAVINCI supera les limitacions dels sistemes de votació existents i ofereix una solució resistent a la censura, gasless, anti-suborn, escalable i anònima per a la governança digital.
Pau Escrich
6 min de lectura