Čo je Merkle strom?

Merkle strom je dátová štruktúra, ktorá komprimuje veľký súbor záznamov do jedného krátkeho otlačku (fingerprint). Umožňuje dokázať, že určitý článok je v obrovskej listine, kontrolovaním len niekoľkých malých kúskov, nie celého. Predstavte si rodokmeň, kde každý rodič je súhrnom svojich detí, všetko smeruje k jednému konečnému predkovi.

Mýtus

Merkle strom “uloží” všetky transakcie sám o sebe. Nie úplne. Ukladá iba kompaktné otlačky z nich, a strom sa môže znovu zostaviť z surových záznamov vždy, keď je potrebné.

Ako Merkle strom funguje

Predstavte si blok platieb, ktorý potrebuje rýchly, overiteľný sumarizáciu. Tu je Merkle strom v priamom vysvetlení:

Krok 1: Začnite zo zoznamu položiek ako transakcie, každá z nich je list v strome.
Krok 2: Pretvorte každú položku na krátky otlaček pomocou hash funkcie.
Krok 3: Zospájajte susedné otlačky, zložte každý pár dokopy a znovu hašujte, aby vznikol ich rodič.
Krok 4: Opakujte spájanie a hashing hore, kým nezostane jeden horný otlaček. To je Merkle root tohto súboru.
Krok 5: Aby ste preukázali, že jedno položka je v súbore, stačí iba tá položka spolu s krátkou cestou súrodených otlačkov. Rýchle a malé.

To je myšlienka: malé dôkazy, veľká istota.

Prečo Merkle strom naozaj záleží

Zhrnutím obrovských hŕô (transakčných dát) do jedného kompaktného otlačku, Merkle strom robí overovanie rýchle a lacné.

Výhoda: Môžete overiť začlenenie bez sťahovania celého bloku, šetrí čas a šírku pásma.
Perspektíva: Hodí sa do súčasného internetového režimu: dôveruj, ale overuj, Rolex stretáva Reddit vlákna.
Relevantnosť: Narazíte na to v blokoch Bitcoin, potvrdeniach Ethereum, allowlistoch NFT, airdropoch a rollupoch.

Tip

Ak je počet listov nepárny, väčšina návrhov duplikuje posledný pred hashingom hore stromu. Tiež skontrolujte presný hashovací proces, ktorý vaša reťaz alebo knižnica používa, pretože malé rozdiely pravidiel môžu zmeniť dôkazy.

Kľúčové charakteristiky Merkle stromu

Tu sú veci, ktoré ho robia špeciálnym a užitočným:

Efektivita: Dôkazy zostávajú malé aj keď dátová množina rastie, takže ľahké klientske zariadenia zostávajú ľahké.
Integrita: Zmeňte jeden bajt v listu a zmena sa odrazí na vrchol, čo robí manipuláciu zrejmou.
Koreň: Všetko sa zhrnie do jedného Merkle root, ktorý možno uložiť alebo podpísať pre neskoršie overenie.

Variácie

Merkle strom má niekoľko populárnych variánt, s ktorými sa stretnete:

Binárny: Klasický strom založený na pároch, používaný v blokoch Bitcoin.
Merkle Patricia: Trie založený pohľad pre dáta kľúč-hodnota, používa sa v stave Ethereum a potvrdeniach.
Redukovaný: Obrovský indexovaný strom, kde väčšina listov je prázdna, výborne pre stručné členstvo a dôkazy o neprítomnosti.
Verkle: Novší príbuzný s kratšími dôkazmi pre veľmi veľké rozvetvenie, skúmaný pre budúce upgrady.

Pripomienka

Dôkazy Merkle stromu sú len také spoľahlivé, ako je header alebo checkpoint, ktorý prijímate. Ak dôverujete nesprávnemu koreňu, najčistejší dôkaz nič nepovie.

Príklad

Ľahká peňaženka v štýle Bitcoinu môže overiť vašu platbu kontrolou krátkej cesty hashov od vašej transakcie až k bloku hlavičky, bez stiahnutia celej transakčnej histórie.

Zaujímavosť

Ralph Merkle načrtl tento nápad na konci siedmich desaťročí ako študentský projekt, a dlhé roky sa objavoval v akademických kruhoch, kým Satoshi ho nepoužil v Bitcoine. Dôkaz, že dobré nápady starnú dobre.

Záver

Bottom line? Merkle strom vám dá rýchle, malé dôkazy, že niečo patrí do veľkej množiny, bez drámy a bez ťažkých sťahovaní.

Merkle Tree