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 3BF0419A5 for ; Wed, 3 Apr 2019 23:03:26 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-qt1-f175.google.com (mail-qt1-f175.google.com [209.85.160.175]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C8C5C7A6 for ; Wed, 3 Apr 2019 23:03:24 +0000 (UTC) Received: by mail-qt1-f175.google.com with SMTP id x12so1069731qts.7 for ; Wed, 03 Apr 2019 16:03:24 -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=meDNqgbJMXUk+LgCPrMhmqvmmO1Avkso4aSKiZfzEXk=; b=GnFubEaCrpfkLJ36QMMRI0DgR/QByzbK0pfYwuINPY31Z/5n1CCjPUNzUsQqFV+GQv KQEmSf9G/VncTePtYSkDZI/ZC5ri1mNmUQGF7uZfEjftDiYaDo4PSwBjBGLX4Fm754sN LQPFI6HMmr4+ZX3x/X+BVRCk/owgKICa192sgoRdF8r63b6vNI+jMWSr02zvaD1wcOe8 WeMATx2QmDjEobOJwdbDfSrVtXVsaCb1iBp3PNEmcGBZ341D81S2PRqZuREO1ScbXZit kKrOqUBeA7bDcM9zgIvdDgvWgHJty/Zli56NNhmvg8zfKbNrtflicjKStDNS0kZfNvLa XGMw== 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=meDNqgbJMXUk+LgCPrMhmqvmmO1Avkso4aSKiZfzEXk=; b=EQjqOlfK87FEB7emSWmpyrZY/B5/MqT31PiCTnl4Har9JYq2wnWUsYRAsTDN3cnlX8 8cezqqqtwNmejQXCotU8V8NZZsiXE/9YVOrLqW6Ex515rlZljhdQH3Vjj4f/6MW9lVHQ 5H7FH5UukrtWo6woz0EpHGYYZfBLNGp5hmxfWXA389U8piYZ3R2qcmxFHqA7BGVs3G/W l1YtqVhI30GE229A030HXdGAvT1vDJKym8Gp7EA8UsgQjVxjo6AwrvJ4AIdBYVmltjJ1 nM5/r7Hs05fkVY/Hy1sHuy1/Ip7y6f/AvdhHzZ1H9V9y2szYwW9BMM3vkJhLiBdTx/+i AuyQ== X-Gm-Message-State: APjAAAXfHXKEgYbeyMmVNyQHnP3gr/yG+7eZm4OCX5HdvF2tYTzzSRbT OLzsM4nb/CZStmu52sm9eisIlZmENZVGBPowfnE= X-Google-Smtp-Source: APXvYqwc9bxY2tx4hrForjYmZ1jOGiD3ME5BDd1YiJlmbepUPiAcGJUciQFJyQ/idm7jDfsy+FBchG3gUYQLSziHegA= X-Received: by 2002:ac8:308a:: with SMTP id v10mr2502782qta.185.1554332603801; Wed, 03 Apr 2019 16:03:23 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Jim Posen Date: Wed, 3 Apr 2019 16:03:12 -0700 Message-ID: To: "James O'Beirne" , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000b665240585a842b2" 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: Thu, 04 Apr 2019 02:12:35 +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: Wed, 03 Apr 2019 23:03:26 -0000 --000000000000b665240585a842b2 Content-Type: text/plain; charset="UTF-8" Big Concept ACK. I think this would be one of the biggest usability improvements for Bitcoin and I see no security issues with the assumevalid approach. I also agree that it's important to start work on this even before the ultimate, perfect accumulator has been designed/tested and the commitment scheme can always be upgraded later on. assumeutxo syncing actually seems pretty orthogonal to the accumulator research. I have a few questions - So any nodes that do an initial sync will stop at the assumeutxo height, serialize a snapshot of the chain state and store it? How many nodes are expected to do this? Any idea how long this takes? Should it be enabled by default? - Would pruned nodes still download all historic blocks to double-check the snapshot or only full nodes that intend to serve block data? - How long are old snapshots retained? Presumably during a new release nodes should keep at least a version back. Without P2P signalling of which snapshots are available, they maybe have to keep all old snapshots or even download old ones. and comments - The snapshot should probably be chunked up to minimize the amount of bandwidth/IO/memory a malicious node could waste before you realize. Also, it would make parallel downloading easier. On Tue, Apr 2, 2019 at 4:43 PM 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 > --000000000000b665240585a842b2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Big Concept ACK. I think this would be one of the biggest = usability improvements for Bitcoin and I see no security issues with the as= sumevalid approach. I also agree that it's important to start work on t= his even before the ultimate, perfect accumulator has been designed/tested = and the commitment scheme can always be upgraded later on. assumeutxo synci= ng actually seems pretty orthogonal to the accumulator research.

I have a few questions

- So any nodes that do a= n initial sync will stop at the assumeutxo height, serialize a snapshot of = the chain state and store it? How many nodes are expected to do this? Any i= dea how long this takes? Should it be enabled by default?
- Would= pruned nodes still download all historic blocks to double-check the snapsh= ot or only full nodes that intend to serve block data?
- How long= are old snapshots retained? Presumably during a new release nodes should k= eep at least a version back. Without P2P signalling of which snapshots are = available, they maybe have to keep all old snapshots or even download old o= nes.

and comments

- The s= napshot should probably be chunked up to minimize the amount of bandwidth/I= O/memory a malicious node could waste before you realize. Also, it would ma= ke parallel downloading easier.

On Tue, Apr 2, 2019 at 4:43 PM J= ames O'Beirne via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org= > wrote:
=
Hi,

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

# Motivation

To start a fully validating bitcoi= n client from scratch, that client currently
needs to perform an = initial block download. To the surprise of no one, IBD=C2=A0
take= s a linear amount time based on the length of the chain's history. For= =C2=A0
clients running on modest hardware under limited bandwidth= constraints,=C2=A0
say a mobile device, completing IBD takes a c= onsiderable amount of time=C2=A0
and thus poses serious usability= challenges.

As a result, having fully validating = clients run on such hardware is rare and
basically unrealistic. C= lients with even moderate resource constraints
are encouraged to = rely on the SPV trust model. Though we have promising
improvement= s to existing SPV modes pending deployment[1], it's worth
thi= nking 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
m= odes, and which is in the spirit of an existing default, `assumevalid`. It = may
help modest clients transact under a security model that clos= ely resembles
full validation within minutes instead of hours or = days.

# assumeutxo

The ba= sic idea is to allow nodes to initialize using a serialized version of the<= /div>
UTXO set rendered by another node at some predetermined height. T= he
initializing node syncs the headers chain from the network, th= en obtains and
loads one of these UTXO snapshots (i.e. a serializ= ed version of the UTXO set
bundled with the block header indicati= ng its "base" and some other metadata).

= Based upon the snapshot, the node is able to quickly reconstruct its chains= tate,
and compares a hash of the resulting UTXO set to a preordai= ned hash hard-coded
in the software a la assumevalid. This all ta= kes ~23 minutes, not accounting for
download of the 3.2GB snapsho= t[2].=C2=A0

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 or= der to achieve full validation. Crucially, even while the
backgro= und 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 put much= thought into this. In concept it doesn't
matter too much whe= re the snapshots come from since their validity is
determined via= content hash.

# Security

Obviously there are some security implications due consideration. While th= is
proposal is in the spirit of assumevalid, practical attacks ma= y become easier.
Under assumevalid, a user can be tricked into tr= ansacting 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].=C2=A0

The same att= ack is made easier in assumeutxo because, unlike in assumevalid,
= the attacker need not construct a valid PoW chain to get the victim's n= ode into
a false state; they simply need to get the user to accep= t a bad `-assumeutxo`
parameter and then supply them an easily ma= de UTXO snapshot containing, say, a
false coin assignment.
<= div>
For this reason, I recommend that if we were to implemen= t assumeutxo, we not
allow its specification via commandline argu= ment[4].

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

# More full= y validating clients

A particularly exciting use-c= ase for assumeutxo is the possibility of mobile
devices functioni= ng as fully validating nodes with access to the complete UTXO
set= (as an alternative to SPV models). The total resource burden needed to sta= rt 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.
=C2=A0=C2=A0
A mobile user could init= ialize an assumed-valid bitcoin node within an hour,
transact imm= ediately, 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 connection= s.

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.
<= br>
---

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

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

I= 9;d like to discuss here whether this is a good fit for Bitcoin conceptuall= y. Concrete
plans for deployment steps should be discussed in the= Github issue, and after all=C2=A0
that my implementation may be = reviewed as a sketch of the specific software
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000b665240585a842b2--