Conhecimento Zero (Zk-SNARKS): configurações atualizáveis na blockchain

[tsnnst]

Conhecimento Zero (Zk-SNARKS): configurações atualizáveis ​​na blockchain

Zk-SNARKs provaram ser um ‘canivete suíço’ para blockchain e livros distribuídos, com aplicativos em privacidade, interoperabilidade e escalabilidade

31 de agosto de 2022 - Thomas Kerber - 12 minutos de leitura

Desde sua introdução, as provas de conhecimento zero (ZKPs) têm sido usadas para oferecer suporte a aplicativos em potencial, desde computação terceirizada verificável até credenciais anônimas, em uma infinidade de configurações que exigem um equilíbrio entre privacidade e integridade. Os ZKPs permitem que uma parte prove a outra que uma determinada declaração ou afirmação é verdadeira, sem revelar o conteúdo dessa declaração. A aplicação de ZKPs em uma variedade de casos de uso na cadeia contribui para resolver problemas de privacidade, interoperabilidade e escalabilidade.

Neste post, vamos dar uma olhada nos diferentes tipos de ZKPs e seus casos de uso específicos. Também discutimos Zk-SNARKs, alguns problemas conhecidos em sua aplicação, e propomos um mecanismo blockchain com características seguras em condições comparáveis ​​ao protocolo blockchain. O artigo é baseado na materia de pesquisa ‘Mining for Privacy: How to Bootstrap a Snarky Blockchain’ (Mineração para Privacidade: como inciar uma Blockchain a partir do conhecimento zero) escrito por Thomas Kerber, Aggelos Kiayias e Markulf Kohlweiss.

Diferentes tipos de ZKPs

Na configuração blockchain, é comum que os clientes baixem e verifiquem todas as transações publicadas na rede. Isso significa que tamanhos de prova pequenos e tempo de verificação rápido são importantes para a implantação prática de protocolos de conhecimento zero. Existem vários esquemas práticos para escolher, com um vasto espaço de trocas em desempenho e suposições criptográficas:

• Argumentos de conhecimento zero não interativos (NIZKs): este é o conceito mais geral. O NIZK pode ser não sucinto, mas, como benefício, pode depender de suposições criptográficas padrão e geralmente satisfaz fortes garantias de segurança.

• Argumentos sucintos não interativos de conhecimento zero (SNARGs): alcance a concisão ao custo de suposições criptográficas mais fortes e garantias de segurança muitas vezes mais fracas.

• Argumentos de conhecimento sucintos não interativos de conhecimento zero (SNARKs ou às vezes zk-SNARKs): estes são SNARGs que também são provas de conhecimento e conhecimento zero. O nome também é popular por causa do poema sem sentido de Lewis Carrol ‘The Hunting of the Snark’ (A caça ao Snark).

• Argumentos transparentes sucintos de conhecimento (STARKs): transparente aqui se refere à configuração que requer apenas uma função de hash confiável. Isso é benéfico, mas pode vir com uma sobrecarga de desempenho.

Atualmente, o sistema de prova mais atraente do ponto de vista do verificador é um argumento sucinto de conhecimento (pré-processamento) não interativo, ou zk-SNARK para abreviar, que tem um tamanho de prova constante pequeno e custos de verificação em tempo constante, mesmo para arbitrariamente grandes relações. Os Zk-SNARKs provaram ser um “canivete suíço” para blockchain e livros-registro distribuídos, com aplicações em privacidade, interoperabilidade e escalabilidade.

Casos de uso

Os casos de uso de zk-SNARKs são muito diversos. Às vezes, SNARKs são empregados para melhorar as propriedades de desempenho e concisão do sistema. Outros casos de uso empregam zk-SNARKs para melhorar a privacidade. Alguns casos são mistos, onde ambos os aspectos desempenham um papel.

Na configuração da blockchain, levando em consideração o desempenho e a concisão, o zk-SNARKS pode contribuir muito para casos de uso como:

