<p>You can use SCIP (succinct computational integrity and privacy) for this. (see also <a href="http://www.scipr-lab.org/" rel="nofollow noreferrer">http://www.scipr-lab.org/</a>)</p>

<p>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.</p>

<p>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.</p>

<p>However, with the currently known methods, generating the proof takes a long time. See <a href="https://bitcoin.stackexchange.com/a/37920/575">Nick's answer</a> for a faster method that applies specifically to this case.</p>

CC BY-SA 3.0
2015-06-11T20:25:22.080Z
Looking at this now: https://www.youtube.com/watch?v=YRcPReUpkcU
morsecoder
CC BY-SA 3.0
2015-06-14T13:15:20.307Z
@StephenM347: If you're interested in a more recent video about the same topic, see https://youtu.be/8T3SE5SyOXg?t=1h1m.
Meni Rosenfeld
CC BY-SA 3.0
2015-06-11T20:15:39.477Z
2015-06-12T07:44:47.013Z
2017-04-13T12:47:32.940Z
Meni Rosenfeld
<p>There's a suggested change to Bitcoin (adding skiplists to the header) that would make that quite possible. See Appendix B of <a href="https://www.blockstream.com/sidechains.pdf" rel="nofollow">Blockstream's sidechains paper</a>,  Efficient SPV Proofs:</p>

<blockquote>
  <p>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.</p>
  
  <p>[...]</p>
  
  <p>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.</p>
</blockquote>

<p>Also see Mark Friedenbach's Email on the bitcoin-dev mailing list concerning compact SPV proofs: <a href="http://sourceforge.net/p/bitcoin/mailman/message/32111357/" rel="nofollow">http://sourceforge.net/p/bitcoin/mailman/message/32111357/</a></p>

CC BY-SA 3.0
2015-06-11T22:15:39.490Z
2015-07-29T14:50:32.380Z
2015-07-29T14:50:32.380Z
Nick ODell
<p>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. </p>

<p><strong>Is there an alternative proof of work where these 'work-proofs' do not grow in size indefinitely?</strong></p>

<p>EDIT:</p>

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

CC BY-SA 3.0
2015-06-11T19:03:37.010Z
If you just want to prove the work, isn't the difficulty of the block it's in enough?
Luca Matteis
CC BY-SA 3.0
2015-06-11T19:33:58.750Z
@LucaMatteis Not really, I'm thinking it would be nice to be able prove a transaction is in the main chain by linking it to the genesis block in some way, and showing the rate of blocks being built on it, all without downloading the whole header chain.
morsecoder
<proof-of-work>
Is there a PoW system that shows cumulative work without an ever-increasing proof size?
morsecoder
# Is there a PoW system that shows cumulative work without an ever-increasing proof size?

(Asked by: username_0 on 2015-06-11)

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".

**Tags:** proof-of-work

> **Comments:**
> **username_1**: If you just want to prove the work, isn't the difficulty of the block it's in enough?  
> **username_0**: @username_1 Not really, I'm thinking it would be nice to be able prove a transaction is in the main chain by linking it to the genesis block in some way, and showing the rate of blocks being built on it, all without downloading the whole header chain.  

---

## 2 answers

### Answer by username_3 on 2015-06-11. Score: 5 | Accepted answer

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](https://www.blockstream.com/sidechains.pdf), 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 by username_2 on 2015-06-11. Score: 4

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 [username_3's answer](https://bitcoin.stackexchange.com/a/37920/575) for a faster method that applies specifically to this case.

> **Comments:**
> **username_0**: Looking at this now: https://www.youtube.com/watch?v=YRcPReUpkcU  
> **username_2**: @StephenM347: If you're interested in a more recent video about the same topic, see https://youtu.be/8T3SE5SyOXg?t=1h1m.  

---

