Rudarstvo

Ono što je stablo Merkle

Stabla Merkle su temeljni dio onoga što čini blokove blokade. Iako je definitivno teoretski moguće izraditi blockchain bez stabala Merkle, jednostavno stvaranjem ogromnih blokova zaglavlja koja izravno sadrže svaku transakciju, čineći tako veliki izazovi za skalabilnost, koji nedvojbeno stavlja mogućnost bespomoćne upotrebe blokova izvan dosega svih, ali najviše moćna računala na duži rok.

Zahvaljujući stablima Merkle, moguće je izraditi Ethereum čvorove koji rade na svim računalima i prijenosnicima velikih i malih, pametnih telefona, pa čak i interneta uređaja poput onih koje će proizvoditi Slock. to. Pa kako točno funkcioniraju ova stabla Merkle, i koja vrijednost oni pružaju, sada iu budućnosti?

Prvo , osnove. Stablo Merkle, u najopćenitijem smislu, je način da se istovara veliki broj komada podataka koji se oslanjaju na podjelu komada u kante, gdje svaka vrećica sadrži samo nekoliko komada, a zatim uzima lijes svakog kante i ponavlja isti proces, nastavljajući to sve dok ukupan broj preostalih hashova ne postane samo jedan: root hash.

Najčešći i najjednostavniji oblik stabla Merkle je binarni Mekle stablo, gdje se kantu uvijek sastoji od dva susjedna komada ili haseka; može se prikazati na sljedeći način:

Kakva je to prednost ovog neobičnog algoritma raspršivanja? Zašto ne samo spojiti sve komade u jednu veliku komad i koristiti redoviti algoritam raspršivanja na to? Odgovor je da omogućava uredan mehanizam poznat kao Merkle dokaz:

Merkleov dokaz sastoji se od komade, korijena hashe stabla, a "grana" koja se sastoji od svih haseva koji idu uz put od komad korijena. Netko tko je pročitao dokaz može potvrditi da je hashing, barem za tu granu, dosljedan i ide sve do stabla i stoga da je dani komad zapravo na toj poziciji na stablu.

Aplikacija je jednostavna: pretpostavimo da postoji velika baza podataka i da se cijeli sadržaj baze podataka pohranjuje u stablu Merkle gdje je korijen stabla Merkle javno poznat i pouzdan (npr. Digitalno je potpisan od strane dovoljno pouzdanih stranaka, ili postoji mnogo dokaza o tome da radi na tome). Zatim, korisnik koji želi napraviti ključnu vrijednost pretraživanja u bazi podataka (npr."recite mi da je objekt u poziciji 85273") može zatražiti dokaz o Merkleu, a po primitku dokaza provjeriti je li točan i stoga je vrijednost primljene zapravo na poziciji 85273 u bazi s tim posebno korijena.

Omogućuje mehanizam za ovjeravanje malog količine podataka, kao što je hash, koji se proširuje i na autentifikaciju velikih baza podataka potencijalno neograničene veličine.

Prednost koju pruža jest koncept koji je Satoshi opisao kao "pojednostavljenu provjeru plaćanja": umjesto da preuzme

svaku

transakciju i svaki blok, "lakši klijent" može skinuti samo lanac zaglavlja zaglavlja , 80-byte komada podataka za svaki blok koji sadrži samo pet stvari: hash prethodnog zaglavlja vremensku oznaku

  • vrijednost miniranja
  • dokaz rad nonce
  • korijenski raspršivač za stablo Merkle koji sadrži transakcije za taj blok.
  • Ako svjetlosni klijent želi odrediti status transakcije, može jednostavno zatražiti dokaz o Merkleu koji pokazuje da je određena transakcija u jednoj od stabala Merkle čiji je korijen u zaglavlju blokova za glavni lanac.
  • To nam donosi prilično daleko, ali klijenti lakog tipa Bitcoina imaju ograničenja. Jedno od ograničenja je to što, dok mogu dokazati uključivanje transakcija, ne mogu dokazati ništa o trenutnom stanju (npr. Digitalna imovina, registracija imena, status financijskih ugovora itd.). Koliko imaš bitcoina sada?

Bitcoin Light klijent može koristiti protokol koji uključuje upite višestrukih čvorova i vjerujući da će barem jedan od njih obavijestiti o određenoj potrošnji transakcija iz vaših adresa, a to će vam donijeti prilično daleko za taj slučaj upotrebe, ali za druge složenije aplikacije nije dovoljno dovoljno; točna narav učinka transakcije može ovisiti o učinci nekoliko prethodnih transakcija, koji sami ovise o prethodnim transakcijama, pa bi u konačnici trebali autentificirati svaku pojedinu transakciju u cijelom lancu. Da bi se to okrunilo, Ethereum uzima koncept Merkle stabla jedan korak dalje.

Svaki blok zaglavlja u Ethereumu ne sadrži samo jedan Merkle stablo, ali

tri

stabla za tri vrste objekata:

Transakcije Primici (u osnovi, dijelovi podaci koji pokazuju efekt

  • svake transakcije)
  • Država To omogućuje napredni napredak svjetlosnog klijentskog protokola koji omogućuje lakim klijentima da lako stvaraju i daju provjerljive odgovore na mnoge vrste upita: Je li ta transakcija uključena u određeni blok?
  • Recite mi sve slučajeve događaja tipa X (npr. Ugovor o udovoljavanju grupama koji je postigao cilj) koji je emitirala ova adresa u posljednjih 30 dana

