Hi all. I have an idea for a RanDAO-like scheme that I think might work better than the existing RanDAO. I’d appreciate your thoughts.
Note: an easier-to-read format is at:
https://1drv.ms/w/s!AhIODQZva_pCuDp-eyAcZNvDorFr
To refresh, the basic idea behind RanDAO is that a number of different agents come up with random strings (s), and then publicly commit to hash(s). Then, once everybody has committed, the original s is revealed by each agent, and the XOR of all of the various s strings is the random guess.
This works because as long as there is even one honest participant, the XOR of the strings will be effectively random.
The problem I have with RanDAO is that it’s highly vulnerable to a user who does not reveal s in stage 2. If anybody doesn’t reveal s, no random number is generated. For example:
a) A lazy (or malfunctioning) agent could simply fail to submit their s.
b) A dishonest user could wait to see what everybody else has revealed. They effectively then have veto power over the random number that was generated.
RanDAO attempts to get around this by requiring each agent to give a good-faith deposit, which only gets refunded if s is revealed. However I fear that this is not particularly effective in industrial-strength applications: the penalty for cheating needs to be larger than the benefit of cheating. And the benefit of cheating on randomness can be huge, particularly for industrial-scale applications (imagine a lottery where one person gets veto power on every random draw).
My suggestion builds off of the underlying RanDAO concept, but layers in n-of-k secret sharing to ameliorate (but not eliminate) problems relating to failure to reveal.
Simplified version of my idea is as follows:
Assume that there are 1,000 guessing agents, and that at least 30 of them are honest. Later I will show how we can flex these assumptions.
1) Stage 1: each guesser generates a private random number “s”, and two public/private key pairs, pair A and B. Each guesser publishes their public key B as well as an encryption of their random number using their public key A.
2) Wait N blocks (say, 6)
3) Stage 2: Each agent encrypts their private key A into an N-of-K (say: 990-of-965) secret share. Meaning, 990 strings will be created, of which any 965 can be used to reconstruct the original private key A.
4) Stage 2 continued: Each agent randomly selects 990 of the 1,000 published public keys B, and encrypts the secret share via that public key and publishes to the block chain
5) Wait N blocks (say, 6)
6) Stage 3: Each agent publishes their private key A. If a handful of agents didn’t reveal the private key A, their private key A can probably be recovered (this last part can be done off-chain to save cost).
7) Stage 3 continued: The smart contract then trivially decrypts the original random number “s”, and XOR’s them all together to come up with the random guess.
Now let’s consider how this system is arguably better than RanDAO, and where it may still be vulnerable.
The first advantage is that it is resilient to a handful of agents accidentally failing to submit s. As long as at least 965 agents follow through (96.5% uptime), the original private keys A and thus s’es will be recovered.
The second advantage is that it is more resilient to the last-to-commit exploit. This is a bit harder to explain.
We are worried about the scenario where the cabal of dishonest agents has figured out the private key A of all of the honest agents. If this happens, the dishonest agents still have veto power, because as soon as they realize the XOR is a number they don’t like, they just stop publishing their keys in stage 2.
The only defense against this is if at least one of the honest guessers’ private key A remains unknown to the dishonest cabal. Let’s see how likely that is. Recall that each of the honest guessers is randomly choosing 990 other guessers to get their key shares. Out of those 990 shares, any 965 are enough to reconstruct the secret, so we are hoping that the dishonest cabal got less than 965 of those keys, and the honest ones got 15 or more.
Intuitively, this is extremely likely: with a random draw of 990 balls out of a population with 30 ‘honest’ balls and 970 ‘dishonest’ balls, it’s extremely likely that about 27-30 honest balls were chosen and that about 960-963 dishonest balls were chosen. It is astronomically unlikely to have 30 different draws have 965 or more dishonest public keys chosen.
More formally, we can say that with G guessers, K-of-N secret sharing, and H honest agents, the likelihood that a single honest agent had their private key A compromised is:
[Please see one drive version at
https://1drv.ms/w/s!AhIODQZva_pCuDp-eyAcZNvDorFr for properly-formatted equations]
Therefore the likelihood that all H agents were compromised is:
[Please see one drive version at
https://1drv.ms/w/s!AhIODQZva_pCuDp-eyAcZNvDorFr for properly-formatted equations]
So for example, with G=1000,K=990,N=965,H=30, we have:
• The likelihood that a given honest guess will be compromised is 1 in 15,257.
• The likelihood that all 30 honest guesses will be compromised is 1 in 15,257^30 = 1 in 3.2*10^125. So… not likely.
Alternatively, with G=100,K=97,N=97,H-3, we have:
• The likelihood that a given honest guess will be compromised is 1 in 4,851.
• The likelihood that all 3 honest guesses will be compromised is 1 in 114 billion
By the way, I would appreciate it if somebody could check my math above.
Now, let’s talk about some of the practical drawbacks of this scheme.
1) is fatal from a security standpoint.
2) The second drawback is that this system is still dependent on the assumption that you have enough honest guessers. If in the first example, there were actually only 27 honest guessers rather than 30, the odds of compromise are about 1 in 10^18 rather than 1 in 10^125. Worse, if there were only 25 honest guessers, compromise is certain. Of course there is no way to keep dishonest agents out, the key is to get enough honest agents into the system. A few ideas along these lines:
a. A few semi-trusted institutions could agree to keep a certain number of these agents running at any time (for example, Ethereum Foundation, Google, Facebook and Microsoft could each agree to have at least 1% of guessing power at any given time, as a public service)
b. A very simple client-side guessing agent should be developed
c. Guessing agents should get some fee income as an incentive for more people to generate guessing power. This will be a low fee income because the marginal cost of running a guessing agent is close to zero.
d. The client calling the smart contract could require as a precondition that a certain number of trusted agents be amongst those participating. It could even be their own agents. So for example, I might say, “Allow a minimum of 100 and a maximum of 1,000 guessing agents on this round, and it must include these 25 agents that I control”
3) Practically speaking, we want the system to be resilient to a number of different use cases. So I think the inputs to the smart contract calling this should include:
a. Fee
b. Minimum and maximum number of guessing agents (note: maximum is very dangerous because a dishonest cabal could front-run and take all of the agent slots… I’d only consider this secure if the user also specifies their own trusted guessing agents as part of the group)
c. Guessing agents that must be included in stage 1 (if any)
d. Some user-defined means to determine K and N. For instance: “Once you figure out G in stage 1, at the beginning of stage 2, set N as 96.5% of G, and set K such that as long as at least 3% of the guessers are honest, the likelihood of compromise is less than 1 in 10^30”
