path: root/cf/24559a2453cd7257b21cc55ef0d0f7c72960a9

Return-Path: <elombrozo@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 2741A1145
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 26 Dec 2015 08:23:46 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pf0-f173.google.com (mail-pf0-f173.google.com
	[209.85.192.173])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 72AB789
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 26 Dec 2015 08:23:45 +0000 (UTC)
Received: by mail-pf0-f173.google.com with SMTP id 78so87242290pfw.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat, 26 Dec 2015 00:23:45 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=from:to:subject:cc:date:message-id:in-reply-to:reply-to:user-agent
	:mime-version:content-type;
	bh=Z5K+QnKwaN+qdCVuY94auqzvL38aHGO6Vhx3NzQJWRU=;
	b=R8ho4dZAY6JAOqzcn68O1/vFS1yAP7gHOwCdirrTxhO/5Nq0eD4+8DBaI6yCCXA+Ms
	McIU+vMdjZwmiebsCU95gqksMLA87dGhRkBJsSgS3F72tbur2NQuEceAjJcJ7Hig5MUd
	tdZEb2TsUOpYuWxHzxw5PH5dO+dFoGFxO2vAXgpusgjUrYqtlVL3qf3/gzQspDbds60I
	3OOt1PiELp8EXJzc6uCyV3rEUFKGJxVQODrr4Ox631TxxL7uzyrLxAXhRl9nnepYtK34
	kR8wTkt/FoTiS2Bx17CPUq2JcVFFc+pPyIuiVjvxLFvTnGK4OruMKZ79cHn4AYaRdmkL
	cnOQ==
X-Received: by 10.98.89.210 with SMTP id k79mr42278380pfj.45.1451118225203;
	Sat, 26 Dec 2015 00:23:45 -0800 (PST)
Received: from [192.168.1.108] (cpe-76-167-237-202.san.res.rr.com.
	[76.167.237.202]) by smtp.gmail.com with ESMTPSA id
	mj1sm68618853pab.34.2015.12.26.00.23.44
	(version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128);
	Sat, 26 Dec 2015 00:23:44 -0800 (PST)
From: "Eric Lombrozo" <elombrozo@gmail.com>
To: "Peter Todd" <pete@petertodd.org>, =?utf-8?q?Emin=20G=c3=bcn=20Sirer?=
	<el33th4x0r@gmail.com>
Date: Sat, 26 Dec 2015 08:23:38 +0000
Message-Id: <ema8a70574-c28e-4c43-a1e3-5f2f4df7d3a2@platinum>
In-Reply-To: <20151220132842.GA25481@muck>
Reply-To: "Eric Lombrozo" <elombrozo@gmail.com>
User-Agent: eM_Client/6.0.23181.0
Mime-Version: 1.0
Content-Type: multipart/alternative;
	boundary="------=_MB37047242-D767-40D1-B083-6B0B57E9FB78"
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW
	autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>, nbvfour@gmail.com
Subject: Re: [bitcoin-dev] We need to fix the block withholding attack
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 26 Dec 2015 08:23:46 -0000


--------=_MB37047242-D767-40D1-B083-6B0B57E9FB78
Content-Type: text/plain; format=flowed; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Peter Todd wrote:
  Fixing block withholding is relatively simple, but (so far) requires a
