Bitcoin - митове и легенди (част 1)

blog

Забележка:
Математическите формули в този текст са изписани на LaTeX, за визуализация на който се използва MathJax. Ако вместо формули виждате нещо като \(\Var[nonce] = \frac{1}{p^2}\), то MathJax не функционира по някаква причина, най-вероятно блокиран от NoScript.

С нарастващата популярност на Bitcoin – базираната на случайни събития криптовалута, съвсем естествено, започва зараждането на мистицизма по отношение на функционирането на случайния елемент в нея, аналогично на тотото. Което за пореден път доказва факта, че човешкото мислене просто отказва да функционира в термините на случайни събития и е по-склонно да се впусне в дебрите на мистицизма, отколкото да приеме случващите се събития за случайни.

Ще се опитам да анализирам някои от най-разпространените заблуди в общността на копачите на битмонети. Тъй като не разбирам от финанси, ще се концентрирам само върху техническите митове и легенди.

Малко предварителна информация

Блоковете в Bitcoin се “изкопават” в резултат на криптографски процес, свеждащ се до изчисляване на двоен SHA256 хеш на съдържанието на част от блока, докато стойността на хеша стане по-малка от т.нар. цел. Хеширането се прилага върху заглавната част на блока, включваща следните полета:

  • номер на версията – за момента фиксирана на 0x00000001;
  • хеш на предишния блок – двоен SHA256 хеш на заглавната част на последно открития блок;
  • корен на дървото на Merkle за транзакциите, съдържащи се в блока;
  • времеви маркер на блока – стандартен Unix времеви маркер в брой секунди от епохата (00:00:00 UTC на 01.01.1970 г.);
  • компактен вид на целта – указва трудността, при която е бил генериран блока;
  • т.нар. “nonce” – променлива част от заглавието на блока, която започва от 0x00000000 и се увеличава с единица докато стойността на хеша стане по-малка от целта; преносът при препълване се записва в специалната първа транзакция, което променя стойността на корена на дървото на Merkle.

Основна заблуда: блоковете имат предварително определен размер; има големи и малки блокове

Генерирането на блок в Bitcoin е като игра на рулетка. На всяка стъпка от операцията се генерира 256-битов хеш, който се сравнява с целта. Хеширащата операция е детерминистична, но хаотична – при един и същи вход винаги се получава един и същи резултатен хеш, но промяна дори на един бит от входа води до получаване на напълно различен резултатен хеш – полезни и всъщност силно желани свойства на хеш функцията. Ако всички полета в заглавната част на блока са фиксирани, то хеш със стойност по-малка от целта ще се постигне при точно определена най-малка стойност на nonce. Единственото наистина фиксирано поле е това на версията, а всички останали се променят при едни или други условия:

  • хеш на предишния блок – променя се тогава, когато някой друг открие нов блок; нямаме контрол върху този процес, тъй като не контролираме изчислителните ресурси на останалите участници в мрежата (случаен процес);
  • корен на дървото на Merkle – променя се, когато има нова Bitcoin транзакция, която желаем да обработим и включим в съдържанието на блока или всеки път когато полето nonce прехвърли \(2^{32}-1\); бихме могли да ограничим случайната промяна на полето, ако не приемаме нови транзакции (случаен процес);
  • времеви маркер на блока – променя се на добре известни периоди от време, като Bitcoin допуска до 2 часа отклонение от средното време на мрежата, така че стойността може да се държи фиксирана в известен период от време;
  • компактен вид на целта – променя се относително рядко – вендъж на всеки 2016 блока, като точният момент зависи от това кога ще бъде открит 2016-тия блок (случен процес).

Дори и при дадени начални стойности на променящите се полета стойността на печелившия nonce да е фиксирана, случайният характер на промяната на указаните по-горе полета води до това, че текущата печеливша стойност се изменя непрекъснато и по почти случаен начин. Почти случаен е поради свойството на хеш функцията много силно да изменя стойността си при каква да е промяна на входните данни. Това прави много трудно, на практика невъзможно, евристичното познаване на търсената стойност на nonce и единственият практически приложим метод е този на изчерпващото търсене. Промяната на някое от полетата в заглавната част рестартира търсенето обратно от 0.

