Al utilizar la estructura de Merkle Tree podemos implementar eficazmente una búsqueda para determinar pertenencia al árbol, o en este caso, al bloque en el que queremos buscar.
Esto se realiza con un algoritmo de complejidad computacional O(log n), pues aprovechamos que en el Merkle Tree los nodos que no son hojas son el resultado de realizar hash sobre otros dos hashes para construir un camino una hoja hasta la raíz.
Para implementar este algoritmo necesitamos determinar cuáles hashes escoger, para ello identificamos la hoja que queremos determinar su pertenencia y mientras se resuelve la recursividad seleccionamos los nodos intermedios que tengan el mismo nodo padre que la hoja encontrada.
Al encontrar los nodos requeridos comparamos el valor del hash de ambos con el de su padre, así sucesivamente hasta llegar a la raíz, si es que coincide el valor del hash de la raíz con el resultado del camino recorrido entonces se corrobora la pertenencia de la hoja al bloque.
Esto a parte de tener una complejidad computacional eficaz resulta en una reducción del espacio usado para corroborar la pertenencia de elementos, pues en caso de usar una estructura con un array, tendríamos que hacer una copia de toda la estructura para iterar sobre ella, mientras que al usar este árbol solo necesitamos el valor del hash de la raíz.
Al utilizar la estructura de Merkle Tree podemos implementar eficazmente una búsqueda para determinar pertenencia al árbol, o en este caso, al bloque en el que queremos buscar. Esto se realiza con un algoritmo de complejidad computacional O(log n), pues aprovechamos que en el Merkle Tree los nodos que no son hojas son el resultado de realizar hash sobre otros dos hashes para construir un camino una hoja hasta la raíz.
Para implementar este algoritmo necesitamos determinar cuáles hashes escoger, para ello identificamos la hoja que queremos determinar su pertenencia y mientras se resuelve la recursividad seleccionamos los nodos intermedios que tengan el mismo nodo padre que la hoja encontrada.
Al encontrar los nodos requeridos comparamos el valor del hash de ambos con el de su padre, así sucesivamente hasta llegar a la raíz, si es que coincide el valor del hash de la raíz con el resultado del camino recorrido entonces se corrobora la pertenencia de la hoja al bloque.
Esto a parte de tener una complejidad computacional eficaz resulta en una reducción del espacio usado para corroborar la pertenencia de elementos, pues en caso de usar una estructura con un array, tendríamos que hacer una copia de toda la estructura para iterar sobre ella, mientras que al usar este árbol solo necesitamos el valor del hash de la raíz.