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



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

    Я опишу вариант формирования блокчейна, который используется в Dcoin. Для его применения необходимо иметь уверенность, что ноды не смогут бесконтрольно размножаться.

    В Dcoin ноды не могут бесконтрольно размножаться, т.к. каждый майнер — это живой человек, который доказал другим майнерам, что он человек и у него нет клонов. Слово «майнер» тут, скорее всего, не очень вписывается, но так уж сложилось, что я его использую именно в таком ключе.

    Каждый раз после создания нового блока происходит распределение майнеров по уровням.

    Предположим, что на 0-м уровне оказался майнер с ID 1056. Тогда распределение по уровням будет выглядеть так:
    0: 1056
    1: 1057, 1058
    2: 1059, 1060, 1061, 1062
    N: 1056+(2^N)-1 -> 1056+((2^N)-1)*2

    Как определяется ID, который находится на 0-м уровне, я расскажу чуть позже.

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

    Блок имеет следующую структуру:
    Поле Описание Размер
    BLOCK_ID Порядковый номер блока 4 байта
    TIME Время, когда был создан блок 4 байта
    USER_ID ID пользователя, который создал блок 5 байт
    LEVEL Уровень, на котором был майнер в момент создания блока 2 байта
    SIGN Подпись от (TYPE, BLOCK_ID, PREV_BLOCK_HASH, TIME, USER_ID, LEVEL, MRKL_ROOT), сделанная при помощи node-ключа От 128 байт до 512 байт
    TRANSACTIONS Транзакции До 3Mb

    Время


    При получении нового блока проверяется время его генерации, которое указала нода, создавшая этот блок. При проверке времени учитывается количество секунд, затраченное на генерацию, проверку и ожидание на уровне.

    Через 120 секунд после времени подписания последнего блока нода майнера на 0-м уровне создает блок, записывая в него транзакции, которые у неё накопились.

    Если по какой-то причине нода майнера с 0-го уровня не отправила в сеть блок, то через 120 секунд (если 120 секунд не прошло, то все ноды ждут блока с 0-го уровня) блок могут подписать ноды с 1-го уровня и т. д. Если нода с 0-го уровня проснется и начнет всем рассылать свой блок, то у неё будет шанс его «протолкнуть» только в том случае, если большинство нодов еще не получили следующий блок.

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

    Сравнение хэшей


    Если блок подпишут ноды майнеров, например, со 2-го уровня, то получится 4 валидных блока, которые разделят всю сеть на 4 сегмента, и все сегменты будут уверены, что у них верный блок и верная цепочка блоков.

    Для того чтобы избежать такой сегментации, используется поиск наименьшего хэша от user_id,block_id,prev_head_hash.



    Таким образом, когда какая-нибудь нода получит, например, 4 блока от майнеров с одного уровня, то она выберет тот, у которого будет наименьший хэш, а остальные 3 проигнорирует. При этом ID у сравниваемых блоков должны быть равными.

    Манипуляции с хэшем невозможны, т.к. в нем нет данных, которые можно изменить.

    Процесс поиска блока с наименьшим хэшем вначале происходит между нодами одного уровня в течение от 5 до 8192 секунд в зависимости от уровня. Таким образом, в большинстве случаев в общую сеть попадают блоки с уже выбранным наименьшим хэшем.

    Майнер, который находится на 0-м уровне, определяется вот так:
    $ctx = hexdec(substr($hash, 0, 6));
    $hi = $ctx / 127773;
    $lo = $ctx % 127773;
    $x = 16807 * $lo - 2836 * $hi;
    if ($x <= 0)
    	$x += 0x7fffffff;
    $level_0_miner_id = (($ctx = $x) % ($max_miner_id + 1));
    $level_0_miner_id = ($level_0_miner_id==0)?1:$level_0_miner_id;
    

    Где $hash = sha256(sha256(user_id,block_id,prev_head_hash))), $max_miner_id — порядковый номер последнего зарегистрировавшегося майнера, prev_head_hash — это предыдущий хэш от user_id,block_id,prev_head_hash.

    Таким образом, сделать так, чтобы блоки подписывали какие-то определенные майнеры, невозможно, т.к. нет значения, которым можно манипулировать с целью изменения хэша (на основе которого происходит распределение майнеров по уровням). Благодаря этому описанный вариант формирования блокчейна может использоваться на практике.
    Dсoin
    Компания
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 15

      0
      Что насчет «Sybil Attack»?
        +1
        Ах, да, посмотрел ru.dcoinwiki.com/%D0%9C%D0%B0%D0%B9%D0%BD%D0%B5%D1%80
        Вердикт: нет, не взлетит.
          0
          Еще замечания:
          $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-й уровень, чем другие.
            0
            Честно говоря, почему именно 127773, 16807, 2836 я детально не разбирался, просто сделал тесты на разных хэшах и $max_miner_id, увидел, что распределение идет равномерно и решил оставить как есть.
            Вот тут есть некоторые ответы — www.christianpinder.com/articles/pseudo-random-number-generation/
            Результаты тестов сейчас найду и выложу.
              0
              Тесты:
              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
                0
                Возьмите max_miner_id побольше. Хотябы 3'000'000'000 (это даже меньше чем 32-битный MAX_UINT)
                  0
                  Да, Вы правы, после 2'147'483'647 майнера появится проблема. Спасибо, что указали на неё. Нужно будет поправить функцию определения майнера на 0-м уровне
                  0
                  Короче, простенький скрипт перебрал мне все возможные значения $ctx,
                  в итоге $x может иметь ровно 16777215 различных значений, что в точности совпадает с 224-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;
                    0
                    У меня что-то не сходится. Можете показать результаты тестов работы Вашего варианта на 10к блоках и 3 млрд max_miner_id?
                      0
                      Показать что? Что 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
                      и т.д.
                        0
                        О, пардон, конечно же
                        $n = ceil( log($max_miner_id) / log(16) ); // log — натуральный логарифм
                          0
                          И, наверное, Вы хотели написать while( $x > $max_miner_id )
                          Да, согласен, Ваш вариант лучше, с Вашего позволения, его внедрю.
                            0
                            Нет, именно
                            while ( $x < $max_miner_id )

                            т.к. 0 ≤ $x < 24 * $n
                            и $x/2 < $max_miner_id ≤ $x

                            Получается, что $x — это и есть следующий miner_id, уменьшенный на 1 (из приведенного фрагмента я понял, что miner_id начинаются с 1.
                              +1
                              Пардон, конечно же вы правы, while( $x >= $max_miner_id )
                  0
                  В двух словах, боюсь, ответить не смогу. Вот тут большая часть статьи как раз на эту тему.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое