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]).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Nu primești eroare, ci o rădăcină Merkle greșită: o tranzacție din bloc nu mai e acoperită de rădăcină. Semnul clasic: un bloc cu 3 tranzacții are aceeași rădăcină ca blocul cu primele 2, deci a treia poate fi schimbată fără ca rădăcina să se modifice.
Cauza e o încercare de a evita IndexError la perechi: range(0, len(nivel) - 1, 2) nu mai citește nivel[i + 1] dincolo de capăt, dar nici nu mai include ultimul nod. Regula din Bitcoin pentru niveluri cu număr impar de noduri e să dublezi ultimul hash (îl împerechezi cu el însuși). Regula se aplică la fiecare nivel, nu doar la frunze: 5 tranzacții dau 3 noduri pe nivelul următor, deci și acolo se dublează ultimul.
De ce apare: cauzele frecvente
1Ultimul nod sărit
while len(nivel) > 1:
nivel = [sha(nivel[i] + nivel[i + 1]) for i in range(0, len(nivel) - 1, 2)]while len(nivel) > 1:
if len(nivel) % 2 == 1:
nivel.append(nivel[-1])
nivel = [sha(nivel[i] + nivel[i + 1]) for i in range(0, len(nivel), 2)]Dublezi ultimul nod la fiecare nivel impar, apoi faci perechi pe toată lungimea.
2Dublare doar la frunze
if len(frunze) % 2:
frunze.append(frunze[-1])
nivel = frunze
while len(nivel) > 1:
nivel = [sha(nivel[i] + nivel[i + 1]) for i in range(0, len(nivel) - 1, 2)]nivel = frunze
while len(nivel) > 1:
if len(nivel) % 2:
nivel.append(nivel[-1])
nivel = [sha(nivel[i] + nivel[i + 1]) for i in range(0, len(nivel), 2)]Și nivelurile intermediare pot avea număr impar de noduri.
Repară eroarea, direct în pagină
Funcția radacina_merkle de mai jos dă aceeași rădăcină pentru 3 tranzacții ca pentru primele 2, deci a treia nu e protejată. Repară-o după regula Bitcoin (dublezi ultimul nod la fiecare nivel cu număr impar), ca programul să afișeze 3 tx = 2 tx: False și 3 tx = 3 tx + dublură: True.
import hashlib
def sha(b):
return hashlib.sha256(b).digest()
def radacina_merkle(txs):
nivel = [sha(t.encode()) for t in txs]
while len(nivel) > 1:
nivel = [sha(nivel[i] + nivel[i + 1]) for i in range(0, len(nivel) - 1, 2)]
return nivel[0].hex()
doua = ["Ana->Bogdan:5", "Bogdan->Carmen:2"]
trei = doua + ["Carmen->Dan:1"]
r2, r3 = radacina_merkle(doua), radacina_merkle(trei)
print("Rădăcină 3 tx:", r3[:16])
print("3 tx = 2 tx:", r3 == r2)
print("3 tx = 3 tx + dublură:", r3 == radacina_merkle(trei + ["Carmen->Dan:1"]))Rădăcină 3 tx: 33e6a66f76d77cef 3 tx = 2 tx: False 3 tx = 3 tx + dublură: True
Indiciu
La un nivel cu număr impar de noduri, adaugă încă o dată ultimul nod înainte să faci perechile.
Reparația
import hashlib
def sha(b):
return hashlib.sha256(b).digest()
def radacina_merkle(txs):
nivel = [sha(t.encode()) for t in txs]
while len(nivel) > 1:
if len(nivel) % 2 == 1:
nivel.append(nivel[-1])
nivel = [sha(nivel[i] + nivel[i + 1]) for i in range(0, len(nivel), 2)]
return nivel[0].hex()
doua = ["Ana->Bogdan:5", "Bogdan->Carmen:2"]
trei = doua + ["Carmen->Dan:1"]
r2, r3 = radacina_merkle(doua), radacina_merkle(trei)
print("Rădăcină 3 tx:", r3[:16])
print("3 tx = 2 tx:", r3 == r2)
print("3 tx = 3 tx + dublură:", r3 == radacina_merkle(trei + ["Carmen->Dan:1"]))De ce merge
Cu range(0, len(nivel) - 1, 2), la 3 frunze se făcea o singură pereche (0 și 1), iar frunza 2 dispărea, deci rădăcina era cea a primelor două tranzacții. Dublând ultimul nod la fiecare nivel impar, a treia tranzacție intră în calcul. Ultima linie arată și efectul regulii: lista cu ultima tranzacție dublată are aceeași rădăcină.
Cum o eviți pe viitor
Testează funcția Merkle pe 1, 2, 3, 4 și 5 tranzacții și verifică două lucruri: rădăcina pentru 3 tranzacții e diferită de cea pentru primele 2, iar rădăcina pentru [a, b, c] e egală cu cea pentru [a, b, c, c] (efectul dublării, o slăbiciune cunoscută din Bitcoin, CVE-2012-2459). Pune dublarea în interiorul buclei, nu înainte de ea.
Întrebări frecvente
De ce Bitcoin dublează ultimul nod și nu îl urcă direct?
E o alegere de design din implementarea originală. Alte sisteme urcă nodul fără pereche neschimbat sau folosesc un hash gol. Important e ca toate nodurile să folosească aceeași regulă.
Dublarea nu creează probleme?
Da, una: [a, b, c] și [a, b, c, c] au aceeași rădăcină. Bitcoin o tratează respingând blocurile cu tranzacții duplicate.
Erori înrudite
IndexError: list index out of range Ai cerut un element de pe o poziție care nu există în listă: de obicei frunze[i + 1] la un arbore Merkle cu număr impar de tranzacții sau lant[-1] pe un lanț gol. Verifică lungimea listei înainte și tratează cazul impar sau gol. 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 +. Hash diferit pentru aceleași date: ordinea cheilor în json.dumps Două dicționare cu aceleași date, dar cu cheile adăugate în altă ordine, dau texte JSON diferite, deci hash-uri diferite. Serializează determinist: json.dumps(date, sort_keys=True, separators=(",", ":")). Î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.
