¿Por qué Merkle Tree es más eficiente cuando las ramas de los árboles no se almacenan en blockchain?

Supongamos que tenemos 8 transacciones en un bloque Xde la siguiente manera y conocemos el valor hash de cada nodo de todo el árbol Merkle (es decir, incluidos los nodos intermediarios como 45). Luego, si alguien afirma que texiste una transacción Xy está ubicada en 6. Para verificar esto, solo necesitamos buscar valores de hash en 7, 45, 0123 y hash hasta la parte superior y compararlos con Merkle root 01234567.

Supongo (basado en esto ) que el árbol de Merkle es más rápido que el hash de la concatenación de TXID0 ~ TXID7 directamente porque el algoritmo hash se ejecuta más rápido en archivos pequeños (incluso en ~log(N)tiempos de ejecución) que en un archivo grande (es decir, la concatenación de NTXID, Nes 8 aquí ) de una sola vez.

Pero al leer esta publicación, parece que solo la raíz de Merkle y los NTXID se almacenan en un bloque y tenemos que recrear la estructura de árbol cada vez que verificamos una transacción, lo que en realidad ejecutaría funciones hash ~Nveces en lugar de ~log(N)veces (si estaba en lo correcto matemáticamente).

Mis preguntas son:

  1. ¿Los ~Ntiempos de hash son aún más rápidos que el hash una vez en Nvalores de hash concatenados?
  2. ¿Por qué no se almacena el árbol de Merkle? ¿Se debe a consideraciones de almacenamiento?

ingrese la descripción de la imagen aquí

Respuestas (1)

La velocidad del hash es aproximadamente lineal en la cantidad de bytes procesados: SHA2 procesa un bloque de 64 bytes a la vez, y el tiempo necesario es igual a la cantidad de bloques procesados. La computación de un hashtree procesa más bloques debido a los niveles intermedios, pero casi todo el procesamiento se puede realizar en paralelo, a diferencia del hash lineal, que debe realizarse secuencialmente.

Un nodo solo verifica un bloque una vez. Para ese propósito, no importa mucho si el hash es un árbol o lineal, aunque si se explota el paralelismo, calcular un hash de árbol es más rápido.

[Y Bitcoin Core usa instrucciones vectoriales para procesar hashes de árbol en paralelo para acelerar varias veces. Actualmente no se molesta en usar múltiples núcleos para eso, aunque podría.]

Sin embargo, un cliente ligero no valida un bloque completo, normalmente ni siquiera recupera un bloque completo. En cambio, quiere saber si una transacción está en un bloque. Aquí, la estructura hash importa mucho. Si se usara un hash lineal, la única forma de probar que una transacción está en un bloque para un cliente ligero sería enviarle el bloque completo. Con un hash de árbol, solo es necesario enviarle valores de log2 (n) y la transacción en sí.

El árbol no se almacena en las implementaciones actuales de Bitcoin porque no hay ninguna operación que realmente se beneficie de que se almacene en las implementaciones. Probar que se pagó a un cliente lite es una operación relativamente poco frecuente y volver a calcular el árbol hash es económico. Una implementación podría comenzar a almacenarlo si tuviera una razón para hacerlo. Los TXID tampoco se almacenan, ya que solo se pueden calcular a partir de las transacciones mismas.

¿Por qué Merkle Tree es más eficiente cuando las ramas de los árboles no se almacenan en blockchain?
RespuestasAquíPolítica de privacidad1y, 0v