From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 97A78A58 for ; 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 ; Thu, 23 Feb 2017 03:30:39 +0000 (UTC) Received: by mail-yb0-f195.google.com with SMTP id d88so250289ybi.2 for ; 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 Date: Wed, 22 Feb 2017 19:30:37 -0800 Message-ID: To: Peter Todd , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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

This kind of thing is long o= verdue!

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.


- 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 t= o be
implemented as a consensus protocol change to be useful. All the benefits t= hey
provide to full nodes with regard to allowing for old UTXO data to be prune= d -
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, i= n
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, allowi= ng
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 you = that
data on demand.

2) The TXO set is a super-set of the UTXO set; all data in the UTXO set is = also
present in the TXO set. Thus a TXO commitment with spent TXO's pruned i= s
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: n= ot
only are new entries to the TXO set always appended to the end - an operati= on
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=
frequently updated than newer entries.

4) Thus a full node that doesn't have enough local storage to maintain = the full
UTXO set can instead keep track of a TXO commitment, and prune older UTXO&#= 39;s
from it that are unlikely to be spent. In the event those UTXO's are sp= ent,
transactions and blocks spending them can trustlessly provide the necessary=
data to temporarily fill-in the node's local TXO set database, allowing= the
next commitment to be calculated.

5) By *not* committing the TXO commitment in the block itself, we obsolete = my
concept of delayed TXO commitments: you don't need to have calculated t= he TXO
commitment digest to validate a block anyway!


# Deployment Plan

1) Implement a TXO commitment scheme with the ability to efficiently store = 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&#= 39;ve
pruned.

3) Add P2P support to produce, consume, and update TXO unspentness proofs a= s
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 ob= viously
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 you=
trust is a *better* security model than having miners attest to validity: t= he
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 commitmen= ts
is something anyone can do provided they have a full node. Similarly, we co= uld
ship Bitcoin nodes with an assumed-valid TXO commitment, and have those nod= es
fill in the UTXO data from their peers.

However it is a weaker security model, in that a false TXO commitment can m= ore
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
compromise may be to use assumed valid TXO commitments, extending my partia= l
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.framewo= rk),
=C2=A0 =C2=A0Peter Todd, Jul 17th 2013, Bitcoin development mailing list, =C2=A0 =C2=A0https://li= sts.linuxfoundation.org/pipermail/bitcoin-dev/2013-July/002917.ht= ml

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org

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


--001a113db3c09fa0e405492a3c45--