Vitalik Buterin: Como a tecnologia zk-SNARKs protege a privacidade?

zk-SNARKs são uma ferramenta criptográfica poderosa que se tornou uma parte cada vez mais essencial de aplicativos blockchain e não baseados em blockchain. A sua complexidade é evidente tanto na compreensão de como funcionam como na forma como podem ser utilizados de forma eficaz. Este artigo investiga como os zk-SNARKs se adaptam às aplicações atuais, fornece exemplos do que eles podem ou não alcançar e oferece diretrizes gerais sobre quando os zk-SNARKs são adequados para aplicações específicas. Será dada especial ênfase ao seu papel na garantia da privacidade.

O que são zk-SNARKs?

Imagine ter uma entrada pública x, uma entrada privada w e uma função (pública) f(x,w) → {True,False}, que valida as entradas. Com zk-SNARKs, pode-se provar que eles conhecem aw, de modo que para um dado f e x, f(x,w) = True, tudo sem revelar o que w realmente é. Além disso, os verificadores podem autenticar a prova muito mais rápido do que poderiam calcular f(x,w), mesmo que soubessem w.

Isso confere ao zk-SNARKs dois atributos: privacidade e escalabilidade. Conforme mencionado, nossos exemplos neste artigo focarão principalmente no aspecto da privacidade.

Prova de adesão

Suponha que você tenha uma carteira Ethereum e queira provar que essa carteira está registrada em um sistema de prova de humanidade, sem revelar quem realmente é o indivíduo registrado. Esta função pode ser descrita matematicamente como:

Entrada privada (w): Seu endereço A, sua chave privada de endereço k

Entrada pública (x): conjunto de endereços de todos os perfis de prova de humanidade verificados {H1…Hn}

Função de verificação f(x,w):

Interprete w como um par (A, σ) ex como uma lista de perfis válida {H1…Hn}

Verifique se A é um dos endereços em {H1…Hn}

Confirme privtoaddr(k) = A

Se ambas as verificações forem aprovadas, retorne True. Se algum deles falhar, retorne False.

O provador gera seu endereço A e a chave associada k, fornecendo w=(A,k) como entrada privada para f. Eles obtêm a entrada pública, que é o conjunto atual de perfis de prova de humanidade verificados {H1…Hn}, da cadeia. Eles então executam o algoritmo de prova zk-SNARK, que (assumindo que a entrada está correta) produz uma prova. Essa prova é enviada ao verificador, junto com a altura do bloco onde foi buscada a lista de perfis verificados.

O verificador também lê a cadeia, adquirindo a lista {H1…Hn} da altura especificada pelo provador, e verifica a prova. Se a verificação for bem-sucedida, o verificador acredita que o provador possui um perfil de prova de humanidade verificado.

Antes de me aprofundar em exemplos mais complexos, recomendo fortemente a compreensão completa do exemplo acima.

Tornando as provas de adesão mais eficientes

Uma desvantagem do sistema de prova acima mencionado é que o verificador precisa estar ciente de todo o conjunto de perfis {H1…Hn}, o que requer tempo O(n) para “introduzir” este conjunto no mecanismo zk-SNARK. Este problema pode ser resolvido usando a raiz Merkle na cadeia, que abrange todos os perfis, como entrada pública (potencialmente apenas a raiz estatal). Adicionamos outra entrada privada, uma prova Merkle M, confirmando que a conta A do provador está na parte pertinente da árvore.

Uma alternativa altamente recente e mais eficiente às provas Merkle para provas de adesão ZK é Caulk. No futuro, alguns desses casos de uso poderão fazer a transição para soluções semelhantes ao Caulk.

ZK-SNARKs e moedas

Projetos como Zcash e Tornado.cash nos permitem possuir moedas que protegem a privacidade. Agora, pode-se pensar que eles poderiam utilizar as mencionadas “provas humanas ZK”, mas não se trata de provar acesso a provas de perfis humanos; trata-se de provar acesso a moedas. Aqui reside um problema: temos de abordar simultaneamente a privacidade e a despesa dupla. Ou seja, não devemos gastar a mesma moeda duas vezes.

