Quote from: knightdk on March 04, 2016, 08:09:42 PM

So what if the miner produces a pruning block for me nodes that has a higher block height than the actual? Then the miner expands on that block? Currently the best blockchain is chosen by having the greatest sum of difficulty, but this breaks that because it cannot be calculated with a partial blockchain. How would the node be able to know that the blockcthat it knows of is incorrect? If it receives the actual blockchain how will it know that is the correct one versus the incorrect one given by a malicious node/miner?

Very good points. As a core assumption of Bitcoin, a single miner can not replicate the difficulty of the entire network. Using that knowledge, here is a first-take at such a procedure to download and verify a pruned blockchain:

1) A new miner downloads all unique pruned blockchains visible to them. It is assumed that one of them will be correct because the Bitcoin network is the most powerful network in the world.
2) If there are no competing chains, great! If there are competing chains, they must be compared to find out which is the true blockchain and which is/are the counterfeit(s). As you pointed out it is easier to counterfeit back to a Pruning Block than the blockchain because you do not need to generate all blocks back to the genesis block, you just need to lie with the pruning block you start with. Thus, we can take additional precautions:
a) Check the block difficulty level of the blocks. If it is too low throw the blocks out. This will limit the people who could take advantage of this attack to only very powerful miners, as you can't fake the difficulty of a block.
b) Download back to the last 2 pruning blocks instead of just the last 6 regular blocks. At 1008 blocks between pruning blocks plus 6 confirmations for the pruning block, this means the malicious miner would need to generate at least 1014 near the current difficulty of the actual network instead of 6. This will limit the risk to extremely powerful miners, as even a miner/pool with 10% of the network would take 2.5 months to do this.
c) Check that current transactions are getting through in a timely fashion (e.g. monitor for 6+ blocks for anything fishy). Your node can monitor all published transactions and make sure they are included. If they are not being included in one chain they you know something is fishy with that. This will prevent against pre-generating 2000 blocks and then re-playing the blocks back.
d) Validate that times of the blocks make sense. This will prevent re-playing a pre-generated block sequence more than once since the dates/times will not line up.
e) As a final fallback for those not willing to take any risk, download the whole chain.

Further Note: Because there will always be full nodes (or even partial nodes running against the true chain), they can always warn people and miners can manually switch back to the correct chain if someone does try this attack. Once on the correct chain, they will stay there, so power will not be moved over to fake chains.

Thus, to do this attack, you must give up your mining reward for 1000+ blocks, and at the end you will be caught by full-nodes and your chain abandoned as news of the fake chain spreads across the world with proof from the full nodes, which will be a very big loss for you. Thus, it is pretty clear that such an attack would not be in your own self-interest.

Quote from: knightdk on March 04, 2016, 08:09:42 PM

So then what would happen to the original UTXO that is replaced/removed by the pruning block. What if someone wanted to spend from that? Someone who has synced the bickering and then took it offline prior to the pruning block being mined?

The pruning block doesn't replace the UTXOs, it only contains copies of them. They should not be considered separate transactions.

Quote from: knightdk on March 04, 2016, 08:09:42 PM

The blockchain cannot grow exponentially forever because the block size limit forces a maximum growth rate. It can only grow at 144 Mb per day right now.

True, but the amount of transactions people want to make can grow exponentially. If the limits aren't raised accordingly, exponentially more people will be boxed out, fees will skyrocket, and the Bitcoin adoption rate will decrease.