Quote from: gmaxwell on June 08, 2019, 11:43:26 PM

Quote from: RHavar on June 08, 2019, 10:05:01 PM

That made it pretty impractical to manipulate the lotto (after finding a block, a miner would have to wait 20 minutes to check if it was good or not), unless the miner was prepared/able to 51% attack bitcoin at the same time Tongue

The naive way of constructing this makes it then take 20 minutes computation to verify, which isn't that attractive if you imagine the verifier is some lame mobile client and the attacker is a mining farm.

Fortunately you can use a verifiable delay function.

Quote

Quote from: ETFbitcoin on June 08, 2019, 05:04:33 PM

2. Use many blocks in a sequence as entropy source since it's difficult to manipulate n blocks in a sequence.

How does that work? If you get n blocks in a sequence -- the result is always going to be influenced by the last block in the sequence, who would be able to perform the same sort of attacks as if you just had used that 1 block.

I keep seeing people propose this an their proposals always turn out to be totally broken, but in fact there is a way to do this that I call tapering.

Step 1. A block is 3xVDFed to pick a random value.
Step 2. The next block is 2xVDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 3. The next block is VDFed to pick a single bit: if it's one, go back to step 1 for the next block.
Step 4. The last step 1 outcome is accepted.

This will terminate in a couple steps on average.

You can make all kinds of variations on this, e.g. start the reset probability high and slope it down. But the general idea is that while single block may be biased, multiple blocks are at least somewhat mutually independent. Effort you spend grinding out a low block in step 1 is likely to get discarded by step 2/3 resets... but all can do is accept or reset the process, so those blocks doesn't have much influence on the outcome.

I'm sure effort that has gone into research on "randomness extractors" could be used to generalize this to achieve a guaranteed worst case bias achievable under useful assumptions- Essentially that work is trying to address this problem: You have a function with multiple inputs, the attack has control over some not all of them, can observe at least some of the ones he can't control, and you don't know what inputs are attacker controlled/observed... what function allows you to extract the most uniform number, in spite of the attackers efforts, and how far from uniform can the attacker make it?

Unfortunately, almost all randomness extractor work is highly theoretical, non-constructive, and nearly incomprehensible to me... so I can't even tell if any of the existing approaches is applicable.

In any case, if large amounts of bias is needed by the attacker, I think these techniques can make achieving it much more costly.

Tapering works nice with VDFs, since you can attempt to make the time that the random value will be known long after the decision to use it or not needs to be made.

Another hardening approach you can use that I've described before is bonding:

Block X pays a bitcoin to pubkey A.
Block X+1 picks a random value.
Some expensive work function operates on the random value using the private key for pubkey A.
Block >X+10 spend A's coins off to someplace else.

Now: to rig the random value the miner and the private key holder for A must collude. "A" can't influence the outcome at all (except say by just never releasing the private key), but the miner cannot grind without their help. Why a bitcoin and privatekey instead of just a hash commitment in A's transaction? So that if A tells the miner(s) the secret before X+2, the miners could just steal the coins instead of helping A's randomness.

Another hardening approach you can use that I've described before is multiparty verifiable oracles:

BLS signatures are completely deterministic the signature of message X is always S. BLS signatures can also easily support N of M threshold signing. So you have published N of M BLS threshold public key... to produce a final random value, you have a transaction (or OTS timestamp) commit to your BLS pubkey, then get a blockchain produced random value from a later block and sign it. The signature is your final random result.

Now creation of a biased random result requires a collusion of N parties plus the miner, jamming release of the random value requires >M-N parties to fail.

Can you come up with new formulas that replace my formulas, my formula is only effective when dealing with 2 people?