Blockhash for Randomness vs Block Withholding Attack

[JPJA]

The Block Withholding Attack should NOT be a concern. Here’s why.

The Attack

A miner who finds a valid block can choose not to broadcast it. Say Alice is a miner and the block she just generated settles a dice roll. She wins if the coin lands on heads (H) but her newly discovered block landed on tails (T). She can broadcast this block, but then she’ll lose the coin flip. To have a chance of still winning the coin flip, she therefore better NOT broadcast the block.

The Probabilities

A fair coin has a 50/50 chance of H or T. It’s trivial to make any newly discovered blockhash determine a coin flip with these probabilities. However, with the Withholding Attack, Alice skews these probabilities. If she controls 10% of the hashing power, these are the possibilities:

• 45% some other miner finds a H block
• 45% some other miner finds a T block
• 5% Alice finds a H block, so she wins, and naturally broadcasts
• 5% Alice finds a T block which she withholds
• The block that does get broadcast has 50% of being H or 50% of being T

Summing the probabilities, we see 45% + 5% + another 2.5% chance of H.

That’s 52.5% for heads vs 47.5% for tails.

The probability of H is a tiny bit higher since Alice can do this twice, thrice, or more if she’s on a lucky streak. I’ll anyway round up to to 53% for the remaining calculations.

The Miner’s Economic Dilemma

If Alice withholds a block, she loses the block reward. Currently that’s 12.5 BTC + roughly 1.5 BTC in fees. That’s around $16,000.

Her potential upside by doing so is that’s she may win the coin flip. The probability is still only 50% so withholding a block is worthwhile only if she can win more than $32,000 (twice a block reward).

The Opponent’s Dilemma

Bob can take the other side of the coin flip. He’s not a miner and his probability of winning is 47%. Whether he wants to play despite the slightly unfair coin, depends on his risk preferences.

The Economic Outcome

Slightly skewed probabilities will be partially offset by slightly better odds for the non-miner side. In the case of Bob, the odds may settle so that he gets 2.05 XCP if he wins for each 1 XCP he bets.

Still, some players will be deferred from participating. This is called a dead weight loss, and it happens everywhere in the economy. When there’s VAT (sales tax) on a product, some consumers will not buy and some retails won’t stick around. The same with tax on labor. Employment participation would be higher without it. With used cars there’s information asymmetry between buyer and seller but people do buy used cars nevertheless.

The dead weight loss from the withholding attack is insignificant

The likely use of XCP betting is not so much coin flips, but rather lotteries where one side gets a high payout with a low probability and the other side a low payout with a high probability. The former group is traditional lottery players or gamblers. These are risk seekers. The other side will need to escrow/risk large sums of XCP for a potential small gain. It’s likely these will be professionals who demand a positive expected return, i.e. they are risk averse.

The exact odds are set by these two groups interacting.

A common ground, an equilibrium, will be found. Remember that traditional lotteries have very low payouts. Isn’t less than 50% normal? Yet it’s a billion dollar industry.

Miner manipulation is a minuscule problem that may occur only after tens of thousands of USD worth are played in a single bet.

Another point - even if XCP betting reaches this level, and people do start worrying about this, they will simply spread their bets out on several blocks, so each one remains too small for profitable manipulation.

---

Timestamp Manipulation

A related attack, with a simple solution, can happen if the oracle broadcasts the block’s timestamp. I’ll not go into details but the miner can basically set his timestamp ahead of real time (up to two hours is allowed), giving him more than 10x higher chances of doing a withholding attack. Still it’s only profitable if the sums involved are in the tens of thousands of USD.

But the solution is simple. The oracle is free to set whatever timestamp he pleases, so the automated XCP oracle should look at the previous block’s timestamp, not the last one where he gets randomness from.

[deweller]

You are correct that the miner would be throwing away resources to affect the outcome. But any attack vector, even a small one, makes me hesitant to include it as part of the core protocol.

I can’t think of a way of completely mitigating a withholding or timestamp attack.

[JPJA]

I researched it further and

• nya, a withholding attack seems impossible to theoretically mitigate but players can easily avoid it
• no, a timestamp attack is not possible

The withholding attack has been discussed extensively by Ethereum devs. For their games too, it would have been desirable to use block hash for entropy. However, it always boils down to one final block determining the outcome, even if several blocks are used.

Some other solutions were suggested, but I won’t go into those here. They easily become a web of incentives - that may or may not work - but in any way require heck a lot of coding and possible bugs.

Counterparty has one enormous advantage over Ethereum though. It costs 5 eth to withhold a block. Therefore an attack is cheap and likely to occur with Ethereum. With Bitcoin’s much more valuable blocks this attack is very expensive.

This puts us in a unique position where we can offer lotteries and no one else can.

