<p>I think a mining process that made use of stochastic sampling of a large data set would meet the requirements you have laid out. The blockchain even provides a great data set for this. For example, let's say each nonce requires you to randomly sample the blockchain to pick out a few bytes. Since you use many nonces while mining and couldn't predict which data you would need from the block chain, you would basically need to have the whole block chain (any publicly agreed upon data set, really) available while mining. The solution can then be verified with a small sample of that data set and some proof that the data is in the set. When using the blockchain example, you would probably need a chain of block headers and a merkle branch for the transaction data selected.</p>

<p>Another way to do this would be to <strong>use a large random merkle tree</strong>. Let's say someone created a merkle tree of 2^31 random 32 byte values. When taking into account that the merkle branches have to be stored as well, this is <code>(1 + 2 + 2^2 + 2^3 + ... + 2^31) * 32 bytes</code>, or <code>(2^32-1)*32 ~= 137.4 GB</code> of data in all. This data is very publicly available for anyone who really wanted to download it and verify the merkle root. The merkle root would be made known as the mining merkle root, and it is a well known and agreed upon constant. Mining involves sampling this random merkle tree and hashing, and with finding a successful solution, the merkle tree branch is provided, proving that the data that was sampled is actually in the publicly agreed upon merkle tree. </p>

<blockquote>
  <p>In this scheme, it takes ~137.4 GB of memory to mine, but only ~1 kB of data to verify a solution against the publicly agreed upon mining merkle root.</p>
</blockquote>

<p>And the numbers could obviously be tweaked here to allow people to mine without giving up 137.4 GB of their harddrive. A balance would have to be reached.</p>

<p>I actually like this way better, now that I think about it, because it doesn't have the side effect that mining can take longer as the block chain grows. You could probably even snapshot the bitcoin block chain and use that as a pubicly verifiable data set. But the block chain method essentially forces nodes to be full nodes as well, which is interesting, so it's a tradeoff. </p>

<hr>

<p>Edit: With a quick search, I turned up this paper that solves essentially the same problem with a different stochastic sampling method involving the birthday paradox. Their solution is interesting because it involves building your own large data set each time. But this may not actually be a good thing, as it discourages re-building of blocks when new transactions come in.</p>

<p><a href="http://www.hashcash.org/papers/momentum.pdf" rel="nofollow">http://www.hashcash.org/papers/momentum.pdf</a></p>

<p>A relevant bitcointalk discussion on the Momentum algorithm: </p>

<p><a href="https://bitcointalk.org/index.php?topic=313479.0" rel="nofollow">https://bitcointalk.org/index.php?topic=313479.0</a></p>

<p>I think it's funny how the 'momentum' aspect (not being able to update merkle after it is first created) is touted as the defining characteristic of the algorithm, even though it's actually a pretty significant downside, delaying confirmation of all transactions by 1 block. It may also exacerbate the problem where miners don't want to mine large blocks because they take long to propagate. i.e. It may be more profitable to continue mining with your tiny block even after you have heard about a new block on the network because the momentum you already have makes it easier. I think the fact that bitcoin's PoW algorithm does not have any momentum is actually a great feature, allowing for transactions to get confirmed quickly. </p>

<p>Using an unchanging data set, like in the solution I provided above, provides the desired asymmetric memory requirements in working/verifying work, while also avoiding the problem of momentum.</p>

