path: root/0e/2002c4cc479fed92bf5ffacf1d0b4aea9714db

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">&lt;<a href=3D"mailto:=
bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.=
linuxfoundation.org</a>&gt;</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&#39;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&#39;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&#39;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&#39;s are sp=
ent,<br>
transactions and blocks spending them can trustlessly provide the necessary=
<br>
data to temporarily fill-in the node&#39;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&#39;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&#39;s also possible to produce=
<br>
serialized UTXO snapshots for bootstrapping new nodes. Equally, it&#39;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> &#39;peter&#39;[:-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--