• Clientes Leves: para aumentar a eficiência dos parâmetros e a estrutura geral das aplicações. Sistemas de prova eficientes (sem um requisito de conhecimento zero) desempenham um papel importante na inicialização de clientes leves. Os sistemas de prova recursiva também agem como uma boa combinação para este caso de uso para garantir a segurança para recursão ilimitada, bem como o uso de funções externas (por exemplo, funções de hash) em provas recursivas.
• Contratos inteligentes: para descarregar possíveis congestionamentos do livro-registro devido à execução de contratos inteligentes públicos. A compilação de código on-chain para SNARKs, com tempo de verificação constante ou logarítmico, pode permitir validadores mais complexos.
• Prova de trabalho útil (PoUW): SNARKs podem ser a chave para verificar ‘computações úteis’ realizadas por mineradores, que de outra forma seriam caros para validar na cadeia.

Do ponto de vista da privacidade, muitos aplicativos empregam provas de conhecimento zero para implantar soluções de pagamento seguras, troca de opções, gerenciamento de identidades, votação, leilões, estatísticas verificáveis ​​(uma forma de oráculo blockchain) ou comunicação anônima incentivada. Os casos de uso podem incluir:

• Contratos inteligentes privados: os SNARKs são parte integrante do projeto atual de contratos inteligentes privados. Duas coisas são primordiais: universalidade, para oferecer suporte a contratos inteligentes implantados pelo usuário e facilidade de compilação. A expressividade dos contratos inteligentes pode ser eliminada para reduzir o espaço do problema, por exemplo, não permitindo loops ilimitados e recursão, de modo que a composição SNARK recursiva não é necessária. Fundamentalmente, algum subconjunto de uma linguagem de contrato de alto nível pode ser compilado em um circuito SNARK.

• Pagamentos privados: os ativos podem ser vistos como uma forma particular de reivindicação de identidade que inclui a modelagem da escassez. Uma proposta de pagamentos privados também pode oferecer suporte a tokens multiativos e não fungíveis e conectar esses tokens a contratos inteligentes.

• Gerenciamento de identidade: no contexto de credenciais verificáveis, os emissores podem afirmar reivindicações sobre assuntos gerando objetos criptográficos (credenciais). Posteriormente, os sujeitos apresentam suas credenciais para outros usuários que atuam como verificadores. Os verificadores são então capazes de validar que um emissor fez declarações sobre o assunto que apresenta a credencial.

• Votação e tesouraria: As provas ZK podem ser usadas na votação da tesouraria. Um sistema de tesouraria para protocolo de criptomoedas, por exemplo, fornece um esquema de votação que preserva a privacidade, onde as cédulas do eleitor são criptografadas e posteriormente contabilizadas usando cálculos homomórficos. As provas ZK no tesouro são protocolos Sigma não interativos baseados em DLP usados ​​para provar a exatidão de mensagens criptografadas em vários estágios do protocolo (por exemplo, que a cédula do eleitor criptografada contém uma cédula composta corretamente).

Os casos de uso mistos incluem:

• Oráculos Blockchain: SNARKs podem reduzir o custo de verificação ao agregar dados de várias fontes e podem reduzir o tamanho dos dados on-chain postados, incluindo apenas o valor agregado e a prova, em vez de todos os pontos de dados. Para atingir essas duas propriedades, as partes devem ser capazes de provar de forma sucinta o conhecimento das assinaturas em vários pontos de dados, bem como a respectiva média/mediana/variância.
• Sidechains: uma cadeia em uma configuração de pegging de cadeia pode atuar como um cliente leve para a outra cadeia, verificando transações de cadeia cruzada na outra cadeia sem ter que verificar a totalidade dessa cadeia. A diferença é que esta indexação é frequentemente mantida a longo prazo e, portanto, as provas podem ser fornecidas regularmente e de forma “atualizável”. Consulte Sidechains de prova de participação para obter mais informações.

Problemas conhecidos

O conhecimento zero não interativo requer alguma aleatoriedade compartilhada ou uma string de referência comum. Para muitos sistemas sucintos, uma propriedade mais forte é necessária:

Não só é necessário um valor aleatório compartilhado, mas também deve aderir a uma estrutura específica. Uma string de referência estruturada (SRS) normalmente consiste em elementos de grupo relacionados, ou seja: gxi para todo i∈𝕫n.

A maneira óbvia de amostrar tal string de referência da aleatoriedade pública revela os expoentes usados ​​– e o conhecimento desses valores quebra a solidez do próprio sistema de prova. Para piorar a situação, a segurança desses sistemas normalmente depende (entre outras coisas) do conhecimento de suposições de expoentes, que afirmam que para criar elementos de grupo relacionados de tal maneira requer conhecer os expoentes subjacentes e, portanto, qualquer amostra SRS terá que ‘conhecer’ os expoentes usados ​​e ser confiável para apagá-los, tornando-se, de fato, um único ponto de falha para o sistema subjacente.

A computação segura de várias partes (MPC) pode ser, e tem sido, usada para reduzir a confiança depositada em tal processo de configuração. No entanto, a seleção dos participantes para a computação segura e a verificação da geração do SRS pelo protocolo MPC mantêm um elemento de centralização. O uso de MPC continua sendo um elemento controverso na configuração de um sistema descentralizado que requer SNARKs.

Resolvendo problemas de privacidade com geração segura de SRS

Uma string de referência estruturada atualizável (uSRS) pode ser inicializada com segurança usando um livro-registro distribuído, exigindo que os criadores de blocos realizem atualizações em um uSRS em evolução durante um período de configuração inicial. Depois de aguardar o acordo sobre o uSRS final, ele pode ser usado com segurança.

A prova disso está nos meios básicos de operação dos livros de registro estilo Nakamoto: diferentes usuários podem estender uma cadeia de blocos se puderem satisfazer alguma condição, sendo esta condição associada a um tipo de dificuldade que garante que os atacantes sejam limitados no número de extensões que podem executar. Dada essa estrutura, associamos uma atualização do uSRS a cada bloco antes de um tempo 𝛿1. Este tempo é selecionado de forma que as propriedades de segurança do livro-registro garantam que pelo menos um dos blocos seja honesto em cada cadeia competitiva neste ponto.

Isso pode ser construído a partir de uma funcionalidade do livro-registro com um estado de liderança adicional, que é derivado de informações que os mineradores incorporam em seus blocos para codificar as atualizações do uSRS. Isso é deixado suficientemente amplo para permitir outros usos também. A ideia básica é mostrar que um livro-registro que realiza atualizações do uSRS em seu estado de liderança é equivalente ao que não o faz, mas é acompanhado por um uSRS segura. Após o tempo 𝛿1, os usuários aguardam mais um período de tempo 𝛿2 até que o prefixo comum garanta que todas as partes concordem com a string de referência.

Abstração de razão proposta

Nossa construção da funcionalidade de string de referência estruturada atualizável baseia-se nas propriedades do prefixo comum, qualidade da cadeia e crescimento da cadeia definidos na análise do backbone Bitcoin por Garay et al., para algoritmos de consenso do estilo Nakamoto:

• Prefixo comum. Dadas as cadeias atuais 𝛱1 e 𝛱2 de duas partes, e removendo k blocos da primeira, é um prefixo da segunda: 𝛱1⌊k ≺𝛱2.

• Qualidade da cadeia existencial. Para a corrente atual de qualquer parte 𝛱, quaisquer blocos l consecutivos nesta corrente incluirão pelo menos um bloco criado por uma parte honesta.

• Crescimento da cadeia. Se a cadeia de uma parte tiver comprimento c, s intervalos de tempo depois, ela terá pelo menos comprimento c+𝛾.

Construção descentralizada da uSRS

Nossa construção proposta, detalhada no artigo Mining for Privacy, é simples: cada cadeia está associada a um uSRS específico e, quando um minerador estende uma cadeia, eles também realizam uma atualização do uSRS. Na gênese da cadeia, a aleatoriedade conhecida (ou mesmo nenhuma aleatoriedade) pode ser usada. O princípio por trás desse design é direto: a capacidade de atualização do uSRS garante que, se uma única atualização for realizada honestamente (tanto usando aleatoriedade verdadeira quanto apagando essa aleatoriedade após a atualização), o uSRS resultante pode ser usado com segurança. Contamos com a propriedade de qualidade da cadeia existencial para garantir isso – uma vez que l blocos foram gerados, pelo menos um deles deve ser criado por um minerador honesto e, portanto, após l blocos, o uSRS de uma cadeia é seguro.

