Mini-Blockchain proposal: How is the proof-chain secured against injections?

Question

I have just finished reading the paper Purely P2P Crypto-Currency With Finite Mini-Blockchain by J.D. Bruce. While I got the impression, that the rolling blockchain as an idea might work, I was left wondering about one detail in the proposal.

It seems to me that the proof-chain fails to live-up to it's purpose:
Bruce suggests that it would be sufficient to keep the proof-of-work solutions of the blocks as a proof-chain. Yet, how could one verify the proof-chain if all the block data has been discarded as suggested? Wouldn't it be possible to replace any blockhash in the proof-chain with another valid blockhash and start a competing mini-blockchain from that point?

That way an attacker could spend any amount of time on the mini-blockchain and just insert it into the proof-chain whenever it is sufficiently long.

Am I missing something? Why would the proposal work as intended by the author? Or is it actually "broken"?

Answer 1

Block data is not necessary to check proof of work, or to check that past block headers has not been altered. This is because for a block to pass proof of work check, the hash of its header must be less than a certain value. So, the header (which is just 80 bytes in Bitcoin) has enough information to check proof of work. Also, each header includes the hash of header of the previous block. So, assuming that the hash function is collision-resistant, it is impossible to modify any of the previous headers without changing the hash of the last header, and it is impossible to change any header while keeping proof of any work done after the corresponding block. The only way to "fake" a mini-blockchain is to outrun the honest miners, which requires an attacker to have comparable amount of hash power.