Possibly stupid question on tx pruning.

[hannesnaude]

Hi all.

I used to think that I understood how tx pruning works. However, I recently realised that there is an important question which I cannot seem to answer. I understand how the merkle tree can allow us to verify the block hash even when most or all of the txs in the block have been pruned.

What I do not understand is how we can be sure that unpruned txs are unspent in the presence of pruning. To give an example let's assume a tx history like this
In block 1 - A mines 50 BTC
In block 2 - A pays 50 BTC to B.
In block 3 - B pays 50 BTC to C.

Normally these three txs form an unbroken chain from the unspent output (in C's hands) all the way back to the coinbase tx. If we start pruning txs and tx 3 is unspent and buried under enough blocks we may prune txs 1 & 2. Now the only thing that a new node that downloads the block chain sees is

block 1 - txs pruned but merkle tree can be used to verify hash
block 2 - txs pruned but merkle tree can be used to verify hash
block 3 - B pays 50 BTC to C.

We can no longer verify the history of B's coins all the way back to coinbase, but we can see that the network accepted the payment at the time, so it must be valid. However, what if a malicious attacker sends us the following history.

block 1 - A mines 50 BTC.
block 2 - txs pruned but merkle tree can be used to verify hash.
block 3 - B pays 50 BTC to C.

All the hashes check out, and the blockchain is intact, so we have no reason to reject this history. But according to this it would appear as if both A and C have 50 BTC to spend (After all the pruned tx in block 2 may been "Z pays 50 BTC to B" for all I know). If we are then sent a tx where A pays the 50 BTC to D we would accept it and unwittingly assist in a double spending attack on the network by attempting to mine a block that contains this fraudulent tx.

In Satoshi's own words : "The only way to confirm the absence of a transaction is to be aware of all transactions." Transaction pruning appears to contradict this principle. All is fine if I am pruning the transactions myself after having downloaded the unpruned block chain and verified it fully. But if I am accepting a pruned chain from another node, both versions of the tx history shown above are equally believable and I have no way of knowing which is genuine.

I am sure there must be a (simple?) answer to this but I cannot seem to grasp it. Please clarify.



     

[ByteCoin]

But if I am accepting a pruned chain from another node, both versions of the tx history shown above are equally believable and I have no way of knowing which is genuine.

The problem you outline very lucidly really only harms miners. Non-miners who receive an incorrectly pruned blockchain are at worst prone to relaying or generating double spend transactions and/or blocks. If the majority of miners maintain correctly pruned blockchains then double spend transactions or blocks never become confirmed.
A miner who accepts an incorrectly pruned blockchain will be prone to produce blocks containing double-spend transactions and these blocks will not be built on and therefore the miner's expected block reward will not be spendable. This is a waste of the miner's hash power.

Note that with the current system, it seems likely that at least a few parties will have to remember ALL the transactions forever. If we ever lost confidence in the correctness of the pruned blockchains then knowledge of certain pruned transactions could become very valuable as releasing the information could invalidate vast numbers of transactions and blocks. This problem is entirely avoided in my proposed system called "balance sheets".

ByteCoin

[kjj]

In Satoshi's own words : "The only way to confirm the absence of a transaction is to be aware of all transactions." Transaction pruning appears to contradict this principle. All is fine if I am pruning the transactions myself after having downloaded the unpruned block chain and verified it fully. But if I am accepting a pruned chain from another node, both versions of the tx history shown above are equally believable and I have no way of knowing which is genuine.

So, er, don't do that then.

Pruning is intended to be an endpoint operation.  Each node must see and verify each block for itself.  After that, it can prune local storage, but it can't pass pruned blocks on to other nodes.

[hannesnaude]

Thanks guys. That's pretty much what I concluded, namely that we can prune txs ourselves, but never accept pruned blocks from (untrusted) others.   

But, if this is the use case, surely we can prune far more aggressively? Once a block is verified and sufficiently old we can drop all spent transactions in it, as well as the inputs of all the unspent transactions, without retaining so much as a hash.

This breaks our ability to prove (via the merkle branch) that the remaining unspent transactions were in the block in the first place, but we have already verified this, so unless we don't trust our past selves, there is no need to retain the proof.

The only capability that we lose relative to someone who prunes according to the recommended mechanism, is the ability to provide a third party with the details of old unspent transactions as well as the Merkle branches that links them to the block that they appeared in. But, if we assume, (as implementations that prune inevitably do) that someone else is retaining the unpruned history, this is hardly an issue, since the enquirer can simply get the proof that they seek from the unnamed someone?