Изводът до момента е: блоковете биха имали фиксирана отнапред големина, измерена като брой хеширания до откриване на печелившата стойност на nonce, но само ако в мрежата има един единствен участник, което очевидно не е така.

Втора основна заблуда: късметлии и каръци

Ще започна с малко елементарна теория на вероятностите.

На всяка стойност на \(nonce\) съответства хеш в интервала \(0 \ldots 2^{256}–1\), като вероятността той да е по-малък от търсената цел \(target\) е:

$$ p(hash < target) = \frac{target}{2^{256}}\,. $$

Целта \(target\) е функция на трудността \(D\):

$$ target = \frac{\mathrm{0xffff} \cdot 2^{208}}{D} $$

или

$$ p(hash < target) = \frac{\mathrm{0xffff}}{D \cdot 2^{48}} = \frac{2.328271 \times 10^{–10}}{D} $$

(за простота нататък ще пиша само \(p\))

Тъй като стойностите на хеша за съседни стойности на \(nonce\) се отличават силно, то отделните събития “хешът с дадена стойност на \(nonce\) е по-малък от \(target\)” са на практика независими. Тогава вероятността да бъде открита печелившата стойност на \(nonce\) след \(k\) на брой хеширания (т.е. \(nonce\) да бъде равен на \(k-1\)) е:

$$ p(nonce = k-1) = (1 - p)^{k-1} p\,. $$

За случайните величини с подобно поведение казваме, че следват геометрично разпределение с параметър \(p\). За това рапределение е известно, че математическото очакване, т.е. средната стойност от безброй много опити, е:

$$ \newcommand{\E}{\mathrm{E}} \E[nonce] = \frac{1}{p} - 1 = D \cdot 4295032833 - 1 \approx D \cdot 4295032833\,. $$

На практика обаче не можем да осредним безкраен брой опити, тъй като сме ограничени от крайното време, с което разполагаме, или в рамките на което правим наблюденията. Степента на отклонение на отделните измервания от средната стойност се нарича вариация на разпределението и за геометричното разпределение тя е:

$$ \newcommand{\Var}{\mathrm{Var}} \Var[nonce] = \frac{1 - p}{p^2} \approx \frac{1}{p^2} = D^2 \cdot 1.844731 \times 10^{19}\,. $$

Вариацията на геометричното разпределение е обратнопропорционална на вероятността за успех и в конкретния случай нараства с квадрата на трудността. Осредняването върху броя хеширания за откриване на \(N\) (краен брой) блока дава средна стойност, която принципно се отличава от теоретичната, като нейната вариация е:

$$ \Var[mean] = \frac{1}{N} \Var[nonce] = \frac{D^2}{N} \cdot 1.844731 \times 10^{19}\,. $$

Средноквадратичното (стандартно) отклонение е квадратен корен от вариацията и тогава относителното средноквадратично отклонение на средната стойност на големините на \(N\) блока при трудност \(D\) е:

$$ \sigma(N) = \frac{\sqrt{\Var[mean]}}{\E[nonce]} = \frac{N^{-1/2}\frac{1}{p}}{\frac{1}{p}-1} \approx \frac{1}{\sqrt{N}}\,. $$

Важният извод от това е, че при един и същ брой блокове \(N\), върху които осредняваме, отклонението от средната стойност е толкова по-голямо, колкото по-голяма е стойността на трудността \(D\), но относителното отклонение зависи единствено от броя на блоковете, върху които се извършва осредняването. По централната гранична теорема самата средна стойност има разпределение, клонящо към нормално, центрирано в математическото очакване \(\E[nonce]\), т.е. в дългосрочен план всички късметлийски периоди, в които средният брой хеширания е по-малък от математическото очакване, точно се компенсират от каръшки периоди, в които средният брой хеширания е по-голям от математическото очакване.

