Discussion:
Protocol-Level Pruning
Add Reply
Marc Bevand via bitcoin-dev
2017-11-16 16:56:46 UTC
Reply
Permalink
Raw Message
It occurred to me that we could push the classic concept of pruning even
further: we could significantly shrink the blockchain as well as reduce the
amount of network traffic during initial block download by doing something
I would call protocol-level pruning. This would, as of today, reduce the
size of the blockchain by a factor of 50, hence enabling massive on-chain
scaling.

The idea behind PLP is to serialize the UTXO set in a standardized way, and
publish a hash of it in the block header so that the blockchain commits to
it. Since hashing and verifying it is a moderately intensive operation,
perhaps the UTXO set hash should be published only once every 576 blocks (4
days).

When a new Bitcoin node joins the network, it would download the block
headers only (not the block data), it would identify the most recent block
containing the UTXO set hash, and download the UTXO set from peers. From
that point on, it downloads and verifies all blocks as normal.

Every 576 blocks, nodes serialize and verify that their UTXO set hash
matches the one published in the blockchain. Doing so becomes a new part of
consensus rules. The last 576 blocks could then be permanently discarded as
they are no longer useful.

Today the serialized UTXO set is about 3GB and the blockchain is about
150GB. Therefore PLP would cut down the amount of data stored by full nodes
by a factor of ~50 as they would have to store only the UTXO set plus at
most 576 blocks.

One trivial optimization is possible: to avoid hashing the entire UTXO set
every 576 blocks (which would take multiple seconds even on a fast
machine), the UTXO set serialization could be a sparse merkle tree
<https://eprint.iacr.org/2016/683.pdf> which would allow on-the fly
recomputation of the hash as new blocks are mined: when a UTXO is added to
(or removed from) the tree, only a small number of hash operations are
needed to recalculate the UTXO set merkle tree root hash.

Maybe we don't even need sparse merkle trees, but a regular merkle tree
would suffice: the tree leaves would be small groups of UTXOs (some bits in
the ID/hash of a UTXO would determine which leaf it belongs to.)

Unlike classic pruning mode, *ALL* full nodes on the network could switch
to PLP. There is no need for any node to archive the entire blockchain any
more.

I can think of one downside of PLP: nodes would no longer be able to handle
reorgs that go further back than the last UTXO set hash published on the
chain (since previous blocks have been discarded). So, perhaps keeping
around the last N*576 blocks (N=10?) would be a sufficient workaround.

Thoughts?

-Marc
Bryan Bishop via bitcoin-dev
2017-11-16 17:14:47 UTC
Reply
Permalink
Raw Message
It's not clear to me if you are have looked at the previous UTXO set
commitment proposals.

some utxo set commitment bookmarks (a little old)
http://diyhpl.us/~bryan/irc/bitcoin/utxo-commitments-or-fraud-proofs.stdout.txt

TXO bitfields
http://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2017-07-08-bram-cohen-merkle-sets/

delayed TXO commitments
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html

TXO commitments do not need a soft-fork to be useful
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013591.html

rolling UTXO set hashes
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html

lotta other resources available, including source code proposals..

- Bryan
http://heybryan.org/
1 512 203 0507
Marc Bevand via bitcoin-dev
2017-11-16 17:19:13 UTC
Reply
Permalink
Raw Message
Ah, thanks, I suspected the idea was too simple and must have been
discussed before, but somehow I missed these proposals. I've got some
reading to do.

-Marc
Post by Bryan Bishop via bitcoin-dev
It's not clear to me if you are have looked at the previous UTXO set
commitment proposals.
some utxo set commitment bookmarks (a little old)
http://diyhpl.us/~bryan/irc/bitcoin/utxo-commitments-or-
fraud-proofs.stdout.txt
TXO bitfields
http://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/
2017-07-08-bram-cohen-merkle-sets/
delayed TXO commitments
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
2016-May/012715.html
TXO commitments do not need a soft-fork to be useful
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
2017-February/013591.html
rolling UTXO set hashes
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
2017-May/014337.html
lotta other resources available, including source code proposals..
- Bryan
http://heybryan.org/
1 512 203 0507 <(512)%20203-0507>
William Casarin via bitcoin-dev
2017-11-17 19:07:04 UTC
Reply
Permalink
Raw Message
Post by Bryan Bishop via bitcoin-dev
It's not clear to me if you are have looked at the previous UTXO set
commitment proposals.
some utxo set commitment bookmarks (a little old)
http://diyhpl.us/~bryan/irc/bitcoin/utxo-commitments-or-fraud-proofs.stdout.txt
TXO bitfields
http://diyhpl.us/wiki/transcripts/sf-bitcoin-meetup/2017-07-08-bram-cohen-merkle-sets/
delayed TXO commitments
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html
TXO commitments do not need a soft-fork to be useful
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013591.html
rolling UTXO set hashes
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html
lotta other resources available, including source code proposals..
Thanks!

Has anyone categoried list discussions by topic like this? It seems a
lot of this stuff is scattered between mailing lists, irc conversations,
etc and can be hard to know whats floating out there.
--
https://jb55.com
Loading...