[RoboTeddy]

Can imagine a protocol for generating randomness to some arbitrary security level (at the expense of locking up security deposits):

(1) Anyone can decide to become a 'randomness provider' by putting up a large security depsoit

(2) Every epoch (some number of blocks), each provider chooses a private random number and commits to it by publishing its hash

(3) During the next epoch but, each provider publishes the random they committed to earlier.

(4) xor together all the random values. The result is a pseudorandom number everyone can agree on, and which should be sufficiently good for many applications include PoS selection

If any provider fails to publish the random number they committed to, they lose their security deposit and there is no random value provided for the associated epoch. The process starts over.

If you're worried about bribing attacks over all providers, recognize that all we need is a single altruistic provider to keep the system safe. Altruistic behavior may be rare compared to selfish behavior, but I think we can usually rely on its nonzero presence.

If you're still really worried that collusion could be going on amongst ALL randomness providers, just become a provider yourself.

It's possible for a provider to wait for all other providers to reveal their values, and then privately determine whether or not the final random value would be favorable to them; they then have the option of canceling the epoch by keeping their private value hidden and losing their security deposit. This option (in combination with a particular application, and the size of the security deposit of providers) puts a bound on what the random value can be safely used for (e.g., if it's for a lottery, the expected value of another truly random swing at the jackpot has to be lower than the value of a security deposit).

[konschubert]

> If you're worried about bribing attacks over all providers, recognize that all we need is a single altruistic provider to keep the system safe. Altruistic behavior may be rare compared to selfish behavior, but I think we can usually rely on its nonzero presence.

You also need to be sure that the others don't ignore the single altruistic source.

In a byzantine system, you can't distinguish if somebody is offline or if the others are silencing him.

[RoboTeddy]

> You also need to be sure that the others don't ignore the single altruistic source.

Well sure, but the code people run listens to all the providers. Everyone is listened to automatically. That's part of the social consensus encoded in software. If you don't follow along, you end up on your own fork. That's how these systems work — e.g, you also need to make sure that people don't "ignore" the consequences of failed hash checks throughout a cryptocurrency codebase.

It would be quite possible to run your provider on a machine hidden somewhere, and inject your transactions to nodes at random points in the network. It'd be pretty tough to silence someone directly.

Miner censorship attacks, e.g. a 51% attack, are also possible (i.e., all miners, or a sufficient majority, refuse to mine your tx until the epoch ends). This kind of censorship threat is always present for all kinds of transactions; in theory they're particularly pernicious for protocols like this one that require a tx to be submitted by a deadline. But no one is claiming that these systems are completely invulnerable to a misbehaving majority of miners or validators.

[caf]

I don't see any incentive to actually publish random values - wouldn't it be easier to just commit to and publish zero every time?

[RoboTeddy]

Altruism probably works here. It's cheap to pick a pseudorandom value. But if you didn't want to rely on altruism, the system could offer a reward to anyone who reveals the secret someone committed to early (half that provider's security deposit could be destroyed; the other half given over in reward to the reporter).

[barbegal]

That's all well and good but who manages the security deposit?

[RoboTeddy]

The system itself, e.g. the code of a smart contract. Example implementation: https://github.com/randao/randao

[barbegal]

So the randomness providers secure the deposit of their own randomness. The circularity of the system means it won't work in practice. RANDAO is secured by the proof of work miners.

[RoboTeddy]

Actually, this kind of "snake eating its own tail" loop is exactly how cryptocurrencies operate. For example, proof of work blockchains secure themselves by creating mining incentives with money that has value because it is secure.

It works because the system can regress over time, e.g. value at t=n can be used to secure a greater amount of value at t=n+1. (Although value needn't be strictly increasing for system to operate; if value decreases, so do the security requirements)