No entanto, não é suficiente saber que a string de referência de uma determinada cadeia é segura - para a maioria das aplicações práticas, queremos que todos os usuários concordem com a string de referência. Isso é fornecido pela propriedade prefixo comum, que garante que para qualquer cadeia de l+k blocos de comprimento, todos os outros usuários terão a mesma cadeia de referência que a gerada por esta cadeia – desde que os usuários parem de atualizar após l blocos!

Por fim, o crescimento da cadeia garante que o evento em que estamos interessados ​​– quando todos concordarem com a cadeia de referência – acabará por ocorrer. Garante que os usuários eventualmente terão uma cadeia de comprimento l+k. Especificamente, como a cada s unidades de tempo, blocos são gerados, o evento ocorrerá o mais tardar no tempo ⌈(l+k)/s⌉.

Isso tudo está bem em abstrato, mas deixa questões de praticidade: essas análises abstratas assumem que as atualizações podem ser criadas com pouco ou nenhum custo e que não afetam o procedimento padrão de mineração. No entanto, isso não é bem verdade para a mineração de prova de trabalho:

1. As atualizações são relativamente caras, levando de 5 a 10 minutos para serem computadas, dependendo do tamanho do uSRS de destino.

2. É possível trapacear nas atualizações, executando-as mais rapidamente, mas sem adicionar a segurança da string de referência.

Combinados, esses fatores representam um desafio, especialmente na configuração de prova de trabalho, onde a atualização precisa ser realizada antes que um minerador possa iniciar a mineração de um bloco. Isso atrasa os mineradores não trapaceiros, enquanto seus colegas trapaceiros já estão minerando! Como resultado, a dificuldade de mineração (correspondente ao tempo pretendido entre os blocos) não deve ser muito baixa, pois quanto menor, maiores os benefícios de um minerador trapaceiro. Por outro lado, uma dificuldade alta naturalmente leva a um tempo maior para se chegar a um consenso. Essa compensação está representada na Figura 1.

Desde que a dificuldade seja calibrada adequadamente, uma análise de simulação mostra que esse efeito não prejudica a segurança geral. Dependendo da probabilidade de falha (є) que estamos dispostos a tolerar e da fração do poder de mineração de um invasor (а) contra a qual queremos nos proteger, o uSRS pode ser gerado com segurança com o procedimento em algumas horas ou em vários meses em um cenário mais pessimista, como mostra a Figura 1.

Figura 1. O tempo necessário até que pelo menos uma atualização honesta seja garantida, em função do tempo de bloqueio de destino

Fonte: Documento de pesquisa ‘Mining for Privacy: How to Bootstrap a Snarky Blockchain’

Um problema semelhante ocorre ao considerar o comportamento racional – mineradores que buscam apenas lucro também tentarão trapacear em suas atualizações, não por maldade, mas simplesmente porque podem produzir blocos mais rapidamente se o fizerem. Isso pode ser contornado recompensando adicionalmente o bom comportamento – uma amostra de mineradores pode ser solicitada após o fato para fornecer aleatoriedade para suas atualizações e demonstrar que foi externado de maneira apropriada (por exemplo, usando uma função de hash). Se conseguirem fazê-lo, podem ganhar uma recompensa adicional, compensando qualquer perda que possam ter por não trapacear.

Em resumo, a aplicabilidade do zk-SNARKs beneficia varios casos diferentes de uso na cadeia, resolvendo problemas de privacidade, interoperabilidade e escalabilidade. Embora a configuração confiável, necessária para muitos zk-SNARKs, pareça estar em desacordo com a natureza descentralizada dos livros-registro distribuídos, ela pode ser executada de maneira totalmente descentralizada para SNARKs com cadeias de referência atualizáveis. Embora em princípio também seja possível usar SNARKs transparentes como o Halo, as técnicas descritas acima permitem que SNARKs como o Plonk (que pode ser mais eficiente dependendo das circunstâncias), contando com strings de referência atualizáveis, também sejam usados ​​com segurança para aplicativos em cadeia – não é mais o caso que as configurações SNARK são muito opacas para confiar, se é que alguma vez foram.