Overview

The Randomizer module was introduced to improve the previous randomization technique (tezos transaction hash) by providing true, fair and verifiable randomness on fxhash. The Randomizer modules relies on a 2-step process to ensure a fair source of randomness for every user:

• on mint, some pseudo-randomness is generated on-chain
• an off-chain authority then reveals a random number which is combined with the on-chain one

Properties of the Randomizer

• randomness is completely fair
• randomness is generated using a transparent process, which cannot be predicted but can be verified once revealed (One-way functions)
• randomness cannot be attacked as long as the off-chain authority stores the random numbers secretely
• as soon as a random request is written on-chain, the off-chain Authority can expose the random number via its open API

Why is an off-chain module required ?

There isn't any source of randomness available on-chain when an operation is executed. Blockchains are fully deterministic state machines, when a block is added to the chain, the only inputs it is based on are the state at the end of the previous block, the transactions to be included in the new block, and some properties of the block (such as its index on the blockchain, or the timestamp at which it is injected). All of these informations are known in advance, before injecting the transaction. As such, an attacker can predict the on-chain randomness and compute the data which will be generated by a transaction before sending it.

That's why we use a 2-step process, such that the final randomness associated with an iteration is only known on-chain after a few blocks. However, our system is designed to provide a way for users to get the final randomness as soon as their mint operation is injected (as the randomness associated to it is known in advance by our authority). This ensure a seamless reveal process, allowing users to preview their iteration as soon as the mint is injected on the blockchain.

Trade-offs

We want to be transparent about the trade-offs of such a system. The off-chain authority must be active for new mints to get their random number associated. This is a trade-off of decentralization for security. However, once revealed, the mints are permanent and even if the authority were to disappear, it would only impact new mints. This trade-off is unfortunately necessary for true randomness.

Technical details

System overview

The different modules:

• Randomizer Smart Contract called at mint() time by all the issuer contracts to request a seed, is responsible for mapping random seeds to seed requests
• Authority an off-chain module, ran by fxhash, responsible for generating, revealing and exposing the secret seeds
  • worker watches blockchain for generate() requests, triggering the associated reveal()
  • api exposes final seeds before reveal() operation occur (useful to reveal iterations before their seed is finally revealed on-chain)

Trustless random seed generation

Overview

The secret seeds are pre-computed in advance, and stored safely in a database only accessible to the Authority itself. The computation of the seeds is done such as the generation process can be verified publicly (and on-chain by the smart contract) after the seeds are revealed.

A reverse hash-chain is the computational process behind the random numbers generated.

Computation process

The Authority pre-computes a hash chain using keccak256.

• first, 2 inputs are computed:
  • the tail or hash_0 of the chain: 32 random bytes
  • a salt: 8 random bytes
• salt+hash_0 are hashed using keccak256, outputting a hash of 32 bytes: hash_1
• salt+hash_1 are hashed using keccak256, outputting a hash of 32 bytes: hash_2
• this process is repeated N times, resulting in N+1 hashes of 32 bytes, so called hash chain
• the final hash of this series is called the head

One-way nature of hash chains

Hash chains have a feature particularly relevant to the needs of our system: knowing the salt and any hash from the chain, it is very easy to compute the following hashes. However, knowing the salt and just one hash, it is close to impoosible to compute a previous hash. These kind of functions are known as One-way functions in computer science.

While it is not impossible to reverse the computation (or force it by random guesses), in our case it takes orders of magnitude more time to compute it than the time it will take for the Authority to reveal the next hash (a new hash is revealed every 2 minutes on average). Each time a new hash in revealed, it invalidates computations made for the previous one.

Using the hash chain for the reveal process

To ensure fairness of the reveal process for consumers of the Randomizer, we need the Smart Contract to enforce the hash chain must be revealed in order. Before revealing any hash, the Authority commits to the salt and the head of the chain it will reveal.

Then, it will reveal hashes in the reverse order of the hash chain. Each time a hash is revealed, the Smart Contract will ensure that keccak(salt, new_hash) = preview_hash_revealed. If not, the Authority tried to reveal a wrong hash, and the operation is rejected. This process ensures the authority itself cannot temper with random numbers generated (it can never reveal an unfair number).

When generate() requests are coming to the Randomizer contract, they are indexed in the order they come. When revealing, the secret hashes are also revealed in order. This mechanism allows the Authority to know which secret hash will be associated with each generate() request, and as such the Authority can expose this secret hash off-chain even before it is revealed.

Entropy and semi-reliance on Authority

When a generate request is sent to the Randomizer Smart Contract, some pseudo-random bytes are produced on-chain, by hashing:

• block timestamp
• token id
• issuer id

This is referred to as the public seed.

The final seed of an iteration is computed as keccak(public_seed, secret_seed). This ensures that even though some entropy is lost with the hash chain process, it is compensated by the on-chain entropy. Moreover, it also ensures that the Authority alone doesn't know all the future seeds of the tokens.

Summary of the reveal process

• previous hash is stored in the Smart Contract (in the beginning, this is the hash chain head)
• user requests to generate() a random seed, when calling a mint() entry point
  • a 32 bytes public seed is generated by hashing:
    • block timestamp
    • issuer contract version
    • token id
  • the public seed is stored
• the Authority observes the generate() call, and triggers a reveal() call
  • it sends the next hash in the hash chain, as secret_seed
• the reveal call generates a final seed
  • the secret_seed is verified, by comparing keccak256(secret_seed) with previous hash
  • the final seed is computed by hashing the public seed and the secret seed together final_seed = keccak256(concat(public_seed, secret_seed))
• the final seed is stored in the smart contract, associated to the (issuer_version, token_id)
• the previous hash is replaced by the secret_seed provided to the reveal entry point: it will be used for the next comparison

Ensuring back-compatibility with pre-Randomizer projects

We needed the new Randomizer module to work with already existing projects. Prior to the Randomizer, the tezos transaction hash of mint() operations was used as a seed for the tokens. A tezos transaction hash is a 51 characters string of base58 character set (examples: ooUNLHqpe69DW7nBCAaq5u4nPzi6zBMtXgfE2Xhfj8XgQ7i8tGU, ooj2HmX8dgniNPuPRcapyXBn9vYpsNwgD1uwx98SLceF6iCZJZK). The transaction hash is computed by hashing the whole bytes of a transaction into 32 bytes, and base58check encoding those bytes with the prefix 0x0574.

So basically, given any 32 bytes, we can generate a "tezos transaction hash format" output, which can be fed to the projects just as before.

The Randomizer itself is working with 32 bytes segments, and an off-chain convention defines how to turn those 32 bytes into a project-ready hash. The fxhash signer is responsible for this process.

Key aspects of the Randomizer

• once the Authority commits a head for the hash chain, it can only reveal the associated hash chain in order. There is no way for it to reveal seeds outside of the chain (as prevented by the Smart Contract itself), making it a fair provider of random bytes
• the Authority can always commit to a new hash chain, but must do so publicly by calling the Randomizer Smart Contract; as such users can verify if the Authority has provided a reasonable explanation for the reset of the chain. Reasonable explanations can be:
  • the tail of the hash chain has been reached
  • the hash chain has been compromised
• the hash chain is too strong to be attacked; to find the previous element of any element in the sequence, it takes many orders of magnitude of time compared to the time it will take for this previous element to be revealed on-chain. Whenever a new element is revealed, all the time spent in attacking the previous one is nullified.
• the Authority itself cannot dictate what final seeds will be: because a final seed is computed with a public_seed unknown by the Authority at the time when the hash chain is computed, it cannot know in advance what final_seeds will be, ensuring a fair process for other parties.