Ett Merkle-träd är en datastruktur som används i datavetenskapliga applikationer. I bitcoin och andra kryptokurser används Merkle-träd för att koda blockchain-data mer effektivt och säkert.
De kallas också "binära hashträd."
Bryta ner Merkle Tree
I bitcoin's blockchain körs ett block av transaktioner genom en algoritm för att generera en hash, som är en sträng med siffror och bokstäver som kan användas för att verifiera att en given uppsättning data är densamma som den ursprungliga uppsättningen transaktioner, men att inte få den ursprungliga uppsättningen transaktioner. Bitcoin programvara kör inte hela blocket av transaktionsdata - vilket i genomsnitt representerar 10 minuters transaktioner - genom hashfunktionen samtidigt. Snarare är varje transaktion hashad, sedan kopplas varje transaktionpar samman och hashas ihop, och så vidare tills det finns en hash för hela blocket. (Om det finns ett udda antal transaktioner fördubblas en transaktion och dess hash är sammankopplad med sig själv.)
Visualiserad, den här strukturen liknar ett träd. I diagrammet nedan betecknar "T" en transaktion, "H" en hash. Observera att bilden är mycket förenklad; ett genomsnittligt block innehåller över 500 transaktioner, inte åtta.
Hastorna på den nedre raden benämns "löv", de mellanliggande hasherna som "grenar" och hashen överst som "roten". Merkle-roten för ett visst block lagras i rubriken: till exempel är Merkle-roten till block # 482819 e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Roten kombineras med annan information (programvaruversionen, det tidigare blockets hash, tidsstämpeln, svårighetsmålet och nonce) och kör sedan genom en hashfunktion för att producera blockets unika hash: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 i fallet med block # 48. Denna hash ingår inte faktiskt i det relevanta blocket, utan det nästa; det skiljer sig från Merkle-roten.
Merkle-trädet är användbart eftersom det tillåter användare att verifiera en specifik transaktion utan att ladda ner hela blockchainen (över 130 gigabyte i slutet av augusti 2017). Säg till exempel att du ville verifiera att transaktion T D ingår i blocket i diagrammet ovan. Om du har root-hash (H ABCDEFGH) är processen som ett spel med sudoku: du frågar nätverket om H D, och det returnerar H C, H AB och H EFGH. Merkle-trädet låter dig verifiera att allt redovisas med tre hash: med tanke på H AB, H C, H EFGH och roten H ABCDEFGH, H D (den enda saknade hash) måste finnas i data.
Merkle-träd är uppkallad efter Ralph Merkle, som föreslog dem i ett papper från 1987 med titeln "En digital signatur baserad på en konventionell krypteringsfunktion." Merkle uppfann också kryptografisk hashing.
