Presentamos Lisk Tree

octubre 04, 2020 VICTOR HUGO LAZARTE 0 Comments

 


Introducción

Si está interesado en blockchains y criptomonedas, es probable que se haya topado con árboles Merkle (también conocidos como árboles hash). Vale la pena señalar que casi todos los proyectos de blockchain utilizan árboles Merkle como parte de sus protocolos. En la versión 5.0.0 del Lisk SDK, presentamos lisk-tree, la nueva biblioteca que manejará los árboles Merkle en el protocolo Lisk. 

Esta entrada de blog se puede dividir en 2 secciones. La primera sección está diseñada para proporcionar un curso intensivo sobre los árboles de Merkle, que cubre los conceptos más importantes, como las raíces de Merkle y las pruebas de inclusión. En la segunda sección, presentamos lisk-tree, describimos cómo se implementan los árboles Merkle en Lisk y finalmente explicamos las mejoras que aportan al protocolo Lisk.

Glosario

A continuación, encontrará la terminología técnica principal utilizada a lo largo de esta publicación de blog como punto de referencia para ayudar a proporcionar una comprensión clara. Cuando no se especifica, asumimos que cada valor de datos es una matriz de bytes.

  • Conjunto de datos original: el conjunto inicial de bloques de datos a partir del cual construimos el árbol Merkle, por ejemplo, una matriz de valores de bytes.
  • Bloque de datos: un elemento del conjunto de datos original.
  • (Merkle) Raíz: los bytes finales que se pueden usar para verificar la integridad de la estructura de datos.
  • Nodo de rama: un nodo interno del árbol, es decir, un nodo que no pertenece a la capa base.
  • Nodo hoja: un nodo externo del árbol, es decir, un nodo que pertenece a la capa base.
  • Hashing: asignación de datos de tamaño arbitrario a un valor de bytes de tamaño fijo. Por ejemplo, el protocolo Lisk usa la función hash SHA-256. 
  • Ruta de inclusión: una matriz de valores de datos que se puede usar, junto con la raíz de Merkle, para demostrar la pertenencia de ciertos datos al conjunto de datos original.
  • Agregar ruta: una matriz de valores de datos que se pueden usar, junto con nuevos datos que se agregan al árbol, para calcular la nueva raíz de Merkle.
     

¿Qué es un árbol Merkle?

Figura 1: Un árbol de Merkle obtenido de los nombres de los miembros del equipo de investigación. Los cuadros blancos representan el conjunto de datos original, los cuadros verdes son nodos de hoja y, finalmente, los cuadros amarillos son nodos de rama. En la parte superior del árbol se encuentra la raíz de Merkle. Los nodos no emparejados se envían a la capa superior sin aplicar un hash (cuadros discontinuos). Tenga en cuenta que en esta publicación de blog acortamos la salida de la función hash para facilitar la lectura. 

Un árbol Merkle es una estructura de datos autenticada organizada como un árbol . Tratemos de entender qué significa exactamente cada una de estas palabras:

  • Merkle : este nombre se deriva del verdadero inventor de los árboles de hachís, Ralph Merkle .
  • estructura de datos : una estructura de datos es una colección de datos con un conjunto de operaciones que se pueden realizar en ella. Un ejemplo de estructura de datos es una matriz, un objeto o un árbol Merkle.
  • autenticado : la integridad de la estructura de datos se puede verificar de manera eficiente utilizando la raíz (Merkle) del árbol. El conjunto de datos no se puede modificar sin cambiar la raíz de Merkle.
  • árbol : la estructura de datos subyacente está organizada como un árbol, donde cada nodo principal se obtiene mediante el hash de los datos de los nodos secundarios en la capa inferior. Aquí consideramos solo árboles binarios , donde cada padre tiene dos hijos. 

