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 164392C for ; Sun, 14 Apr 2019 13:17:07 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it1-f196.google.com (mail-it1-f196.google.com [209.85.166.196]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CD83E1C0 for ; Sun, 14 Apr 2019 13:17:05 +0000 (UTC) Received: by mail-it1-f196.google.com with SMTP id 139so22706710ita.4 for ; Sun, 14 Apr 2019 06:17:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=9w+4KDEsTdNEIkrHnnpL5KDikCs/4O9+9kL3bmBhfWg=; b=PKYJc9LOoUfNekKGlQmgzin75YPNI44UnOfj4WrmqzHhfZCiRK6jbvbuaepcyQjRLQ ZFoST54n50pYaCgrQTSj7dhwSEiDb4NA7xjBgJNzDtSqK5hSOjwzLkEgG0WCe+RbVmQL /OXBcO8W3v2n+HCkOyuL/rDR3IUmQg1rYzZiCTwfzeSQtiUbc4AMapNzIjfKEDLg8m4D desWfdsc8yaYBIewUwEjFLW0Xpuivj2Aztr6OnWpHSXVlbwolgb11We6y7/XBwF+FILV 4wg20Oa+ObuIgHm/uHZyn5Y1tZxFij7q4RJD1IApKQ07f89pHAEWClXC2i9UkUy79X/Q +cig== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=9w+4KDEsTdNEIkrHnnpL5KDikCs/4O9+9kL3bmBhfWg=; b=I180QNvCMWgTXvnNc59L1bnxA69UFmjur4uUKSuIhSNPGWdWwuALyWf/YviuS7lhSx zWCz3tkp+HvwAz/6huOeB1rkDrQ2iujvOVWkhs3UDVUv4y0cbAVf5aWsjEbby1JpCZV8 j27VLPzYoYge5g3zFKR3+FJcHHO5zG1UQei6P1DdGdByq+N8oPV3aYnJTThtq/yfySKR Rq2t9+jg0Rih6oaaD7PDHlHrP3hdn9G9yU1sdB0O1/rOtwo9ZnqYm+yenyPp5/tYzbJI mpLeDnR7uR77mJaSChE6RloScvROJ0l2Tnc44ow9y4Dk2eHLZg/tK1imrTLhQ0m4uGyE whmQ== X-Gm-Message-State: APjAAAWgG2Tzpu7Z0X7aTwCFhipHVIWa20yY39zlA9gGpNFTCUGRPOwt WjG5Bv3xHrNM2/rM1JNQexUDpqYDF5YMGPU1vrdmhQjr X-Google-Smtp-Source: APXvYqwEcAjo7ykRMaQj3co71n2sL0eq+jWAA4UtbXmqxsgQHenlgcTYPnEpr2jnfqsocN/L6y4fmdnazy0AXZdZ2CQ= X-Received: by 2002:a05:660c:40d:: with SMTP id c13mr12604634itk.115.1555247824543; Sun, 14 Apr 2019 06:17:04 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Omar Shibli Date: Sun, 14 Apr 2019 16:16:53 +0300 Message-ID: To: Bitcoin Protocol Discussion , "James O'Beirne" Content-Type: multipart/alternative; boundary="0000000000001ea6bf05867d5a59" 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 X-Mailman-Approved-At: Sun, 14 Apr 2019 18:54:19 +0000 Subject: Re: [bitcoin-dev] assumeutxo and UTXO snapshots 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: Sun, 14 Apr 2019 13:17:07 -0000 --0000000000001ea6bf05867d5a59 Content-Type: text/plain; charset="UTF-8" This sounds really promising to me, I think it could seriously improve the current SPV trust model. In abstract these are the possible setups today: Full node: All history, 100% monetary sovereignty. SPV: fancy term to Electrum trust model, random selection of nodes, with full delegation of monetary responsibility. I think in that spirit a hybrid approach of full node + spv. As follows: Hardware spv with only genesis hash block seeded, as a safe bootstrap, from there only headers is needed for validation, and ongoing new fresh blocks and associated historic blocks for conducting transactions. On Wed, Apr 3, 2019 at 2:43 AM James O'Beirne via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi, > > I'd like to discuss assumeutxo, which is an appealing and simple > optimization in the spirit of assumevalid[0]. > > # Motivation > > To start a fully validating bitcoin client from scratch, that client > currently > needs to perform an initial block download. To the surprise of no one, IBD > takes a linear amount time based on the length of the chain's history. For > clients running on modest hardware under limited bandwidth constraints, > say a mobile device, completing IBD takes a considerable amount of time > and thus poses serious usability challenges. > > As a result, having fully validating clients run on such hardware is rare > and > basically unrealistic. Clients with even moderate resource constraints > are encouraged to rely on the SPV trust model. Though we have promising > improvements to existing SPV modes pending deployment[1], it's worth > thinking about a mechanism that would allow such clients to use trust > models closer to full validation. > > The subject of this mail is a proposal for a complementary alternative to > SPV > modes, and which is in the spirit of an existing default, `assumevalid`. > It may > help modest clients transact under a security model that closely resembles > full validation within minutes instead of hours or days. > > # assumeutxo > > The basic idea is to allow nodes to initialize using a serialized version > of the > UTXO set rendered by another node at some predetermined height. The > initializing node syncs the headers chain from the network, then obtains > and > loads one of these UTXO snapshots (i.e. a serialized version of the UTXO > set > bundled with the block header indicating its "base" and some other > metadata). > > Based upon the snapshot, the node is able to quickly reconstruct its > chainstate, > and compares a hash of the resulting UTXO set to a preordained hash > hard-coded > in the software a la assumevalid. This all takes ~23 minutes, not > accounting for > download of the 3.2GB snapshot[2]. > > The node then syncs to the network tip and afterwards begins a simultaneous > background validation (i.e., a conventional IBD) up to the base height of > the > snapshot in order to achieve full validation. Crucially, even while the > background validation is happening the node can validate incoming blocks > and > transact with the benefit of the full (assumed-valid) UTXO set. > > Snapshots could be obtained from multiple separate peers in the same > manner as > block download, but I haven't put much thought into this. In concept it > doesn't > matter too much where the snapshots come from since their validity is > determined via content hash. > > # Security > > Obviously there are some security implications due consideration. While > this > proposal is in the spirit of assumevalid, practical attacks may become > easier. > Under assumevalid, a user can be tricked into transacting under a false > history > if an attacker convinces them to start bitcoind with a malicious > `-assumevalid` > parameter, sybils their node, and then feeds them a bogus chain > encompassing > all of the hard-coded checkpoints[3]. > > The same attack is made easier in assumeutxo because, unlike in > assumevalid, > the attacker need not construct a valid PoW chain to get the victim's node > into > a false state; they simply need to get the user to accept a bad > `-assumeutxo` > parameter and then supply them an easily made UTXO snapshot containing, > say, a > false coin assignment. > > For this reason, I recommend that if we were to implement assumeutxo, we > not > allow its specification via commandline argument[4]. > > Beyond this risk, I can't think of material differences in security > relative to > assumevalid, though I appeal to the list for help with this. > > # More fully validating clients > > A particularly exciting use-case for assumeutxo is the possibility of > mobile > devices functioning as fully validating nodes with access to the complete > UTXO > set (as an alternative to SPV models). The total resource burden needed to > start a node > from scratch based on a snapshot is, at time of writing, a ~(3.2GB > + blocks_to_tip * 4MB) download and a few minutes of processing time, > which sounds > manageable for many mobile devices currently in use. > > A mobile user could initialize an assumed-valid bitcoin node within an > hour, > transact immediately, and complete a pruned full validation of their > assumed-valid chain over the next few days, perhaps only doing the > background > IBD when their device has access to suitable high-bandwidth connections. > > If we end up implementing an accumulator-based UTXO scaling design[5][6] > down > the road, it's easy to imagine an analogous process that would allow very > fast > startup using an accumulator of a few kilobytes in lieu of a multi-GB > snapshot. > > --- > > I've created a related issue at our Github repository here: > https://github.com/bitcoin/bitcoin/issues/15605 > > and have submitted a draft implementation of snapshot usage via RPC here: > https://github.com/bitcoin/bitcoin/pull/15606 > > I'd like to discuss here whether this is a good fit for Bitcoin > conceptually. Concrete > plans for deployment steps should be discussed in the Github issue, and > after all > that my implementation may be reviewed as a sketch of the specific software > changes necessary. > > Regards, > James > > > [0]: > https://bitcoincore.org/en/2017/03/08/release-0.14.0/#assumed-valid-blocks > [1]: https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki > [2]: as tested at height 569895, on a 12 core Intel Xeon Silver 4116 CPU @ > 2.10GHz > [3]: > https://github.com/bitcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161 > [4]: Marco Falke is due credit for this point > [5]: utreexo: https://www.youtube.com/watch?v=edRun-6ubCc > [6]: Boneh, Bunz, Fisch on accumulators: https://eprint.iacr.org/2018/1188 > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > -- Sent from Gmail Mobile --0000000000001ea6bf05867d5a59 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
This sounds really promising to me, I think it could= seriously improve the current SPV trust model.

In abstract these are the possible setups tod= ay:

Full node: All histo= ry, 100% monetary sovereignty.

SPV: fancy term to Electrum trust model, random selection of nodes, = with full delegation of monetary responsibility.
I think in that spirit a hybrid approach of full n= ode + spv.

As follows:
Hardware spv with only genesis hash block seeded, as = a safe bootstrap, from there only headers is needed for validation, and ong= oing new fresh blocks and associated historic blocks for conducting transac= tions.

On Wed, Apr 3, 2019 at 2:43 AM James O'Beirne via bitcoin-de= v <bitcoin-dev@= lists.linuxfoundation.org> wrote:
Hi,

I'd like to discuss assumeutxo, which is an appealing and simple=C2= =A0
optimization in the spirit of assumevalid[0].

<= /div>
# Motivation

To start a fully validating= bitcoin client from scratch, that client currently
needs to perf= orm an initial block download. To the surprise of no one, IBD=C2=A0
takes a linear amount time based on the length of the chain's histor= y. For=C2=A0
clients running on modest hardware under limited ban= dwidth constraints,=C2=A0
say a mobile device, completing IBD tak= es a considerable amount of time=C2=A0
and thus poses serious usa= bility challenges.

As a result, having fully valid= ating clients run on such hardware is rare and
basically unrealis= tic. Clients with even moderate resource constraints
are encourag= ed to rely on the SPV trust model. Though we have promising
impro= vements to existing SPV modes pending deployment[1], it's worth
thinking about a mechanism that would allow such clients to use trust
models closer to full validation.

The subj= ect of this mail is a proposal for a complementary alternative to SPV
=
modes, and which is in the spirit of an existing default, `assumevalid= `. It may
help modest clients transact under a security model tha= t closely resembles
full validation within minutes instead of hou= rs or days.

# assumeutxo

= The basic idea is to allow nodes to initialize using a serialized version o= f the
UTXO set rendered by another node at some predetermined hei= ght. The
initializing node syncs the headers chain from the netwo= rk, then obtains and
loads one of these UTXO snapshots (i.e. a se= rialized version of the UTXO set
bundled with the block header in= dicating its "base" and some other metadata).

Based upon the snapshot, the node is able to quickly reconstruct its = chainstate,
and compares a hash of the resulting UTXO set to a pr= eordained hash hard-coded
in the software a la assumevalid. This = all takes ~23 minutes, not accounting for
download of the 3.2GB s= napshot[2].=C2=A0

The node then syncs to the netwo= rk tip and afterwards begins a simultaneous
background validation= (i.e., a conventional IBD) up to the base height of the
snapshot= in order to achieve full validation. Crucially, even while the
b= ackground validation is happening the node can validate incoming blocks and=
transact with the benefit of the full (assumed-valid) UTXO set.<= /div>

Snapshots could be obtained from multiple separate= peers in the same manner as
block download, but I haven't pu= t much thought into this. In concept it doesn't
matter too mu= ch where the snapshots come from since their validity is
determin= ed via content hash.

# Security

Obviously there are some security implications due consideration. Wh= ile this
proposal is in the spirit of assumevalid, practical atta= cks may become easier.
Under assumevalid, a user can be tricked i= nto transacting under a false history
if an attacker convinces th= em to start bitcoind with a malicious `-assumevalid`
parameter, s= ybils their node, and then feeds them a bogus chain encompassing
= all of the hard-coded checkpoints[3].=C2=A0

The sa= me attack is made easier in assumeutxo because, unlike in assumevalid,
the attacker need not construct a valid PoW chain to get the victim&#= 39;s node into
a false state; they simply need to get the user to= accept a bad `-assumeutxo`
parameter and then supply them an eas= ily made UTXO snapshot containing, say, a
false coin assignment.<= /div>

For this reason, I recommend that if we were to im= plement assumeutxo, we not
allow its specification via commandlin= e argument[4].

Beyond this risk, I can't think= of material differences in security relative to
assumevalid, tho= ugh I appeal to the list for help with this.

# Mor= e fully validating clients

A particularly exciting= use-case for assumeutxo is the possibility of mobile
devices fun= ctioning as fully validating nodes with access to the complete UTXO
set (as an alternative to SPV models). The total resource burden needed = to start a node
from scratch based on a snapshot is, at time of w= riting, a ~(3.2GB
+ blocks_to_tip * 4MB) download and a few minut= es of processing time, which sounds
manageable for many mobile de= vices currently in use.
=C2=A0=C2=A0
A mobile user coul= d initialize an assumed-valid bitcoin node within an hour,
transa= ct immediately, and complete a pruned full validation of their
as= sumed-valid chain over the next few days, perhaps only doing the background=
IBD when their device has access to suitable high-bandwidth conn= ections.

If we end up implementing an accumulator-= based UTXO scaling design[5][6] down
the road, it's easy to i= magine an analogous process that would allow very fast
startup us= ing an accumulator of a few kilobytes in lieu of a multi-GB snapshot.
=

---

I've created a related= issue at our Github repository here:

and have submit= ted a draft implementation of snapshot usage via RPC here:

I'd like to discuss here whether this is a good fit for Bitcoin conce= ptually. Concrete
plans for deployment steps should be discussed = in the Github issue, and after all=C2=A0
that my implementation m= ay be reviewed as a sketch of the specific software
changes neces= sary.

Regards,
James


[2]: as tested at height 569895, on a 12 core Intel Xeo= n Silver 4116 CPU @ 2.10GHz
[4]: Marco Falke is due credit for this point
[= 6]: Boneh, Bunz, Fisch on accumulators: https://eprint.iacr.org/2018/1188

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--
Sent from Gmail Mobile
--0000000000001ea6bf05867d5a59--