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

Generation of block random seed

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

This information is up-to-date at the moment of writing. It may change at any network upgrade.

Once in a while, a lottery contract is created on TON. Usually it uses an unsafe way to handle randomness, so generated values can be predicted by user and lottery can be drained.

But exploiting weaknesses in random numbers generation often involves using a proxy contract which forwards message if random value is correct. There exist proposals for wallet contracts which will be able to execute arbitrary code (specified and signed by user, of course) onchain, but most popular wallet versions don't support doing this. So, if lottery is checking whether gambler is participating through a wallet contract, is it safe?

Or, this question can be written as follows. Can an external message be included in block where random value is exactly as needed by sender?

Of course, sender doesn't affect randomness in any way. But validators generating blocks and including proposed external messages do.

How validators affect seed​

There is not much information about this even in whitepapers so most developers get confused. Here's the only mention of block random in TON Whitepaper:

The algorithm used to select validator task groups for each shard (w, s) is deterministic pseudorandom. It uses pseudorandom numbers embedded by validators into each masterchain block (generated by a consensus using threshold signatures) to create a random seed, and then computes for example Hash(code(w). code(s).validator_id.rand_seed) for each validator.

However, the only thing that is guaranteed to be truthful and up-to-date is code. So let's look at 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();
  }

This is code that generates random seed for block. It's located in collator code because it's needed by party generating blocks (and is not required for lite validators).

So, as we can see, seed is generated with block by single validator or collator. The next question is:

Can decision on including external message be made after seed is known?​

Yes, it can. The proof is as follows: if external message is imported, its execution must be successful. Execution can be dependent on random values so block seed is guaranteed to known beforehand.

So, there is way to hack "unsafe" (let's call it single-block, because it doesn't use any information from blocks after sending message) random if sender can cooperate with validator. Even if randomize_lt() is used. The validator can either generate seed that is suitable for sender or include proposed external message in block that will satisfy all conditions. Validator doing so will still be considered fair. This is the essence of decentralization.

And, to make this article cover randomness fully, here's one more question.

How does block seed affect random in contracts?​

Seed generated by validator isn't used directly in all contracts. Instead, it's hashed with account address.

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;
}

Then pseudorandom numbers are generated with procedure described on TVM instructions page:

x{F810} RANDU256
Generates a new pseudo-random unsigned 256-bit Integer x. The algorithm is as follows: if r is the old value of the random seed, considered as a 32-byte array (by constructing the big-endian representation of an unsigned 256-bit integer), then its sha512(r) is computed; the first 32 bytes of this hash are stored as the new value r' of the random seed, and the remaining 32 bytes are returned as the next random value x.

We can confirm this by looking into code of preparation of contract's c7 (c7 is tuple for temporary data, that stores contract address, start balance, random seed, etc) and generation of random values themselves.

Conclusion​

No random in TON is completely safe in sense of unpredictability. This means no perfect lottery can exist here, nor can any lottery be believed in to be fair.

Typical usage of PRNG may possibly include randomize_lt(), but it is possible to trick such a contract by choosing correct blocks to send messages to it. The proposed solution to that is sending messages to other workchain, receiving answer, thus skipping blocks, etc... but it only puts off the threat. In fact, any validator (that is, 1/250 of TON Blockchain) can choose correct time for sending a request to lottery contract so that answer from other workchain arrives in block generated by him, then he is free to choose any block seed he wishes. The danger will increase once collators appear in mainnet, as they can't ever be fined by standard complaints because they don't put any stake into Elector contract.