Os zk-SNARKS são uma poderosa ferramenta criptográfica que se tornou uma parte cada vez mais essencial tanto de aplicações blockchain como não baseadas em blockchain. A sua complexidade é evidente tanto na compreensão de como funcionam como na forma como podem ser eficazmente utilizados. Este artigo aprofunda como os zk-SNARKS se adaptam às aplicações atuais, fornece exemplos do que podem e não podem alcançar e oferece orientações gerais sobre quando os zk-SNARKS são adequados para aplicações específicas. Uma ênfase particular será no 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 um w, tal que para um determinado f e x, f (x, w) = Verdade, 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 se soubessem e.

Isto dá ao ZK-SNARKS dois atributos: privacidade e escalabilidade. Como mencionado, os nossos exemplos neste artigo centrar-se-ão principalmente no aspecto da privacidade.

Comprovante de Adesão

Suponha que tenha uma carteira Ethereum e queira provar que esta carteira está registada num sistema de prova de humanidade, sem revelar quem é realmente o indivíduo registado. Esta função pode ser descrita matematicamente como:

Entrada privada (w): A sua morada A, a sua morada chave privada 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, σ) e x como uma lista de perfis válida {H1…Hn}

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

Confirme privtoaddr (k) = A

Se ambas as verificações forem aprovadas, devolva Verdadeiro. Se algum deles falhar, devolva False.

O provador gera o seu endereço A e a chave associada k, fornecendo w= (A, k) como a entrada privada para f. Obtêm a opinião pública, que é o conjunto atual de perfis verificados de prova de humanidade {H1…Hn}, da cadeia. Em seguida, executam o algoritmo de prova zk-SNark, que (assumindo que a entrada está correta) produz uma prova. Esta prova é enviada ao verificador, juntamente com a altura do bloco onde eles buscavam 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 mergulhar em exemplos mais complexos, recomendo fortemente compreender completamente o exemplo acima.

Tornar 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 O (n) tempo para “inserir” este conjunto no mecanismo zk-SNARK. Este problema pode ser resolvido usando a raiz Merkle na cadeia, que engloba todos os perfis, como entrada pública (potencialmente apenas a raiz do estado). 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 é o Caulk. No futuro, alguns destes casos de utilização poderão fazer a transição para soluções semelhantes ao Caulk.

zk-SNARKS e Moedas

Projetos como o Zcash e o Tornado.cash permitem-nos possuir moedas que protegem a privacidade. Agora, poder-se-ia pensar que poderiam utilizar as mencionadas “provas humanas ZK”, mas não se trata de provar o acesso a provas de perfil humano; trata-se de provar o acesso a moedas. Aqui reside um problema: temos de abordar tanto a privacidade como os gastos duplos simultaneamente. Ou seja, não devemos gastar a mesma moeda duas vezes.

Veja como resolvemos: Qualquer pessoa que possua uma moeda tem um “s” secreto privado. 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 está armazenado numa árvore Merkle.

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

• As entradas públicas incluem um anulador N, a raiz de Merkle R atual ou recente e uma nova folha L' (destinada ao destinatário que tem um 'secreto' passado para o 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 enraizada 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 o L', mas está “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 usado 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, ligamos dois valores: L (aparecendo na cadeia quando a moeda é cunha) e N (aparecendo quando gasto), sem revelar qual L se conecta a qual N. A conexão entre L e N só é discernível quando conhece o segredo s que os gera. 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.

Isto é um primitivo crucial de compreender. Muitos mecanismos que descrevemos abaixo baseiam-se nisto, embora com finalidades variadas.

Moedas com Saldos Arbitrários

O acima exposto pode ser facilmente alargado a moedas com saldos arbitrários. Mantemos o conceito de uma “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 encriptado. 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 entrada é igual à soma dos saldos de saída, e ambos os saldos de saída são não negativos.

ZK Anti-negação de serviço

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

Primeiro, a configuração: seja k a chave privada do utilizador e a=privtoAddr (k) o endereço correspondente. Uma lista de endereços válidos é pública (por exemplo, um registo na cadeia). Até agora, isso reflete o exemplo à prova de humanos: tem de provar que possui a chave privada de um endereço sem revelar qual. Mas não queremos apenas provas de que está na lista. Precisamos de um protocolo que lhe permita provar que está na lista mas limita as suas provas.

Vamos dividir o tempo em períodos: cada um com duração de 3,6 segundos (fazendo 1000 períodos por hora). O nosso objetivo é permitir que cada utilizador envie apenas uma mensagem por período; se enviarem duas no mesmo período, serão pego. Para permitir explosões ocasionais, podem usar períodos recentes. Portanto, se um utilizador tiver 500 períodos não utilizados, pode enviar 500 mensagens de uma só vez.