Koji je trenutni saldo računa?

  • Ima li ovaj račun?
  • Pretpostavimo pokretanje ove transakcije u ovom ugovoru. Kakav bi bio izlaz?
  • Prvo se obrađuje stablo transakcije; treći i četvrti obrađuju drvo stablo, a drugi stablo prijema. Prva četiri su prilično jednostavna za izračunavanje; poslužitelj jednostavno pronalazi objekt, prenosi Merkleovu granu (popis haseva koji se kreću od objekta do korijena stabla) i odgovara natrag svjetlosnom klijentu s ogrankom.
  • Peti također upravlja stablo države, ali način na koji se izračunava je složeniji. Ovdje moramo konstruirati ono što se može nazvati
  • Merkle State transition transition proof

. U biti, to je dokaz koji tvrdi: ako pokrenete transakciju

T na stanje s korijenom S , rezultat će biti stanje s korijenom S , s log L i izlazom O ("izlaz" postoji kao koncept u Ethereumu jer je svaka transakcija funkcionalni poziv, nije teoretski potrebna). Za izračunavanje dokaza, poslužitelj lokalno stvara lažni blok, postavlja stanje na S i pretvara se da je lagan klijent prilikom primjene transakcije. To jest, ako proces primjene transakcije zahtijeva da klijent utvrdi ravnotežu računa, svjetlosni klijent izrađuje upit o ravnoteži. Ako svjetlosni klijent treba provjeriti određenu stavku u pohrani određenog ugovora, svjetlosni klijent postavlja upit za to, i tako dalje. Poslužitelj "odgovara" na sve svoje upite pravilno, ali prati sve podatke koje šalje natrag. Poslužitelj zatim šalje klijentu kombinirane podatke iz svih tih zahtjeva kao dokaz. Klijent zatim poduzima isti postupak, ali

pomoću predviđenog dokaza kao baza podataka

; ako je rezultat jednak onome što poslužitelj tvrdi, klijent prihvaća dokaz.

Patricia Trees Gore je spomenuto da je najjednostavnija vrsta Merkle stabla binarni Merkle stablo; međutim, stabla koja se koriste u Ethereumu su složenija. Ovo je "Merkle Patricia stablo" koju čujete u našoj dokumentaciji. Ovaj članak neće biti u detaljnoj specifikaciji; to je najbolje učiniti ovaj i ovaj članak, iako ću razgovarati o osnovnom rasuđivanju.

Binarni Merkle stabla su vrlo dobre strukture podataka za autentifikaciju podataka koji su u "list" formatu; u osnovi, niz komada jedan za drugim. Za stabla transakcija oni su također dobri, jer nije bitno koliko vremena potrebno za stvaranje stabla, budući da je stablo stvoreno jednom, a zatim zauvijek zamrznuta krutina.

Međutim, za stablo države, situacija je složenija. Država u Ethereumu uglavnom se sastoji od mape s ključem i vrijednošću, gdje su ključevi adrese, a vrijednosti su izjave računa, u kojem se navodi balans, nonce, kôd i pohrana za svaki račun (gdje je pohrana samo stablo). Na primjer, stanje geneze Morden testnet izgleda ovako:

{"0000000000000000000000000000000000000001": {"saldo": "1"}, "0000000000000000000000000000000000000002": {"saldo": "1"}, "0000000000000000000000000000000000000003": { : "1"}, "0000000000000000000000000000000000000004": {"balance": "1"}, "102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {"balance": "1606938044258990275541962092341162602522202993782792835301376"}}

Za razliku od povijesti transakcija, često se ažurira: ravnoteža i kontekst računa često se mijenjaju, a što je više, često se umetaju novi računi, a ključevi u pohrani često se umeću i brišu.Ono što je željeno je struktura podataka u kojoj možemo brzo izračunati novi korijen stabla nakon umetanja, ažuriranja uređivanja ili brisanja operacije bez rekomputacije cijelog stabla. Postoje i dva vrlo poželjna sekundarna svojstva: Dubina stabla je omeđena, čak i kada je u pitanju napadač koji namjerno izrađuje transakcije kako bi stablo bilo što dublje moguće. Inače, napadač može izvršiti napad odricanja od službe manipulacijom stabla tako da bude tako dubok da svaki pojedinačni ažuriranje postaje izuzetno spor. Korijen stabla ovisi samo o podacima, a ne o redoslijedu ažuriranja. Obnavljanje ažuriranja u drugom redoslijedu, pa čak i recomputiranje stabla od nule ne bi trebalo mijenjati korijen.

Patricia stablo, po jednostavnim riječima, možda je najbliži što možemo doći do postizanja svih tih svojstava istovremeno. Najjednostavnije objašnjenje za način na koji to funkcionira jest taj da ključ ispod kojeg se pohranjuje vrijednost kodira u "put" koji morate skloniti stablu. Svaki čvor ima 16 djece, pa je put određen šifriranim kodiranjem: na primjer, ključ

pas

šifrirani kodirani

  • 6 4 6 15 6 7
  • , pa biste počeli s korijenom , spustite 6. dijete, zatim četvrto, i tako dalje dok ne dođete do kraja.

U praksi postoji nekoliko dodatnih optimizacija koje možemo učiniti kako bi proces bio učinkovitiji kada je stablo rijetko, ali to je osnovni princip. Dva gore spomenuta članka opisuju sve značajke u mnogo više detalja.