Provas de conhecimento zero: é como mágica, mas vou explicar

Suponha que Peggy precise provar a Victor que possui um segredo sem revelá-lo. Ela conseguirá fazer isso de uma forma que convença Victor de que ela realmente conhece o segredo? Esta é a questão central de um dos processos criptográficos mais poderosos que podemos empregar em sistemas de identidade: provas de conhecimento zero (ZKPs) .

Suponha, por exemplo, que Peggy tenha uma carteira de motorista digital e queira provar a Victor, o barman, que ela tem mais de 21 anos sem apenas entregar sua carteira de motorista ou mesmo mostrar a ele sua data de nascimento. Os ZKPs permitem que Peggy prove que sua carteira de motorista diz que ela tem pelo menos 21 anos de uma forma que convence Victor sem que Peggy tenha que revelar mais nada (ou seja, não há excesso de conhecimento).

Este problema foi explorado pela primeira vez pelos pesquisadores do MIT Shafi Goldwasser, Silvio Micali e Charles Rackoff na década de 1980 como forma de combater o vazamento de informações. O objetivo é reduzir a quantidade de informações extras que o verificador, Victor, pode obter sobre a provadora, Peggy.

Uma forma de entender como funcionam os ZKPs é a história da Caverna do Alibaba, publicada pela primeira vez pelos criptógrafos Quisquater, Guillou e Berson1. O diagrama a seguir fornece uma ilustração.

A Caverna do Alibaba tem duas passagens, denominadas A e B, que separam uma única passagem conectada à entrada. Peggy possui um código secreto que lhe permite destrancar uma porta que conecta A e B. Victor quer comprar o código, mas não pagará até ter certeza de que Peggy sabe disso. Peggy não vai compartilhar com Victor até que ele pague.

O algoritmo para Peggy provar que conhece o código é o seguinte:

• Victor fica do lado de fora da caverna enquanto Peggy entra e seleciona uma das passagens. Victor não tem permissão para ver o caminho que Peggy segue.
• Victor entra na caverna e chama "A" ou "B" aleatoriamente.
• Peggy emerge da passagem correta porque ela pode facilmente destrancar a porta, independentemente da escolha que fez ao entrar.
• É claro que Peggy poderia ter tido sorte e acertado, então Peggy e Victor repetem o experimento muitas vezes.

Se Peggy sempre puder voltar por qualquer passagem que Victor escolher, então há uma probabilidade crescente de que Peggy realmente conheça o código. Depois de 20 tentativas, há menos de uma chance em um milhão de que Peggy esteja simplesmente adivinhando qual letra Victor irá chamar. Isto constitui uma prova probabilística de que Peggy conhece o segredo.

Esse algoritmo não apenas permite que Peggy convença Victor de que conhece o código, mas também faz isso de uma forma que garante que Victor não consiga convencer mais ninguém de que Peggy conhece o código. Suponha que Victor registre toda a transação. A única coisa que um observador vê é Victor gritando cartas e Peggy emergindo do túnel direito. O observador não pode ter certeza de que Victor e Peggy não concordaram antecipadamente com uma sequência de cartas para enganar os observadores.

Assim, embora Peggy não possa negar a Victor que conhece o segredo, ela pode negar que conhece o segredo a terceiros. Isso garante que tudo o que ela provar a Victor permaneça entre eles e Victor não possa vazar – pelo menos de uma forma criptográfica que prove que veio de Peggy. Peggy mantém o controle de seu segredo e do fato de saber disso.

Quando dizemos “conhecimento zero” e falamos que Victor não aprendeu nada além da proposição em questão, isso não é perfeitamente verdade. Na caverna do Alibaba, Peggy prova sem saber que conhece o segredo. Mas há muitas outras coisas que Victor aprende sobre Peggy e as quais os ZKPs nada podem fazer. Por exemplo, Victor sabe que Peggy pode ouvi-lo, fala a língua dele, anda e é cooperativa. Ele também pode aprender coisas sobre a caverna, como aproximadamente quanto tempo leva para destrancar a porta. Peggy descobre coisas semelhantes sobre Victor. Portanto, a realidade é que a prova é um conhecimento aproximadamente zero e não um conhecimento perfeitamente zero.

ZKP Sistemas

O exemplo da Caverna do Alibaba é um uso muito específico de ZKPs, o que é chamado de prova de conhecimento de conhecimento zero . Peggy está provando que sabe (ou possui alguma coisa). De modo mais geral, Peggy pode querer provar muitos fatos para Victor. Estes podem incluir frases proposicionais ou mesmo valores. Os ZKPs também podem fazer isso.

Para entender como podemos provar proposições com conhecimento zero, considere um exemplo diferente, às vezes chamado de Problema Socialista do Milionário . Suponha que Peggy e Victor queiram saber se estão recebendo um salário justo. Especificamente, eles querem saber se recebem o mesmo valor, mas não querem divulgar sua taxa horária específica entre si ou mesmo com um terceiro de confiança. Neste caso, Peggy não está provando que conhece um segredo, mas sim uma proposição de igualdade (ou desigualdade).

Para simplificar, suponha que Peggy e Victor recebam US$ 10, US$ 20, US$ 30 ou US$ 40 por hora.

O algoritmo funciona assim:

• Peggy compra quatro cofres e os rotula como US$ 10, US$ 20, US$ 30 e US$ 40.
• Ela joga fora as chaves de todas as caixas, exceto aquela etiquetada com seu salário.
• Peggy dá todas as caixas trancadas para Victor, que em particular coloca um pedaço de papel com um "+" na fenda no topo da caixa etiquetada com seu salário. Ele coloca um recibo com um “-” em todas as outras caixas.
• Victor devolve as caixas para Peggy, que usa sua chave em particular para abrir a caixa com seu salário.
• Se ela encontrar um "+", eles ganham a mesma quantia. Caso contrário, eles ganham um valor diferente. Ela pode usar isso para provar o fato para Victor.

Isto é chamado de transferência alheia e prova que a proposição VictorSalary = PeggySalary é verdadeira ou falsa em conhecimento zero (ou seja, sem revelar qualquer outra informação).

Para que isso funcione, Peggy e Victor devem confiar que o outro será próximo e declarar seu salário real. Victor precisa confiar que Peggy jogará fora as outras três chaves. Peggy deve confiar que Victor colocará apenas um recibo com um “+” nas caixas.

Assim como os certificados digitais precisam de uma PKI para estabelecer confiança além do que seria possível apenas com certificados autoemitidos, os ZKPs são mais poderosos em um sistema que permite que Peggy e Victor provem fatos a partir de coisas que outras pessoas dizem sobre eles, não apenas o que dizem sobre eles. eles mesmos. Por exemplo, em vez de Peggy e Victor autodeclararem seu salário, suponha que eles pudessem confiar em um documento assinado pelo departamento de RH para fazer sua afirmação, de modo que ambos saibam que o outro está declarando seu verdadeiro salário. As Credenciais Verificáveis fornecem um sistema para usar ZKPs para provar muitos fatos diferentes, isoladamente ou em conjunto, de forma a dar confiança no método e nos dados.

ZKPs não interativos

Nos exemplos anteriores, Peggy conseguiu provar coisas a Victor por meio de uma série de interações. Para que os ZKPs sejam práticos, as interações entre o provador e o verificador devem ser mínimas. Felizmente, uma técnica chamada SNARK permite provas não interativas de conhecimento zero.

SNARKs têm as seguintes propriedades (de onde derivam seu nome):

• Sucinto: os tamanhos das mensagens são pequenos em comparação com o comprimento da prova real.
• Não interativo : além de alguma configuração, o provador envia apenas uma mensagem ao verificador.
• ARgumentos: este é realmente um argumento de que algo está correto, não uma prova como a entendemos matematicamente. Especificamente, o provador teoricamente poderia provar declarações falsas com poder computacional suficiente. Portanto, SNARKs são "computacionalmente sólidos" em vez de "perfeitamente sólidos".
• do Conhecimento: o provador conhece o fato em questão.

Você normalmente verá “zk” (para conhecimento zero) pregado na frente para indicar que durante esse processo, o verificador não aprende nada além dos fatos que estão sendo provados.

A matemática subjacente aos zkSNARKs envolve computação homomórfica sobre polinômios de alto grau. Mas podemos entender como os zkSNARKs funcionam sem conhecer a matemática subjacente que garante que eles sejam sólidos. Se você quiser mais detalhes sobre matemática, recomendo "zkSNARKs in a Nutshell" de Christian Reitwiessner .

Como um exemplo simples, suponha que Victor receba um hash sha256 , H , de algum valor. Peggy quer provar que conhece um valor s tal que sha265(s) == H sem revelar s a Victor. Podemos definir uma função C que captura o relacionamento:

 C(x, w) = ( sha256(w) == x )

Portanto, C(H, s) == true , enquanto outros valores para w retornarão false .

Calcular um zkSNARK requer três funções G , P e V . G é o gerador de chaves que usa um parâmetro secreto chamado lambda e a função C e gera duas chaves públicas, a chave de prova pk e a chave de verificação vk . Eles só precisam ser gerados uma vez para uma determinada função C . O parâmetro lambda deve ser destruído após esta etapa, pois não é mais necessário e qualquer pessoa que o possua pode gerar provas falsas .

A função provadora P toma como entrada a chave de prova pk , uma entrada pública x e uma testemunha privada (secreta) w . O resultado da execução de P(pk,x,w) é uma prova, prf , de que o provador conhece um valor para w que satisfaz C .

A função verificadora V calcula V(vk, x, prf) que é verdadeiro se a prova prf estiver correta e falso caso contrário.

Voltando a Peggy e Victor, Victor escolhe uma função C representando o que ele quer que Peggy prove, cria um número aleatório lambda e executa G para gerar as chaves de prova e verificação:

 (pk, vk) = G(C, lambda)

Peggy não deve aprender o valor de lambda . Victor compartilha C , pk e vk com Peggy.

Peggy quer provar que conhece o valor s que satisfaz C para x = H . Ela executa a função de prova P usando estes valores como entradas:

 prf = P(pk, H, s)

Peggy apresenta a prova prf Victor, que executa a função de verificação:

 V(vk, H, prf)

Se o resultado for verdadeiro, então o Victor pode ter certeza de que Peggy conhece o valor s .

A função C não precisa ser limitada a um hash como fizemos neste exemplo. Dentro dos limites da matemática subjacente, C pode ser bastante complicado e envolver qualquer número de valores que Victor gostaria que Peggy provasse, todos de uma vez.

Este artigo é um trecho do meu livro Learning Digital Identity , publicado pela O'Reilly Media.

Notas

1. Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). Como explicar protocolos de conhecimento zero para seus filhos (PDF). Avanços na criptologia – CRYPTO '89: Procedimentos. Notas de aula em Ciência da Computação. 435. pp. doi:10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.