Provas de conhecimento zero explicadas além das criptos

Ideia central

As provas de conhecimento zero permitem que um provador convença um verificador de que conhece a solução de um problema, sem revelar a solução. O texto apresenta a ideia fora do contexto de criptomoedas, usando como exemplo a 3-coloração de um grafo: o provador afirma possuir uma atribuição de até três cores na qual vértices ligados por uma aresta têm cores diferentes, mas não precisa mostrar essa atribuição.

O problema é difícil de resolver em geral, enquanto a verificação de uma solução é rápida, linear no número de arestas. A construção se baseia em um protocolo interativo originalmente descrito por Goldreich, Micali e Widgerson. Em cada rodada, o provador embaralha os nomes das três cores, coloca a cor de cada vértice em uma “caixa trancada” e envia ao verificador apenas valores que escondem seu conteúdo. O verificador escolhe aleatoriamente uma aresta e pede as informações correspondentes aos dois vértices. O provador revela essas informações, e o verificador confirma tanto que elas correspondem aos valores enviados inicialmente quanto que as duas cores são diferentes.

Como o ocultamento funciona

O texto ilustra a ideia com código em Python. Uma função permuta as cores sem alterar a validade da coloração. Depois, cada cor é combinada com um nonce, um dado aleatório específico do vértice, e o conjunto é transformado por uma função hash. O nonce é necessário porque, sem ele, vértices com a mesma cor produziriam hashes iguais, permitindo ao verificador descobrir a estrutura da coloração mesmo sem conhecer os nomes das cores.

O código usa as funções padrão da biblioteca Python apenas por brevidade. O texto ressalta que, em uma implementação mais apropriada, seria melhor usar uma função hash criptográfica, como SHA-256, e fontes de aleatoriedade mais adequadas, como secrets.token_hex(); também menciona a possibilidade de usar hmac. A demonstração separa as ações do provador e do verificador e, depois, leva essa separação a uma arquitetura com servidor e cliente, para reduzir o risco de vazamento acidental de dados entre os lados.

Probabilidade e extensões

Uma única rodada não basta para dar muita confiança: se o provador estiver mentindo, ele pode evitar revelar justamente uma aresta problemática, com probabilidade relacionada ao número total de arestas. Por isso, o protocolo repete a interação com novas permutações e novos valores aleatórios. Conforme o artigo citado, após m² rodadas, a probabilidade de o verificador aceitar uma afirmação falsa é limitada superiormente por (1 - m⁻¹)^(m²), em que m é o número de arestas. No exemplo com 1.000 arestas, o texto calcula cerca de 1% de possibilidade de fraude após 4.600 rodadas, 0,0045% após 10.000 e uma probabilidade muito baixa após 1.000.000 de rodadas.

A mesma estrutura pode ser adaptada a outros problemas NP-completos. Para um Sudoku, por exemplo, o provador embaralharia os dígitos e revelaria aleatoriamente linhas, colunas ou blocos, em vez de cores e arestas. Reduções polinomiais também permitem converter soluções de outros problemas em uma instância de 3-coloração, embora essa conversão possa gerar grafos grandes demais para ser prática. Para provar conhecimento dos fatores de um número composto, o texto observa que técnicas mais sofisticadas seriam preferíveis. A conclusão é que os autores se interessaram sobretudo pela combinação de grafos, teoria da computação e computação em rede, e não pelos usos mais comuns das provas de conhecimento zero, como verificação de idade e criptomoedas.