Protocolo

Vamos começar com uma versão básica usando anuladores. Um utilizador gera um anulador com (N =\ text{hash}(k, e)) onde (k) é a sua chave, e (e) é um número de época, depois publica com mensagem (m). O ZK-SNARK ofusca então o (\ text{hash}(m)). Nada sobre (m) é verificado neste processo, vinculando assim a prova a uma única mensagem. Se um utilizador vincular duas provas a duas mensagens distintas usando o mesmo anulador, 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. A nossa técnica fundamental se baseia no princípio de que “dois pontos determinam uma linha”. Revelar um ponto numa linha revela pouco, mas expor dois pontos revela toda a linha.

Para cada época (e), escolhemos uma linha (L_e (x) =\ text{hash}(k, e)\ times x + k). A inclinação da linha é (\ text{hash}(k, e)), e a intercepção y é (k), ambos desconhecidos 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, o ZK-SNARK é o seguinte:

Entradas Públicas:

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

• (M): A mensagem a ser validada pelo certificado

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

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

Entrada privada:

• (K): A sua chave privada

Função de verificação:

• Verificar 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) juntamente com os 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 estes dois pontos para recuperar a linha e, posteriormente, a intercepção y, que é a chave privada.

Então, se alguém reutiliza uma época, inadvertidamente revela a sua chave privada a todos. Dependendo do contexto, isso pode levar ao roubo de fundos ou simplesmente a transmitir a chave privada e integrá-la num contrato inteligente, resultando na remoção do endereço associado.

Um sistema anti-negação de serviço anónimo fora da cadeia viável, adequado para redes ponto a ponto blockchain, aplicações de chat e sistemas semelhantes, não exige provas de trabalho. O projeto RLN centra-se essencialmente neste conceito, embora com pequenas alterações (nomeadamente, utilizam ambos os anulificadores e a técnica de linha de dois pontos, tornando mais simples detetar instâncias em que uma época é reutilizada).

Reputação negativa da ZK

