Antecedentes y motivación

Antes de comenzar a hablar sobre mejoras en MPT, hablemos primero de los antecedentes para realizar esta investigación.

Estoy estudiando un doctorado y haciendo diseño de cadenas públicas. Además de la actualización de consenso central de esta cadena pública: prueba de trabajo útil, otra tarea importante es implementar un sistema de contrato inteligente compatible con ETH. Actualmente implementamos una máquina virtual basada en el código de bytes de Python, la integramos en un sistema de contrato blockchain y, sorprendentemente, la hicimos compatible con Ethereum RPC. Usamos Python para construir un contrato inteligente que cumpla con el estándar ERC20 para pruebas. Naturalmente, necesitamos implementar un mecanismo de datos KV que pueda transportar decenas de millones de usuarios en el nivel inferior de ejecución del contrato (similar a Mapping in Solidity). se utiliza para almacenar cada La cantidad de tokens en la cuenta, puede haber cientos de millones de dichas cuentas).

A continuación, el contenido del trabajo del diseño de la cadena pública naturalmente toca conceptos como MPT y trie. Nos referimos al diseño de Ethereum, Threetrees, trie, MPT, etc.

Encuentra cuellos de botella

Afortunadamente, antes de que estuviéramos listos para implementar el contrato inteligente para llamar a MPT, de repente ejecutamos un programa de referencia de árbol MPT simple en el servidor de AWS. Después de intentar utilizar Trie y MPT para insertar un volumen de datos de 100 millones de KV, nos sorprendió mucho obtener el resultado: el rendimiento del árbol MPT era realmente muy bajo.

Al ejecutar el siguiente código, observamos que: insertar 10 millones de pares clave-valor de KV en Rocksdb lleva unos minutos para Trie y unas horas para MPT. Cuando aumentamos la magnitud de los datos de prueba a 100 millones, el insertador de MPT tarda varios días en ejecutarse. Esto significa que cuando la cadena de bloques utilice la estructura de datos MPT para ejecutar contratos inteligentes, la velocidad también será muy limitada.

Los experimentos han demostrado que la sobrecarga causada por el uso de la estructura de datos MPT no solo ralentizará la velocidad de ejecución de los contratos inteligentes, sino que también reducirá la velocidad de sincronización de los nodos de blockchain (incluso cuando el ancho de banda es suficiente, descargar datos de otros nodos y reconstruirlos). nodos, también debe tardar varios días). Sin embargo, dado que el diseño de la estructura de datos de Ethereum es difícil de modificar, incluso si lo reescribimos u optimizamos con un lenguaje de programación "más rápido", si la estructura de datos subyacente no se actualiza, será difícil para la cadena de bloques superar las limitaciones de rendimiento.

prueba_mpt_write.py

prueba_mpt_write.py

Todavía recuerdo que cuando aprendí a escribir código por primera vez, los profesores nos dijeron un principio básico: programa = algoritmo + estructura de datos. Si limitamos la estructura de datos, incluso si optimizamos desesperadamente el algoritmo (que a menudo requiere varios años de esfuerzos académicos y, en muchos casos, es casi imposible mejorar), será difícil superar las limitaciones de rendimiento del sistema actual. estructura de datos. Por lo tanto, un plan de mejora muy académico, que busca un algoritmo de reemplazo de MPT con mejor rendimiento, puede llevar varios años de investigación. Como predecesor que trabaja en esta dirección, Verkle Tree utiliza métodos polinomiales para optimizar la estructura de datos de blockchain. Probaremos algunas ideas más únicas y simples.

Si utilizamos el pensamiento de primeros principios, ¿no podemos utilizar MPT? Si podemos evitar MPT e implementar contratos inteligentes directamente en Trie, ya no habrá sobrecarga causada por MPT (el primer principio de Ma Yilong, algo que no existe no tendrá sobrecarga de rendimiento).

Como precio, es posible que nuestra solución recién diseñada no sea directamente compatible con el MPT existente, pero como la interfaz Ethereum RPC no se modifica, se puede reutilizar gran parte de la infraestructura existente de Ethereum: como Etherjs y MetaMask. Omitir MPT pertenece a la optimización de la estructura de datos interna, que es una exploración gratuita del rendimiento de blockchain.

