Lehekülje Hajussüsteemid prax 2 2025 kevad lähteteksti vaatamine

[[Fail:minememe.jpg]]

= Ülesanne =

Teise praktikumi jaoks võid valida ühe kahest ülesandest:

* Esimene variant: hajutatud konsensus distributed ledgeris 

* Teine variant on sinu enda valitud teema, mis on õppejõuga eelnevalt kooskõlastatud: et kas sisuliselt sobib ja kas on mõistliku keerukusega. See on mõttekas valik, kui sul on juba mõte mõne rakendusliku süsteemi ise-ehitamiseks ja sisu klapib meie kursusega. Siin allpool selle variandi kohta rohkem nõudeid või soovitusi ei ole.

= Ülesanne: hajutatud konsensus distributed ledgeris =

Stsenaarium on sarnane harilikule plokiahela rakendusele: mitu sõltumatut osapoolt saadavad teistele kirjeid (näiteks, ülekandeid), ning iga osapool salvestab kõiki ülekanded ledgeri faili,
kustiganes nad ka ei tuleks. Samas peavad kõigi osapoolte ledgeri failid olema identsed, seda ka juhul, kui mõni osapool vahel ei saa saadetud ülekannet kätte või keegi saadab 
täielikku jama, mida ignoreeritakse.