Veja como resolvemos: Qualquer pessoa que possua uma moeda possui um “s” secreto privado. Eles calculam uma “folha” L=hash(s,1) localmente, que é publicada na cadeia, tornando-se parte do estado, N=hash(s,2), que chamamos de anulador. O estado é armazenado em uma árvore Merkle.

Para gastar uma moeda, o remetente deve produzir um ZK-SNARK onde:

• As entradas públicas incluem um anulador N, a raiz Merkle atual ou recente R e uma nova folha L' (destinada ao destinatário que tem um segredo s' passado ao remetente como L'=hash(s',1)).

• As entradas privadas compreendem um segredo s, uma folha L e um ramo Merkle M.

A função de verificação verifica:

• M é um ramo Merkle válido, provando que L é uma folha da árvore com raiz em R, onde R é a raiz Merkle do estado atual.

• hash(s,1)=L e hash(s,2)=N.

A transação contém o anulador N e a nova folha L'. Na verdade, não provamos nada sobre L', mas ele é “misturado” na prova para evitar modificações por terceiros durante a transação. Para validar a transação, a cadeia verifica o ZK-SNARK e verifica se N foi utilizado em transações anteriores. Se for bem sucedido, N é adicionado ao conjunto de anuladores gastos, tornando-o inutilizável novamente. L' é adicionado à árvore Merkle.

Usando ZK-SNARKs, vinculamos dois valores: L (aparecendo na cadeia quando a moeda é cunhada) e N (aparecendo quando gasta), sem revelar qual L se conecta a qual N. A conexão entre L e N só é discernível quando você conheça os segredos que os geram. Cada moeda cunhada pode ser usada uma vez (já que há apenas um N válido para cada L), mas a moeda específica usada a qualquer momento permanece oculta.

Este é um primitivo crucial para entender. Muitos mecanismos que descrevemos abaixo são baseados nisso, embora com finalidades variadas.

Moedas com saldos arbitrários

O que foi dito acima pode ser facilmente estendido a moedas com saldos arbitrários. Mantemos o conceito de “moeda”, mas cada moeda carrega um saldo (privado). Uma maneira simples de conseguir isso é que cada moeda tenha armazenamento em cadeia, não apenas com a folha L, mas também com um saldo criptografado. Cada transação consumiria duas moedas e criaria duas novas, adicionando dois pares (folha, saldo criptografado) ao estado. O ZK-SNARK também verifica se a soma dos saldos de insumos é igual à soma dos saldos de produtos, e ambos os saldos de produtos são não negativos.

ZK Anti-negação de serviço

Uma ferramenta anti-DOS intrigante: imagine que você tem alguma identidade na rede que não é facilmente criada; pode ser um perfil à prova de humanos ou 32 validadores ETH, ou apenas uma conta com saldo ETH diferente de zero. Poderíamos criar uma rede ponto a ponto mais resistente ao DOS, aceitando apenas mensagens que comprovem que o remetente possui um perfil. Cada perfil teria permissão para até 1.000 mensagens por hora. Se um remetente trapacear, seu perfil será removido da lista. Mas como garantimos a privacidade?

Primeiro, a configuração: seja k a chave privada do usuário e A=privtoaddr(k) o endereço correspondente. Uma lista de endereços válidos é pública (por exemplo, um registro na cadeia). Até agora, isso reflete o exemplo à prova de humanos: você deve provar que possui a chave privada de um endereço sem revelar qual. Mas não queremos apenas provas de que você está na lista. Precisamos de um protocolo que permita provar que está na lista, mas limite suas provas.

Dividiremos o tempo em períodos: cada um com duração de 3,6 segundos (perfazendo 1.000 períodos por hora). Nosso objetivo é permitir que cada usuário envie apenas uma mensagem por período; se enviarem dois no mesmo período, são pegos. Para permitir rajadas ocasionais, eles podem usar períodos recentes. Assim, se um usuário tiver 500 períodos não utilizados, ele poderá enviar 500 mensagens de uma só vez.

Protocolo

