Лекция на OpenFest 2011

След минутката телевизионна слава в предаването на БНТ “Красива наука”, вече практически нищо не ме спира да говоря пред публика от непознати хора. Затова и най-после се преборих с предразсъдъците си и реших да се включа с лекция в тазгодишното издание на OpenFest. Под заглавието “Направи си сам суперкомпютър” се крие доста амбициозна цел, но времето от 45 минути едва ли ще позволи да я реализирам изцяло. Все пак, ако проявявате някакъв интерес към мащабната изчислителна техника, то заповядайте идната неделя от 17:15 в зала “София” на Интерпред.

Лекцията преди моята, тази на Пейо Попов за електронните пари, и Bitcoin в частност, също ще си струва да присъствате. Залата е същата, а началото е час по-рано — в 16:15.

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

Note

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

В част 1 дадох математическата обосновка на несъстоятелността на редица митове и легенди в света на Bitcoin, породени от субективната невъзможност за правилно възприемане на случайните събития като такива. Сега ще покажа, че процесите всъщност се описват с достатъчно добра точност от теорията и че последната не е само математическо бръщолевене.

Сравнение с експерименталните наблюдения

Разглеждаме следната извадка от публичната статистика на басейна deepbit.net, обхващаща няколко дена на постоянна трудност \(D = 1379192\):

Период Блокове Дялове Средно Късмет
29.06 57 80389531 1410343 +2.3%
30.06 64 79751252 1246113 –9.6%
01.07 62 83054752 1339593 –2.9%
02.07 57 85609229 1501916 +8.9%
03.07 55 86255018 1568273 +13.7%
04.07 65 89260819 1373243 –0.4%
05.07 51 98434841 1930095 +39.9%
29.06—06.07 411 602755442 1466558 +6.3%

Късметът е дефиниран като относителното отклонение на средното за деня от математическото очакване. Отрицателните стойности означават късмет, а положителните — каръщина. Върху тези данни може да се приложи т.нар. Z-тест:

\begin{equation*} Z = \frac{mean - \mathrm{E}[shares]}{\sigma / \sqrt{N}}\,\,, \end{equation*}

където \(mean\) е средното за деня на броя дялове \(N\), а \(\sigma\) е теоретичното стандартно отклонение на геометричното разпределение. 95% от всички случаи на отклонение от математическото очакване следва да попадат в рамките на \(|Z| \leq 1.96\).

Период Блокове СОСС [1] Късмет Z-мярка
29.06 57 13.2% +2.3% 0.171
30.06 64 12.5% –9.6% –0.772
01.07 62 12.7% –2.9% –0.226
02.07 57 13.2% +8.9% 0.672
03.07 55 13.5% +13.7% 1.017 (!)
04.07 65 12.4% –0.4% –0.035
05.07 51 14.0% +39.9% 2.853 (!!)
29.06—06.07 411 4.9% +6.3% 1.284 (!)

С (!) е маркирано попадение в горната част на 95% доверителен интервал (\(1 < |Z| \leq 1.96\)). Средната стойност за 05.07 лежи извън рамките на две стандартни отклонения, но попада в рамките на три стандартни отклонения (\(|Z| \leq 3\)), което вече покрива 99.74% от възможните случаи.

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

Съвпадението между теоретичното геометрично разпределение и експерименталното такова е видимо и на следната графика:

../images/139.png

С черно е показана хистограмата на броя блокове като функция на броя дялове за откриването им, а със сините импулси — хистограма на геометричното разпределение. Съвпадението е повече от добро. Вертикалната пунктирана червена линия показва математическото очакване.

В предишната част беше показано, че верояността за срещане на каръшки блок (с повече от средното дялове), последван от два късметлийски блока (с по-малко от средното дялове) е 14.7%, а вероятността за срещане на трите блока в произволен ред е 44.1%. Изброяването на срещането на такъв тип блокове в информацията от deepbit показва, че от общо 409 тройки 58 удовлетворяват шаблона ULL, а 172 тройки удовлетворяват шаблона 1U + 2L, което дава експериментални вероятности:

  • \(p_\textrm{exp}(ULL) = \frac{58}{409} = 14.2\%\) при теоретична стойност 14.7%;
  • \(p_\textrm{exp}(1U + 2L) = \frac{172}{409} = 42.1\%\) при теоретична стойност 44.1%.

