Генераторы случайных чисел в смарт-контрактах

В этой статье рассматриваются алгоритмы генерации псевдослучайных чисел в смарт-контрактах на solidity. Предполагается, что читатель понимает работу Ethereum на логическом уровне.

Над материалом работала команда компании AXIOMA GROUP.

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

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

Смарт-контракты выполняются в детерминированной среде, поэтому источником энтропии для ГСЧ могут быть только внешние данные. Основная задача разработки ГСЧ на ethereum заключается в реализации надежного источника энтропии.

Варианты получения энтропии:

• Использование хэшей будущих блоков ethereum или bitcoin через BTCRelay.
• Схема commit-reveal. Получение энтропии в несколько этапов, исключающих манипуляции с источником энтропии.
  
• Схема, не исключающая возможность манипуляций с источником энтропии, но делающая такие манипуляции экономически невыгодными.
  
• Централизованный доверенный источник энтропии. (oracle)
  

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

Схема работы алгоритма

В смарт-контракте вызывается функция, которая сохраняет номер текущего блока N и блокируется, пока не будет получено достаточно подтверждений, например, пока не будет смайнен блок N+20.

При повторном вызове функции на основе хэша блока N (опционально + хэши нескольких блоков после N) генерируется случайное число. Если блок N был больше 256 блоков назад, то его хэш будет равен 0, поэтому необходимо либо прерывать работу смарт-контракта, либо использовать более свежий блок, например, N + 256.

Уязвимости

В ethereum хранятся хэши только 256 последних блоков, поэтому если подтверждение не поступило вовремя, хэш блока всегда будет 0. Пример использования уязвимости: [SmartBillions lottery contract just got hacked! : ethereum]

Этот способ тем не менее возможно применять, если в случае устаревшего блока прибавлять 256 к номеру блока, пока его хэш не станет отличаться от 0. Такой подход используется в проекте crypto kitties [3].

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

Также, способ не является детерминированным в случае устаревания блоков. Хэш будет меняться каждые 256 блоков, т.е. каждые 43 минуты, если новый блок создается раз в 10 секунд.

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

Путем симуляции атаки [GitHub - Bunjin/Rouleth: Roulette Smart Contract on Ethereum Blockchain] были получены данные о затратах на манипуляцию в зависимости от доли хэшрейта пула.

Анализ сималяции показал, что атакующий должен обладать по крайней мере 3% от мощности сети. В таком случае атакующий будет терять около 23 ETH за неопубликованный валидный блок. Эта сумма однако уменьшается с ростом вычислительной мощности атакующего. При обладании 10% от мощности сети потери будут составлять всего 2 ETH за блок. При 25% – 1.2 ETH. Если атакующему принадлежит 51% мощности сети, то потери снизятся до 0.5 ETH за блок, но в таком случае вся сеть будет находиться в опасности намного более серьезной, чем взлом одного смарт-контракта. [7]

Еще один пример расчета вероятности атаки – статья [Программирование генератора случайных чисел на Ethereum / Хабр], но в ней не учитывается возможность отправить блок как uncle.

Следует иметь в виду, что приведенные суммы потерь рассчитаны для сети ethereum и зависят от сложности сети и вознаграждения за блок. В сетях, использующих merged-mining или proof of stake, сложность сети значительно меньше, чем в сетях, использующих proof of work, поэтому использование хэшей блока в них менее безопасно, чем в ethereum.

На момент написания статьи имеется 1 пул с хэшрейтом более 25% от общего, 4 пула с хэшрейтом более 10%, 5 пулов с хэшрейтом более 3%, [Ethereum Top Miner Stats].

Таким образом, представляется реальной атака со стоимостью одной попытки 1.2 ETH.

Вероятность успеха зависит от бизнес-логики смарт-контракта. Если логику можно свести к угадыванию целого числа от 1 до N, вероятность успешной атаки равна 1/N. Следовательно, использование алгоритма, основанного на хэше блока, становится рискованным при цене операции больше N * 1.2 ETH. (Например, при подбрасывании монетки ставка не должна превышать 2.4 ETH ≈ $600).

Усложнить манипуляцию можно, используя хэш не одного, а нескольких блоков.

Цена при использовании BTCRelay

В сети bitcoin есть 5 пулов с хэшрейтом более 10% от общего [Распределение количества переборов хэшей (hashrate) - Blockchain.info].

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

