Intuição sobre ZKP: a caverna de Ali Babá

Uma prova de conhecimento zero (ZKP) permite que um provador convença um verificador de que conhece um segredo (ou de que uma afirmação é verdadeira) sem revelar o próprio segredo. Há três propriedades: completude, solidez e conhecimento zero.

Se o provador conhece o segredo, ele sempre consegue convencer o verificador. Um provador honesto que segue o protocolo terá sucesso com probabilidade 1 (ou com probabilidade esmagadora). O verificador não rejeitará uma prova válida.

Um provador trapaceiro (que não conhece o segredo) não consegue convencer o verificador, exceto com probabilidade desprezível. Cada rodada de interação reduz a probabilidade de trapaça — após k rodadas: no máximo 2^{-k} de probabilidade de sucesso para um trapaceiro.

O verificador não aprende nada além do fato de que a afirmação é verdadeira. Formalmente: existe um simulador que, sem conhecer o segredo, produz uma transcrição indistinguível da interação real entre provador e verificador. O verificador não obtém nenhum conhecimento adicional.

Uma caverna tem uma passagem em anel com uma porta mágica no meio. O provador (Alice) afirma que conhece a senha. O verificador (Bob) espera do lado de fora. Alice entra e segue pela esquerda ou pela direita. Bob grita por qual lado ela deve sair. Se Alice conhece a senha, sempre sai pelo lado correto. Probabilidade de trapaça por rodada: 1/2.

Após 20 rodadas, um trapaceiro consegue ter sucesso com probabilidade 2^{-20} ≈ 1 em um milhão. Alice (que conhece a senha) é bem-sucedida todas as vezes. Bob nunca aprende a senha — ele apenas vê Alice sair pelo lado solicitado. Isso é conhecimento zero.

As provas de conhecimento zero interativas exigem comunicação de ida e volta entre o provador e o verificador. As provas de conhecimento zero não interativas (NIZKs) usam a transformação de Fiat-Shamir: substituem o desafio aleatório do verificador por um hash do compromisso (hash = oráculo aleatório). Isso produz uma única cadeia de prova que qualquer pessoa pode verificar.

Uma ZKP é uma prova de conhecimento (PoK) se a estratégia do provador implica que ele poderia extrair o segredo. Isso é mais forte do que apenas provar que uma afirmação é verdadeira. As assinaturas ECDSA e Schnorr são provas de conhecimento não interativas da chave privada.

Autenticação por senha sem enviar a senha. Verificação de idade sem revelar a data de nascimento. Provas de intervalo (seu salário está dentro de um intervalo) sem revelar o salário. Cadeia de blocos: prove que conhece uma transação válida sem revelar a transação.

Conhecimento zero perfeito: a saída do simulador é idêntica à transcrição real. ZK estatístico: indistinguível, exceto com probabilidade desprezível. ZK computacional: indistinguível para verificadores de tempo polinomial. Garantias mais fracas = provas mais eficientes.

A caverna é um protocolo de três movimentos: compromisso → desafio → resposta. Formalmente, chama-se protocolo Sigma. A maioria das provas ZKP práticas (Schnorr, Pedersen, Fiat-Shamir) são protocolos Sigma ou composições deles. O nome vem do formato Σ do diagrama do fluxo de mensagens.

As provas ZKP demonstram conhecimento de um segredo sem revelá-lo. Três propriedades: completude, solidez e conhecimento zero. A caverna de Ali Baba ilustra uma ZKP interativa. A seguir: protocolos Sigma e identificação de Schnorr.