Utilisation des MerkleTree pour la Certification de documents

En tant que freelance j’ai travaillé sur la problématique de la certification de documents grâce à la blockchain. J’ai reçu plusieurs demandes similaires, mais l’une d’elles exigeait l’implémentation d’une nouvelle structure de données, les Merkle Tree. C’est une structure de donnée très utilisée dans la décentralisation et pour cause: grâce aux Merkle Tree et au Merkle Proof nous avons mis en place un nouveau système de certification qui possède des proprietés inédites.

Cas d’usage

Dans un article précédent j’ai décrit un système d’horodatage sur la Blockchain qui a permis à un de mes clients de certifier des contrats de manière irréfutable et relativement abordable. Une fonctionnalité importante était de pouvoir prouver qu’un document n’avait PAS été certifié à posteriori.

J’ai reçus une demande similaire peut de temps plus tard, avec des contraintes supplémentaires. Imaginez un service qui permette à une entreprise de certifier le rôle et le salaire de ses employés. Une fois cette certification émise, les employés pourraient prouver, via mon client, la véracité de leur CV à un employeur éventuel. C’est un type de vérification qui vient avec de nouvelles contraintes:

Contrainte 1, Scalabilité

La quantité de document à certifier était beaucoup plus grande (centaine de milliers par lots). Cela rend le système d’horodatage “simple” prohibitif: l’horodatage d’un document coûte quelques centimes. Multiplié par des centaines de milliers de documents, on arrive à plusieurs dizaines de milliers de dollars par lot.

Contrainte 2, Confidentialité et Droit à L’oubli

Le document et sa preuve doivent rester aux mains de l’utilisateur. Une fois que la certification a été produite, on veut laisser l’utilisateur maître de la donnée. On doit donc être très attentif à l’information qui est partagée. On ne peut pas horodater un lot de document comme un seul fichier, car il faudrait ensuite transmettre TOUS les documents à tous les utilisateurs.

Contrainte 3, Durabilité

La certification doit persister pendant plusieurs décennies, même si le fournisseur de service disparaît ou abandonne le produit. Cela rend les systèmes de stockage décentralisés comme IPFS difficilement défendables car ils nécessitent que “quelqu’un” persiste la donnée. Notez qu’aujourd’hui un service comme Filecoin pourrait convenir mais la solution qu’on a mise en place est toujours plus efficace en termes de coûts.

Structure de Donnée: Les Merkle Tree

Dans l’article précédent on a vu les fonctions de hash qui permettent de calculer l’empreinte d’un document. Ces fonctions sont très utiles, car si deux personnes possèdent un document elles peuvent rapidement calculer l’empreinte son empreinte et les comparer sans avoir besoin d’échanger tout le fichier.

Dans notre cas on va pousser l’utilisation des hash encore plus loin avec une structure de donnée appelée le Merkle Tree. C’est un arbre pour lequel chaque nœud contient le hash de ses enfants.

La construction de l’arbre est simple, on calcule l’empreinte de chaque document, puis on groupe ces empreintes deux par deux, et on calcule un nouveau hash. On répète l’opération jusqu’à obtenir une seule empreinte. Cette dernière empreinte s’appelle la racine de l’arbre.

C’est une opération récursive qui nous permet de prendre n’importe quel nombre de documents et de produire une seule empreinte. C’est très efficace pour notre service car on pourra horodater cette dernière empreinte en suivant la méthode de l’article précédent.

En utilisant cette approche, on peut signer des centaines de milliers de documents très rapidement. Le calcul de l’arbre est long mais c’est une opération qu’on fait off-chain sur un serveur « classique » qui ne coûte pas grand-chose. On finit toujours par stocker une seule empreinte sur la blockchain. Le coût sur la blockchain est donc le même, peu importe le nombre de documents à certifier.

Cette propriété nous permet de passer la Contrainte 1 (scalabilité)

Donc on horodate la racine de notre arbre de hash sur la blockchain, et on transmet une preuve à nos utilisateurs.

Merkle Proof

Le Merkle Tree a une autre propriété intéressante : il est possible de prouver l’existence de n’importe quel document dans l’arbre sans connaître les autres documents.

