MIME-Version: 1.0
References: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com>
In-Reply-To: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com>
From: Omar Shibli <omarshib@gmail.com>
Date: Sun, 14 Apr 2019 16:16:53 +0300
Message-ID: <CAE3EOfjhts_1m2ocrTvLJetcMUHvYgc9B8k5B4aEmgGUMDMW=w@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>, 
	"James O'Beirne" <james.obeirne@gmail.com>
Content-Type: multipart/alternative; boundary="0000000000001ea6bf05867d5a59"
Subject: Re: [bitcoin-dev] assumeutxo and UTXO snapshots
Precedence: list

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

<div><div dir=3D"auto">This sounds really promising to me, I think it could=
 seriously improve the current SPV trust model.</div></div><div dir=3D"auto=
"><br></div><div dir=3D"auto">In abstract these are the possible setups tod=
ay:</div><div dir=3D"auto"><br></div><div dir=3D"auto">Full node: All histo=
ry, 100% monetary sovereignty.</div><div dir=3D"auto"><br></div><div dir=3D=
"auto">SPV: fancy term to Electrum trust model, random selection of nodes, =
with full delegation of monetary responsibility.</div><div dir=3D"auto"><br=
></div><div dir=3D"auto">I think in that spirit a hybrid approach of full n=
ode + spv.</div><div dir=3D"auto"><br></div><div dir=3D"auto">As follows:</=
div><div dir=3D"auto">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.</div><div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"g=
mail_attr">On Wed, Apr 3, 2019 at 2:43 AM James O&#39;Beirne via bitcoin-de=
v &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@=
lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmai=
l_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left=
:1ex"><div dir=3D"ltr"><div dir=3D"ltr"><div>Hi,<br></div><div><br></div><d=
iv>I&#39;d like to discuss assumeutxo, which is an appealing and simple=C2=
=A0</div><div>optimization in the spirit of assumevalid[0].</div><div><br><=
/div><div># Motivation</div><div><br></div><div>To start a fully validating=
 bitcoin client from scratch, that client currently</div><div>needs to perf=
