a16z: Como o Cicada usa quebra-cabeças de bloqueio de tempo e provas de conhecimento zero para permitir a votação na cadeia

Cicada tem novas propriedades de privacidade, minimiza suposições de confiança e é eficiente o suficiente para ser usado na rede principal Ethereum.

**Escrito por:**Michael Zhu

** Compilado por: Lynn, MarsBit **

Todos os sistemas de votação que funcionam de maneira significativa dependem da integridade e da transparência. Em face disso, isso torna o blockchain uma plataforma ideal para construir esses sistemas – de fato, muitas organizações descentralizadas adotaram a votação sem permissão como um meio de expressar a intenção coletiva, muitas vezes empunhando uma vasta riqueza ou ajustando os principais parâmetros de protocolo no caso de. Mas a votação on-chain também tem desvantagens. A privacidade ainda é inexplorada e subdesenvolvida, o que não é bom para os sistemas de votação Web3 – na maioria dos protocolos de votação on-chain atualmente em uso, as cédulas e os resultados das votações são completamente públicos. Sem privacidade, os resultados da votação podem ser facilmente manipulados e os incentivos eleitorais desalinhados, levando potencialmente a resultados antidemocráticos.

É por isso que estamos lançando o Cicada: uma nova biblioteca Solidity de código aberto que utiliza quebra-cabeças de bloqueio de tempo e provas de conhecimento zero para permitir a votação privada na cadeia. Comparado aos sistemas existentes, o Cicada possui novas propriedades de privacidade, minimiza as suposições de confiança e é eficiente o suficiente para ser usado na rede principal Ethereum.

Nesta postagem, examinamos o estado da privacidade do voto e fornecemos uma descrição de alto nível de como o Cicada funciona (provas formais serão disponibilizadas). Também encorajamos os desenvolvedores a verificar o repositório do GitHub - o Cicada pode ser ajustado e estendido de várias maneiras para oferecer suporte a diferentes esquemas e recursos de votação, e esperamos trabalhar com a comunidade para explorar essas possibilidades.

Breve Pesquisa de Votos Privados

Em qualquer sistema de votação (on-chain ou não), há muitos níveis diferentes de privacidade a serem considerados. A divulgação de cédulas individuais, contagens contínuas e identidades eleitorais afetam a motivação do eleitor de maneiras diferentes. Quais propriedades de privacidade são necessárias depende do contexto da votação. Alguns que aparecem com frequência na literatura de criptografia e ciências sociais:

• Privacidade da cédula: cédulas secretas, também conhecidas como "cédulas australianas", foram desenvolvidas para sistemas de votação do mundo real como uma forma de preservar as preferências individuais do eleitor e mitigar o suborno e a coerção (definidas na cadeia, podemos exigir uma propriedade mais forte do que a cédula privacidade - consulte "ausência de recebimento" abaixo). A privacidade do voto também pode atenuar o viés de desejo social - alguém tem menos pressão para votar com base no que os outros pensam de suas escolhas.
• Privacidade das contagens em andamento: muitos sistemas de votação ocultam as contagens em andamento ou quantos votos já foram dados para cada opção, enquanto os eleitores ainda estão votando, para evitar afetar a participação e os incentivos dos eleitores. Já vimos isso acontecer no mundo real; por exemplo, os senadores dos EUA que votam mais tarde têm maior probabilidade de se alinhar com seu partido do que os senadores que votam mais cedo. E on-chain: na votação com peso simbólico, as baleias podem enganar seus oponentes com uma falsa sensação de segurança, mantendo-os à frente (alguns podem ser preguiçosos demais para votar, presumindo que vencerão de qualquer maneira) e, em seguida, lançar seu próprio voto em o último minuto Venha e decida o resultado.
• Anonimato do eleitor: em muitos sistemas de votação do mundo real, seu voto não é público, mas o fato de você ter votado é geralmente público. Isso é importante para evitar fraudes eleitorais, porque a publicação dos registros eleitorais permite que as pessoas verifiquem se outras pessoas votaram em seu nome. On-chain, no entanto, podemos evitar a fraude do eleitor preservando o anonimato usando primitivas criptográficas - por exemplo, com o Semaphore, você pode provar sem saber que é um eleitor válido que ainda não votou.
• Sem capacidade de recebimento: os eleitores individuais fornecem um "recibo" de sua cédula para provar como votaram para um terceiro, o que poderia resultar na venda de ingressos. Uma propriedade intimamente relacionada, mas mais forte, é a resistência à coerção, que impede alguém de coagir os eleitores a votar de uma determinada maneira. Essas propriedades são particularmente atraentes em um ambiente descentralizado, onde os direitos de voto podem se tornar líquidos por meio de mercados de contratos inteligentes. Infelizmente, eles também são difíceis de implementar - na verdade, Juels e outros apontam que é impossível em um ambiente sem permissão sem hardware confiável.

O Cicada está focado na privacidade da contagem durante o voo, mas (como discutiremos mais adiante) pode ser combinado com provas de participação em grupos de conhecimento zero para obter o anonimato do eleitor e a privacidade da cédula.

Apresentando a cigarra: privacidade na contagem de votos do problema de timelock homomórfico

Para obter a privacidade da contagem de votos em andamento, o Cicada utiliza primitivas criptográficas que (até onde sabemos) nunca foram usadas na cadeia antes.

Primeiro, o quebra-cabeça do bloqueio do tempo (Rivest, Shamir, Wagner, 1996) é um quebra-cabeça criptografado que encapsula um segredo que só pode ser revelado depois de decorrido um período de tempo predeterminado - mais especificamente, o quebra-cabeça pode ser repetido por Do some non- cálculos paralelos para descriptografar. Os quebra-cabeças bloqueados por tempo são úteis no contexto da votação para obter privacidade na execução das estatísticas: os usuários podem enviar seus votos como quebra-cabeças bloqueados por tempo, para que sejam mantidos em segredo durante o processo de votação, mas possam ser revelados após a votação. Ao contrário da maioria das outras estruturas de votação privadas, isso permite que a privacidade estatística opere sem depender de agências estatísticas (como trabalhadores eleitorais contando papel ou cédulas digitais), criptografia de limite (várias partes confiáveis devem cooperar para descriptografar uma mensagem) ou quaisquer outras partes confiáveis: Qualquer um pode resolver um quebra-cabeça de timelock para garantir que o resultado seja revelado após a votação.

Em segundo lugar, um quebra-cabeça de timelock isomórfico (Malavolta Thyagarajan, 2019) tem a propriedade adicional de que alguns cálculos em valores criptografados são possíveis com o conhecimento da chave secreta, descriptografia do quebra-cabeça ou uso de um backdoor. Em particular, um quebra-cabeça timelock linearmente homomórfico nos permite combinar quebra-cabeças para produzir um novo quebra-cabeça que encapsula a soma dos valores secretos do quebra-cabeça original.

Como os autores do artigo apontam, os quebra-cabeças de timelock linearmente homomórficos são um primitivo particularmente adequado para a votação privada: os votos podem ser codificados como quebra-cabeças e podem ser combinados homomorficamente para obter um quebra-cabeças de contagem final codificado. Isso significa que apenas um cálculo é necessário para revelar o resultado final, em vez de resolver um quebra-cabeça exclusivo para cada votação.

Uma nova estrutura: eficiência e compensações

Há várias questões a serem consideradas para que um esquema de votação seja prático na cadeia. Primeiro, um invasor pode tentar manipular votos lançando uma cédula codificada incorretamente. Por exemplo, podemos querer que o quebra-cabeça de timelock para cada cédula seja codificado como um valor booleano: "1" para a proposta que está sendo votada e "0" para não. Um defensor fervoroso da proposta pode tentar codificar algo como "100" para expandir seu poder de voto efetivo.

Podemos evitar esse ataque fazendo com que o eleitor apresente uma prova de conhecimento zero da validade do voto junto com o próprio voto. No entanto, as provas de conhecimento zero são computacionalmente caras - para manter o custo da participação do eleitor o mais baixo possível, as provas devem ser (1) computáveis com eficiência no lado do cliente e (2) verificáveis com eficiência na cadeia.

Para tornar as provas o mais eficientes possível, usamos um protocolo sigma personalizado — provas de conhecimento zero projetadas para relações algébricas específicas, em vez de um sistema de prova geral. Isso torna o tempo do provador extremamente rápido: gerar uma prova de validade da cédula em Python leva 14 ms em um laptop comum.

Embora o validador do protocolo sigma seja conceitualmente simples, ele requer um número razoavelmente grande de exponenciações modulares. O esquema homomórfico linear de Malavolta e Thyagarajan usa criptografia de Paillier, portanto, essas exponenciações executarão o módulo N ^ 2 para algum módulo RSA N. Para tamanhos razoáveis de N, a exponenciação é muito cara (milhões de gás) na maioria das cadeias EVM. Para reduzir custos, Cicada usa ElGamal Exponencial - ElGamal Exponencial ainda fornece homomorfismos aditivos, mas trabalha em módulos menores (N em vez de N^2).

Uma desvantagem de usar o ElGamal é que a etapa final de descriptografar a contagem requer força bruta do log discreto (observe que isso é feito fora da cadeia e efetivamente verificado na cadeia). Portanto, só funciona se o número final esperado de votos for bem pequeno (digamos, menos de 2^32, ou cerca de 4,3 milhões de votos). No esquema original baseado em Paillier, as contagens podem ser descriptografadas com eficiência, independentemente de seu tamanho.

