a16z: Por qué no pueden existir cadenas de bloques sin estado

Autor: Miranda Christ (estudiante de doctorado en informática en la Universidad de Columbia/pasante de investigación de cifrado a16z), Joseph Bonneau (a16zcrypto) Fuente: a16z crypto; Compilador: Yvonne, MarsBit

A medida que la cadena de bloques admite más usuarios y transacciones más frecuentes, crece la cantidad de información ("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.

Esta carga de almacenamiento se volvería inmanejable para una cadena de bloques con suficientes cuentas o UTXO para respaldar las transacciones diarias reales de la mayoría de las personas, lo que dificultaría ser un validador y una amenaza para la descentralización. Es tentador considerar la criptografía como una solución, y herramientas como los árboles Merkle y las pruebas de conocimiento cero nos han ayudado a alcanzar objetivos que antes eran increíbles.

Este es exactamente el objetivo de una "cadena de bloques sin estado". Sin embargo, a pesar de una gran cantidad de trabajo en este ámbito, todavía están lejos de ser prácticos. Pero resulta que este retraso en el progreso es inherente: la brecha entre estas estructuras y la practicidad nunca podrá salvarse. Nuestro trabajo reciente muestra que cualquier esquema de blockchain sin estado, por inteligente que sea, no es factible sin medidas adicionales para gestionar el estado. Como demostramos al final de este artículo, este resultado improbable no debería ser desalentador.

estado sin estado

Hoy en día, el tamaño del Estado es grande 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), que actualmente es inaceptablemente bajo. Según el diseño actual, el estado necesario para soportar verdaderamente las transacciones diarias (cientos de miles a millones de TPS) se volverá inmanejable y requerirá el uso de varios terabytes o incluso petabytes de espacio de almacenamiento.

Esto ha llevado a la gente a buscar formas técnicas de reducir drásticamente la cantidad de estado requerida por los validadores: una cadena de bloques sin estado requeriría que los validadores solo almacenen un estado de tamaño constante, independientemente del rendimiento de la transacción. (En realidad, el término es inapropiado: todavía hay un estado, lo suficientemente pequeño como para acomodar cualquier rendimiento futuro, a menudo de tamaño constante.) Este requisito de almacenamiento liviano hará que sea más fácil ejecutar nodos de validación; de manera optimista, todos pueden ejecutar un nodo en su teléfono. Dado que aumentar el número de validadores aumentará la seguridad de la cadena, es importante reducir las barreras de entrada para los validadores.

