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 EF35C11D1 for ; Sat, 26 Dec 2015 08:27:02 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pf0-f182.google.com (mail-pf0-f182.google.com [209.85.192.182]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E81E889 for ; Sat, 26 Dec 2015 08:27:01 +0000 (UTC) Received: by mail-pf0-f182.google.com with SMTP id 65so44212818pff.3 for ; Sat, 26 Dec 2015 00:27:01 -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=N1IB5PC6taByUzfuNPtzKfVZMoRQ1uEodSRiR9FmanE=; b=IARDtbEj2p2nBH7vU1WXgMnkyi6zB76vVUxnTLSVF0hGGnSIEGRYrRMHMA/7l/hDKU s/EQAF1BjH2U92QVUi9TlLukG/bvUusH3cCj0SMt0wCHMkjd7Mb/siEoW2X8VuXI79B5 Y69K3xijMA07PNPtI4L1LxmSP0TctnuxV/+0yFKAE/iTXLcCveFUk7vUW5pLb9593tmE VkgJDW7PaUTQxIi7DGa0JYWouHTao6/ry3dWCJcmbDtPiQQLyfZOmwPQWPRbNiicsJfj EVIYq8UY8qsudYTV/xtJ3Ded0Og/S78KOTzwycnasfH5Hao9D7nmO9vj7VtWY3E7XKC3 hFxw== X-Received: by 10.98.8.82 with SMTP id c79mr41020479pfd.122.1451118421692; Sat, 26 Dec 2015 00:27:01 -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 c20sm2589904pfj.74.2015.12.26.00.27.00 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 26 Dec 2015 00:27:01 -0800 (PST) From: "Eric Lombrozo" To: "Peter Todd" , =?utf-8?q?Emin=20G=c3=bcn=20Sirer?= Date: Sat, 26 Dec 2015 08:26:54 +0000 Message-Id: In-Reply-To: Reply-To: "Eric Lombrozo" User-Agent: eM_Client/6.0.23181.0 Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="------=_MB6AF2FC99-758F-4AE8-BBFB-E6DFE6FDE234" 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:27:03 -0000 --------=_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" To: "Peter Todd" ; "Emin G=C3=BCn Sirer"=20 Cc: nbvfour@gmail.com; "Bitcoin Dev"=20 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
Note: my stupid email client didn't indent Peter Todd's quote correctl= y. The first paragraph is his, the second is my response.
 
------ Original Message ------
From: "Eric Lombrozo" <elomb= rozo@gmail.com>
To: "Peter Todd" <pete@petert= odd.org>; "Emin G=C3=BCn Sirer" <el33th4x0r@gmail.com>
Sent: 12/26/2015 12:23:38 AM
Subject: Re[2]: [bitcoin-dev] We need to fix the block withholding = 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 will
have the desirable= side effect of clearly show consent by the entire
ecosystem, SPV client= s included.
 
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/bitcoin-dev/2015-May/008356.html] have been proposed before..= .but they add significant complications to the protocol and requi= re nontrivial app migration efforts. 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!
 
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
--------=_MB6AF2FC99-758F-4AE8-BBFB-E6DFE6FDE234--