Imagine estabelecer o 0chan, um fórum online como o 4chan que oferece anonimato completo (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 greves.

O sistema de reputação pode atender a reputações positivas ou negativas; no entanto, acomodar a reputação negativa exige infraestruturas adicionais. Isto exige que os utilizadores incorporem todos os dados de reputação nas suas provas, mesmo que sejam negativos. Vamos focar-nos principalmente neste caso de uso desafiador, semelhante ao que a Unirep Social pretende implementar.

Postagem vinculada: Conhecimento Básico

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

Entradas Públicas:

• Anulador, N

• A raiz do estado blockchain mais recente, R

• Publicar conteúdo ('misturado' na prova para ligá-lo ao post, sem quaisquer cálculos)

Entradas Privadas:

• A sua chave privada, k

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

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

• O quinto post que 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 encriptação (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 é realmente uma raiz de estado recente e (ii) se o anulador N não foi usado antes. Até agora, assemelha-se a moedas de preservação da privacidade descritas anteriormente, mas adicionamos um processo para 'cunhar' novas contas e removemos a capacidade de 'enviar' a 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 tiver a chave k, pode 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), saberia que o anulador foi gerado usando a chave k.

Adicionar Reputação:

Neste esquema, a reputação está em cadeia e explícita. Alguns contratos inteligentes têm um método chamado AddReputation, que leva o anulador liberado com uma postagem e o número de unidades de reputação a serem adicionadas ou subtraídas como entrada.

Estendemos os dados armazenados na cadeia para cada postagem. Em vez de armazenar apenas o anulador 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 (a partir de 0 para novas contas).

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

Suponha que um post usa root R e armazena {N, h¯, u¯}. Dentro da sua prova, tem um link para um post anterior que armazenava os dados {Nprev, h¯prev, u¯prev}. A prova do post também tem de atravessar todas as entradas de reputação publicadas entre hprev e h. Para cada anulador N, a função de verificação descriptografa N usando a chave do utilizador k. Se a descriptografia produz um índice válido, aplica a atualização de reputação. Se o total de todas as atualizações de reputação for igual a δ, isso prova u = uprev + δ.

Se quisermos implementar uma regra de “três ataques e está fora”, o ZK-SNARK também garantiria u > -3. Se quisermos uma regra em que um post com rep ≥ 100 receba uma etiqueta especial de “post 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. Um post seria fora da cadeia, embora exija apontar para um RCA feito na semana passada. Os RCAs estariam na cadeia, atravessando todas as atualizações de reputação desde o RCA anterior do editor. Desta forma, a carga na cadeia é reduzida a uma transação por post por semana, mais uma transação para cada mensagem de reputação.

Responsabilizar as Partes Centralizadas

Às vezes, é necessário projetar um sistema com um “operador” centralizado. As razões para isso podem variar: às vezes, é para escalabilidade, e outras, é para a privacidade, especialmente a privacidade dos dados mantidos pelo operador. Por exemplo, o sistema de votação resistente à coerção MACI exige que os eleitores apresentem os seus votos em cadeia, encriptados com uma chave detida por um operador centralizado. Este operador descriptografa todos os votos em cadeia, conta-os e exibe o resultado final. Usam o ZK-SNARK para provar que tudo o que fizeram era preciso. 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 à blockchain e ao ZK-SNARK, o nosso nível de confiança no operador permanece mínimo. Operadores mal-intencionados podem violar a resistência coercitiva, mas uma vez que os votos são publicados na cadeia de blocos, não podem trapacear censurando os votos. E uma vez que devem fornecer um ZK-SNARK, não podem trapacear calculando mal os resultados.

Combinar zk-SNARKS com MPC

Uma utilização mais avançada do zk-SNARKs é em cálculos onde é necessária prova, com entradas distribuídas entre duas ou mais partes, e não gostaríamos que nenhuma das partes soubesse da entrada dos outros. Num cenário bipartidário, os circuitos distorcido podem cumprir os requisitos de privacidade; para N partes, podem ser utilizados protocolos de computação multipartidários mais intrincados. O zk-SNARKS pode ser integrado com estes protocolos para cálculos multipartidários verificáveis. Isto permite sistemas avançados de reputação, permitindo que vários participantes executem cálculos conjuntos nas suas entradas privadas. A matemática para conseguir isso de forma eficaz ainda está nos seus estágios iniciais.

O que não podemos tornar privado?

O zk-SNARKS é altamente eficaz na criação de sistemas onde os utilizadores têm 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. O Uniswap é um exemplo difícil de privatizar. No Uniswap, existe uma “entidade” lógica central — a conta do fornecedor de liquidez, que não pertence a ninguém, e todas as transações Uniswap ocorrem com esta conta. Não pode ocultar o estado desta conta uma vez que alguém precisa manter este estado em texto simples para provar isso, e cada transação exigiria o seu envolvimento ativo. Poderia usar os circuitos distorcidos do ZK-SNARK para fazer uma versão centralizada, segura e privada do Uniswap, mas não está claro se os benefícios superariam os custos. Pode nem oferecer quaisquer benefícios reais: os contratos precisam informar os utilizadores sobre os preços dos ativos, e as mudanças de preço por bloco podem revelar a atividade da transação. Os blockchains podem globalizar a informação do estado, e os zk-SNARKS podem privatizá-la, mas não existe um método sólido para globalizar e privatizar as informações do estado simultaneamente.

Juntar os primitivos

Nas secções acima, vimos exemplos de ferramentas que são poderosas por si só mas também podem servir como blocos de construção para outras aplicações. Os anuladores, vitais para as moedas, reaparecem agora noutros casos de utilização. A técnica de “ligação coercitiva” usada na secção de reputação negativa tem uma aplicação ampla. É altamente eficaz para muitas aplicações onde o “perfil” de um utilizador muda ao longo do tempo de formas intrincadas, e quer obrigar os utilizadores a seguir as regras do sistema, preservando a privacidade. Os utilizadores podem até ter a tarefa de representar o seu “estado” interno usando uma árvore Merkle totalmente privada. A ferramenta de “pool de compromissos” mencionada pode ser construída com o ZK-SNARK. Se certas aplicações não podem funcionar totalmente na cadeia e requerem um operador centralizado, as mesmas técnicas podem manter o operador honesto. O ZK-SNARK é uma ferramenta potente, que combina benefícios de responsabilidade e privacidade. Embora tenham as suas limitações, em alguns casos, os designs de aplicações inteligentes podem contornar essas restrições. Espero ver mais aplicações adotarem o ZK-SNARK e eventualmente construir aplicações que fundam o ZK-SNARK com outras formas de encriptação nos próximos anos.

Isenção de responsabilidade：

1. Este artigo foi reimpresso de [Foresightnews]. Todos os direitos de autor pertencem ao autor original [Jacob Ko]. Se houver objeções a esta reimpressão, contacte a equipa do Gate Learn, e eles tratarão disso imediatamente.
2. Isenção de responsabilidade: As opiniões e opiniões expressas neste artigo são exclusivamente do autor e não constituem nenhum conselho de investimento.
3. As traduções do artigo para outras línguas são feitas pela equipa do Gate Learn. A menos que mencionado, é proibido copiar, distribuir ou plagiar os artigos traduzidos.