Голяма част от копачите групират усилията си в басейни (mining pools). Басейните работят като раздават дялове – блокове с най-ниската възможна трудност \(D^1 = 1\). Когато клиентът реши и върне на басейна такъв блок (дял), вероятността той да удовлетворява по-строгия критерий на текущата трудност е:

$$ p(\text{share wins}) = \frac{D^1}{D} = \frac{1}{D} $$

Т.е. броят на върнатите дялове до решаване на блока е също геометрично разпределена велична с параметър \(p = \frac{1}{D}\), като всичко написано за броя хеширания по-горе се пренася директно върху броя на дяловете за блок. Теоретичната средна стойност и вариацията на броя дялове до решаване на блок е равна на текущата трудност:

$$ \E[shares] = \frac{1}{p(\text{share wins})} = D $$ $$ \Var(shares) = D^2 - D \approx D^2\,(\text{за големи } D)\,. $$

Средната стойност е функция само на текущата трудност \(D\) и не зависи от броя на участниците в басейна – големите басейни имат същото разпределение и вариация на броя дялове до решаване на блок, каквото имат и малките басейни. Този факт следва да се помни, тъй като ще потрябва в разсъжденията по-нататък.

Традиционно в копаческите Bitcoin общности се обръща специално внимание на броя дялове до решаване на блок (всичко по-надолу дословно важи и за \(nonce\)) в следните времеви интервали:

  • интервал на една и съща трудност – \(N = 2016\) и относителното стандартно отклонение на средната стойност от теоретичното средно е ±2.2%;
  • интервал на една и съща трудност в рамките на един голям басейн (1/3 от общата изчислителна мощност) – \(N \approx 672\) и относителното стандартно отклонение на средната стойност от теоретичното средно е ±3.9%;
  • един ден – \(N \approx 144\) (средно по 2 седмици за 2016 блока) и относителното стандартно отклонение на средната стойност от теоретичното средно е ±8.3%;
  • един ден в рамките на голям миньорски басейн – \(N \approx 48\) (1/3 от общата изчислителна мощност на мрежата) и относителното стандартно отклонение на средната стойност от теоретичното средно е ±14.4%;
  • няколко поредни блока – \(N < 4\) и относителното стандартно отклонение на средната стойност от теоретичното средно надвишава ±50%.

Много важна особеност на геометричното разпределение е неговата силна асиметрия спрямо средната стойност. Стойностите на броя дялове и на \(nonce\) са ограничени отдолу (1 за дяловете и 0 за \(nonce\)), но не са ограничени отгоре, т.е. съществува, макар и клоняща към нула, вероятност печеливш хеш да не бъде открит дори след многократно надвишаващи средния брой хеширания. От друга страна, вероятността намалява монотонно с увеличаване на \(nonce\) и (парадоксално) е най-голяма при \(nonce\) = 0, т.е. по-вероятно е да се открие печеливш хеш още от първия опит, отколкото след точно хиляда поредни опита! Ако се постави условието обаче печеливш хеш да бъде намерен за не повече от \(N\) опита, то тогава говорим за монотонно растящата кумулативната функция на разпределение (CDF). 63% от блоковете се откриват след по-малко от теоретичния среден брой дялове, а останалите 37% след повече от теоретичния среден брой. И тук именно се корени генезисът на мита за късметлиите и каръците: 2/3 от блоковете се откриват след по-малко от средния брой хеширания, но тези над средното, макар и по-рядко срещани, се откриват след (често) на порядъци по-голям брой хеширания поради силната асиметрия на разпределението. Клопката, в която мнозина попадат, е че след като текущото търсене надвиши определен брой хеширания, блокът се обявява за много “голям” и се търси нов копачески пул, в който блоковете са “малки”. Къде е основата на заблудата?

След “голям” блок се чакат “малки” блокове

Вероятността блок да бъде решен след пресмятане на по-малко от средния брой дялове (или хеширания) е \(p(Luck) = 63.2\%\). Вероятността да бъдат необходими повече от средния брой дялове е \(p(Unluck) = 1 - p(Luck) = 36.8\%\) (разпределението на късметлийските и каръшки блокове следва отрицателното биномно разпределение, бидейки сума от множество геометрични разпределения). Вероятността да бъде наблюдаван каръшки блок (U), следван от два късметлийски (L), при това точно в този ред, е:

$$ p(ULL) = p(U) \cdot p(L) \cdot p(L) = 14.7\%\,. $$

Вероятността трите блока да бъдат наблюдавани в произволен ред е:

$$ p(1U + 2L) = p(ULL) + p(LUL) + p(LLU) = 44.1\%\,. $$

Независимо от реда на случване, общото време за откриване на трите блока е едно и също. Затова е изключително неправилно ограничаването на наблюденията само върху тези случаи, при които е фиксирана наредбата на блоковете. Вероятността да се случи един каръшки и три късметлийски блока е:

  • в точно тази наредба – \(p(ULLL) = 9.3\%\);
  • в произволен ред – \(p(1U + 3L) = 37.2\%\).

Ако се ограничим само в наблюденията на случващото се след появата на каръшкия блок, то не бихме забелязали 1/3 от случаите на късмет.

Вероятността намалява силно, ако се засилят дефинициите на късметлийски и каръшки блокове. Нека например за късметлийски да приемем блок, който се решава след по-малко от 1/3 от средния брой дялове (или хеширания). Вероятността за такъв късметлийски блок е \(p(L) = 28.3\%\). Вероятността да бъдат необходими 3 пъти повече от средния брой дялове за решаване на каръшки блок е \(p(U) = 5.0\%\). Вероятността да бъде наблюдавана комбинацията от един каръшки и два късметлийски блока, при това точно в този ред, е:

$$ p(ULL) = p(U) \cdot p(L) \cdot p(L) = 0.4\%\,. $$

Вероятността трите блока да бъдат наблюдавани в какъвто и да било ред на случване е 1.2%. Изискването да се наблюдава още един късметлийски блок понижава вероятността до \(p(ULLL) = 0.11\%\) и \(p(1U + 3L) = 0.45\%\).

Вероятността след каръшки блок да се наблюдава късметлийски по формулата за условната вероятност е:

$$ p(L|U) = \frac{p(LU)}{p(U)} = \frac{p(L) \cdot p(U)}{p(U)} = p(L)\,. $$

Резултатът е напълно очакван предвид статистическата независимост на случването на късметлийски и каръшки блокове. Късметлийските блокове се случват с една и съща вероятност независимо от типа на предхождащия блок. Същото важи и за каръшките блокове.

Смяна на басейна за избягване от “лош късмет”

Важно е да се разбере следният изключително важен факт: случването на блок с определен брой дялове по никакъв начин не влияе на разпределението на късмета в следващите блокове. Също така, откриването на блокове в различните басейни е напълно независимо, поради което можем да приложим разсъжденията от предишната точка директно върху случая на прескачане от басейн на басейн в търсене на късмета, който да компенсира вече случил се каръшки блок.

Копаенето в един басейн е също толкова резултатно, колкото и местенето в нов басейн след всеки новооткрит блок. Разликата между различните басейни е само във вариацията:

  • големите басейни откриват повече блокове за даден период и следователно, осредявайки върху повече блокове, имат по-малка вариация на средното за периода, т.е. гарантират един стабилен като осцилация на количество доход в биткойни, ако индивидуалната и сумарната скорости на хеширане остават постоянни в рамките на периода;
  • малките басейни откриват малък брой блокове за даден период от време и следователно имат много по-голяма вариация на средното.

Голямата вариация в малките басейни може да изкуши някой да избяга от басейна след случване на няколко поредни късметлийски блока в голям басейн с малка вариация в очакване на нова късметлийска серия. От всичко написано по-горе вече би трябвало да е ясно, че наблюдаването на няколко поредни късметлийски блока изобщо не променя разпределението на следващите блокове и съответно няма гаранция, че следващият блок няма да се окаже силно каръшки. Възможна е печалба от случайни силно късметлисйки серии, но тяхното предсказване е практически невъзможно и всякакви опити са всъщност чист хазарт.

В част 2 ще покажа с числени експерименти съвпадението на теорията със случващото се в Bitcoin системата.