a16z: Sobre la imposibilidad de una "cadena de bloques sin estado"

Escrito originalmente por Miranda Christ y Joseph Bonneau

Recopilación del texto original: Deep Tide TechFlow

A medida que la cadena de bloques admite más usuarios y transacciones más frecuentes, aumenta la cantidad de información (o "estado") almacenada por los validadores para verificar las transacciones. Por ejemplo, en Bitcoin, el estado consta de un conjunto de resultados de transacciones no gastadas (UTXO). En Ethereum, el estado consiste en el saldo de cada cuenta y el código y almacenamiento de cada contrato inteligente.

A medida que la cadena de bloques crezca con suficientes cuentas o UTXO para respaldar transacciones diarias reales para una parte considerable de la población, esta carga de almacenamiento se volverá inmanejable, lo que hará que convertirse en un validador sea difícil y una amenaza para la descentralización. Una solución tentadora es recurrir a la criptografía, donde herramientas como los árboles Merkle y las pruebas de conocimiento cero nos ayudan a lograr cosas que antes eran inimaginables.

Este es exactamente el objetivo de una "cadena de bloques sin estado". Pero a pesar de muchas investigaciones sobre ellos, todavía están lejos de ser prácticos. Pero resulta que este retraso en el progreso es inherente: la brecha entre estas construcciones y la practicidad nunca se cerrará. Nuestro trabajo reciente muestra que cualquier propuesta de blockchain sin estado, por inteligente que sea, no es factible sin medidas adicionales para gestionar el estado. Sin embargo, como mostramos al final de este artículo, este resultado de improbabilidad no debería ser desalentador.

sin Estado

Hoy en día, el Estado es enorme pero manejable. Por ejemplo, un nodo Bitcoin almacena alrededor de 7 GB de datos y un nodo Ethereum almacena alrededor de 650 GB de datos. Sin embargo, la carga de almacenamiento en los nodos completos aumenta aproximadamente de manera lineal con el rendimiento de la cadena (transacciones por segundo o TPS), lo que todavía es inaceptable en la actualidad. Tal como está diseñado actualmente, el estado requerido para respaldar verdaderamente las transacciones diarias (de decenas a cientos de miles de transacciones por segundo) se volvería inmanejable y requeriría gigabytes o incluso petabytes de almacenamiento.

Esto ha motivado a la gente a encontrar formas técnicas de reducir significativamente la cantidad de estado requerida por los validadores. Es crucial la implementación de una cadena de bloques sin estado, que requeriría que los validadores solo almacenen estados de tamaño constante independientemente del rendimiento de la transacción (en realidad, el término es un nombre inapropiado: todavía hay un estado, lo suficientemente pequeño como para que sea práctico en cualquier futuro). rendimiento (generalmente tamaño constante). Este requisito de almacenamiento liviano hará que sea más fácil ejecutar un nodo de validación; de manera optimista, todos pueden ejecutar un nodo en su teléfono. Dado que aumentar el número de validadores aumenta la seguridad de la cadena, es importante reducir la barrera de entrada para los validadores.

A pesar de una gran cantidad de investigaciones sobre cadenas de bloques sin estado (por ejemplo, por Todd, Buterin, Boneh et al. y Srinivasan et al.), están lejos de ser prácticas y, hasta donde sabemos, ninguna se ha implementado. El problema fundamental con todas las cadenas de bloques sin estado conocidas es que requieren que los usuarios almacenen datos adicionales llamados testigos para ayudar a los validadores a verificar las transacciones que involucran sus cuentas. Por ejemplo, este testigo podría ser una prueba de inclusión de Merkle que muestre que la cuenta y el saldo del usuario están incluidos en el compromiso estatal global. Cuando los usuarios realizan transacciones, envían este testigo a los validadores para demostrar que sus cuentas tienen saldos suficientes.

