Curso intensivo de Sparse Merkle Trees

Un árbol de Merkle disperso (SMT) es una estructura de datos autenticada organizada como un árbol, construida sobre un mapa clave-valor. Un mapa clave-valor es una colección de pares (clave, valor) de modo que cada clave aparece como máximo una vez. Admite las siguientes operaciones:

• Buscar : devuelve el valor asociado con una determinada clave.
• Insertar : inserta un determinado par clave-valor en la colección.
• Actualizar : actualiza el valor asociado con una determinada clave.
• Eliminar : elimina un determinado par clave-valor de la colección.

En consecuencia, el SMT también admite estas operaciones, como se explica en la siguiente sección. El SMT se construye a partir del mapa clave-valor de la siguiente manera. Cada entrada posible del mapa clave-valor corresponde a un nodo hoja del árbol . Cada nodo hoja tiene una clave y un valor (correspondientes a la clave de entrada y el valor), así como una propiedad hash, obtenida al combinar la clave y el valor. Si una entrada no está presente en el mapa, simplemente le asignamos un nodo hoja vacío (un nodo con un valor vacío y un hash constante). La posición del nodo de la hoja en el árbol se fija mediante su clave. Por ejemplo, para una longitud de clave de 5 bits, el primer nodo hoja tiene la clave 00000, los siguientes tienen 00001, 00010 y así sucesivamente.

Los nodos de la rama principal se obtienen combinando dos nodos secundarios de forma recursiva, hasta que en la parte superior nos queda un solo nodo, la raíz de Merkle del árbol. En consecuencia, cada nodo de rama tiene un hijo izquierdo, un hijo derecho y una propiedad hash, que se obtienen al combinar los valores hash de los nodos secundarios. Como nota técnica al margen, utilizamos diferentes funciones hash para nodos hoja y rama para prevenir ataques de segundas imágenes (ver la sección de publicación del blog "Leaf versus Branch Hash"  ).

Figura 1: Un árbol Merkle escaso completo. Cada clave posible en el mapa clave-valor subyacente tiene un nodo hoja correspondiente en la capa base. Los nodos de rama (recuadros amarillos) se obtienen mediante el hash recursivo de pares de nodos de hoja (recuadros verdes), hasta que se alcanza un único nodo, la raíz de Merkle (recuadro azul). Si la longitud de la clave es de 32 bytes, el árbol tiene 256 capas (aquí elidas para mayor claridad) y 2  nodos de hoja.

Esto recuerda mucho a los árboles Merkle normales, introducidos en LIP 0031 , con una diferencia muy importante: el orden de inserción de los bloques de datos no importa y la raíz del árbol solo depende del estado final del mapa. En criptografía, esto significa que un SMT es un acumulador criptográfico [1]. Un acumulador es una función hash que posee esta independencia histórica (propiedad cuasi-conmutativa) y permite pruebas de inclusión eficientes.: un Prover puede convencer a un Verificador de que un determinado elemento está presente en la estructura de datos subyacente sin revelar ningún otro elemento, y el tamaño de la prueba se escala logarítmicamente con el número de bloques de datos. En un SMT, la entrada de la función hash es el mapa clave-valor subyacente y la salida es la raíz de Merkle. Debido a la independencia del historial, los SMT son la opción adecuada para autenticar mapas de clave-valor.

Por otro lado, un árbol Merkle regular es un ejemplo de compromiso vectorial [2], porque la estructura de datos subyacente es una matriz. Esto significa que la raíz de Merkle también autentica el orden de los bloques de datos en la matriz. Esta propiedad puede ser muy útil, por ejemplo, para autenticar las transacciones incluidas en un bloque o el orden de los mensajes entre cadenas en la solución de interoperabilidad Lisk y, en general, si estamos trabajando con arreglos. Sin embargo, la inserción de un nuevo bloque de datos en una posición específica no se puede hacer de manera eficiente, ya que sería necesario volver a calcular todo el árbol. Debido a este hecho, los árboles Merkle normales no son adecuados para autenticar mapas de clave-valor, pero son la opción adecuada para autenticar matrices, donde solo se agregan nuevos bloques de datos.

