¿Cómo diseñar un mejor esquema de recursividad de prueba?
Casi todos los problemas encontrados en las pistas zkRollup y zkEVM son esencialmente problemas algorítmicos. La razón principal por la que se menciona con frecuencia la aceleración de hardware ZK-Proof es que los algoritmos actuales son generalmente lentos.
Para evitar caer en la vergonzosa situación de "el algoritmo no es suficiente, el hardware se utiliza para compensar", debemos resolver el problema desde la esencia del algoritmo. Diseñando una recursión exquisita a prueba de entrega El esquema 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 la Capa 1 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 a resolver.
Para Ethereum, zkRollup utiliza el algoritmo de prueba de conocimiento cero como componente subyacente para mover los costosos cálculos que originalmente debían 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 proyectos como StarkWare, zkSync, desplazamiento, y tecnología zorro.
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, lo que puede reducir la cantidad de cálculo de la Capa 1. Para obtener una longitud de prueba suficientemente pequeña, cada El proyecto zkRollup está mejorando el algoritmo y el diseño de la arquitectura. Por ejemplo, Fox ha desarrollado su algoritmo de prueba FOAKS en combinación con el último algoritmo de prueba de conocimiento cero para obtener el tiempo y la duración de prueba óptimos.
Además, en la etapa de verificación de pruebas, el medio 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 conoce como agregación de pruebas.
Intuitivamente hablando, verificar las pruebas generadas por zkEVM es un proceso lineal y el Verificador necesita 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 por parte del verificador significa más cálculos de Capa 1, lo que también generará tarifas de gas más altas.
Primero veamos un ejemplo: Alice quiere demostrarle al mundo que fue a Fox Park del 1 al 7 de este mes. Por eso, podrá hacerse una foto en el parque con el periódico del día cada día del 1 al 7, y estas siete fotos se convertirán en prueba.
Poner siete fotos directamente en un sobre en el ejemplo anterior es agregación de pruebas en un sentido intuitivo, lo que corresponde a conectar diferentes pruebas y verificarlas linealmente en secuencia, es decir, verificar primero la primera prueba y luego verificar la segunda.
Dos pruebas y pruebas posteriores. El problema es que este enfoque no cambiará el tamaño de la prueba ni el tiempo de la prueba, que es lo mismo que probar y verificar una por una. Si desea lograr una compresión espacial logarítmica, debe utilizar la recursión de prueba que se menciona a continuación.
Esquema de recursión de prueba utilizado por Halo2 y STARK
Para explicar mejor qué es una prueba recursiva, volvamos al ejemplo anterior.
Las siete imágenes de Alice son siete pruebas. Ahora considere fusionarlos, para que Alice pueda tomar una foto el día 1, tomar esta foto el día 2 y el periódico el día 2, y tomar la foto del día 2 y el periódico en la foto 3. 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, y otros amigos pueden verificar que están del 1 al 7 cuando ven la última foto del día 7.
Alice fue toda al parque. Se puede ver que las siete fotografías de prueba anteriores se han comprimido en una. Y una habilidad clave en este proceso son las “fotos que contienen fotos”, lo que equivale a anidar recursivamente fotos anteriores en fotos posteriores. Es diferente a juntar muchas fotografías y tomar una sola.
El truco de prueba recursiva de zkRollup puede comprimir en gran medida el tamaño de la prueba. Específicamente, cada transacción generará pruebas. Configuramos el circuito de cálculo de la transacción original como C0, P0 como la prueba de corrección de C0 y V0 como el proceso de cálculo para verificar P0.
El probador también convierte V0 en el circuito correspondiente, denominado C0′. Actualmente, para el proceso de cálculo de prueba, C1 de otra transacción, se pueden fusionar los circuitos de C0′ y C1. De esta manera, una vez verificada la prueba de corrección P1 del circuito fusionado, equivale a verificar los dos circuitos anteriores al mismo tiempo. Se logra la corrección de la transacción, es decir, la compresión.
Mirando hacia atrás en el proceso anterior, se puede encontrar que el principio de compresión es convertir el proceso de verificación y prueba en un circuito y luego generar "prueba por prueba", por lo que desde esta perspectiva, es una operación que puede repetirse continuamente. hacia abajo, por lo que también se conoce como prueba recursiva.
El esquema de recursión de prueba adoptado por Halo2 y STARK puede generar pruebas en paralelo y combinar múltiples pruebas, de modo que se pueda verificar la exactitud de múltiples ejecuciones de transacciones mientras se verifica un valor de prueba, lo que puede comprimir la sobrecarga de cálculo, mejorando así 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 optimización e innovación de nivel inferior. El algoritmo FOAKS diseñado por Fox hace esto aplicando ideas recursivas dentro de una prueba hasta este punto.
Esquema de recursión de prueba utilizado por FOAKS
Fox Tech es un proyecto zkRollup basado en zkEVM. En su sistema de prueba, también se 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 para reducir continuamente el problema a demostrar hasta que el problema reducido sea lo suficientemente simple, necesitamos dar otro ejemplo.
En el ejemplo anterior, Alice demuestra que fue a Fox Park cierto día tomando una foto, por lo que Bob hace una sugerencia diferente. Piensa que el problema de demostrar que Alice ha estado en el parque se puede reducir a demostrar que el teléfono móvil de Alice ha estado en el parque. Y probar este asunto se puede reducir a demostrar que la ubicación del teléfono móvil de Alice está dentro del alcance del parque.
Por lo tanto, para demostrar que Alice ha estado en el parque, solo necesita enviar una ubicación con su teléfono móvil mientras está en el parque. De esta manera, el tamaño de la prueba se cambia de una fotografía (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 teléfono móvil de Alice haya estado en Fox Park no significa que Alice haya estado allí, pero en situaciones reales, este proceso de reducción es estrictamente matemático.
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. Y en lugar de mostrar que estas ecuaciones se satisfacen, las escribimos nuevamente como circuitos, y así sucesivamente, hasta que finalmente, las ecuaciones para probar la satisfacción se vuelven lo suficientemente simples como para que podamos probarla directamente.
A partir de este proceso, podemos ver que esto se acerca más al significado de "recursión". Vale la pena mencionar que no todos los algoritmos pueden utilizar esta técnica recursiva, suponiendo que cada recursión cambiará la prueba de 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)), entonces la complejidad computacional total se convierte en O1(n)=O(f(n))+O(g(n)) después de una recursión, y O2(n) después de dos recursiones) =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, dicha técnica recursiva puede funcionar eficazmente sólo cuando las dos funciones de f y g correspondientes a las características del algoritmo satisfacen Ok(n)
Conclusión
La complejidad de la prueba siempre ha sido una de las claves más importantes en la aplicación de pruebas de conocimiento cero. La naturaleza de la complejidad de la prueba será cada vez más importante a medida que las cosas a probar se vuelvan cada vez más complejas, especialmente en aplicaciones ZK gigantes como zkEVM.
En este escenario, la complejidad de la prueba tendrá un impacto decisivo en el rendimiento del producto y la experiencia del usuario. Entre las muchas formas de reducir la complejidad de la prueba final, la optimización del algoritmo central es la más importante.
Fox ha diseñado un exquisito esquema de prueba de entrega basado en el algoritmo más avanzado y utiliza esta tecnología para crear el zkEVM más adecuado. Se espera que el algoritmo ZK-FOAKS se convierta en el líder en rendimiento en la industria zkRollup.
EXENCIÓN DE RESPONSABILIDADES: La información de este sitio web se proporciona como un comentario general del mercado y no constituye un consejo de inversión. Le animamos a que haga su propia investigación antes de invertir.
Únase a nosotros para estar al tanto de las novedades: https://linktr.ee/coincu
Harold
Coincú Noticias
Autor
Conocimiento
¿Cómo diseñar un mejor esquema de recursividad de prueba?
Casi todos los problemas encontrados en las pistas zkRollup y zkEVM son esencialmente problemas algorítmicos. La razón principal por la que se menciona con frecuencia la aceleración de hardware ZK-Proof es que los algoritmos actuales son generalmente lentos.
Para evitar caer en la vergonzosa situación de "el algoritmo no es suficiente, el hardware se utiliza para compensar", debemos resolver el problema desde la esencia del algoritmo. Diseñando una recursión exquisita a prueba de entrega El esquema 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 la Capa 1 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 a resolver.
Para Ethereum, zkRollup utiliza el algoritmo de prueba de conocimiento cero como componente subyacente para mover los costosos cálculos que originalmente debían 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 proyectos como StarkWare, zkSync, desplazamiento, y tecnología zorro.
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, lo que puede reducir la cantidad de cálculo de la Capa 1. Para obtener una longitud de prueba suficientemente pequeña, cada El proyecto zkRollup está mejorando el algoritmo y el diseño de la arquitectura. Por ejemplo, Fox ha desarrollado su algoritmo de prueba FOAKS en combinación con el último algoritmo de prueba de conocimiento cero para obtener el tiempo y la duración de prueba óptimos.
Además, en la etapa de verificación de pruebas, el medio 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 conoce como agregación de pruebas.
Intuitivamente hablando, verificar las pruebas generadas por zkEVM es un proceso lineal y el Verificador necesita 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 por parte del verificador significa más cálculos de Capa 1, lo que también generará tarifas de gas más altas.
Primero veamos un ejemplo: Alice quiere demostrarle al mundo que fue a Fox Park del 1 al 7 de este mes. Por eso, podrá hacerse una foto en el parque con el periódico del día cada día del 1 al 7, y estas siete fotos se convertirán en prueba.
Poner siete fotos directamente en un sobre en el ejemplo anterior es agregación de pruebas en un sentido intuitivo, lo que corresponde a conectar diferentes pruebas y verificarlas linealmente en secuencia, es decir, verificar primero la primera prueba y luego verificar la segunda.
Dos pruebas y pruebas posteriores. El problema es que este enfoque no cambiará el tamaño de la prueba ni el tiempo de la prueba, que es lo mismo que probar y verificar una por una. Si desea lograr una compresión espacial logarítmica, debe utilizar la recursión de prueba que se menciona a continuación.
Esquema de recursión de prueba utilizado por Halo2 y STARK
Para explicar mejor qué es una prueba recursiva, volvamos al ejemplo anterior.
Las siete imágenes de Alice son siete pruebas. Ahora considere fusionarlos, para que Alice pueda tomar una foto el día 1, tomar esta foto el día 2 y el periódico el día 2, y tomar la foto del día 2 y el periódico en la foto 3. 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, y otros amigos pueden verificar que están del 1 al 7 cuando ven la última foto del día 7.
Alice fue toda al parque. Se puede ver que las siete fotografías de prueba anteriores se han comprimido en una. Y una habilidad clave en este proceso son las “fotos que contienen fotos”, lo que equivale a anidar recursivamente fotos anteriores en fotos posteriores. Es diferente a juntar muchas fotografías y tomar una sola.
El truco de prueba recursiva de zkRollup puede comprimir en gran medida el tamaño de la prueba. Específicamente, cada transacción generará pruebas. Configuramos el circuito de cálculo de la transacción original como C0, P0 como la prueba de corrección de C0 y V0 como el proceso de cálculo para verificar P0.
El probador también convierte V0 en el circuito correspondiente, denominado C0′. Actualmente, para el proceso de cálculo de prueba, C1 de otra transacción, se pueden fusionar los circuitos de C0′ y C1. De esta manera, una vez verificada la prueba de corrección P1 del circuito fusionado, equivale a verificar los dos circuitos anteriores al mismo tiempo. Se logra la corrección de la transacción, es decir, la compresión.
Mirando hacia atrás en el proceso anterior, se puede encontrar que el principio de compresión es convertir el proceso de verificación y prueba en un circuito y luego generar "prueba por prueba", por lo que desde esta perspectiva, es una operación que puede repetirse continuamente. hacia abajo, por lo que también se conoce como prueba recursiva.
El esquema de recursión de prueba adoptado por Halo2 y STARK puede generar pruebas en paralelo y combinar múltiples pruebas, de modo que se pueda verificar la exactitud de múltiples ejecuciones de transacciones mientras se verifica un valor de prueba, lo que puede comprimir la sobrecarga de cálculo, mejorando así 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 optimización e innovación de nivel inferior. El algoritmo FOAKS diseñado por Fox hace esto aplicando ideas recursivas dentro de una prueba hasta este punto.
Esquema de recursión de prueba utilizado por FOAKS
Fox Tech es un proyecto zkRollup basado en zkEVM. En su sistema de prueba, también se 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 para reducir continuamente el problema a demostrar hasta que el problema reducido sea lo suficientemente simple, necesitamos dar otro ejemplo.
En el ejemplo anterior, Alice demuestra que fue a Fox Park cierto día tomando una foto, por lo que Bob hace una sugerencia diferente. Piensa que el problema de demostrar que Alice ha estado en el parque se puede reducir a demostrar que el teléfono móvil de Alice ha estado en el parque. Y probar este asunto se puede reducir a demostrar que la ubicación del teléfono móvil de Alice está dentro del alcance del parque.
Por lo tanto, para demostrar que Alice ha estado en el parque, solo necesita enviar una ubicación con su teléfono móvil mientras está en el parque. De esta manera, el tamaño de la prueba se cambia de una fotografía (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 teléfono móvil de Alice haya estado en Fox Park no significa que Alice haya estado allí, pero en situaciones reales, este proceso de reducción es estrictamente matemático.
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. Y en lugar de mostrar que estas ecuaciones se satisfacen, las escribimos nuevamente como circuitos, y así sucesivamente, hasta que finalmente, las ecuaciones para probar la satisfacción se vuelven lo suficientemente simples como para que podamos probarla directamente.
A partir de este proceso, podemos ver que esto se acerca más al significado de "recursión". Vale la pena mencionar que no todos los algoritmos pueden utilizar esta técnica recursiva, suponiendo que cada recursión cambiará la prueba de 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)), entonces la complejidad computacional total se convierte en O1(n)=O(f(n))+O(g(n)) después de una recursión, y O2(n) después de dos recursiones) =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, dicha técnica recursiva puede funcionar eficazmente sólo cuando las dos funciones de f y g correspondientes a las características del algoritmo satisfacen Ok(n)
Conclusión
La complejidad de la prueba siempre ha sido una de las claves más importantes en la aplicación de pruebas de conocimiento cero. La naturaleza de la complejidad de la prueba será cada vez más importante a medida que las cosas a probar se vuelvan cada vez más complejas, especialmente en aplicaciones ZK gigantes como zkEVM.
En este escenario, la complejidad de la prueba tendrá un impacto decisivo en el rendimiento del producto y la experiencia del usuario. Entre las muchas formas de reducir la complejidad de la prueba final, la optimización del algoritmo central es la más importante.
Fox ha diseñado un exquisito esquema de prueba de entrega basado en el algoritmo más avanzado y utiliza esta tecnología para crear el zkEVM más adecuado. Se espera que el algoritmo ZK-FOAKS se convierta en el líder en rendimiento en la industria zkRollup.
EXENCIÓN DE RESPONSABILIDADES: La información de este sitio web se proporciona como un comentario general del mercado y no constituye un consejo de inversión. Le animamos a que haga su propia investigación antes de invertir.
Únase a nosotros para estar al tanto de las novedades: https://linktr.ee/coincu
Harold
Coincú Noticias
Otras publicaciones
Artículos Relacionados
Noticias
El suministro de tokens Sui es controvertido cuando más del 84% de los tokens apostados están controlados por los fundadores
Noticias
El 90% de los volúmenes de transacciones de Stablecoin no cuentan con la participación de usuarios reales
Noticias
La violación de datos de Bitfinex ahora está causando controversia, el CEO de Tether expresa su refutación
Noticias
La nueva demanda colectiva sobre Coinbase ataca a Exchange con cargos por cotización de valores
Noticias
Contratos de red liquidados: ¡75.9 millones de dólares perdidos en 24 horas, impactando a los comerciantes!
Noticias
Inversión de Pantera Capital TON impulsada para mejorar las capacidades de pago P2P
Noticias
¡El presidente de la SEC es acusado de engaño con respecto a la legitimidad de Ethereum!
ECONOMÉTRICOS
Abril es el peor mes para Bitcoin en medio de salidas de ETF: informe
Noticias
Roger Ver arrestado en España, acusado de fraude fiscal de 48 millones de dólares
Noticias
Un error de dirección provoca una pérdida de 68 millones de dólares para el WBTC y la víctima cae en una estafa de phishing
Conocimiento
Minería de Bitcoin: ¿Cuánto tiempo se tarda en extraer 1 Bitcoin?
Conocimiento
Predicciones electorales en Estados Unidos: los efectos y la importancia del nuevo presidente de Estados Unidos
Conocimiento
Posibles candidatos a las elecciones estadounidenses de 2024: ¿quién ganará?
Noticias
