From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 2741A1145 for ; 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 ; Sat, 26 Dec 2015 08:23:45 +0000 (UTC) Received: by mail-pf0-f173.google.com with SMTP id 78so87242290pfw.2 for ; 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" To: "Peter Todd" , =?utf-8?q?Emin=20G=c3=bcn=20Sirer?= Date: Sat, 26 Dec 2015 08:23:38 +0000 Message-Id: In-Reply-To: <20151220132842.GA25481@muck> Reply-To: "Eric Lombrozo" 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 , 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
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 clearl= y show consent by the entire
ecosystem, SPV clients included.
 <= /DIV>
I think we can generalize this and 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.
 
jl2012 wrote:
After the meeting I find a softfork solution. It is very inefficient= and I am leaving it here just for record.
 
1. In the first output of the second transaction of a block, mining= pool will commit a random nonce with an OP_RETURN.
 
2. Mine as normal. When a block is found, the hash is concatenated = with the committed random nonce and hashed.
 
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.
 
4. For each difficulty retarget, the secondary target is decreased = by 2 ^ 1/64.
 
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.
 
All miners have to sacrifice 1% reward for 10 years. Confirmation will= also be 1% slower than it should be.
 
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.
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.
 
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.
 
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 they = add significant complications to the protocol and require nontrivial= app migration efforts. 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!
 
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 = ;ugly and significantly impact system usability...and I think theory tells= us we can't do any better.
 
- Eric
= --------=_MB37047242-D767-40D1-B083-6B0B57E9FB78--