SPV-visible hardfork. (Luke-Jr's two-stage target mechanism) We should
do this hard-fork in conjunction with any blocksize increase, which will
have the desirable side effect of clearly show consent by the entire
ecosystem, SPV clients included.

I think we can generalize this and argue that it is impossible fix this=20
without reducing the visible difficulty and blinding the hasher to an=20
invisible difficulty. Unfortunately, changing the retargeting algo to=20
compute lower visible difficulty (leaving all else the same) or=20
interpreting the bits field in a way that yields a lower visible=20
difficulty is a hard fork by definition - blocks that didn't meet the=20
visible difficulty requirement before will now meet it.

jl2012 wrote:
>After the meeting I find a softfork solution. It is very inefficient=20
>and I am leaving it here just for record.
>
>1. In the first output of the second transaction of a block, mining=20
>pool will commit a random nonce with an OP_RETURN.
>
>2. Mine as normal. When a block is found, the hash is concatenated with=
=20
>the committed random nonce and hashed.
>
>3. The resulting hash must be smaller than 2 ^ (256 - 1/64) or the=20
>block is invalid. That means about 1% of blocks are discarded.
>
>4. For each difficulty retarget, the secondary target is decreased by 2=
=20
>^ 1/64.
>
>5. After 546096 blocks or 10 years, the secondary target becomes 2 ^=20
>252. Therefore only 1 in 16 hash returned by hasher is really valid.=20
>This should make the detection of block withholding attack much easier.
>
>All miners have to sacrifice 1% reward for 10 years. Confirmation will=20
>also be 1% slower than it should be.
>
>If a node (full or SPV) is not updated, it becomes more vulnerable as=20
>an attacker could mine a chain much faster without following the new=20
>rules. But this is still a softfork, by definition.
jl2012's key discovery here is that if we add an invisible difficulty=20
while keeping the retarget algo and bits semantics the same, the visible=
=20
difficulty will decrease automatically to compensate. In other words, we=
=20
can artificially increase the block time interval, allowing us to force=20
a lower visible difficulty at the next retarget without changing the=20
retarget algo nor the bits semantics. There are no other free parameters=
=20
we can tweak, so it seems this is really the best we can do.

Unfortunately, this also means longer confirmation times, lower=20
throughput, and lower miner revenue. Note, however, that confirmations=20
would (on average) represent more PoW, so fewer confirmations would be=20
required to achieve the same level of security.

We can compensate for lower throughput and lower miner revenue by=20
increasing block size and increasing block rewards. Interestingly, it=20
turns out we *can* do these things with soft forks by embedding new=20
structures into blocks and nesting their hash trees into existing=20
structures. Ideas such as extension blocks=20
[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-May/008356.ht=
ml]=20
have been proposed before...but they add significant complications to=20
the protocol and require nontrivial app migration efforts. Old nodes=20
would not get forked off the network but backwards compatibility would=20
still be a problem as they would not be able to see at least some of the=
=20
transactions and some of the bitcoins in blocks. But if we're willing to=
=20
accept this, even the "sacred" 21 million asymptotic limit can be raised=
=20
via soft fork!

So in conclusion, it *is* possible to fix this attack with a soft fork=20
and without altering the basic economics...but it's almost surely a lot=20
more trouble than it's worth. Luke-Jr's solution is far simpler and more=
=20
elegant and is perhaps one of the few examples of a new feature (as=20
opposed to merely a structure cleanup) that would be better to deploy as=
=20
a hard fork since it's simple to implement and seems to stand a=20
reasonable chance of near universal support...and soft fork alternatives=
=20
are very, very ugly and significantly impact system usability...and I=20
think theory tells us we can't do any better.

- Eric
--------=_MB37047242-D767-40D1-B083-6B0B57E9FB78
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

<HTML><HEAD>
<STYLE id=3DeMClientCss>BLOCKQUOTE.cite {
	PADDING-LEFT: 10px; MARGIN-LEFT: 5px; BORDER-LEFT: #cccccc 1px solid; PADD=
ING-RIGHT: 0px; MARGIN-RIGHT: 0px
}
BLOCKQUOTE.cite2 {
	PADDING-TOP: 0px; PADDING-LEFT: 10px; MARGIN-LEFT: 5px; BORDER-LEFT: #cccc=
cc 1px solid; MARGIN-TOP: 3px; PADDING-RIGHT: 0px; MARGIN-RIGHT: 0px
}
.plain PRE {
	FONT-SIZE: 100%; FONT-FAMILY: monospace; WHITE-SPACE: pre-wrap; FONT-WEIGH=
T: normal; FONT-STYLE: normal
}
.plain TT {
	FONT-SIZE: 100%; FONT-FAMILY: monospace; WHITE-SPACE: pre-wrap; FONT-WEIGH=
T: normal; FONT-STYLE: normal
}
A IMG {
	BORDER-LEFT-WIDTH: 0px; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px;=
 BORDER-TOP-WIDTH: 0px
}
#x1c2fb1324db1464cb9ece942bf916590 {
	FONT-SIZE: 12pt; FONT-FAMILY: Tahoma
}
#x2e2ab106f7c24bab8de993a2b4c236d1 {
	FONT-SIZE: 12pt; FONT-FAMILY: Tahoma
}
.plain PRE {
	FONT-SIZE: 12pt; FONT-FAMILY: Tahoma
}
.plain TT {
	FONT-SIZE: 12pt; FONT-FAMILY: Tahoma
}
BODY {
	FONT-SIZE: 12pt; FONT-FAMILY: Tahoma
}
</STYLE>

<STYLE></STYLE>

<META content=3Dtext/html;charset=3Dutf-8 http-equiv=3DContent-Type></HEAD>
<BODY scroll=3Dauto class>
<DIV>Peter Todd wrote:<TT><FONT face=3DTahoma><SPAN id=3Dx2e2ab106f7c24bab8=
de993a2b4c236d1></DIV>
<DIV id=3Dx8655a99ab33b49b1842b20e56535579c class=3Dplain><FONT face=3DTaho=
ma><SPAN id=3Dx2e2ab106f7c24bab8de993a2b4c236d1><FONT face=3DTahoma><SPAN=
 id=3Dx2e2ab106f7c24bab8de993a2b4c236d1>
<BLOCKQUOTE class=3Dcite2 cite=3D20151219184240.GB12893@muck type=3D"cite">=
<TT>
<DIV></TT></SPAN></FONT>&nbsp;Fixing block withholding is relatively simple=
, but (so far) requires a<BR>SPV-visible hardfork. (Luke-Jr's two-stage =
target mechanism) We should<BR>do this hard-fork in conjunction with any=
 blocksize increase, which will<BR>have the desirable side effect of clearl=