A diferencia del almacenamiento de claves privadas, que nunca es necesario cambiar, estos testigos cambian con frecuencia, incluso para los usuarios que no realizan transacciones activamente, lo que supone una carga poco realista para los usuarios. De manera similar, imagínese si estuviera monitoreando constantemente todas las demás transacciones con tarjetas de crédito a nivel mundial y actualizando algunos datos locales en consecuencia para usar su propia tarjeta de crédito. Para que una cadena de bloques sea práctica, los usuarios deben poder interactuar con la cadena de bloques sin conexión y solo al enviar transacciones. En muchos casos, como en el caso de las carteras de hardware, actualizar los testigos no sólo es inconveniente, sino imposible.

Esto nos lleva a una pregunta de investigación natural: ¿Podemos construir una cadena de bloques sin estado que no requiera actualizaciones frecuentes de los testigos (o una que solo requiera actualizaciones poco frecuentes de los testigos)? Para responder a esta pregunta, desarrollamos un marco teórico novedoso (Sistema de prueba revocable) que generaliza las cadenas de bloques sin estado. Utilizando este marco, demostramos un resultado improbable: la compensación entre un estado global compacto y actualizaciones frecuentes de testigos es intrínsecamente difícil de conciliar. Nuestra técnica de prueba es teórica de la información, lo que significa que las computadoras futuras no serán lo suficientemente potentes para resolver este problema: la brecha entre la construcción de blockchain sin estado y la practicidad nunca se cerrará.

Antecedentes de nuestra investigación

Para ayudar a comprender nuestros resultados de imposibilidad, primero describimos una forma natural pero ineficiente de construir cadenas de bloques sin estado utilizando árboles Merkle. Nuestro objetivo es permitir que los validadores determinen si una transacción enviada por un usuario es válida; por ejemplo, si el usuario tiene suficiente saldo en la cuenta para realizar la transacción. En un esquema de blockchain sin estado, los validadores almacenan un estado de tamaño constante. Cuando los usuarios realizan una transacción, deben incluir un testigo en la transacción. Un validador puede utilizar el estado actual y el par (transacción, testigo) enviado por el usuario para verificar que el usuario tiene suficiente saldo en la cuenta para realizar la transacción.

Primero construimos un árbol Merkle donde cada par (ID de cuenta, saldo) (a, b) se incluye como un nodo hoja. El estado de tamaño constante V almacenado por los validadores es la raíz de este árbol, que actúa como un compromiso con un conjunto de pares de saldos de cuentas. Cada usuario mantiene su testimonio como prueba de inclusión de Merkle. Una prueba de inclusión de Merkle para una hoja (a,b) consta de nodos asociados (v1,...,vk) a lo largo del camino desde esa hoja hasta la raíz del árbol. Dada una transacción por la cuenta a y un saldo reclamado b, un verificador puede verificar que b es efectivamente el saldo de la cuenta a comparando la prueba (v1,...,vk) de (a,b) con su estado actual V. Si es así, el validador ejecuta la transacción y debe actualizar el saldo de la cuenta en consecuencia. Una propiedad conveniente de los árboles de Merkle es que, dada una prueba de inclusión de Merkle para una hoja, es fácil calcular la raíz del resultado cuando esa hoja cambia. En otras palabras, el verificador puede calcular fácilmente un estado actualizado V' que capture el nuevo saldo de la cuenta a después de que se ejecute la transacción.

Este esquema de árbol de Merkle tiene dos inconvenientes importantes. En primer lugar, el testigo de un usuario es relativamente grande y crece logarítmicamente con el número total de cuentas en el sistema. Lo ideal es que tengan un tamaño constante, y esto lo podemos conseguir utilizando esquemas como los acumuladores RSA.