Vamos começar com uma versão básica usando anuladores. Um usuário gera um nulificador com (N = \text{hash}(k, e)) onde (k) é sua chave e (e) é um número de época e, em seguida, publica-o com a mensagem (m). ZK-SNARK então ofusca o (\text{hash}(m)). Nada sobre (m) é verificado neste processo, vinculando assim a prova a uma única mensagem. Se um usuário vincular duas provas a duas mensagens distintas usando o mesmo anulador, ele corre o risco de ser pego.

Agora, mudamos para uma versão mais complexa. Neste cenário, o protocolo subsequente revela a sua chave privada em vez de apenas confirmar se alguém usou a mesma época duas vezes. Nossa técnica fundamental depende do princípio de que “dois pontos determinam uma linha”. Revelar um ponto numa linha revela pouco, mas expor dois pontos revela a linha inteira.

Para cada época (e), escolhemos uma linha (L_e(x) = \text{hash}(k, e) \times x + k). A inclinação da reta é (\text{hash}(k, e)), e a interceptação y é (k), ambas desconhecidas do público. Para produzir um certificado para a mensagem (m), o remetente fornece (y = L_e(\text{hash}(m)) = \text{hash}(k, e) \times \text{hash}(m) + k ), juntamente com uma prova ZK-SNARK de que o cálculo de (y) é preciso.

Resumindo, ZK-SNARK é o seguinte:

Entradas Públicas:

• ({A_1…A_n}): uma lista de contas válidas

• (M): A mensagem que está sendo validada pelo certificado

• (E): O número da época do certificado

• (Y): Avaliação da função de linha

Entrada privada:

• (K): Sua chave privada

Função de verificação:

• Verifique se (\text{privtoaddr}(k)) existe em ({A_1…A_n})

• Confirme (y = \text{hash}(k, e) \times \text{hash}(m) + k)

Mas e se alguém usar uma época duas vezes? Eles revelariam dois valores (m_1) e (m_2) junto com seus valores de certificado (y_1 = \text{hash}(k, e) \times \text{hash}(m_1) + k) e (y_2 = \text{hash}(k, e) \times \text{hash}(m_2) + k). Podemos então utilizar esses dois pontos para recuperar a linha e posteriormente a interceptação y, que é a chave privada.

Portanto, se alguém reutilizar uma época, inadvertidamente revelará sua chave privada para todos. Dependendo do contexto, isto pode levar ao roubo de fundos ou à simples transmissão da chave privada e à sua integração num contrato inteligente, resultando na remoção do endereço associado.

Um sistema anti-negação de serviço anônimo off-chain viável, adequado para redes peer-to-peer blockchain, aplicativos de bate-papo e sistemas similares, não exige prova de trabalho. O projecto RLN centra-se essencialmente neste conceito, embora com pequenas alterações (nomeadamente, utilizam tanto nulificadores como a técnica da linha de dois pontos, tornando mais simples a detecção de casos em que uma época é reutilizada).

A reputação negativa de ZK

Imagine criar o 0chan, um fórum online como o 4chan que oferece anonimato completo (você nem tem nomes permanentes), mas com um sistema de reputação para promover conteúdo de maior qualidade. Tal sistema poderia ter um DAO de governança para sinalizar postagens que violam as regras do sistema, introduzindo um mecanismo de três ataques.

O sistema de reputação pode atender a reputações positivas ou negativas; no entanto, acomodar a reputação negativa exige infraestrutura adicional. Isso exige que os usuários incorporem todos os dados de reputação em suas provas, mesmo que sejam negativos. Vamos nos concentrar principalmente neste caso de uso desafiador, semelhante ao que o Unirep Social pretende implementar.

Postagem vinculada: conhecimento básico

Qualquer pessoa pode postar transmitindo uma mensagem na rede que contém a postagem, acompanhada de um ZK-SNARK. Este ZK-SNARK serve como prova de que (i) você possui uma identidade externa única que lhe concede permissão para criar uma conta, ou (ii) você publicou anteriormente postagens específicas. Especificamente, o ZK-SNARK funciona da seguinte forma:

Entradas Públicas:

• Anulificador, N

• Raiz de estado de blockchain mais recente, R

• Conteúdo da postagem ('misturado' na prova para vinculá-lo à postagem, sem nenhum cálculo)

Entradas privadas:

• Sua chave privada, ok

