...
Eroare Blockchain · Arbori Merkle

Dovada Merkle pică: ordinea stânga / dreapta a fraților inversată

Pe scurt

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

Greșit
PYTHON
for frate, parte in dovada:
    curent = h(curent + frate)
Corect
PYTHON
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

Greșit
PYTHON
parte = "stanga" if index % 2 == 0 else "dreapta"
Corect
PYTHON
parte = "dreapta" if index % 2 == 0 else "stanga"
index //= 2

Un nod cu index par e copil stâng, deci fratele lui e în dreapta; indexul se înjumătățește la fiecare nivel.

Repară tu

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.

Codul care dă eroarea
PYTHON
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))
După reparație, programul afișează
tx1 True
tx2 True
tx3 True
tx4 True
Indiciu

Dacă fratele e în stânga, el vine primul la lipire.

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

← Toate erorile Blockchain

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.