Haketarboj en Bitcoin

Haketarboj (ankaŭ nomitaj arboj de Merkle) uziĝas en programoj de samtavola ŝutada kaj sekuraj aplikoj. Bitcoin kaj aliaj retmonoj uzas ilin kaj ili estas unu el la plej gravaj teknikoj en retmono, sed ne la solaj.

Bitcoin uzas blokĉenon por trakti ĝian datumon, sed la blokĉeno ne estas haketarbo, la blokĉeno enhavas datumon pri la ĝiroj kaj la sistemo uzas haketarbo por certigi tiun datumon.

Kiel funkcias haketarboj

Baze, oni kreas arbon kie la foliaj nodoj konektas al datumero kaj la nodo enhavas la haketaĵon de la datumo. Ĝi kalkulas la haketaĵon per haketfunkcio. (Resume haketfunkcio prenas datumon de malfiksita longeco kaj kreas datumon de antaŭfiksita longeco kun eble aliaj trajtoj kiel: malfacileco ke oni krei alian originalan datumon kiu ankaŭ produktas la saman haketaĵon). La haketaĵo de ĉiuj nefolia nodo estas la haketaĵo de la kombinaĵo de siaj filaj nodoj. Ekzemple, por la nodo "Haketaĵo a" ĝia haketaĵo estas la sumo de "Haketaĵo α" kaj "Haketaĵo β". Tiel por certigi ke la haketarbo ne ŝanĝiĝas, oni povas kompari la haketaĵo de la radikaj nodoj.

Kiel Bitcoin kreas haketarbo por la ĝiroj

Bitcoin ne uzas haketarbon por la blokĉenon, sed uzas la algoritmon por la datumujo de ĝiroj.

La algoritmo estas jene:

1. Bitcoin duope haketaĵigas datumeron, do ni difinu duopeHaketigi estu sha256(sha256(ion)). 
2. Se la nombro de datumeroj estas nepara, ni uzas la haketaĵo de la lasta datumero dufoje. 

Alia ol tio ĝi kreas haketaĵon rikure el tavoloj por aro de ĝirojn.

Ekzemple:

d1 = duopeHaketigi(a)
d2 = duopeHaketigi(b)
d3 = duopeHaketigi(c)
d4 = duopeHaketigi(ĉ)
d5 = duopeHaketigi(d)
d6 = duopeHaketigi(d)

a, b, c, ĉ, kaj d estas ĝiroj. Por la unua rikuro ni haketigas ilin, rimarku ke ni havas nepara nombro da ĝiroj, do ni ripetas duopeHaketigi(d) denove. Tiam ni parigas la haketaĵojn kaj kalkulas novajn haketaĵojn:

d7 = duopeHaketigi(d1 ĉemeti d2)
d8 = duopeHaketigi(d3 ĉemeti d4)
d9 = duopeHaketigi(d5 ĉemeti d6)
d10 = duopeHaketigi(d5 ĉemeti d6)

kaj faru tion denove

d11 = duopeHaketigi(d7 ĉemeti d8)
d12 = duopeHaketigi(d9 ĉemeti d10)

kaj fine

d13 = duopeHaketigi(d11 ĉemeti d12)


d13 estas la radiko de la haketarbo por la ĝiroj.

Kiel ĝi uziĝas en la blokĉeno

La blokĉeno enhavas ĉapon, haketaĵon, haketaĵon de la antaŭa bloko kaj la radiko de la haketarbo, kalkulite kiel supre. Oni povas bildigi ĝin kiel:

Tie, por bloko 1 la "radiko de haketarbo" estus d13 kaj la "Ĝiroj de bloko 1" enhavus la datumon.

Fino

Ja estas aliaj partoj de la blokĉeno, sed nun vi almenaŭ komprenas kiel la sistemo traktas kaj sekurigas ĝirojn.

Demandoj

• Ĉu vi povas pripensi aliajn uzojn por haketarboj?
• Se vi aldonus alian folian nodon al haketarbo, kiom da nodoj oni bezonus ĝisdatigi?
• Ĉu haketarbo funkcias pli simila al funkcia datumstrukturo ol ordema datumstrukturo?