CC BY-SA 3.0
2015-03-28T06:29:44.203Z
If the mining was based on data in the block chain, someone could insert data that appeared random, but was actually highly compressable if you knew some secret key. The second approach seems sound, though.
Nick ODell
CC BY-SA 3.0
2015-03-28T07:01:54.500Z
@NickODell, thanks. I've edited my post, you may be interested in the Momentum algorithm as well.
morsecoder
CC BY-SA 3.0
2015-03-28T12:39:18.267Z
Using the blockchain for data at least sort of forces miners to be a full node, that's at least some advantage I guess. Using 137GB of random data means you're just waiting for someone to build an ASIC with 137GB RAM and everyone else is screwed (so much for resistance...).
Jannes
CC BY-SA 3.0
2015-03-28T16:57:13.140Z
@Jannes If you're building an ASIC with 137 GB of RAM, why not make the RAM external, so you can get it for less? And if the algorithm largely depends on RAM, why not replace the ASIC with a CPU?
Nick ODell
CC BY-SA 3.0
2015-03-28T20:45:03.700Z
@NickODell because local RAM is always faster than external RAM and ASIC is always faster than CPU? That's the whole point. There is no point in making PoW CPU/GPU resistant because if it's worth it, someone will make an ASIC for it. Because an ASIC is basically just a CPU+RAM with all the unnecessary (general purpose) stuff cut out. To make it faster. In the end you're burning Watts... that's the whole point. Absolute speed doesn't matter (same Watts) but speed relative to others matters! If you need to be rich to invest in an ASIC plant you get an unfair advantage -> centralization.
Jannes
CC BY-SA 3.0
2015-04-07T17:55:17.837Z
@NickODell, the ziftrCOIN algorithm also uses an algorithm that requires more memory to calculate than it does to verify, through using the merkle tree right in the block as the merkle tree I described in my answer. The advantage is you can prove knowledge of all of the data you are mining while only requiring one of the transactions to prove a header is valid to an SPV node.
morsecoder
CC BY-SA 3.0
2015-04-08T20:05:36.783Z
@NickODell, my answer has shown 3 different ways of doing this, do these not meet your requirements?
morsecoder
CC BY-SA 3.0
2015-04-08T22:03:42.727Z
@StephenM347 All three have different problems 1) Someone could insert random looking data 2) Someone could run multiple miners in parallel on the same data set,  3) Has the problems you noted. They're all good tries at the problem, but they fall flat for one reason or another.
Nick ODell
CC BY-SA 3.0
2015-04-12T15:21:28.183Z
Wouldn't a a simple cycle-finding or distinguished point based collision search reduce the memory cost of momentum a lot while increasing computational cost only by a small factor?
CodesInChaos
CC BY-SA 3.0
2015-03-28T06:24:20.427Z
2015-03-28T07:03:55.040Z
2015-03-28T07:03:55.040Z
morsecoder
<p>My "Cuckoo Cycle" <a href="https://github.com/tromp/cuckoo" rel="nofollow">https://github.com/tromp/cuckoo</a> is a memory bound graph-theoretic Proof-of-Work that is trivial to verify and AFAIK the only one whose runtime is dominated by memory latency.</p>

CC BY-SA 3.0
2015-04-27T17:17:29.020Z
I thought that this algorithm was obselete? https://github.com/tromp/cuckoo/issues/2
Nick ODell
CC BY-SA 3.0
2015-04-27T17:39:05.953Z
No; only the original mining algorithm is obsolete. The new one, that uses edge-trimming as suggested by Dave Andersen, has resisted attack so far. Please see the README and the whitepaper for all details, including a comparison with Momentum.
John Tromp
CC BY-SA 3.0
2015-04-27T15:39:35.217Z
2015-04-27T15:39:35.217Z
John Tromp
<p><a href="http://www.hashcash.org/papers/dagger.html" rel="nofollow">Dagger</a> is intended to require lots of memory to create, but little to verify.</p>

CC BY-SA 3.0
2015-04-07T19:30:17.900Z
2015-04-07T19:30:17.900Z
Nick ODell
<p>Litecoin resists GPU speedup by using an scrypt-based hashing function that takes some amount of memory to generate and verify. The problem with this is that the <code>r</code> parameter needs to be set high enough that it is difficult to use a GPU, but low enough that low-memory clients (i.e. smartphones) can still efficiently verify blocks.</p>

<p>Is there a proof of work which takes significantly more memory to generate proof of work for a block than it does to verify that a block contains sufficient proof-of-work?</p>

<p>I've heard of two possible approaches: time-memory tradeoff with scrypt and a graph-theory hashing algorithm that takes lots of memory to find solutions.</p>

