Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id A0C40158E for ; Fri, 18 Sep 2015 20:37:08 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wi0-f169.google.com (mail-wi0-f169.google.com [209.85.212.169]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3E51E1AF for ; Fri, 18 Sep 2015 20:37:07 +0000 (UTC) Received: by wiclk2 with SMTP id lk2so78635075wic.0 for ; Fri, 18 Sep 2015 13:37:05 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=ZwKUvyjlg/xHig2mEvSHd5TRe3dphcExv3HPYFkGvkU=; b=OdXSI/m0Xj602Mb5s0i1FXkjAif9MhQ5geZOXVqZYhq1xtjZUOe5EVF7wU1trWcxu6 lcZzN3hFfa7Bra/3LMLOdRxxwypWx0ZrLvtgmMhfkH/S+atlgqd2N7kWv5WT2aiI1J1z VnnM5q/VYXZOBHAIRj739TqE3OjQYRjXe7QL1nW2tWNr+5VtrLlLzCxjXP8kl/o0i84B yTPF8b4gVWwSma40seZigxExO/SfoUO3JIssFuVlq4t5S+OBscAI1B0UFYIkZg1UKe7B 4FiCXWMxameG7bcld2AoYOLEnwbwdN6oRN2FVD4mYXIfgXNhzOcCdwtjtp/5bTiGfO4I HkBw== X-Gm-Message-State: ALoCoQmiPq1n9XR5EDBWpfy+35GT8tHioDvhH+1l8CoXoIdkuX0HQGfns+4gyW3lz+6nlDjwX3i6 MIME-Version: 1.0 X-Received: by 10.194.122.97 with SMTP id lr1mr9485432wjb.26.1442608625671; Fri, 18 Sep 2015 13:37:05 -0700 (PDT) Received: by 10.194.37.5 with HTTP; Fri, 18 Sep 2015 13:37:05 -0700 (PDT) Received: by 10.194.37.5 with HTTP; Fri, 18 Sep 2015 13:37:05 -0700 (PDT) In-Reply-To: References: <5D55F6EC-801B-4607-882F-B76CF57298B1@gmail.com> <55FC6951.9010704@gmail.com> Date: Fri, 18 Sep 2015 22:37:05 +0200 Message-ID: From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= To: =?UTF-8?Q?Rune_Kj=C3=A6r_Svendsen?= Content-Type: multipart/alternative; boundary=089e01228c70aef97b05200b7ee0 X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,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 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: Fri, 18 Sep 2015 20:37:08 -0000 --089e01228c70aef97b05200b7ee0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Well, with utxo commitments at some point maybe is enough to validate the full headers history but only the last 5 years of ttansaction history (assuming utxo commitments are buried 5 years worth of blocks in the past). This scales much better than validating the full history and if we get a 5 year reorg something is going really wrong anyway... Maybe after validating the last 5 years you also want to validate the rest of the history backards to get the "fully-full node" security. Of course 5 years it's just an arbitrary number: 2 or maybe even 1 would probably be secure enough for most people. I've referred to this idea as "hard checkpoints" or "moving the genesis block forward" in the past. On Sep 18, 2015 4:18 PM, "Rune Kj=C3=A6r Svendsen" < bitcoin-dev@lists.linuxfoundation.org> wrote: > There are a couple of points I=E2=80=99d like to address. > > Firstly, yes, >50% attacks are a problem for Bitcoin. Bitcoin does not > function if the majority of mining power is dishonest. There is no way > around that. It=E2=80=99s how proof-of-work functions. And if we lose > proof-of-work, we lose Bitcoin. > > Secondly, I=E2=80=99m not suggesting that UTXO set hashes *replace* block= hashes, > or even that it should be in the block header (probably in the coinbase > somewhere). I suggest it as an *addition* to the existing consensus rules= . > Full nodes can still verify the chain with the added step of hashing the > UTXO set for every block. Of course, this can easily be deferred to after > proof-of-work has been verified already, such that no work is wasted. > Unless a 51% attack is in effect. But I argue that this is a moot point, > since Bitcoin is useless anyway under such circumstances. > > Lastly, I=E2=80=99m not suggesting miners discard the blockchain history.= A miner > has an incentive to be absolutely sure that the chain he=E2=80=99s buildi= ng on is > the right one. If he=E2=80=99s wrong, he loses money/income. There=E2=80= =99s simply no > reason for a professional miner *not* to do the full initial sync, which > only needs to be done once. Non-miners, who just want to check the balanc= e > of their wallet, however, really don=E2=80=99t need to retrieve informati= on about > Hal Finney sending bitcoins to Satoshi in 2010. In any case, this practic= e > isn=E2=80=99t sustainable. > > In the end, it isn=E2=80=99t possible to control whether a miner verifies= the > entire blockchain anyway (anyone can send the UTXO set over the wire). No= t > letting the proof-of-work cover the UTXO hash doesn=E2=80=99t solve this = problem, > it only makes it impossible to know whether a given UTXO set is the one > that the majority is mining on without retrieving the entire blockchain, > and doing the verification yourself. People can choose to skip that > regardless of what we do. > > Furthermore, all nodes have the option of deciding which level of securit= y > they want. We=E2=80=99re not lessening security of the protocol, we=E2=80= =99re > strengthening the security of something that=E2=80=99s already possible t= o do > (build on top of an unverified blockchain), but we=E2=80=99d rather want = that > people not do. > > /Rune > > > > On 18 Sep 2015, at 21:43, Patrick Strateman via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > > > > Full nodes using UTXO set commitments is a change to the bitcoin > > security model. > > > > Currently an attacker with >50% of the network hashrate can rewrite > history. > > > > If full nodes rely on UTXO set commitments such an attacker could creat= e > > an infinite number of bitcoins (as in many times more than the current > > 21 million bitcoin limit). > > > > Before we consider mechanisms for UTXO set commitments, we should > > seriously discuss whether the security model reduction is reasonable. > > > > On 09/18/2015 12:05 PM, Rune Kj=C3=A6r Svendsen via bitcoin-dev wrote: > >> Currently, when a new node wants to join the network, it needs to > retrieve the entire blockchain history, starting from January 2009 and up > until now, in order to derive a UTXO set that it can verify new > blocks/transactions against. With a blockchain size of 40GB and a UTXO si= ze > of around 1GB, the extra bandwidth required is significant, and will keep > increasing indefinitely. If a newly mined block were to include the UTXO > set hash of the chain up until the previous block =E2=80=94 the hash of t= he UTXO > set on top of which this block builds =E2=80=94 then new nodes, who want = to know > whether a transaction is valid, would be able to acquire the UTXO set in = a > trustless manner, by only verifying proof-of-work headers, and knowing th= at > a block with an invalid UTXO set hash would be rejected. > >> > >> I=E2=80=99m not talking about calculating a complicated tree structure= from the > UTXO set, which would put further burden on already burdened Bitcoin Core > nodes. We simply include the hash of the current UTXO set in a newly > created block, such that the transactions in the new block build *on top* > of the UTXO set whose hash is specified. This actually alleviates Bitcoin > Core nodes, as it will now become possible for nodes without the entire > blockchain to answer SPV queries (by retrieving the UTXO set trustlessly > and using this to answer queries). It also saves bandwidth for Bitcore Co= re > nodes, who only need to send roughly 1GB of data, in order to synchronise= a > node, rather than 40GB+. I will continue to run a full Bitcoin Core node, > saving the entire blockchain history, but it shouldn=E2=80=99t be a requi= rement to > hold the entire transaction history in order to start verifying new > transactions. > >> > >> As far as I can see, this also forces miners to actually maintain an > UTXO set, rather than just build on top of the chain with the most > proof-of-work. Producing a UTXO set and verifying a block against a chain > is the same thing, so by including the hash of the UTXO set we force mine= rs > to verify the block that they want to build on top of. > >> > >> Am I missing something obvious, because as far as I can see, this > solves the problem of quadratic time complexity for initial sync: > http://www.youtube.com/watch?v=3DTgjrS-BPWDQ&t=3D2h02m12s > >> > >> The only added step to verifying a block is to hash the UTXO set. So i= t > does require additional computation, but most modern CPUs have a SHA256 > throughput of around 500 MB/s, which means it takes only two seconds to > hash the UTXO set. And this can be improved further (GPUs can do 2-3 GB/s= ). > A small sacrifice for the added ease of initial syncing, in my opinion. > >> > >> /Rune > >> _______________________________________________ > >> bitcoin-dev mailing list > >> bitcoin-dev@lists.linuxfoundation.org > >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > > > > _______________________________________________ > > bitcoin-dev mailing list > > bitcoin-dev@lists.linuxfoundation.org > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --089e01228c70aef97b05200b7ee0 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Well, with utxo commitments at some point maybe is enough to= validate the full headers history but only the last 5 years of ttansaction= history (assuming utxo commitments are buried 5 years worth of blocks in t= he past). This scales much better than validating the full history and if w= e get a 5 year reorg something is going really wrong anyway...
Maybe after validating the last 5 years you also want to validate the rest = of the history backards to get the "fully-full node" security. Of course 5 years it's just an arbitrary number: 2 or maybe even 1 woul= d probably be secure enough for most people. I've referred to this idea= as "hard checkpoints" or "moving the genesis block forward&= quot; in the past.

On Sep 18, 2015 4:18 PM, "Rune Kj=C3=A6r Sv= endsen" <b= itcoin-dev@lists.linuxfoundation.org> wrote:
There are a couple of points I=E2=80=99d li= ke to address.

Firstly, yes, >50% attacks are a problem for Bitcoin. Bitcoin does not f= unction if the majority of mining power is dishonest. There is no way aroun= d that. It=E2=80=99s how proof-of-work functions. And if we lose proof-of-w= ork, we lose Bitcoin.

Secondly, I=E2=80=99m not suggesting that UTXO set hashes *replace* block h= ashes, or even that it should be in the block header (probably in the coinb= ase somewhere). I suggest it as an *addition* to the existing consensus rul= es. Full nodes can still verify the chain with the added step of hashing th= e UTXO set for every block. Of course, this can easily be deferred to after= proof-of-work has been verified already, such that no work is wasted. Unle= ss a 51% attack is in effect. But I argue that this is a moot point, since = Bitcoin is useless anyway under such circumstances.

Lastly, I=E2=80=99m not suggesting miners discard the blockchain history. A= miner has an incentive to be absolutely sure that the chain he=E2=80=99s b= uilding on is the right one. If he=E2=80=99s wrong, he loses money/income. = There=E2=80=99s simply no reason for a professional miner *not* to do the f= ull initial sync, which only needs to be done once. Non-miners, who just wa= nt to check the balance of their wallet, however, really don=E2=80=99t need= to retrieve information about Hal Finney sending bitcoins to Satoshi in 20= 10. In any case, this practice isn=E2=80=99t sustainable.

In the end, it isn=E2=80=99t possible to control whether a miner verifies t= he entire blockchain anyway (anyone can send the UTXO set over the wire). N= ot letting the proof-of-work cover the UTXO hash doesn=E2=80=99t solve this= problem, it only makes it impossible to know whether a given UTXO set is t= he one that the majority is mining on without retrieving the entire blockch= ain, and doing the verification yourself. People can choose to skip that re= gardless of what we do.

Furthermore, all nodes have the option of deciding which level of security = they want. We=E2=80=99re not lessening security of the protocol, we=E2=80= =99re strengthening the security of something that=E2=80=99s already possib= le to do (build on top of an unverified blockchain), but we=E2=80=99d rathe= r want that people not do.

/Rune


> On 18 Sep 2015, at 21:43, Patrick Strateman via bitcoin-dev <bitcoin-dev@lists.linuxf= oundation.org> wrote:
>
> Full nodes using UTXO set commitments is a change to the bitcoin
> security model.
>
> Currently an attacker with >50% of the network hashrate can rewrite= history.
>
> If full nodes rely on UTXO set commitments such an attacker could crea= te
> an infinite number of bitcoins (as in many times more than the current=
> 21 million bitcoin limit).
>
> Before we consider mechanisms for UTXO set commitments, we should
> seriously discuss whether the security model reduction is reasonable.<= br> >
> On 09/18/2015 12:05 PM, Rune Kj=C3=A6r Svendsen via bitcoin-dev wrote:=
>> Currently, when a new node wants to join the network, it needs to = retrieve the entire blockchain history, starting from January 2009 and up u= ntil now, in order to derive a UTXO set that it can verify new blocks/trans= actions against. With a blockchain size of 40GB and a UTXO size of around 1= GB, the extra bandwidth required is significant, and will keep increasing i= ndefinitely. If a newly mined block were to include the UTXO set hash of th= e chain up until the previous block =E2=80=94 the hash of the UTXO set on t= op of which this block builds =E2=80=94 then new nodes, who want to know wh= ether a transaction is valid, would be able to acquire the UTXO set in a tr= ustless manner, by only verifying proof-of-work headers, and knowing that a= block with an invalid UTXO set hash would be rejected.
>>
>> I=E2=80=99m not talking about calculating a complicated tree struc= ture from the UTXO set, which would put further burden on already burdened = Bitcoin Core nodes. We simply include the hash of the current UTXO set in a= newly created block, such that the transactions in the new block build *on= top* of the UTXO set whose hash is specified. This actually alleviates Bit= coin Core nodes, as it will now become possible for nodes without the entir= e blockchain to answer SPV queries (by retrieving the UTXO set trustlessly = and using this to answer queries). It also saves bandwidth for Bitcore Core= nodes, who only need to send roughly 1GB of data, in order to synchronise = a node, rather than 40GB+. I will continue to run a full Bitcoin Core node,= saving the entire blockchain history, but it shouldn=E2=80=99t be a requir= ement to hold the entire transaction history in order to start verifying ne= w transactions.
>>
>> As far as I can see, this also forces miners to actually maintain = an UTXO set, rather than just build on top of the chain with the most proof= -of-work. Producing a UTXO set and verifying a block against a chain is the= same thing, so by including the hash of the UTXO set we force miners to ve= rify the block that they want to build on top of.
>>
>> Am I missing something obvious, because as far as I can see, this = solves the problem of quadratic time complexity for initial sync: http://www.youtube.com/watch?v=3DTgjrS-BPWDQ&a= mp;t=3D2h02m12s
>>
>> The only added step to verifying a block is to hash the UTXO set. = So it does require additional computation, but most modern CPUs have a SHA2= 56 throughput of around 500 MB/s, which means it takes only two seconds to = hash the UTXO set. And this can be improved further (GPUs can do 2-3 GB/s).= A small sacrifice for the added ease of initial syncing, in my opinion. >>
>> /Rune
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-d= ev@lists.linuxfoundation.org
>> https://lists.linuxfoundation= .org/mailman/listinfo/bitcoin-dev
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@l= ists.linuxfoundation.org
> https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--089e01228c70aef97b05200b7ee0--