Is there a PoW system that shows cumulative work without an ever-increasing proof size?

Question

Let's say I have an output in the blockchain at height 100,000. At height 200,000, I want to prove that my output has the work of 100k blocks built onto it, securing it. In Bitcoin, proving that the output has X number of hashes securing it requires providing the full chain of headers, or 80 bytes * 100,000.

Is there an alternative proof of work where these 'work-proofs' do not grow in size indefinitely?

EDIT:

Now that I have found some resources, the terminology for I was looking for is "compact SPV proofs".

Answer 1

There's a suggested change to Bitcoin (adding skiplists to the header) that would make that quite possible. See Appendix B of Blockstream's sidechains paper, Efficient SPV Proofs:

The inspiration for compact SPV proofs is the skiplist [Pug90], a probabilistic data structure which provides log-complexity search without requiring rebalancing (which is good because an append-only structure such as a blockchain cannot be rebalanced). We require a change to Bitcoin so that rather than each blockheader committing only to the header before it, it commits to every one of its ancestors. These commitments can be stored in a Merkle tree for space efficiency: by including only a root hash in each block, we obtain a commitment to every element in the tree. Second, when extracting SPV proofs, provers are allowed to use these commitments to jump back to a block more than one link back in the chain, provided the work actually proven by the header exceeds the total target work proven by only following direct predecessor links. The result is a short DMMS which proves just as much work as the original blockchain.

[...]

Therefore if we want to skip the entire remaining chain in one jump, we expect to search only halfway; by the same argument we expect to skip this half after only a quarter, this quarter after only an eighth, and so on. The result is that the expected total proof length is logarithmic in the original length of the chain. For a million-block chain, the expected proof size for the entire chain is only log2(1000000) ≈ 20 headers. This brings the DMMS size down into the tens-of-kilobytes range.

Also see Mark Friedenbach's Email on the bitcoin-dev mailing list concerning compact SPV proofs: http://sourceforge.net/p/bitcoin/mailman/message/32111357/

Answer 2

You can use SCIP (succinct computational integrity and privacy) for this. (see also http://www.scipr-lab.org/)

SCIP is a general method that allows you to provide a short, easily checkable proof, for the fact that you know some information which, when input into a given program, results in a given value.

So you could take the program that checks the tx has all those confirmations the normal way, and the use SCIP to generate a short proof of this fact. The proof length does not increase with the size of the data or the runtime of the program, and thus satisfies your requirements. And you can do this without any changes to Bitcoin itself.

However, with the currently known methods, generating the proof takes a long time. See Nick's answer for a faster method that applies specifically to this case.