When your blockchain needs to roll the dice
Many of the applications we use every day depend on randomness, from to lotteries over scientific application to leader election or private key generation. Today we talk about public randomness, which more precisely refers to values that are unpredictable until revealed but then immutable and available to everyone.
On blockchains randomess is not easy to create due to their deterministic nature. Every participant needs to agree on the same random value. Typical workarounds like block generation times or block hashes are easy to manipulate for a block creator. Common signature schemes like Secp256k1 or Ed25519 don’t produce unique signatures and can be bended at will. You also don’t want to trust a single party for publishing random values as this party might bias the values in a way that favours them or simply stop producing values. Even in more sophisticated commit-reveal schemes, there is at least one party that has the last mover advantage and can either manipulate the result or at least deny publishing its part such that the application halts.
There have been attempts to include random beacon functionality into Tendermint directly, but I haven’t seen any production-ready solution yet.
Now there is a project called drand, which aims to provide a random number generator for the internet. I’ll not go too much into detail of how it works as the Randomness Summit 2020 is basically a one-day marketing campaign explaining everything about it. But the deal is: instead of trusting a single party, you trust a group of oganizations (the League of Entropy) to produce an unpredictable and unbiased value. The so called random beacons are created every 30 seconds, are ordered by a round number, are signed and can be verified in a client.
The CosmWasm drand client
In drand, random beacons are distributed via HTTP, Gossipsub, Tor or Twitter. Such network sources cannot be accessed by a blockchain directly. However, we can create a CosmWasm smart contract which allows storing random beacons on chain. Using cross-contract queries, other contracts can then read those random values and use them in their logic.
Beacon verification
Any beacon is self verifiable, i.e. you can check the validity of a single beacon without having to verify the whole chain. The signature is a BLS12–381 signature of the input previous_signature || round. The 32 byte randomness is simply a SHA-256 hash of the signature. In order to avoid accepting malicious beacons, the contract needs to be able to verify the signatures. Drand signature verification is available in the Rust crate drand-verify, which compiles nicely to Wasm and can be used in contracts. There is one caveat though: verifiying a single signature in Wasm takes about 200 milliseconds and costs 500 million CosmWasm VM gas (about 5 million Cosmos SDK gas).
Once the beacon is verified, there is no need to store all of its data on chain. We can simply derive the 32 bytes randomness after verification and only store a map from round to randomness.
Incentivization model
Adding beacons to the randomness contract costs gas and once the randomess was added, it becomes a common good that is freely accessible by everyone. Since beacons become part of the redundant, public, immutable blockchain state, there is no way to restrict access to it without changing fundamentals of the technology. So the question is, how to incentivise an off-chain party to collect beacons and add them to chain?
One approach is a bounty system. An application that depends on randomness at round n in the future can put a bounty on round n. Once the beacon becomes available and the bounty is higher than the cost to add it to chain, some actor will add it. If there is not yet enough bounty on n, whoever needs this beacon either needs to increase the bounty or add the beacon for a higher cost.
This brings in some interesting ecomonic mechanisms. If the bounty is high enough, many actors will compete on claiming it such that the beacon is available very fast. If the bounty is too low the beacon might be added slowly, having to wait for a cheap block proposer. Multiple applications can pool to provide a bounty for future rounds. This can become very efficient when many apps agree to only use every e.g. 10th or 60th round (i.e. one beacon every 5min or 30 min).
Further development
Everything we discussed above is implemented and working. Right now, the 657 KiB large contract cannot be uploaded to x/wasm chains, because of a hard size limit. CosmWasm 0.12 will solve that. It might also be necessary to adjust transaction and block size limits as well as gas limits to allow contract upload and execution.
Once everything is working, we are considering to add APIs provided by the VM for heavy cryptographic operations. This should lower the gas cost significantly. However, the contract does not depend on such optimizations.
Last but not least the economic model might lead to situations where no participant is willing to pay a bounty and waits until others do. This might require better economics.
Kudos
None of this work would have been possible without the team behind drand, the Electric Coin Co. team for implementing BLS12–381 in Rust and the Filecoin team for implementing Hash to Curve in Rust.