Para construir un árbol Merkle, proceda de la siguiente manera:

  1. Hash de forma individual cada elemento del conjunto de datos original en un nodo hoja .  
  2. Hash juntos pares de nodos hoja y almacenar el valor resultante en un nodo de rama principal Los nodos no emparejados simplemente se empujan hacia arriba en el árbol para eventualmente emparejarse con un nodo de una capa superior. La función hash para obtener un nodo hoja o rama es diferente. La razón de esto se explica en la sección "Hoja versus hash de rama" , a continuación.
  3. Siga hash pares de nodos de rama hasta que llegue a un único nodo de rama superior, la raíz del árbol.

En la Fig. 1, se puede ver un ejemplo ilustrativo de un árbol Merkle construido a partir de los nombres de los miembros del equipo de investigación de Lisk. 

Prueba de inclusión

Figura 2: El árbol de Merkle que se muestra en la Fig. 1 se utiliza para ilustrar la prueba de inclusión. Para probar que el valor de datos "Iker" (cuadro con borde azul) es parte del árbol, el Prover envía los valores hash en los cuadros con borde rojo, junto con sus posiciones en el árbol. El Verificador puede utilizar esta información para volver a calcular la raíz de Merkle (cuadro superior con borde azul) y comprobar que corresponde a la misma que tienen

Se podría argumentar por qué pasar por toda la molestia de construir el árbol, cuando sería más fácil simplemente codificar los datos originales directamente para obtener una sola raíz. El punto es que una vez que se construye el árbol, es posible crear pruebas de inclusión breves para cualquier dato presente en el conjunto de datos original. Estas pruebas de inclusión son solo el conjunto de valores hash intermedios necesarios para volver a calcular la raíz de Merkle. 

Hay dos partes involucradas en una prueba de inclusión: el Verificador y el Probador . La responsabilidad del Verificador es verificar que ciertos datos sean parte del conjunto de datos original, mientras que el papel del Probador es preparar la prueba y entregársela al Verificador. Suponemos que el Verificador conoce la raíz de Merkle y (obviamente) los datos que desean verificar, pero no todo el conjunto de datos. Mientras que el Prover tiene acceso a todo el árbol (o solo al conjunto de datos original, a partir del cual puede reconstruir el árbol). 

El procedimiento para una prueba de inclusión es el siguiente:

  1. El Verificador envía al Probador el bloque de datos para el que desea obtener una prueba de inclusión.
  2. El Prover encuentra este bloque en el árbol Merkle y su índice, indicando la posición del bloque en el árbol.
  3. El Prover recopila todos los hashes intermedios necesarios y los transmite al Verifier, junto con el índice y la longitud del conjunto de datos original.
  4. El Verificador usa los hashes y el bloque de datos que ya tienen para recalcular la raíz de Merkle y verifica que sea igual al que tenían originalmente. El índice y la longitud del conjunto de datos se utilizan para inferir en qué orden los bloques de datos deben combinarse con hash. 

Un ejemplo de una prueba de inclusión se puede ver arriba en la Fig. 2. El Verificador guarda los datos en los cuadros con borde azul (el bloque de datos "Iker" y la raíz de Merkle). Pueden verificar que "Iker" es parte del equipo de investigación solicitando una prueba de inclusión, que en este caso incluye 3 hashes (recuadros con borde rojo), el índice de "Iker" en el árbol (2 en este caso) y la longitud del conjunto de datos (5). Usando esta información, el Verificador sabe que tiene que hacer hash "Iker" a la izquierda con el primer hash en la prueba, luego el resultado tiene que ser hash a la derecha con el segundo elemento de prueba, y finalmente a la izquierda nuevamente con el el tercero.

Sin la construcción del árbol Merkle, el Verificador necesitaría solicitar los otros 4 elementos del conjunto de datos. No parece que estemos ahorrando mucho aquí (solo 3 hashes frente a 4). Sin embargo, el punto importante a reconocer aquí es que el tamaño de una prueba de inclusión solo escala logarítmicamente   con el tamaño del conjunto de datos original (en lugar de linealmente). 

