...
Eroare Blockchain · Arbori Merkle

Rădăcina Merkle ignoră ultima tranzacție la număr impar

Pe scurt

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

Greșit
PYTHON
while len(nivel) > 1:
    nivel = [sha(nivel[i] + nivel[i + 1]) for i in range(0, len(nivel) - 1, 2)]
Corect
PYTHON
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

Greșit
PYTHON
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)]
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
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"]))
După reparație, programul afișează
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.

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

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