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.
Top comments (0)