Why not just have everyone generate a random string and hash it N times (where N is like 1 million), and then publicly commit to that hash?
Then you can have any subset of your network generate a random number together by each one revealing the previous hash, and then combining them. You can use those resulting hashes as seeds for some random number generation.
This technique can also be used for many other things, including HOTP (hash based one time passwords), discovery of friends based on hashed phone numbers, etc. but if you want to generate random numbers without worrying about entropy and anyone able to predict the next number, just use this.
You need to kind of gossip and aggregate the commitments X. And each time the nodes reveal the previous input X_n = hash^(-1) (X), you have to verify that hash^N(X_n) = X, and then use that to generate your random keys.
The only snag here is knowing which nodes get to provide the input. Because some nodes may be offline, and some may not be. It’s best if the random number is a function of what nodes are in the set. And after a while you stop listening to new X_n and you broadcast the ones you heard, so everyone can sort of find a union of all those nodes, and use that as the seed for the next random number.
Since Ethereum already has a special “baton” it passes around, to the miner who solves PoW, or some special nodes found with PoS, then you can just have THOSE nodes collect the random numbers from some set R of other nodes, signed by those nodes, and publish this combination as the random number. The only thing is you have to somehow be sure R is not completely under the control of the miner to select, otherwise they’ll have control of that random number. This is the tough part, because whatever criteria you choose, it has to be flexible enough for R to contain at least a few nodes. But it can’t be so flexible that the miner can eventually select their favorite group R and collude.
In fact you can probably replace Kademlia with just a global routing table (add whoever joins into a giant table) and use these random numbers to select the group of computers is going to be doing consensus about a certain thing. As the random numbers change (similar to a HOTP) you migrate the shard to the new consensus group.
(That’s an alternative routing system we’re building at intercoin.org, alternative to Kademlia, because it’s faster. But less private, because you have to know everyone’s IP address, so a malicious adversary can DDOS all the nodes. And yes, some countries would probably do that. So this alternative routing system would only really be good for private blockchains.)