В сети bitcoin нет анклов, поэтому при отказе от блока майнер полностью теряет вознаграждение – 12.6 BTC, при этом шанс найти еще один блок раньше других майнеров равна 0.1^2 = 0.01. При отказе от двух блоков, вероятность найти еще один блок раньше других майнеров равна 0.1^3 = 0.001 и т.д.

Аналогично, если нужное атакующему действие происходит с вероятностью 1/N, использование метода становится рискованным при цене N / 0.111 * 12.6 BTC. (Например, при подбрасывании монетки, ставка не должна превышать 227 BTC ≈ $1.3 миллиона)

Таким образом, использование хэшей bitcoin-блоков BTCRelay в качестве внешнего оракула достаточно надежно.

Схема работы алгоритма

Каждый участник генерирует уникальное для своего аккаунта число *s*, и отправляет sha(s) вместе с депозитом в смарт-контракт. Хэш sha(s) сохраняется в смарт-контракте.

После отправки хэшей все участники должны в течении определенного времени отправить свои числа s в открытом виде. В смарт-контракте считается хэш sha(s) и сравнивается с ранее сохраненным. Если хэши не совпали, т.е. участник отправил неправильное число или не отправил число в отведенное время, его депозит не возвращается, а остальные участники могут вернуть свои депозиты.

После получения чисел *s* в открытом виде от всех участников они передаются в функцию, генерирующую случайное число.

Эта схема реализована в сервисе Randao.

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

Уязвимости

Метод commit-reveal не требует доверия, считается надежным, но обладает недостатками.

Commit-reveal требует постоянного наличия активных участников и требует продолжительного ожидания результата.

Метод чувствителен к бездействию пользователей. Если один из участников не прислал подтверждение, то случайное число не будет получено. Также метод чувствителен и к ddos-атаке [7], при которой добросовестные участники вынуждено бездействуют и теряют залог.

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

Для решения этой проблемы В. Бутерин предложил улучшение RANDAO, при котором считается цепочка из хэшей начальных значений и хэшей блоков по принципу PoW, таким образом определение результата последним участником будет занимать слишком много времени, и если он будет пытаться его определить, то не успеет отправить подтверждение [Could Ethereum do this better? Tor Project is working on a web-wide random number generator : ethereum].

Пример реализации подобного решения, но с использованием в качестве энтропии хэша блока, а не commit-reveal: [GitHub - zweicoder/RNGesus: Secure, trustless, distributed Random Number Generation].

Суть решения – использовать в качестве случайного числа SHA3N (next block hash), где Nподбирается так, чтобы время на вычисление случайного числа было сопоставимо с временем генерации блока. В таком случае,даже если майнер успевает сгенерировать два валидных блока раньше, чем другие майнеры сгенерируют один валидный блок, он не успеет проверить, какой из двух блоков дает более выгодный результат до того, как блок от других майнеров будет отправлен в сеть. Недостаток такого решения – большая стоимость вычисления случайного числа.

Схема работы алгоритма

• Контора генерирует пару ключей, приватный и публичный, для алгоритма цифровой подписи.
• Контора создает смарт-контракт, содержащий публичный ключ в открытом виде.
  
• Игрок выбирает результат, на который он хочет сделать ставку и генерирует уникальное (ранее не использовавшееся в данной игре) случайное число R.
  
• Игрок отправляет в смарт-контракт свою ставку, результат, на который он поставил, и число R.
  
• Смарт-контракт проверяет валидность переданных данных, затем добавляет число R к адресу игрока. Полученное число V сохраняется в смарт-контракте.
  
• Контора подписывает число V своим приватным ключом и отправляет полученную подпись S в смарт-контракт.
  
• Смарт-контракт проверяет подпись с помощью известного открытого ключа.
  
• Эта подпись затем используется для генерации случайного числа [1].
  

Подробно тут: >[misc/rng4ethereum at master · gluk256/misc · GitHub] [5]

Уязвимости

Зависит от хэш-функции. Есть безопасные реализации на RSA [5].

Метод работает только при наличии второй стороны – казино – имеющей секретный ключ. Метод чувствителен к бездействию этой стороны, поэтому бизнес-логика должна сделать бездействие экономически невыгодным. Казино может узнать случайное число заранее и не отправлять его, если оно проигрышное, в этом случае игрок все равно получит выигрыш, однако, если логика зависит от конкретного числа, то этот алгоритм не может быть использован. [10]

Схема работы алгоритма

Пример простейшей схемы [solidity-patterns/Randomness.sol at master · fravoll/solidity-patterns · GitHub]:

• Игроки делают ставки.
• После закрытия ставок доверенный аккаунт присылает seed.
  
