Date: Sun, 20 Dec 2015 05:28:43 -0800
From: Peter Todd <pete@petertodd.org>
To: Emin =?iso-8859-1?B?R/xu?= Sirer <el33th4x0r@gmail.com>
Message-ID: <20151220132842.GA25481@muck>
References: <20151219184240.GB12893@muck>
	<CAAcC9yvh2ma2dFhNDEKs7vfXyQF9L+T0YtRvOsJ15AbfVti=cw@mail.gmail.com>
	<219f125cee6ca68fd27016642e38fdf1@xbt.hk>
	<CAAcC9ys_t7X0WpQ8W3577M8GLiA5sPV2F1BJ9qZbnMkE-1j3+Q@mail.gmail.com>
	<aff8da46a69bdd7ef92ca87725866a5c@xbt.hk>
	<CAPkFh0vNECi1OmBwki+8NNAQbe6EG2FEE4RR5z=kYVLLDFHUXg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="k1lZvvs/B4yU6o8G"
Content-Disposition: inline
In-Reply-To: <CAPkFh0vNECi1OmBwki+8NNAQbe6EG2FEE4RR5z=kYVLLDFHUXg@mail.gmail.com>
Cc: nbvfour@gmail.com, Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] We need to fix the block withholding attack
Precedence: list


--k1lZvvs/B4yU6o8G
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sun, Dec 20, 2015 at 12:12:49AM -0500, Emin G=FCn Sirer via bitcoin-dev =
wrote:
> There's quite a bit of confusion in this thread.
>=20
> 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 wo=
rk
> 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:
>=20
> 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.

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

--k1lZvvs/B4yU6o8G
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQGrBAEBCACVBQJWdq0HXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDAwMTg4YjYzMjFkYTdmZWFlNjBkNzRjN2IwYmVjYmRhYjNi
MWEwYmQ1N2YxMDk0N2QvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQwIXyHOf0udwKUAf/Z5c7+UmZjfyKtQ1HV/zqkECx
wguR5s6oiiWA+3NjYFqVEfirU45DNWdy8nxNfejCy5C9K7XtTwM9+sEcC7Opf0Zd
c49N/6DGWLl6KQD/ntIHPcK1ykBDuDdioAb3eE9R0PXdOjcDi9tXVlVeLaEeLq7a
ThsNrcqEfHYmFfrNtE5HVk4RIYfo0kI57toKd0S/2kDrvrNhY4QDEHEndQhW+BZ3
vKotqMSm+Y+78D97/GFuMoilTnbKygepsbSkxqAwQwoAwot/Sxk0O05irpVPWfO9
aQWFY+I7WVlJgeN4/zADFwZaEN1+UcLCofvPzXA6CwSl2fhI6aGKHOcnCNaAtw==
=1qD0
-----END PGP SIGNATURE-----

--k1lZvvs/B4yU6o8G--