En el último post, realizamos un examen exhaustivo de las transacciones. Las transacciones son la unidad fundamental de cálculo en las redes de criptomonedas. Sin transacciones, no hay blockchain. Un bloque consta de varias transacciones, así como datos relacionados. Para cualquier bloque que contenga transacciones, queremos determinar dos propiedades: en primer lugar, que estas transacciones no han sido manipuladas y, en segundo lugar, si una transacción particular está presente en el bloque.
Recordará de un post anterior que el atributo de bloque prevblockhash se usa para probar
si el bloque anterior ha sido manipulado. Este hash se calcula sobre el
encabezado de bloque del bloque anterior. Las transacciones en el bloque anterior no están en este encabezado del bloque. Sin embargo, el encabezado del bloque contiene la raíz merkle de estas transacciones. Esta raíz se puede utilizar para verificar la integridad de las transacciones en el bloque. Si alguno de las transacciones se han alterado, la raíz merkle cambiará y, en consecuencia, el hash del bloque anterior no coincidirá, invalidando la transacción.
En este post veremos cómo se utilizan los árboles merkle para verificar la integridad de
los los bloques de transacciones. Después de esto, implementaremos código los arboles de merkle de Blancoin.
estructura de los arboles de datos
En Ciencias de la Computación, un árbol es una colección de nodos donde los nodos están relacionados con otros a través de las relaciones entre padres, hijos y hermanos. Esto se explica mejor por medio de un diagrama:
En este diagrama, cada nodo está representado por un círculo. Hay 12 nodos, etiquetados
de A a L. Estos nodos están organizados en cuatro capas. Cada nodo, excepto el nodo A, es
conectado a un nodo por encima de él con una línea. El nodo de arriba se llama nodo padre. Por ejemplo, D es un nodo padre de H, y C es un padre de E así como F. El nodo A no tiene un padre; se llama nodo raíz. Aparte de los nodos G a L, que están en la parte inferior de esta estructura de árbol, cada nodo está conectado a dos nodos debajo. Estos dos nodos se denominan hijos (o hijos izquierdo y derecho) del nodo de arriba (que es un
nodo padre). Por ejemplo, el nodo E tiene dos hijos, los nodos I y J. E es el padre de
estos nodos. Los nodos hijos de un nodo padre se denominan hermanos entre sí. Los nodos en la parte inferior del árbol no tienen hijos y se denominan nodos hoja.
Este diagrama es un ejemplo de árbol binario; todos los nodos excepto los nodos hoja
tengo dos niños. Además, este es un árbol equilibrado ya que todos los nodos de las hojas estan al mismo nivel. No es necesario que cada nodo padre tenga dos hijos o que
el árbol esté equilibrado. Podemos construir árboles donde los nodos tienen un número variable de hijos y donde el árbol no está equilibrado. Sin embargo, los árboles binarios equilibrados poseen propiedades interesantes; en particular, podemos hacer inserciones y eliminaciones muy rápidas de nodos en el árbol. Además, la búsqueda de un nodo en estos árboles es muy rápida.
Cada nodo en un árbol normalmente contendrá punteros a sus hijos, su nodo padre como
así como datos específicos del dominio en el que se utiliza el árbol. Los punteros en estos
los nodos permiten el movimiento bidireccional a través del árbol.
arboles de merkle
En implementaciones típicas de criptomonedas, una gran porción de datos de un bloque contiene una colección de transacciones. Por ejemplo, un bloque de Bitcoin puede contener 2000–4000 transacciones. En Blancoin, las transacciones de un bloque se representan como una lista. Cada elemento de la lista es una transacción y cada transacción tiene una estructura de diccionario. Veremos en breve, podemos representar esta lista de transacciones como una estructura de árbol.
Un árbol merkle es un árbol binario equilibrado donde los nodos están relacionados a través de hashes criptográficos. El nodo raíz del árbol merkle identifica de forma única al árbol. Supongamos que tenemos una lista de ocho transacciones en un bloque. Construiremos el arbol de merkle de esta lista de la siguiente manera.
Para cada una de estas transacciones, calcule el hash criptográfico SHA256 de la transacción como una cadena hexadecimal. Estos valores se convertirán en los nodos hoja de nuestro árbol merkle:
TnhH es el hash SHA256 de la enésima transacción. Dado que un árbol merkle es un
árbol binario, debe contener un número par de nodos hoja. Por lo tanto, si tenemos un número impar de transacciones en el bloque, simplemente agregaremos la última transacción dos veces a la lista de transacciones. Ahora podemos derivar la segunda capa del árbol merkle. Comenzando con el nodo hoja más a la izquierda, consideramos su hermano en el lado derecho. Concatenamos los dos hashes, T1H y T2H y calculamos el hash SHA256 de esta cadena concatenada:
T12H = SHA256(T1H + T2H)Luego concatenamos el siguiente par de hashes de nodo hoja y calculamos el hash SHA256:
T34H = SHA256(T3H + T4H)Procedemos de esta manera hasta que se hayan procesado todos los nodos hoja. Esta
nos dará una lista de hashes criptográficos cuya longitud es la mitad del número de hojas
nodos. Los nodos de la segunda capa del árbol merkle se construyen a partir de esta nueva lista:
Para derivar la tercera capa del árbol merkle, calculamos los hashes:
T1234H = SHA256(T12H + T34H)
T5678H = SHA256(T56H + T78H)Ahora tenemos la tercera capa del árbol merkle:
Finalmente, concatenamos los hashes SHA256 en los dos nodos que están en el tercer
nivel del árbol merkle:
T12345678H = SHA256(T1234H + T5678H)Esto nos da la representación final del árbol merkle para las ocho transacciones en
el bloque:
El valor hash T12345678H se denomina raíz merkle. Es un hash criptográfico de
las transacciones en el bloque. Si alguna de las transacciones está alterada o si su orden
en la lista de transacciones del bloque se cambia, la raíz merkle será inconsistente con
su valor anterior. Dado que la raíz merkle está en el header del bloque, el header del bloque se volverá inconsistente. Puedes preguntarte por qué necesitamos construir un árbol merkle. La respuesta corta es que un árbol binario equilibrado, como el árbol Merkle, es una estructura de búsqueda notablemente eficiente.Considera una lista hipotética de un millón de transacciones en bloque. Esta lista puede ser
representado como un árbol merkle con una profundidad de 20 capas. Además, podemos buscar una transacción particular en esta lista en tiempo O(log n) donde n es el tamaño del número de transacciones.
Otra característica de un árbol merkle es que la ruta a cualquier nodo hoja (transacción)
a través del árbol merkle es único. Considere la transacción cuyo hash SHA256 es T6H;
la ruta a esta transacción se puede representar como:
T12345678 + T5678 + T56 + T6En la Figura de abajo, esta ruta se indica con líneas enfatizadas:
derivando el arbol de merkle de blancoin
En un post anterior escribimos parte del código Python para la cadena de bloques Blancoin. La función merkle_root en este módulo se eliminó y devolvió un valor simulado. Lo haremos ahora rectificando esta deficiencia y codificando la función para calcular y devolver la raíz merkle de una lista de transacciones en un bloque.
Elimina la función merkle_root en su archivo hblockchain.py y agregua el siguiente código al final de su módulo hblockchain. La función principal merkle_root convierte los valores del diccionario en cadenas codificadas en JSON, así que asegúrate de haber importado el módulo estándar de Python json en hblockchain:
def merkle_root(buffer: "List", start: "bool" = False) -> "bool or string":
"""
merkle_tree: computes the merkle root for a list of transactions.
Receives a list of transactions and a boolean flag to indicate whether
the function has been called for the first time or whether it is a
recursive call from within the function.
Returns the root of the merkle tree or False if there is an error.
"""
try:
# if start is False then we verify have a list of SHA-256 hashes
if start == False:
for value in buffer:
if rcrypt.validate_SHA256_hash(value) == False:
raise(ValueError("tx list SHA-256 validation failure"))
buflen = len(buffer)
if buflen != 1 and len(buffer)%2 != 0:
buffer.append(buffer[-1])
# make the merkle leaf nodes if we are entering the function
# for the first time
if start == True:
tmp = buffer[:]
tmp = make_leaf_nodes(tmp)
if tmp == False: return False
buffer = tmp[:]
# if buffer has one element, we have the merkle root
if (len(buffer) == 1):
return buffer[0]
# construct the list of parent nodes from the child nodes
index = 0
parents = []
while index < len(buffer):
tmp = rcrypt.make_SHA256_hash(buffer[index] + buffer[index+1])
parents.append(tmp)
index += 2
# recursively call merkle tree
ret = merkle_root(parents, False)
except Exception as error:
logging.error("exception: %s: %s", "merkle_root",error)
return False
return ret
def make_leaf_nodes(tx_list: "list") -> "List or False":
"""
make_leaf_nodes: makes the leaf nodes of a merkle tree.
Receives a list of transactions. If the number of transactions is an
odd number, appends the last transaction to the list again so that we can
make a balanced binary tree.
Computes the hexadecimal string encoded SHA-256 message digest of each
transaction and appends it to a leaf node list that is initially empty.
Returns the leaf node list or False if there is an error
"""
try:
# cannot have an empty transaction list
if (len(tx_list) == 0): raise(ValueError("tx list zero length"))
# verify we have a list type
if type(tx_list) is not list: raise(ValueError("tx is not a list type"))
# verify the type of each transaction is a dict
for tx in tx_list:
if type(tx) is not dict: raise(ValueError("tx is not a dict type"))
# must have an even number of transactions
if len(tx_list) % 2 == 1 or len(tx_list) == 1:
tx_list.append(tx_list[- 1] )
# copy the transaction list
trx_list = list(tx_list)
# convert each transaction into a JSON string
tx = []
for transaction in trx_list:
tx.append(json.dumps(transaction))
# make the leaf nodes
sha256_list = []
for transaction in tx:
sha256_list.append(rcrypt.make_SHA256_hash(transaction))
except Exception as err:
logging.debug('make_leaf_nodes: exception: ' + str(err))
return False
return sha256_list
Hay dos funciones: merkle_root y make_leaf_nodes. merkle_root recibe una lista
de transacciones en bloque. merkle_root es llamado por las funciones validate_block y blockheader_hash.
merkle_root es una función recursiva; recibe un flag booleano como segundo parámetro.
Este indicador es True si se llama a merkle_root desde las funciones antes mencionadas y False si esta función ha sido llamada por sí misma. Lo primero que hace merkle_root es llamar a la función make_leaf_nodes, cuya tarea es construir los nodos hoja del árbol merkle. make_leaf_nodes realiza algunas validaciónes en la lista de transacciones que recibe. Si esta lista está vacía, devuelve False. Una lista de transacciones vacía no tendrá nodos hoja. Luego se realiza una verificación de tipo para verificar que haya recibido una lista y no otros datos estructura. También verifica que cada elemento de la lista sea un tipo de diccionario. Si las cosas van mal devuelve un valor False. De lo contrario, make_leaf_nodes construye los nodos hoja del merkle para esta lista de transacciones y devuelve estos valores.
merkle_root luego procesa los nodos de hoja para construir el árbol merkle llamándose a sí mismo de forma recursiva con el flag establecido en False.
pytest para el arbol de merkle
Ahora escribiremos algunas pruebas unitarias de pytest para validar el código merkle. Agregue el siguiente pytest en la parte inferior de su módulo test_blockchain.
Una vez que se haya agregado el código de prueba unitaria, ejecute las pruebas desde el directorio unit_tests:
>(virtual) pytest test_blockchain.py -k -sDebes observar un total de 30 pruebas aprobadas:
def test_empty_merkle_root(monkeypatch):
"""
test that the merkle root of a block cannot be empty
"""
hblockchain.blockchain.clear()
monkeypatch.setattr(hblockchain, "merkle_root", lambda x, y: "")
assert hblockchain.add_block(block_1) == False
hblockchain.blockchain.clear()
def test_invalid_merkle_root(monkeypatch):
"""
test an invalid merkle root
"""
monkeypatch.setattr(hblockchain, "merkle_root", lambda x, y: rcrypt.
make_SHA256_hash('msg1'))
monkeypatch.setitem(block_1, "merkle_root", \
"A88a1fd32a1f83af966b31ca781d71c40f756a3dc2a7ac44ce89734d2186f63z")
assert hblockchain.add_block(block_1) == False
"""
test the merkle root
These merkle tests do not test the validity of transactions
"""
def test_merkle_root_empty_tx(monkeypatch):
"""
test the merkle root for an empty transaction list
"""
monkeypatch.setattr(hblockchain, "merkle_root", \
lambda x, y: rcrypt.make_SHA256_hash('msg0'))
monkeypatch.setitem(block_0, "tx", [])
monkeypatch.setattr(hblockchain, "merkle_root", \
lambda x, y: rcrypt.make_SHA256_hash('msg1'))
monkeypatch.setitem(block_1, "tx", [])
assert hblockchain.add_block(block_1) == False
def test_merkle_root_tx_bad_type():
"""
test the merkle root for a bad transaction list type
"""
assert bool(hblockchain.merkle_root ("123", True)) == False
def test_merkle_bad_flag():
"""
test the merkle root for a bad flag parameter
"""
assert bool(hblockchain.merkle_root ([{"a":1}], False)) == False
def test_merkle_root_transactions_dict_type():
"""
test the merkle root for a transaction list is a dict type
"""
assert bool(hblockchain.merkle_root ({'a': 1}, True)) == False
def test_merkle_root_random_transaction():
"""
test merkle root for synthetic random transactions
does not test hash of previous block
"""
hblockchain.blockchain.clear()
block_0["merkle_root"] = hblockchain.merkle_root(block_0["tx"], True)
assert hblockchain.add_block(block_0) == True
block_1["merkle_root"] = hblockchain.merkle_root(block_1["tx"], True)
block_1["prevblockhash"] = hblockchain.blockheader_hash(block_0)
assert hblockchain.add_block(block_1) == True
block_2["merkle_root"] = hblockchain.merkle_root(block_2["tx"], True)
block_2["prevblockhash"] = hblockchain.blockheader_hash(block_1)
assert hblockchain.add_block(block_2) == True
conclusion
Los árboles de Merkle son importantes en las aplicaciones de blockchain por dos razones principales. En primer lugar, nos permiten probar de manera eficiente si una lista de transacciones ha sido manipulada. En segundo lugar, podemos utilizar estos árboles para verificar si una transacción en particular está en una lista de transacciones. En este post, hemos examinado los árboles merkle y el código escrito para hacer un árbol merkle de una lista de transacciones en un bloque. En el próximo post, escribiremos el código de transacción para Blancoin y realizaremos una prueba unitaria de este código.
BlockchainLanzarote 