Provas recursivas

Em uma prova recursiva, uma prova atesta a validade de outra ou de outras. Ela é implementada codificando o algoritmo de verificação do sistema, o verifier circuit, dentro do próprio circuito que se demonstra. A cada passo, gera-se uma nova prova que certifica que o último lote de computação está correto e que a prova anterior era válida. O resultado é uma única prova final de tamanho constante que respalda uma cadeia de computação tão longa quanto se queira. Conceitos associados são a computação verificável incremental (IVC) e os dados que carregam a própria prova (proof-carrying data).

É a base da escalabilidade massiva e da agregação em rollups: permite comprimir milhares de transações ou muitas provas individuais em uma só, verificável on-chain a custo fixo, e manter um estado de blockchain de tamanho constante. As técnicas modernas de acumulação ou folding adiam a parte custosa da verificação, a abertura do compromisso polinomial, e a acumulam em uma única operação ao final, o que barateia a recursão.

Os marcos ilustram isso. Halo (Bowe, Grigg e Hopwood, 2019) foi o primeiro exemplo prático de composição recursiva sem trusted setup. Nova (Kothapalli, Setty e Tzialla, CRYPTO 2022) introduz IVC por meio de folding com o menor verifier circuit da literatura. O Halo 2, da Zcash, implementa composição recursiva sem trusted setup, e a Mina Protocol mantém uma cadeia de tamanho constante de cerca de 22 KB graças à recursão por meio de seu sistema Pickles.