teisipäev, 24. november 2015

hashcash elektroonilised postmargid

Üks võibolla veidi varju jäänud, kuid tegelikult laialt kasutatav kontseptsioon on töötamise kinnituse (proof of work) algoritm hashcash. Minu huvi selle algoritmi vastu on eelkõige seotud e-postiga, kuid algoritmi tuntuim kasutus on hoopis seotud krüptoraha Bitcoin protokolliga, sest justnimelt hashcash on see "ülesanne," mida kõik Bitcoini kaevurid jooksvalt lahendama peavad. Hashcashi räside omaduseks on see, et neid on raske genereerida (nõuab palju CPU jõudu), aga kerge kontrollida (CPU kulu on olematu).

Asja tuum on iseenesest lihtne: üks osapool saab hashcashi abil teisele tõestada, et on teinud mingi küsimuse lahendamise nimel märkimisväärse hulga tööd. E-posti puhul oleks pidanud see töö kujunema elektroonilise postmargi hinnaks. Saatja peab kirja saatmiseks investeerima mõnevõrra CPU tsükleid ehk siis maksma "margi" eest, kus "margiks" on töö tulemus ning margi olemasolu kirja päises tõestaks saatja panust. Lihtne ülesanne legitiimsele saatjale ("margi" genereerimine võtab võibolla vaid sekundi), aga raske spämmerile, kes peaks selliseid marke genereerima suures koguses.

Paraku ei saanud hashcash postmarkidest kunagi eriti asja. SpamAssassin suhtub margipäise (X-Hashcash) olemasollu positiivselt, aga sellega enamvähem selle levik ka piirdub. Spämmi küsimuses on see ka täiesti mõistetav – protokolli loojad ei saanud omal ajal kuidagi ette näha, et tänaseks on spämmerite käsutuses suure arvutusvõimsusega botnet'id, mis suudaks vajaminevaid marke arvutada tõenäoliselt kiireminigi (tegu on siiski väga kergesti paralleliseeritava ülesandega), kui legitiimsed saatjad seda teha saaks.

Nüüd aga siis algoritmi enda juurde. Tegu on suuresti tavalise räsi genereerimisega (hashcash puhul sha1, bitcoini puhul sha256), kuid mitte ainult. Töö tegemine garanteeritakse räsile tingimuste seadmisega, näiteks elektrooniliste markide puhul peavad räsi esimesed 20 bitti olema väärtusega 0. Mõnevõrra on see sarnane eelmises postituses kirjeldatud meetodile onion domeeninimede genereerimisele, ainult et kui seal tahtsime saada räsi (domeeninime) algusesse mingeid oma valitud sümboleid, siis hashcash puhul loetakse räsi algusest 0 bitte. Kusjuures margiks ei ole mitte räsi ise, vaid väärtus, millest sellise räsi saime.

Näide

Ütleme, et tahame saata kirja aadressile andris.reinman@gmail.com ning nüüd on meil vaja genereerida selle aadressi jaoks üks mark. Mark sisaldab andmeid algoritmi kohta (milline hashcash versioon, mitu nullbitti peab olema), saaja kohta (ehk siis saaja e-posti aadress) ning juhuslikku väärtust (nonce). Kuna nonce genereerimine võib olla liiga kulukas, siis saame väärtusele lisada ka kaunteri – iga kord kui teeme väärtusest räsi ja selle tulemus ei vasta tingimustele, suurendame kaunterit ühe võrra ja proovime uuesti.

Näitna kasutame järgmist marki (protokoll näeb ette väljade eraldajana koolonit):

1:20:151124104010:andris.reinman@gmail.com::riNR+WfrgW1XSEOr:1

Esimene väli on hashcash versioon (1), teine määrab vajaliku arvu nullbitte (20 bitti), kolmas on ajatempel kujul YYMMDD[HHMMSS], neljas on saaja aadress, viies väli on jäetud tuleviku jaoks tühjaks, kuues on nonce ja seitsmes on kaunter (ruumi säästmiseks kasutan kaunteris hex vormingus numbreid).

Igatahes kui me teeme sellest väärtusest sha1 räsi, saame tulemuseks sellise:

2871ead94a099c4b612db8751652f9e8ecf7af01

Nagu näha, ei vasta see kuidagi seatud tingimustele. 20 nullbiti jaoks peaks räsi hex vorming algama 5 nulliga. Aga proovime edasi, suurendame kaunterit nii kaua, kuni leiame soovitud väärtuse.

1946814 räsi hiljem on meil juba selline mark:

1:20:151124104010:andris.reinman@gmail.com::riNR+WfrgW1XSEOr:1db4be

Millest saamegi soovitud tulemuse, kus väärtuse esimesed 20 bitti on 0 bitid:

00000052aa08f0edf3b5d51cb2a1b1efe015af01

Edasi saame kleepida saadud margi juba e-kirja päisesse

X-Hashcash: 1:20:151124104010:andris.reinman@gmail.com::riNR+WfrgW1XSEOr:1db4be

Kui saaja taolise margiga kirja kätte saab, võib ta võtta margist sha1 räsi ja saada samuti sobiva tulemuse. Lisaks peaks saaja kirja panema ka nonce, sest ükski teine mark sama nonce väärtust enam kasutada ei saa. Kolmanda kaitsemeetmena peab saaja jälgima ka kuupäeva, et see ei oleks liiga kaugel minevikus ega ka tulevikus. Kui kõik klapib, võib saaja kirja ehtsaks pidada.

Kommentaare ei ole: