Pruebas recursivas

En una prueba recursiva, una prueba atestigua la validez de otra u otras. Se implementa codificando el algoritmo de verificación del sistema, el verifier circuit, dentro del propio circuito que se demuestra. En cada paso se genera una prueba nueva que certifica que el último lote de computación es correcto y que la prueba anterior era válida. El resultado es una única prueba final de tamaño constante que respalda una cadena de computación tan larga como se quiera. Conceptos asociados son la computación verificable incremental (IVC) y los datos que portan su prueba (proof-carrying data).

Es la base del escalado masivo y de la agregación en rollups: permite comprimir miles de transacciones o muchas pruebas individuales en una sola, verificable en cadena a coste fijo, y mantener un estado de blockchain de tamaño constante. Las técnicas modernas de acumulación o folding difieren la parte costosa de la verificación, la apertura del compromiso polinómico, y la acumulan en una sola operación al final, lo que abarata la recursión.

Los hitos lo ilustran. Halo (Bowe, Grigg y Hopwood, 2019) fue el primer ejemplo práctico de composición recursiva sin trusted setup. Nova (Kothapalli, Setty y Tzialla, CRYPTO 2022) introduce IVC mediante folding con el verifier circuit más pequeño de la literatura. Halo 2 de Zcash implementa composición recursiva sin trusted setup, y Mina Protocol mantiene una cadena de tamaño constante de unos 22 KB gracias a la recursión mediante su sistema Pickles.