Fair, barely malleable CSPRNG that can still be deterministic?

Question

Just for fun, I wanted to start off making a test contract that generates ERC-20 tokens based off of prime length when in binary representation. I decided to use Rabin-Miller for the primality test, because it's cheap and I'm not trying to make a practical contract. The problem is I need to generate λ random uints, where λ is the security parameter/accuracy of test. Ethereum, being a Turing-complete dApp platform, needs all nodes to run and crunch the same exact numbers to get the same results (i.e. use EVM to output the same data). That means Solidity has no built in RNG that is deterministic.

I don't want to have the contract sender msg.sender to have to generate a random number for the contract to SHA-3. I would rather a solution that only requires submission of the integer to test primality in general. That would require deterministic computation alone.

Wouldn't this problem be solved if miners were also pitching in entropy to the blocks they mine as well as transactions and nonces, and the entropy from multiple blocks by different miners each be hashed, concatenated and hashed again? I think that would reduce entropy malleability to an acceptable amount.

I'm not a cryptographer, nor a programmer, but I just wonder why RNG is so hard to implement practically on Ethereum. I'm sure it's possible, but it hasn't been done yet because either:

1. No method has been found that could be implemented in a practical or secure sense.
2. A method was found, but it uses too much computation.
3. Implementation would require a chain fork.
4. A method can be implemented in contracts, but costs too much gas to use.
5. Something entirely different.

From the other questions, namely When can BLOCKHASH be safely used for a random number? When would it be unsafe? , attackers could refuse to broadcast blocks that are unfavorable (e.g. odds are against winning a lottery prize), and wait until they mine a block that is favorable to broadcast. If multiple, distinct miners, had their entropy sources combined and hashed, would random numbers be safer to use? Or would the miner simply use different accounts to cheat the system?

Answer 1

How can I securely generate a random number in my smart contract? should address your question. The problem mostly comes down to the ability for miners to discard blocks that don't favor them, as you stated. Even when multiple sources of entropy are used to evaluate to one random number per block, miners can still just inspect the one random number (no matter how much entropy was used to obtain it) and discard it if it is not what they want.

One answer states that https://github.com/randao/randao attempts to address this problem using some of the ideas that you posed. Another option is an oracle like random.org, but that would require trusting both random.org and the oracle service that you use.