En effet, si je vous fournis un document et les hash intermédiaires vous pouvez recalculer l’empreinte de la racine et donc vérifier que mon document n’a pas été modifié. Par exemple, dans le schéma ci-dessous, avec les deux hash intermédiaire (en bleue) et le Contract B, il est possible de retrouver la racine.

Notez que pour 4 documents, la preuve contient 2 hashs intermédiaires, Pour 1024 documents, la preuve contient 10 hashs, Pour 500 000 documents, la preuve contient 19 hashs. C’est une relation logarithmique entre la donnée en entrée et la taille de la preuve à confier aux utilisateurs. En gros, plus on hash de documents plus la solution devient « rentable ».

Dans la pratique

Dans la pratique cela signifie qu’on transmet à l’utilisateur final le document ET la preuve (les hash intermédiaires).

C’est une contrainte supplémentaire mais ce compromis est utile dans notre cas: seul l’utilisateur final reçoit la preuve associée à son document, il est donc seul maître de sa donnée.

Cette propriété nous permet de passer la Contrainte 2 (Droit À L’Oubli)

Démonstration

On a adopté la solution du QR Code dont voici un exemple:

Ce QR Code contient l’identité Andrew O’Reilly, son rôle dans l’entreprise, ET la preuve de merkle. Si vous lisez ce QR code avec votre téléphone, vous devriez arriver sur une application web qui exécuter la vérification décrite plus haut.

Vous pouvez aussi tester l’application en ouvrant cette page

Voici une capture d’écran du résultat de la vérification:

Dans le QR Code suivant, j’ai modifié le rôle d’Andrew pour le faire passer pour le PDG de l’entreprise:

En ouvrant la page de démonstration vous verrez que la preuve échoue.

Et voici la capture de la vérification qui échoue:

Notez que ces QR code sont assez volumineux car ils contiennent TOUTE la donnée à vérifier. Notre système de certification ne repose donc pas sur un service extérieur pour stocker la data ce qui rend le service pérenne.

Cette propriété nous permet de passer la Contrainte 3 (Durabilité)

La Partie Off-chain

La partie off-chain est similaire à celle évoquée dans l’article précédent.

La complexité de la blockchain est “absorbée” par la partie off-chain et cachée au reste de l’application. Dans ces conditions la blockchain devient un service “comme un autre” qui fournit une fonctionnalité bien précise dans notre infrastructure.

Quelques détails importants

Si vous devez implémenter un service similaire, il faut penser à:

S’assurer que le processus de création et de vérification des hashes soit déterministe:

Au moment de la vérification de la preuve, on a seulement le hash à vérifier et le hash de la preuve en cours. Or Hash(A + B) est différent de Hash(B + A), il faut donc définir une manière d’ordonner les hashs. Par soucis de simplicité je les tri alpha-numériquement. Ainsi le processus de calcul de la preuve repose uniquement sur les informations qu’on possède pendant la preuve.

Ajouter de l’entropie sur les données “simple”

Dans le cas de la vérification d’identité on doit prendre en compte l’éventualité qu’un utilisateur malveillant tente de brute-forcer les empreintes. Avec quelques informations de départ (nom, prénom, rôle), il serait possible de “deviner” les autres informations manquantes. Pour éviter ça, je rajoute une chaîne de caractères aléatoire dans les données. Cela rend le hash de la preuve imprévisible, même avec les données de départ.

Finalement

Le merkle tree est une structure très utilisée dans la décentralisation. Il a des propriétés très utiles, dans notre cas on l’utilise pour certifier des centaines de milliers de documents pour un coût minimum. Le principe de preuve nous permet de fournir une certification qui préserve la confidentialité et la pérennité des données utilisateurs.

Une démonstration de l’application est disponible: blockchain-proof.singulargarden.com.

Vous pouvez utiliser la fonctionnalité QR Code, avec les images de l’article. Il y a aussi une vérification plus classique sur la page d’accueil. Voici deux exemples de fichiers et la preuve.

• Wendy Blanda
• Wendy Blanda (Modifié)
• Wendy Blanda - Merkle Proof

Si vous voulez en savoir plus ou si vous avez des questions, je vous invite à me contacter directement sur LinkedIn ou Twitter.