La segunda desventaja es más difícil de evitar: cada vez que otro usuario realiza una transacción, el comprobante del par de saldos de la cuenta cambia. Recuerde que la prueba de un nodo hoja consta de los nodos asociados en el camino desde ese nodo hoja hasta la raíz del árbol. Si los otros nodos de hoja cambian, uno de los nodos cambiará, provocando un problema real. La mayoría de los usuarios de blockchain quieren mantener pasivamente sus monedas en billeteras y solo conectarse cuando quieren realizar transacciones. Sin embargo, en una cadena de bloques sin estado, los usuarios deben monitorear constantemente las transacciones de otras personas para mantener actualizada la información de sus testigos. Si bien un tercero podría realizar este seguimiento en nombre del usuario, esto se desvía del modelo estándar de cadena de bloques sin estado. En la práctica, este es un desafío insuperable para las cadenas de bloques sin estado, lo que supone una pesada carga para los usuarios.

Nuestra conclusión: la apatridia no es posible

Este fenómeno no solo se aplica a este tipo de estructura de árbol Merkle: todos los esquemas de blockchain sin estado conocidos requieren que los usuarios actualicen su información de testigo con frecuencia, lo cual demostramos aquí. Más precisamente, mostramos que la cantidad de usuarios que deben actualizar la información de sus testigos crece aproximadamente de manera lineal con la cantidad total de transacciones realizadas por todos los usuarios.

Esto significa que incluso si la usuaria Alice no realiza ninguna transacción, es posible que su información de testigo deba cambiar con las transacciones de otros usuarios. Mientras el estado compacto almacenado por los validadores sea demasiado pequeño para capturar el estado completo (es decir, el conjunto de todos los saldos de cuentas), aumentar el tamaño del estado compacto no ayuda mucho. Trazamos esta relación que se muestra a continuación en función de nuestro teorema, junto con la cantidad de cambios de testigo necesarios por día para cadenas de bloques con diferentes rendimientos. Estos gráficos muestran la cantidad de veces que una cadena de bloques sin estado óptima necesitaría cambiar la información de los testigos. Aquí, el universo de datos se refiere al número total de cuentas en el modelo de cuenta o al número total de UTXO en el modelo UTXO.

En el centro de nuestra prueba se encuentra un argumento teórico de la información. Un principio central de la teoría de la información, formalizado por Claude Shannon, es que si Alice elige un objeto al azar de un conjunto de tamaño 2n y desea decirle a Bob qué objeto ha elegido, debe enviarle al menos n bits. Si existe un esquema de cadena de bloques sin estado en el que los usuarios rara vez actualizan la información de sus testigos, Alice puede decirle a Bob qué objeto ha elegido con menos de n bits, lo cual es imposible, como demostró Shannon. Por lo tanto, una cadena de bloques sin estado no existe.

Para simplificar, describimos aquí una prueba de una afirmación ligeramente más débil: no existe una cadena de bloques sin estado en la que los usuarios nunca necesiten actualizar la información de sus testigos. El punto es que Alice usa un esquema blockchain sin estado para codificar su mensaje a Bob. Inicialmente, tanto Alice como Bob conocen el conjunto completo de pares de saldos de cuenta para los n usuarios. Supongamos que cada cuenta tiene al menos una moneda. Tanto Alice como Bob también conocen el estado sucinto V de la cadena de bloques sin estado y los testigos wi de todos los pares de saldos de cuentas (ai, bi). Alice y Bob también acuerdan un mapeo entre mensajes y conjuntos de cuentas. Alice elegirá un conjunto A de cuentas correspondientes a su mensaje y luego gastará monedas de esas cuentas. Ella utilizará la cadena de bloques sin estado para comunicarle a Bob el conjunto de su elección desde el cual él podrá aprender sobre ella.

Codificación: Alice gasta una moneda de cada cuenta en A. Utilizando un esquema de cadena de bloques sin estado, Alice calcula el estado actualizado V' y se lo envía a Bob.

Decodificación: para cada i, Bob comprueba si Verify(wi, (ai, bi)) es verdadero. Bob genera el conjunto de cuentas B de modo que Verify(wi, (ai, bi)) = false.