En el protocolo Lisk, un bloque completo puede contener como máximo ~ 128 transacciones. En este caso, la prueba de inclusión para una transacción tendría una longitud Log 128 = 7 (donde Log indica el logaritmo en base 2), en lugar de 127. ¡Esto ya es un buen guardado! De hecho, el Verificador también puede verificar la presencia de múltiples bloques de datos a la vez . En realidad, esto puede ahorrar espacio en la prueba, ya que el Verificador puede calcular directamente algunos valores hash requeridos.

Un punto adicional para mencionar aquí es que el conjunto de datos original en la Fig. 2 está ordenado alfabéticamente. Esto significa que si damos una prueba de inclusión para dos elementos adyacentes en el conjunto de datos, constituirá una prueba de no inclusión para cualquier bloque de datos que se quedaría en el medio.

Como ejemplo, podemos demostrar que no hay "Gianluigi" en el equipo de investigación al demostrar que tanto "Andreas" como "Iker" están presentes y ubicados uno al lado del otro en el conjunto de datos original (esto se puede verificar usando su índice ).

Esta es una propiedad general: si sabemos con certeza que el conjunto de datos original siempre estará ordenado (de acuerdo con una cierta regla), siempre es posible dar una prueba de no inclusión utilizando esta estrategia.

Árbol de Lisk

En esta sección, revisamos algunos casos de uso de árboles Merkle en el protocolo Lisk y describimos las especificaciones de lisk-tree. Si desea ver más información, consulte las especificaciones proporcionadas en LIP 0031 .

Casos de uso

Lisk se beneficiará de los árboles Merkle en los siguientes lugares:

Pruebas de inclusión para transacciones en un bloque  

En la versión 5.0.0 del SDK, cada encabezado de bloque almacenará el transactionRoot en lugar del payloadHash. La transactionRoot se calcula como la raíz de Merkle de los ID de las transacciones incluidas en la carga útil del bloque (los detalles se especifican en LIP 0032 ). Usando el transactionRoot y una prueba de inclusión, será posible verificar si una determinada transacción es parte del bloque sin descargar el bloque completo.

Regenesis descentralizada 

Como parte del objetivo de la hoja de ruta "Introducir la regeneración descentralizada" , crearemos una instantánea de la cadena de bloques Lisk (como se especifica en LIP 0035 ). Esta instantánea se utilizará para realizar un esfuerzo para implementar el nuevo protocolo. La referencia al último estado de la cadena de bloques se almacenará como la raíz Merkle de los hashes de todos los bloques hasta la instantánea.

Especificaciones técnicas

Si llegaste tan lejos, ¡felicitaciones! Ahora sabe qué son los árboles de Merkle y por qué los estamos implementando en el protocolo Lisk. Esta sección final brinda más información sobre algunas decisiones técnicas que tomamos. En particular, cubriremos el concepto de hash de rama y hoja y por qué es importante definir diferentes funciones de hash. En general, optamos por seguir las especificaciones de transparencia del certificado . A continuación, hash es la función hash SHA256 y | indica la concatenación de bytes.

Hachís de hoja contra rama


Figura 3: (arriba) El árbol de Merkle construido a partir del conjunto de datos x = [D1, D2, D3, D4] (abajo) El árbol Merkle construido a partir del conjunto de datos x '= [D1, D2, D3' = hash (D3) | hash (D4)] Si usamos la misma función hash para los nodos de hoja y rama, L3 '= B2 , y por lo tanto ambos árboles tienen la misma raíz R.

En nuestra construcción, los árboles de Merkle aceptan conjuntos de datos de entrada con una longitud arbitraria. Debido a esto, podrían ser potencialmente susceptibles a ataques de segundas imágenes previas. En un segundo ataque previo a la imagen, el objetivo del atacante es encontrar una segunda entrada x ′ que tenga el mismo valor de otra entrada x dada, es decir, encontrar x '≠ x tal que hash (x) = hash (x' ). En los árboles de Merkle, esto corresponde a tener dos conjuntos de datos de entrada diferentes x y x 'que dan la misma raíz de Merkle. 

