Перейти к основному содержимому

Генерация случайного начального значения блока

warning

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

предупреждение

Эта информация актуальна на момент написания статьи. Она может измениться при любом обновлении сети.

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

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

Или этот вопрос можно сформулировать следующим образом. Можно ли включить внешнее сообщение в блок, в котором случайное значение будет точно таким, как нужно отправителю?

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

Как валидаторы влияют на начальное значение​

Об этом не так много информации даже в whitepapers, поэтому большинство разработчиков оказываются в затруднении. Вот единственное упоминание о случайности блока в TON Whitepaper:

Алгоритм, используемый для выбора групп задач валидаторов для каждого шарда (w, s), является детерминированным псевдослучайным. Он использует псевдослучайные числа, внедренные валидаторами в каждый блок мастерчейна (сгенерированные в результате консенсуса с использованием пороговых подписей), для создания случайного начального значения, а затем вычисляет, например, Hash(code(w). code(s).validator_id.rand_seed) для каждого валидатора.

Однако единственная вещь, которая гарантированно правдива и актуальна, - это код. Итак, давайте посмотрим на collator.cpp:

  {
    // generate rand seed
    prng::rand_gen().strong_rand_bytes(rand_seed->data(), 32);
    LOG(DEBUG) << "block random seed set to " << rand_seed->to_hex();
  }

Это код, который генерирует случайное начальное значение для блока. Он находится в коде коллатора, потому что он необходим стороне, генерирующей блоки (и не требуется для lite-валидаторов).

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

Можно ли принять решение о включении внешнего сообщения после того, как начальные значения будут известны?​

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

Таким образом, существует **способ взломать "небезопасный" (назовем его single-block, поскольку он не использует никакой информации из блоков после отправки сообщения) рандом, если отправитель может сотрудничать с валидатором. Даже если используется randomize_lt(). Валидатор может либо сгенерировать начальное значение, подходящее отправителю, либо включить в блок предложенное внешнее сообщение, которое будет удовлетворять всем условиям. Валидатор, поступающий таким образом, все равно будет считаться справедливым. В этом и заключается суть децентрализации.

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

Как начальные значения блока влияют на случайность в контрактах?​

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

bool Transaction::prepare_rand_seed(td::BitArray<256>& rand_seed, const ComputePhaseConfig& cfg) const {
  // we might use SHA256(block_rand_seed . addr . trans_lt)
  // instead, we use SHA256(block_rand_seed . addr)
  // if the smart contract wants to randomize further, it can use RANDOMIZE instruction
  td::BitArray<256 + 256> data;
  data.bits().copy_from(cfg.block_rand_seed.cbits(), 256);
  (data.bits() + 256).copy_from(account.addr_rewrite.cbits(), 256);
  rand_seed.clear();
  data.compute_sha256(rand_seed);
  return true;
}

Затем генерируются псевдослучайные числа с помощью процедуры, описанной на странице Инструкции TVM:

x{F810} RANDU256
Генерирует новое псевдослучайное беззнаковое 256-битное целое число x. Алгоритм следующий: если r - старое случайное начальное значение, рассматриваемое как 32-байтовый массив (путем построения big-endian представления беззнакового 256-битного целого числа), то вычисляется его sha512(r); первые 32 байта этого хеша хранятся как новое r' случайного начального значения, а оставшиеся 32 байта возвращаются как следующее случайное значение x.

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

Заключение​

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

Обычное использование PRNG (генератор псевдослучайных чисел) может включать randomize_lt(), но такой контракт можно обмануть, выбрав правильные блоки для отправки ему сообщений. Предлагаемое решение - отправлять сообщения в другой воркчейн, получать ответ, пропуская блоки, и т.д... но это только снижает степень уязвимости. На самом деле, любой валидатор (то есть 1/250 блокчейна TON) может выбрать правильное время для отправки запроса лотерейному контракту так, чтобы ответ от другого воркчейна пришел в сгенерированном им блоке, после чего он волен выбрать любое начальное значение блока по своему усмотрению. Опасность возрастет, как только коллаторы появятся в mainnet, так как они никогда не смогут быть оштрафованы по стандартным жалобам, потому что они не вкладывают никаких средств в контракт Elector.