assumeutxo and UTXO snapshots
16 messages, 2 to 23 Apr 2019. Started by James O'Beirne.
James O'Beirne (4), Luke Dashjr (3), Ethan Scruples (2), Dave Scotese (2), Jim Posen (2), Jonas Schnelli, Peter Todd, Omar Shibli
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
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,… 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’m 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/012478.html
Quoted text (120 lines)
> Am 02.04.2019 um 22:43 schrieb James O'Beirne via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org>: > > 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
This would lead to users trusting third parties (like developers) way too much.
Furthermore, removing the ability for users to easily set it removes the one reasonable use case: where the user has already verified the state at some point previously, and saved the hash (ie, as backup of the UTXO set).
Luke
On Tuesday 02 April 2019 20:43:11 James O'Beirne via bitcoin-dev wrote:
Quoted text (144 lines)
> 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-L1 >61 [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
Jonas,
If we can get mandatory UTXO commitments soft forked into Bitcoin, we get the advantage of a non-growing IBD, which I think everyone would agree is a benefit that, uh, grows over time. The thing I do not see people noticing is that we actually pay little to no security price for this benefit.
To see this, consider Alice, who starts from a UTXO snapshot made at current height - 50,000 and Bob who validates from genesis.
After her partial validation, Alice is satisfied that she is in possession of the UTXO set-- she is in consensus with the rest of the network peers.
However, Bob realizes that there is actually an invalid block at current height - 50,001.
Three things to notice:
1. This scenario essentially cannot happen. There is no way that the miners are going to stack 50,000 blocks on top of an invalid block without the economic majority abandoning the invalid chain.
2. If this scenario DOES happen, Bob has learned about it too late for it to matter to Bob. The blockchain Bob wants to be on is the one that everyone has been using for the last year, whether or not it is besmirched by an invalid block.
3. If this scenario DOES happen, and Bob DOES want to reject the last 50,000 mined blocks as invalid, he may discover to his dismay that in the 1 year since the invalid block, mischievous entities have enough time to mine equally weighted alternative histories from the Genesis block forward to the invalid block, meaning that Bob has no way to use POW to come to consensus with other Bobs out there.
On Wed, Apr 3, 2019 at 3:33 AM Jonas Schnelli via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (201 lines)
> 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,… 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’m 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/012478.html > > > Am 02.04.2019 um 22:43 schrieb James O'Beirne via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org>: > > > > 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 > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
Thanks for the reply, Jonas. I should've figured someone had hit the mailing list with this one before!
In hindsight, I may have overemphasized the use of this for low-powered mobile devices. Indeed I think this may also be a worthwhile optimization for common hardware too.
On the margin, if a user wants to interact with Bitcoin they will download software that allows them to do it immediately - this results in many people defaulting to a light client. If Bitcoin were able to initialize from scratch in a comparable amount of time and then populate the full chain in the background, we may have many more people *incidentally* running full nodes.
Regardless of whether or not we use UTXO snapshots per se, I'd argue that the pattern of doing some kind of quick initialization (whether it's with assumed-valid data, or headers-contingent data like BIP157) and then performing full validation in the background is a good way to ensure that we have a healthier population of full nodes than we would otherwise.
For this reason, and (as Ethan points out) because IBD's linear setup time is infeasible in the long-term, I think this pattern is an obvious direction for the bitcoin client to go.
Quoted text (1 line)
> * 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?
As you note in your post from 2016, where and how we retrieve the snapshot is more or less immaterial because we compare a hash of its contents to a previously specified value that the code ships with (the `assumeutxo` hash). We don't need to trust the source serving it to us, although bandwidth DoS prevention via some kind chunked delivery from peers would be worth thinking about.
Regards, James
On Wed, Apr 3, 2019 at 2:37 AM Jonas Schnelli <dev@jonasschnelli•ch> wrote:
Quoted text (197 lines)
> 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,… 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’m 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/012478.html > > > Am 02.04.2019 um 22:43 schrieb James O'Beirne via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org>: > > > > 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 > >
Every block's hash is smaller than the difficulty at that time. Block 569927's hash was VERY small (started with 21 zeros). The ratio of block hash to difficulty requirement (0xffffffff - difficulty, I think) could be used to identify blocks as "special," thus providing the opportunity to popularize unimportant but memorable-and-therefore-useful details. How can they be useful if they are unimportant? They are useful for sanity checking. For example, if the drunken bishop walk (or some other popular randomart) produced by block 569927's hash looked like a face, that would be memorable: "The block with the smallest hash in 2019 (maybe ever?) looks like a face after the drunken bishop walk."
If a few of these showed up each year, then Bob and/or Alice would have a good chance of seeing that something was wrong if and when they checked. It would not be surprising, given Ethan's assumption that the invalid block Bob found contributed to Alice's UTXOs, that at some point, the history one of them has would be missing the memorable things beginning at some block height because, clearly, one of them has been forked.
Luke's comment that it could "lead to users trusting third parties (like developers) way too much" is pertinent too, but I think an honest abatement of that concern is impossible without teaching everyone C++. "Developers" as an open group (anyone can fork the github repo, find a problem, and make an issue) deserve the trust we put in them, and that's because they're accountable (any such error found in the repo will have been put there by someone). The same thing goes for making it possible to download (*not just the compiled software*, but) the entire UTXO Set if a commitment of it is hardcoded into the software, as James suggests. We all trust "developers" like that, and it's okay. No one holds the "ring of power."
On Wed, Apr 3, 2019 at 8:39 AM Ethan Scruples via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (245 lines)
> Jonas, > > If we can get mandatory UTXO commitments soft forked into Bitcoin, we get > the advantage of a non-growing IBD, which I think everyone would agree is a > benefit that, uh, grows over time. The thing I do not see people noticing > is that we actually pay little to no security price for this benefit. > > To see this, consider Alice, who starts from a UTXO snapshot made at > current height - 50,000 and Bob who validates from genesis. > > After her partial validation, Alice is satisfied that she is in possession > of the UTXO set-- she is in consensus with the rest of the network peers. > > However, Bob realizes that there is actually an invalid block at current > height - 50,001. > > Three things to notice: > > 1. This scenario essentially cannot happen. There is no way that the > miners are going to stack 50,000 blocks on top of an invalid block without > the economic majority abandoning the invalid chain. > > 2. If this scenario DOES happen, Bob has learned about it too late for it > to matter to Bob. The blockchain Bob wants to be on is the one that > everyone has been using for the last year, whether or not it is besmirched > by an invalid block. > > 3. If this scenario DOES happen, and Bob DOES want to reject the last > 50,000 mined blocks as invalid, he may discover to his dismay that in the 1 > year since the invalid block, mischievous entities have enough time to mine > equally weighted alternative histories from the Genesis block forward to > the invalid block, meaning that Bob has no way to use POW to come to > consensus with other Bobs out there. > > On Wed, Apr 3, 2019 at 3:33 AM Jonas Schnelli via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org> wrote: > >> 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,… 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’m 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/012478.html >> >> > Am 02.04.2019 um 22:43 schrieb James O'Beirne via bitcoin-dev < >> bitcoin-dev@lists•linuxfoundation•org>: >> > >> > 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 >> >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation•org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
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:
Quoted text (159 lines)
> 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 >
On Wednesday 03 April 2019 15:39:29 Ethan Scruples via bitcoin-dev wrote:
Quoted text (2 lines)
> If we can get mandatory UTXO commitments soft forked into Bitcoin, we get > the advantage of a non-growing IBD,
No, we don't. This is exactly the danger. UTXO snapshots are NOT an alternative to a real IBD. There are HUGE security implications for this. Frankly, the danger that someone would do such a thing is itself a good reason not to ever add UTXO commitments.
Luke
On Wednesday 03 April 2019 21:39:32 Dave Scotese via bitcoin-dev wrote:
Quoted text (3 lines)
> Luke's comment that it could "lead to users trusting third parties (like > developers) way too much" is pertinent too, but I think an honest abatement > of that concern is impossible without teaching everyone C++.
Learning C++ is something within everyone's capability. Even people who do not wish to learn it can hire someone to perform review for them.
Quoted text (5 lines)
> "Developers" > as an open group (anyone can fork the github repo, find a problem, and make > an issue) deserve the trust we put in them, and that's because they're > accountable (any such error found in the repo will have been put there by > someone).
No, we are not. We explicitly disclaim any warranty, and do not want your trust.
Quoted text (3 lines)
> The same thing goes for making it possible to download (*not > just the compiled software*, but) the entire UTXO Set if a commitment of it > is hardcoded into the software, as James suggests.
Verifying a UTXO set commitment is impossible short of a real IBD. It's not even comparable.
Quoted text (2 lines)
> We all trust > "developers" like that, and it's okay.
No, it isn't okay. There are plenty of fiat options if you want a trust-based currency. Bitcoin is supposed to be something more than that.
Luke
Quoted text (1 line)
> This is exactly the danger. UTXO snapshots are NOT an alternative to a
real IBD. There are HUGE security implications for this.
This is a perfect example of what I am talking about when I say that people do not appear to notice that there is no important security implication to be found here.
If there are huge security implications for this, then I am keen to hear them. In the scenario I have described, what advantage does Bob have over Alice? What actionable information has Bob gained, and what is the action he can take with it in hand? What value does Bob receive in return for the electricity he has spent validating the previous blocks? I cannot find any, but I am open to hearing the answer, and I think others would benefit from knowing it as well.
On Wed, Apr 3, 2019 at 10:49 PM Luke Dashjr <luke@dashjr•org> wrote:
Quoted text (11 lines)
> On Wednesday 03 April 2019 15:39:29 Ethan Scruples via bitcoin-dev wrote: > > If we can get mandatory UTXO commitments soft forked into Bitcoin, we get > > the advantage of a non-growing IBD, > > No, we don't. This is exactly the danger. UTXO snapshots are NOT an > alternative to a real IBD. There are HUGE security implications for this. > Frankly, the danger that someone would do such a thing is itself a good > reason not to ever add UTXO commitments. > > Luke >
Quoted text (5 lines)
> > Learning C++ is something within everyone's capability. Even people who do > not > wish to learn it can hire someone to perform review for them. >
Anyone with enough knowledge of C++ to audit the entire the Bitcoin Core codebase is more than capable of running it with assumeutxo disabled and checking the hard-coded vale themself.
Quoted text (1 line)
>
I recommend that anyone following this thread read through the recent IRC exchange between Greg Maxwell and Luke Dashjr: http://www.erisian.com.au/bitcoin-core-dev/log-2019-04-04.html <http://www.erisian.com.au/bitcoin-core-dev/log-2019-04-04.html>
The conversation starts on line 205 at 2019-04-04T02:54:50.
On Thu, Apr 4, 2019 at 2:38 AM Jim Posen via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (14 lines)
> Learning C++ is something within everyone's capability. Even people who do >> not >> wish to learn it can hire someone to perform review for them. >> > > Anyone with enough knowledge of C++ to audit the entire the Bitcoin Core > codebase is more than capable of running it with assumeutxo disabled and > checking the hard-coded vale themself. > >> _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
On Wed, Apr 03, 2019 at 02:39:32PM -0700, Dave Scotese via bitcoin-dev wrote:
Quoted text (10 lines)
> Every block's hash is smaller than the difficulty at that time. Block > 569927's hash was VERY small (started with 21 zeros). The ratio of block > hash to difficulty requirement (0xffffffff - difficulty, I think) could be > used to identify blocks as "special," thus providing the opportunity to > popularize unimportant but memorable-and-therefore-useful details. How can > they be useful if they are unimportant? They are useful for sanity > checking. For example, if the drunken bishop walk (or some other popular > randomart) produced by block 569927's hash looked like a face, that would > be memorable: "The block with the smallest hash in 2019 (maybe ever?) looks > like a face after the drunken bishop walk."
As hashest smaller than the target have no significance to the Bitcoin consensus I'd suggest not basing any features on that property. It's just as arbitrary as picking whole decimal number block heights, yet has the additional downsides of being harder to compute, and being likely to confuse people as to how the Bitcoin consensus works.
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:
Quoted text (159 lines)
> 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 >
No piece of data that does have significance to the Bitcoin consensus can be memorable because it occurs (about) every ten minutes. In order to get something memorable to provide sanity (let's say, anti-sybil-attack) checking, it has to be rare, but recurrent. The opportunity is actually already there, but it usually goes by without providing the benefits.
For example, I found this blog post <http://www.righto.com/2014/02/ascii-bernanke-wikileaks-photographs.html> by Ken Shirriff who describes artifacts that can be found in the blockchain. These artifacts are not intimately tied to their location in the blockchain, so anyone building an alternative blockchain can relatively easily add the artifacts with the same timestamp and at the same height, masking the counterfeit. In order to prevent that, the memorable thing has to be intimately tied to work-intensive results, like the ratio of the hash to the target. Nelson Mandela's image appearing in the blockchain does NOT prove to me it's the blockchain I can see at blockchain.com right now, but if the smallest block hash in that blockchain, on 12/13/13, after all the zeroes, starts with 3da1 (144 * 65536 times as much work) and is one of the three block hashes from that day that have two occurrences of a double-e (about 256 times more work), then it will. The problem is that I'll probably forget most of those details - but not that Mandela's image went in the blockchain near the end of 2013.
On Sat, Apr 13, 2019 at 12:09 PM Peter Todd <pete@petertodd•org> wrote:
Quoted text (28 lines)
> On Wed, Apr 03, 2019 at 02:39:32PM -0700, Dave Scotese via bitcoin-dev > wrote: > > Every block's hash is smaller than the difficulty at that time. Block > > 569927's hash was VERY small (started with 21 zeros). The ratio of block > > hash to difficulty requirement (0xffffffff - difficulty, I think) could > be > > used to identify blocks as "special," thus providing the opportunity to > > popularize unimportant but memorable-and-therefore-useful details. How > can > > they be useful if they are unimportant? They are useful for sanity > > checking. For example, if the drunken bishop walk (or some other popular > > randomart) produced by block 569927's hash looked like a face, that would > > be memorable: "The block with the smallest hash in 2019 (maybe ever?) > looks > > like a face after the drunken bishop walk." > > As hashest smaller than the target have no significance to the Bitcoin > consensus I'd suggest not basing any features on that property. It's just > as > arbitrary as picking whole decimal number block heights, yet has the > additional > downsides of being harder to compute, and being likely to confuse people > as to > how the Bitcoin consensus works. > > -- > https://petertodd.org 'peter'[:-1]@petertodd.org >
Good morning all,
Over the past weeks I've had a number of conversations with a few frequent contributors about this idea. I've condensed these discussions into a proposal document which you can view here: https://github.com/jamesob/assumeutxo-docs/tree/2019-04-proposal/proposal
The document is structured as an FAQ, and so hopefully it addresses some of the common questions that would come up in this thread. If you'd like to comment, there's an associated pull request here: https://github.com/jamesob/assumeutxo-docs/pull/1
Regards, James
On Tue, Apr 2, 2019 at 4:43 PM James O'Beirne <james.obeirne@gmail•com> wrote:
Quoted text (155 lines)
> 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 > >