Figura 2: Comparación entre un RMT (izquierda) y un SMT (derecha). En el RMT, la estructura de datos subyacente es una matriz de bloques de datos, en este ejemplo las transacciones insertadas en un bloque. En un SMT, la estructura de datos subyacente es un mapa de clave-valor general, en este ejemplo con solo algunos pares clave-valor no vacíos. El RMT es adecuado para trabajar con una matriz, y la raíz de Merkle (cuadro azul) también autentica la orden de inserción. Un SMT es adecuado para trabajar con mapas de valores clave y la raíz de Merkle no depende del orden de inserción.

Los SMT también tienen otra propiedad interesante, ya que admiten pruebas eficientes de no inclusión : el Prover puede convencer al Verificador de que una determinada entrada no está presente en el mapa, y el tamaño de la prueba se escala logarítmicamente con el número de bloques de datos. Debido a esta propiedad, los SMT satisfacen la definición de acumuladores universales [4].

Esta herramienta puede ser útil en una variedad de situaciones: Imagine que el gobierno mantiene un registro central de todas las personas que dieron positivo a Covid en el último mes. A cada persona se le asigna una identificación que es la combinación de su número de identificación nacional y el mes actual. Luego, el registro central se organiza en un SMT, y para ingresar a un evento público, todos deben mostrar con una prueba de no inclusión que su identificación no es parte del registro central.

Sin embargo, hay un problema: como se mencionó anteriormente, el SMT contiene un nodo para cada clave posible, que para claves de 32 bytes (256 bits) da 2 nodos hoja y 256 capas. Tenga en cuenta que en cualquier escenario realista, la gran mayoría de estos nodos hoja estarían vacíos, sin una entrada asociada en el mapa subyacente (de ahí el nombre árbol de Merkle disperso ). Es imposible almacenar y manipular una cantidad tan astronómica de nodos. Por lo tanto, confiamos en las siguientes optimizaciones:

1. Cada subárbol con exactamente una hoja no vacía es reemplazado por la hoja misma.
2. Cada subárbol que contiene solo nodos vacíos se reemplaza por un nodo vacío, un nodo constante con un valor hash fijo.

La construcción resultante es similar a los árboles Jellyfish Merkle propuestos para el protocolo Diem [5]. Si las claves se distribuyen aleatoriamente, obtenemos un árbol con un número de capas que se escala como Log (N), donde N es el número de entradas en el mapa. Esto garantiza que las operaciones en el árbol toman un promedio de Log (N) pasos y las pruebas de (no) inclusión tienen un tamaño promedio de Log (N)

Figura 3: Aplicamos dos optimizaciones para reducir el número de nodos en el árbol: 1) Cualquier subárbol con exactamente 1 nodo no vacío (cuadro verde) es reemplazado por el nodo mismo. 2) Cualquier subárbol con solo nodos vacíos (recuadros blancos) se reemplaza por un nodo vacío. Los cuadros amarillos representan los nodos de las ramas.

Operaciones en el árbol

Una propiedad crucial de un SMT es la capacidad de agregar, eliminar y actualizar elementos del árbol, por ejemplo, cuando se actualiza el mapa subyacente. Para nuestros propósitos, una clave que no está presente en el mapa se puede considerar como si estuviera emparejada con un valor vacío. En este sentido, la inserción puede verse como una operación de actualización en un valor previamente vacío y la eliminación como una operación de actualización para establecer un valor en vacío.

Un acumulador que soporta estas operaciones se denomina acumulador dinámico [3], aunque estrictamente hablando en la literatura esta propiedad requiere un costo constante con el número de elementos acumulados, mientras que nosotros nos conformamos con el escalado logarítmico.

Actualizar

