Vad är ett Merkle Tree? Nybörjarguide för denna Blockchain-komponent

Merkle Tree

Merkle Trees är en grundläggande komponent i blockkedjor som stöder deras funktionalitet. De möjliggör effektiv och säker verifiering av stora datastrukturer, och i fallet med blockkedjor, potentiellt gränslösa datamängder.

Implementeringen av Merkle-träd i blockkedjor har flera effekter. Det gör att de kan skala samtidigt som de tillhandahåller den hashbaserade arkitekturen för att de ska kunna upprätthålla dataintegritet och ett trivialt sätt att verifiera dataintegriteten.

Kryptografiska hashfunktioner är den underliggande tekniken som gör det möjligt för Merkle-träd att fungera, så först är det viktigt att förstå vad kryptografiska hashfunktioner är.

Kryptografiska Hash-funktioner

Enkelt uttryckt är en hashfunktion vilken funktion som helst som används för att mappa data med en godtycklig storlek (ingång) till en fast storlek. En hashingalgoritm tillämpas på dataingången och den resulterande utsignalen med fast längd kallas hash.

Många hashingalgoritmer är allmänt tillgängliga och kan väljas utifrån dina behov.

Den resulterande hashen från den godtyckliga ingången är inte bara fast i längd, den är också helt unik för ingången och själva funktionen är deterministisk. Oavsett hur många gånger du kör funktionen på samma ingång, kommer utgången alltid att vara densamma.

Till exempel, om du har följande datauppsättningar nedan som en ingång, är de resulterande utgångarna unika för varje ingång. Lägg märke till hur i det andra och tredje exemplet, även om skillnaden mellan ingångarna bara är ett ord, är de resulterande utgångarna helt olika.

Detta är mycket viktigt eftersom det möjliggör “fingeravtryck” av data.

En kryptografisk hashfunktion, bild från Wikipedia

Eftersom utgångslängden (hashsumman i exemplet) alltid är densamma som bestäms av den använda hashingalgoritmen kan enorma mängder data identifieras enbart genom deras resulterande hash.

Med system som innehåller stora mängder data kan fördelarna med att kunna lagra och identifiera data med en fast längdutdata skapa stora lagringsbesparingar och bidra till att öka effektiviteten.

Inom blockkedjor används hashingalgoritmer för att bestämma blockkedjans tillstånd.

Blockkedjor är länkade listor som innehåller data och en hashpekare som pekar på föregående block, vilket skapar en kedja av anslutna block, därav namnet “blockchain”.

Varje block är kopplat till varandra via en hashpekare, vilket är hash för data inuti det föregående blocket tillsammans med adressen till det tidigare blocket. Genom att länka datablock i detta format representerar varje resulterande hash av det föregående blocket hela tillståndet för blockkedjan eftersom alla hashdata från de tidigare blocken har hashats till en hash.

Detta representeras (i fallet med SHA-256-algoritmen) av en sådan utgång (hash).

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Hashet ovan är fingeravtrycket för hela blockchain-tillståndet före det. Blockkedjans tillstånd före det nya blocket (som hashdata) är ingången, och den resulterande hash är utdata.

Även om det är möjligt att använda kryptografiska haschar utan Merkle-träd är det extremt ineffektivt och inte skalbart. Att använda hash för att lagra data i ett block i serieformat är tidskrävande och besvärligt.

Som du kommer se tillåter Merkle-träd trivial upplösning av dataintegritet samt kartläggning av dessa data genom hela trädet med Merkle-bevis.

Merkle-träd och Merkle-bevis

Uppkallad efter Ralph Merkle, som patenterade konceptet 1979, är Merkle-träd i grunden datastrukturträd där varje icke-bladnod är en hash av sina respektive barnnoder.

Bladnoderna är den lägsta nivån av noder i trädet. Först kan det låta svårt att förstå, men om du tittar på den vanliga figuren nedan blir det mycket lättare att förstå.

Hash-träd

Ett exempel på ett binärt hashträd, Bild från Wikipedia

Det är viktigt att lägga märke till hur de icke-lövknutorna eller “grenarna” (representerade av Hash 0-0 och Hash 0-1) på vänster sida är hash av sina respektive barn L1 och L2. Lägg också märke till hur gren Hash 0 är hash för sina sammanhängande barn, grenar Hash 0-0 och Hash 0-1.

Exemplet ovan är den vanligaste och enklaste formen av ett Merkle-träd som kallas ett binärt Merkle-träd. Som du kan se finns det en topp hash som är hash för hela trädet, känd som root hash. I huvudsak är Merkle-träd en datastruktur som kan ta “n” antal hash och representera det med en enda hash.

Trädets struktur möjliggör effektiv kartläggning av godtyckligt stora mängder data och möjliggör enkel identifiering av var förändringar i dessa data inträffar. Detta koncept möjliggör Merkle-bevis, med vilka någon kan verifiera att hashningen av data är konsekvent hela vägen upp i trädet och i rätt position utan att faktiskt behöva titta på hela uppsättningen hash.