Bob genera con éxito el mismo conjunto que eligió Alice: B = A. Primero, observe que si Alice gasta una moneda de la cuenta ai, el testigo de su antiguo saldo ya no debería aceptarse; de lo contrario, Alice podría gastar dos veces. Por lo tanto, para cada cuenta ai en A, Verify(wi, (ai, bi)) = false y Bob incluirá esta cuenta en B. Por otro lado, Bob nunca incluirá en B las cuentas de las que Alice no gastó monedas, porque los saldos de estas cuentas siguen siendo los mismos y (recordemos la afirmación relajada que queremos probar) sus testigos nunca cambiarán. Por tanto, B es exactamente igual a A.

Finalmente, resolvemos nuestra contradicción calculando el número de bits que Alice debería enviar a Bob. Hay 2^n subconjuntos que puede elegir, por lo que, según la ley de Shannon, debe enviar al menos n bits a Bob. Sin embargo, sólo envía un estado V' de tamaño constante, que es mucho más corto que n bits.

Aunque utilizamos una cadena de bloques sin estado al describir nuestra prueba, Alice y Bob pueden realizar una comunicación eficiente similar utilizando una variedad de otras estructuras de datos autenticadas, incluidos acumuladores, compromisos de vectores y diccionarios autenticados. Formalizamos dichas estructuras de datos utilizando una nueva abstracción que llamamos sistema de prueba reversible.

Efecto del resultado

Nuestros resultados muestran que no se puede "eliminar criptográficamente el estado" y que no existe una fórmula mágica para un esquema de compromiso que nos permita construir una cadena de bloques sin estado donde los usuarios nunca tengan que actualizar sus testigos. El estado no desaparece, sino que se transfiere de los validadores y se envía a los usuarios en forma de frecuentes actualizaciones de testigos.

Existen otras soluciones prometedoras que se desvían del modelo blockchain estrictamente sin estado. Una relajación natural de este modelo es permitir que un tercero (ni usuarios ni validadores) sea responsable de almacenar el estado completo. Este tercero, llamado nodo de servicio de prueba, utiliza el estado completo para generar la información testigo más reciente para el usuario. Luego, los usuarios pueden realizar transacciones utilizando estos testigos como en una cadena de bloques sin estado normal, donde los validadores todavía solo almacenan el estado compacto. El mecanismo de incentivos de este sistema, especialmente cómo los usuarios compensan los nodos de prueba de servicio, es una interesante dirección de investigación abierta.

Si bien nuestra discusión hasta ahora se ha centrado en las cadenas de bloques L1, nuestros resultados también tienen implicaciones para los sistemas L2, como los servidores Rollup. Los rollups (ya sean optimistas o ZK) normalmente almacenan un compromiso con un estado grande en L1 con un valor pequeño. Este estado incluye la cuenta de cada usuario en L2. Queremos que estos usuarios puedan retirar fondos directamente en L1 (sin la cooperación de los servidores L2), publicando un testigo del saldo de su cuenta actual. Esta configuración es también un ejemplo de un sistema de prueba reversible en nuestro modelo. De hecho, se puede argumentar que las cadenas de bloques sin estado ya están implementadas en la práctica, en forma de L2 Rollups.

Desafortunadamente, sin embargo, esto significa que nuestros resultados de imposibilidad se aplican directamente. El testigo de recuperación del resumen de un usuario debe cambiar con frecuencia; de lo contrario, casi todo el estado L2 tendría que escribirse en L1. Como resultado, hoy en día los Rollups suelen asumir la existencia de un comité de disponibilidad de datos (a veces llamado "validium"), similar a un "nodo de servicio de prueba" que ayuda a los usuarios a calcular nuevos testigos cuando están listos para retirarlos. Nuestros resultados muestran que siempre se aplicará la advertencia a los usuarios en la documentación de Ethereum: "Sin datos de transacciones, los usuarios no pueden calcular pruebas de Merkle para demostrar la propiedad de los fondos y realizar retiros".