• Игроки вызывают функцию, генерирующую случайное число на основе seed.
  

Схема работы Oraclize [Oraclize Documentation]:

• Смарт-контракт, наследующий контракт usingOraclize, вызывает функцию, которая создает специальный блокчейн-event.
• Демон Oraclize следит за появлением блокчейн-event и, в зависимости от его типа, запрашивает данные из внешних источников.
  
• После поступления данных демон Oraclize вызывает функцию __callback смарт-контракта и передает данные в нее.
  

Уязвимости

Основная проблема – доверие к централизованному источнику.

Оракулы могут передавать данные из другого блокчейна, например, из bitcoin в ethereum через BTCRelay. С помощью BTCRelay можно использовать хэш будущего bitcoin-блока в качестве источника энтропии. В таком случае проблемы доверия не возникает, но появляется проблема стимулирования майнеров. Подробнее BTCRelay рассмотрен в разделе «Безопасность при использовании хэша будущего блока».

Для исключения доверия можно применять технологию Ledger.[Welcoming our brand new “Ledger proof” – Oraclize]

Она заключается в том, что смарт-контракту предоставляются доказательства того, что был выполнен конкретный, заранее известный алгоритм в детерминированной среде и что используемые в этом алгоритме приватные ключи не были изменены. Ledger proof планируют использовать в Oraclize при генерации случайных чисел.

Использование оракула чувствительно к атаке «опережение транзакции» (front-running transaction). Пример эксплойта [web3_utilz/front-running attack (lotteryExploit) at master · pertsev/web3_utilz · GitHub]. Исполнение контракта не должно зависеть от его положения в блоке.

Схему commit-reveal можно использовать совместно с хэшем будущего блока для увеличения числа источников энтропии, однако такая схема наследует недостатки обоих методов.

Ряд интересных алгоритмов ГПСЧ и их анализ есть в >репозитории [5].

Алгоритм, использующий задержку вычисления для предотвращения манипуляций майнера. Идея в том, что при вычислении случайного числа выполняется большое число ресурсоемких функций и в момент, когда майнер сможет понять, устраивает его результат или нет, у него уже не останется времени, чтобы сгенерировать новый блок раньше других майнеров. [9]

[GitHub - bbuenz/VerifiableBeacon: Public verifiable randomness beacons on Ethereum]

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

При наличии в системе некоторого центрального экономически мотивированного участника (например, казино) хорошо подходит алгоритм signidice.

Если участие казино в работе смарт-контрактов нежелательно или оно каким-то образом децентрализовано, также подходит метод генерации СЧ через оракулов.

Для распределение депозитов от многих равноправных сторон (например, лотерея, в которой случайным образом определяется победитель) подходит алгоритм commit/reveal.

Использование для генерации СЧ оракулов хорошо подходит для системы с одним участником. Также использование оракулов будет полезно, если система чувствительна к недобросовестности участников (например, долгая неработоспособность в случае, если один из участников signidice или commit-reveal будет бездействовать).

Надежность СЧ зависит не только от алгоритма ГПСЧ, но и от логики программы, которая его использует. В случае неправильной логики возможны манипуляции, значительно повышающие вероятность конкретного случайного результата, даже если сам ГПСЧ выдает непредсказуемые результаты, имеющие все статистические свойства настоящего случайного числа.

При проектировании системы, использующей ГПСЧ, необходимо учитывать мотивацию всех сторон, которые своими действиями или бездействием могут повлиять на результат работы смарт-контрактов (майнеры, оракулы, игроки, казино и т.д.). При расчете вероятности успешной манипуляции следует учитывать возможность атак, использующих криптографические коллизии.

Случаи, в которых возможны коллизии и которых следует избегать при разработке ГПСЧ:

Использование устаревших хэш-функций, таких как SHA1, в целях совместимости. Например, [GitHub - ensdomains/solsha1: Pure-solidity implementation of the SHA1 hash function</a>.].

Если SHA1 применить в алгоритме commit-reveal, будет возможна следующая манипуляция: участник, используя вычислительные мощности современных видеокарт или ASIC-ов, находит несколько чисел, имеющих одинаковый SHA1-хэш, затем на этапе reveal отправляет то число, которое даст наиболее выгодный результат (pre-image attacks).

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

Тестирование ГПСЧ на соответствие стандартамИспользование цифровой подписи ECDSA, так как подходящую подпись можно подобрать, изменяя входные параметры функции проверки подписей. Пример атаки: [web3_utilz/ECDSA signature generating (cheating) at master · pertsev/web3_utilz · GitHub].

