zkCraft: Prompt-Guided LLM as a Zero-Shot Mutation Pattern Oracle for TCCT-Powered ZK Fuzzing

1. O Problema

Os circuitos de Conhecimento Zero (Zero-Knowledge - ZK) são fundamentais para sistemas privados e escaláveis, mas sua implementação correta é extremamente difícil devido ao acoplamento estrito entre o gerador de testemunhas (que calcula valores privados) e o sistema de restrições (usado para verificação de prova).

Quando essa alinhamento falha, surgem duas classes principais de falhas com consequências de segurança graves:

1. Falhas Sub-constraintadas (Under-constrained): O sistema de restrições aceita execuções que nenhum testemunho válido poderia produzir (permitindo, por exemplo, forjar identidades ou burlar regras de negócio).
2. Falhas Super-constraintadas (Over-constrained): Execuições válidas que produzem testemunhos corretos são rejeitadas pelas restrições.

As abordagens existentes apresentam limitações:

• Detectores Estáticos: Frequentemente perdem discrepâncias semânticas que só aparecem durante a geração de testemunhas.
• Verificação Formal/SMT: Não escalam bem para circuitos grandes e lutam com o espaço de busca combinatório de edições de programa e atribuições de entrada.
• Fuzzing Dinâmico: Depende de chamadas caras a solucionadores (solvers) e mutações não guiadas que geram muitos candidatos de baixo valor.
• LLMs (Modelos de Linguagem): Podem gerar padrões de teste ricos semanticamente, mas geralmente estão desconectados da busca baseada em provas, gerando propostas caras de validar ou muitos falsos positivos.

O zkCraft visa preencher essa lacuna, integrando localização algébrica, provas de violação sucintas e mutação guiada por LLMs de forma determinística.

---

2. Metodologia

O zkCraft é um pipeline nativo de ZK que transforma a busca por pequenas edições vulneráveis em uma única declaração de existência algébrica, certificada por uma prova interativa. O processo é dividido em três estágios principais:

A. Estágio 1: Extração de Assinatura Esparsa (Slicing)

• O sistema analisa o circuito R1CS (Rank-1 Constraint System) e calcula diagnósticos por linha (restrição).
• Define dois contadores para cada linha: $\kappa_w$ (interseção com variáveis de testemunha) e $\kappa_c$ (interseção com termos constantes/públicos).
• Gera uma "impressão digital" (fingerprint) compacta e um escore de prioridade ($s_i$) para selecionar um conjunto limitado de linhas candidatas ($R_{cand}$) para mutação, reduzindo o espaço de busca.

B. Estágio 2: Comprometimento Row-Vortex e Violation IOP (Nativo ZK)

Esta é a inovação central. Em vez de iterar chamadas de solucionadores (SMT/SAT), o zkCraft:

1. Row-Vortex Polynomial: Codifica a seleção de linhas candidatas e os constantes de substituição em um polinômio bivariado $R(X, Y)$.
2. Comprometimento: O provador compromete este polinômio usando um esquema de comprometimento polinomial eficiente (ex: HyperPlonk+ ou BaseFold).
3. Violation IOP (Interactive Oracle Proof): O provador executa um protocolo de soma-verificação (Sum-Check) para provar a existência de um conjunto de edições e uma testemunha $w'$ tal que:
   • As restrições editadas são satisfeitas ($F_{\delta,c}(w') = 0$).
   • A saída pública difere da original ($y' \neq y$).
4. Resultado: O resultado é uma prova sucinta ($\pi$) que atesta a existência da vulnerabilidade.

C. Estágio 3: Síntese Determinística e Extração

• Proof-as-Counterexample: A prova aceita não apenas certifica o bug, mas permite a recuperação determinística da testemunha concreta e das edições específicas.
• O verificador (ou um extrator) reconstrói o vetor de seleção e os constantes de substituição a partir das aberturas do comprometimento.
• O sistema sintetiza o programa mutado $P'$ e gera o contra-exemplo concreto $(x', z', y')$ sem necessidade de reexecução completa do TCCT (Trace-Constraint Consistency Test) para verificação, pois a prova já garante a aceitação.

D. Oráculos LLM (Aceleradores Opcionais)

• O zkCraft utiliza LLMs como oráculos de templates de mutação zero-shot.
• O modelo não participa da resolução de restrições. Ele recebe prompts determinísticos para sugerir mutações no lado direito (RHS) de atribuições fracas (ex: substituir por 0, $q-1$, ou constantes pequenas) e heurísticas de amostragem de entrada.
• Isso direciona a busca para casos de borda sem introduzir não-determinismo nas provas de segurança.

---

3. Principais Contribuições

1. Framework Nativo ZK de Busca: Mapeia a busca por edições vulneráveis para uma única declaração algébrica de existência, certificada por uma Violation IOP, eliminando a necessidade de múltiplas chamadas a solucionadores.
2. Comprometimento Row-Vortex: Uma nova estrutura de polinômio bivariado que compacta a seleção de linhas e parâmetros de substituição, permitindo que uma única prova certifique a existência de múltiplas edições potenciais.
3. Interface LLM Determinística: Uso de LLMs como geradores de templates de mutação (não como solucionadores), mantendo a auditabilidade e a segurança algébrica do sistema.
4. Proof-as-Counterexample: A prova gerada serve diretamente como um certificado de vulnerabilidade auditável, permitindo a recuperação imediata do contra-exemplo concreto para o desenvolvedor.
5. Implementação Prática: Técnicas de fingerprinting por linha, heurísticas de pontuação e síntese em campos finitos para recuperação de substituições concretas.

---

4. Resultados Experimentais

O zkCraft foi avaliado em 452 suites de testes reais de Circom, cobrindo circuitos de pequeno a muito grande porte.

• Eficácia de Detecção:
  • Detectou 88 bugs únicos no conjunto total de benchmarks, superando ferramentas de estado da arte como ZKFUZZ, ZKAP, Circomspect e Picus.
  • Alcançou 100% de precisão (Precision) com zero falsos positivos em todos os tamanhos de circuito testados.
  • Identificou bugs previamente desconhecidos em projetos de produção, incluindo erros de primitivas incorretas, falsificação de identidade e cálculos de recompensa errôneos.
• Desempenho e Velocidade:
  • Convergência Rápida: O zkCraft encontrou a maioria dos bugs detectáveis dentro de 100 segundos, enquanto métodos baseados em fuzzing não guiado ou SMT puro levam ordens de magnitude mais tempo.
  • Redução de Custo: Substituiu milhares de chamadas de solucionador por uma única prova IOP, reduzindo drasticamente o tempo de execução.
• Tamanho da Prova:
  • Utilizando backends como HyperPlonk+, o tamanho da prova permanece constante em 96 bytes, independentemente do número de restrições (dentro de certos limites de grau), enquanto o tempo do provador cresce sub-linearmente.
• Análise de Ablação:
  • A remoção de componentes-chave (como Row-Vortex, Violation IOP ou oráculos LLM) resultou em lentidão significativa (até 100x) ou perda de bugs, validando a importância de cada módulo.

---

5. Significado e Impacto

O zkCraft representa um avanço significativo na segurança de circuitos ZK ao pontejar a verificação formal e a depuração automatizada.

• Escalabilidade: Ao substituir a busca combinatória exaustiva por provas criptográficas sucintas, torna viável a verificação de circuitos grandes e complexos que antes eram intratáveis para ferramentas baseadas em SMT.
• Auditabilidade: A capacidade de extrair um contra-exemplo concreto diretamente de uma prova criptográfica oferece um nível de confiança e transparência superior, facilitando a triagem e correção por desenvolvedores.
• Segurança Prática: A detecção de bugs sutis (sub e super-constraintados) em projetos reais de produção demonstra que o framework pode prevenir vulnerabilidades críticas antes da implantação.
• Futuro: O trabalho estabelece um novo paradigma para o desenvolvimento de ZK, onde a geração de testes e a verificação de bugs são tratadas como problemas de prova de conhecimento zero, integrando IA (LLMs) de forma segura e determinística ao ciclo de vida de desenvolvimento.

Em resumo, o zkCraft oferece um caminho escalável e robusto para o desenvolvimento de circuitos ZK livres de erros, combinando a precisão da álgebra com a inteligência heurística dos LLMs.