Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 91903181C for ; Sun, 20 Sep 2015 00:48:22 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wi0-f181.google.com (mail-wi0-f181.google.com [209.85.212.181]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3AF4418C for ; Sun, 20 Sep 2015 00:48:21 +0000 (UTC) Received: by wiclk2 with SMTP id lk2so70114364wic.1 for ; Sat, 19 Sep 2015 17:48:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=4W/0S/+9vLjLlxfZDLCfMGa0WcmXBU51smVzA9hTmEY=; b=qyBHS2OFFr1R6E+8fBTjGJ/W7QGYd9ddEiUMX70kHHMUxDmXtb/0fnhap9TTCrKhu+ ciaz+aX1HpuErE4FAsmyBKR/xVZgVJZdnZLbg9so/oxISkkklx1Lqdf6cCb0Uq87R9gF vAfHfQ3fFUG2h1DsS2lmjqYriTe6hg9PFXFh93I0CJX9MdTU3DFQK1oOhcErAnbW3Fvg ZuZT1UMsLuI5eyGrOd7kcYxq5bI9hr/CzKiuXy8NHK2zpy4KvD0nHx9NEN3EpJOIeOL2 iwrApzfWKpBZoG6tb0wrS2cyyLsoH8iE33OpMqStw2LzYk0si8TFkuV8wb2XiK4Z/psL X8mQ== MIME-Version: 1.0 X-Received: by 10.180.187.244 with SMTP id fv20mr5925751wic.23.1442710099676; Sat, 19 Sep 2015 17:48:19 -0700 (PDT) Sender: dscotese@gmail.com Received: by 10.27.211.132 with HTTP; Sat, 19 Sep 2015 17:48:19 -0700 (PDT) In-Reply-To: References: <5D55F6EC-801B-4607-882F-B76CF57298B1@gmail.com> <55FC6951.9010704@gmail.com> <55FCC8B5.9070906@openbitcoinprivacyproject.org> <4424FA4D-C84F-43DD-BA7F-BAC2D570A373@gmail.com> <55FD990F.8060102@openbitcoinprivacyproject.org> Date: Sat, 19 Sep 2015 17:48:19 -0700 X-Google-Sender-Auth: mEBbGotMYtwTx4HzqFPjg5sCsBk Message-ID: From: Dave Scotese To: "Rune K. Svendsen" Content-Type: multipart/alternative; boundary=001a11c37e4601553b0520231fc4 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,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@lists.linuxfoundation.org" Subject: Re: [bitcoin-dev] Hash of UTXO set as consensus-critical 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: Sun, 20 Sep 2015 00:48:22 -0000 --001a11c37e4601553b0520231fc4 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable It seems there should be a practical limit to the size of a re-org - I mean a practical limit that is smaller than the current height. Vincent's proposal suggests that a year's worth of blocks is such a practical limit. I agree. There are probably lower limits that are practical too, but I like an entire year just to be conservative. As Vincent points out, "An attacker will need to have hidden hashing power to overwrite a years worth of blocks." TL;DR for the rest of this: Txns that lose confirmations from a reorg and then show up in the mempool but not in any of the next few blocks indicate malicious mining. I see a blind spot here. We are seeing the rule that says the longest chain is the valid chain as impossible to break, but it isn't. We broke it to fix the BerkelyDB problem. The code itself would have prevented us from doing that IF 51% of the hashpower had been used to build on the wrong chain, but it wasn't. Justus' question about what malicious means is key here. The blind spot is a bit more complex than just viewing the longest chain as impossible to break except with more than 51% of the hash power. The blind spot is our inability to distinguish between malicious blocks and honest blocks. Rune suggests that empty blocks indicate malice. I like that (which is why I advocate using BitcoinDaysDestroyed to decide between blocks at the same height that appear at nearly the same time, rather than first-seen). There are other methods we can use to distinguish between malicious blocks and honest ones. I'm inventing one right now, but I'm sure better ones can be found. Here's mine: Once a transaction has been confirmed, its originator generally takes on the responsibility of re-broadcasting it if it gets re-org'd out of its confirmation(s). Many mempools will see that re-broadcast, *if it happens*. Any malice in a 51% attack would come in the form of failing to include such transactions. If we have a history of orphaned blocks, then we can check to see which ones have been included in non-orphaned blocks since they got reorg'd out. Such transactions should be top-priority after a reorg, even if they have zero fees. When there is a transaction that doesn't appear in a new block within a couple hours of a reorg, that indicates dishonesty, usually in the sender (but that could be negligence), but possibly in the miner. Looking at the mempool would determine which, wouldn't it? notplato On Sat, Sep 19, 2015 at 1:11 PM, Rune K. Svendsen via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > An honest miner is a miner that supports the network by building on top o= f > the best valid chain. A malicious miner is one who wants to disrupt the > Bitcoin network, not support it, for example by executing a 51% attack > which mines empty blocks on top of the best chain. > > > /Rune > > > Den 19/09/2015 kl. 19.19 skrev Justus Ranvier < > justus@openbitcoinprivacyproject.org>: > > > >> On 19/09/15 10:45, Rune Kj=C3=A6r Svendsen wrote: > >> We need to distinguish between two different things here: > >> > >> 1) A 51% attack, where the majority of mining power is *malicious* > (hence =E2=80=9Cattack=E2=80=9D) > > > > What does "malicious" mean? > > > > In other words, If miner A is mining honestly, and miner B is mining > > maliciously, what are some of the possible difference in their behaviou= r > > we would observe? > > > > > > -- > > Justus Ranvier > > Open Bitcoin Privacy Project > > http://www.openbitcoinprivacyproject.org/ > > justus@openbitcoinprivacyproject.org > > E7AD 8215 8497 3673 6D9E 61C4 2A5F DA70 EAD9 E623 > > <0xEAD9E623.asc> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --=20 I like to provide some work at no charge to prove my value. Do you need a techie? I own Litmocracy and Meme Racing (in alpha). I'm the webmaster for The Voluntaryist which now accepts Bitcoin. I also code for The Dollar Vigilante . "He ought to find it more profitable to play by the rules" - Satoshi Nakamoto --001a11c37e4601553b0520231fc4 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
It seems there should be a practi= cal limit to the size of a re-org - I mean a practical limit that is smalle= r than the current height.=C2=A0 Vincent's proposal suggests that a yea= r's worth of blocks is such a practical limit.=C2=A0 I agree.=C2=A0 The= re are probably lower limits that are practical too, but I like an entire y= ear just to be conservative.=C2=A0 As Vincent points out, "An attacker= will need to have hidden hashing power to overwrite a years worth of block= s."

TL;DR for the rest of this: Txns that lose confi= rmations from a reorg and then show up in the mempool but not in any of the= next few blocks indicate malicious mining.

I see a blind spot= here.=C2=A0 We are seeing the rule that says the longest chain is the vali= d chain as impossible to break, but it isn't.=C2=A0 We broke it to fix = the BerkelyDB problem.=C2=A0 The code itself would have prevented us from d= oing that IF 51% of the hashpower had been used to build on the wrong chain= , but it wasn't.

Justus' question about what malicious= means is key here.=C2=A0 The blind spot is a bit more complex than just vi= ewing the longest chain as impossible to break except with more than 51% of= the hash power.=C2=A0 The blind spot is our inability to distinguish betwe= en malicious blocks and honest blocks.

Rune suggests that empt= y blocks indicate malice.=C2=A0 I like that (which is why I advocate using = BitcoinDaysDestroyed to decide between blocks at the same height that appea= r at nearly the same time, rather than first-seen).=C2=A0 There are other m= ethods we can use to distinguish between malicious blocks and honest ones.= =C2=A0 I'm inventing one right now, but I'm sure better ones can be= found.

Here's mine: Once a transaction has been confirmed= , its originator generally takes on the responsibility of re-broadcasting i= t if it gets re-org'd out of its confirmation(s).=C2=A0 Many mempools w= ill see that re-broadcast, if it happens.=C2=A0 Any malice in a 51% = attack would come in the form of failing to include such transactions.=C2= =A0 If we have a history of orphaned blocks, then we can check to see which= ones have been included in non-orphaned blocks since they got reorg'd = out.=C2=A0 Such transactions should be top-priority after a reorg, even if = they have zero fees.=C2=A0 When there is a transaction that doesn't app= ear in a new block within a couple hours of a reorg, that indicates dishone= sty, usually in the sender (but that could be negligence), but possibly in = the miner.=C2=A0 Looking at the mempool would determine which, wouldn't= it?

notplato

On Sat, Sep 19, 2015 at 1:11 PM, Rune K. Svendsen via bi= tcoin-dev <bitcoin-dev@lists.linuxfoundation.org&g= t; wrote:
An honest miner is a min= er that supports the network by building on top of the best valid chain. A = malicious miner is one who wants to disrupt the Bitcoin network, not suppor= t it, for example by executing a 51% attack which mines empty blocks on top= of the best chain.


/Rune

> Den 19/09/2015 kl. 19.19 skrev Justus Ranvier <justus@openbitcoinprivacyproject.org>:
>
>> On 19/09/15 10:45, Rune Kj=C3=A6r Svendsen wrote:
>> We need to distinguish between two different things here:
>>
>> 1) A 51% attack, where the majority of mining power is *malicious*= (hence =E2=80=9Cattack=E2=80=9D)
>
> What does "malicious" mean?
>
> In other words, If miner A is mining honestly, and miner B is mining > maliciously, what are some of the possible difference in their behavio= ur
> we would observe?
>
>
> --
> Justus Ranvier
> Open Bitcoin Privacy Project
> http://www.openbitcoinprivacyproject.org/
> justus@openbit= coinprivacyproject.org
> E7AD 8215 8497 3673 6D9E 61C4 2A5F DA70 EAD9 E623
> <0xEAD9E623.asc= >
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev



--
I like to provide some work at no cha= rge to prove my value. Do you need a techie?=C2=A0
I own Litmocracy and Meme Racing (in alpha).
I= 'm the webmaster for The Voluntaryist which now accepts Bitcoin.
I also code for = The Dollar Vigila= nte.
"He ought to find it more profitable to play by the rules&= quot; - Satoshi Nakamoto
--001a11c37e4601553b0520231fc4--