conocimientos previos

Rocksdb y Trie

El árbol del diccionario Trie es una estructura de datos de árbol avanzada mencionada en los libros de texto universitarios. En el video del profesor Xiao, MPT se basa en el árbol del diccionario Trie. Podemos pensar que el entorno de implementación de Trie está en la memoria.

Sin embargo, en nuestra ingeniería, no podemos usar Trie directamente para implementar el producto directamente, porque también necesitamos conservar los datos en el disco duro. Este paso requiere mucha optimización de ingeniería, por lo que generalmente implementamos el árbol MPT basado en Rocksdb.

Rocksdb es la bifurcación de código abierto de FB basada enleveldb y usa LSMT en la parte inferior (consulte el artículo The log-structured merge-tree). Desde un punto de vista abstracto, podemos pensar en Rocksdb como un árbol de diccionario optimizado y persistente.

El uso básico de Rocksdb es muy simple. Utiliza principalmente tres operaciones básicas: Obtener y consultar por prefijo Iterar.

máquina de estados

La máquina de estados es una herramienta que la gente suele utilizar para modelar cadenas de bloques. Es muy simple: agregue una entrada a un estado original para obtener un nuevo estado.

El estado global de Ethereum puede entenderse como el estado de una máquina de estado. Por ejemplo, en el bloque 1, los valores KV de todos los contratos inteligentes son un estado global. Todas las transacciones en un bloque son ejecutadas por EVM y pueden entenderse. como una máquina de estado, como una llamada de contrato Mint, hace que el Saldo de un usuario y las variables Total del contrato cambien a 1000 en el bloque 2.