Siempre que queramos actualizar un nodo hoja, la estrategia general es comenzar desde la raíz y navegar por el árbol hacia abajo. La clave de la nueva hoja se usa para decidir si debemos movernos hacia la izquierda o hacia la derecha, mirando la representación binaria de la clave y moviéndonos hacia la izquierda si el siguiente dígito es un 0 o hacia la derecha si es un 1. Repetimos este proceso hasta que se encuentra una hoja o un nodo vacío. Si el nodo final tiene la misma clave de la hoja nueva, simplemente actualizamos su valor. De lo contrario, si es un nodo vacío, lo reemplazamos con la nueva hoja.

Figura 4: Para agregar un nuevo nodo de hoja al árbol (cuadro rojo punteado, clave de hoja = 5), navegamos desde la raíz a la nueva posición de hoja utilizando los dígitos de la representación binaria de la clave de hoja. Cuando se encuentra un nodo vacío (cuadro blanco), lo reemplazamos con la nueva hoja.

Si, en cambio, el nodo final es un nodo hoja, creamos nuevos nodos de rama hasta que las claves del nuevo nodo y el nodo final diverjan, y agregamos estos nodos como hijos al último nodo de rama. Los nodos vacíos se insertan como hijos de los nuevos nodos de rama según sea necesario. Finalmente actualizamos todos los nodos de sucursal que se visitaron en este proceso.

Figura 5: Para agregar un nuevo nodo de hoja al árbol (cuadro rojo punteado, clave de hoja = 3), navegamos desde la raíz a la nueva posición de hoja usando la tecla. Cuando se encuentra otro nodo de hoja (cuadro verde), creamos tantos nodos de rama como sea necesario y agregamos las dos hojas como hijos.

Generación y verificación de pruebas

La generación de una prueba funciona de manera similar. Navegamos por el árbol hasta encontrar una hoja o un nodo vacío. Si el nodo final es aquel para el que estábamos generando una prueba, tenemos una prueba de inclusión; de lo contrario, el nodo consultado no está en el árbol y tenemos una prueba de no inclusión. Los hash de los nodos hermanos no visitados que se encuentran en el proceso se entregan al Verificador como parte de la prueba. Sin embargo, no queremos agregar los nodos vacíos, ya que su valor hash es una constante de protocolo ya conocida por el Verificador. En su lugar, agregamos un mapa de bits que indica qué nodos en la ruta de inclusión no están vacíos.

Además, también admitimos techos múltiples, es decir, pruebas de (no) inclusión para varios nodos a la vez, lo que ahorra aún más espacio de prueba. En este caso, el Verificador puede volver a calcular algunos de los valores hash necesarios a partir de los elementos que ya contienen.

Por ejemplo, el ejemplo de la Figura 6, a continuación, muestra el techo múltiple para los nodos A, B, C y D (recuadros con borde rojo). Los nodos B y C son parte del árbol, mientras que los nodos A y D no lo son. Por lo tanto, el Prover devuelve una prueba de inclusión para los nodos B y C, así como el nodo vacío en la ruta del nodo A y el nodo hoja en la ruta del nodo D. El multiproof incluye todos los hashes de los nodos hermanos encontrados en la ruta. (cuadros llenos de rojo), así como un mapa de bits individual para cada nodo consultado. Por ejemplo, el mapa de bits para el nodo A sería 1011, donde el 0 indica la presencia de un nodo vacío en la ruta.

Figura 6: Un ejemplo de techo múltiple. Las claves consultadas corresponden a los nodos hoja A, B, C y D (recuadros con borde rojo). Los nodos de hoja A y D no forman parte del árbol (el borde del cuadro está discontinuo). En este caso, la prueba de no inclusión se proporciona probando la presencia de un nodo vacío u otra hoja en la ruta al nodo consultado. El Prover proporciona los valores hash de los nodos representados por recuadros rojos llenos como parte de la prueba. El Verificador puede volver a calcular la raíz de Merkle utilizando estos hash, comenzando por los nodos consultados. Los nodos vacíos en la ruta se indican mediante un mapa de bits para cada nodo consultado.

