From: Jonas Schnelli <dev@jonasschnelli.ch>
Content-Type: multipart/signed;
	boundary="Apple-Mail=_08A94A04-02EE-4F38-B7DD-9505D85CDD85";
	protocol="application/pgp-signature"; micalg=pgp-sha256
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
Date: Wed, 3 Apr 2019 08:37:31 +0200
References: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com>
To: James O'Beirne <james.obeirne@gmail.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <CAPfvXf+JS6ZhXUieWVxiaNa4uhhWwafCk3odMKy5F_yi=XwngA@mail.gmail.com>
Message-Id: <816FFA03-B4D9-4ECE-AF15-85ACBFA4BA8F@jonasschnelli.ch>
Subject: Re: [bitcoin-dev] assumeutxo and UTXO snapshots
Precedence: list


--Apple-Mail=_08A94A04-02EE-4F38-B7DD-9505D85CDD85
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

Thanks James for the post.

I proposed a similar idea [1] back in 2016 with the difference of =
signing the UTXO-set hash in a gitian-ish way.

While the idea of UTXO-set-syncs are attractive, there are probably =
still significant downsides in usability (compared to models with less =
security), mainly:
* Assume the UTXO set is 6 weeks old (which seems a reasonable age for =
providing enough security) a peer using that snapshot would still =
require to download and verify ~6048 blocks (~7.9GB at 1.3MB blocks,=E2=80=
=A6 probably CPU-days on a phone)
* Do we semi-trust the peer that servers the UTXO set (compared to a =
block or tx which we can validate)? What channel to we use to serve the =
snapshot?

If the goal is to run a full node on a consumer device that is also been =
used for other CPU intense operations (like a phone, etc.), I=E2=80=99m =
not sure if this proposal will lead to a satisfactory user experience.

The longer I think around this problem, the more I lean towards =
accepting the fact that one need to use dedicated hardware in his own =
environment to perform a painless full validation.

/jonas

[1] =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-February/0124=
78.html

> Am 02.04.2019 um 22:43 schrieb James O'Beirne via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org>:
>=20
> Hi,
>=20
> I'd like to discuss assumeutxo, which is an appealing and simple
> optimization in the spirit of assumevalid[0].
>=20
> # Motivation
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> # assumeutxo
>=20
> 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).
>=20
> 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].
>=20
> 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.
>=20
> 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.
>=20
> # Security
>=20
> 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].
>=20
> 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.
>=20
> For this reason, I recommend that if we were to implement assumeutxo, =
we not
> allow its specification via commandline argument[4].
>=20
> 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.
>=20
> # More fully validating clients
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> ---
>=20
> I've created a related issue at our Github repository here:
>   https://github.com/bitcoin/bitcoin/issues/15605
>=20
> and have submitted a draft implementation of snapshot usage via RPC =
here:
>   https://github.com/bitcoin/bitcoin/pull/15606
>=20
> 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.
>=20
> Regards,
> James
>=20
>=20
> [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-L=
161
> [4]: Marco Falke is due credit for this point
> [5]: utreexo: https://www.youtube.com/watch?v=3DedRun-6ubCc
> [6]: Boneh, Bunz, Fisch on accumulators: =
https://eprint.iacr.org/2018/1188
>=20
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


--Apple-Mail=_08A94A04-02EE-4F38-B7DD-9505D85CDD85
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename=signature.asc
Content-Type: application/pgp-signature;
	name=signature.asc
Content-Description: Message signed with OpenPGP

-----BEGIN PGP SIGNATURE-----

iQIzBAEBCAAdFiEEyhopCNzi8TB0xizeHrd2uwPHki0FAlykVKsACgkQHrd2uwPH
ki1IPQ//VJrSuLp594MgKdJSKPY0jtNR8lOgrOncaGCSyzAio90LT+BjgSR6UGDO
B8arYeL9dHYwSmIGh1I7sZIBzPOKRxHNHpA92+cV1pNOlPiwiX9eI5GTGNsswY4/
yXDm/L1hhe3J+3o/Oac/+FFCcopoEu0aM1O978K5cMkndv15GHYi5Bw0vuTq8Kwo
Z/Taiap+i80RrhEPXr86/h7NQpbKMjosJbIZR4kuwQWp8IJZkisDlrlbOS8rXdrw
126c4Rihj/0rGKrV1NBXpwKhmJcGe3s9UDSFX5Bi0yidohuhSxZ7NzH2goKs0AHV
K1zFFoelbGdPJi558qbl2ySHJsWrWaxm+1zAbxAO0KucYlMdIEDmqo2eJKjATWJy
lKAoFFgB/kY9PC2WB6WcwUDP23Z0Km1WFBCuWrnrNJ6ys3QLF9ZiYnfqHEuGF9cR
hG4DJg1TZ38WU7aRyB81YA0B1O7D3Rwz0E5r64YstT+k30v7eFFb3qdf3FQYSEqD
27gBhE2cpkuv3kSN5DIvzZSKv7WXw/vjQPV9aeDA1EKMpER9SIDEKimZmmzqDRtH
KD9Rn6EKbBaWd6ujHYld7y9PMpn6gBD9cKylGmuwBRu989w7qVKJzrbmWVlhX0HS
F7aop+4ZO+qGu3bwcIN7ibuEZ1fduHUCKFXmFTTo3CjuBJrG4+c=
=eJi8
-----END PGP SIGNATURE-----

--Apple-Mail=_08A94A04-02EE-4F38-B7DD-9505D85CDD85--