Аналогично шаблонът ULLL се среща 39 пъти от общо 408 четворки блокове, а шаблонът 1U + 3L — 147 пъти, което дава експериментални вероятности:

  • \(p_\textrm{exp}(ULLL) = \frac{39}{408} = 9.6\%\) при теоретична стойност 9.3%;
  • \(p_\textrm{exp}(1U + 3L) = \frac{147}{408} = 36.0\%\) при теоретична стойност 37.2%.

Вижда се, че експерименталните стойности са доста близки до теоретичните.

По-строгата дефиниция на късметлийски (по-малко от 1/3 от математичното очакване брой дялове) и каръшки (повече от 3 пъти математичното очакване брой дялове) блокове понижава теоретичните вероятности до \(p(ULL) = 0.4\%\), \(p(1U + 2L) = 1.2\%\), \(p(ULLL) = 0.11\%\) и \(p(1U + 3L) = 0.45\%\). Броят на извадките е твърде малък за надежно наблюдаване на толкова редки събития, което се потвърждава от факта, че комбинацията ULL не се среща нито веднъж, докато комбинацията 1U + 2L се среща само един път. Последното показва колко неправилно е разглеждането на поредицата от блокове само и единствено след срещането на особено каръшки блок.

[1] СОСС — стандартно отклонение на средната стойност

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

Note

Математическите формули в този текст са изписани на 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\) е:

\begin{equation*} p(hash < target) = \frac{target}{2^{256}}\,\,. \end{equation*}

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

\begin{equation*} target = \frac{0xffff \cdot 2^{208}}{D} \end{equation*}

или

\begin{equation*} p(hash < target) = \frac{0xffff}{D \cdot 2^{48}} = \frac{2.328271 \times 10^{–10}}{D} \end{equation*}

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

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

\begin{equation*} p(nonce = k-1) = (1 - p)^{k-1} p\,\,. \end{equation*}

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

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

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

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

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

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

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

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

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

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

\begin{equation*} p(\text{share wins}) = \frac{D^1}{D} = \frac{1}{D} \end{equation*}

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

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

Средната стойност е функция само на текущата трудност \(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), при това точно в този ред, е:

\begin{equation*} p(ULL) = p(unluck) \cdot p(luck) \cdot p(luck) = 14.7\%\,\,. \end{equation*}

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

\begin{equation*} p(1U + 2L) = p(ULL) + p(LUL) + p(LLU) = 44.1\%\,\,. \end{equation*}

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

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

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

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

\begin{equation*} p(ULL) = p(unluck) \cdot p(luck) \cdot p(luck) = 0.4\%\,\,. \end{equation*}

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

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

\begin{equation*} p(L|U) = \frac{p(LU)}{p(U)} = \frac{p(L) \cdot p(U)}{p(U)} = p(L)\,\,. \end{equation*}

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

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

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

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

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

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

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

Наука с Physon (2011)

Днес беше второто официално представяне на клъстера ни като част от Деня на отворените врати на Физически факултет на СУ. Решихме да се изхитрим и да минем мързеливо като само обновим числата по слайдовете от предишното. Кой да се сети, че дните на отворените врати традиционно се посещават и от ученици…

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

Следва статичната версия на представянето, за който проявява интерес:

Наука с Physon (Ден на отворените врати 2011)

Отново с благодарности към финансиращите организации НФНИ и ЕК.

Обратно на линия

Той изсъхна след наводнението и отново е на линия. Той е по-шумен отвсякога сега, когато се наложи да премахнем издулия се и изгнил паркет и балатума и да го оставим върху мозайката. Той ще бучи на живо в събота, 16 април 2011 г., когато в Деня на отворените врати на ФзФ ще бъде представен (за пореден път) от 13:00 в семинар В44.

Ако си падате по бучащи компютри, пращящи лазери и плазми, цвърчаща електроника или се чудите как трошат парите на данъкоплатците ония във ФзФ на СУ, то заповядайте в събота и бъдете просветени (или възмутени) :)