BIP proposal: Pruned block format

[grau]

WITHDRAWN

I ask for your feedback on following BIP proposal

MOTIVATION
Block messages pruned of spent output would reduce chain download time (and its size) by an order of magnitude.

PROPOSAL
Admit tx messages in blocks whereby the following special form indicates a pruned subtree of the block Merkle tree:

Blocks in this format would be accepted only in chain-download if trailing the last recent block by a significant margin. See follow up discussion for reasoning. The height pruned blocks are accepted until might be regulated by a global rule of checkpointing e.g.
(floor(current_height/1000)-1)*1000. Clients would imply they are at least 1000 behind the head if receiving pruned blocks.

A block can be pruned of transactions spent until current checkpoint height (not until the current head).



version: 1
tx_in count: 1
tx_in:
       previous_output : hash of the pruned merkle sub-tree
       script length: 0
       (signature script omitted since zero length)
       sequence: 0xFFFFFFFF
tx_out count: 0
lock_time: 0

The node would recognize pruned merkle sub-tree by checking for tx_out == 0 that is otherwise not permitted and use the previous_output hash in its Merkle tree hash computation for tree nodes above this.

NOTE:
An implementation of the proposal is available for test purposes in the bitsofproof node, link below.

[1714191542]

1714191542

[1714191542]

1714191542

[1714191542]

1714191542

[Pieter Wuille]

What purpose does this serve?

There is no way for the sender to prove that it didn't prune too little or too much, so you're essentially trusting the sender. The only part that can be validated is the proof-of-work in the block headers, so you're creating a node that requires SPV-level trust in history, and has no guarantees that it can correctly do block validation for future blocks.

If you want to set up a full zero-trust node, there is no way around processing the entire history. If you don't, you don't need more than the headers and transactions that interest you anyway.

In particular for SPV nodes, so that those don't need to download the entire history, we're working on a proposal to have client submit a transaction filter (for keys/txids in their wallet) to the server, and receive filtered blocks/transactions.

[grau]

What purpose does this serve?

There is no way for the sender to prove that it didn't prune too little or too much, so you're essentially trusting the sender. The only part that can be validated is the proof-of-work in the block headers, so you're creating a node that requires SPV-level trust in history, and has no guarantees that it can correctly do block validation for future blocks.

If pruning is applied sufficiently trailing the head then the amount of proof of work above it delivers increasing guarantee, that the pruned hashes are computed correctly.

Receiver can also check global health of pruning by comparing the unspent output with total coinbase expected for the height. If that matches, then future transactions must use the unspent (not pruned) transactions to be valid, their validation is not less secure then now.

Receiving a partially pruned block chain might be a compromise between full trust and no trust for higher performance.

[Pieter Wuille]

I don't understand. At no point is a snapshot or a hash of the state of the UTXO set committed to the blockchain. There have been plans for adding a sort of "merkle root of the UTXO set" to the coinbase, which would change this discussion, but for now, no such data exists.

So, I don't see how you can verify anything a server claims about the UTXO set, except by building it yourself. The sender may arbitrarily prune a transaction which is spent, or leave a spent transaction in (making you think it can still be spent). Done correctly, no merkle root will break, and the PoW of all blocks will be a perfect match. You can indeed verify that the sum of the coinbases matches (ignoring fees that were forgotten to be claimed...), but this is trivial to bypass.

The point is not that transferring the UTXO set is not useful - it certainly is - but anything that requires trust in the sender has no place in the P2P protocol in my opinion. Maybe an RPC to export/import the UTXO set from/to a file... but at the P2P level, nodes shouldn't need to trust each other at all.

[grau]

The sender may arbitrarily prune a transaction which is spent, or leave a spent transaction in (making you think it can still be spent)

Pruning has to be pair-wise, that means the cheating server has to deal with consequences rippling through the structure, but needed to be covered for the fraud not to be obvious to detect such as that the sum of UTXO matches expected coinbase for the height.

Therefore the deceiver would have to pick offsetting transactions too. Those would eventually need to be spent.
Works only if the server has that money, or creates further problems of pair-wise pruning.

There may be further practical obstacles, I am trying to think through.

I know that this is not the same level of security, but think that it is not trivial to cheat with. Such extension might not be suitable for the wild, but might be applicable for servers known to the receiver, if not the pruned block could be plainly rejected.
Edit: See reasoning in later posts, why it might be applicable even with zero trust

[grau]

The point is not that transferring the UTXO set is not useful - it certainly is - but anything that requires trust in the sender has no place in the P2P protocol in my opinion. Maybe an RPC to export/import the UTXO set from/to a file... but at the P2P level, nodes shouldn't need to trust each other at all.

I think I should emphasize that this is not the same as transferring UTXO, since pruned blocks would not be sent or accepted for the last recent, but e.g. one thousand blocks behind the head block. If pruning is significantly trailing, it gets hard to cheat.

[grau]

Let's assume clients accept pruned blocks if they are behind the head with X blocks.

Let's assume Alice spent some transaction and would want to make this disappear through pruning. She would have to wait X blocks, and hope that her spend is not spent again, since if yes pruning would no longer benefit her.

Let's assume she is "lucky" and her spend is still where it was. Now to prune her transaction, she would have to also prune the neighboring transaction in the Merkle tree, that if spend in the next X block, then no luck again. This gets exponentially harder if her transaction is not at the end of the block (leafs of the Merkle tree), since then she would have to make even more other disappearing.

Only if at some future time point all spends rooted in her spend and spends she needs to make disappearing for the tree would be no longer moving for X blocks, then she has a chance, that however gets again exponentially improbable as her and (Merkle) neighboring spends taints the future.

Do you see, why it is hard to cheat with a trailing pruned block?

If X is large enough it could be practically secure.

