2.1.3. Exemple
2.1.3. Exemple
L'arbre Merkle binaire avec 7 feuilles :
hash
/ \
/ \
/ \
/ \
/ \
k l
/ \ / \
/ \ / \
/ \ / \
g h i j
/ \ / \ / \ |
a b c d e f d6
| | | | | |
d0 d1 d2 d3 d4 d5
Le chemin d'audit pour d0 est [b, h, l].
Le chemin d'audit pour d3 est [c, g, l].
Le chemin d'audit pour d4 est [f, j, k].
Le chemin d'audit pour d6 est [i, k].
Le même arbre, construit progressivement en quatre étapes :
hash0 hash1=k
/ \ / \
/ \ / \
/ \ / \
g c g h
/ \ | / \ / \
a b d2 a b c d
| | | | | |
d0 d1 d0 d1 d2 d3
hash2 hash
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
k i k l
/ \ / \ / \ / \
/ \ e f / \ / \
/ \ | | / \ / \
g h d4 d5 g h i j
/ \ / \ / \ / \ / \ |
a b c d a b c d e f d6
| | | | | | | | | |
d0 d1 d2 d3 d0 d1 d2 d3 d4 d5
La preuve de cohérence entre hash0 et hash est PROOF(3, D[7]) = [c, d, g, l]. c, g sont utilisés pour vérifier hash0, et d, l sont en outre utilisés pour montrer que hash est cohérent avec hash0.
La preuve de cohérence entre hash1 et hash est PROOF(4, D[7]) = [l]. hash peut être vérifié en utilisant hash1=k et l.
La preuve de cohérence entre hash2 et hash est PROOF(6, D[7]) = [i, j, k]. k, i sont utilisés pour vérifier hash2, et j est en outre utilisé pour montrer que hash est cohérent avec hash2.