Dovada Merkle pică: ordinea stânga / dreapta a fraților inversată
La verificarea unei dovezi Merkle, fiecare frate trebuie lipit în partea corectă: h(frate + curent) dacă fratele e în stânga, h(curent + frate) dacă e în dreapta. Dacă lipești mereu în aceeași parte, dovada pică pentru aproape toate tranzacțiile.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Nu primești nicio eroare: funcția de verificare întoarce False pentru o tranzacție care chiar e în bloc, sau merge doar pentru prima tranzacție (cea mai din stânga). Concatenarea nu e comutativă: h(a + b) și h(b + a) sunt hash-uri complet diferite, deci ordinea contează la fiecare nivel.
O dovadă Merkle (folosită de portofelele ușoare SPV) este lista hash-urilor-frați de pe drumul de la frunză la rădăcină, plus poziția fiecăruia (stânga sau dreapta), dată explicit sau dedusă din indexul frunzei: la fiecare nivel, dacă indexul curent e par, fratele e în dreapta; dacă e impar, în stânga; apoi indexul se împarte la 2. Greșeala tipică e să ignori poziția și să scrii mereu h(curent + frate), care e corect doar când nodul curent e copil stâng. Testează verificarea pentru fiecare frunză din arbore, nu doar pentru prima.
De ce apare: cauzele frecvente
1Fratele lipit mereu în dreapta
for frate, parte in dovada:
curent = h(curent + frate)for frate, parte in dovada:
curent = h(frate + curent) if parte == "stanga" else h(curent + frate)Poziția fratelui spune în ce ordine se lipesc cele două hash-uri.
2Poziția dedusă greșit din index
parte = "stanga" if index % 2 == 0 else "dreapta"parte = "dreapta" if index % 2 == 0 else "stanga"
index //= 2Un nod cu index par e copil stâng, deci fratele lui e în dreapta; indexul se înjumătățește la fiecare nivel.
Repară eroarea, direct în pagină
Funcția verifica de mai jos primește o tranzacție, dovada ei Merkle (perechi frate + parte) și rădăcina blocului, dar lipește mereu fratele în dreapta, așa că dovezile pentru tx2, tx3 și tx4 pică. Repară funcția ca să țină cont de parte, iar programul să afișeze True pentru toate cele patru tranzacții.
import hashlib
def h(b):
return hashlib.sha256(b).digest()
tx = [b"tx1", b"tx2", b"tx3", b"tx4"]
f = [h(t) for t in tx]
n01, n23 = h(f[0] + f[1]), h(f[2] + f[3])
radacina = h(n01 + n23)
dovezi = {
0: [(f[1], "dreapta"), (n23, "dreapta")],
1: [(f[0], "stanga"), (n23, "dreapta")],
2: [(f[3], "dreapta"), (n01, "stanga")],
3: [(f[2], "stanga"), (n01, "stanga")],
}
def verifica(t, dovada, radacina):
curent = h(t)
for frate, parte in dovada:
curent = h(curent + frate)
return curent == radacina
for i, t in enumerate(tx):
print(t.decode(), verifica(t, dovezi[i], radacina))tx1 True tx2 True tx3 True tx4 True
Indiciu
Dacă fratele e în stânga, el vine primul la lipire.
Reparația
import hashlib
def h(b):
return hashlib.sha256(b).digest()
tx = [b"tx1", b"tx2", b"tx3", b"tx4"]
f = [h(t) for t in tx]
n01, n23 = h(f[0] + f[1]), h(f[2] + f[3])
radacina = h(n01 + n23)
dovezi = {
0: [(f[1], "dreapta"), (n23, "dreapta")],
1: [(f[0], "stanga"), (n23, "dreapta")],
2: [(f[3], "dreapta"), (n01, "stanga")],
3: [(f[2], "stanga"), (n01, "stanga")],
}
def verifica(t, dovada, radacina):
curent = h(t)
for frate, parte in dovada:
if parte == "stanga":
curent = h(frate + curent)
else:
curent = h(curent + frate)
return curent == radacina
for i, t in enumerate(tx):
print(t.decode(), verifica(t, dovezi[i], radacina))De ce merge
h(a + b) și h(b + a) sunt hash-uri diferite, deci ordinea lipirii trebuie să refacă exact arborele original. Pentru tx3, primul frate (tx4) e în dreapta, dar al doilea (n01) e în stânga, iar codul vechi îl lipea în partea greșită. Cu verificarea părții, toate cele patru dovezi ajung la aceeași rădăcină.
Cum o eviți pe viitor
Scrie verificarea și construirea dovezii împreună și testează-le pe toate frunzele unui arbore cu 4 și cu 5 tranzacții (cazul impar). Păstrează poziția explicit în dovadă, ca pereche (hash, "stanga" sau "dreapta"), în loc să te bazezi pe convenții implicite. Desenează arborele pe hârtie pentru un caz mic și urmărește drumul unei frunze din dreapta.
Întrebări frecvente
De ce verificarea merge pentru prima tranzacție?
Pentru că prima frunză e copil stâng la toate nivelurile, deci fratele e mereu în dreapta, exact cum presupune codul greșit.
Nu pot sorta cele două hash-uri înainte de lipire?
Unele sisteme fac asta (de exemplu listele albe Merkle din unele contracte Ethereum), și atunci poziția nu mai contează. Dar trebuie ca și construirea arborelui să sorteze; Bitcoin nu sortează.
Erori înrudite
Rădăcina Merkle diferită: concatenezi textul hex în loc de bytes Hash-ul unui nod din arborele Merkle se calculează din cei 32 + 32 de bytes ai copiilor lipiți, nu din cele 64 + 64 de caractere hex ale lor. Cu hexdigest() + hexdigest() obții alt hash. Lucrează cu digest() în arbore și transformă în hex doar la afișare. Rădăcina Merkle ignoră ultima tranzacție la număr impar Bucla care face perechi merge până la len(nivel) - 1, așa că la un număr impar de noduri ultimul rămâne fără pereche și dispare. În Bitcoin ultimul nod se dublează: if len(nivel) % 2: nivel.append(nivel[-1]). TypeError: sequence item 0: expected str instance, bytes found Ai lipit cu "".join(...) o listă de bytes, de obicei hash-uri digest() într-un arbore Merkle. Separatorul text "" lipește doar texte: pentru bytes folosește b"".join(...), sau concatenează direct cu +. Învață Blockchain de la zero, cu exerciții la fiecare lecție
Curs Blockchain și criptomonede: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 15 lecții sunt gratuite.