A pesar de una gran cantidad de investigaciones sobre cadenas de bloques sin estado (por ejemplo, Todd, Buterin, Boneh et al., 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 del usuario y su saldo están incluidos en el compromiso estatal global. Cuando un usuario realiza una transacción, envía este testigo a un validador, lo que demuestra que su cuenta tiene saldo suficiente.

A diferencia del almacenamiento de claves privadas que nunca necesitan cambiarse, 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 tuviera que monitorear constantemente todas las demás transacciones con tarjetas de crédito a nivel mundial y actualizar 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 permanecer fuera de línea e interactuar con la cadena de bloques solo cuando envían transacciones. En muchos casos, como en las carteras de hardware, actualizar los testigos no sólo es inconveniente, sino imposible.

Esto lleva a una pregunta de investigación natural: ¿Podemos construir una cadena de bloques sin estado que no necesite actualizar testigos (o que rara vez necesite actualizar testigos)? Para responder a esta pregunta, desarrollamos un nuevo marco teórico (que puede ser un sistema de prueba de revocación), que generaliza las cadenas de bloques sin estado. Utilizando este marco, demostramos un resultado concluyentemente imposible: la compensación entre un estado global compacto y actualizaciones frecuentes de testigos es fundamental. 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 estructura de blockchain sin estado y la practicidad nunca se cerrará.

Antecedentes de la investigación

Para ayudar a desarrollar la intuición para resultados imposibles, primero describiremos la construcción natural pero ineficiente de una cadena de bloques sin estado utilizando árboles Merkle. Nuestro objetivo es que los validadores determinen si una transacción enviada por un usuario es válida; por ejemplo, si el usuario tiene un saldo de cuenta lo suficientemente grande como 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 una 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 el conjunto de pares de saldos de cuentas. Cada usuario mantiene su prueba Merkle de inclusión del par (ID de cuenta, saldo) como testigo. La prueba de Merkle de inclusión de una hoja (a, b) consta de nodos asociados (v 1,…, vk) a lo largo de su camino hacia la raíz del árbol. Dada una transacción realizada por un usuario que utiliza la cuenta a y reclama un saldo b, un validador puede comprobar que b es efectivamente el saldo de la cuenta a comprobando que (a, b) demuestra (v 1,…, vk) con su estado actual V . Si es así, el validador ejecutará la transacción y deberá actualizar el saldo de la cuenta en consecuencia. Una propiedad conveniente de los árboles Merkle es que, dada la prueba de contención de Merkle de una hoja, es fácil calcular la raíz resultante cuando esa hoja cambia. En otras palabras, un validador 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.

El enfoque del árbol de Merkle tiene dos inconvenientes importantes. Primero, la cantidad de testigos de usuarios es relativamente grande y crece logarítmicamente en la cantidad total de cuentas en el sistema. Idealmente, deberían tener un tamaño constante, lo que podemos lograr utilizando esquemas como los acumuladores RSA (Boneh et al. en el contexto de blockchains sin estado).

La segunda desventaja es más difícil de evitar: cada vez que otros usuarios realizan una transacción, la prueba del par cuenta-saldo cambia. Recuerde que la prueba de una hoja consta de nodos asociados en el camino desde esa hoja hasta la raíz del árbol. Si alguna otra hoja cambia, uno de estos nodos cambia, causando problemas en la práctica. La mayoría de los usuarios de blockchain quieren mantener pasivamente sus monedas en una billetera, iniciando sesión solo cuando quieren realizar una transacción. Sin embargo, en la práctica de esta cadena de bloques sin estado, los usuarios deben monitorear constantemente las transacciones de otras personas para mantener actualizados a sus testigos. (Aunque terceros pueden realizar este monitoreo en nombre de los usuarios, esto se desvía del modelo estándar de blockchain sin estado. Discutiremos este tema al final de este artículo.) De hecho, este es un problema para las blockchains sin estado. Un desafío insuperable que supone una pesada carga para los usuarios.

Nuestra conclusión: la apatridia es imposible

Este fenómeno no es exclusivo de las estructuras de árbol de Merkle: todos los esquemas de blockchain sin estado conocidos requieren que los usuarios actualicen sus testigos con frecuencia. Lo ilustramos en este artículo. Más precisamente, mostramos que la cantidad de usuarios que deben actualizar su testigo 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 ha realizado ninguna transacción, es posible que su 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 siguiendo el teorema siguiente, junto con la cantidad de cambios de testigo necesarios por día para cadenas de bloques de diferentes rendimientos. Estos gráficos muestran cuántas veces debe cambiar el testigo para lograr una cadena de bloques sin estado óptima. Aquí, el campo de datos se refiere al número total de cuentas (en el modelo de cuenta) o 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 propuesto 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 a sus testigos, entonces Alice puede decirle a Bob qué objeto ha elegido en menos de n bits; Shannon demuestra que esto es imposible. Por lo tanto, una cadena de bloques sin estado no puede existir.

Para simplificar, describiremos aquí una prueba de una afirmación ligeramente más débil: no puede haber una cadena de bloques sin estado donde los usuarios nunca necesiten actualizar sus testigos. La idea clave es que Alice codifica su mensaje a Bob utilizando un esquema blockchain sin estado. Inicialmente, tanto Alice como Bob conocen los pares completos de saldos de cuenta de 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ía un conjunto de cuentas A correspondientes a su mensaje y gastaría tokens de esas cuentas. Ella utilizará la cadena de bloques sin estado para comunicar con Bob el conjunto que elija, y de ese conjunto él podrá aprender cuáles son sus mensajes.

Codificación: Alice gasta una ficha de cada una de las cuentas de A. Utilizando un esquema de cadena de bloques sin estado, Alice calcula un estado actualizado V' y envía V' a Bob.

Decodificación: Para cada i, Bob verifica si Verify( wi , ( ai , bi )) . 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 ha gastado un token de la cuenta ai, no se deben aceptar más testigos de su saldo anterior; de lo contrario, Alice podría gastar el doble. Por lo tanto, para cada cuenta ai en A, Verificar( wi , ( ai , bi )) = false y Bob incluirá esa cuenta en B. Por otro lado, Bob nunca incluirá en B la cuenta identificada por Alice. No hay forma de gastar una moneda, porque los saldos de estas cuentas siguen siendo los mismos y (recordemos la declaración vaga que intentábamos probar) sus testigos nunca cambian. Por tanto, B es exactamente igual a A.

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

(Los lectores familiarizados con la criptografía pueden notar que aquí pasamos por alto algunos detalles; por ejemplo, la decodificación de Bob falla con una probabilidad insignificante. Nuestro artículo incluye una prueba completa).

Si bien describimos nuestras pruebas en términos de cadenas de bloques sin estado, Alice y Bob pueden realizar una comunicación similar demasiado eficiente utilizando otras estructuras de datos autenticadas (por ejemplo, acumuladores, compromisos de vectores). Formalizamos dichas estructuras de datos utilizando una nueva abstracción, a la que llamamos sistemas de prueba reversibles.

IMPACTO DE LOS RESULTADOS

Nuestros resultados muestran que no se puede "cifrar el estado": no existe una solución mágica 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 del validador al usuario y se envía al usuario en forma de testigos actualizados con frecuencia.

Existen algunas soluciones potenciales, pero rompen con el modelo blockchain estrictamente sin estado. Este modelo permite que un tercero (ni un usuario ni un validador) sea responsable de almacenar el estado completo. Esta parte se denomina Nodo de servicio de prueba (con los controles más estrictos realizados por Srinivasan et al.) y utiliza el estado completo para generar testigos actualizados en nombre de los usuarios. Luego, los usuarios pueden usar estos testigos para realizar transacciones, como en una cadena de bloques sin estado normal, donde los validadores solo almacenan un estado compacto. El mecanismo de incentivos del 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 acumulativos. Un resumen (ya sea optimista o ZK) normalmente toma un estado grande y lo confirma utilizando un valor pequeño almacenado en L1. 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 del sistema de prueba reversible en nuestro modelo. De hecho, se podría argumentar que las cadenas de bloques sin estado ya se implementan en la práctica en forma de paquetes acumulativos L2.

Desafortunadamente, esto significa que nuestros resultados de imposibilidad se aplican directamente. El testigo de retiro acumulativo de un usuario debe cambiar con frecuencia; de lo contrario, casi todo el estado L2 tendría que escribirse en L1. Como resultado, las colecciones actuales suelen asumir un comité de disponibilidad de datos (a veces llamado "comité de validez") que funciona como un "nodo de servicio de pruebas" que ayuda a los usuarios a calcular nuevos testigos cuando están listos para salir. Nuestros hallazgos sugieren que las advertencias a los usuarios en la documentación de Ethereum (“Sin acceso a los datos de las transacciones, los usuarios no pueden calcular las pruebas de Merkle necesarias para demostrar la propiedad de los fondos y realizar retiros”) siempre se aplicarán.

A medida que se desarrollen los sistemas blockchain, será aún más importante desarrollar formas más eficientes de gestionar el estado de la cadena de bloques. Aunque nuestros resultados para excluir cadenas de bloques sin estado pueden parecer negativos, los resultados de imposibilidad son útiles para los diseñadores de cadenas de bloques, ya que nos dicen que centremos nuestra investigación en otra parte, idealmente ayudándonos a encontrar soluciones viables más rápido.