Merkle Tree

Hva er Merkle Tree?

Merkle Tree er en datastruktur som komprimerer et stort sett med poster til ett kort fingeravtrykk. Den lar deg bevise at et element finnes i en stor liste ved å sjekke bare noen få små biter, ikke hele oppsettet. Tenk deg et slektstre der hver forelder er en oppsummering av sine barn, som til slutt føres opp til én felles forfar.

Hvordan Merkle Tree fungerer

Tenk deg en blokk med betalinger som trenger en rask, verifiserbar oppsummering. Slik fungerer Merkle Tree i enkle ord:

• Trinn 1: Start med en liste over elementer som transaksjoner, hver er et blad i treet.
• Trinn 2: Gjør hvert element om til et kort fingeravtrykk ved hjelp av en hash function.
• Trinn 3: Parre nabofingeravtrykk, slå hvert par sammen, og hash igjen for å lage deres overordnede.
• Trinn 4: Gjenta paring og hashing oppover til ett øverste fingeravtrykk står igjen. Det er Merkle root for dette settet.
• Trinn 5: For å bevise at ett element er i settet, trenger du bare det elementet pluss en kort sti med søskenfingeravtrykk. Raskt og smått.

Det er poenget: små bevis, stor tillit.

Hvorfor Merkle Tree er viktig

Ved å oppsummere store mengder transaction data til ett kompakt fingeravtrykk, gjør Merkle Tree verifisering rask og rimelig.

• Fordel: Du kan sjekke inkludering uten å laste ned hele blokken, noe som sparer tid og båndbredde.
• Perspektiv: Det passer humøret på internett akkurat nå: trust but verify, Rolex møter Reddittråder.
• Relevans: Du vil møte det i Bitcoinblokker, Ethereumkvitteringer, NFT allowlists, airdrops og rollups.

Hovedtrekk ved Merkle Tree

Dette gjør den spesiell og nyttig:

• Effektivitet: Bevis forblir små selv når datasettet vokser mye, så lette klienter forblir lette.
• Integritet: Endrer du en byte i et blad, forplanter endringen seg til toppen, noe som gjør manipulasjon tydelig.
• Root: Alt samles i en enkelt Merkle root som kan lagres eller signeres for senere kontroll.

Varianter

Merkle Tree har noen populære varianter du vil støte på:

1. Binær: Det klassiske treet som er bygget parvis, brukt i Bitcoinblokker.
2. Merkle Patricia: En triebasert variant for nøkkelverdidata, brukt i Ethereumstate og kvitteringer.
3. Sparse: Et stort indeksert tre der de fleste blader er tomme, godt egnet for kompakte bevis for medlemskap og bevis for fravær av medlemskap.
4. Verkle: En nyere slektning med kortere bevis for svært stor forgrening, undersøkt for fremtidige oppgraderinger.

Eksempel

En lett lommebok i Bitcoinstil kan bekrefte betalingen din ved å sjekke en kort sti av hashes fra transaksjonen din opp til blokkheaderen, uten å laste ned hele transaction history.

Visste du at

Ralph Merkle skisserte denne ideen på slutten av syttitallet som et studentprosjekt, og den ble liggende i akademiske kretser i flere år før Satoshi brukte den i Bitcoin. Bevis på at gode ideer holder seg over tid.

Oppsummering

Konklusjon? Merkle Tree gir deg raske, små bevis på at noe hører hjemme i et stort sett, ingen drama, ingen tunge nedlastinger.