Arbre de Merkle: diferència entre les revisions
Contingut suprimit Contingut afegit
mCap resum de modificació |
|||
Línia 1:
{{FR|data=agost de 2019}}
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 (informàtica)|node]] arrel, un conjunt ordenat de fulles, i, entremig, un conjunt de nodes. Cada fulla conté un [[Funció hash|resum]] (''hash'' en anglès) d'un [[Fitxer informàtic|fitxer]] digital de qualsevol tipus (text, números, imatges, [[Certificat digital|certificats digitals]], missatges, [[Transacció financera|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.<ref name=":0">{{Ref-web|url=https://www.codeproject.com/Articles/1176140/Understanding-Merkle-Trees-Why-use-them-who-uses-t|títol=Understanding Merkle Trees - Why use them, who uses them, and how to use them|consulta=Agost 2019|llengua=anglès|editor=|data=13 Març 2017}}</ref> Fou presentat<ref>{{Ref-publicació|cognom=Merkle|nom=Ralph|article=A Digital Signature Based on a Conventional Encryption Function|publicació=Advances in Cryptology — CRYPTO '87. Lecture Notes in Computer Science. 293|url=|data=1988|pàgines=369-378}}</ref> i patentat<ref>{{Ref-publicació|cognom=Merkle|nom=Ralph|article="Method of providing digital signatures"|publicació=US patent 4309569|url=https://worldwide.espacenet.com/textdoc?DB=EPODOC&IDX=US4309569|data=1982|pàgines=}}</ref> per Ralph C. Merkle.
== Exemple ==
[[Fitxer:ArbreMerkle.png|miniatura|400x400px|Exemple d'arbre de Merkle amb vuit fitxers|alt=]]
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<sub>i</sub>)
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.''<ref name=":0" /><br />
| |||