Un concepto de máquina de estados que se pasa por alto fácilmente se llama función de transición de estado, que define reglas de entrada cuando la entrada no es razonable, la información de entrada será rechazada. Por ejemplo, cuando intentamos transferir una cantidad negativa a otra persona, dicha transacción no se ejecutará (por supuesto, un contrato inteligente con errores puede aceptar dicha transacción. En ETH, la función de transición de estado puede ejecutarla automáticamente a través de un Turing -lenguaje completo.

Introducción a la MPT

Quizás haya oído hablar de los tres árboles de Ethereum: el árbol de transacciones, el árbol de estado y el árbol de recibos. Todos son árboles MPT, cuyo nombre completo es Merkle Patricia Tries. Entre ellos, el árbol de estado es probablemente el mejor caso de uso para utilizar la estructura de datos MPT. Para obtener más detalles, consulte la explicación en video del maestro Xiao.

El árbol MPT se basa en la estructura de datos Trie y puede calcular todos los datos de estado en un hash raíz como un árbol Merkle y colocarlo en el encabezado del bloque Ethereum. Hay tres hashes raíz de árboles MPT en el encabezado del bloque Ethereum, que normalmente llamamos tres árboles.

¿Es posible no colocar la raíz del estado global en el encabezado del bloque? Sí, las transacciones se colocan en bloques de Bitcoin y la raíz Merkle de la transacción se coloca en el encabezado del bloque (se usa un árbol Merkle, pero no se usa MPT). Pero Bitcoin no tiene contratos inteligentes como Ethereum, ni tiene el concepto de estado global. Cuando Ethereum diseñó inicialmente la cadena de bloques con contratos inteligentes, abandonó el diseño de bloque de 1 M de Bitcoin y UTXO, eligió la estructura de datos y el modelo de cuenta MPT y utilizó Gas para resolver el problema del tiempo de inactividad, satisfaciendo las necesidades de los contratos inteligentes durante la operación global. estado.

Entonces, ¿cuál es el objetivo de utilizar MPT en Ethereum?

  1. Encuentre el estado correspondiente de la cadena de bloques a través de la raíz de Merkle en el encabezado del bloque.

  2. Ahorra espacio ocupado por datos duplicados.

  3. El estado correcto se puede verificar mediante el hash raíz.

El primer punto es un requisito estricto. Es necesario leer varios estados mientras se ejecuta EVM. Si se utiliza un patrón de diseño similar a Bitcoin UTXO, es necesario rastrear muchos bloques para obtener el estado del saldo de la cuenta de un determinado usuario. El uso de MPT satisface muy bien las necesidades.

Punto 2, MPT ahorra espacio y el estado de la cadena de bloques puede considerarse como un diccionario enorme. En cada bloque, solo se actualiza una pequeña parte de las claves y la mayoría de las claves aún mantienen sus valores originales. Con el árbol MPT, solo puede actualizar los valores clave que deben actualizarse, sin copiar el estado sin cambios en cada bloque.

Punto 3: La ventaja de MPT es que la verificación del estado global se ha completado utilizando el valor de la clave de estado al que accede el hash raíz. Esta es también la razón principal por la que escribir el árbol MPT lleva mucho tiempo. Si no se utiliza MPT, los nodos aún pueden verificar la coherencia de los datos durante la sincronización de bloques.

Al completar los puntos 1 y 2 sin usar MPT, podemos evitar la sobrecarga de MPT. Por lo tanto, necesitamos diseñar una solución basada en Trie (puede entenderse como Rocksdb) para almacenar los datos de estado de la cadena de bloques.

diseño

Principalmente diseñamos una solución basada en Trie para almacenar el estado en cadena. De acuerdo con los primeros principios, si no hay una estructura de datos MPT, no se requiere una sobrecarga del sistema para ejecutar MPT. Siempre que el sistema de contrato inteligente basado en Trie se pueda implementar y ejecutar correctamente, significa que la optimización se ha completado. En la práctica, podemos pensar en Rocksdb como un Trie. Una comprensión más simple es que es una base de datos KV de alto rendimiento.

Utilice [estado global como prefijo_contrato dirección_variable nombre_altura del bloque_hash del bloque] como valor clave de la base de datos KV, como el siguiente formato. Entre ellos, 0x1 es la dirección del contrato, Total es el nombre de la variable, 1 es la altura del bloque y ABC1234 es el valor hash del bloque (se omitirá más adelante).

estado global_0x1_total_1_abc1234

En Ethereum Solidity, las variables se pueden definir como Memoria, Almacenamiento y Datos de llamada. Nos centramos principalmente en el tipo de Almacenamiento porque se almacenará en el estado global. Además de las variables simples, también consideramos el mapeo. Debido a que el orden de magnitud de los usuarios en la cadena de bloques es global, habrá un mapeo KV extremadamente grande. Además, trataremos los tipos de datos como Array como estructuras de datos simples y los almacenaremos directamente en Json en Rocksdb. Cuando codificamos, naturalmente debemos estimar la magnitud de los datos de valor en la estructura de datos KV para elegir un método de almacenamiento apropiado.

Variables de estado de almacenamiento de contrato

¿Cómo podemos lograr el primer y segundo objetivo de diseño de MPT sin utilizar MPT?

Supongamos que tenemos una variable Total en el contrato ERC20. Esta variable solo cambiará cuando el número total de Tokens aumente (Mint) o disminuya (Burn), pero el valor de Total permanece cuando el usuario A transfiere dinero (Transfer) al usuario B. constante.

Para simplificar, supongamos que la dirección del contrato es 0x1. Cuando la altura del bloque es 1, el propietario del contrato realizó un Mint 2000. En bloques con una altura de 2 a 8, el usuario realizó múltiples transferencias. La altura del bloque actual es 9. .

En este punto, solo necesitamos consultar en la base de datos la clave con el prefijo [globalstate_0x1_total_]. Aunque nuestro último bloque actual es el 9, dado que la variable Total no ha cambiado en los bloques 2-8, el primer resultado de la consulta anterior será el valor de [globalstate_0x1_total_1], por lo que encontramos el último valor de la variable Total, el Total variable que cambió en el bloque 1.

En este momento, se genera un nuevo bloque. Supongamos que el usuario realiza Mint dos veces más en el bloque 9 y en el bloque 11. Aquí encontramos una característica de Rocksdb si tenemos la siguiente clave.

estado_global_0x1_total_1 : 2000

estado_global_0x1_total_9 : 4000

estado_global_0x1_total_11 : 6000

Entonces el primer resultado de la búsqueda siempre será el bloque 1, no el último bloque 11. Debido a que aún no hemos encontrado un parámetro para cambiar el orden de los resultados de búsqueda en la documentación de Rocksdb, usamos un pequeño truco: usamos un número mayor, como 100, para restar la altura del bloque (en realidad, será mucho mayor) y lo rellenamos. con ceros, por lo que los últimos bloques ocuparán el primer lugar en los resultados de búsqueda.

estado_global_0x1_total_089 : 6000

estado_global_0x1_total_091 : 4000

estado_global_0x1_total_099 : 2000

Tipo de asignación de almacenamiento

Como mencionamos anteriormente, la magnitud de la clave de la estructura de datos del Mapping puede ser enorme, por lo que es imposible para nosotros convertir el diccionario Json de decenas de miles de claves en el Mapping en una cadena. De lo contrario, el costo de agregar y eliminar claves. , o modificar los Valores será muy alto.

Suponiendo que la dirección del usuario es 0x2, ampliamos ligeramente el formato de clave de almacenamiento anterior:

[globalstate_0x1_[balance_0x2]_2] : 2000

El [nombre de variable] anterior aquí se ha ampliado a [nombre de variable + Clave del diccionario de mapeo]

Los datos anteriores representan que el saldo del usuario 0x2 en la altura del bloque 2 es 2000. Si no hay datos actualizados para cubrir el saldo actual, entonces los datos del usuario en el bloque 2 representan el estado más reciente.

estado_global_0x1_balance_0x2_098 : 2000

estado_global_0x1_total_0x1_099 : 2000

Verificar bloque

Al igual que la raíz del árbol Merkle, la raíz del árbol MPT también representa una verificación del estado global. Siempre que podamos garantizar la coherencia de los datos del bloque, si debemos usar MPT y escribir Root en el encabezado del bloque es una opción de diseño.

Hemos realizado algunas mejoras en el diseño del bloque para que el encabezado del bloque contenga dos cuerpos, uno es el bloque de datos de la transacción y el otro es el bloque de datos de actualización del estado.

El bloque de datos de transacción contiene el hash de todas las transacciones. Los mineros o nodos pueden comenzar desde el estado global de una determinada altura de bloque, ejecutar todas las transacciones en el orden indicado en el bloque de datos de transacción y obtener el estado global del siguiente bloque. Si el volumen de transacciones es grande, la ejecución paralela es poco probable (porque se alterará el orden de las transacciones), por lo que llevaría más tiempo requerir que nodos de todo el mundo ejecuten todas las transacciones.

Con este fin, diseñamos un bloque de datos de actualización de estado, que incluye los valores de clave de estado global actualizados después de ejecutar todas las transacciones. Si es un nodo que está muchos bloques detrás, además de ejecutar una máquina virtual para ejecutar todas las transacciones, también puede actualizar el contenido del Cuerpo según el estado e insertar valores clave directamente en la base de datos para ahorrar potencia informática. y acortar el tiempo de sincronización.

Por supuesto, los valores clave utilizados para realizar todas las actualizaciones de transacciones deben ser exactamente los mismos que el Diff contenido en el bloque de actualización de estado; de lo contrario, este nuevo bloque será ilegal.

Supongamos que hay 10,000 nodos en el mundo. Cuando tiramos un dado y establecemos una probabilidad del 1% para ejecutar una transacción, alrededor de 100 nodos ejecutarán la transacción entre bloques y otros nodos dependerán del contenido de la actualización del estado de la conexión. bloque de datos Entonces esta área Muchos nodos en el sistema blockchain podrán guardar muchas operaciones repetidas.

lograr

Después de completar el diseño anterior, inmediatamente comenzamos a implementar esta idea.

Primero, integramos la máquina virtual Python en el sistema blockchain. Esta es una máquina virtual Python implementada en Python, que actualmente es compatible con el código de bytes PY 3.10. Esperamos que los contratos inteligentes puedan usar parte de la sintaxis de Python. Por ejemplo, solo necesitamos funciones y no queremos que los desarrolladores usen Class, por lo que actualmente no admitimos completamente todos los códigos de bytes de PY.

En cuanto al compilador, Solidity necesita desarrollar un compilador dedicado para convertir el código fuente en código de bytes EVM. Usando Python, puedes convertir fácilmente el código fuente de Python en código de bytes PY con la ayuda de este excelente lenguaje de infraestructura con una historia de treinta años. Los usuarios apenas notarán el tiempo de compilación.

Nuestro repositorio de códigos de VM es el siguiente. Todos pueden darnos sus opiniones y solucionar posibles problemas de seguridad:

Enlace: https://github.com/EcoPoW/python_stf_vm En el segundo paso, desarrollamos una versión Python de ERC20 y el código se actualiza constantemente. A diferencia de Solidity, no usamos palabras clave para identificar cómo se almacenan las variables, todas las variables locales están en la memoria y usamos las funciones globales _get y _put para leer y escribir el estado. Enlace: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

https://github.com/EcoPoW/BitPoW/blob/master/state.py

Implementación y mejora

Nos tomó alrededor de dos meses desde que planteamos las preguntas hasta el diseño y la implementación de la codificación.

Después de todo un verano de diseño + codificación real, el nuevo sistema de contrato inteligente, que solo usa el árbol de diccionario Trie sin depender de la estructura de datos MPT, está listo para ejecutarse (puede intentar ejecutar el nodo de prueba localmente a través del clon de Github). Evitar el almacenamiento de contratos inteligentes basado en MPT significa que, con suficiente ancho de banda, el tiempo de sincronización de un nodo con un tamaño de 100 millones de KV se puede reducir de varios días a unos pocos minutos. La eficiencia de ejecución de los contratos inteligentes también será más rápida y una mayor parte de los cálculos consumidos por la CPU se utilizarán para ejecutar el código de bytes en lugar de las operaciones hash necesarias para construir el árbol Merkle. Tuvimos suerte de que al implementar contratos inteligentes en el proyecto, no seguimos directamente el diseño "estándar de la industria", sino que primero intentamos la optimización y la resta, y obtuvimos una cadena de bloques de contratos inteligentes con la "estructura de datos" correcta. Porque a diferencia de los productos Web2, que comparamos con cambiar neumáticos mientras se conduce un automóvil, la cadena de bloques Web3 se parece más al lanzamiento de un cohete. Es difícil realizar mejoras estructurales importantes en una cadena de bloques en funcionamiento, por lo que sólo podemos mejorar el "siguiente" sistema y estar completamente preparados antes de conectarnos.

En la actualidad, se ha implementado la red de prueba Testnet2 de la cadena de bloques BitPoW que diseñamos. Todos pueden usar MetaMask para conectarse a esta cadena de bloques a través de RPC para probar y probar transferencias ERC20 basadas en Python VM. Al mismo tiempo, todavía tenemos mucho trabajo por hacer y todavía necesitamos confiar en la comunidad para promover esta nueva infraestructura blockchain.

Invitamos a todos a conocer y probar la implementación de estas nuevas tecnologías basadas en conceptos, incluidas las pruebas de rendimiento después de eliminar MPT y las pruebas de seguridad de nuevos contratos inteligentes y nuevas cadenas.

Resumir

Hasta ahora, hemos pasado por alto MPT y hemos diseñado una solución de almacenamiento de contrato inteligente basada directamente en Trie. Actualmente implementamos esta mejora en una cadena de bloques basada en Python vm como prueba de viabilidad. Nos tomó alrededor de tres meses desde descubrir el problema hasta proponer una solución e implementarla en código. Pero lo más importante de este estudio es que, como mucha gente común, después de aprender el conocimiento de MPT en el aula, no pensamos más en ello. mejorándolo. La solución no es complicada, pero requiere práctica y acción. La solución no es complicada, pero requiere práctica y acción. Sólo pensando activamente en la práctica podemos encontrar inspiración y seguir innovando. Estoy muy agradecido con LXDAO por apoyar esta investigación y espero encontrar más amigos en la comunidad que estén interesados ​​en la capa inferior de blockchain. La industria aún es muy temprana y la infraestructura está lejos de estar madura. Esperamos promover la popularización del conocimiento subyacente de blockchain para que más personas puedan participar en la vanguardia de la innovación tecnológica.