La guía para principiantes que me hubiera gustado hace unos meses antes de profundizar en estas cosas
Lo que necesitarás:
- un fondo de ciencias de la computación
- los fundamentos de Ethereum
- Los fundamentos del cálculo (optimización de restricciones)
Lo que usted obtendrá:
- los fundamentos de los SNARK de conocimiento cero
- los fundamentos de los árboles Merkle
- cómo Ethereum podría escalar a miles de transacciones por segundo gracias a SNARK
Los SNARK le permiten a un Probador probarle a un Verificador que tiene una solución W al problema F con entradas compartidas / conocidas X, sin revelar W.
Encontrar la solución al problema podría requerir una gran cantidad de potencia computacional y memoria.
Por lo tanto, el Verificador básicamente puede estar 100% seguro de que el Prover ha funcionado correctamente (y ha encontrado una solución), sin volver a hacer el trabajo solo para verificar la solución ni conocer la solución en absoluto. ¡Es magia!
El proceso tiene 3 pasos:
- CONFIGURACIÓN - El problema F (que debe expresarse como un programa aritmético cuadrático, ver más abajo) está preparado para SNARK. Este proceso es muy intensivo en memoria y computación, dependiendo de la complejidad del problema (→ El número de entradas y restricciones → La dimensión de la matriz del problema de satisfacción de restricciones). Todas las partes deben confiar en el jugador que realiza la Configuración (podría ser el Verificador), ya que la salida de la Configuración se utiliza en las siguientes fases. La configuración generalmente se realiza utilizando libsnark, una biblioteca C ++ que es la implementación más popular para zkSNARKs.
- PROVING - El Prover, que tiene una solución W para el problema F con entradas compartidas X (¡tal vez haya gastado grandes cantidades de CPU y memoria para encontrarlo!), Usa libsnark y la salida de la Preparar fase para crear una prueba 𝚷. Este proceso definitivamente requiere mucha memoria y mucha computación (dependiendo de la complejidad del problema, como se indicó anteriormente). El tamaño de la salida (es decir, la prueba 𝚷) es sucinta y constante, independientemente de la complejidad del problema. El Prover necesita confiar en quién ha realizado la fase de Configuración, ya que usa su salida ...
- VERIFICANDO - Un verificador: proporciona como entrada la salida de la fase de configuración, las entradas compartidas X y la prueba 𝚷: comprueba la prueba. Si la verificación es exitosa, el Prover logró demostrarle a un Verificador que ha encontrado la solución W al problema F ... ¡sin revelar W! Lo bueno es que no solo la Prueba es sucinta y siempre tiene la misma longitud ..., el proceso de verificación es rápido y no requiere de mucha memoria / computación. A diferencia de las dos fases anteriores ... ¡la verificación se puede hacer fácilmente con un teléfono inteligente en milisegundos!
Un buen resumen (fuente):
¿Cómo puede pasar esto? Bueno, ¡es magia de Merlín! Si quieres obtener las matemáticas detrás de esto, empieza desde aquí.
¿Cómo puedo transformar mi software en un programa aritmético cuadrático?
Como se mencionó anteriormente, el problema F de la fase de configuración debe ser un programa aritmético cuadrático. Las reglas del juego son difíciles:
- Las entradas de su software deben ser números. Convierta sus cosas (matrices, cadenas, etc.) en números. Eso es trivial
- Un "sistema de ecuaciones con restricciones cuadráticas" significa:
donde x es el vector n-dimensional de sus entradas, m es el número de restricciones (es decir, el número de ecuaciones de su sistema), C es la matriz de coeficientes n-por-n y q es un vector de coeficientes n-dimensionales. Si no le gustan la matriz y los vectores, aquí está el caso n = 3 ym = 2 (3 entradas, 2 restricciones):
- La implementación es un circuito aritmético, lo que significa que el resultado es Problema resuelto (el sistema está resuelto, es decir, todos los polinomios son iguales a 0) o Problema no resuelto (todos los demás casos). En otras palabras: "estas entradas son / no son una de las soluciones a este problema".
- Los coeficientes C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 son las restricciones del sistema. Esto es básicamente lo que define su software. Cámbielos ... ¡y obtendrá otro software! Volviendo a cómo funcionan los SNARK: C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 son la entrada de la fase de configuración. El resultado de la fase de configuración (que necesita para probar y verificar) está, por lo tanto, estrictamente relacionado con esos C₁, C₂, ..., C𝚖, q₁, q₂, ..., q𝚖 y funciona solo para ese problema. ¡Si los cambia, está definiendo otro software / problema y necesita volver a ejecutar la fase de Configuración! x₁, x₂, ..., x𝗇 son las variables (es decir, lo que tienes que adivinar para obtener la solución de un sistema). Entonces, cuando decimos "Estimado Prover, ¿podría encontrar una solución secreta W para el problema F con entradas compartidas / públicas X", nos referimos por ejemplo a "Estimado Prover, ¿puede encontrar los valores x₁, x₂, ..., x𝗇 que resuelven el sistema? con, por ejemplo, x₇ = 2393, x₅₂₆ = 5647? Puede hacer lo que quiera con todos x𝗇, excepto x₇ y x₅₂₆, que están restringidos a las entradas compartidas / públicas.
Es una vida difícil pero puedes sobrevivir ... Si necesitas bucles, puedes desplegarlos repitiendo la misma operación muchas veces. O si necesita, por ejemplo, x₁⁴ x₂⁵, defina una nueva entrada x₃ = x₁⁴ x₂⁵ y use x₃ en sus restricciones. Se trata de agregar variables y restricciones ... ¡Incluso para softwares bastante simples, es fácil alcanzar cientos de millones o miles de millones de entradas y restricciones!
¿Quieres saber más? Leer esta página. Y también echa un vistazo a este básico código_a_r1cs.py de ethereum / research.
¿Qué es un árbol Merkle?
Una función hash es una regla que asigna una entrada de tamaño arbitrario a una salida de tamaño fijo. Podríamos inventar una función hash bastante inútil "Concatenar las dos primeras con las dos últimas letras" que transforma "Woody Allen" en "Woen" y "Paul McCartney" en "Paey".
Un árbol de Merkle es una estructura de datos donde cada padre es el hash de sus dos hijos. En la parte superior se encuentra la raíz, que es el hash de los dos hijos del nivel 1. En la parte inferior, cada hoja es el hash de una entrada externa.
Usando nuestra función hash ficticia "Woody Allen" → "Woen":
Cuando una hoja cambia, la modificación se propaga hasta la raíz. Si ANTHONY cambia, también cambian ANNY (hoja), CENY y CECO (Root). Cualquiera que sea la hoja que cambie, la raíz también cambia.
No necesita todo el árbol para volver a calcular la raíz. En nuestro ejemplo, si ANTHONY cambia y conoce tanto a JACO como a CECILY, puede volver a calcular fácilmente la raíz incluso si ignora por completo a JAMES, MARCO, JAES y MACO. ¡Para árboles enormes esto ahorra mucho tiempo!
¿Y qué?
Los árboles Merkle son excelentes para las verificaciones de integridad de datos. Usualmente: usted sabe cuál es la raíz válida y verifica que los datos recibidos coincidan con esa raíz. Por ejemplo: una parte de confianza que no puede darle el conjunto de datos completo de los nombres de las personas en la Tierra (sin tiempo, sin ancho de banda o tal vez ella / él no tiene los datos) le da solo la Raíz (p. Ej. "CECO"). Palabras clave: usted recibe millones de nombres, con referencia al número de hoja, por miles de partes no confiables. Bueno, dado que tiene la raíz correcta, puede verificar en quién puede confiar, quién le está dando datos falsos ...
¡Los árboles de Merkle también son parte de tu vida! Cuando estás descargando un archivo Torrent de 3 GB, tu archivo se divide en millones de pequeños fragmentos. El hash de cada fragmento se almacena en una hoja. Como sabe cuál es la raíz válida del árbol, cada vez que alguien recibe un fragmento del archivo, puede verificar si es correcto. Si no es así, puede pedirle la misma porción a otra persona.
Puede hacerlo incluso si aún no ha descargado el árbol completo / todas las hojas: si sabe que la raíz es CECO y confía en JACO ... cuando recibe el fragmento ANTHONY, puede verificarlo incluso si no lo ha descargado sin embargo, los trozos MARCO y JAMES.
Por qué los árboles de Merkle son útiles en la tecnología de contabilidad distribuida es sencillo: utiliza protocolos de consenso (lento, costoso) solo para llegar a un consenso sobre la raíz. Luego, los nodos no confiables de la red pueden compartir datos de manera eficiente y directa ... y pueden dormir sanos y salvos gracias a las comprobaciones de integridad con Root.
Cuando Dios le pidió a Ethereum que eligiera 2 superpoderes entre Seguridad, Escalabilidad y Descentralización ... Ethereum sacrificó la Escalabilidad. En realidad, no hay un límite fuerte para las "transacciones por segundo": el límite se refiere a la cantidad de gas de cada bloque, que es, simplificando, la cantidad de operaciones que puedo hacer en cada bloque. Este límite es de 8 millones de gas. Eso podría significar muchas transacciones "pequeñas" (sin datos adjuntos a las transacciones, sin operaciones que se ejecuten en esos datos) o pocas transacciones grandes. Depende de los nodos de Ethereum, que envían transacciones, y de los mineros de Ethereum, que incluyen en el bloque las transacciones que pagan más.
Se extrae un bloque cada ~ 15 segundos. Eso significa ~ 32 millones de gases por minuto, lo que definitivamente no es suficiente si queremos que los dapps de Ethereum se generalicen.
Por cierto: deténgase con esas tediosas comparaciones entre Ethereum y Visa. Un sistema centralizado hacerlo ser más rápido que Ethereum ... ¡por diseño! Hacen cosas diferentes y los necesitas en diferentes situaciones. Si no necesita descentralización y un entorno sin confianza ... por supuesto, debe elegir Visa. En breve: ¡El hecho de que su licuadora gire más rápido que su lavadora no significa que va a limpiar sus pantalones en una licuadora!
¡Armemos el rompecabezas! Imagine que podría "comprimir" muchas transacciones pequeñas en una transacción grande gracias a SNARKs. Si el gas gastado por esta gran transacción es menor que la suma del gas gastado por las pequeñas transacciones, eso significa que está ahorrando gas.
Y ahorrar gas significa:
- Usuarios que gastan menos en transacciones en general → Esto sería un impulso para todo el ecosistema
- Poder poner más cosas en un bloque → ¡Ethereum gira más rápido que tu licuadora!
¿Cómo funciona?
Hay usuarios, un repetidor (o más intermediarios) que agregan transacciones y un contrato inteligente.
- Los usuarios que deseen jugar a este juego envían su Ether (o tokens) a un contrato inteligente auditado públicamente. Por cada nuevo jugador se crea una nueva hoja en un árbol Merkle. La hoja incluye información sobre el propietario del Ether (su dirección, que también es la clave pública), la cantidad de Ether y nonce (el contador de transacciones de esa cuenta, que es 0 cuando se agrega la hoja)
- Cuando A quiere enviar Ether a B (ambos necesitan tener una hoja / cuenta en el contrato inteligente), A empaqueta una transacción, que incluye la dirección del encuenta, la a cuenta, la nuncio apostólico de la cuenta de, la cantidad de éter para ser transferido y el firma de la transacción (firmada con la clave privada de la cuenta "de", obviamente). Luego, él / ella envía la transacción empaquetada al relé.
- El retransmisor agrega todas las transacciones recibidas en un intervalo de tiempo determinado (por ejemplo, una hora), actualiza el árbol de Merkle con las cantidades de los nuevos saldos y crea una prueba SNARK que demuestra que todas las firmas y la raíz del nuevo árbol de Merkle son válidas. El retransmisor finalmente envía el nuevo estado y la prueba al contrato inteligente.
- El contrato inteligente valida la prueba en cadena. Si es válido, guarda la raíz del árbol Merkle del estado Nuevo en la memoria interna del contrato.
Básicamente, la raíz del árbol de Merkle representa el estado completo de todas las cuentas. Y no puede cambiarlo (= robar dinero) a menos que pueda probar la validez de las firmas cuyas transacciones conducen al Nuevo estado resumido por la nueva raíz que está enviando.
En pocas palabras: los usuarios tienen transacciones súper rápidas y casi gratuitas, como en Coinbase, sin necesidad de confiar en el retransmisor, que no puede hacer nada, a diferencia de Coinbase, sin su firma.
Es una cadena lateral sin custodia cuyo estado se resume en una raíz de árbol de Merkle.
Conectemos lo que aprendimos anteriormente sobre SNARK con lo que acabamos de discutir sobre el escalado. Hay diferentes formas de hacer eso. Compararé 2 recetas: las de Vitalik versión y barryWhiteHat's versión.
La CONFIGURACIÓN se realiza por ...
El tipo que inicia el proyecto, que también crea el contrato inteligente. Cuanto más auditable sea, mejor. Deberías confiar en él / ella ... es un configuración confiable!
El contrato inteligente ahorra ...
2 raíces Merkle (valores de bytes32): el primer árbol contiene las direcciones de las cuentas (firmas públicas), los saldos de las segundas cuentas y luego
PROVING se hace por ...
El relevo
El retransmisor envía al contrato inteligente ...
- Las 2 raíces Merkle del nuevo estado (árbol de direcciones y saldos + árbol nonces)
- La lista de transacciones, sin firmas. “Cada transacción cuesta 68 gas por byte. Por lo tanto, para una transferencia regular, podemos esperar que el costo marginal sea 68 * 3 (desde) + 68 * 3 (hasta) + 68 * 1 (tarifa) + 68 * 4 + 4 * 2 (cantidad) + 68 * 2 (nonce) u 892 gas "
Las entradas conocidas del proceso PROVING son ...
- las 2 raíces del viejo estado de Merkle
- Las 2 nuevas raíces estatales de Merkle
- lista de transacciones
El proceso PROVING demuestra que ...
Dado que los
- Las 2 raíces antiguas de Merkle (ya almacenadas en el contrato)
- las 2 nuevas raíces estatales de Merkle (enviadas en la transacción agregada)
- la lista de transacciones (enviada en la transacción agregada)
... el retransmisor tiene firmas válidas para moverse del estado con 2 raíces antiguas al estado con 2 raíces nuevas con esas transacciones.
La VERIFICACIÓN se realiza por ...
El contrato inteligente (¡codificado en solidez, vyper, como quieras!)
VERIFICANDO las entradas conocidas del proceso son ...
El mismo proceso de PROVING conoce entradas, claramente ...!
Límites de escalabilidad
Cada transacción agregada usa 650k de gas para la verificación SNARK (costo fijo) más ~ 900 de gas costo marginal por transacción (¡cuesta enviar datos!). Entonces, utilizando todo el bloque, el relé puede agregar como máximo:
lo que significa ~ 544 tx por segundo
barryWhiteHat's versión
La CONFIGURACIÓN se realiza por ...
El chico que comienza el proyecto.
El contrato inteligente ahorra ...
1 raíz de Merkle con el estado actual. Cada hoja es el estado hash de una cuenta.
¿Quieres Para crear ¿una cuenta?
state = AccountState (pubkey, balance, nonce)
state.index = self._tree.append (state.hash ())
PROVING se hace por ...
El relevo
El retransmisor envía al contrato inteligente ...
- prueba 𝚷
- la nueva raíz de Merkle del estado
- prueba 𝚷
Las entradas conocidas del proceso PROVING son ...
- la raíz de Merkle del viejo estado
- la nueva raíz de Merkle del estado
El proceso PROVING demuestra que ...
Dado que los
- la raíz de Old Merkle (ya almacenada en el contrato)
- la nueva raíz de Merkle (senti en la transacción agregada)
... el retransmisor tiene una lista de transacciones con firmas válidas para pasar del estado con raíz antigua a estado con raíz nueva
La VERIFICACIÓN se realiza por ...
El contrato inteligente (¡codificado en solidez, vyper, como quieras!)
VERIFICANDO las entradas conocidas del proceso son ...
El mismo proceso de PROVING conoce entradas, claramente ...!
Límites de escalabilidad
El retransmisor no está enviando datos de transacciones al contrato inteligente (lo cual es costoso), por lo que el límite es en realidad la cantidad de gas para verificar la prueba SNARK.
Mencionando a Howard Wu trabajo sobre la ejecución de la fase PROVING de SNARK en sistemas distribuidos, barryWhiteHat con optimismo afirma que es posible confirmar 16666 transacciones en un enorme SNARK (¡mil millones de restricciones!).
barryWhiteHat también piensa es posible verificar la prueba 𝚷 en la cadena con 500k de gas, lo que significa que puede colocar 16 SNARKs (8 millones / 500k) por bloque, que es ~ 1.07 SNARKs por segundo ... lo que significa ~ 17,832 tx por segundo (16,666 * 1.07).
Al infinito y más allá
- Todo lo que brilla no es oro / 1. La cantidad de potencia informática y memoria que necesita en la fase de prueba puede ser literalmente impactante. Especialmente en la versión de barryWhiteHat, donde parte de la complejidad se mueve fuera de la cadena. Barry escribe “En una computadora portátil con 7 GB de RAM y 20 GB de espacio de intercambio, tiene dificultades para agregar 20 transacciones por segundo”. Bueno, si el objetivo es 17,832 tx por segundo ... LOL. Esto presenta desafíos de computación paralela no triviales. Pero si el costo promedio de $ por transacción es mucho más barato que la opción normal sin SNARKs ... el juego vale la pena.
- Todo lo que brilla no es oro / 2. ¡Hay un problema relevante de disponibilidad de datos! Como solo se guarda la raíz del árbol en el contrato, debe asegurarse de que siempre esté disponible una versión completa del árbol (o, es lo mismo, todo el historial de transacciones). Si los datos no están disponibles, el retransmisor, incluso con transacciones válidas firmadas, no puede hacer nada porque no puede probar el estado antiguo → transacciones → estado nuevo.
- Para que el retransmisor no tenga confianza y Ethers en el contrato tenga el mismo valor de Ethers fuera (problema de liquidez) ... los usuarios deberían poder retirar dinero del contrato inteligente cuando lo deseen, sin depender de un relayer (específico). ¿Cómo? Esto no está en el alcance de esta publicación 101, pero puede leer sobre esto en los enlaces adjuntos.
- ¿Desea comprender más acerca de cómo se puede manejar el Estado actual (direcciones, saldos y nonces) con un árbol Merkle? ¿Agregar una hoja, actualizar una hoja, etc.? Revisa esta biblioteca (archivo de prueba esta página) que utiliza este subyacente módulo. Gracias HarryR!
- ¿Desea configurar su entorno personal Ethereum-SNARKs? Comencemos fuera de la cadena con C ++ (configuración, prueba, verificación) esta página. Luego puedes pasar a Ethereum (¡no olvides que solo la verificación se realiza en cadena!) Con Zokrates (repo, la documentación para comenzar).
- ¿Qué tal el uso de acumuladores RSA en lugar de árboles Merkle? Google "Rsa acumuladores ethereum" para comenzar…
¡Disfruta!
Twitter @marco_derossi
- 7
- Mi Cuenta
- Todos
- entre
- disponibilidad
- conceptos básicos
- mil millones
- cases
- el cambio
- Cheques
- coinbase
- informática
- Consenso
- contrato
- Precio
- Current
- Estado actual
- DApps
- datos
- conjunto de datos
- Descentralización
- Dimensiones
- Libro mayor distribuido
- tecnología de libro distribuido
- Entorno
- Éter
- Etereum
- EU
- EV
- falso
- Finalmente
- Nombre
- Gratuito
- función
- juego
- GAS
- GitHub
- Diezmos y Ofrendas
- Gold
- candidato
- maravillosa
- guía
- hachís
- esta página
- Alta
- historia
- Cómo
- hr
- HTTPS
- enorme
- Cientos
- ia
- índice
- información
- IP
- IT
- Trabajos
- Clave
- portátil
- large
- Lead
- Libro mayor
- Nivel
- LG
- Biblioteca
- Liquidez
- Lista
- Corriente principal
- Mapas
- mediano
- millones
- Mineros
- dinero
- meses
- Más popular
- movimiento
- nombres
- del sistema,
- nodos
- números
- Operaciones
- solicite
- Otro
- propietario
- Pagar
- (PDF)
- Personas
- jugador
- Popular
- industria
- privada
- clave privada
- Programa
- proyecto
- prueba
- Demuestra
- público
- clave pública
- resumen
- rsa
- reglas
- correr
- ambiente seguro
- ahorro
- Escalabilidad
- Escala
- la ampliación
- Ciencia:
- EN LINEA
- set
- Compartir
- compartido
- En Corto
- sencillos
- Tamaño
- sueño
- inteligente
- contrato inteligente
- teléfono inteligente
- So
- Software
- solidez
- Soluciones
- RESOLVER
- Espacio
- Gastos
- comienzo
- fundó
- Estado
- Zonas
- exitosos
- te
- Todas las funciones a su disposición
- Tecnología
- test
- equipo
- Tokens
- parte superior
- torrente
- transaccional
- Transacciones
- Confía en
- Actualizaciones
- usuarios
- propuesta de
- Verificación
- .
- W
- QUIENES
- palabras
- Actividades:
- funciona
- valor
- X