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:26:54 +0000
Message-Id: <em3b7f52a1-0627-432f-9c18-3c3381fdda25@platinum>
In-Reply-To: <ema8a70574-c28e-4c43-a1e3-5f2f4df7d3a2@platinum>
Reply-To: "Eric Lombrozo" <elombrozo@gmail.com>
User-Agent: eM_Client/6.0.23181.0
Mime-Version: 1.0
Content-Type: multipart/alternative;
	boundary="------=_MB6AF2FC99-758F-4AE8-BBFB-E6DFE6FDE234"
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>, nbvfour@gmail.com
Subject: Re: [bitcoin-dev] We need to fix the block withholding attack
Precedence: list


--------=_MB6AF2FC99-758F-4AE8-BBFB-E6DFE6FDE234
Content-Type: text/plain; format=flowed; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Note: my stupid email client didn't indent Peter Todd's quote correctly.=
=20
The first paragraph is his, the second is my response.

------ Original Message ------
From: "Eric Lombrozo" <elombrozo@gmail.com>
To: "Peter Todd" <pete@petertodd.org>; "Emin G=C3=BCn Sirer"=20
<el33th4x0r@gmail.com>
Cc: nbvfour@gmail.com; "Bitcoin Dev"=20
<bitcoin-dev@lists.linuxfoundation.org>
Sent: 12/26/2015 12:23:38 AM
Subject: Re[2]: [bitcoin-dev] We need to fix the block withholding=20
attack

>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=20
>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=20
>>with 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=20
>>2 ^ 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=20
>>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=20
>visible difficulty will decrease automatically to compensate. In other=20
>words, we can artificially increase the block time interval, allowing=20
>us to force a lower visible difficulty at the next retarget without=20
>changing the retarget algo nor the bits semantics. There are no other=20
>free parameters we can tweak, so it seems this is really the best we=20
>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.h=
tml]=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=20
>the transactions and some of the bitcoins in blocks. But if we're=20
>willing to accept this, even the "sacred" 21 million asymptotic limit=20
>can be raised 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=20
>more elegant and is perhaps one of the few examples of a new feature=20
>(as opposed to merely a structure cleanup) that would be better to=20
>deploy as a hard fork since it's simple to implement and seems to stand=
=20
>a reasonable chance of near universal support...and soft fork=20
>alternatives are very, very ugly and significantly impact system=20
>usability...and I think theory tells us we can't do any better.
>
>- Eric
--------=_MB6AF2FC99-758F-4AE8-BBFB-E6DFE6FDE234
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: quoted-printable

<HTML><HEAD>
<STYLE id=3DeMClientCss>blockquote.cite { margin-left: 5px; margin-right:=
 0px; padding-left: 10px; padding-right:0px; border-left: 1px solid #cccccc=
 }
blockquote.cite2 {margin-left: 5px; margin-right: 0px; padding-left: 10px;=
 padding-right:0px; border-left: 1px solid #cccccc; margin-top: 3px; paddin=
g-top: 0px; }
.plain pre, .plain tt { font-family: monospace; font-size: 100%; font-weigh=
t: normal; font-style: normal; white-space: pre-wrap; }
a img { border: 0px; }body {font-family: Tahoma;font-size: 12pt;}
.plain pre, .plain tt {font-family: Tahoma;font-size: 12pt;}
</STYLE>

<STYLE>#x7e6927bc026f4b879e57ab6cb48f8a21 BLOCKQUOTE.cite
{PADDING-LEFT: 10px; MARGIN-LEFT: 5px; BORDER-LEFT: #cccccc 1px solid; PADD=
ING-RIGHT: 0px; MARGIN-RIGHT: 0px}
#x7e6927bc026f4b879e57ab6cb48f8a21 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}
#x7e6927bc026f4b879e57ab6cb48f8a21 .plain PRE, #x7e6927bc026f4b879e57ab6cb4=
8f8a21 .plain TT
{FONT-SIZE: 100%; FONT-FAMILY: monospace; WHITE-SPACE: pre-wrap; FONT-WEIGH=
T: normal; FONT-STYLE: normal}
#x7e6927bc026f4b879e57ab6cb48f8a21 A IMG
{BORDER-LEFT-WIDTH: 0px; BORDER-RIGHT-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px;=
 BORDER-TOP-WIDTH: 0px}
#x7e6927bc026f4b879e57ab6cb48f8a21 #x1c2fb1324db1464cb9ece942bf916590, #x7e=
6927bc026f4b879e57ab6cb48f8a21 #x2e2ab106f7c24bab8de993a2b4c236d1, #x7e6927=
bc026f4b879e57ab6cb48f8a21 .plain PRE, #x7e6927bc026f4b879e57ab6cb48f8a21=
 .plain TT, #x7e6927bc026f4b879e57ab6cb48f8a21
{FONT-SIZE: 12pt; FONT-FAMILY: Tahoma}
</STYLE>
</HEAD>
<BODY scroll=3Dauto class>
<DIV>Note: my stupid email client didn't indent Peter Todd's quote correctl=
y. The first paragraph is his, the second is my response.</DIV>
<DIV>&nbsp;</DIV>
<DIV>------ Original Message ------</DIV>
<DIV>From: "Eric Lombrozo" &lt;<A href=3D"mailto:elombrozo@gmail.com">elomb=
rozo@gmail.com</A>&gt;</DIV>
<DIV>To: "Peter Todd" &lt;<A href=3D"mailto:pete@petertodd.org">pete@petert=
odd.org</A>&gt;; "Emin G=C3=BCn Sirer" &lt;<A href=3D"mailto:el33th4x0r@gma=
il.com">el33th4x0r@gmail.com</A>&gt;</DIV>
<DIV>Cc: <A href=3D"mailto:nbvfour@gmail.com">nbvfour@gmail.com</A>; "Bitco=
in Dev" &lt;<A href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoi=
n-dev@lists.linuxfoundation.org</A>&gt;</DIV>
<DIV>Sent: 12/26/2015 12:23:38 AM</DIV>
<DIV>Subject: Re[2]: [bitcoin-dev] We need to fix the block withholding =
attack</DIV>
<DIV>&nbsp;</DIV>
<DIV id=3Dx7e6927bc026f4b879e57ab6cb48f8a21 class=3Dclass>
<BLOCKQUOTE class=3Dcite2 cite=3Dema8a70574-c28e-4c43-a1e3-5f2f4df7d3a2@pla=
tinum type=3D"cite">
<DIV>Peter Todd wrote:<TT><FONT face=3DTahoma><SPAN id=3Dx2e2ab106f7c24bab8=
de993a2b4c236d1></SPAN></FONT></TT></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></DIV></TT></BLOCKQUOTE></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 clearly show consent by the entire<BR>ecosystem, SPV client=
s included.<BR>&nbsp;</SPAN></FONT></DIV>
<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 [<A href=3D"https://lists.linuxfoundation.org/pip=
ermail/bitcoin-dev/2015-May/008356.html">https://lists.linuxfoundation.org/=
pipermail/bitcoin-dev/2015-May/008356.html</A>] have been proposed before..=
.but&nbsp;they add&nbsp;significant complications to the protocol and requi=
re nontrivial app migration&nbsp;efforts.&nbsp;Old nodes would not get fork=
ed 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 bitcoins 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></DIV></BLOCKQUOTE></DIV></BODY></HTML>
--------=_MB6AF2FC99-758F-4AE8-BBFB-E6DFE6FDE234--