Räsipuu

Räsipuu (ka Merkle'i puu) on puu, mille lehed on alusandmestiku räsid ning ülejäänud tipud on oma alamate räsid. Räsipuu põhiline eesmärk on tõestada andmekillu kuulumist tervikusse. Sellise tegevuse keerukus on alusandmestiku suhtes logaritmiline.

Eelised ja omadused

Räsipuu omadused tulenevad otseselt räsifunktsioonide omadustest – peamiselt sellest, et räsifunktsioon on ühepidine. Seetõttu, teades vaid mõne tipu räsi, ei ole enam teada selle alamtipud, küll aga saab kindla hulga alamtippudega arvutada välja juurtipu.

Räsipuul on palju omadusi, mida eraldi eesmärkidena saab ära kasutada:

Vähendab turvatavate andmete mahtu – terviku usaldamiseks piisab juurräsi usaldamisest.
Vähendab edastatavate andmete mahtu – terviku kontrollimiseks piisab tõestada vaid teekond puu lehest juureni.
Varjab kontrollimisel terviku ülejäänud osad – terviku kontrollimisel pole vaja esitada teisi andmekilde.

Turvalisus

Räsipuu turvalisus põhineb kasutatava räsifunktsiooni turvalisusel.

Kuna juurtipp ei viita puu kõrgusele, on eksisteerivale räsipuule teoreetiliselt võimalik konstrueerida mõni selline räsiahel, mille alusandmestik on erinev, kuid mille juurtipp on identne. Sellise ründe hajutamiseks määratakse räsiahelale tihti maksimaalne kõrgus või hoitakse kõrgust tipu lisaparameetrina.

Kasutusalad (kus ja miks)

Bitcoin kasutab räsipuid plokkides tehingute kontrollimiseks.^[1] GuardTime kasutab räsipuid ajatemplite ja võtmevaba allkirjastusmehanismi alustalana.^[2]

Konstrueerimine

Räsipuu ehitatakse mingile andmehulgale nii, et igale andmekillule vastab puus mingi leht. Iga uue tipu saamiseks räsitakse selle alamtipud. Tavaliselt kasutatakse räsipuu ehitamiseks kahendpuud. See tähendab, et iga kihi iga kaks tippu räsitakse kokku järgmise kihi tipuks kuni alles jääb üks tipp.

Tervikusse kuulumise tõestamine

Andmekillu tervikusse kuulumise tõestamiseks piisab teada lehttipust juurtipuni iga sõlmpunkti puuduolevaid komponente. Lisaks on tarvis usaldada juurräsi. Kahendpuul põhineva räsipuu puhul piisab anda iga andmekillu tervikusse kuuluvuse tõestamiseks teekond sõlmtippude vasak- ja parempoolsete räsidena.

Võrdlus plokiahelaga

Teine sarnase eesmärgiga andmestruktuur on plokiahel.

Plokiahel on ahel, milles iga järgmise kirje arvutamisel võetakse arvesse ka eelmist. Nii väljendab ahela viimane kirje krüptograafiliselt tervet ahelat. Plokiahel on seetõttu tavaliselt kasutusel järk-järgult täienevate andmehulkade puhul, näiteks bitcoin'i tehingute puhul.^[1] Räsipuud on aga mugavam ehitada fikseeritud andmehulgale, sest vastasel juhul võib puu kergesti tasakaalust välja minna ning efektiivsuse eelis kaob. Räsipuusse tipu tuleb lisamisel vaadelda puud tervikuna, vajadusel puu tasakaalustada ning muuta kõiki tippe muudetuist juureni.

Kui plokiahela saab sõltuvuste tõttu ehitada vaid jadamisi, siis räsipuu tippe võib konstrueerida ka paralleelselt.

Küll aga plokiahelas mõne keskmise kirje muutumisel tuleb muuta ka kõiki järgnevaid kirjeid; räsipuul tuleb selleks liikuda mööda puud juurtipuni, mis on lihtsam – logaritmilise keerukusega.

Plokiahelas tuleb kirje kontrollimiseks anda kaasa info kõikide järgnevate kirjete kohta; räsipuul tuleb lehe kontrollimiseks kaasa anda vaid sõlmpunktide moodustamiseks vajalikud räsid.

Viited

↑ ^1,0 ^1,1 Ray, Shaan (14. detsember 2017). "Merkle Trees". Hackernoon. Vaadatud 04.12.2019.
↑ Buldas, Ahto; Kroonmaa, Andres; Laanoja, Risto (2013). "Keyless Signatures' Infrastructure: How to Build Global Distributed Hash-Trees" (PDF). Guardtime. Vaadatud 04.12.2019.{{netiviide}}: CS1 hooldus: mitu nime: autorite loend (link)

[:0-1] 1,0 ^1,1 Ray, Shaan (14. detsember 2017). "Merkle Trees". Hackernoon. Vaadatud 04.12.2019.

[2] Buldas, Ahto; Kroonmaa, Andres; Laanoja, Risto (2013). "Keyless Signatures' Infrastructure: How to Build Global Distributed Hash-Trees" (PDF). Guardtime. Vaadatud 04.12.2019.{{netiviide}}: CS1 hooldus: mitu nime: autorite loend (link)

[1]

[2]