Mikä on Merkle-puu?
Merkle-puu on tietorakenne, joka tiivistää suuren tietuejoukon yhdeksi lyhyeksi sormenjäljeksi. Sen avulla voit todistaa, että kohde kuuluu valtavaan luetteloon, tarkistamalla vain muutaman pienen osan koko luettelon sijaan. Kuvittele sukupuu, jossa jokainen vanhempi on yhteenveto lapsistaan ja kaikki haarat johtavat yhteen lopulliseen kantaisään.
Merkle-puu ”tallentaa” kaikki tapahtumat itse. Ei aivan. Se tallentaa niistä vain tiiviit sormenjäljet, ja puun voi tarvittaessa muodostaa uudelleen alkuperäisistä tietueista.
Näin Merkle-puu toimii
Kuvittele maksuista koostuva lohko, josta tarvitaan nopeasti todennettava yhteenveto. Näin Merkle-puu toimii yksinkertaisesti selitettynä:
- Vaihe 1: Aloita luettelosta, jonka kohteita ovat esimerkiksi tapahtumat. Kukin niistä on puun lehti.
- Vaihe 2: Muunna jokainen kohde lyhyeksi sormenjäljeksi hajautusfunktiolla.
- Vaihe 3: Yhdistä vierekkäiset sormenjäljet pareiksi, liitä kummankin parin osat yhteen ja hajauta tulos uudelleen niiden vanhemman muodostamiseksi.
- Vaihe 4: Jatka parien muodostamista ja hajauttamista taso tasolta, kunnes jäljellä on yksi ylimmän tason sormenjälki. Se on tämän joukon Merkle-juuri.
- Vaihe 5: Todistaaksesi, että kohde kuuluu joukkoon, tarvitset vain kyseisen kohteen ja lyhyen polun sen sisaruskohtien sormenjälkiä. Nopeaa ja vaivatonta.
Siinäpä idea: pieniä todisteita, vahvaa luottamusta.
Miksi Merkle-puu on tärkeä
Tiivistämällä valtavat määrät tapahtumatietoja yhdeksi kompaktiksi sormenjäljeksi Merkle-puu tekee tarkistamisesta nopeaa ja edullista.
- Hyöty: Voit tarkistaa sisältymisen lataamatta koko lohkoa, mikä säästää aikaa ja kaistanleveyttä.
- Näkökulma: Se sopii tämän hetken internetin henkeen: luota, mutta varmista – Rolex kohtaa Reddit-ketjut.
- Merkitys: Törmäät siihen Bitcoin-lohkoissa, Ethereum-tositteissa, NFT-sallittujen listauksissa, airdropeissa ja rollupeissa.
Jos lehtiä on pariton määrä, monet toteutukset kopioivat viimeisen lehden ennen hajauttamista puussa ylöspäin. Tarkista myös tarkasti, mitä hajautusmenetelmää lohkoketjusi tai käyttämäsi kirjasto hyödyntää, sillä pienet erot säännöissä voivat muuttaa todisteita.
Merkle-puun keskeiset ominaisuudet
Seuraavat ominaisuudet tekevät siitä erityisen ja hyödyllisen:
- Tehokkuus: Todisteet pysyvät pieninä, vaikka tietojoukko kasvaisi valtavaksi, joten kevyet asiakkaat pysyvät kevyinä.
- Eheys: Yhden tavun muuttaminen lehdessä välittyy aina juureen asti, jolloin peukalointi näkyy selvästi.
- Juuri: Kaikki tiivistyy yhdeksi Merkle-juureksi, jonka voi tallentaa tai allekirjoittaa myöhempiä tarkistuksia varten.
Muunnelmat
Merkle-puusta on muutamia suosittuja versioita, joihin saatat törmätä:
- Binäärinen: Perinteinen pareihin perustuva malli, jota käytetään Bitcoin-lohkoissa.
- Merkle Patricia: avain-arvo-tiedoille tarkoitettu trie-pohjainen malli, jota käytetään Ethereumin tilassa ja tositteissa.
- Harva: Suuri indeksoitu puu, jonka useimmat lehdet ovat tyhjiä. Sopii erinomaisesti tiiviisiin jäsenyys- ja jäsenyyden puuttumisen todisteisiin.
- Verkle: Uudempi sukulaisrakenne, jonka todisteet ovat lyhyempiä erittäin laajoissa haarautumisissa. Sitä tutkitaan tulevia päivityksiä varten.
Merkle-puun todisteet ovat yhtä luotettavia kuin hyväksymäsi otsake tai tarkistuspiste. Jos luotat väärään juureen, selkeinkään todiste ei kerro mitään.
Esimerkki
Bitcoin-tyylinen kevyt lompakko voi varmistaa maksusi tarkistamalla lyhyen hajautusarvojen polun tapahtumastasi lohkon otsakkeeseen lataamatta koko tapahtumahistoriaa.
Hauska fakta
Ralph Merkle luonnosteli tämän idean 1970-luvun lopulla opiskelijaprojektina, ja se pysyi vuosia akateemisissa piireissä, ennen kuin Satoshi käytti sitä Bitcoinissa. Hyvät ideat kestävät aikaa.
Yhteenveto
Lyhyesti sanottuna Merkle-puu antaa sinulle nopeita ja pieniä todisteita siitä, että jokin kuuluu suureen joukkoon – ilman säätöä ja raskaita latauksia.