Crea una cuenta o inicia sesi贸n

隆Contin煤a aprendiendo sin ning煤n costo! 脷nete y comienza a potenciar tu carrera

Aprende todo un fin de semana sin pagar una suscripci贸n 馃敟

Aprende todo un fin de semana sin pagar una suscripci贸n 馃敟

Reg铆strate

Comienza en:

0D
11H
57M
7S
Curso de Bitcoin para Developers

Curso de Bitcoin para Developers

Juan Sebasti谩n Marulanda

Juan Sebasti谩n Marulanda

Merkle trees

4/16
Recursos

Una Blockchain almacena gran cantidad de informaci贸n que crece cada segundo. Sin un buen mecanismo de compactaci贸n de todas los datos de un bloque, ser铆a imposible de escalar y poco portable tener un nodo, ya que pocos computadores tendr铆an los recursos de hardware necesarios para mantener uno.

Qu茅 es el 脕rbol de Merkle

El Merkle Tree es una estructura jer谩rquica de datos interconectada con hashes criptogr谩ficos, usada para resumir y verificar grandes conjuntos de datos. Sin este, toda la informaci贸n en la Blockchain ser铆a mucho m谩s pesada, haci茅ndola m谩s dif铆cil de computar.

Con este recurso matem谩tico, se implementa el uso de un algoritmo doble SHA256, con el que se obtiene una 鈥渉uella digital鈥 del total de las transacciones dentro de un bloque.

En el encabezado de los bloques, se asigna un campo que contiene el valor obtenido por el 谩rbol de Merkle. Este 谩rbol es binario y solo contiene los datos de las transacciones que pertenecen a un bloque. Se construye desde sus hojas nodo (leaf nodes) hasta su ra铆z o el valor final (Merkle Root).

Cada hoja del 谩rbol es una transacci贸n. Como los 谩rboles son binarios, se dividen en grupos de dos y si la cantidad de transacciones es impar, se duplica la 煤ltima para mantener la paridad de dos en cada rama.

Las transacciones, en pares de dos, son encriptadas utilizando un algoritmo SHA256 y este valor es concatenado con la rama 鈥渉ermana鈥 del 谩rbol para formar otro hash. Las transacciones contin煤an concaten谩ndose y encript谩ndose de dos en dos hasta llegar a la ra铆z y obtener el Merkle root.

Ejemplo 谩rbol de Merkle

Qu茅 son las pruebas de Merkle (Merkle proofs)

Para comprobar que una transacci贸n efectivamente corresponde a cierto bloque y asegurar su integridad es con las pruebas de Merkle.

Por ejemplo, suponiendo que queremos verificar hK (en verde) en el siguiente 谩rbol Merkle:

Ejemplo 谩rbol de Merkle corrupto

Comenzamos verificando hABCDEFGH y hIJKLMNOP, las dos primeras hojas del 谩rbol. Podemos comprobar que hABCDEFGH es correcto (en azul), por lo tanto lo descartamos. Sin embargo, hIJKLMNOP no lo es as铆 que continuamos profundizando por esa rama.

Solicitamos hIJKL y hMNOP para su validaci贸n y el algoritmo detecta que hMNOP es correcto para descartarlo y continuar profundizando por hIJKL ya que no logramos verificarlo.

Nuevamente, solicitamos las hojas hIJ y hKL desde este punto para realizar la verificaci贸n, descartar hIJ y darnos cuenta de que el problema viene desde hKL. Al obtener las transacciones hK y hL, comprobamos que los datos de hK son incorrectos y podemos reparar el 谩rbol completo.

Conclusi贸n

El algoritmo para encriptar y desencriptar un 谩rbol de Merkle puede ser un reto m谩s que interesante para ti si te propones desarrollar tu propia implementaci贸n con el lenguaje que m谩s te guste.

Esta es la manera en que la Blockchain de Bitcoin asegura la integridad de la informaci贸n y vuelve a esta gran base de datos inmutable. Cualquier alteraci贸n malintencionada en una transacci贸n, simplemente el resto de los nodos, lo detectar铆a y no llegar铆an a un consenso.


Contribuci贸n creada por: Luis Enrique Herrera y Kevin Fiorentino (Platzi Contributor).

Aportes 22

Preguntas 3

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

