From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: <elombrozo@gmail.com> Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 97A78A58 for <bitcoin-dev@lists.linuxfoundation.org>; Thu, 23 Feb 2017 03:30:40 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-yb0-f195.google.com (mail-yb0-f195.google.com [209.85.213.195]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 49B54148 for <bitcoin-dev@lists.linuxfoundation.org>; Thu, 23 Feb 2017 03:30:39 +0000 (UTC) Received: by mail-yb0-f195.google.com with SMTP id d88so250289ybi.2 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 22 Feb 2017 19:30:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=ynDB3Hu7zDzI9B0OLoQ3oGWT85W6tUtun4UUCug92cE=; b=GRONbWJQzZX354DgyzvE5UdeaxWkWsiMkliyMKSy83jpcDRcb829Jm+xhuzgQtEoT4 XCMJqBQpxVxdylltTdjKrxPJXNu110reAeLQMBeuQSQ97TdFkpwmUHW2LzYrSFs3u7cH lPwQevaHLO9tjzozrkKqFfmlRT7h6O722H3JnC3+vDntD0JApVg3qv4YcgvD/QmoU4Yf Iju3tofIMsNKKsqhHBuTZz/fGQ9lDiE9/XR0wgDDvmUo4aL2Ndtb7wJ4CDS+5ZSHo/3E pw8ckEPMvJWfR6+j9B1VgB7oHMvuR4tXp8h8J6EfVfnc8TZQJY8CZbKZHXDxr73rCKH0 +bmA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=ynDB3Hu7zDzI9B0OLoQ3oGWT85W6tUtun4UUCug92cE=; b=cmSfwhPz5qtX1H7KzyNE4hb1kwUgyg99bzOwbtt/oQwGKb5bkcNKRCGlW7WR9uDCi3 4Yjnl9jvI0hlSgSIgdrvYBHN7Nhf80t+nxq4XWqVp8ZfTWPBzMNczGEFKMOxLBh//ITH TUA0Lxp6haoRLIMzzqVhJyHJSm9ZR1QpvL8cPIVWP9Pk4BoaL/4LzqTNkjg7ZPMrp+Ol 2+UJVqBflyJCVkXZumQMQqYJJ42DQfA/sQlCW90+fCAb1PHA/3wAfGSwMXmk/4PgJPUV EuyEkVxxuqS1ntwsxuEF8L3/HIBa6QLbT7P0Xvm7Kobe36Wdg/qE33h2QLqPtWyVUBzT FbMQ== X-Gm-Message-State: AMke39n1z60aNoKZTolWgOvcePKf3MGBYOY+C++h/74jYNKde2Qx7toMi1/SFhgKeffWm8Kl41zeo3sHRix0Nw== X-Received: by 10.37.8.65 with SMTP id 62mr26547823ybi.73.1487820638099; Wed, 22 Feb 2017 19:30:38 -0800 (PST) MIME-Version: 1.0 Received: by 10.37.113.195 with HTTP; Wed, 22 Feb 2017 19:30:37 -0800 (PST) In-Reply-To: <20170223011147.GB905@savin.petertodd.org> References: <20170223011147.GB905@savin.petertodd.org> From: Eric Lombrozo <elombrozo@gmail.com> Date: Wed, 22 Feb 2017 19:30:37 -0800 Message-ID: <CABr1YTfSak2d199=_-ifRAmZkx6X3d5pMRqsU0ke_QwDmsiOnA@mail.gmail.com> To: Peter Todd <pete@petertodd.org>, Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> Content-Type: multipart/alternative; boundary=001a113db3c09fa0e405492a3c45 X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] TXO commitments do not need a soft-fork to be useful X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol 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: Thu, 23 Feb 2017 03:30:40 -0000 --001a113db3c09fa0e405492a3c45 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable This kind of thing is long overdue! I think it=E2=80=99s a great idea to attempt this without soft forking TXO commitments yet so we can see what works best. - E On Wed, Feb 22, 2017 at 5:11 PM, Peter Todd via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Something I've recently realised is that TXO commitments do not need to b= e > implemented as a consensus protocol change to be useful. All the benefits > they > provide to full nodes with regard to allowing for old UTXO data to be > pruned - > and thus solving the UTXO bloat problem - can be implemented even without > having miners commit to the TXO commitment itself. This has a significant > deployment advantage too: we can try out multiple TXO commitment schemes, > in > production, without the need for consensus changes. > > > # Reasoning > > 1) Like any other merkelized data structure, a TXO commitment allows a > data set > - the TXO set - to be securely provided by an untrusted third party, > allowing > the data itself to be discarded. So if you have a valid TXO commitment, > you can > discard the TXO data itself, and rely on untrusted entities to provide yo= u > that > data on demand. > > 2) The TXO set is a super-set of the UTXO set; all data in the UTXO set i= s > also > present in the TXO set. Thus a TXO commitment with spent TXO's pruned is > equivalent to a UTXO set, doubly so if inner nodes in the commitment tree > commit to the sum-unspent of their children. > > 3) Where a outpoint-indexed UTXO set has a uniform access pattern, an > insertion-ordered TXO set has a delibrately *non-uniform* access pattern: > not > only are new entries to the TXO set always appended to the end - an > operation > that requires a known, log2(n), sized set of merkle tips - but due to los= t > coins alone we can guarantee that older entries in the TXO set will be le= ss > frequently updated than newer entries. > > 4) Thus a full node that doesn't have enough local storage to maintain th= e > full > UTXO set can instead keep track of a TXO commitment, and prune older UTXO= 's > from it that are unlikely to be spent. In the event those UTXO's are spen= t, > transactions and blocks spending them can trustlessly provide the necessa= ry > data to temporarily fill-in the node's local TXO set database, allowing t= he > next commitment to be calculated. > > 5) By *not* committing the TXO commitment in the block itself, we obsolet= e > my > concept of delayed TXO commitments: you don't need to have calculated the > TXO > commitment digest to validate a block anyway! > > > # Deployment Plan > > 1) Implement a TXO commitment scheme with the ability to efficiently stor= e > the > last n versions of the commitment state for the purpose of reorgs (a > reference-counted scheme naturally does this). > > 2) Add P2P support for advertising to peers what parts of the TXO set > you've > pruned. > > 3) Add P2P support to produce, consume, and update TXO unspentness proofs > as > part of transaction and block relaying. > > 4) Profit. > > > # Bootstrapping New Nodes > > With a TXO commitment scheme implemented, it's also possible to produce > serialized UTXO snapshots for bootstrapping new nodes. Equally, it's > obviously > possible to distribute those snapshots, and have people you trust attest > to the > validity of those snapshots. > > I argue that a snapshot with an attestation from known individuals that y= ou > trust is a *better* security model than having miners attest to validity: > the > latter is trusting an unknown set of unaccountable, anonymous, miners. > > This security model is not unlike the recently implemented -assumevalid > scheme(1), in that auditing the validity of the assumed valid TXO > commitments > is something anyone can do provided they have a full node. Similarly, we > could > ship Bitcoin nodes with an assumed-valid TXO commitment, and have those > nodes > fill in the UTXO data from their peers. > > However it is a weaker security model, in that a false TXO commitment can > more > easily be used to trick a node into accepting invalid transactions/blocks= ; > assumed valid blocks requires proof-of-work to pull off this attack. A > compromise may be to use assumed valid TXO commitments, extending my > partial > UTXO set(2) suggestion of having nodes validate the chain backwards, to > eventually validate 100% of the chain. > > > # References > > 1) https://github.com/bitcoin/bitcoin/pull/9484 > 2) [Bitcoin-development] SPV bitcoind? (was: Introducing > BitcoinKit.framework), > Peter Todd, Jul 17th 2013, Bitcoin development mailing list, > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/ > 2013-July/002917.html > > -- > https://petertodd.org 'peter'[:-1]@petertodd.org > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a113db3c09fa0e405492a3c45 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"> <p class=3D"gmail-p1"><span class=3D"gmail-s1">This kind of thing is long o= verdue!</span></p> <p class=3D"gmail-p2">I think it=E2=80=99s a great idea to attempt this wit= hout soft forking TXO commitments yet so we can see what works best.</p><p = class=3D"gmail-p2"><br></p> <p class=3D"gmail-p1"><span class=3D"gmail-s1">- E</span></p></div><div cla= ss=3D"gmail_extra"><br><div class=3D"gmail_quote">On Wed, Feb 22, 2017 at 5= :11 PM, Peter Todd via bitcoin-dev <span dir=3D"ltr"><<a href=3D"mailto:= bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.= linuxfoundation.org</a>></span> wrote:<br><blockquote class=3D"gmail_quo= te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"= >Something I've recently realised is that TXO commitments do not need t= o be<br> implemented as a consensus protocol change to be useful. All the benefits t= hey<br> provide to full nodes with regard to allowing for old UTXO data to be prune= d -<br> and thus solving the UTXO bloat problem - can be implemented even without<b= r> having miners commit to the TXO commitment itself. This has a significant<b= r> deployment advantage too: we can try out multiple TXO commitment schemes, i= n<br> production, without the need for consensus changes.<br> <br> <br> # Reasoning<br> <br> 1) Like any other merkelized data structure, a TXO commitment allows a data= set<br> - the TXO set - to be securely provided by an untrusted third party, allowi= ng<br> the data itself to be discarded. So if you have a valid TXO commitment, you= can<br> discard the TXO data itself, and rely on untrusted entities to provide you = that<br> data on demand.<br> <br> 2) The TXO set is a super-set of the UTXO set; all data in the UTXO set is = also<br> present in the TXO set. Thus a TXO commitment with spent TXO's pruned i= s<br> equivalent to a UTXO set, doubly so if inner nodes in the commitment tree<b= r> commit to the sum-unspent of their children.<br> <br> 3) Where a outpoint-indexed UTXO set has a uniform access pattern, an<br> insertion-ordered TXO set has a delibrately *non-uniform* access pattern: n= ot<br> only are new entries to the TXO set always appended to the end - an operati= on<br> that requires a known, log2(n), sized set of merkle tips - but due to lost<= br> coins alone we can guarantee that older entries in the TXO set will be less= <br> frequently updated than newer entries.<br> <br> 4) Thus a full node that doesn't have enough local storage to maintain = the full<br> UTXO set can instead keep track of a TXO commitment, and prune older UTXO&#= 39;s<br> from it that are unlikely to be spent. In the event those UTXO's are sp= ent,<br> transactions and blocks spending them can trustlessly provide the necessary= <br> data to temporarily fill-in the node's local TXO set database, allowing= the<br> next commitment to be calculated.<br> <br> 5) By *not* committing the TXO commitment in the block itself, we obsolete = my<br> concept of delayed TXO commitments: you don't need to have calculated t= he TXO<br> commitment digest to validate a block anyway!<br> <br> <br> # Deployment Plan<br> <br> 1) Implement a TXO commitment scheme with the ability to efficiently store = the<br> last n versions of the commitment state for the purpose of reorgs (a<br> reference-counted scheme naturally does this).<br> <br> 2) Add P2P support for advertising to peers what parts of the TXO set you&#= 39;ve<br> pruned.<br> <br> 3) Add P2P support to produce, consume, and update TXO unspentness proofs a= s<br> part of transaction and block relaying.<br> <br> 4) Profit.<br> <br> <br> # Bootstrapping New Nodes<br> <br> With a TXO commitment scheme implemented, it's also possible to produce= <br> serialized UTXO snapshots for bootstrapping new nodes. Equally, it's ob= viously<br> possible to distribute those snapshots, and have people you trust attest to= the<br> validity of those snapshots.<br> <br> I argue that a snapshot with an attestation from known individuals that you= <br> trust is a *better* security model than having miners attest to validity: t= he<br> latter is trusting an unknown set of unaccountable, anonymous, miners.<br> <br> This security model is not unlike the recently implemented -assumevalid<br> scheme(1), in that auditing the validity of the assumed valid TXO commitmen= ts<br> is something anyone can do provided they have a full node. Similarly, we co= uld<br> ship Bitcoin nodes with an assumed-valid TXO commitment, and have those nod= es<br> fill in the UTXO data from their peers.<br> <br> However it is a weaker security model, in that a false TXO commitment can m= ore<br> easily be used to trick a node into accepting invalid transactions/blocks;<= br> assumed valid blocks requires proof-of-work to pull off this attack. A<br> compromise may be to use assumed valid TXO commitments, extending my partia= l<br> UTXO set(2) suggestion of having nodes validate the chain backwards, to<br> eventually validate 100% of the chain.<br> <br> <br> # References<br> <br> 1) <a href=3D"https://github.com/bitcoin/bitcoin/pull/9484" rel=3D"noreferr= er" target=3D"_blank">https://github.com/bitcoin/<wbr>bitcoin/pull/9484</a>= <br> 2) [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framewo= rk),<br> =C2=A0 =C2=A0Peter Todd, Jul 17th 2013, Bitcoin development mailing list,<b= r> =C2=A0 =C2=A0<a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin= -dev/2013-July/002917.html" rel=3D"noreferrer" target=3D"_blank">https://li= sts.linuxfoundation.<wbr>org/pipermail/bitcoin-dev/<wbr>2013-July/002917.ht= ml</a><br> <span class=3D"HOEnZb"><font color=3D"#888888"><br> --<br> <a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http= s://petertodd.org</a> 'peter'[:-1]@<a href=3D"http://petertodd.org"= rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br> </font></span><br>______________________________<wbr>_________________<br> bitcoin-dev mailing list<br> <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.= <wbr>linuxfoundation.org</a><br> <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org= /mailman/listinfo/bitcoin-<wbr>dev</a><br> <br></blockquote></div><br></div> --001a113db3c09fa0e405492a3c45--