Merkle-träd: transaktionsintegritet i stor skala

Ett Bitcoin-block innehåller cirka 2000 transaktioner. För att bevisa att transaktion T ingår utan att ladda ned alla 2000 transaktioner behöver vi ett kompakt bevis. Merkle-träd löser detta: bevisstorleken = O(log n) hashvärden i stället för O(n) transaktioner.

Löv: SHA256d (dubbel-SHA-256) för varje transaktion. Förälder: SHA256d(left_child_hash || right_child_hash). Upprepa tills en enda rothash återstår. Om antalet noder är udda dupliceras den sista noden. Roten är Merkle-roten som lagras i blockhuvudet (32 byte).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

För att bevisa att transaktion T finns på position i: ange syskonhasharna på varje nivå från bladet för T till roten (O(log n) hashvärden). Verifieraren beräknar om roten utifrån T och syskonvägen. Om den beräknade roten stämmer med Merkle-roten i blockhuvudet är det bevisat att T ingår.

1024 transaktioner → ett Merkle-bevis = 10 hashvärden = 320 byte. Ett helt block = ~1 MB. SPV-klienter laddar bara ned det 80 byte stora blockhuvudet + ett Merkle-bevis på 320 byte för varje transaktion de är intresserade av — 99,97 % mindre bandbredd jämfört med att ladda ned hela blocket.

Om någon transaktion i trädet ändras ändras dess lövhash, vilket fortplantas uppåt och ändrar Merkle-roten. Den ändrade roten stämmer då inte längre med blockhuvudet (som är förseglat med PoW). Alla ändringar kan upptäckas genom att beräkna roten utifrån transaktionerna.

Ethereum utökar Merkle-träd med tries (Patricia Merkle Trie): ett radix-trie med hexadecimalt prefix där varje nod hashas för att bilda en Merkle-struktur. Används för: tillståndstrie (kontosaldon), transaktionstrie, kvittotrie. Möjliggör effektiva bevis av kontotillstånd utan data från en fullständig nod.

En Merkle Mountain Range (MMR) är en append-only-Merkle-struktur för loggliknande data. Nya element läggs till; topparna (rötterna för delträd med storlek som är en tvåpotens) underhålls. Används i Grin/MimbleWimble och ZCash för effektiva, kompakta bevis över en append-only-logg.

Verkle-träd ersätter Merkle-träd i Ethereums färdplan (EIP-6800): de använder vektoråtaganden (KZG-polynomåtaganden) i stället för hashvärden. Bevisstorlek: O(1) jämfört med O(log n) för Merkle-träd. Det gör det möjligt för tillståndslösa klienter att verifiera tillstånd utan att lagra hela trien.

Certificate Transparency (RFC 6962) använder en append-only-Merkle-logg: varje certifikat som utfärdas av en CA är ett löv. Inklusionsbevis verifierar att ett certifikat har loggats. Konsistensbevis verifierar att loggen endast har utökats (ingen radering eller insättning). Webbläsarleverantörer verifierar SCT:er via denna logg.

Gits träd (ögonblicksbilder av kataloger) är Merkle-träd: varje trädnod hashar sina filblobbar och underträd. En commit-hash identifierar hela kodbasens tillstånd unikt. Därför ger git checkout alltid exakt samma filer.

Merkle-träd möjliggör inklusionsbevis med O(log n). Bitcoin lagrar Merkle-roten i blockhuvuden; SPV-klienter använder bevis. Ethereum utökar detta till Patricia Merkle Tries. Verkle-träd kommer att ersätta Merkle-träd för O(1)-bevis. Nästa avsnitt: Proof of Work-mining och svårighetsgrad.