[casascius]

Won't work

For the reason Pieter said

It's not just that Alice could attack, it's that nodes can propagate garbage through the network.

You can't trust a pruned block if you have no way to verify that what is missing is not supposed to be there.

Search for "meta-tree" to find discussion as to how to change that.

[grau]

This is not about transferring UTXO, that the meta-tree is.

You agree that full chain is secure.

A chain that is pruned X blocks before the head is just as safe as the chain was as it was X blocks long, with the difference that spends are now not rooted in coinbases but in old spends, isn't it?

If one would attempt to remove an old spend it would violate the requirement that their sum match the coinbase sum for the height,
thats easy to verify.

[grau]

Root spends would be arbitrarily behind head-X, the pruned chain would be actually more secure then the original chain of length X, since it would still exhibit the full hash work since the earliest unspent, that remains the genesis.

[casascius]

Not sure what you mean by coinbase sum. There is no such thing.

Removing transactions doesn't change the sum of all unspent transactions, because transactions (other than coinbase) have a net zero effect on the total unspent bitcoins.

[grau]

Coinbase sum: the of coins generated by miner. A deterministic amount by chain height insn't it?

A correctly pruned chain has remaining root spends totaling to the coinbase sum, removing any of them would violate this.

Added: the coinbase sum for the height gives an upper boundary on root spends acceptable until that height. This helps the client filter garbage while downloading the pruned portion of the chain.

So, removing root spends will be catched latest as the client reaches the checkpoint.
Adding or altering new root spends is obviously as hard as adding new coinbase.

[Pieter Wuille]

So all you are proposing here is a hack to have a UTXO merkle root per-transaction transmitted using the existing tx/block messages?

That means you'll still need some mechanism for transferring the actual unspent outputs... why not use that other mechanism immediately?

Also, there is no way to prove that the txid of the transaction matches what is claimed for a particular set of unspent outputs. A server can simply invent UTXO's and claim that they belong to some existing (and valid) transaction. So a server that serves pruned blocks can replace an UTXO of a very old but unspent transaction by one that credits an address of himself (with the same amount). There is no way the receiver can ever detect this, except by rebuilding the full UTXO set from scratch himself, which requires the full blocks.

[grau]

So all you are proposing here is a hack to have a UTXO merkle root per-transaction transmitted using the existing tx/block messages?

No. It is not a hack to transfer utxo. It is to transfer a chain where spent output is removed if it happened way before the current node. More recent spend transactions remain.

A server can simply invent UTXO's and claim that they belong to some existing (and valid) transaction.

Again, not utxo is transferred. One can not invent a tx way back on chain.
One might attempt to prune it, but that is uncovered by the check of coinsum I wrote above.

Please ask yourself what is the difference between a chain of length X with coinbases (as is) or a chain that is at least X long and root spends play the role of coinbases?

If replacing those root spends would be easy then why is that hard to replace coinbases?

[Pieter Wuille]

Ok, maybe we first need to clear this up: how are you transferring the actual pruned transactions? The specification you give only contains a merkle root.

[grau]

Ok, maybe we first need to clear this up: how are you transferring the actual pruned transactions? The specification you give only contains a merkle root.

Pruned transactions are not transferred, they are pruned.

Pruning however is only allowed for blocks way back behind the current last block (last checkpoint) and only transactions are pruned that were already spent until the prune checkpoint. If those and only those transactions are pruned, then the remaining root spends (transactions remained in the pruned blocks) have to have an output sum equal to what the coinbase sum would be in the original blocks until the checkpoint height, therefore you can not just prune any of them without notice.

You can also not add one since the chain after the checkpoint puts proof of work on them.

Those root spends are just like coinbases of a chain after the checkpoint.

[Pieter Wuille]

Ok, I'm afraid I misunderstood your proposal from the start. Sorry.

You're not proposing a way to send just the unspent outputs of old transactions - you're proposing a way to send transactions marked as 'fully spent'.

Yes, yes I believe this would work. It would allow a fully verifying node to bootstrap with SPV-level trust in the network and reduced download/cpu usage. I need to think harder about edge cases, but it sounds reasonable. Interesting. There's no risk in doing this all the way even - you still only need SPV trust.

Also, I believe some recent developments (for filtered blocks, which is a different use case, but still applicable) may improve your proposal. To transfer filtered blocks, we designed a very compact format for transferring any subset of the transactions while not losing the ability to verify the proof-of-work. See https://github.com/sipa/bitcoin/commit/partialmerkle.

[grau]

Thanks a lot for your patience, since I also developed the Idea while discussing.

I think we have a breakthrough here that finally addresses the chain download clog.
Please assign a BIP number, so I write this clean and submit for final review by the community.

[grau]

Sorry, I have to withdraw this.

Peter might have found some value, but my original thoughts were wrong, as the sender indication of full spend could only be validated by the receiver using subsequent full blocks.

[Mike Hearn]

I don't think it's worth worrying about chain download. This is not going to be an important issue in the near future.

If you are just a regular end user, you should use a client like MultiBit or the Android Bitcoin Wallet where you can already start up a new wallet from scratch in <1 minute. The getheaders optimization means you can seek through years worth of chain in the time it takes you to fetch a few megabytes of data. The download time for the clients themselves are larger. And that's without proper checkpointing! Once bitcoinj starts chain catchup from the last checkpoint, I think setup time for a new wallet will reliably be within the <20 seconds range.

Now if you want to set up a fully verifying "supernode", then you're supposed to be in it for the long haul. The resource usages are getting higher all the time. You should be setting up a node with the intention of running it and keeping it running as a service to the community. If it takes a day to sync the chain, no big deal for something you will be running for months or years (0.8 can sync much faster than a day but let's imagine a lot of growth).