orm an initial block download. To the surprise of no one, IBD=C2=A0</div><d=
iv>takes a linear amount time based on the length of the chain&#39;s histor=
y. For=C2=A0</div><div>clients running on modest hardware under limited ban=
dwidth constraints,=C2=A0</div><div>say a mobile device, completing IBD tak=
es a considerable amount of time=C2=A0</div><div>and thus poses serious usa=
bility challenges.</div><div><br></div><div>As a result, having fully valid=
ating clients run on such hardware is rare and</div><div>basically unrealis=
tic. Clients with even moderate resource constraints</div><div>are encourag=
ed to rely on the SPV trust model. Though we have promising</div><div>impro=
vements to existing SPV modes pending deployment[1], it&#39;s worth</div><d=
iv>thinking about a mechanism that would allow such clients to use trust</d=
iv><div>models closer to full validation.</div><div><br></div><div>The subj=
ect of this mail is a proposal for a complementary alternative to SPV</div>=
<div>modes, and which is in the spirit of an existing default, `assumevalid=
`. It may</div><div>help modest clients transact under a security model tha=
t closely resembles</div><div>full validation within minutes instead of hou=
rs or days.</div><div><br></div><div># assumeutxo</div><div><br></div><div>=
The basic idea is to allow nodes to initialize using a serialized version o=
f the</div><div>UTXO set rendered by another node at some predetermined hei=
ght. The</div><div>initializing node syncs the headers chain from the netwo=
rk, then obtains and</div><div>loads one of these UTXO snapshots (i.e. a se=
rialized version of the UTXO set</div><div>bundled with the block header in=
dicating 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 =
chainstate,</div><div>and compares a hash of the resulting UTXO set to a pr=
eordained hash hard-coded</div><div>in the software a la assumevalid. This =
all takes ~23 minutes, not accounting for</div><div>download of the 3.2GB s=
napshot[2].=C2=A0</div><div><br></div><div>The node then syncs to the netwo=
rk 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 order to achieve full validation. Crucially, even while the</div><div>b=
ackground 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 pu=
t much thought into this. In concept it doesn&#39;t</div><div>matter too mu=
ch where the snapshots come from since their validity is</div><div>determin=
ed via content hash.</div><div><br></div><div># Security</div><div><br></di=
v><div>Obviously there are some security implications due consideration. Wh=
ile this</div><div>proposal is in the spirit of assumevalid, practical atta=
cks may become easier.</div><div>Under assumevalid, a user can be tricked i=
nto transacting under a false history</div><div>if an attacker convinces th=
em to start bitcoind with a malicious `-assumevalid`</div><div>parameter, s=
ybils 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 sa=
me attack 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 node into</div><div>a false state; they simply need to get the user to=
 accept a bad `-assumeutxo`</div><div>parameter and then supply them an eas=
ily made 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 im=
plement assumeutxo, we not</div><div>allow its specification via commandlin=
e argument[4].</div><div><br></div><div>Beyond this risk, I can&#39;t think=
 of material differences in security relative to</div><div>assumevalid, tho=
ugh I appeal to the list for help with this.</div><div><br></div><div># Mor=
e fully validating clients</div><div><br></div><div>A particularly exciting=
 use-case for assumeutxo is the possibility of mobile</div><div>devices fun=
ctioning as fully validating nodes with access to the complete UTXO</div><d=
iv>set (as an alternative to SPV models). The total resource burden needed =
to start a node</div><div>from scratch based on a snapshot is, at time of w=
riting, a ~(3.2GB</div><div>+ blocks_to_tip * 4MB) download and a few minut=
es of processing time, which sounds</div><div>manageable for many mobile de=
vices currently in use.</div><div>=C2=A0=C2=A0</div><div>A mobile user coul=
d initialize an assumed-valid bitcoin node within an hour,</div><div>transa=
ct immediately, and complete a pruned full validation of their</div><div>as=
sumed-valid chain over the next few days, perhaps only doing the background=
</div><div>IBD when their device has access to suitable high-bandwidth conn=
ections.</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 i=
magine an analogous process that would allow very fast</div><div>startup us=
ing 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://g=
ithub.com/bitcoin/bitcoin/issues/15605" target=3D"_blank">https://github.co=
m/bitcoin/bitcoin/issues/15605</a></div><div><br></div><div>and have submit=
ted a draft implementation of snapshot usage via RPC here:</div><div>=C2=A0=
 <a href=3D"https://github.com/bitcoin/bitcoin/pull/15606" target=3D"_blank=
">https://github.com/bitcoin/bitcoin/pull/15606</a></div><div><br></div><di=
v>I&#39;d like to discuss here whether this is a good fit for Bitcoin conce=
ptually. Concrete</div><div>plans for deployment steps should be discussed =
in the Github issue, and after all=C2=A0</div><div>that my implementation m=
ay be reviewed as a sketch of the specific software</div><div>changes neces=
sary.</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/=
release-0.14.0/#assumed-valid-blocks" target=3D"_blank">https://bitcoincore=
.org/en/2017/03/08/release-0.14.0/#assumed-valid-blocks</a></div><div>[1]: =
<a href=3D"https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki" =
target=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0157.medi=
awiki</a></div><div>[2]: as tested at height 569895, on a 12 core Intel Xeo=
n Silver 4116 CPU @ 2.10GHz</div><div>[3]: <a href=3D"https://github.com/bi=
tcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L161" target=3D"_blank"=
>https://github.com/bitcoin/bitcoin/blob/84d0fdc/src/chainparams.cpp#L145-L=
161</a></div><div>[4]: Marco Falke is due credit for this point</div><div>[=
5]: utreexo: <a href=3D"https://www.youtube.com/watch?v=3DedRun-6ubCc" targ=
et=3D"_blank">https://www.youtube.com/watch?v=3DedRun-6ubCc</a></div><div>[=
6]: Boneh, Bunz, Fisch on accumulators: <a href=3D"https://eprint.iacr.org/=
2018/1188" target=3D"_blank">https://eprint.iacr.org/2018/1188</a></div><di=
v><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></div>-- <br><div dir=3D"ltr" class=3D"gmail_signature" =
data-smartmail=3D"gmail_signature">Sent from Gmail Mobile</div>

--0000000000001ea6bf05867d5a59--