Pero esto es fácil de hacer: para cualquier x = [D1, D2, D3, D4], simplemente elija x '= [D1, D2, D3' = hash (D3) | hash (D4)], como se muestra arriba en la Fig. 3. Observe que L3 'es igual a B2, lo que da como resultado la misma raíz de Merkle.

Para resolver este problema, anteponemos un indicador diferente a los datos antes de aplicar el hash, dependiendo de si el nodo resultante es un nodo hoja o rama. En particular, definimos las funciones hash de hojas y ramas de la siguiente manera:

  • leafHash (datos) = hash (00 | datos)
  • branchHash (hijo1, hijo2) = hash (01 | hijo1 | hijo2)

Si intentamos usar el mismo truco, esto da como resultado dos raíces diferentes, ya que ahora D3 y D4 se mezclarían juntos de manera diferente en los dos casos:

  • L3 '= leafHash (hash (D3) | hash (D4))
  • B2 = branchHash (hash (D3) | hash (D4)).

Agregar datos al árbol

Figura 4: (arriba) Al agregar nuevos datos al conjunto de datos, podemos actualizar el árbol usando solo los hashes en la ruta de adición (cuadros con bordes morados). (abajo) El árbol actualizado. ¡Nazar ahora es miembro del equipo de investigación! La nueva ruta de adición se indica nuevamente mediante cuadros con bordes de color púrpura.

El conjunto de datos original a partir del cual se construyó el árbol se puede expandir posteriormente para agregar nuevos datos. En este caso, la raíz de Merkle y, en general, el árbol, en principio, deben volver a calcularse desde cero. Resulta que es posible agregar nuevos datos a un árbol existente de manera eficiente . Lo que esto significa es que el número de operaciones necesarias para actualizar el árbol es solo logarítmico en el tamaño del conjunto de datos. Para hacer esto, almacenamos una matriz adicional, llamada ruta de adición. La ruta de adición contiene como máximo valores de Log N , con N el tamaño del conjunto de datos original. 

Usando la ruta de adición, podemos agregar nuevos datos al árbol de la siguiente manera:

  1. Agregue el nuevo bloque de datos al conjunto de datos original y cree el nuevo nodo hoja correspondiente.
  2. Suba el árbol capa por capa y vuelva a calcular los nodos de rama relevantes utilizando los hash de la ruta de adición. Tenga en cuenta que solo deben actualizarse los nodos de rama Log N.
  3. Finalmente actualice la raíz de Merkle y mantenga la nueva ruta de adición.

En la Fig. 4 (arriba), la ruta del anexo está indicada por los recuadros con bordes morados. Después de agregar un nuevo bloque de datos al árbol, la raíz de Merkle y la ruta de adición se pueden actualizar simplemente usando la ruta de adición anterior, lo que da como resultado el nuevo árbol en la Fig. 4 (parte inferior). La nueva ruta de anexión está indicada por los cuadros con bordes morados.

Conclusión

La biblioteca lisk-tree introduce árboles Merkle en el protocolo Lisk como se especifica en LIP 0031 . Los árboles de Merkle se utilizarán para almacenar la raíz de las transacciones en el encabezado del bloque ( LIP 0032 ) y para realizar la regeneración descentralizada ( LIP 0035 ). Sin embargo, en el futuro pueden ser importantes para otros aspectos del protocolo como la interoperabilidad. 

Para más preguntas y comentarios sobre el tema, organizaremos un AMA en Lisk.chat con Alessandro Ricottone (Investigador científico) el próximo jueves 24 de septiembre 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 debates sobre este y otros temas.

Lisk tiene la misión de permitirle crear aplicaciones blockchain descentralizadas, eficientes y transparentes. 

Recursos:

 Fuente: Blog de Lisk

  Introducción Si está interesado en blockchains y criptomonedas, es probable que se haya topado con árboles Merkle (también conocidos como ...