El proceso de verificación consiste en recalcular la raíz de Merkle a partir del nodo consultado, utilizando los hashes hermanos y el mapa de bits proporcionado en la prueba.

Nuevo modelo de estado

Ahora que hemos cubierto la parte técnica, analicemos cómo se utilizarán los SMT en el nuevo modelo de estado. Como se mencionó, los SMT son la opción natural para autenticar un mapa de valor clave, por lo que son la herramienta perfecta para autenticar el almacén de estado de una cadena. Creamos un SMT en la parte superior del almacén estatal, el árbol del estado , e insertamos la raíz Merkle de este árbol, la raíz del estado , en cada encabezado de bloque. Esto proporciona varios beneficios:

• Interoperabilidad: la raíz de estado se utiliza durante el procesamiento de transacciones de actualización entre cadenas para autenticar los mensajes salientes de una cadena.
• Consistencia del estado : todos los nodos de la red podrán verificar la consistencia del estado con solo verificar la raíz del estado. Por ejemplo, si un bloque contiene una transacción que acredita aleatoriamente a un usuario A o un usuario B con tokens, entonces cualquier nodo que obtenga un resultado diferente del falsificador de bloques rechazaría inmediatamente el bloque, ya que las raíces de dos estados diferirían.
• Clientes ligeros : la raíz del estado se puede utilizar para proporcionar pruebas eficientes del estado de una cuenta determinada.

Una cadena de bloques creada con Lisk SDK define una única tienda global. Cada módulo registrado en la cadena define su propio mapa genérico de clave-valor, mediante el cual cada elemento se identifica mediante las siguientes propiedades:

• ID de módulo : el ID del módulo, que identifica el mapa clave-valor. Reservaremos todos los ID de módulo que comiencen con un 0 en su representación binaria para los módulos que se envían con el SDK de forma predeterminada. Los ID de los módulos desarrollados como parte de cada aplicación de blockchain comenzarán con un 1. El ID del módulo tiene una longitud fija de 4 bytes.
• Prefijo tienda : Cada módulo puede definir varios cubos , para separar diferentes estructuras de datos dentro de la tienda. Cada segmento está identificado por el prefijo de la tienda. El prefijo de tienda tiene una longitud fija de 2 bytes.
• Clave de tienda : la clave de tienda identifica un determinado elemento dentro de un depósito de tienda.
• Esquema JSON : el esquema utilizado en el códec Lisk para serializar el valor
• 

Figura 7: Árbol de estado de una cadena de bloques Lisk. La raíz Merkle del árbol, la raíz del estado (cuadro azul), autentica el estado de la cadena. Cada módulo define su propia tienda (cajas de colores). Los módulos SDK y específicos de la aplicación se separan imponiendo que sus ID de módulo comiencen con un 0 (módulos SDK) o con un 1 (módulos de aplicación) en su representación binaria.

Cada elemento tiene un nodo hoja correspondiente en el árbol de estado, con las siguientes propiedades:

• Clave : La clave de un nodo hoja es la concatenación del ID de módulo, el prefijo de la tienda y el hash de la clave de la tienda. Anteponer la ID del módulo permite separar diferentes subárboles para cada módulo, mientras que el prefijo de tienda separa diferentes subárboles de cubeta dentro de un subárbol de módulo. La clave de la tienda tiene un hash para garantizar que los nodos hoja se distribuyan aleatoriamente dentro de un determinado segmento de tienda. El hash de la clave de la tienda también fija la longitud de una clave de hoja en 4 + 2 + 32 = 38 bytes. Como consecuencia, el árbol de estado tiene como máximo 38 * 8 = 304 capas, aunque es muy poco probable que este sea el caso dadas nuestras optimizaciones.
• Valor : el valor viene dado por el hash del valor del elemento.
• Hash : el hash es igual al hash de la hoja de clave y valor.

El hash de la clave de la tienda y los valores al crear un nodo hoja tiene la ventaja adicional de no tener que revelar la clave real y el valor de la entrada en el mapa subyacente al crear una prueba de no inclusión.

Figura 8: Ampliación del estado del módulo de token. Los saldos de los usuarios se almacenan en depósitos de la tienda de usuarios , mientras que la información sobre los tokens nativos enviados a otras cadenas se almacena en la tienda de depósito en garantía. La clave del nodo hoja correspondiente viene dada por la concatenación del ID del módulo de token (4 bytes = 32 capas), el prefijo de la tienda de la tienda del usuario (2 bytes = 16 capas) y el hash de la clave de la tienda (32 bytes, Log (N) capas debido a las optimizaciones). Para la tienda del usuario, la clave de la tienda viene dada por la concatenación de la dirección del usuario y el identificador del token. El valor se serializa utilizando el esquema de almacenamiento del usuario . Para la tienda de depósito en garantía, la clave de la tienda viene dada por el ID de la cadena. El valor se serializa utilizando el esquema de depósito en garantía .

Esta nueva arquitectura de estado es sustancialmente diferente de la definida en LIP 0030 . Anteriormente, el estado de una cadena se organizaba por cuenta en lugar de por módulo . Por ejemplo, el saldo de un usuario se almacenaría junto con todas las demás propiedades relacionadas con ese usuario específico (ver ejemplo en LIP 0030 ). En cambio, en este nuevo modelo de estado, el saldo de un usuario se almacena en el estado del módulo de token, separado de todas las demás propiedades.

Separar el almacén de estado en varios mapas de valores clave nos permite compartimentar lógicamente cada módulo, siguiendo el mismo mantra detrás de nuestra arquitectura de cadena: cada módulo define su parte del estado y sus propias transiciones de estado :

• Estado del módulo : los pares clave-valor almacenados en el mapa del módulo. Por ejemplo, el saldo del usuario y las cuentas de depósito en garantía almacenadas en el módulo de token.
• Transiciones de estado del módulo : las transacciones definidas en un módulo (por ejemplo, la transacción de transferencia de token en el módulo de token), así como la lógica ejecutada con cada bloque o transacciones, como la recompensa asignada al falsificador después de que se ha procesado un bloque.

Novedades para desarrolladores

En la versión 5 del SDK, al crear un nuevo módulo, los desarrolladores deben especificar los esquemas JSON utilizados para serializar estructuras de datos con el códec Lisk . En la próxima iteración del SDK, los desarrolladores definirán el prefijo de la tienda, la clave de la tienda y el esquema JSON para cada estructura de datos en su módulo personalizado. Si necesita inspiración, consulte el módulo de interoperabilidad LIP .

Conclusión

LIP 0039 introduce árboles de Merkle dispersos al protocolo Lisk. La nueva versión del SDK implementará árboles de Merkle dispersos para autenticar el estado de la cadena de bloques en la raíz del estado, como se especifica en LIP "Modelo de estado y raíz del estado" . Como tal, los árboles de Merkle dispersos serán una piedra angular de la interoperabilidad de Lisk, pero en el futuro también podrían usarse en otras partes del protocolo.

Para más preguntas y comentarios sobre el tema, organizaremos un AMA en Lisk.chat con Alessandro Ricottone (Investigador científico), el próximo viernes 25 de junio a las 4 pm CEST. También invitamos a todos los miembros de la comunidad a que vayan al foro de Lisk Research, donde siempre nos complace escuchar sus comentarios y participar en discusiones sobre este y otros temas.

Referencias externas

[1]:  https://cs.nyu.edu/~fazio/research/publications/accumulators.pdf

[2]:  https://eprint.iacr.org/2011/495.pdf

[3]:  https://link.springer.com/chapter/10.1007/3-540-45708-9_5

[4]:  https://link.springer.com/chapter/10.1007/978-3-540-72738-5_17

[5]:  https://diem-developers-components.netlify.app/papers/jellyfish-merkle-tree/2021-01-14.pdf

• Fuente: blog de Lisk,

•