Aprimoramento da Interação do Usuário em Provas de Conhecimento Zero com Rust e Bellman

Bem-vindo de volta à nossa exploração em curso de provas de conhecimento zero usando a linguagem de programação Rust e a biblioteca Bellman. Em nosso artigo anterior, mergulhamos no fascinante mundo dos zk-SNARKs e demonstramos como eles podem ser usados para verificar a exatidão de uma solução de Sudoku sem revelar a solução em si. No entanto, leitores astutos e entusiastas da criptografia apontaram um aspecto crítico da interação com o usuário que estava faltando. Vamos corrigir isso e aprimorar nosso solucionador de Sudoku com interação real com o usuário.

Falhas na Implementação Inicial

Em nossa incursão inicial, o exemplo se concentrou na verificação de um quadro secreto de Sudoku em relação a uma solução conhecida dentro das restrições de uma prova de conhecimento zero. Embora isso tenha demonstrado o poder e a privacidade dos zk-SNARKs, faltou um elemento essencial de qualquer jogo de Sudoku: a interação do usuário. Normalmente, um usuário (ou verificador em termos criptográficos) sugere valores para as células vazias e o jogo (ou provador) confirma se esses valores estão corretos. Nosso exemplo inicial não permitia essa interação, que é crucial para uma aplicação mais realista e prática dos zk-SNARKs em jogos de Sudoku.

Aprimorando a Interação do Usuário

Para tornar nosso exemplo de Sudoku mais interativo e realista, atualizamos o programa para permitir que um verificador sugira valores para as células vazias do Sudoku. O verificador envia a solução proposta e o programa verifica sua correção usando a magia das provas de conhecimento zero, ao mesmo tempo que mantém a solução real oculta. Essa abordagem reflete muito mais a experiência real do Sudoku, em que a emoção está em resolver o problema, não apenas em verificar uma solução existente.

A Dinâmica da Prova Sem Conhecimento

No contexto das provas de conhecimento zero, especialmente os zk-SNARKs, o provador (que cria a prova) deve conhecer a solução que está comprovando; no entanto, ele não revela essa solução diretamente ao verificador. Isso pode parecer um pouco contraintuitivo quando falamos em melhorar a interação do usuário, especialmente quando os usuários propõem soluções para um jogo de Sudoku. Vamos esclarecer como um provador que conhece a solução pode validar as propostas dos usuários, como a solução real é "codificada" na prova e as implicações para quadros de Sudoku maiores.

Como o Provador Valida as Proposições

Na configuração típica do zk-SNARK para algo como um jogo de Sudoku, presume-se que o provador conheça a solução real do jogo. Esse conhecimento é necessário para construir a prova.

Quando os usuários (verificadores) sugerem valores para as células vazias no jogo de Sudoku, eles estão essencialmente propondo uma solução completa que acreditam estar correta. A prova em si é construída de forma que só será válida se a solução proposta estiver correta.

Codificando a Solução Real na Prova

A solução real é "codificada" na prova por meio da construção do circuito no zk-SNARK. Quando o provador gera a prova, ele está essencialmente provando que conhece uma solução (a solução real) que satisfaz as restrições estabelecidas no circuito (as regras do Sudoku, neste caso) sem revelar qual é essa solução.

Quando o verificador valida uma solução proposta, a prova inclui essencialmente verificações de cada célula em relação às restrições. Se a solução proposta satisfizer todas as restrições (o que significa que ela é igual à solução real de um jogo de Sudoku correto), a prova será válida. Caso contrário, o processo de verificação falhará.

Durante todo esse processo, a solução real nunca é revelada a ninguém, exceto ao provador. O verificador não aprende nada sobre a solução, exceto se a solução proposta está correta.

A Solução Atualizada em Rust

Vamos detalhar a solução atualizada. O núcleo de nosso aprimoramento está na struct Sudoku e no método synthesize em nosso circuito. Agora incluímos a solução real e a solução proposta em nossa struct. Durante o processo de síntese, adicionamos restrições para verificar se a solução proposta corresponde à solução real para cada célula. O mais importante é que essa comparação é feita de uma forma que ainda não revela a solução real ao verificador.

Aqui está a implementação do Rust revisada:

// Struct do Sudoku atualizada para incluir a solução proposta
struct Sudoku {
   solution: Option<Vec<u32>>,        // A solução real do Sudoku
   proposed_solution: Option<Vec<u32>>, // A solução proposta pelo verificador/usuário
}

// Implementando o trait de circuito para o Sudoku
impl Circuit<Fr> for Sudoku {
   fn synthesize<CS: ConstraintSystem<Fr>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
       let mut grid = Vec::with_capacity(9);

       // ... [Configuração anterior do grid e outras restrições]
       // Restrições para verificar a solução proposta pelo usuário
       if let (Some(solution), Some(proposed_solution)) = (self.solution, self.proposed_solution) {
           for i in 0..9 {
               let actual_val = Fr::from(solution[i]);
               let proposed_val = Fr::from(proposed_solution[i]);

               // Assegura que o valor proposto seja igual ao valor real de cada célula
               cs.enforce(
                   || format!("match_{}", i),
                   |lc| lc + CS::one() * actual_val,
                   |lc| lc + CS::one(),
                   |lc| lc + CS::one() * proposed_val,
               );
           }
       }

       Ok(())
   }
}

Efeito no Tamanho da Prova com Quadros de Sudoku Maiores

À medida que o tamanho do quadro de Sudoku aumenta, por exemplo, de 3x3 para 1000x1000 ou até 1Mx1M, o número de restrições e variáveis no circuito aumenta linearmente com o número de células. Cada célula e as relações entre as células (linhas, colunas e regiões devem conter valores exclusivos) aumentam a complexidade do circuito.

Uma das vantagens dos zk-SNARKs é que o tamanho da prova permanece relativamente pequeno e constante, independentemente do tamanho do cálculo que está sendo provado. Entretanto, o tempo e os recursos computacionais necessários para gerar e verificar essas provas aumentarão com circuitos maiores e mais complexos.

Embora teoricamente possível, surgem limitações práticas com os quadros de Sudoku muito grandes. O tempo para construir o circuito, gerar a prova e, principalmente, a fase de configuração do CRS pode se tornar impraticável para tamanhos excessivamente grandes. O custo computacional tanto para o provador quanto para o verificador aumenta e a configuração inicial (configuração confiável ou sua versão descentralizada) torna-se mais complicada.

Conclusão

Ao aprimorar a interação do usuário para aplicativos baseados em zk-SNARK, é fundamental entender a mecânica de como as soluções são propostas, verificadas e codificadas nas provas. Embora os zk-SNARKs ofereçam recursos avançados para manter a privacidade e verificar a correção, a escalabilidade em termos de computação e recursos é uma questão importante, especialmente à medida que a complexidade do problema aumenta. A compreensão dessa dinâmica permite implementações mais eficazes e práticas de provas de conhecimento zero em aplicativos do mundo real.

Esse artigo foi escrito por Deep RnD e traduzido por Fátima Lima. O original pode ser lido aqui.