Bitcoin dokaz dela - verjetnost

O matematiki, številih, množicah in računih...
Odgovori
jaka3d
Prispevkov: 1
Pridružen: 19.6.2018 10:40

Bitcoin dokaz dela - verjetnost

Odgovor Napisal/-a jaka3d » 19.6.2018 11:30

Pozdravljeni,
moje znanje o verjetnosti je bolj pomankljivo zato imam nekaj vprašanj o le-te pri dokazu dela protokola/kriptovalute Bitcoin.

Kratek povzetek:
Bitcoin/bitcoin uporablja za vzpostavitev konsenza med deležniki ti. proof-of-work algoritem. Da lahko deležnik ustvari blok mora ustvariti dokaz o opravljanem delu. To naredi z (dvojno) uporabo SHA256 hash funkcije. Če je vrednost \(256\) bitnega binarnega niza - binarne številke - manjša od neke predpisane in spreminjajoče se vrednosti je to dokaz. Algoritem je asimetričen; za iskanje porabimo veliko časa, za preverjanje pa samo eno enoto časa. SHA256 ima lastnost naključnosti - \(1\) bit spremembe pri vhondem binarnem nizu ustvari popolnoma drugačen, naključen rezultat.

Od tu naprej se začenjajo vprašanja.
* Če vzamemo vse možne vhode v funkcijo SHA256 (od dolžine \(1\) do \(\infty\)).. verjetnost, da pade katerakoli binarna številka med \(0\) in \(2^ {256-1}\) je enaka \(\frac{1}{2^{256}}\)

Prva točka verjetno ni pravo vprašanje ampak izhaja iz defincije. Če je funkcija res naključna potem je ta lastnost ekvivalentna. Je trditev pravilna?

Tukaj se pojavi dvom. Problem izgleda podobno kot problem \(n\) košov, \(n\) žogic.

Če imamo \(n\) žogic, \(n\) košev in je verjetnost, da zadanemo koš med vsemi koši enaka (\(\frac{1}{n}\)), potem ostane \(\frac{n}{e}\) košov praznih.
Torej če imamo \(2^{256}\) košev in naredimo \(2^{256}\) hash operacij, potem ostane \(\frac{2}{2^{256}}\) košov/binarnih številk "praznih".

Tukaj se zdaj pojavi vprašanje definicije naključnosti SHA256. Ali naključnost pomeni to, da je verjetenost, da bo vsaka vrednost "zadeta" enaka, ali pomeni naključnost to, da je po koncu sekvence hash operacij vsaka zadeta enkrat. Ali pa tretja možnost, da sem zašel in je ta "naravna" razporeditev samo posledica predpostavk in če izvedemo neskončno operacij, je verjetnost, da pade katerakoli vrednost enaka, pri \(m \neq \infty\) metih se pa "polnost" košov ter število praznih lahko razlikuje.

Hvala za Vaš čas in odgovore :D

Uporabniški avatar
shrink
Prispevkov: 14372
Pridružen: 4.9.2004 18:45

Re: Bitcoin dokaz dela - verjetnost

Odgovor Napisal/-a shrink » 24.7.2018 21:05

jaka3d napisal/-a:
19.6.2018 11:30
Pozdravljeni,
moje znanje o verjetnosti je bolj pomankljivo zato imam nekaj vprašanj o le-te pri dokazu dela protokola/kriptovalute Bitcoin.

Kratek povzetek:
Bitcoin/bitcoin uporablja za vzpostavitev konsenza med deležniki ti. proof-of-work algoritem. Da lahko deležnik ustvari blok mora ustvariti dokaz o opravljanem delu. To naredi z (dvojno) uporabo SHA256 hash funkcije. Če je vrednost \(256\) bitnega binarnega niza - binarne številke - manjša od neke predpisane in spreminjajoče se vrednosti je to dokaz. Algoritem je asimetričen; za iskanje porabimo veliko časa, za preverjanje pa samo eno enoto časa. SHA256 ima lastnost naključnosti - \(1\) bit spremembe pri vhondem binarnem nizu ustvari popolnoma drugačen, naključen rezultat.

Od tu naprej se začenjajo vprašanja.
* Če vzamemo vse možne vhode v funkcijo SHA256 (od dolžine \(1\) do \(\infty\)).. verjetnost, da pade katerakoli binarna številka med \(0\) in \(2^ {256-1}\) je enaka \(\frac{1}{2^{256}}\)

Prva točka verjetno ni pravo vprašanje ampak izhaja iz defincije. Če je funkcija res naključna potem je ta lastnost ekvivalentna. Je trditev pravilna?
Ja, če funkcija lahko naključno generira eno od \(2^{256}\) vrednosti, potem je verjetnost \(\frac{1}{2^{256}}\). V realnosti pa gre za psevdogeneratorje, tako da takšni algoritmi generirajo psevdonaključne vrednosti, kar pa je dovolj dobra aproksimacija naključnih vrednosti.
Tukaj se pojavi dvom. Problem izgleda podobno kot problem \(n\) košov, \(n\) žogic.

Če imamo \(n\) žogic, \(n\) košev in je verjetnost, da zadanemo koš med vsemi koši enaka (\(\frac{1}{n}\)), potem ostane \(\frac{n}{e}\) košov praznih.
Torej če imamo \(2^{256}\) košev in naredimo \(2^{256}\) hash operacij, potem ostane \(\frac{2}{2^{256}}\) košov/binarnih številk "praznih".
Ne, problem je identičen metanju 1 žoge na \(2^{256}\) košev: verjetnost, da zadeneš določen koš, je \(\frac{1}{2^{256}}\).
Tukaj se zdaj pojavi vprašanje definicije naključnosti SHA256. Ali naključnost pomeni to, da je verjetenost, da bo vsaka vrednost "zadeta" enaka, ali pomeni naključnost to, da je po koncu sekvence hash operacij vsaka zadeta enkrat. Ali pa tretja možnost, da sem zašel in je ta "naravna" razporeditev samo posledica predpostavk in če izvedemo neskončno operacij, je verjetnost, da pade katerakoli vrednost enaka, pri \(m \neq \infty\) metih se pa "polnost" košov ter število praznih lahko razlikuje.

Hvala za Vaš čas in odgovore :D
Naključnost v osnovi pomeni, da ne vemo, katero vrednost bo generiral algoritem. Enaka verjetnost generiranja posamezne vrednosti pa je lastnost enakomernih diskretnih verjetnostnih porazdelitev.

Če porazdelitev ni enakomerna in se torej določene vrednosti pojavljajo z večjo verjetnostjo, to ne nujno pomeni, da pojav ni naključen (npr. Poissonova porazdelitev).

Odgovori