[RFC] Stake of Random for the secure random source

[ryoqun]

(Because I'm new to designing blockchains, I might miss some critical points. Admittedly, I still completely don't understand the problem mentioned at here. So my proposal might be completely a bogus idea. Or if it tickles your creativity, please give me some feedback!)

(I'm aware of this, but also that too. This is just a very rough idea, so chosen a lightweight way. Sorry for spamming!)

Stake of Random

Background

Randoms are very important. But ensuring randomness is hard, that's because proving the correctness of randomness is hard at the philosophical level. Did you notice the correctness part? You should have heard similar problem... Let's solve with staking. So, much like correct block selection by the network on the whole, we define the correctness of randomness by staking. So, randomness is staked and guaranteed as much as the underlying proof of stake; less than 1/3 (or 2/3?) of malicious participants are tolerated.

Indeed, we still need to rely on a CSPRNG in a deterministic and verifiable manner at the individual node level. Then, at the network level, we collect the slice of bytes of it published by nodes and hash them all to create a finalized random seed at some interval.

Details

The gist for such a CSPRNG: We use ed25519, aes-ctr, and PoH in some bizarre (or smart?) way.

First, good nodes vote to the randomness staking by generating a signed message with this construction: ed25519(aes-256-ctr(private session key, ctr), <PoH recent blockhash>, node's private key) and broadcasting it. Let's call this a randomness vote. (This announcement of random data still could be regarded as a vote because basically the node is declaring this as the correctly random, and waiting the outcome of voting as a mixture with other node's randoms)

ctr always must begin with 0, be monotonically incremented, be unique (no reuse of the same ctr), be singleton (no multiple votes in a single voting interval) as the PoH block hash progresses, any breach of it can easily be verified by anyone at individual cipher block level, thanks to the deterministic ed25519 and the PoH, and immediately results in slashing.

Also, ctr of 0 automatically starts a new randomness voting session for a node, and the session can be ended by publishing the private session key.

Only after ending the session, any lamports are rewarded. And at this stage, the entire session, in other words, the complete sequence of published cipher blocks can be proved that the node indeed generated cryptographically secure random numbers with previously announced parameters, also the verification process can be parallelized thanks to aes-ctr.

Also, a node must really keep the key a secret until ending the session. Any signed claim of a leaked key by others before ending results in slashing the node. After ending the session, any third-party nodes can do any wrongdoings pretendeing to be the node because the private key is now public, however, other nodes can't maliciously slash honest nodes thanks by the PoH. If they really do that, any such signed claim would be revealed that it's after or at the blockhash of the session ending event.

So each node can only control the 1-bit worth of entropy. In other words, vote now or later. Of course, a node can alternatively initiate as many as session, but that would require substantial staking much like normal PoS really to gain some meaningful manipulation power over the network.

At the side of the cluster, many randomness votes are collected. Validators must collect as much as randomness votes from the network and vote for it (heh, a bit confusing). The largest set wins. Then, filter the (sorted?) set of randomness votes through some kind of stake-weighted deterministic digest function to be used as a randomness seed for smart contracts.

So, at final, the random seed for the voting interval is determined; individual smart contract invocations can consume random data derived from PRNG(sha256(the finalized random seed, transaction signature)). This way we avoid identical random sequence is used across multiple transactions, that might cause some problems: Same random sequence should almost never appear again.

In computing resource wise, participating (encrypt and sign zeros at interval) and validating (parallelizable {en,de}cryption) should be cheap with AES-NI/CUDA/OpenCL.

Concerns

• Smart contracts must be explicit to use random and must pay to use randomness. Time is money, Space is money, so is random. :p
• To check past randomness voting, we must hold all randomness voting session parameters, and successful session termination or observed slashing incidents, that might be a problem.
• As much as PoS, censoring problem ensues?
• Is there any similar previous related works/ideas?
• No need the mixing of nodes' voting sessions? Just a single random sequence done by the leader at the moment is enough, aligning this randomness voting interval with the leader schedule?

Thanks for reading!

[ryoqun]

@garious @aeyakovenko Hi, recently I got interested in Solana. I'm very excited by the overall design philosophy/architecture.

After some researching, I came up this idea. Could you review this if you have some time? Thanks in advance!

[aeyakovenko]

@ryoqun a generalized random source on chain requires a simultaneous reveal, no party may know any bits prior to everyone knowing them, and withholding or re-ordering messages can’t change the outcome of the result.

https://nearprotocol.com/blog/randomness-in-blockchain-protocols/

[ryoqun]

@aeyakovenko Thanks for checking this and providing a pointer to me. That was very educational. So my idea is like now insecure naive RANDAO...

So, if I understand correctly, this part of my idea was not met with one of the requirements (withholding can't change the outcome of the result):

So each node can only control the 1-bit worth of entropy. In other words, vote now or later.

This part intrigued me. So after a bit of digging. I found this:

However, it has turned out that even this ability to introduce a 1-bit bias on a per-validator level can lead to very significant control when many validators collude. The simple RANDAO-based chain can in fact be completely taken over by 34% of the validators.

Also, such kind of colluding is a real threat because of this insight:

In practice, however, the gain for a malicious actor from biasing the randomness is unbounded whereas the penalty for aborting is bounded.

Along with the biasability, an attack called a late revealer attack is now mountable. To address that, a specially-constructed reveal step is necessary.

Surely, it seems random source is hard to implement correctly...

Anyway thank you very much! I'm closing this now that I know it won't work.