Код смарт-контракта ГПСЧ необходимо проверять на подверженность известным атакам: [Rouleth/Security.md at master · Bunjin/Rouleth · GitHub], Reentrancy attack [http://solidity.readthedocs.io/en/latest/security-considerations.html #re-entrancy].

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

Следует учитывать, что из смарт-контракта доступны хэши только последних 256 блоков, а хэши всех более старых блоков будут равны нулю.

Проверка на опережение транзакции. Исполнение контракта не должно зависеть от его положения в блоке.

В случае использования хэш функций нужно учитывать, что keccak256("foo", "bar") == keccak256("fo", "obar») и при необходимости получения хэша от суммы строк использовать keccak256(keccak256("foo"), keccak256("bar"))

На основе полученной энтропии необходимо сгенерировать псевдослучайное число таким образом, чтобы оно было непредсказуемо и имело все статистические свойства как у настоящего случайного числа. Основной критерий – если seed неизвестен, то следующее случайное число невозможно предсказать на основе последовательности предыдущих случайных чисел. Хэш-функции обладают этими свойствами по определению, поэтому получить псевдослучайное число можно так:

R = uint256(keccak256(seed)).

Для повышения доверия пользователей онлайн казино и покер-румы проходят сертификацию своих ГПСЧ. Для сертификации алгоритм должен пройти набор тестов NIST (National Institute of Standards and Technology). Он включает различные тесты: от теста на соотношение 0 и 1 в генерируемой последовательности до теста на сжатие алгоритмом LZO (случайная последовательность не может быть существенна сжата, потому что не должна иметь много повторяющихся последовательностей) [11].

The Frequency (Monobit) Test,

Frequency Test within a Block,

The Runs Test,

Tests for the Longest-Run-of-Ones in a Block,

The Binary Matrix Rank Test,

The Discrete Fourier Transform (Spectral) Test,

The Non-overlapping Template Matching Test,

The Overlapping Template Matching Test,

Maurer's "Universal Statistical" Test,

The Linear Complexity Test,

The Serial Test,

The Approximate Entropy Test,

The Cumulative Sums (Cusums) Test,

The Random Excursions Test, and

The Random Excursions Variant Test.

В Proof Of Toss случайные числа используются для распределения событий между судьями, которые определяют выигравшие результаты. Каждому событию назначается 50 судей. Судьи заинтересованы в манипуляциях, которые позволят назначить себе конкретное событие. Поэтому в Proof of Toss применяются экономические и технические меры для того, чтобы такие манипуляции были невыгодны:

1. перед распределением судьи вносят депозит = 1/50 от суммарного вознаграждения за судейство.

2. для распределения используется вариант схемы коммит-раскрытие, при котором, в отличии от Randao, нераскрытие участником начального числа не останавливает работу алгоритма.

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

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

Основной недостаток метода: это работает долго.

Алгоритм:

Как мы видим, выбор метода ГПСЧ требует проведения анализа бизнес-логики приложения, определение сценариев возможных атак и разработку экономических мер противодействия им. Универсального способа генерации случайных чисел на блокчейне в данный момент не существует. Перспективные методы, такие как Ledger для Oraclize и Randao++, еще находятся в разработке.

Пост подготовила команда компании AXIOMA GROUP.

Пообщаемся в комментариях?

Источники

1. [Предсказание случайных чисел в умных контрактах Ethereum / Хабр]

2. [Could Ethereum do this better? Tor Project is working on a web-wide random number generator: ethereum]

3. [GitHub - axiomzen/eth-random: commit-reveal RNG method in Ethereum]

4. https://randao.org/whitepaper/Randao_v0.85_en.pdf

5. [misc/rng4ethereum at master · gluk256/misc · GitHub]

6. [GitHub - pertsev/web3_utilz: Useful snippets of js code for interacting with Smart Contracts](https://github.com/pertsev/web3_utilz)

7. [Whitepaper/DAO.Casino WP.md at master · DaoCasino/Whitepaper · GitHub]

8. [Rouleth/Provably_Fair_No_Cheating.md at master · Bunjin/Rouleth · GitHub]

9. http://www.jbonneau.com/doc/BGB17-IEEESB-proof_of_delay_ethereum.pdf

10. [DAO.Casino Development Update November — December 2017]

11. [Правда о ГСЧ покер румов / Блог компании Покерофф / Хабр]

12. https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf

13. https://csrc.nist.gov/publications/detail/sp/800-115/final

14. http://www.ijcee.org/papers/439-JE503.pdf