O que é uma prova de conhecimento zero (zero-knowledge proof)

Uma prova de conhecimento zero é uma forma de provar que uma afirmação é verdadeira sem revelar a afirmação em si. Quem prova é o prover; quem confere é o verifier. A definição amplamente usada hoje sai de um artigo de 1985, The knowledge complexity of interactive proof systems: um protocolo por o qual uma parte prova a outra que algo é verdade, sem revelar nenhuma informação além do fato de aquela afirmação específica ser verdade.

Na prática, o protocolo precisa cumprir três condições. Completude: se a afirmação for válida e os dois lados agirem de forma honesta, a prova sempre passa. Solidez: uma afirmação falsa não consegue enganar o verificador, a não ser com probabilidade ínfima. Conhecimento zero: o verificador não aprende nada sobre o conteúdo, apenas se ele é válido.

Na forma interativa, a prova tem três partes. A testemunha (witness) é a informação secreta que o prover diz conhecer; ele escolhe uma pergunta do conjunto que só quem tem a informação sabe responder, calcula a resposta e envia. O verificador lança um desafio (challenge) aleatório, e o prover devolve a resposta (response). Repetindo o ciclo muitas vezes, a chance de blefar cai até o verificador se convencer. É a história da caverna de Ali Baba: Peggy prova a Victor que conhece a frase que abre a porta mágica, sem dizer a frase.

Provas interativas exigiam os dois lados disponíveis e deixavam o resultado inútil para terceiros. Blum, Feldman e Micali propuseram as provas não interativas, com uma chave compartilhada: uma única rodada de comunicação, e qualquer um com a chave e o algoritmo de verificação confere a prova depois.

Os dois sistemas em uso hoje seguem esse caminho. ZK-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) gera provas pequenas, menores que a informação original, e rápidas de verificar, mas depende de um setup confiável: parâmetros públicos (Common Reference String) gerados numa cerimônia com várias partes, cuja segurança se mantém se ao menos uma destruir sua parte da aleatoriedade. ZK-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge) dispensa o setup confiável, usando aleatoriedade publicamente verificável, escala melhor quando a base de dados cresce e produz provas maiores.

Mecanismos assim já rodam. Zcash e Monero ocultam remetente, destinatário e valores; o Tornado Cash mistura transações na Ethereum. O World ID usa provas para mostrar que alguém é um humano único sem revelar quem é, com o Semaphore da equipe PSE da Ethereum Foundation; o documento digital nacional do Butão, construído na Ethereum, permite atestar cidadania ou maioridade sem expor os dados do documento. Em computação verificável, rollups e validiums executam milhares de transações fora da cadeia e enviam a prova para a Ethereum, que aplica o resultado sem reexecutar; a verificação de um ZK-SNARK na Ethereum custa cerca de 500 mil gas. O MACI apura votações on-chain sem revelar o voto de cada um.

Ainda não está tudo resolvido. Gerar provas exige máquinas caras, e verificar provas encarece as aplicações. O setup confiável dos SNARKs exige confiar nos participantes da cerimônia, e as curvas elípticas deles podem cair para computadores quânticos um dia; STARKs dependem só de hashings resistentes a colisão e são considerados imunes a essa ameaça. O EIP-7503, que propõe transferências privadas nativas na Ethereum, segue como proposta, não como regra da rede.