• Uma identidade externa (endereço A) ou o anulador, Nprev, usado na postagem anterior

• Uma prova Merkle, M, de que a cadeia contém A ou Nprev

• A i-ésima postagem que você publicou usando esta conta

Função de verificação:

1. Confirme que M é um ramo Merkle válido, provando que (A ou Nprev, o que for fornecido) é uma folha de uma árvore com raiz R.

2. Verifique N = enc(i, k) onde enc é uma função de criptografia (por exemplo, AES).

3. Se i=0, verifique A=privtoaddr(k), caso contrário, verifique Nprev=enc(i−1,k).

Além da validação da prova, a cadeia também verifica (i) se R é na verdade uma raiz de estado recente e (ii) se o anulador N não foi usado antes. Até este ponto, ela se assemelha às moedas de preservação de privacidade descritas anteriormente, mas adicionamos um processo para “cunhar” novas contas e removemos a capacidade de “enviar” sua conta para chaves diferentes. Em vez disso, todos os anuladores são gerados usando a chave original. Empregamos enc aqui para tornar o anulador reversível. Se você tiver a chave k, poderá descriptografar qualquer anulador específico na cadeia; se o resultado for um índice válido em vez de um jargão aleatório (por exemplo, podemos apenas verificar dec(N) <2^64), você saberia que o anulador foi gerado usando a chave k.

Adicionando reputação:

Neste esquema, a reputação está na rede e é explícita. Alguns contratos inteligentes possuem um método chamado addReputation, que recebe como entrada o anulador liberado com uma postagem e o número de unidades de reputação a serem adicionadas ou subtraídas.

Estendemos os dados armazenados na rede para cada postagem. Em vez de armazenar apenas o nulificador N, armazenamos {N, h¯, u¯} onde:

• h¯ = hash(h, r) onde h representa a altura do bloco da raiz de estado referenciada na prova.

• u¯ = hash(u, r) onde u é a pontuação de reputação da conta (começando em 0 para novas contas).

R aqui está um valor aleatório adicionado para evitar que h e u sejam encontrados por meio de pesquisa de força bruta. Em termos criptográficos, adicionar R torna o hash um compromisso oculto.

Suponha que uma postagem use root R e armazene {N, h¯, u¯}. Dentro de sua prova, há um link para uma postagem anterior que armazenou os dados {Nprev, h¯prev, u¯prev}. A prova da postagem também precisa passar por todas as entradas de reputação postadas entre hprev e h. Para cada nulificador N, a função de verificação descriptografa N usando a chave k do usuário. Se a descriptografia gerar um índice válido, ela aplicará a atualização de reputação. Se o total de todas as atualizações de reputação for igual a δ, então prova que u = uprev + δ.

Se desejarmos implementar uma regra de “três rebatidas e você estará fora”, ZK-SNARK também garantiria u > -3. Se quisermos uma regra em que uma postagem com rep ≥ 100 receba uma tag especial de “postagem de alta reputação”, isso também pode ser feito.

Para aumentar a escalabilidade deste sistema, podemos dividi-lo em dois tipos de mensagens: Posts e RCAs. Uma postagem estaria fora da rede, embora exija apontar para um RCA feito na semana passada. Os RCAs estariam na rede, percorrendo todas as atualizações de reputação desde o RCA anterior do editor. Dessa forma, a carga na cadeia é reduzida para uma transação por postagem por semana, mais uma transação para cada mensagem de reputação.

Responsabilizando as Partes Centralizadas

Às vezes, é necessário projetar um sistema com um “operador” centralizado. As razões para isso podem variar: às vezes é por escalabilidade e outras vezes por privacidade, especialmente a privacidade dos dados mantidos pela operadora. Por exemplo, o sistema de votação resistente à coerção MACI exige que os eleitores enviem os seus votos em cadeia, encriptados com uma chave detida por um operador centralizado. Este operador descriptografa todos os votos da rede, contabiliza-os e exibe o resultado final. Eles usam o ZK-SNARK para provar que tudo o que fizeram foi correto. Esta complexidade adicional é crucial para garantir uma privacidade robusta (conhecida como resistência coercitiva): os utilizadores não podem provar a ninguém como votaram, mesmo que quisessem. Graças ao blockchain e ao ZK-SNARK, nosso nível de confiança na operadora permanece mínimo. Operadores maliciosos podem violar a resistência coercitiva, mas como os votos são publicados na blockchain, eles não podem trapacear censurando os votos. E como eles devem fornecer um ZK-SNARK, eles não podem trapacear calculando mal os resultados.

