5

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.

  • What do you mean by "verify" hash function? Re-generate it and compare? – amaclin Mar 27 '15 at 20:10
  • @amaclin Sort of? I've narrowed my question. Is it more clear? – Nick ODell Mar 27 '15 at 20:18
  • 1
    @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 Mar 28 '15 at 12:30
  • 1
    @Jannes You're entering the realm of speculating on the motives of altcoin creators, which is incredibly offtopic. – Nick ODell Mar 28 '15 at 15:39
  • 1
    Related: lists.randombit.net/pipermail/cryptography/2013-January/… but probably not suitable altcoin use. – CodesInChaos Apr 12 '15 at 15:15
2
+100

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.

  • 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 Mar 28 '15 at 6:29
  • 1
    @NickODell, thanks. I've edited my post, you may be interested in the Momentum algorithm as well. – morsecoder Mar 28 '15 at 7:01
  • 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 Mar 28 '15 at 12:39
  • 1
    @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 Mar 28 '15 at 16:57
  • 1
    @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 Mar 28 '15 at 20:45
1

Dagger is intended to require lots of memory to create, but little to verify.

1

My "Cuckoo Cycle" https://github.com/tromp/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.

  • I thought that this algorithm was obselete? github.com/tromp/cuckoo/issues/2 – Nick ODell Apr 27 '15 at 17:17
  • 1
    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 Apr 27 '15 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.