Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 8F31617CB for ; Fri, 18 Sep 2015 22:22:37 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ig0-f170.google.com (mail-ig0-f170.google.com [209.85.213.170]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 34C2021C for ; Fri, 18 Sep 2015 22:22:36 +0000 (UTC) Received: by igcpb10 with SMTP id pb10so45666545igc.1 for ; Fri, 18 Sep 2015 15:22:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=procabiak.com; s=procabiakindustries; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=GLqhl/ek4vcduK5xrufNZQSMwYmHmRolsU7pJY3//BM=; b=Rxf3UHcySHp2gJINH5VkKxbatJWroHrw//YTW43nwh1NBZ9z1WO0QT4JqhbLRRc/Pv vpZdFtgpEGCg02uNjR8e5zWPbC0hDN17O9a1DWn8BWgVo0yP2eQN3PS+dKuz0Fm9K9do s3sNhLM1mgfyI1Jhv9jGj2Z8oKBJlQmHJ7xC4= 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=GLqhl/ek4vcduK5xrufNZQSMwYmHmRolsU7pJY3//BM=; b=Ys9t3vJg86ZJXcvu3jV6fJZ6sTjNriLUJez75Iaga2kuFwzcyscU/kvgfyyECtwQ89 3PX3YMHDW2aPVB+kSkcyOfm05oc40wBOJAHQeiElRN7t4M4q+LbVGIoiidFghnG/sTPd KrYzQ5BjODjyNXOuZPQuVS2GdTN2L2RvC0m5OeSAuOZIL0mWyan8T0Wpz29a6wJwF68R ukEmQSOSEkFbXJl/IyMTWfBjqSrqAY7CfXwbzfsrTM5eEfpa7lyChyr1+DMI32ZOsqG0 KArF7Il8PTm8bilTaKzoocgkOIMfGO0PmBHaNypM6L9jS6zKsNGFOjhdDOMnkjzkJYao bjdQ== X-Gm-Message-State: ALoCoQl0ZqiyFlxgp4i6YOB2LLCg3hQ5aKmRRskLvbqW1P3QinV9sgQXJsqeXtS91YxYmEf/Ne06 MIME-Version: 1.0 X-Received: by 10.50.111.113 with SMTP id ih17mr717231igb.64.1442614955531; Fri, 18 Sep 2015 15:22:35 -0700 (PDT) Received: by 10.36.68.213 with HTTP; Fri, 18 Sep 2015 15:22:35 -0700 (PDT) X-Originating-IP: [1.152.97.45] Received: by 10.36.68.213 with HTTP; Fri, 18 Sep 2015 15:22:35 -0700 (PDT) In-Reply-To: References: <5D55F6EC-801B-4607-882F-B76CF57298B1@gmail.com> <55FC6951.9010704@gmail.com> Date: Sat, 19 Sep 2015 08:22:35 +1000 Message-ID: From: Vincent Truong To: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= Content-Type: multipart/alternative; boundary=089e0149bb32f9259e05200cf75e X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,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@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: Fri, 18 Sep 2015 22:22:37 -0000 --089e0149bb32f9259e05200cf75e Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable This way lets us protect from 51% overwrites for a whole year: 1. Hash utxo set as is today, H1, and store it in a block. 2. At the same time, store a copy of the utxo set for H1 on disk, D1 3. After 1 year, create D2, then wait for H2 (if a fork happens then recreate D2 and see which wins) 4. The block with H2 must hash on top of H1 4. Blocks before H1 can be safely pruned by the network, only keeping D1 for reference/validation, plus blocks the node wants to keep (data/colored coins) 5. After 1 year, repeat for H3. 7. D1 can also be dropped after a few days once D3 is up, since the H1 securing D1 would have been pruned with H3's usage of D2 by then. This reduces the security model from 'always secure' to 'secure, as of last year'. An attacker will need to have hidden hashing power to overwrite a years worth of blocks. Which I think would be hard enough. The attacker can also try to undo a freshly built Hn, but because we can build Dn first and wait for Hn, the nodes should be expecting the same hash. They also serve as automated checkpoints to prevent them from overwriting all of it. On Sep 19, 2015 6:38 AM, "Jorge Tim=C3=B3n" < bitcoin-dev@lists.linuxfoundation.org> wrote: > s/move the genesis block forward/move your genesis checkpoint forward/ > On Sep 18, 2015 4:37 PM, "Jorge Tim=C3=B3n" wrote: > >> Well, with utxo commitments at some point maybe is enough to validate th= e >> full headers history but only the last 5 years of ttansaction history >> (assuming utxo commitments are buried 5 years worth of blocks in the pas= t). >> 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* blo= ck >>> 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 s= tep >>> 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 histor= y. A >>> miner has an incentive to be absolutely sure that the chain he=E2=80=99= s building >>> on is the right one. If he=E2=80=99s wrong, he loses money/income. Ther= e=E2=80=99s simply >>> no reason for a professional miner *not* to do the full initial sync, w= hich >>> only needs to be done once. Non-miners, who just want to check the bala= nce >>> of their wallet, however, really don=E2=80=99t need to retrieve informa= tion about >>> Hal Finney sending bitcoins to Satoshi in 2010. In any case, this pract= ice >>> isn=E2=80=99t sustainable. >>> >>> In the end, it isn=E2=80=99t possible to control whether a miner verifi= es the >>> entire blockchain anyway (anyone can send the UTXO set over the wire). = Not >>> letting the proof-of-work cover the UTXO hash doesn=E2=80=99t solve thi= s 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 protoco= l, 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 wan= t 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 >>> create >>> > an infinite number of bitcoins (as in many times more than the curren= t >>> > 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 = size >>> of around 1GB, the extra bandwidth required is significant, and will ke= ep >>> increasing indefinitely. If a newly mined block were to include the UTX= O >>> 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 wan= t to know >>> whether a transaction is valid, would be able to acquire the UTXO set i= n a >>> trustless 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 structu= re from >>> the UTXO set, which would put further burden on already burdened Bitcoi= n >>> Core nodes. We simply include the hash of the current UTXO set in a new= ly >>> created block, such that the transactions in the new block build *on to= p* >>> of the UTXO set whose hash is specified. This actually alleviates Bitco= in >>> Core nodes, as it will now become possible for nodes without the entire >>> blockchain to answer SPV queries (by retrieving the UTXO set trustlessl= y >>> 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 synchroni= se a >>> node, rather than 40GB+. I will continue to run a full Bitcoin Core nod= e, >>> saving the entire blockchain history, but it shouldn=E2=80=99t be a req= uirement 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 cha= in >>> is the same thing, so by including the hash of the UTXO set we force mi= ners >>> 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 SHA= 256 >>> 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 >>> >> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --089e0149bb32f9259e05200cf75e Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

This way lets us protect from 51% overwrites for a whole yea= r:

1. Hash utxo set as is today, H1, and store it in a block. 2. At the same time, store a copy of the utxo set for H1 on disk, D1
3. After 1 year, create D2, then wait for H2 (if a fork happens then recrea= te D2 and see which wins)
4. The block with H2 must hash on top of H1
4. Blocks before H1 can be safely pruned by the network, only keeping D1 fo= r reference/validation, plus blocks the node wants to keep (data/colored co= ins)
5. After 1 year, repeat for H3.
7. D1 can also be dropped after a few days once D3 is up, since the H1 secu= ring D1 would have been pruned with H3's usage of D2 by then.

This reduces the security model from 'always secure'= to 'secure, as of last year'. An attacker will need to have hidden= hashing power to overwrite a years worth of blocks. Which I think would be= hard enough.

The attacker can also try to undo a freshly built Hn, but be= cause we can build Dn first and wait for Hn, the nodes should be expecting = the same hash. They also serve as automated checkpoints to prevent them fro= m overwriting all of it.

On Sep 19, 2015 6:38 AM, "Jorge Tim=C3=B3n&= quot; <bitcoin-= dev@lists.linuxfoundation.org> wrote:

s/move the genesis block forward/mo= ve your genesis checkpoint forward/

On Sep 18, 2015 4:37 PM, "Jorge Tim=C3=B3n&= quot; <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 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...
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" <bitcoin-dev@lists.linuxfoundation.org> wrote:
There are a couple of poi= nts I=E2=80=99d like 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 <bitcoi= n-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.<= 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-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/mail= man/listinfo/bitcoin-dev

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

--089e0149bb32f9259e05200cf75e--