MIME-Version: 1.0
References: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com>
In-Reply-To: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com>
From: Jim Posen <jim.posen@gmail.com>
Date: Wed, 3 Apr 2019 16:03:12 -0700
Message-ID: <CADZtCSjx-YeGzfs4DtuXZ-8y4tWiHB7Luh133S0ZPbQzWz-dbw@mail.gmail.com>
To: "James O'Beirne" <james.obeirne@gmail.com>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000b665240585a842b2"
Subject: Re: [bitcoin-dev] assumeutxo and UTXO snapshots
Precedence: list

--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

<div dir=3D"ltr">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&#39;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.<div><br></=
div><div>I have a few questions<div><br></div><div>- 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?</div><div>- Would=
 pruned nodes still download all historic blocks to double-check the snapsh=
ot or only full nodes that intend to serve block data?</div><div>- 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.</div><div><br></div><div>and comments</div><div><br></div><div>- 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.</div></div></div><br><div class=3D"gmail_qu=
ote"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, Apr 2, 2019 at 4:43 PM J=
ames O&#39;Beirne via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.l=
inuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org=
</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">=
<div dir=3D"ltr"><div dir=3D"ltr"><div>Hi,<br></div><div><br></div><div>I&#=
39;d like to discuss assumeutxo, which is an appealing and simple=C2=A0</di=
v><div>optimization in the spirit of assumevalid[0].</div><div><br></div><d=
iv># Motivation</div><div><br></div><div>To start a fully validating bitcoi=
n client from scratch, that client currently</div><div>needs to perform an =
initial block download. To the surprise of no one, IBD=C2=A0</div><div>take=
s a linear amount time based on the length of the chain&#39;s history. For=
=C2=A0</div><div>clients running on modest hardware under limited bandwidth=
 constraints,=C2=A0</div><div>say a mobile device, completing IBD takes a c=
onsiderable amount of time=C2=A0</div><div>and thus poses serious usability=
 challenges.</div><div><br></div><div>As a result, having fully validating =
clients run on such hardware is rare and</div><div>basically unrealistic. C=
lients with even moderate resource constraints</div><div>are encouraged to =
rely on the SPV trust model. Though we have promising</div><div>improvement=
s to existing SPV modes pending deployment[1], it&#39;s worth</div><div>thi=
nking about a mechanism that would allow such clients to use trust</div><di=
v>models closer to full validation.</div><div><br></div><div>The subject of=
 this mail is a proposal for a complementary alternative to SPV</div><div>m=
odes, and which is in the spirit of an existing default, `assumevalid`. It =
may</div><div>help modest clients transact under a security model that clos=
ely resembles</div><div>full validation within minutes instead of hours or =
days.</div><div><br></div><div># assumeutxo</div><div><br></div><div>The ba=
sic idea is to allow nodes to initialize using a serialized version of the<=
/div><div>UTXO set rendered by another node at some predetermined height. T=
he</div><div>initializing node syncs the headers chain from the network, th=
en obtains and</div><div>loads one of these UTXO snapshots (i.e. a serializ=
ed version of the UTXO set</div><div>bundled with the block header indicati=
ng its &quot;base&quot; and some other metadata).</div><div><br></div><div>=
Based upon the snapshot, the node is able to quickly reconstruct its chains=
tate,</div><div>and compares a hash of the resulting UTXO set to a preordai=
ned hash hard-coded</div><div>in the software a la assumevalid. This all ta=
kes ~23 minutes, not accounting for</div><div>download of the 3.2GB snapsho=
t[2].=C2=A0</div><div><br></div><div>The node then syncs to the network tip=
 and afterwards begins a simultaneous</div><div>background validation (i.e.=
, a conventional IBD) up to the base height of the</div><div>snapshot in or=
der to achieve full validation. Crucially, even while the</div><div>backgro=
und validation is happening the node can validate incoming blocks and</div>=
<div>transact with the benefit of the full (assumed-valid) UTXO set.</div><=
div><br></div><div>Snapshots could be obtained from multiple separate peers=
 in the same manner as</div><div>block download, but I haven&#39;t put much=
 thought into this. In concept it doesn&#39;t</div><div>matter too much whe=
re the snapshots come from since their validity is</div><div>determined via=
 content hash.</div><div><br></div><div># Security</div><div><br></div><div=
