Arbre de Merkle

Un arbre de Merkle (Merkle tree en anglès) és una estructura de dades en forma d'arbre binari usada en criptografia i en informàtica. Consta d'un node arrel, un conjunt ordenat de fulles, i, entremig, un conjunt de nodes. Cada fulla conté un resum (hash en anglès) d'un fitxer digital de qualsevol tipus (text, números, imatges, certificats digitals, missatges, transaccions, etc.) i mida. Cada node té, normalment, dos fills i conté el resum de la concatenació dels resums dels dos fills. El node arrel també conté el resum de la concatenació dels seus dos fills, i per tant és un resum del conjunt de fitxers associats a les fulles de l'arbre. Qualsevol canvi en el contingut d'algun dels fitxers o en la seva ordenació implicarà un canvi en el resum contingut a l'arrel. Fou presentat i patentat per Ralph C. Merkle.

Exemple

Exemple d'arbre de Merkle amb vuit fitxers

La figura mostra un exemple d'arbre amb vuit fitxers. L'arbre consta de vuit fulles, una per cada fitxer. Cada fulla conté el resum del seu fitxer, calculat aplicant una certa funció resum H aplicada al fitxer. Així, el contingut de la fulla i serà H(F_i) on Fi és el contingut del fitxer. La funció resum més usada és la SHA.

Cada node té dos fills, i el seu contingut és el resultat d'aplicar la funció resum H a la concatenació del contingut dels seus dos fills. En l'exemple, el node que s'ha anomenat 01 conté el resultat d'aplicar H a la concatenació del contingut de les fulles 0 i 1. El node arrel també té dos fills i el seu contingut es calcula de manera semblant als altres. En l'exemple, el contingut de l'arrel (anomenada 01234567) és el resultat d'aplicar la funció H a la concatenació dels continguts dels nodes anomenats 0123 i 4567.

Operacions

Les dues operacions més importants que es fan amb arbres de Merkle són la prova d'auditoria i la prova de consistència.

Prova d'auditoria

Aquesta operació (anomenada Audit proof en anglès) s'executa a petició d'un usuari que és el propietari d'un fitxer, o que en coneix el contingut. Aquest usuari creu que el fitxer hauria d'estar inclòs en un arbre de Merkle emmagatzemat en un cert servidor, del qual només en sap el contingut de l'arrel de l'arbre. L'usuari vol que el servidor li proporcioni una prova fefaent que l'arbre conté el fitxer.

L'operació, que s'executa en el servidor, rep de l'usuari el resum del fitxer en qüestió. El servidor respon amb un conjunt mínim de resums tals que l'usuari pot comprovar per ell mateix que, efectivament, el fitxer forma part de l'arbre i que l'arbre té l'arrel que ell coneix. Aquest conjunt de resums és la prova demanada.

Un exemple, usant l'arbre de la figura, podria ser el d'un usuari que demana una prova de la inclusió del fitxer 3 en l'arbre. L'usuari, que coneix el contingut de l'arrel, envia el resum del fitxer 3 al servidor. Aquest respondria amb el contingut dels nodes 2, 01 i 4567. Amb el contingut d'aquests nodes, l'usuari pot calcular el contingut del node arrel i comprovar que efectivament és el mateix que el que ell ja coneix. El càlcul consistiria en:

1. Calcular el contingut del node 23 amb el dels nodes 2 (proporcionat pel servidor) i el 3.
2. Calcular el contingut del node 0123 amb el dels nodes 01 (proporcionat pel servidor) i el 23 (calculat en el pas anterior),
3. Calcular el contingut del node arrel amb el dels nodes 0123 (calculat en el pas anterior) i el 4567 (proporcionat pel servidor).

Prova de consistència

Aquesta operació (anomenada Consistency proof en anglès) permet a un usuari verificar que dues versions (anterior i posterior) d'un arbre de Merkle emmagatzemades en un mateix servidor són consistents. Això vol dir que la versió posterior conté els mateixos fitxers que l'anterior, i en el mateix ordre, i que els nous fitxers inclosos en la versió posterior van després de l'anterior. L'usuari coneix els resums de les dues versions, i el nombre de fitxers que contenia la versió anterior.

L'operació, que s'executa en el servidor que conté l'arbre, rep de l'usuari només el nombre de fitxers (o, el que és el mateix, fulles) que contenia la versió anterior. El servidor respon amb un conjunt mínim de resums tals que l'usuari pot comprovar per ell mateix que, efectivament, la versió anterior està inclosa (sense modificacions) en la posterior i que el resum de la versió posterior és el que ell ja coneix. Aquest conjunt de resums és la prova demanada.

Un exemple, senzill, usant l'arbre de la figura, podria ser el d'un usuari que demana la prova de consistència de la versió que contenia els quatre primers fitxers amb la que conté els vuit fitxers. L'usuari coneix el resum de la versió anterior (el contingut del node 0123) i el de la versió actual (el contingut del node 01234567). En aquest cas, el servidor respondria amb al contingut del node 0123 (resum de la versió anterior) i el contingut del node 4567. L'usuari pot calcular el resum de la versió actual a partir dels nodes 0123 i 4567 i comprovar que és igual al que ja coneixia.

Usos

Alguns dels usos més coneguts dels arbres de Merkle són:

• Bitcoin. Bitcoin construeix un arbre de Merkle per cada bloc que conté. Els blocs acostumen a tenir diversos centenars o més d'un miler de transaccions. El node arrel de l'arbre resumeix el conjunt de les transaccions d'un bloc i el seu ordre. El node arrel s'emmagatzema en la capçalera del bloc, mentre que les fulles i la resta de nodes no s'emmagatzemen explícitament, però es poden calcular sempre que calgui. La funció resum que usa Bitcoin és la SHA. Els usuaris de Bitcoin poden demanar proves d'auditoria que demostrin que una transacció està inclosa en un bloc.