Return-Path: <jtimon@jtimon.cc> Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id A4BB2167A for <bitcoin-dev@lists.linuxfoundation.org>; Fri, 18 Sep 2015 20:38:09 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wi0-f174.google.com (mail-wi0-f174.google.com [209.85.212.174]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 465D115A for <bitcoin-dev@lists.linuxfoundation.org>; Fri, 18 Sep 2015 20:38:08 +0000 (UTC) Received: by wicfx3 with SMTP id fx3so78421270wic.1 for <bitcoin-dev@lists.linuxfoundation.org>; Fri, 18 Sep 2015 13:38:07 -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=0ay2oVINjRe/MgKA8PW2m5akOxKHIzYz2oS7B+hsDJg=; b=ita7vhdfP0lOyB/ikNs/tHt0JvKBLepjLIKif1jXn2SOGZPTjWvmnufn+T1poy3ICB AuBwQk6JvVR+wn3xnMpDeQT942K11jLotnanNikdGqIGRswCPWZ7OkgzOd6DGk1R9YCh bRk4Hi4M+gPna3Xc2sXCvpP1/zPY1R3e1M3h8cstT9ZNPaxs9aTUp16zwXktoMMLPvdq 4JCJYxp+JVGhrvZgQfRutOfKNohTjHch5oS/FxkFfYKyyDuVsRoQpa84I+tIcp8JedY2 6S1cmG2w8kTDahBTl9ot0zCdLcjZQETDjJSH7SsuY4iT3h3c4yxe5VsBDCkHBsDTg58e hQUQ== X-Gm-Message-State: ALoCoQmkhtgOTkHsj3lUS4/Ab+4lm37EnlaVb8BaMqyE1nTv9V9OxVTipF2tGcVUXO9dzWmKkQj2 MIME-Version: 1.0 X-Received: by 10.180.84.225 with SMTP id c1mr162781wiz.92.1442608687029; Fri, 18 Sep 2015 13:38:07 -0700 (PDT) Received: by 10.194.37.5 with HTTP; Fri, 18 Sep 2015 13:38:06 -0700 (PDT) Received: by 10.194.37.5 with HTTP; Fri, 18 Sep 2015 13:38:06 -0700 (PDT) In-Reply-To: <CABm2gDrQm8-vQi6YBx9xh4GanJi-ZfiJpSW8nghvGeoLsuDVsw@mail.gmail.com> References: <5D55F6EC-801B-4607-882F-B76CF57298B1@gmail.com> <55FC6951.9010704@gmail.com> <A16FDC0B-877F-47F1-A631-77F46251BB07@gmail.com> <CABm2gDrQm8-vQi6YBx9xh4GanJi-ZfiJpSW8nghvGeoLsuDVsw@mail.gmail.com> Date: Fri, 18 Sep 2015 22:38:06 +0200 Message-ID: <CABm2gDp-=Z0UHQ=7BnC8P_XJ3XCpU4n_L6kx6tfVovRmsGjFaw@mail.gmail.com> From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= <jtimon@jtimon.cc> To: =?UTF-8?Q?Rune_Kj=C3=A6r_Svendsen?= <runesvend@gmail.com> Content-Type: multipart/alternative; boundary=f46d0418282e57537c05200b82ee X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,HTML_MESSAGE, RCVD_IN_DNSWL_LOW,URIBL_BLACK autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Dev <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 <bitcoin-dev.lists.linuxfoundation.org> List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> X-List-Received-Date: Fri, 18 Sep 2015 20:38:09 -0000 --f46d0418282e57537c05200b82ee Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable s/move the genesis block forward/move your genesis checkpoint forward/ On Sep 18, 2015 4:37 PM, "Jorge Tim=C3=B3n" <jtimon@jtimon.cc> wrote: > 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 res= t > 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* bloc= k 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 rule= s. >> 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 afte= r >> 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 build= ing 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 balan= ce >> of their wallet, however, really don=E2=80=99t need to retrieve informat= ion about >> Hal Finney sending bitcoins to Satoshi in 2010. In any case, this practi= ce >> isn=E2=80=99t sustainable. >> >> In the end, it isn=E2=80=99t possible to control whether a miner verifie= s the >> 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 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 >> 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 possible = to 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 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. >> > >> > 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 u= p >> 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 s= ize >> of around 1GB, the extra bandwidth required is significant, and will kee= p >> 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 = the 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 t= hat >> a block with an invalid UTXO set hash would be rejected. >> >> >> >> I=E2=80=99m not talking about calculating a complicated tree structur= e 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 newl= y >> created block, such that the transactions in the new block build *on top= * >> of the UTXO set whose hash is specified. This actually alleviates Bitcoi= n >> 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 C= ore >> nodes, who only need to send roughly 1GB of data, in order to synchronis= e 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 requ= irement 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 chai= n >> is the same thing, so by including the hash of the UTXO set we force min= ers >> 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 >> 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-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 >> > --f46d0418282e57537c05200b82ee Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <p dir=3D"ltr">s/move the genesis block forward/move your genesis checkpoin= t forward/</p> <div class=3D"gmail_quote">On Sep 18, 2015 4:37 PM, "Jorge Tim=C3=B3n&= quot; <jtimon@jtimon.cc> wrote:<br type=3D"attribution"><blockquote c= lass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;= padding-left:1ex"><p dir=3D"ltr">Well, with utxo commitments at some point = maybe is enough to validate the full headers history but only the last 5 ye= ars of ttansaction history (assuming utxo commitments are buried 5 years wo= rth of blocks in the past). This scales much better than validating the ful= l history and if we get a 5 year reorg something is going really wrong anyw= ay...<br> 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.<br= > 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.<br> </p> <div class=3D"gmail_quote">On Sep 18, 2015 4:18 PM, "Rune Kj=C3=A6r Sv= endsen" <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" t= arget=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br ty= pe=3D"attribution"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 = .8ex;border-left:1px #ccc solid;padding-left:1ex">There are a couple of poi= nts I=E2=80=99d like to address.<br> <br> 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.<br> <br> 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.<br> <br> 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.<br> <br> 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.<br> <br> 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.<br> <br> /Rune<br> <br> <br> > On 18 Sep 2015, at 21:43, Patrick Strateman via bitcoin-dev <<a hre= f=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoi= n-dev@lists.linuxfoundation.org</a>> wrote:<br> ><br> > Full nodes using UTXO set commitments is a change to the bitcoin<br> > security model.<br> ><br> > Currently an attacker with >50% of the network hashrate can rewrite= history.<br> ><br> > If full nodes rely on UTXO set commitments such an attacker could crea= te<br> > an infinite number of bitcoins (as in many times more than the current= <br> > 21 million bitcoin limit).<br> ><br> > Before we consider mechanisms for UTXO set commitments, we should<br> > seriously discuss whether the security model reduction is reasonable.<= br> ><br> > On 09/18/2015 12:05 PM, Rune Kj=C3=A6r Svendsen via bitcoin-dev wrote:= <br> >> 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.<br> >><br> >> 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.<br> >><br> >> 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.<br> >><br> >> Am I missing something obvious, because as far as I can see, this = solves the problem of quadratic time complexity for initial sync: <a href= =3D"http://www.youtube.com/watch?v=3DTgjrS-BPWDQ&t=3D2h02m12s" rel=3D"n= oreferrer" target=3D"_blank">http://www.youtube.com/watch?v=3DTgjrS-BPWDQ&a= mp;t=3D2h02m12s</a><br> >><br> >> 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.<br= > >><br> >> /Rune<br> >> _______________________________________________<br> >> bitcoin-dev mailing list<br> >> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D= "_blank">bitcoin-dev@lists.linuxfoundation.org</a><br> >> <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitc= oin-dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation= .org/mailman/listinfo/bitcoin-dev</a><br> ><br> ><br> > _______________________________________________<br> > bitcoin-dev mailing list<br> > <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bl= ank">bitcoin-dev@lists.linuxfoundation.org</a><br> > <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-= dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev</a><br> <br> _______________________________________________<br> bitcoin-dev mailing list<br> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">= bitcoin-dev@lists.linuxfoundation.org</a><br> <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev</a><br> </blockquote></div> </blockquote></div> --f46d0418282e57537c05200b82ee--