And even if a game does become large enough for miner manipulation to be worthwhile,they can only skew the probabilities somewhat, which is a possibility that everyone involved knows about. If they don’t mind this, fine, the game goes on. But if they do mind, people will choose to play on several smaller games rather than a few very large ones. This solves the attack vector, if worth solving.

---

Regarding time attack. The oracle should first look for a block with a timestamp above the trigger time, then wait for the next block to decide the outcome. No miner will gain anything from altering the timestamp.

[JPJA]

Just realized there is a way the protocol can detect withholding attacks. The oracle can (temporarily) stop broadcasting and refund open bets when this occurs.

HOWEVER it’s a statistical approach, and it won’t detect the first few withholding attacks.

The time between two blocks is expected to be ten minutes. As you know, it’s rarely exactly ten minutes but the variability in block time follows a known distribution. So if you measure a lot of blocks you’ll discover they follow very closely to the theoretical distribution and the average is close to ten minutes.

If bet settlement blocks take longer than ten minutes on average then a withholding attack is likely taking place. Exactly how likely the true cause is indeed an attack (not normal variability) can be determined by maths. It’s a bit complicated - university statistics curriculum - but such of calculations are often used in econometrics (decisions under uncertainty). Our calculations can conclude (e.g. with 95% confidence) that an attack takes place.

---

P.S. To model this, think of two kinds of miners - honest and dishonest. The dishonest one is the one that will withhold blocks if it’s in his interest to do so. The above mentioned approach opens a new secondary attack. In cases where he finds a block but it’s in his interest to publish it (since he wins the bet) he can alter the timestamp. He can also alter the timestamp on the one block prior to bet settlement. But this can all be circumvented by looking at the median - not the average - since the dishonest miner will be a minority. The devil’s advocate may ask what if he is the majority? But then Bitcoin will have problems so large that this is the least of our concern.

---

P.S.2. I don’t recommend going this route at all. Even if the maths and theory makes it doable, I don’t think it’s worthwhile to do these calculations. It adds complexity. In previous posts I argued why a witholding attack IMO isn’t an issue we should focus on.

[JPJA]

Here’s a more thorough analysis of a miner attack.

Let’s illustrate the probabilities:

There’s a 97% chance another miner finds the block, multiplied with a 1/4 chance it’s a winning block. Likewise the miner has a 3% chance of finding the block and then there’s another 1/4 chance it is a winning block.

However, if he does find a block and it’s a loser, an honest miner would broadcast it and get zero payout. Instead, an attacking miner sees an opportunity to withhold this block and so the tree replicates at this point. Then again there’s a slight chance the same repeats. Mathematically, the expected payout can be formulated as an infinite geometric series.

I made a table in excel to show the attacking miner’s profitability.

The selected cell shows a miner with a 2% share who places a 25 XCP wager at neutral odds at winning 100 XCP, but with a 3% fee on the payout, so it’s total 97 XCP. He has a slightly negative expected profit on this bet, even though a withholding attack is taken into account.

To understand what I mean by profit, consider the 100% column. In this hypothetical scenario the miner controls all the hashing power. He can withhold blocks until he finds one where he wins, thus he’s guaranteed to win. Since the payout after fee is 97 XCP and he wagered 25 XCP, his profit is 72 XCP.

A more realistic example is maybe a large 16% pool performing the attack. It turns out a 50/50 coin flip bet is the most lucrative. From 100 XCP at stake (50 of his own, 50 counterwager) he expects to earn 2.72 XCP.

Now take into account the opportunity cost. By withholding a block he loses (at the moment) roughly $30,000. He needs to expect to profit at least this amount on the lottery, else a withholding attack does not make sense.

Since he only profits an expected 2.72 XCP per 100 XCP at stake, the lottery must be worth at least $1.1 mlin, of which $550,000 worth of XCP is wagered by himself.

With a lower oracle fee, the threshold for a withholding attack is reduced somewhat - but not dramatically.

Even with no fee the 16% miner needs $690.000 at play on a coin flip to do a withholding attack.

[JPJA]

Darn, in above calculations I made one unfortunate assumption. Doesn’t change the conclusion though, just good to keep in mind:

When the oracle takes a fee, say 3%, and the sum of wager+counterwager is 100 XCP, then the payout is 97. How shall this 3 XCP fee be divided between the two players? In table above it’s divided proportionally, e.g. in a 1/1024 bet the counterwager is almost 100 but this does not make sense. The payout is 97 XCP! One can adjust for this but then the player with a 1/1024 chance of winning gets terrible odds.

Here’s the game size required in USD for a withholding attack to be feasible. Fee set at 0.1%

Empty cell means attack is not lucrative no matter the game size. Practically speaking, an attack is always prohibitively expensive.

Feel free to review calculations. I cannot upload the excel file here but PM me and I’ll mail it to you.