zk-SNARKs: argumentos sucintos não interativos

Uma prova SNARK de conhecimento zero (argumento sucinto não interativo de conhecimento zero) é uma prova que: (1) oferece conhecimento zero, (2) é sucinta (prova minúscula, verificação rápida independentemente do tamanho da computação), (3) é não interativa (uma única sequência de caracteres de prova).

Os protocolos Sigma funcionam para afirmações simples (conhecimento de um logaritmo discreto). Para computações complexas — «executei esta função corretamente com entradas privadas» — precisamos de um sistema de provas de uso geral. Os SNARK demonstram computações arbitrárias em tempo de verificação O(1).

A computação é primeiro expressa como um circuito aritmético: um grafo acíclico direcionado de portas de adição e multiplicação sobre um corpo finito. Exemplo: demonstrar que se conhece x tal que x^3 + x + 5 = 35 sem revelar x=3. O circuito tem aproximadamente 5 portas.

Um circuito aritmético é convertido em R1CS: um conjunto de restrições (A*z)*(B*z) = C*z, onde z é um vetor com todos os valores dos fios. Cada porta de multiplicação se transforma em uma restrição. O provador precisa encontrar z que satisfaça todas as restrições sem revelar os fios privados.

R1CS é convertido em um QAP: polinômios A(x), B(x), C(x) tais que A(x)*B(x)-C(x) é divisível por um polinômio-alvo t(x) se e somente se as restrições forem satisfeitas. O provador demonstra conhecer um quociente polinomial H(x) sem revelar o testemunho.

Groth16 (2016) é o SNARK geral mais eficiente. Após uma configuração confiável (geração da CRS), o provador produz uma prova composta por 3 elementos de grupo (~192 octetos para BLS12-381). Verificação: 3 operações de emparelhamento. A prova tem tamanho constante, independentemente do tamanho do circuito.

Groth16 exige uma configuração confiável por circuito: amostrar o resíduo tóxico (um segredo aleatório), calcular a cadeia de referência comum (CRS) e então destruir o resíduo tóxico. Se o resíduo sobreviver, um adversário poderá forjar provas. Cerimônias multiparticipantes (Powers of Tau) distribuem a confiança.

PLONK (2019) usa uma configuração confiável universal: uma única cerimônia funciona para todos os circuitos até um limite de tamanho. Não é necessária uma configuração por circuito. Compensação: provas ligeiramente maiores que as do Groth16. Usado em implementações de zkEVM (Polygon Hermez, zkSync Era).

As provas STARK (argumentos escaláveis e transparentes de conhecimento) não exigem uma configuração confiável e usam funções de resumo criptográfico (seguras contra ataques quânticos). Compensação: provas maiores (dezenas de KB contra 200 octetos). Usadas na StarkWare/StarkNet e na linguagem Cairo. As provas SNARK são menores; as provas STARK são resistentes a ataques quânticos.

Groth16 usa emparelhamentos bilineares: e: G1 × G2 → GT, onde e(a*P, b*Q) = e(P,Q)^{ab}. Isso permite verificar identidades polinomiais no expoente sem revelar os valores. A curva BLS12-381 é otimizada para emparelhamentos eficientes do Groth16.

Tempo de geração de provas do Groth16 para um circuito com 10^6 portas: aproximadamente 10 segundos em uma CPU moderna. Verificação: aproximadamente 1 ms. Essa assimetria é intencional: o provador (que realizou a computação pesada) trabalha; o verificador (nó da cadeia de blocos) quase não trabalha.

Qual é a principal desvantagem do Groth16 em comparação com o PLONK?

As provas SNARK de conhecimento zero demonstram computações arbitrárias com provas de tamanho constante. Fluxo: computação → circuito aritmético → R1CS → QAP → prova SNARK. Groth16 é o mais eficiente (configuração confiável por circuito); PLONK usa configuração universal. A seguir: aplicações de ZKP na cadeia de blocos.