Un Bloque de Bitcoin tiene en promedio 1930 Transacciones.

El reto tiene dos maneras de solucionarse.

  1. Se pide encontrar s铆 existe el Hash Tx F en el merkle Root del reto sin reconstruir todo el 谩rbol.

  2. La otra forma, es reconstruyendo el Binary Merkle Tree.

Dejar茅 las dos soluciones al reto

// Using Merkle Proof or Paths, find short path

StepsUpwards: HE + HGH + HABCD  = True at Merkle Root
//Demostramos que HF existe en el conjunto de Merkle Root obteniendo la ruta m谩s corta.

// Binary Merkle Tree for TxF //

Merkle Root: HABCDEFGH
Step5: HABCD / HEFGH
Step4: HEF / HGH
Step3: HE / HF
Step2: HF
Step1: TxF

Habcdefgh=Habcd+Hefgh / Hefgh=Hef+Hgh / Hef=He+Hf

Hola estuve un buen rato buscando y analizando el algoritmo para resolver la problem谩tica del final del video. Les anexo los links:

https://medium.com/crypto-0-nite/merkle-proofs-explained-6dd429623dc5
https://www.youtube.com/watch?v=1pasjSinXDs
https://www.youtube.com/watch?v=2kPFSoknlUU

Bitcoin ya quedo atr谩s, dentro de 5 a帽os Ethereum van a sustituir a su Merkle Trees y trusted setups en ZK-STARKS, a esto se le llama Polynomial commitments.

Merkle Path:
Para demostrar que un dato espec铆fico est谩 incluido en un 谩rbol de merkle necesitamos obtener lo que se conoce como Merkle Path o camino de Merkle. En esencia, se trata de una colecci贸n que contiene todos aquellos nodos necesarios para reconstruir la ra铆z de Merkle.
.
Definici贸n extra铆da del siguiente art铆culo que les recomiendo leer para complementar el contenido visto en esta sesi贸n:
Merkle Trees

Una Merkle proof o Merkle Path es el n煤mero m铆nimos de nodos requeridos para calcular la raiz Merkle.

[](https://docs.symbolplatform.com/concepts/data-validation.html#:~:text=A Merkle proof (also known,calculate the Merkle root again.&text=The following steps are taken,if exists within a block.)

explicacion de arboles de merkle en espa帽ol https://www.youtube.com/watch?v=Usxypgr8Y-w

Merkle Tree | Merkle Root | Blockchain

https://www.youtube.com/watch?v=fB41w3JcR7U

Merkle Tree

Aunque seguramente no recibir谩 feedback, dejo mi respuesta al reto:

Hash de Hf y He da Hef
Hash de Hef con Hash de Hgh da hash de Hefgh
Hash de Hefgh y Habcd da la ra铆z Habcdefgh

No tengo claro si esta es la respuesta pero para encontrar HF se aria una igualacion y al final se sacaria HF como un equivalente:

HABCD+HEFGH = HABCD + ((HE)+(HF)(HG)+(HH))

     HABCD + HEFGH

HF = --------------------------------
(HE)+(HGHH)

creo que seria la forma mas rapida sin recontruir todo el arbol

Esta explicaci贸n sobre los bloques de transacciones me ha parecido, de lejos, la mejor que he visto nunca. Gracias 馃檶馃徑

me encanta este curso

muy buena clase

RESUMEN CLASE 4:
MERKLE TREES

  • Estructura de datos usada para resumir y verificar grandes conjuntos de datos.

  • Algoritmo usado por Bitcoin: double-SHA256

  • Huella digital del conjunto de transacciones dentro del bloque.

Reto 2:
Investiga sobre Merkle Paths y c贸mo probar la existencia de un elemento sobre el siguiente 谩rbol.

SOLUCION:

HE + HGH + HABCD  = Merkle Root

Merkle Paths es el camino que nos permite revisar que si un elemento en el 谩rbol ha cambiado o no.

En el ejemplo de la clase podemos verificar el elemento F, solo con revisar el Hash de: TxE, TxEF, TxEFGH y TxABCDEFGH

Lo del reto se resolver铆a con la llave p煤blica comparada contra el hash de la ra铆z del 谩rbol? Me refiero a si esa llave p煤blica se presentar铆a en el hash de la ra铆z. No me aclaro muy bien.