Combinando ZK-SNARKs com MPC

Um uso mais avançado de ZK-SNARKs é em cálculos onde a prova é necessária, com entradas distribuídas entre duas ou mais partes, e não gostaríamos que nenhuma parte soubesse sobre as contribuições dos outros. Em um cenário bipartido, circuitos distorcidos podem atender aos requisitos de privacidade; para N partes, protocolos de computação multipartidários mais complexos podem ser usados. ZK-SNARKs podem ser integrados a esses protocolos para cálculos multipartidários verificáveis. Isso permite sistemas avançados de reputação, permitindo que vários participantes executem cálculos conjuntos com base em suas informações privadas. A matemática para conseguir isso efetivamente ainda está em seus estágios iniciais.

O que não podemos tornar privado?

ZK-SNARKs é altamente eficaz na criação de sistemas onde os usuários possuem estados privados. No entanto, não pode manter um estado tão privado que ninguém conhece. Para que a informação seja comprovada, o provador deve conhecê-la em texto simples. Uniswap é um exemplo difícil de privatizar. No Uniswap, existe uma “entidade” lógica central – a conta do provedor de liquidez, que não pertence a ninguém, e todas as transações do Uniswap ocorrem com esta conta. Você não pode ocultar o estado desta conta, pois alguém precisa manter esse estado em texto simples para provar isso, e cada transação exigiria seu envolvimento ativo. Você poderia usar os circuitos distorcidos do ZK-SNARK para criar uma versão centralizada, segura e privada do Uniswap, mas não está claro se os benefícios superariam os custos. Pode até não oferecer quaisquer benefícios reais: os contratos precisam de informar os utilizadores sobre os preços dos activos, e as mudanças de preços por bloco podem revelar a actividade de transacção. As blockchains podem globalizar a informação estatal, e os ZK-SNARKs podem privatizá-la, mas não existe um método sólido para globalizar e privatizar a informação estatal simultaneamente.

Juntando as primitivas

Nas seções acima, vimos exemplos de ferramentas que são poderosas por si só, mas que também podem servir como blocos de construção para outras aplicações. Os anuladores, vitais para as moedas, agora reaparecem em outros casos de uso. A técnica de “vinculação coercitiva” usada na seção de reputação negativa tem ampla aplicação. É altamente eficaz para muitos aplicativos onde o “perfil” de um usuário muda ao longo do tempo de maneiras complexas e você deseja obrigar os usuários a seguir as regras do sistema enquanto preserva a privacidade. Os usuários podem até ser encarregados de representar seu “estado” interno usando uma árvore Merkle totalmente privada. A ferramenta “commitment pool” mencionada pode ser construída com ZK-SNARK. Se certos aplicativos não puderem funcionar totalmente on-chain e exigirem um operador centralizado, as mesmas técnicas podem manter o operador honesto. ZK-SNARK é uma ferramenta potente que combina benefícios de responsabilidade e privacidade. Embora tenham suas limitações, em alguns casos, designs de aplicativos inteligentes podem contornar essas restrições. Espero ver mais aplicativos adotando o ZK-SNARK e, eventualmente, construindo aplicativos que combinem o ZK-SNARK com outras formas de criptografia nos próximos anos.

Isenção de responsabilidade:

1. Este artigo foi reimpresso de [Foresightnews]. Todos os direitos autorais pertencem ao autor original [Jacob Ko]. Se houver objeções a esta reimpressão, entre em contato com a equipe do Gate Learn e eles cuidarão disso imediatamente.
2. Isenção de responsabilidade: As opiniões e pontos de vista expressos neste artigo são exclusivamente do autor e não constituem qualquer conselho de investimento.
3. As traduções do artigo para outros idiomas são feitas pela equipe do Gate Learn. A menos que mencionado, é proibido copiar, distribuir ou plagiar os artigos traduzidos.