>Obviously there are some security implications due consideration. While th=
is</div><div>proposal is in the spirit of assumevalid, practical attacks ma=
y become easier.</div><div>Under assumevalid, a user can be tricked into tr=
ansacting under a false history</div><div>if an attacker convinces them to =
start bitcoind with a malicious `-assumevalid`</div><div>parameter, sybils =
their node, and then feeds them a bogus chain encompassing</div><div>all of=
 the hard-coded checkpoints[3].=C2=A0</div><div><br></div><div>The same att=
ack is made easier in assumeutxo because, unlike in assumevalid,</div><div>=
the attacker need not construct a valid PoW chain to get the victim&#39;s n=
ode into</div><div>a false state; they simply need to get the user to accep=
t a bad `-assumeutxo`</div><div>parameter and then supply them an easily ma=
de UTXO snapshot containing, say, a</div><div>false coin assignment.</div><=
div><br></div><div>For this reason, I recommend that if we were to implemen=
t assumeutxo, we not</div><div>allow its specification via commandline argu=
ment[4].</div><div><br></div><div>Beyond this risk, I can&#39;t think of ma=
terial differences in security relative to</div><div>assumevalid, though I =
appeal to the list for help with this.</div><div><br></div><div># More full=
y validating clients</div><div><br></div><div>A particularly exciting use-c=
ase for assumeutxo is the possibility of mobile</div><div>devices functioni=
ng as fully validating nodes with access to the complete UTXO</div><div>set=
 (as an alternative to SPV models). The total resource burden needed to sta=
rt a node</div><div>from scratch based on a snapshot is, at time of writing=
, a ~(3.2GB</div><div>+ blocks_to_tip * 4MB) download and a few minutes of =
processing time, which sounds</div><div>manageable for many mobile devices =
currently in use.</div><div>=C2=A0=C2=A0</div><div>A mobile user could init=
ialize an assumed-valid bitcoin node within an hour,</div><div>transact imm=
ediately, and complete a pruned full validation of their</div><div>assumed-=
valid chain over the next few days, perhaps only doing the background</div>=
<div>IBD when their device has access to suitable high-bandwidth connection=
s.</div><div><br></div><div>If we end up implementing an accumulator-based =
UTXO scaling design[5][6] down</div><div>the road, it&#39;s easy to imagine=
 an analogous process that would allow very fast</div><div>startup using an=
 accumulator of a few kilobytes in lieu of a multi-GB snapshot.</div><div><=
br></div><div>---</div><div><br></div><div>I&#39;ve created a related issue=
 at our Github repository here:</div><div>=C2=A0 <a href=3D"https://github.=
com/bitcoin/bitcoin/issues/15605" target=3D"_blank">https://github.com/bitc=
oin/bitcoin/issues/15605</a></div><div><br></div><div>and have submitted a =
draft implementation of snapshot usage via RPC here:</div><div>=C2=A0 <a hr=
ef=3D"https://github.com/bitcoin/bitcoin/pull/15606" target=3D"_blank">http=
s://github.com/bitcoin/bitcoin/pull/15606</a></div><div><br></div><div>I=
9;d like to discuss here whether this is a good fit for Bitcoin conceptuall=
y. Concrete</div><div>plans for deployment steps should be discussed in the=
 Github issue, and after all=C2=A0</div><div>that my implementation may be =
reviewed as a sketch of the specific software</div><div>changes necessary.<=
/div><div><br></div><div>Regards,</div><div>James</div><div><br></div><div>=
<br></div><div>[0]: <a href=3D"https://bitcoincore.org/en/2017/03/08/releas=
e-0.14.0/#assumed-valid-blocks" target=3D"_blank">https://bitcoincore.org/e=
n/2017/03/08/release-0.14.0/#assumed-valid-blocks</a></div><div>[1]: <a hre=
f=3D"https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki" target=
=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki<=
/a></div><div>[2]: as tested at height 569895, on a 12 core Intel Xeon Silv=
er 4116 CPU @ 2.10GHz</div><div>[3]: <a href=3D"https://github.com/bitcoin/=
bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161" target=3D"_blank">https=
://github.com/bitcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161</a=
></div><div>[4]: Marco Falke is due credit for this point</div><div>[5]: ut=
reexo: <a href=3D"https://www.youtube.com/watch?v=3DedRun-6ubCc" target=3D"=
_blank">https://www.youtube.com/watch?v=3DedRun-6ubCc</a></div><div>[6]: Bo=
neh, Bunz, Fisch on accumulators: <a href=3D"https://eprint.iacr.org/2018/1=
188" target=3D"_blank">https://eprint.iacr.org/2018/1188</a></div><div><br>=
</div></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000b665240585a842b2--