Vad är ett Merkle-träd? Nybörjarguide till denna Blockchain-komponent

Merkle Trees är en grundläggande komponent i blockkedjor som underbygger 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 tillåter dem att skala samtidigt som de tillhandahåller den hash-baserade arkitekturen så att de kan bibehålla dataintegriteten och ett trivialt sätt att verifiera dataintegriteten.

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

Snabb dom: Merkle-träd är datastrukturer sammansatta av kryptografiska hash som möjliggör effektiv integritetsverifiering och kartläggning av stora datamängder, vilket gör dem till en integrerad komponent i system som blockkedjor och distribuerad versionskontroll.

Snabb fakta

Kryptografiska Hash-funktioner

Enkelt uttryckt är en hashfunktion vilken funktion som helst som används för att mappa data av en godtycklig storlek (indata) till en utdata med fast storlek. En hashalgoritm appliceras på datainmatningen och den resulterande utmatningen med fast längd benämns hash.

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

Den resulterande hashen från den godtyckliga inmatningen är inte bara fixerad i längd, den är också helt unik för ingången och själva funktionen är deterministisk. Det vill säga, 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 datamängder nedan som indata, är de resulterande utgångarna unika för varje ingång. Lägg märke till hur i de andra och tredje exemplen, även om skillnaden mellan ingångarna bara är ett ord, de resulterande utgångarna är helt olika.

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

En kryptografisk hashfunktion, Bild från Wikipedia

Eftersom utdatalängden (hashsumman i exemplet) alltid är densamma som bestäms av hashalgoritmen som används, kan enorma mängder data identifieras enbart genom deras resulterande hash.

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

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

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

Varje block är anslutet till varandra genom en hash-pekare, som är hashen av data inuti det föregående blocket tillsammans med adressen till det föregående blocket. Genom att länka datablock i detta format representerar varje resulterande hash i det föregående blocket hela tillståndet för blockkedjan eftersom all hashad data från de tidigare blocken hashas till en hash.

Detta representeras (i fallet med SHA-256-algoritmen) av en utdata (hash) som denna:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Hashen ovan är fingeravtrycket av hela blockkedjans tillstånd före det. Blockkedjans tillstånd före det nya blocket (som hashad data) är indata, och den resulterande hashen är utdata.

Även om det är möjligt att använda kryptografiska hash 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 krångligt.

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

Merkle Trees och Merkle Proofs

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

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

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

Viktigt, lägg märke till hur icke-lövnoderna eller "grenarna" (representerade av Hash 0-0 och Hash 0-1) på vänster sida, är hash för sina respektive barn L1 och L2. Lägg även märke till hur gren Hash 0 är hash för dess sammanlänkade barn, grenar Hash 0-0 och Hash 0-1.

Exemplet ovan är den vanligaste och enklaste formen av ett Merkle-träd känt som ett binärt Merkle-träd. Som du kan se finns det en topphash som är hela trädets hash, känd som rothash. 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 datamängder och möjliggör enkel identifiering av var förändringar i denna data sker. 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 rothashen genom att bara kontrollera en liten delmängd av hasharna snarare än hela datamängden.

Så länge rothashen ä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 på en databas att använda ett Merkle-bevis för att verifiera positionen och integriteten för en databit i en databas som har en speciell rot.

När rothashen är tillgänglig kan hashträdet tas emot från valfri icke-pålitlig 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 Merkles trädstruktur är förmågan att autentisera godtyckligt stora datauppsättningar 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 uppsättningar data till hanterbara mindre delar där barriären för verifiering av integritet är avsevärt reducerad trots den totalt sett större datastorleken.

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

Merkle träd i Bitcoin

Den kryptografiska hash-funktionen som används av Bitcoin är SHA-256-algoritmen. Detta står för "Secure Hashing Algorithm", vars utdata är en fast 256 bitars längd. Den grundläggande funktionen hos 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 blockchain kopplade genom hash från det föregående blocket. I Bitcoin innehåller varje block alla transaktioner inom det blocket samt blockhuvudet 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 whitepaper och illustrerar hur Merkle-trädet passar in i varje block.

Transaktionerna inkluderas 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, tillåter detta existensen av SPV-noder (Simple Payment Verification), även kända som "lättviktsklienter". Dessa noder behöver inte ladda ner hela Bitcoin-blockkedjan, bara blockhuvudena 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 blockhuvuden de arbetar på är en del av den längsta kedjan. En SPV-nod kan sedan bestämma status för en transaktion genom att använda Merkle-beviset för att mappa transaktionen till ett specifikt Merkle-träd med det respektive Merkle-trädets rothash i en blockrubrik som är en del av den längsta kedjan.

Dessutom tillåter Bitcoins implementering av Merkle-träd beskärning av blockkedjan för att spara utrymme. Detta är ett resultat av att endast rothashen lagras i blockhuvudet, därför kan gamla block beskäras genom att ta bort onödiga grenar av Merkle-trädet samtidigt som 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.

Implementeringen av Merkle-trädet är dessutom inte bara begränsad till blockkedjor utan tillämpas på en mängd andra system.

Ethereum, som är den andra mest igenkännliga kryptovalutan, är också ett bra exempel på en annan implementering av Merkle-trädet. Eftersom Ethereum är 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-träd 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äden 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

Merkleträd är en integrerad komponent i blockkedjor och låter dem effektivt fungera med bevisbar oföränderlighet och transaktionsintegritet.

Att förstå vilken roll de spelar i distribuerade nätverk och deras underliggande teknologi 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.