c-darwin Feb 5 2015 at 13:09

Алгоритм формирования блокчейна

3 min

17K

Dсoin corporate blogOpen source*Open data*

Comments 15

vibornoff Feb 5 2015 at 13:51

Что насчет «Sybil Attack»?

vibornoff Feb 5 2015 at 14:03

Ах, да, посмотрел ru.dcoinwiki.com/%D0%9C%D0%B0%D0%B9%D0%BD%D0%B5%D1%80
Вердикт: нет, не взлетит.

vibornoff Feb 5 2015 at 14:21

Еще замечания:

$hi = $ctx / 127773;
$lo = $ctx % 127773;
$x = 16807 * $lo — 2836 * $hi;
if ($x <= 0)
$x += 0x7fffffff;

127773, 16807, 2836 — откуда взяты эти числа и почему они именно такие?

$ctx — 24-битное число, что явно маловато для обеспечения криптографической стойкости.

$hi — никогда не может быть больше 131.3, так что вычитать 2836 * $hi бессмысленно на фоне области допустимых значений для 16807 * $lo

не показано, что $x % ($max_miner_id + 1) — равномерно распределено в области возможных $miner_id (я бы даже сказал что это очевидно не так), а это значит что некоторые майнеры будут чаще попадать на 0-й уровень, чем другие.

c-darwin Feb 5 2015 at 14:38

Честно говоря, почему именно 127773, 16807, 2836 я детально не разбирался, просто сделал тесты на разных хэшах и $max_miner_id, увидел, что распределение идет равномерно и решил оставить как есть.
Вот тут есть некоторые ответы — www.christianpinder.com/articles/pseudo-random-number-generation/
Результаты тестов сейчас найду и выложу.

c-darwin Feb 5 2015 at 15:03

Тесты:
max_miner_id = 10000
Кол-во итераций (блоков) = 10000
miner_id: сколько раз оказались на 0-м уровне
0-1000: 959
1000-2000: 1044
2000-3000: 988
3000-4000: 996
4000-5000: 1005
5000-6000: 1012
6000-7000: 985
7000-8000: 1008
8000-9000: 981
9000-10000: 1022

vibornoff Feb 5 2015 at 15:10

Возьмите max_miner_id побольше. Хотябы 3'000'000'000 (это даже меньше чем 32-битный MAX_UINT)

c-darwin Feb 5 2015 at 15:36

Да, Вы правы, после 2'147'483'647 майнера появится проблема. Спасибо, что указали на неё. Нужно будет поправить функцию определения майнера на 0-м уровне

vibornoff Feb 5 2015 at 15:36

Короче, простенький скрипт перебрал мне все возможные значения $ctx,
в итоге $x может иметь ровно 16777215 различных значений, что в точности совпадает с 2²⁴-1,
так что в итоге вся эта магия бессмысленна, и можно сразу использовать $ctx.

А чтобы гарантировать, что майнер выбирается равномерно, достаточно делать так:

$n = ceil( log2($max_miner_id) / 4 ) * 4;
do {
$hash = sha256($hash);
$x = hexdec(substr($hash, 0, $n));
}
while( $x < $max_miner_id )

$next_miner_id = $x+1;

c-darwin Feb 5 2015 at 16:41

У меня что-то не сходится. Можете показать результаты тестов работы Вашего варианта на 10к блоках и 3 млрд max_miner_id?

vibornoff Feb 5 2015 at 17:37

Показать что? Что next_miner_id равномерно распределен на интервале [ 1… max_miner_id ]? Так это очевидно же.

log2 — двоичный логарифм ( чтобы получить двоичный логарифм из «обычного», надо поделить на log(2) ).
$n — кол-во хексетов, необходимых для кодирования любого $miner_id ( в каждом хексете 4 бита )

на каждой итерации цикл получает псевдослучайное число $x в интервале [ 0… 2^{$n / 4} ]
при этом всегда $x/2 < $max_miner_id <= $x

Поэтому за одну итерацию цикл обнаруживает следующего майнера с вероятностью 1/2
или за 2 итерации обнаруживают майнера с вероятностью 3/4
или за 3 итерации — с вероятностью 7/8
и т.д.

vibornoff Feb 5 2015 at 17:41

О, пардон, конечно же
$n = ceil( log($max_miner_id) / log(16) ); // log — натуральный логарифм

c-darwin Feb 5 2015 at 19:17

И, наверное, Вы хотели написать while( $x > $max_miner_id )
Да, согласен, Ваш вариант лучше, с Вашего позволения, его внедрю.

vibornoff Feb 6 2015 at 00:22

Нет, именно

while ( $x < $max_miner_id )

т.к. 0 ≤ $x < 2^{4 * $n}
и $x/2 < $max_miner_id ≤ $x

Получается, что $x — это и есть следующий miner_id, уменьшенный на 1 (из приведенного фрагмента я понял, что miner_id начинаются с 1.

vibornoff Feb 6 2015 at 00:35

Пардон, конечно же вы правы, while( $x >= $max_miner_id )

c-darwin Feb 5 2015 at 14:23

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