Escolher o módulo RSA N também envolve trade-offs. Nossa implementação usa um módulo de 1024 bits para eficiência de gás. Embora esteja bem acima do maior módulo RSA já fatorado publicamente (829 bits), está abaixo do tamanho comumente recomendado de 2.048 bits para criptografia ou assinatura RSA. No entanto, nosso aplicativo não requer segurança de longo prazo: uma vez encerrada a eleição, não há risco se N for considerado no futuro. É razoável usar um módulo relativamente pequeno, assumindo que as contagens e os votos são tornados públicos depois que o timelock expira. (Isso também pode ser facilmente atualizado no futuro se o algoritmo de decomposição melhorar.)

Anonimato e elegibilidade do eleitor

Como mencionado acima, o Cicada fornece privacidade de contagem de execução - uma propriedade de quebra-cabeça com bloqueio de tempo que mantém a contagem de votos privada durante a votação. No entanto, cada cédula individual também é um quebra-cabeça de timelock, criptografado sob os mesmos parâmetros públicos. Isso significa que, assim como a contagem pode ser descriptografada (realizando os cálculos necessários), cada voto também pode. Em outras palavras, o Cicada garante a privacidade da cédula apenas durante a votação - se observadores curiosos desejarem descriptografar a cédula de um determinado eleitor, eles podem fazê-lo. Descriptografar qualquer cédula individual é tão caro quanto descriptografar a contagem final, portanto, ingenuamente, é preciso O(n) trabalho para descriptografar totalmente uma cédula com n eleitores. Mas todos esses votos podem ser descriptografados em paralelo (supondo que haja máquinas suficientes), levando o mesmo tempo de relógio de parede que leva para descriptografar a contagem final.

Para alguns votos, isso pode não ser desejável. Embora estejamos satisfeitos com a execução temporária da privacidade da contagem de votos, podemos querer a privacidade da votação indefinidamente. Para conseguir isso, podemos combinar Cicada com um protocolo de elegibilidade de eleitor anônimo, instanciado com provas de participação em grupos de conhecimento zero. Dessa forma, mesmo que a cédula seja desclassificada, tudo o que ela revela é que alguém votou dessa forma - e já sabemos disso pela contagem.

Em nosso repositório, incluímos um exemplo de contrato que usa Semaphore para anonimização do eleitor. Observe, no entanto, que o próprio contrato Cicada não faz suposições sobre como a elegibilidade do eleitor é determinada ou aplicada. Em particular, você pode substituir Semaphore por, por exemplo, Semacaulk ou ZK Proof of State (conforme sugerido aqui e aqui).

Autoridade Estatística

Uma de nossas primeiras prioridades ao projetar o Cicada foi evitar a necessidade de uma agência estatística: muitas estruturas de votação privadas exigem uma agência estatística semiconfiável (ou comitê delegado, coordenado por meio de computação multipartidária segura) para receber e agregar votos. Em um contexto de blockchain, isso significa que esses esquemas não podem ser executados apenas por contratos inteligentes, exigindo alguma intervenção humana e confiança.

Na maioria das estruturas, as autoridades de contagem não são confiáveis quanto à integridade (não podem manipular a contagem dos votos), mas são confiáveis quanto à vivacidade - se estiverem offline, não podem calcular o resultado final, atrasando a votação indefinidamente. Em algumas estruturas, eles também são confiáveis para manter a privacidade – ou seja, eles sabem como cada indivíduo vota, mas espera-se que publiquem os resultados das votações sem revelar essa informação.

Embora as autoridades estatísticas sejam uma suposição razoável (e necessária) em muitos cenários do mundo real, elas não são ideais em um ambiente blockchain, onde nosso objetivo é minimizar a confiança e garantir a resistência à censura.

O Cicada explora uma das muitas direções no campo da privacidade do voto on-chain e complementa grande parte da pesquisa que está sendo feita por outros grupos. Como mencionado acima, o Cicada está intimamente relacionado a tecnologias de associação de grupos anônimos, como semáforos, prova de armazenamento ZK e invalidadores de limite de taxa. A cigarra também pode integrar o verificador de provas otimista proposto pela equipe do Nouns Vortex para reduzir a carga de gás dos eleitores.

Há também uma oportunidade de adaptar o Cicada para suportar diferentes esquemas de votação (por exemplo, votação ponderada por token, votação quadrática) - esquemas mais complexos podem ser muito caros computacionalmente para a rede principal Ethereum, mas podem ser práticos em L2. Com isso em mente, agradecemos suas contribuições, bifurcações e sugestões sobre onde levar o Cigarra a seguir.

*Agradecimentos: Cicada foi co-desenvolvido com Joseph Bonneau. Obrigado a Andrew Hall por informações básicas sobre o contexto histórico da privacidade do voto. Obrigado também a Robert Hackett por seu feedback sobre este artigo. Agradecimentos especiais a Stephanie Zinn pela edição. *