Topic: Вероятностный подход к майнингу (Read 2316 times)

а недопонимаю я вот чего.
Формулировка немного не верна.

что блок раунд ищется до тех пор, пока одна из шар не будет удовлетворять некоторому условию, причем порядковый номер шары, которая окажется удачной, есть величина случайная.

Мне вот что неясно.
Но поскольку вся сеть одновременно считает один и тот же блок, то количество шар в блоке для всей сети должно обнуляться при нахождении нового блока одним из узлов.

Или я чего-то недопонимаю?

Спасибо за ссылку. График действительно тот самый, за исключением, что там он нормализованный, а у меня абсолютный.

К примеру, второй график: http://mining.bitcoin.cz/stats/graphs/

Каким образом сам пул определяет сложность? Или ты имеешь ввиду, что сложность в пуле = сложность * (твоя скорость) / (общая скорость пула) ? Понятно, что решить в пуле проще, но для всего пула действует ведь именно глобальная сложность. Или я не прав?


Я сразу написал, что не исключаю такой возможности, однако попросил дать ссылки, потому что я такого не нашел. Понятно, что я не первый до этого додумался. Однако, расчет функции распределения блоков по количеству шар, я не встречал. Если бы ты привел ссылки, откуда это тебе "уже давно известно", думаю многим было бы интересно. Может быть их даже можно было бы прилепить в FAQ. И даже несмотря на то, что это давно известно многие продолжают утверждать, что после длинного блока обязательно будет короткий, и наоборот. Отчасти поэтому я и создал тему.

Это всё уже давно известно и графики построены - баян 

Блок считается найденым, когда в составе его хеш-суммы появляется определенное количество нулей. Чем больше сложность (difficulty), тем больше нулей необходимо.

Например:

Block 139485
Short link: http://blockexplorer.com/b/139485

    * Hash: 00000000000004ff5e57df000b1df517221d08c9d4b5da03de743f4834de2ad5
    * Previous block: 00000000000001d01acd8f6d28e0bf46236a000d3bdcf0f0996d9613ce4e1f4e
    * Time?: 2011-08-03 19:34:27
    * Difficulty: 1 888 786.705353 ("Bits": 1a08e1e5)
...

Пулы дают облегченную задачу для майнеров, и насколько она легче чем настоящая сложность - определяет сам пул.

А так все верно - орел может упасть в любой момент, независимо от того сколько решек было до этого.

Хочу поделиться некоторыми своими математическими размышлениями. Если где-то подобное уже есть, прошу дать ссылку на оригинал. В основном, этот материал будет интересен пул-хоперам, однако, всем остальным, возможно, тоже будет любопытно взглянуть.

Про биткоин я узнал совсем недавно и ради любопытства решил немного помайнить. В процессе майнинга на пулах мне стало интересно, как распределены блоки по количеству шар. Готового ответа на этот вопрос я не нашел, поэтому пришлось думать самому. Итак, на сколько я понял, блок ищется до тех пор пока найденная шара не будет самой короткой. Здесь я могу ошибаться, потому что, как уже было сказано, я новичок, но суть не в этом. А суть в том, что блок ищется до тех пор, пока одна из шар не будет удовлетворять некоторому условию, причем порядковый номер шары, которая окажется удачной, есть величина случайная. Распределение этой случайной величины мы и будем искать. Очевидно, что данная величина является дискретной (кол-во шар дискретно). Сама найденная шара является «испытанием» в терминах теории вероятностей. «Испытание» может быть успешным (шара удовлетворяет некоторому условию) и неуспешным (шара не удовлетворяет условию). Тогда, поиск блока является последовательностью «испытаний» (шар) до первого успешного «испытания» (шары). Из теории вероятностей известно, что такая случайная величина описывается геометрическим распределением. Однако, т.к. дискретность величины очень малая (шаг дискретизации ~10^-6), то можно заменить наше дискретное геометрическое распределение его непрерывным аналогом – экспоненциальным распределением.

Функция экспоненциального распределения из теории вероятностей , где lambda – параметр распределения. Прежде, чем мы определим этот параметр, давайте вспомним физический смысл функции распределения. Значение функции распределении в точке х равно вероятности события Х, такого, что Х≤x. Относительно нашего случая, функция распределения в точке х равна вероятности того, что количество шар в блоке будет меньше или равно х.

Проще говоря, мы можем узнать вероятность того, что размер блока не превысит заданного количества шар!

Осталось только определить параметр lambda. Известно, что первый момент экспоненциального распределения, он же – математическое ожидание, он же – среднее арифметическое, равен 1/lambda. Или lambda=1/E, где Е – среднее арифметическое. Таким образом для того, чтобы построить  функцию распределения нам нужно знать только среднее арифметическое количество шар в блоке. Т.е. собираем статистику по блокам на каком-нибудь пуле и считаем среднее. Для проверки моей теории, я также построил график распределения непосредственно по эмпирическим данным – количество блоков, в которых количество шар < 40000, делим на общее количество блоков; количество блоков с шарами < 80000 делим на общее количество блоков и т.д. В результате получились два графика теоретический (точнее полуэмпирический) - основанный на среднем арифметическом (синяя линия), и эмпирический - построенный по точкам (желтая линия).

Для Deepbit:


Как видно из графиков, наша теория хорошо согласуется с эмпирическими данными.
Для Triplemining график похуже, т.к. блоков там насчитано мало:


Еще я подумал, что среднее количество шар в блоке – это по определению есть сложность. (поправьте, если я не прав) Т.е. lambda=1/d, d – текущая сложность биткойна.
Таким образом для функции распределения нам вообще не нужно никаких данных, кроме текущей сложности! Добавим еще один график (красный) для полностью теоретической функции распределения (основанной только на сложности). Как вы знаете, недавно произошло повышение сложности, поэтому просто для сравнения я добавил график новой сложности (зеленый).

Deepbit:


Triplemining:


ВНИМАНИЕ! Эмпирические данные были получены для предыдущей сложности (1 690 895) и к новой сложности не имеют никакого отношения. Теоретический график (зеленый) для новой сложности (1 888 786) добавлен просто для сравнения, однако, вы можете его использовать в своих расчетах

Для тех, у кого еще остались вопросы, как можно использовать эти графики - поясню. По оси Х отложено количество шар, по оси Y – вероятность того, что шар в блоке будет МЕНЬШЕ этого количества (не обязательно равно, а именно меньше). Например, (для предыдущей сложности) вероятность того, что количество шар в очередном блоке будет меньше 1 200 000 составляет ~50,8%; вероятность того, что количество шар уложится в 6 000 000 составляет 97,1% и т.д.

Если будет время, может быть доведу до ума экселевский файл со всеми расчетами и выложу его здесь.

Важные следствия:

1) вероятность того, что количество шар в блоке окажется 100500 миллионов ВСЕГДА отлична от нуля для ЛЮБОЙ сложности. Естественно, при увеличении сложности эта вероятность увеличивается, при уменьшении – уменьшается, но никогда не становится равной нулю. Короче, всегда, при любой сложности, если сильно НЕ повезет, можно встретить очень-очень-очень-очень длинный блок на стопицот миллионов шар.

2) На форумах часто встречается такой тезис, что если на пуле был длинный блок, то после обязательно должен быть короткий, и наоборот – были короткие, поэтому обязательно будет длинный. Это не так! Т.к. мы убедились, что распределение у нас экспоненциальное, то у него есть важное свойство – «отсутствие памяти». Это означает, что вероятность блока определенной длины всегда постоянна и не зависит от того, какой блок был до этого - короткий или длинный. Т.е. если на пуле подряд было 5 коротких блоков, то вероятность длинного блока в таком случае в точности равна вероятности длинного блока после 5 других длинных. Например, вероятность, что блок будет короче 2 000 000 шар ВСЕГДА равна 69,4%, не зависимо от того, какие блоки были до этого. Вероятность зависит только от текущей сложности.

Это все. На замечания и вопросы буду отвечать по мере возможности.
Если данный материал оказался вам полезен, вы можете отправить благодарность сюда - 13fu8qhyLSD4HmhDaJDFY6wvpajrDKbmP7

Спасибо.