CC BY-SA 3.0
2015-03-27T20:10:03.307Z
What do you mean by "verify" hash function? Re-generate it and compare?
amaclin
CC BY-SA 3.0
2015-03-27T20:18:54.080Z
@amaclin Sort of? I've narrowed my question. Is it more clear?
Nick ODell
CC BY-SA 3.0
2015-03-27T20:27:57.023Z
There is no such thing as "verify hash function". PoW verifies that the result is less than target. But to verify it we should calculate the value
amaclin
CC BY-SA 3.0
2015-03-27T20:33:48.697Z
@amaclin `There is no such thing as "verify hash function"` [Sure there is.](http://en.wikipedia.org/wiki/Cryptographic_hash_function#Verifying_the_integrity_of_files_or_messages) `But to verify it we should calculate the value` I gave the time-memory tradeoff with scrypt as an example, so it's clearly possible.
Nick ODell
CC BY-SA 3.0
2015-03-28T01:29:41.710Z
Litecoin doesn't 'resist' GPU. Not even ASICs. "Tried to resist..." maybe, but there's rumors that the creator was already using a GPU at introduction. Also: finding and verifying a hash are the same thing, only difference is that when verifying you only need to do the calculation once instead of billions of times.
Jannes
CC BY-SA 3.0
2015-03-28T02:18:49.037Z
@Jannes `Litecoin doesn't 'resist' GPU. Not even ASICs.` It's better than Bitcoin, at least. If you have an alternate phrasing, feel free to edit my question. `Also: finding and verifying a hash are the same thing, only difference is that when verifying you only need to do the calculation once instead of billions of times.` I am aware that SHA256 is like that. Might there be some non-SHA256 or non-hashcash-based proof of work system that fulfills the requirements I set out?
Nick ODell
CC BY-SA 3.0
2015-03-28T12:30:34.177Z
@NickODell There is absolutely nothing "better" about it... the whole point of proof of work is to be as simple as possible because it lowers the barrier of entry to new players (ASIC manufacturers). Which means less people in a privileged position of having an unfair advantage over others (like the creators of the coin themselves for example). There's no point in making PoW artificially harder. Of course scamcoin creators try to make it sound like an advantage, but it's really the opposite.
Jannes
CC BY-SA 3.0
2015-03-28T14:21:09.457Z
@Jannes The barrier to entry for ASIC mining is not lowered, given that the Chinese mining farms won't divulge their hardware (and taking account of the supply issues with BFL), I'm inclined to think there's an extremely disparate barrier for entry to asic mining
Wizard Of Ozzie
CC BY-SA 3.0
2015-03-28T15:39:31.403Z
@Jannes You're entering the realm of speculating on the motives of altcoin creators, which is incredibly offtopic.
Nick ODell
CC BY-SA 3.0
2015-03-28T20:53:27.227Z
@WizardOfOzzie IF there is a disparate barrier to entry, it will only become worse if you make the designs and chips more complex. If you do that, you need more smarter people to design them, more expensive machines to make them etc.
Jannes
CC BY-SA 3.0
2015-04-12T15:15:40.577Z
Related: http://lists.randombit.net/pipermail/cryptography/2013-January/003760.html but probably not suitable altcoin use.
CodesInChaos
<proof-of-work><mining-theory>
Is there a proof of work system which takes significantly more memory to generate than it does to verify?
Nick ODell
# Is there a proof of work system which takes significantly more memory to generate than it does to verify?

(Asked by: username_0 on 2015-03-27)

Litecoin resists GPU speedup by using an scrypt-based hashing function that takes some amount of memory to generate and verify. The problem with this is that the `r` parameter needs to be set high enough that it is difficult to use a GPU, but low enough that low-memory clients (i.e. smartphones) can still efficiently verify blocks.

Is there a proof of work which takes significantly more memory to generate proof of work for a block than it does to verify that a block contains sufficient proof-of-work?

I've heard of two possible approaches: time-memory tradeoff with scrypt and a graph-theory hashing algorithm that takes lots of memory to find solutions.

**Tags:** proof-of-work, mining-theory

> **Comments:**
> **username_1**: What do you mean by "verify" hash function? Re-generate it and compare?  
> **username_0**: @username_1 Sort of? I've narrowed my question. Is it more clear?  
> **username_1**: There is no such thing as "verify hash function". PoW verifies that the result is less than target. But to verify it we should calculate the value  
> **username_0**: @username_1 `There is no such thing as "verify hash function"` [Sure there is.](http://en.wikipedia.org/wiki/Cryptographic_hash_function#Verifying_the_integrity_of_files_or_messages) `But to verify it we should calculate the value` I gave the time-memory tradeoff with scrypt as an example, so it's clearly possible.  
> **username_2**: Litecoin doesn't 'resist' GPU. Not even ASICs. "Tried to resist..." maybe, but there's rumors that the creator was already using a GPU at introduction. Also: finding and verifying a hash are the same thing, only difference is that when verifying you only need to do the calculation once instead of billions of times.  
> **username_0**: @username_2 `Litecoin doesn't 'resist' GPU. Not even ASICs.` It's better than Bitcoin, at least. If you have an alternate phrasing, feel free to edit my question. `Also: finding and verifying a hash are the same thing, only difference is that when verifying you only need to do the calculation once instead of billions of times.` I am aware that SHA256 is like that. Might there be some non-SHA256 or non-hashcash-based proof of work system that fulfills the requirements I set out?  
> **username_2**: @username_0 There is absolutely nothing "better" about it... the whole point of proof of work is to be as simple as possible because it lowers the barrier of entry to new players (ASIC manufacturers). Which means less people in a privileged position of having an unfair advantage over others (like the creators of the coin themselves for example). There's no point in making PoW artificially harder. Of course scamcoin creators try to make it sound like an advantage, but it's really the opposite.  
> **username_3**: @username_2 The barrier to entry for ASIC mining is not lowered, given that the Chinese mining farms won't divulge their hardware (and taking account of the supply issues with BFL), I'm inclined to think there's an extremely disparate barrier for entry to asic mining  
> **username_0**: @username_2 You're entering the realm of speculating on the motives of altcoin creators, which is incredibly offtopic.  
> **username_2**: @username_3 IF there is a disparate barrier to entry, it will only become worse if you make the designs and chips more complex. If you do that, you need more smarter people to design them, more expensive machines to make them etc.  
> **username_4**: Related: http://lists.randombit.net/pipermail/cryptography/2013-January/003760.html but probably not suitable altcoin use.  

---

## 3 answers

### Answer by username_5 on 2015-03-28. Score: 2

I think a mining process that made use of stochastic sampling of a large data set would meet the requirements you have laid out. The blockchain even provides a great data set for this. For example, let's say each nonce requires you to randomly sample the blockchain to pick out a few bytes. Since you use many nonces while mining and couldn't predict which data you would need from the block chain, you would basically need to have the whole block chain (any publicly agreed upon data set, really) available while mining. The solution can then be verified with a small sample of that data set and some proof that the data is in the set. When using the blockchain example, you would probably need a chain of block headers and a merkle branch for the transaction data selected.

Another way to do this would be to **use a large random merkle tree**. Let's say someone created a merkle tree of 2^31 random 32 byte values. When taking into account that the merkle branches have to be stored as well, this is `(1 + 2 + 2^2 + 2^3 + ... + 2^31) * 32 bytes`, or `(2^32-1)*32 ~= 137.4 GB` of data in all. This data is very publicly available for anyone who really wanted to download it and verify the merkle root. The merkle root would be made known as the mining merkle root, and it is a well known and agreed upon constant. Mining involves sampling this random merkle tree and hashing, and with finding a successful solution, the merkle tree branch is provided, proving that the data that was sampled is actually in the publicly agreed upon merkle tree.

> In this scheme, it takes ~137.4 GB of memory to mine, but only ~1 kB of data to verify a solution against the publicly agreed upon mining merkle root.

And the numbers could obviously be tweaked here to allow people to mine without giving up 137.4 GB of their harddrive. A balance would have to be reached.

I actually like this way better, now that I think about it, because it doesn't have the side effect that mining can take longer as the block chain grows. You could probably even snapshot the bitcoin block chain and use that as a pubicly verifiable data set. But the block chain method essentially forces nodes to be full nodes as well, which is interesting, so it's a tradeoff.

---

Edit: With a quick search, I turned up this paper that solves essentially the same problem with a different stochastic sampling method involving the birthday paradox. Their solution is interesting because it involves building your own large data set each time. But this may not actually be a good thing, as it discourages re-building of blocks when new transactions come in.

<http://www.hashcash.org/papers/momentum.pdf>

A relevant bitcointalk discussion on the Momentum algorithm:

<https://bitcointalk.org/index.php?topic=313479.0>

I think it's funny how the 'momentum' aspect (not being able to update merkle after it is first created) is touted as the defining characteristic of the algorithm, even though it's actually a pretty significant downside, delaying confirmation of all transactions by 1 block. It may also exacerbate the problem where miners don't want to mine large blocks because they take long to propagate. i.e. It may be more profitable to continue mining with your tiny block even after you have heard about a new block on the network because the momentum you already have makes it easier. I think the fact that bitcoin's PoW algorithm does not have any momentum is actually a great feature, allowing for transactions to get confirmed quickly.

Using an unchanging data set, like in the solution I provided above, provides the desired asymmetric memory requirements in working/verifying work, while also avoiding the problem of momentum.

> **Comments:**
> **username_0**: If the mining was based on data in the block chain, someone could insert data that appeared random, but was actually highly compressable if you knew some secret key. The second approach seems sound, though.  
> **username_5**: @username_0, thanks. I've edited my post, you may be interested in the Momentum algorithm as well.  
> **username_2**: Using the blockchain for data at least sort of forces miners to be a full node, that's at least some advantage I guess. Using 137GB of random data means you're just waiting for someone to build an ASIC with 137GB RAM and everyone else is screwed (so much for resistance...).  
> **username_0**: @username_2 If you're building an ASIC with 137 GB of RAM, why not make the RAM external, so you can get it for less? And if the algorithm largely depends on RAM, why not replace the ASIC with a CPU?  
> **username_2**: @username_0 because local RAM is always faster than external RAM and ASIC is always faster than CPU? That's the whole point. There is no point in making PoW CPU/GPU resistant because if it's worth it, someone will make an ASIC for it. Because an ASIC is basically just a CPU+RAM with all the unnecessary (general purpose) stuff cut out. To make it faster. In the end you're burning Watts... that's the whole point. Absolute speed doesn't matter (same Watts) but speed relative to others matters! If you need to be rich to invest in an ASIC plant you get an unfair advantage -> centralization.  
> **username_5**: @username_0, the ziftrCOIN algorithm also uses an algorithm that requires more memory to calculate than it does to verify, through using the merkle tree right in the block as the merkle tree I described in my answer. The advantage is you can prove knowledge of all of the data you are mining while only requiring one of the transactions to prove a header is valid to an SPV node.  
> **username_5**: @username_0, my answer has shown 3 different ways of doing this, do these not meet your requirements?  
> **username_0**: @StephenM347 All three have different problems 1) Someone could insert random looking data 2) Someone could run multiple miners in parallel on the same data set,  3) Has the problems you noted. They're all good tries at the problem, but they fall flat for one reason or another.  
> **username_4**: Wouldn't a a simple cycle-finding or distinguished point based collision search reduce the memory cost of momentum a lot while increasing computational cost only by a small factor?  

---

### Answer by username_6 on 2015-04-27. Score: 1

My "Cuckoo Cycle" <https://github.com/username_6/cuckoo> is a memory bound graph-theoretic Proof-of-Work that is trivial to verify and AFAIK the only one whose runtime is dominated by memory latency.

> **Comments:**
> **username_0**: I thought that this algorithm was obselete? https://github.com/username_6/cuckoo/issues/2  
> **username_6**: No; only the original mining algorithm is obsolete. The new one, that uses edge-trimming as suggested by Dave Andersen, has resisted attack so far. Please see the README and the whitepaper for all details, including a comparison with Momentum.  

---

### Answer by username_0 on 2015-04-07. Score: 1

[Dagger](http://www.hashcash.org/papers/dagger.html) is intended to require lots of memory to create, but little to verify.


---

