Título original: "Cómo diseñar un esquema recursivo de prueba exquisito" Autor original: Lin Yanxi, CTO de Fox Tech, Meng Xuanji, científico jefe de Fox Tech Prólogo: Casi todos los problemas encontrados en las pistas zkRollup y zkEVM, entre ellos están; problemas esencialmente algorítmicos. La razón principal por la que a menudo se menciona la aceleración de hardware ZKP es que los algoritmos actuales son generalmente lentos. Para evitar caer en la vergonzosa situación de "el algoritmo no es suficiente, el hardware lo compensará", debemos resolver el problema algorítmicamente. Diseñar un esquema exquisito a prueba de recurrencia es la clave para resolver este problema. Con el desarrollo continuo de contratos inteligentes, están apareciendo cada vez más aplicaciones web3, y el volumen de transacciones de Layer1 tradicional como Ethereum está aumentando rápidamente y puede ocurrir congestión en cualquier momento. Cómo obtener una mayor eficiencia garantizando al mismo tiempo la seguridad proporcionada por la Capa 1 se ha convertido en un problema urgente que debe resolverse. Para Ethereum, zkRollup utiliza el algoritmo de prueba de conocimiento cero como componente subyacente para mover cálculos costosos que originalmente deben realizarse en la Capa 1 fuera de la cadena y proporcionar prueba de la corrección de la ejecución a la cadena. El track incluye principalmente proyectos como StarkWare, zkSync, Scroll y Fox Tech. De hecho, en el diseño de zkRollup, existen requisitos de eficiencia muy altos: se espera que el valor de prueba enviado sea lo suficientemente pequeño para reducir la carga de cálculo de Layer1. Para obtener una longitud de prueba suficientemente pequeña, varios proyectos de zkRollup están mejorando los algoritmos y los diseños de arquitectura. Por ejemplo, Fox ha desarrollado su propio algoritmo de prueba FOAKS basado en el último algoritmo de prueba de conocimiento cero para obtener un tiempo y una duración de prueba óptimos. Además, en la etapa de verificación de pruebas, el método más trivial es generar pruebas linealmente y verificarlas secuencialmente. Para mejorar la eficiencia, lo primero que todo el mundo piensa es en empaquetar varias pruebas en una sola prueba, lo que comúnmente se denomina agregación de pruebas (Proof Aggregation). Intuitivamente hablando, verificar las pruebas generadas por zkEVM es un proceso lineal, y el verificador debe verificar cada valor de prueba generado por turno. Sin embargo, la eficiencia de este método de verificación es relativamente baja y la sobrecarga de comunicación es relativamente grande. Para el escenario zkRollup, una mayor sobrecarga del lado del verificador significa más cálculos de la capa 1, lo que también conducirá a tarifas de gas más altas.Comencemos con un ejemplo: Alice quiere demostrarle al mundo que fue a Fox Park del 1 al 7 de este mes. Para ello, podrá hacerse una foto en el parque con el periódico de ese día cada día del 1 al 7, y el paquete de estas 7 fotos se convertirá en una prueba. Figura 1: Esquema general de agregación de pruebas En el ejemplo anterior, poner 7 fotos directamente en un sobre es una agregación de pruebas en un sentido real, esto corresponde a conectar diferentes pruebas y verificarlas linealmente en secuencia, es decir, primero. Verifique la primera prueba, luego la segunda prueba y las pruebas posteriores. El problema es que este enfoque no cambiará el tamaño ni el tiempo de la prueba. Tiene el mismo efecto que probar y verificar una por una. Si desea lograr una compresión espacial de nivel logarítmico, debe utilizar la prueba recursiva (Proof Recursion) que se menciona a continuación. El esquema de prueba recursiva utilizado por Halo2 y STARK Para explicar mejor qué es una prueba recursiva, volvamos al ejemplo anterior. Las 7 fotos de Alice son en realidad 7 pruebas. Ahora considere fusionarlos, para que Alice pueda tomar la foto del No. 1, tomar la foto con el periódico del No. 2 en el No. 2 y tomar la foto del No. 2 y el periódico del No. 3 en el No. 3. . foto. Por analogía, Alice tomó la última foto del día 7 con la foto del día 6 y el periódico del día 7. Cuando otros amigos vean la última foto del día 7, podrán comprobar que entre el 1 y el 7 Alice fueron todas al parque. . Como puede ver, las siete fotografías de prueba anteriores se han comprimido en una sola. Una técnica clave en este proceso son las "fotos que contienen fotos", lo que equivale a anidar recursivamente fotos anteriores en fotos posteriores. Esto es diferente a juntar muchas fotografías y luego tomar una sola. El truco de prueba recursiva de zkRollup puede reducir significativamente el tamaño de la prueba. Específicamente, cada transacción generará una prueba. Suponemos que el circuito de cálculo de la transacción original es C0, P0 es la prueba de corrección de C0, V0 es el proceso de cálculo para verificar P0 y el probador (Prover) también convierte V0 en el correspondiente. El circuito se denota como C0'. En este momento, para el proceso de cálculo de prueba C1 de otra transacción, los circuitos de C0' y C1 se pueden fusionar. De esta manera, una vez que se verifica la corrección de la prueba P1 del circuito fusionado, es equivalente a verificar los dos anteriores en. al mismo tiempo. Se logra la corrección de una transacción, es decir, se logra la compresión.Mirando hacia atrás en el proceso anterior, podemos encontrar que el principio de compresión es convertir el proceso de verificación y prueba en un circuito y luego generar una "prueba de prueba". Entonces, desde esta perspectiva, es una operación que puede realizarse. ser continuamente recursivo, por lo que también se denomina prueba recursiva. Figura 2: El esquema de prueba recursivo utilizado por Halo2 y Stark El esquema de recursión de prueba utilizado por Halo2 y STARK puede generar pruebas en paralelo y fusionar múltiples pruebas, de modo que se pueda verificar la exactitud de múltiples ejecuciones de transacciones mientras se verifica un valor de prueba, que. Puede comprimir la sobrecarga de cálculo y mejorar en gran medida la eficiencia del sistema. Sin embargo, dicha optimización aún se mantiene en un nivel superior al algoritmo de prueba de conocimiento cero específico. Para mejorar aún más la eficiencia, necesitamos innovación y optimización de nivel inferior. El algoritmo FOAKS diseñado por Fox lo hace aplicando la idea recursiva dentro de una prueba. Llegué a este punto. El esquema de recursión probado utilizado por FOAKS es un proyecto zkRollup basado en zkEVM en Fox Tech. En su sistema de prueba, también utiliza la técnica de prueba recursiva, pero la connotación es diferente del método recursivo mencionado anteriormente. La principal diferencia es que Fox usa la idea de recursividad dentro de una prueba. Para expresar la idea central de la prueba recursiva utilizada por Fox, que es reducir continuamente el problema a demostrar hasta que el problema reducido sea lo suficientemente simple, necesitamos dar otro ejemplo. En el ejemplo anterior, Alice tomó una foto para demostrar que fue a Fox Park en un día determinado, por lo que Bob hizo diferentes sugerencias. Creía que el problema de demostrar que Alice fue al parque se puede reducir a demostrar que el móvil de Alice. El teléfono fue al parque. Probar este asunto se puede reducir a demostrar que el teléfono móvil de Alice está ubicado dentro del alcance del parque. Entonces, para demostrar que Alice ha estado en el parque, solo necesita enviar una ubicación usando su teléfono mientras estaba en el parque. De esta manera, el tamaño de la prueba cambia de la foto original (datos de muy altas dimensiones) a datos tridimensionales (latitud, longitud y hora), lo que ahorra costos de manera efectiva. Este ejemplo no es del todo apropiado, porque algunas personas pueden cuestionar que el hecho de que el teléfono móvil de Alice haya estado en Fox Park no significa que Alice misma haya estado allí, pero en situaciones reales, este proceso de reducción es matemáticamente riguroso.Específicamente, el uso de la prueba recursiva de Fox es recursividad a nivel de circuito. Al realizar una prueba de conocimiento cero, escribiremos el problema que se va a probar en un circuito y luego calcularemos algunas ecuaciones que deben satisfacerse a través del circuito. En lugar de demostrar que estas ecuaciones se satisfacen, las escribimos nuevamente en circuitos, y así sucesivamente, hasta que finalmente la ecuación para demostrar que se satisfacen se vuelve lo suficientemente simple como para que podamos probarla fácilmente y directamente. De este proceso podemos ver que hacerlo se acerca más al significado de "recursión". Vale la pena mencionar que no todos los algoritmos pueden utilizar esta técnica recursiva. Se supone que cada recursividad convertirá la prueba con complejidad O (n) en una prueba de O (f (n)) y el cálculo del proceso recursivo en sí. La complejidad es O(g(n)). Después de una recursión, la complejidad computacional total se convierte en O1(n)=O(f(n))+O(g(n)). )=O(f(f(n)))+O(g(n))+O(g(f(n))), después de tres veces es O3(n)=O(f(f(f( n)) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),..., y así sucesivamente. Por lo tanto, sólo cuando f y g son dos funciones correspondientes a características del algoritmo que satisfacen Ok(n) para un cierto k Figura 3: El esquema de prueba recursivo utilizado por ZK-FOAKS Conclusión La complejidad de la prueba siempre ha sido la más importante. En aplicaciones de prueba de conocimiento cero, una de las claves es que la complejidad de la prueba se volverá cada vez más importante a medida que las cosas a probar se vuelvan cada vez más complejas, especialmente en escenarios de aplicaciones ZK gigantes como zkEVM, la complejidad de la prueba tendrá. un gran impacto en el rendimiento y el rendimiento del producto. La experiencia del usuario tiene un impacto decisivo. Entre los muchos métodos para reducir la complejidad de la prueba final, la optimización del algoritmo central es el más importante. Fox diseñó un ingenioso esquema de prueba recursivo basado en los algoritmos más avanzados y utilizó esta tecnología para crear una solución. más adecuado para zkEVM Se espera que el algoritmo ZK-FOAKS se convierta en el líder en rendimiento en el mundo zkRollup. Referencias https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 Este artículo proviene de un envío y no representa las opiniones de BlockBeats