Name: Veedo randomness for shard selection
Overview: Periodically use randomness from Veedo for shard selection, instead of only RenVM’s randomness, allowing corrupted shards to eventually become uncorrupted.
In the next few months, the introduction of shards to RenVM will result in RenVM using its MPC algorithm for randomness as well as signature generation. Our MPC wiki gives a good overview of how randomness in RenVM works. Before diving into the details of the RFC, it is instructive to give a bit of background on how shard selection will work in RenVM assuming this RFC is not implemented.
First, we should recap on some definitions. The RenVM wiki is out-dates on the precise mechanics of shards (mostly a minor change in nomenclature, and some missing details).
- The core is a blockchain maintained by RenVM nodes that is responsible for shard selection and map/reducing transactions (and other work) to the shards.
- The shards are responsible for execution using the RZL MPC algorithm for key and signature generation.
Essentially, the core tells the shards what to do, and the shards do it. In the context of this RFC, one bit of functionality delegated to the core is of particular interest: shard selection.
Once per day, an epoch change is triggered and the core undergoes membership selection for itself and all shards for the next epoch. The members of the core in the current epoch engage in an MPC random number generation to create a random seed. MPC random number generation has a safety threshold of 1/3rd; it is secure when less than 1/3rd of the core is adversarial.
The seed is appended to the cryptographic identity of every node and then hashed to produce a sorting identity. Nodes are then sorted from smallest to largest sorting identity and then selected one by one for each shard. The first N nodes will be the members of the core in the next epoch, the next N nodes will be the members of the first shard in the next epoch, and so on.
This works assuming that the core is not corrupted (more than 1/3rd of its members are adversarial). In this case it becomes possible for the core to manipulate shard selection. It is still non-trivial, because the random number must be selected such that the sorting algorithm gives the desired results, but we should consider any form of manipulation unacceptable.
In the worst case, the corrupted core can find a random number such that the core is still corrupted in the next epoch. This implies that the core will be forever corrupted. The goal of this RFC is to bring in external randomness so that the corruption of the core does not necessarily imply its permanent corruption.
Veedo is a new verifiable delay function built by StarkWare, but it can also be used as a random number generator. The general idea is that, one in every M epochs would use the Veedo random number generator instead of the MPC algorithm. This means that a corrupted core would — at most — stay corrupted for M epochs.
How It Works
Every M epochs, the Ethereum block hash of the block prior to the one that triggered the new epoch would be passed to Veedo to begin a ~10 minute verifiable delay. This results in a random number that no one can know for ~10 minutes. This delay is important, because it prevents mining attacks against the Ethereum blockchain in an attempt to grind for a specific random number (after ~10 minutes the Ethereum blockchain has moved on, making it very difficult to reorg the chain, making grinding ineffective).
There is, of course, a cost required to use Veedo. This cost would be paid for by the rewards RenVM generates, meaning that the cost is essentially being paid for by node operators. I think the cost is on the order of $X00 per invocation, but this can be verified with the StarkWare team. The larger M, the lower the cost of implementing this RFC, but the longer a corrupted core could stay corrupted.
RenVM is currently making ~$5K per day, and once shards are enabled, we expect epochs to be approximately one day in length.
One alternative to using Veedo is to engage all shards, not just the core, in random number generation. I am not entirely sure what this model looks like, but certainly involving all shards makes random number generation much harder to corrupt (harder than stealing all TLV in RenVM which is obviously a worse failure mode). This would incur none of the costs of Veedo, and would prevent RenVM having any dependencies on it, but would increase the work load required by RenVM itself during epoch changes (using all shards to generate one random number is non-trivial).