Istället kan de verifiera att en dataklump överensstämmer med rot hash genom att bara kontrollera en liten delmängd av hasharna snarare än hela datamängden.

Så länge root hash är allmänt känd och pålitlig, är det möjligt för alla som vill göra en nyckel-värde-sökning i en databas att använda ett Merkle-bevis för att verifiera positionen och integriteten för en datadel i en databas som har en viss rot.

När root-hash är tillgängligt kan hash-trädet tas emot från valfri icke-betrodd källa och en gren av trädet kan laddas ner åt gången med omedelbar verifiering av dataintegriteten, även om hela trädet ännu inte är tillgängligt.

En av de viktigaste fördelarna med Merkle-trädstrukturen är förmågan att autentisera godtyckligt stora datamängder genom en liknande hashmekanism som används för att verifiera mycket mindre datamängder.

Trädet är fördelaktigt för att distribuera stora datamängder i hanterbara mindre delar där barriären för verifiering av integritet minskas avsevärt trots den totala större datastorleken.

Roten hash kan användas som fingeravtryck för en hel datamängd, inklusive en hel databas eller representerar hela blockchain-tillståndet. I följande avsnitt kommer vi att diskutera hur Bitcoin och andra system implementerar Merkle-träd.

Merkle träd i Bitcoin

Den kryptografiska hashfunktionen som används av Bitcoin är SHA-256-algoritmen. Detta står för “Secure Hashing Algorithm”, vars utdata är fasta 256 bitar i längd. Den grundläggande funktionen för Merkle-träd i Bitcoin är att lagra och så småningom beskära transaktioner i varje block.

Som nämnts tidigare är block i en blockkedja anslutna genom hash av det tidigare blocket. I Bitcoin innehåller varje block alla transaktioner inom det blocket samt blockrubriken som består av:

  • Blockera versionsnummer
  • Föregående Block Hash
  • Tidsstämpel
  • Gruvsvårighetsmål
  • Nonce
  • Merkle Root Hash

Bilden nedan är från Bitcoin vitt papper och illustrerar hur Merkle-trädet passar in i varje block.

Merkle Tree

Transaktionerna ingår i block av gruvarbetare och hashas som en del av ett Merkle-träd, vilket leder till Merkle-roten som lagras i blockhuvudet. Denna design har ett antal distinkta fördelar.

Framför allt, som beskrivs i vitboken, möjliggör detta existens av Simple Payment Verification (SPV) -noder, även kända som “lätta klienter”. Dessa noder behöver inte ladda ner hela Bitcoin-blockkedjan, bara blockrubrikerna för den längsta kedjan.

SPV-noder kan uppnå detta genom att fråga sina peer-noder tills de är övertygade om att de lagrade blockrubrikerna de arbetar med är en del av den längsta kedjan. En SPV-nod kan sedan bestämma statusen för en transaktion genom att använda Merkle-beviset för att kartlägga transaktionen till ett specifikt Merkle-träd med respektive Merkle-trädets root-hash i ett blockrubrik som ingår i den längsta kedjan.

Dessutom möjliggör Bitcoins implementering av Merkle-träd beskärning av blockkedjan för att spara utrymme. Detta är ett resultat av att endast root-hash lagras i blockhuvudet, därför kan gamla block beskäras genom att man tar bort onödiga grenar av Merkle-trädet medan man bara bevarar de som behövs för Merkle-beviset.

Implementering av Merkle Trees i andra blockkedjor och system

Även om Bitcoin var den första blockkedjan som implementerade Merkle-träd implementerar många andra blockkedjor liknande Merkle-trädstrukturer eller ännu mer komplexa versioner.

Vidare är Merkle-trädimplementeringen inte bara begränsad till blockkedjor och tillämpas på en mängd andra system.

Ethereum, som är den andra mest kända kryptovalutan, är också ett utmärkt exempel på en annan implementering av Merkle-trädet. Eftersom Ethereum är turing-komplett som en plattform för att bygga mycket mer komplexa applikationer använder den en mer komplex version av Merkle-trädet som kallas ett Merkle Patricia Tree som faktiskt är 3 separata Merkle-träd som används för tre typer av objekt. Du kan lära dig mer om dessa träd här.

Slutligen är Merkle-träd en viktig komponent i distribuerade versionskontrollsystem som Git och IPFS. Deras förmåga att enkelt säkerställa och verifiera integriteten hos data som delas mellan datorer i ett P2P-format gör dem ovärderliga för dessa system.

Slutsats

Merkle-träd är en integrerad del av blockkedjor och låter dem effektivt fungera med bevisbar oföränderlighet och transaktionsintegritet.

Att förstå den roll de spelar i distribuerade nätverk och deras underliggande teknik för kryptografiska hashfunktioner är avgörande för att förstå de grundläggande begreppen inom kryptovalutor när de fortsätter att utvecklas till större och mer komplexa system.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me