ZKP & zk-SNARKs
TL;DR
- zk-SNARKs = Argumentos sucintos não interativos de conhecimento zero
- Eles permitem que uma parte prove que sabe algo sem revelar a própria informação
- O Zcash usa zk-SNARKs para provar que uma transação é válida (valores corretos, entradas não gastas) sem revelar remetente, destinatário ou valor
- "Sucinto" significa que a prova é minúscula e rápida de verificar, mesmo para afirmações complexas
- O pool Orchard usa Halo 2, um sistema zk-SNARK sem necessidade de uma configuração confiável
O que é uma prova?
Provas são a base de toda a matemática. Uma prova é uma afirmação ou teorema que você está tentando provar e uma sequência de derivações feita para declarar que o teorema foi provado. Ex.: todos os ângulos de um triângulo somam 180° e podem ser verificados independentemente por qualquer pessoa (verificador).
Provas
Provador ---> Faz uma afirmação ---> Verificador escolhe ---> Aceitar/Rejeitar
(Tanto o provador quanto o verificador são algoritmos)
Na ciência da computação, o termo para provas verificáveis de forma eficiente é provas NP. Essas provas curtas podem ser verificadas em tempo polinomial. A ideia geral é: "Existe uma solução para um teorema e ela é passada ao verificador para conferência"
Em uma linguagem NP = duas condições devem ser atendidas:
Completude: Afirmações verdadeiras serão aceitas pelo verificador (permite que provadores honestos alcancem a verificação)
Solidez: Afirmações falsas não terão provas (para qualquer estratégia de um provador desonesto, ele não conseguirá provar a correção de uma afirmação incorreta).
Provas interativas e probabilísticas
Interação: Em vez de apenas ler a prova, o verificador interage com um provador em várias rodadas de mensagens.
Aleatoriedade: As solicitações do verificador ao provador são aleatórias, e o provador deve ser capaz de responder corretamente a cada uma delas.
Usando interação e aleatoriedade juntas, é possível provar uma afirmação a um verificador cego em Tempo Polinomial Probabilístico (PPT).
As provas interativas conseguem verificar de forma eficiente mais do que provas NP?
Provas NP vs. provas IP:
| Afirmação | NP | IP |
|---|
| NP | sim | sim |
| CO-NP | não | sim |
| #P | não | sim |
| PSPACE | não | sim |
NP - Existe uma solução para uma afirmação
CO-NP - Provar que não existem soluções para uma afirmação
#P - Contar quantas soluções existem para uma afirmação
PSPACE - Provar uma alternância de diferentes afirmações
O que é conhecimento zero?
O que um verificador pode computar após uma interação é idêntico ao que ele poderia provar antes. A interação ao longo de várias rodadas entre o provador e o verificador não aumentou o poder computacional do verificador.
O Paradigm da simulação
Esse experimento existe em toda a criptografia. Ele apresenta uma "Visão Real" e uma "Visão Simulada".
Visão Real: Todos os possíveis históricos de interações entre Provador e Verificador (P,V)
Visão Simulada: O verificador simula todas as possíveis interações entre Provador e Verificador
Um distinguidor em tempo polinomial tenta determinar se está olhando para a visão real ou para a simulada e solicita repetidamente uma amostra de ambas.
Diz-se que as duas visões são "computacionalmente indistinguíveis" se, para todos os algoritmos/estratégias de distinção, mesmo após receber um número polinomial de amostras da visão real ou simulada, a probabilidade for >1/2.
Argumentos de conhecimento zero
Um protocolo interativo (P,V) é de conhecimento zero se existir um simulador (algoritmo) tal que, para todo verificador probabilístico em tempo polinomial (quando o teorema está correto), as distribuições de probabilidade que determinam a visão real a partir da simulada sejam computacionalmente indistinguíveis.
Protocolos interativos são úteis quando há um único verificador. Um exemplo seria um auditor fiscal em um aplicativo de 'prova de impostos' com conhecimento zero.
O que é um SNARK?
Argumento sucinto não interativo de conhecimento
Definição ampla - Uma prova sucinta de que uma afirmação é verdadeira. A prova deve ser curta e rápida de verificar. Em SNARKs, uma única mensagem é enviada do Provador ao Verificador. O verificador então pode escolher aceitar ou rejeitar.
Exemplo de afirmação: "Eu conheço uma mensagem (m) tal que SHA256(m)=0"
Em um zk-SNARK, a prova não revela nada sobre a mensagem (m).
Polinômios: Somatórios de termos contendo uma constante (como 1,2,3), variáveis (como x,y,z) e expoentes de variáveis (como x², y³).
Exemplo: "3x² + 8x + 17"
Circuito aritmético: Um modelo para computar polinômios. De forma mais geral, ele pode ser definido como um Grafo Acíclico Direcionado no qual, em cada nó do grafo, é realizada uma operação aritmética. O circuito consiste em portas de adição, portas de multiplicação e algumas portas constantes. Da mesma forma que circuitos booleanos carregam bits em fios, circuitos aritméticos carregam inteiros.
Neste exemplo, o provador quer convencer o verificador de que conhece uma solução para o circuito aritmético.
Compromissos: Para fazer isso, o provador colocará todos os valores (privados e públicos) associados ao circuito em um compromisso. Compromissos ocultam suas entradas usando uma função cuja saída é irreversível.
Sha256 é um exemplo de função hash que pode ser usada em um esquema de compromisso.
Depois que o provador se compromete com os valores, os compromissos são enviados ao verificador (com a confiança de que ele não conseguirá descobrir nenhum dos valores originais). O provador então consegue mostrar ao verificador que conhece cada um dos valores nos nós do grafo.
Transformação Fiat-Shamir
Para tornar o protocolo não interativo, o provador gera aleatoriedade (usada para o desafio oculto) em nome do verificador usando uma função hash criptográfica. Isso é conhecido como oráculo aleatório. O provador pode então enviar uma única mensagem ao verificador, que poderá conferir se ela está correta.
Para formar um SNARK que possa ser usado em circuitos gerais, dois elementos são necessários:
Esquema de compromisso funcional: Permite que um remetente se comprometa com um polinômio usando uma string curta que pode ser usada por um verificador para confirmar avaliações alegadas do polinômio comprometido.
Oráculo interativo polinomial: O verificador pede ao provador (algoritmo) para abrir todos os compromissos em vários pontos de sua escolha usando um esquema de compromisso polinomial e verifica se a identidade se mantém verdadeira entre eles.
Configuração
Procedimentos de configuração ajudam o verificador resumindo um circuito e gerando parâmetros públicos.
Tipos de configuração de pré-processamento:
Configuração confiável por circuito - É executada uma vez por circuito. É específica para um circuito e a aleatoriedade secreta (Common Reference String) deve ser mantida em segredo + destruída.
Uma configuração comprometida nesse método significa que um provador desonesto pode provar afirmações falsas.
Configuração confiável, mas universal - Só precisa executar uma configuração confiável uma vez e depois consegue pré-processar deterministicamente múltiplos circuitos.
Configuração transparente (sem configuração confiável)- O algoritmo de pré-processamento não usa nenhuma aleatoriedade secreta.
Tipos de construções de provas SNARK:
Groth16: Requer uma configuração confiável, mas tem provas muito curtas que podem ser verificadas rapidamente.
Sonic/Marlin/PLONK: Configuração confiável universal.
DARK/Halo/STARK: Não requerem uma configuração confiável, mas produzem provas ligeiramente mais longas ou podem demorar mais para serem executados pelo provador.
SNARKs são úteis quando múltiplos verificadores são necessários, como em uma blockchain como o Zcash ou um zk-Rollup como Aztec, para que múltiplos nós validadores não precisem interagir ao longo de várias rodadas com cada prova.
Como o zk-SNARK é implementado no Zcash?
De forma geral, provas de conhecimento zero são uma ferramenta para impor comportamento honesto em protocolos sem revelar nenhuma informação.
O Zcash é uma blockchain pública que viabiliza transações privadas. zk-SNARK é usado para provar que uma transação privada é válida dentro das regras de consenso da rede sem revelar quaisquer outros detalhes sobre a transação.
Vídeo explicativo - Nesta palestra, Ariel Gabizon apresenta descrições da Árvore de Compromissos de Notes do Zcash, Avaliação Polinomial Cega e Desafios Ocultos Homomorficamente, e como eles são implementados na rede.
Leia o livro do Halo2 para mais informações.
Outras aplicações de conhecimento zero
zk-SNARKs proporcionam várias vantagens em uma variedade de aplicações diferentes. Vejamos alguns exemplos.
Escalabilidade: Isso é alcançado por meio de 'Terceirização da Computação'. Não há necessidade estrita de conhecimento zero para que uma chain L1 verifique o trabalho de um serviço off-chain. As transações não são necessariamente privadas em uma zk-EVM.
A vantagem de um serviço Rollup baseado em prova (zk-Rollup) é processar um lote de centenas/milhares de transações, e a L1 consegue verificar uma prova sucinta de que todas as transações foram processadas corretamente, escalando a taxa de transferência de transações da rede por um fator de 100 ou 1000.
Interoperabilidade: Isso é alcançado em uma ponte zk ao 'travar' ativos em uma chain de origem e provar para a chain de destino que os ativos foram travados (prova de consenso).
Conformidade: Projetos como Espresso conseguem provar que uma transação privada está em conformidade com as leis bancárias locais sem revelar os detalhes da transação.
Combate à desinformação: Entre vários exemplos fora de blockchain e criptomoedas, está o uso de geração de provas em imagens que foram processadas por veículos de notícias e mídia, permitindo que os espectadores verifiquem independentemente a origem de uma imagem e todas as operações realizadas nela. https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
Aprendizado adicional:
Bibliografia de conhecimento zero - a16z Crypto
zkSNARK's com Hanh Huynh Huu
Zcash: Halo 2 e SNARKs sem configurações confiáveis - Sean Bowe no Dystopia labs
Provas de conhecimento zero com Avi Wigderson - Numberphile
Provas interativas de conhecimento zero - artigo da Chainlink
Aula 1: Introdução e história de ZKP - zklearning.org
Simple Explanation of Arithmetic Circuits - Medium
Scalability is Boring, Privacy is Dead: ZK-Proofs, What are They Good for?
Páginas relacionadas
