Subject: Re: [bitcoin-dev] We need to fix the block withholding attack

From: Peter Todd <[email-masked]>
Date: Sun, 20 Dec 2015 05:28:43 -0800

On Sun, Dec 20, 2015 at 12:12:49AM -0500, Emin Gün Sirer via bitcoin-dev wrote:
> There's quite a bit of confusion in this thread.
> 
> Peter is referring to block withholding attacks. Ittay Eyal (as sole
> author -- I was not involved in this paper [1]) was the first

Ah, thanks for the correction.

> to analyze these attacks and to discover a fascinating, paradoxical
> result. An attacker pool (A) can take a certain portion of its hashpower,
> use it to mine on behalf of victim pool (B), furnish partial proofs of work
> to B, but discard any full blocks it discovers. If A picks the amount of
> attacking hashpower judiciously, it can make more money using this
> attack, than it would if it were to use 100% of its hashpower for its own
> mining. This last sentence should sound non-sensical to most of you,
> at least, it did to me. Ittay did the math, and his paper can tell you
> exactly how much of your hashpower you need to peel off and use
> to attack another open pool, and you will come out ahead.

Now to be clear, I'm not saying any of the above isn't true - it's a
fascinating result. But the hashing/mining ecosystem is significantly
more complex than just pools.

> Back to Ittay's paradoxical discovery:
> 
> We have seen pool-block withholding attacks before; I believe Eligius
> caught one case. I don't believe that any miners will deploy strong KYC
> measures, and even if they did, I don't believe that these measures
> will be effective, at least, as long as the attacker is somewhat savvy.
> The problem with these attacks are that statistics favor the attackers.
> Is someone really discarding the blocks they find, or are they just
> unlucky? This is really hard to tell for small miners. Even with KYC,
> one could break up one's servers, register them under different
> people's names, and tunnel them through VPNs.

There are a number of techniques that can be used to detect block
withholding attacks that you are not aware of. These techniques usually
have the characteristic that if known they can be avoided, so obviously
those who know about them are highly reluctant to reveal what exactly
they are. I personally know about some of them and have been asked to
keep that information secret, which I will.

In the context of KYC, this techniques would likely hold up in court,
which means that if this stuff becomes a more serious problem it's
perfectly viable for large, well-resourced, pools to prevent block
withholding attacks, in part by removing anonymity of hashing power.
This would not be a positive development for the ecosystem.

Secondly, DRM tech can also easily be used to prevent block withholding
attacks by attesting to the honest of the hashing power. This is being
discussed in the industry, and again, this isn't a positive development
for the ecosystem.

> Keep in mind that when an open pool gets big, like GHash did and
> two other pools did before them, the only thing at our disposal used
> to be to yell at people about centralization until they left the big
> pools and reformed into smaller groups. Not only was such yelling
> kind of desperate looking, it wasn't incredibly effective, either.
> We had no protocol mechanisms that put pressure on big pools to
> stop signing up people. Ittay's discovery changed that: pools that
> get to be very big by indiscriminately signing up miners are likely to
> be infiltrated and their profitability will drop. And Peter's post is
> evidence that this is, indeed, happening as predicted. This is a
> good outcome, it puts pressure on the big pools to not grow.

GHash.io was not a pure pool - they owned and operated a significant
amount of physical hashing power, and it's not at all clear that their %
of the network actually went down following that 51% debacle.

Currently a significant % of the hashing power - possibly a majority -
is in the form of large hashing installations whose owners individually,
and definitely in trusting groups, have enough hashing power to solo
mine. Eyal's results indicate those miners have incentives to attack
pools, and additionally they have the incentive of killing off pools to
make it difficult for new competition to get established, yet they
themselves are not vulnerable to that attack.

Moving to a state where new hashing power can't be brought online except
in large quantities is not a positive development for the ecosystem.

This is also way I described the suggestion that Eyal's results are a
good thing as academic - while the idea hypothetically works in a pure
open pool vs. open pool scenario, the real world is significantly more
complex than that simple model.

> Peter, you allude to a specific suggestion from Luke-Jr. Can you
> please describe what it is?

Basically you have the pool pick a secret k for each share, and commit
to H(k) in the share. Additionally the share commits to a target divider
D. The PoW validity rule is then changed from H(block header) < T, to be
H(block header) < T * D && H(H(block header) + k) < max_int / D

Because the hasher doesn't know what k is, they don't know which shares
are valid blocks and thus can't selectively discard those shares.

-- 
'peter'[:-1]@petertodd.org
00000000000000000188b6321da7feae60d74c7b0becbdab3b1a0bd57f10947d