y show consent by the entire<BR>ecosystem, SPV clients included.<BR>&nbsp;<=
/DIV></BLOCKQUOTE>
<DIV>I think we can&nbsp;generalize this and&nbsp;argue that it is impossib=
le fix this without reducing the visible difficulty and blinding the hasher=
 to an invisible difficulty. Unfortunately, changing the retargeting algo=
 to compute lower visible difficulty (leaving all else the same) or interpr=
eting the bits field in a way that yields a lower visible difficulty is =
a hard fork by definition - blocks that didn't meet the visible difficulty=
 requirement before will now meet it.</DIV>
<DIV>&nbsp;</DIV>
<DIV>jl2012 wrote:</DIV>
<DIV><SPAN id=3Dx1c2fb1324db1464cb9ece942bf916590>
<DIV></DIV>
<DIV id=3Dxfe6bba3c1777466e8e850bd3afb30a4c>
<BLOCKQUOTE class=3Dcite2 type=3D"cite">
<DIV>After the meeting I find a softfork solution. It is very inefficient=
 and I am leaving it here just for record.</DIV>
<DIV>&nbsp;</DIV>
<DIV>1. In the first output of the second transaction of a block, mining=
 pool will commit a random nonce with an OP_RETURN.</DIV>
<DIV>&nbsp;</DIV>
<DIV>2. Mine as normal. When a block is found, the hash is concatenated =
with the committed random nonce and hashed.</DIV>
<DIV>&nbsp;</DIV>
<DIV>3. The resulting hash must be smaller than 2 ^ (256 - 1/64) or the =
block is invalid. That means about 1% of blocks are discarded.</DIV>
<DIV>&nbsp;</DIV>
<DIV>4. For each difficulty retarget, the secondary target is decreased =
by 2 ^ 1/64.</DIV>
<DIV>&nbsp;</DIV>
<DIV>5. After 546096 blocks or 10 years, the secondary target becomes 2 =
^ 252. Therefore only 1 in 16 hash returned by hasher is really valid. This=
 should make the detection of block withholding attack much easier.</DIV>
<DIV>&nbsp;</DIV>
<DIV>All miners have to sacrifice 1% reward for 10 years. Confirmation will=
 also be 1% slower than it should be.</DIV>
<DIV>&nbsp;</DIV>
<DIV>If a node (full or SPV) is not updated, it becomes more vulnerable =
as an attacker could mine a chain much faster without following the new =
rules. But this is still a softfork, by definition.</DIV></BLOCKQUOTE>
<DIV>jl2012's key discovery here is that if we add an invisible difficulty=
 while keeping the retarget algo and bits semantics the same, the visible=
 difficulty will decrease automatically to compensate. In other words, we=
 can artificially increase the block time interval, allowing us to force=
 a lower visible difficulty at the next retarget without changing the retar=
get algo nor the bits semantics. There are no other free parameters we can=
 tweak, so it seems this is really the best we can do.</DIV>
<DIV>&nbsp;</DIV>
<DIV>Unfortunately, this also means longer confirmation times, lower throug=
hput, and lower miner revenue. Note, however, that confirmations would (on=
 average) represent more PoW, so fewer confirmations would be required to=
 achieve the same level of security.</DIV>
<DIV>&nbsp;</DIV>
<DIV>We can compensate for lower throughput and lower miner revenue by incr=
easing block size and increasing block rewards. Interestingly, it turns =
out we *can* do these things with soft forks by embedding new structures=
 into blocks and nesting their hash trees into existing structures. Ideas=
 such as extension blocks [https://lists.linuxfoundation.org/pipermail/bitc=
oin-dev/2015-May/008356.html] have been proposed before...but&nbsp;they =
add&nbsp;significant complications to the protocol and require nontrivial=
 app migration&nbsp;efforts.&nbsp;Old nodes would not get forked off the=
 network but backwards compatibility would still be a problem as they would=
 not be able to see at least some of the transactions and some of the bitco=
ins in blocks. But if we're willing to accept this, even the "sacred" 21=
 million asymptotic limit can be raised via soft fork!</DIV>
<DIV>&nbsp;</DIV>
<DIV>So in conclusion, it *is* possible to fix this attack with a soft fork=
 and without altering the basic economics...but it's almost surely a lot=
 more trouble than it's worth. Luke-Jr's solution is far simpler and more=
 elegant and is perhaps one of the few examples of a new feature (as oppose=
d to merely a structure cleanup) that would be better to deploy as a hard=
 fork since it's simple to implement and seems to stand a reasonable chance=
 of near universal support...and soft fork alternatives are very, very&nbsp=
;ugly and significantly impact system usability...and I think theory tells=
 us we can't do any better.</DIV>
<DIV>&nbsp;</DIV>
<DIV>- Eric</DIV></DIV></SPAN></SPAN></FONT></SPAN></FONT></DIV></DIV></TT>=
</BODY></HTML>
--------=_MB37047242-D767-40D1-B083-6B0B57E9FB78--