Praksi eesmärk on katsetada konsensuse rikkumisega ja realiseerida ledgeri identsuse hoidmine: kas krüptoraha tüüpi proof-of-work kaevandamise või proof-of-stake konsensusega, 
või kasutades [https://en.wikipedia.org/wiki/Distributed_database hajutatud andmebaaside] ideid, soovitavalt king, [https://en.wikipedia.org/wiki/Raft_(algorithm) raft] või mõnda analoogilist tüüpi 
[https://en.wikipedia.org/wiki/Consensus_(computer_science) konsensuse-algoritmi].

Konkreetsemalt siis on sul kaks ülesannet, alustada tuleb esimesega ja seejärel teha teine:

== Esiteks ==

Esiteks, tekita olukordi, kus sinu süsteemis sõlmed saavad mingi tegevuse tulemusena erinevad ledgerid, ja soovitavalt suuta neid olukordi reprodutseerida.

Näide kolme sõlmega (S1, S2, S3):

* Sõlm S1 saadab transaktsiooni T1 sõlmele S2, aga mitte sõlmele S3.
* Sõlm S2 saadab transaktsiooni T2 sõlmele S3, aga mitte sõlmele S1.
* Sõlm S3 saadab transaktsiooni T3 sõlmele S1, aga mitte sõlmele S2

Nüüd on sõlmedel järgmised transaktsiooni-failid: S1 (T1,T3), S2 (T1,T2), S3 (T2,T3).

Selleks, et taolist olukorda tekitada, on üldiselt hea mõte teha hulk sõlmi ja siis lasta mitmel sõlmel üheaegselt genereerida erinevaid transaktsioone ja neid laiali saata: tõenäoliselt jõuavad nad eri sõlmedeni eri järjekordades ja võibolla mõneni üldse ei jõua. Pane tähele, et kui "üheaegselt" asemel teed "järjest", siis võivad transaktsioonid kenasti kõigini samas järjekorras jõuda ja probleemi ei pruugi tekkida. Meie aga tahame just, et probleem tekiks!

== Teiseks ==

Teiseks, realiseeri süsteem, mis tagaks, et kõigil sõlmedel oleks sama ledger ehk transaktsiooni-fail.

Selleks peavad sõlmed suhtlema omavahel ja leppima kokku õige ühise transaktsiooni-faili. 

NB! Kui see perfektselt ei õnnestu, on tulemus ikkagi ok: lihtsalt tuleb ettekandes selgitada, millal töötab ja millal mitte.

Üks variant lahenduseks on realiseerida bitcoini tüüpi pikema haru (või pikema ledgeri) eelistamine.

Teine variant lahenduseks on teha regulaarseid nö koordineerimis-koosolekuid, kus:
* Kõik osapooled käivad järjest läbi kõik viimase koordineerimis-koosoleku järgi saabunud failiread järjekorras R1,R2,R3,..., kus R1 oleks esimene rida peale viimast koordineerimist.
* Iga rea jaoks lepivad osapooled kokku selle rea nö "kuninga", kes saadab kõigile õige sisu.

Arusaadavalt tekib siin palju küsimusi, millele vastused tuleb sul leida (a) enda parema äranägemise järgi, (b) lugedes soovitusi ja artikleid, (c) katsetades. 
Muuhulgas ei ole praksis ette kirjutatud, mis algoritmi kasutada. Soovitus: kasuta võimalikult lihtsat, mis samas põhiprobleemidega hakkama saab. Paxos on kõige levinum,
aga keeruline, Raft veidi lihtsam, aga on veel lihtsamaid ja nõrgemaid (praksi jaoks on nõrk variant ok): loe 
[http://www.di.univaq.it/~proietti/slide_algdist2010/5-Consensus.ppt konsensuse materjalidest] juurde.


Huvitavat ja tõenäoliselt kasulikku näitelugemist (aga otsi ise juurde):
* [https://people.disim.univaq.it/guido.proietti/slide_algdist2022/Bitcoin%202022%20part2.pdf detailne presentatsioon] bitcoinist, eeskätt konsensuse-fookusega; lisaks ka [http://timroughgarden.org/f16/l/l9.pdf sama autori lühitekst], vt [http://timroughgarden.org/notes.html siit] "Incentives in Computer Science" alt.
* [http://liu.diva-portal.org/smash/get/diva2:1368903/FULLTEXT01 Permissioned Blockchains and Distributed Databases: A Performance Study]
* [https://en.wikipedia.org/wiki/Raft_(algorithm) Raft wikipedias] ja [https://www.geeksforgeeks.org/raft-consensus-algorithm/ näiteks siin] 
* [https://yusufs.medium.com/creating-distributed-kv-database-by-implementing-raft-consensus-using-golang-d0884eef2e28 Creating Distributed KV Database by Implementing Raft Consensus Using Golang]

== Praksi tulemusena peab sul olema ==

* Ilma konsensuseta variandi jaoks katsetatud erisuguste olukordadega, kus konsensuse saavutamine ei õnnestu. 
* Implementeeritud mitu sõlme, mis suudavad omavahel eeltoodud tüüpi ülesannet lahendada
* Reaalselt katsetatud erisuguste olukordadega, kus konsensuse saavutamine ei ole triviaalne, aga siiski õnnestub (soovitavalt eelmise punkti tüüpi näited): mida sõlmed saatsid, mida kokku lepiti, mismoodi kokkulepe toimus
* <strong>Teha väike ettekanne, kus:</strong>
** Tood näiteid, kus konsensust (ilma uue algoritmita) esialgu ei saavutatud
** Selgitad valitud/ehitatud konsensue tagamise algoritmi põhimõtteid
** Tood näiteid, kus konsensuse ehitamine töötas
** Tood näiteid, kus konsensuse ehitamine läks rikki (kui seda kunagi ei juhtu, siis muidugi näiteid ei saa tuua)
** Annad kiire ülevaate koodist
** Räägid veidi tööprotsessist: kuidas alustasite, mis olid probleemid, kuidas probleeme lahendasite

= Täienduseks ideid: terve distributed ledger =

Siin allolev jutt ei ole praktikumiülesanne, vaid varasemate aastate ülesande kirjeldusest võetud ideed, kuidas tervet distributed ledgerit ehitada. Siit võid saada ideid käesoleva aasta praksi jaoks.

Siinne eesmärk on saada käima lihtsustatud versioon bitcoini-tüüpi
distributed ledgerist. Keerukaid nüansse - mis päris-bitcoini puhul vajalikud - realiseerida ei ole vaja.

Mis meil oleks - kokkuvõtlikult - vaja esimesele praksile lisada:

* Transaktsiooni sisestamine ja konkreetses formaadis edastamine: kes kannab kellele kui palju raha üle
* Digiallkirjastamine, avalikud ja salajased võtmed
* Transaktsioonide kokkukogumine blokiks ja bloki ülekontrollimine
* Bloki merkle juure ehitamine (salvestame lõpuks ainult tipmise hashi puust)
* Bloki kaevandamine: leia bloki hash, mis algaks N nulliga, katsetades eri nonce. Sea N nii, et kaevandamine võtaks ca 5 sek.
* Mitme paralleelbloki olemasolul pikema ahela või parema bloki valimine
* Loodud bloki automaatselt teistele edasisaatmine

Eeldame, et sinu programm juba kuulab ja salvestab ja saadab edasi talle saadetud transaktsioone ja blokke. 

Konkreetseid detaile ei kirjuta me siin praksis kohustuslikuna ette, kuid järgmisena on toodud soovitusi ja nõuandeid.

Päris hea arusaamist tekitava veebidemo [https://anders.com/blockchain/public-private-keys/blockchain.html leiad siit]: kindlasti vaata ka ülalt menüüst keys/signatures/transaction demosid.

== Transaktsioon ==

Võiks olla ilma allkirjata kujul 

   {"from": "sdasd212121", "to": "dsda9sdasdas9", "sum": 0.01, "timestamp": "2012-04-21T18:25:43-05:00"} 
   
kus timestamp on iso kujul. Seejuures transaktsioon tuleb enne signeerimist stringiks teisenda mingil ühesel universaalsel kujul 
(a la keyd konkreetses järjekorraks ja tühikud key-value paaride vahelt eemaldatud) ja allkirjaga kujul 

  {"signature":"alasasasp11", "transaction": {"from": "sdasd212121", "to": "dsda9sdasdas9", "sum": 0.01, "timestamp": "2012-04-21T18:25:43-05:00"}} 
  

Mis on see "from" ja "to" väärtus, ehk, kuidas kasutajaid/kontosid identifitseerida? Las need olla lihtsalt kasutajate avalikud võtmed, millest me järgmisena räägime.

Sinu programm peaks olema võimeline tegema transaktsioone: näiteks nii, et käivitad ta käsurealt ja annad ette transaktsiooni jsoni, tema
allkirjastab ja saadab allkirjaga edasi.

Või siis ta loeb iga N sekundi tagant faili, kuhu saad kirjutada transaktsioonide jsone.

Või mõnel muul sulle mugaval moel.

Allkirjastatud transaktsioon tuleks teistele progedele edasi saata.

== Digiallkirjastamine, avalikud ja salajased võtmed ==

Sul on oma "konto" tegemiseks vaja genereerida mingi public-key krüptosüsteemi jaoks avaliku ja salajase võtme paar. 
Muidugi on oluline, et kõik võrgustiku osalised kasutaks sama public-key krüptosüsteemi.

Kui oled genereerinud uue avaliku võtme A ja vastava privaatvõtme P, siis, teades A-d, ei suuda keegi teine reaalselt leida sinu P-d.

Olgu sinu A avalik võti ja P sinu vastav privaatvõti. Siis krüpteeri(T,P) annab stringi K, nii et igaüks saab teha dekrüpteeri(K,A) mis annab tulemuse X
ja näha, et tulemus X võrdub algse stringiga T. Samas ei suuda keegi genereerida ise stringi K (teadmata P-d), et saaksime dekrüptimisel sama
tulemuse T.

Peamiselt kasutatakse kas RSA tüüpi või elliptilise kõvera tüüpi public-key krüptosüsteeme. Näiteks vana eesti id-kaart kasutas RSA-d, peale sügisest turvaauku
hakati kasutama elliptilist kõverat. Bitcoin kasutab samuti elliptilist kõverat: ECDSA varianti standardse elliptise kurviga "secp256k1". Meie praksis
kasuta lihtsalt sellist süsteemi, mille saad kergemini käima ja mida on sul kergem kasutada.

Kust leida public key krüptograafia teeke?
* Pythoni jaoks on hea variant näiteks [https://github.com/warner/python-ecdsa python-ecdsa]
* Kõige mainstreamim universaalne teek (koos käsurea-utiliitidega) on [https://www.openssl.org/ openssl]
* Pythonis saad openssl-i kasutada näiteks [https://pyopenssl.org/en/stable/ pyopenssl] wrapperiga või käsurea-utiliitidega.

Hea mõte on wikipediast lisaks lugeda [https://en.wikipedia.org/wiki/Public-key_cryptography public key cryptography] ja
[https://en.wikipedia.org/wiki/Digital_signature digital signature].

NB! Põhimõtteliselt võid digiallkirja (ehk, privaatvõtmega krüpteeritud stringi) arvutada kas otse transaktsiooni stringi-kujust või siis selle stringi-kuju SHA hashist.
Miks SHA hashe kasutatakse? Sest pika stringi krüpteerimine on aeglane ja SHA hash on suhteliselt lühike ka pikkade algstringide korral.

== Transaktsioonide kokkukogumine blokiks ja blokiandmete ülekontrollimine ==

Ütleme, et sinuni on jõudnud N transaktsiooni. Sina tahad nad blokiks kokku panna. Kõigepealt vaata, millised transaktsioonid juba on mõnes sinule teada olevas blokis: 
neid ära võta.

Järgmisena peaksid kontrollima, kas kõik transaktsioonid on õieti allkirjastatud: selleks pead transaktsiooni allkirjad transaktsiooni avaliku võtmega 
dekrüptima ja kontrollima, kas tuleb transaktsioonistring: vaata eelmist peatükki.

Järgmisena peaksid kontrollima, kas transaktsiooni tegijal on piisavalt raha: selleks summeeri kõik talle saadetud ja tema poolt saadetud summad üle kõigi sulle
teada olevate blokkide. 

Järgmisena peaksid kontrollima, kas mõni transaktsioon on juba uues kokkupandavas blokis või mõnes vanas blokis olemas: kui jah, siis seda ei tohi kasutada.

Kui mõni transaktsioon on valesti allkirjastatud või raha ei jätku või on topelt, viska see transaktsioon lihtsalt ära.

Reaalse bitcoini kontrolli-algoritmi [https://en.bitcoin.it/wiki/Protocol_rules#.22block.22_messages leiad siit] ja
andmestrukuurid [https://en.bitcoin.it/wiki/Protocol_documentation siit]: seal on praktikumi jaoks liiga palju
detaile, nii et soovitaks mitte hakata kogu seda "ametlikku" süsteemi implementeerima.

Lisa transaktsioonidele veel üks: endale nullist raha kandmine. Pane see näiteks viimaseks transaktsiooniks ja kanna endale 1 coin. Saatja identifikaatoriks
pane näiteks 0. Seda transaktsiooni pole mõtet allkirjastada, jäägu see "eritransaktsiooni" jaoks tühjaks (kontrollimise käigus peaks siis vastavalt vaatama,
et blokis võib olla üks selline 0-saatjaga ilma allkirjata transaktsioon ja see on ok).

Nüüd pane kontrolli edukalt läbinud transaktsioonid blokiks kokku. Selles tee näiteks key/value struktuur ehk json näiteks nii:

   {
    "nr": bloki_number_ehk_eelmise_bloki_nr+1,
    "previous_hash": ahelas_eelmise_bloki_hash,
    "timestamp":  "2012-04-21T18:25:43-05:00",
    "nonce": "asasas11", 
    "hash": "000000sasas0a0s0111",    
    "creator": minu_avalik_võti,
    "merkle_root": "asasasas1w111",
    "count": number_of_transactions,
    "transactions": [{...}, ..., {....}]
   }

== Bloki Merkle juure (merkle root) arvutamine ==

Mõte selles, et seome kõik bloks olevad transaktsioonid nende hashide kaudu puukujuliselt üheks merkle hashiks ja ei oleks vaja hoida
iga transaktsiooni hashi eraldi. Seda peab tegema kindlas järjekorras,
et teised kontrollida saaks. Kõigepealt pead arvutama iga transaktsiooni hashi (selleks konverdi transaktsioon stringiks) ja siis hakka neid hashe hierarhiliselt
paariviisi kokku konkateneerima ja selliselt paariviisi kokku liidetud hashidest uusi hashe arvutama.

Vaata Merkle puu kohta
* [https://en.wikipedia.org/wiki/Merkle_tree wikipedia]
* [https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees bitcoini ametlik lühiinfo]
* [https://bitcoin.stackexchange.com/questions/10479/what-is-the-merkle-root näide bitcoini stackexchangest]

[https://bitcoin.stackexchange.com/questions/1110/how-do-i-implement-a-merkle-tree Siit] leitud seletus rehkendusele:

In each iteration, you concatenate two subsequent hashes of the previous level, and double-sha256 them. 
If there is an odd number of hashes, concatenate the last element with itself. 
This gives you a new list of hashes. Repeat, and stop when one hash remains. This is the merkle root.

Assume you have tx hashes Ha1,Ha2,Ha3,Ha4,Ha5,Ha6,Ha7

*  First iteration: Hb1=Hash(Ha1|Ha2), Hb2=Hash(Ha3|Ha4), Hb3=Hash(Ha5|Ha6), Hb4=Hash(Ha7|Ha7)
*  Second iteration: Hc1=Hash(Hb1|Hb2), Hc2=Hash(Hb3|Hb4)
*  Third iteration: Hd1=Hash(Hc1|Hc2) => Merkle root

NB! Bitcoinis on kombeks arvutada topelt-hashe a la hash(hash(data)) aga meil ei ole mingit põhjust seda teha. Soovitan kasutada lihtsalt ühekordset hashi.

== Bloki kaevandamine ==

Nüüd on sul vaja leida bloki oma hash, kusjuures sobivad ainult sellised hashid, kus on ees N nulli. Katseta, et mitu nulli peaks ees olema, et 
saaksid ühe sobiva hashi ca viie sekundi jooksul (päris bitcoinis on N-e niipalju, et keskmiselt tuleks üks blokk kümnes minutis kogu võrgu kohta).
See nullide nõue on kasutusel ainult selleks, et blokke tuleks harvemini, n.ö. pidur blokkide kiirele genereerimisele.

Selleks võta kogu oma bloki sisu a la 


   {
    "nr": bloki_number_ehk_eelmise_bloki_nr+1,
    "previous_hash": ahelas_eelmise_bloki_hash,
    "timestamp":  "2012-04-21T18:25:43-05:00",
    "nonce": "asasas11", 
    "hash": "000000sasas0a0s0111",    
    "creator": minu_avalik_võti,
    "merkle_root": "asasasas1w111",
    "count": number_of_transactions,
    "transactions": [{...}, ..., {....}]
   }

aga <b>ilma</b> "nonce" ja "hash" väljadeta ja muuda ta stringiks.

Nüüd tee läbi tsükkel:

* leia lühike random string "nonce" N ja pane see eelnevalt leitud blokistringi S lõppu juurde, saad stringi X.
* arvuta saadud stringi X hash. 
* kui saadud hash algab N nulliga, kõik ok ja lõpeta töö.
* vastasel korral mine tsükli esimesele reale tagasi.

Kui sobiv hash leitud, lisa blokile leitud sisuga "nonce" väli ja "hash" väli.

== Mitme paralleelbloki korral õige valimine ==

Sul on üldjuhul suur hulk blokke ahelas. Kui mõni uuematest blokkidest sama "nr" väljaga on topelt, on sul hargnev blokiahel. Siis vali:

* Kõige pikem ahel (kõige suurema numbriga blokk sobib)
* Sama pikkusega ahela puhul vali see, kus 
** harus on rohkem transaktsioone
** kui see ka sama, vali näiteks see, kus viimane timestamp uuem
** kui see ka sama, tee näiteks lihtsalt hashide stringivõrdlus ja vali stringijärjekorras väiksema hashiga blokk

== Loodud bloki automaatselt teistele edasisaatmine ==

Kui sul blokk valmis, siis saada ta lihtsalt teistele programmidele edasi. Nemad saadavad seda omakorda edasi ja loodetavasti jõuab see blokk varsti kõigi hetkel võrgus töötavate ja korraliku ühendusega programmideni.