Программирование генератора случайных чисел на Ethereum

    image


    При разработке смарт-контрактов на Ethereum обычно считается что полагаться на хеш блока как источник рандомности ненадежно, так как майнер может влиять на результат, подбирая хеш блока (см. Private Information and Randomness, How do you get a random number in a contract?)


    Насколько в действительности велика возможность для майнера увеличить свои шансы на выигрыш в игре в которой нужно угадать хеш блока c определенным номером (или некое число производимое от хеша блока)?


    Вероятность угадать случайное число в диапазоне от 0 до 9 составляет 1/10


    Предположим, для простоты, что хеш блока это тоже число от 0 до 9.


    То есть, предположим мы получаем число от 0 до 9 в зависимости от хеша блока, или другими словами приводим хеш блока к числу от 0 до 9.
    Например так:


    function blockHashToNumberFrom0to9(uint blockNumber) public view returns (uint){
        uint random_number = uint(block.blockhash(blockNumber))%10;
        return random_number;
        }

    Предположим, я — майнер, обладающий такой вычислительной мощностью, что каждый 5й блок в сети майниться мной, т.е. мои шансы что я замайню следующий блок 2/10.
    Например, один из крупнейших пулов (см.https://etherscan.io/stat/miner?range=1&blocktype=blocks), нашел способ всем участникам пула договориться об общей ставке в лото, и постараться влиять на результат. При этом конечно надо пренебречь возможными потерями дохода от майнинга.


    Скажем я сделал ставку, и хочу повлиять на результат.


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


    Мои шансы найти два блока подряд: 2/10 * 2/10 = 4/100


    Какие шансы что второй мой блок будет именно тем который мне нужен?


    Рассуждаем следующим образом:


    Шансы что выпадет такое же число 1/10 * 1/10 = 1/100


    Шансы что выпадет другое число 1-1/100 = 99/100


    Шансы что это число окажется тем которое нужно 99/100: 9 = 11/100


    Шансы что эти события совпадут, то есть что я найду два блока подряд раньше чем остальная сеть найдет один и мой второй блок будет тем который мне нужен: 4/100 * 11/100 = 44/10000


    Итого, сам подбирая блок, я увеличиваю свои шансы в игре на 44/10000:


    0.1 + 0.0044 = 0.1044


    Другими словами, мой шанс на выигрыш вместо 10% будет 10.44 %


    Шансы что я найду третий валидный блок раньше чем остальная сеть найдет один и этот блок окажется тем который мне нужен, и т.п. рассчитываются подобным же образом: мы добавляем шансы в которых вероятность отображается дробью числитель которой будет больше на единицы, а знаменатель больше на десятки, т.е. это в сумме не увеличит вероятность больше чем на 1/10000, иными словами при округлении до двух знаков после запятой, это будет то же самое число: ~ 10.44 %
    Для игрока майнящего каждый 10 блок в сети: ~ 10.11 %


    Однако мы исходили из того, что: "Мои шансы что я найду два валидных блока с разными хешами быстрее чем остальная сеть замайнит блок (один) для этого номера блока? 2/10 * 2/10 = 4/100" Это вероятность того что вообще будет найдено два блока подряд этим майнером. Вероятность того что это будет сделано быстрее чем остальная сеть найдет один — еще меньше.


    Соответственно если результат задается не хешем одного блока, а скажем хешами некоторого количества последовательных блоков (скажем мы реализуем лото "5 из 36", где 36 двузначных цифр получаются из хешей 72 последовательных блоков), то возможность майнера повлиять на результат еще меньше. Таким образом если мы в качестве источника рандомности берем хеши нескольких последовательных блоков, шансы отдельно взятого майнера повлиять на результат, настолько малы, что в большинстве случаев ними можно пренебречь, даже есть речь идет о розыгрыше денежных (ETH) призов.


    Интересно было бы мнение сообщества насколько корректно такое рассуждение.


    UPD:
    Мне кажется, важное замечание.

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 15

      +1
      А если первый найденный блок уже является нужным?
      Я бы считал примерно так: фиксация числа от 0 до 9 в 10 раз уменьшает вычислительную мощность (9/10 хэшей отвергаются), осталось лишь посчитать новую долю вычислительной мощности. До снижения в 10 раз она составляла 20%, после — 2% от 82% (мощность всей сети тоже снизилась), итого примерно 2,44%. Тогда с вероятностью 2,44% выпадет нужное число, а с оставшейся — случайное, итого этот пул поднял вероятность с 10% до 2,44% + (100% — 2,44%) * 0,1 = 12,196%. Получается побольше.
        0
        мощность всей сети тоже снизилась

        Почему?
          0
          Потому что мощность всей сети — это сумма мощностей всех майнеров в ней, а один из майнеров снизил мощность.
          0
          Я бы считал примерно так: фиксация числа от 0 до 9 в 10 раз уменьшает вычислительную мощность (9/10 хэшей отвергаются),

          Имхо, хороший подход. Наглядно.

          Таким образом если у нас хеш будет приводится к двузначному числу
          uint random_number = uint(block.blockhash(blockNumber))%99;

          то фиксация числа для майнера снижает вычислительную мощность в 100 раз.
          0
          А если первый найденный блок уже является нужным?

          Тогда мы не можем говорить, о том что майнер манипулировал результатом.
            0
            Почему выборочное поведение для первого блока (нужный блок распространить, ненужный — выкинуть) не считается манипулированием, а такое же поведение для второго считается?
              0
              ну если присутствует
              ненужный — выкинуть
              то считается
                +2
                Так в статье рассматривается вариант, если первый блок выкидывается всегда. В 2% случаев мы выкинули блок, который дал бы нужное число, поэтому и итоговая оценка вероятности в статье на 2% ниже.
                  0
                  поэтому и итоговая оценка вероятности в статье на 2% ниже.

                  Да, мне кажется, справедливое замечание.
            0
            скажем мы реализуем лото "5 из 36"

            (5!x31!)/36! => 120/45239040 = 0.000002653 => 0.0002653% найти 5 из 36.

              0
              Таким образом если мы в качестве источника рандомности берем хеши нескольких последовательных блоков, шансы отдельно взятого майнера повлиять на результат, настолько малы, что в большинстве случаев ними можно пренебречь, даже есть речь идет о розыгрыше денежных (ETH) призов.

              Верно, но у этого подхода есть минусы. Пусть у вас есть метод calculateLotteryWinners, который смотрит на хэши последних 72 блоков. Для секьюрности вы должны заранее наложить несколько ограничений:

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

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

              Теперь вы обязаны иметь offchain-бота, который будет следить за блокчейном и дергать метод в нужным момент — это сложно и децентрализованно.

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

              Ознакомиться с подробным рассказом можно здесь
                0
                все голоса пользователей должна быть сделаны как минимум 72 блока назад

                Естественно. Но на Этериум это не так много времени занимает.
                Да и на практике в этом случае лучше реализовать приведение хешей 36 блоков к двузначным числам.
                метод должен быть вызван обязательно вами

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

                Не обязательно точно в этот блок. В любом блоке номер которого больше оределенного номера.

                Я по такому принципу делал голосование акционеров в смарт-контракте с акциями coinoffering.github.io/dapp/#/smart-contract: голосовать могут только адреса у которых есть токены (акции), а трансакцию инициирующую подсчет голосов можно запустить с любого адреса, но сработает только если время блока больше времени окончания голосования.
                Теперь вы обязаны иметь offchain-бота, который будет следить за блокчейном и дергать метод в нужным момент — это сложно и децентрализованно.

                Это не будет приводить к централизации — может же каждый запустить, а бот может работать для подстраховки: проверять состояние смарт-контракта периодически, если надо, инициировать трансакцию запускающую подсчет хешей в «генераторе случайных чисел». Пример такого бота: github.com/thedeex/deex.price.setter — он у меня цены выставлял в смар-контакте в зависимости от текущего курса USD/ETH, принцип работы аналогичен.
                у вызывающего есть возможность выбрать удобную
                последовательность хэшей

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

                Мне кажется описанный здесь подход проще.

                Ну и вообще тут речь не только о лото и лотерях, просто это наиболее простой и наглядный пример. Речь вообще о надежном методе получения рандомных чисел на блокчейне.
                  0
                  Сеть даёт доступ только к последним 256 блокам. Cryptokitties тоже полагаются на хэши и, к примеру, когда выходят за границу, то берут хэш одного из последних. В этот момент появляется возможность атаки — дёргать метод, когда хэши нравятся. А 256 в масштабах сети настолько же немного, насколько и 72. Как вы предлагаете с этим бороться?
                    0
                    Брать хеши на определенное количество блоков от блока с заранее определенным номером, а не от блока в котором запущен генератор.
                    Как говорили выше можно иметь страховочного бота, который будет следить за смарт-контрактом и запускать генератор (если уже пора, а никто не запустил)
                0
                Хорошая статья по теме:
                Арсений Реутов. Как обмануть криптоказино. Предсказываем случайные числа в умных контрактах Ethereum // «Хакер», 12.04.2018 // xakep.ru/2018/04/12/ethereum-cheating

                Only users with full accounts can post comments. Log in, please.