Since PoW should be considered an essential part of the header, what you are proposing then is to increase header size from 80 bytes upto 72 KB (worst case 10000 items), a nearly 1000 fold increase...

Too bad it also resists human mining :-(

Challenge: give me one NP complete problem for which we can randomly generate instances of any desired difficulty and which humans can solve better than computers.

There is a proof of work where the memory requirements can vary from 1KB to 1PB (a petabyte is a billion GB), where verification is instant, and where increasing the requirement is just a soft fork.

It is a MUST for at least two reasons:

1) because new nodes trying to identify the longest valid chain must process all proofs of work in the entire blockchain history. That's on the order of a million of them. Even if you allow an hour for downloading just the headers, that's only a few milliseconds you can spend on each pow.

and even more importantly:

2) a slow verification is an invitation for a Denial of Service attack where attackers keep feeding you bogus proofs-of-work which you need to spend significant time on to recognize as bogus. Verification should therefore take no more time than it takes to receive a header (well under a millisecond).

This is a serious problem with your proposal. The proof of work is not self-contained within the header.
It requires the verifier to obtain up to 10000 additional pieces of data that must all be verified, which is too much overhead in latency, bandwidth, and verification time.

The N value had to be set low so that verification wouldn't become cumbersome.


They chose a lower-than-desired memory setting because early solver implementations were comically inefficient and they worried miners would be too slow. They also lacked the patience to wait for miner improvements. Verification was never the issue.

To me that is really the point. A competitive single chip ASIC is a big hot-running chip requiring tons of design talent and access to the latest and greatest fabrication technology. This leads to manufacturing centralization and to noisy mining rigs that become obsolete within a year or two.

On the other hand, a chip that needs to interface to separate commodity memory chips can remain smaller, run cooler, and be implemented in a less than bleeding-edge technology, since it only needs to be fast enough to saturate the memory interface.


Yes, there is SRAM, but it still has a limited bandwidth.

Quoting just a performance number is pretty much meaningless, as you can stick an arbitrary number of mining boards in a box.

The most interesting metric is efficiency (energy per Mh) and the second most is price ($ per Mh).

There is no long run, with most coins moving away from (200,9) Equihash, including Zcash by end of year...

EDIT: I should prepend that statement with a big IMO (In my opinion). I'm expecting Zcash to change PoW and stop supporting the old parameters, but nothing is decided at this point.

Of course you can spoof timestamps at will, but difficulty adjustment still only happens once every 2016 blocks, and can then at most quadruple. So you still need to find PoW for 2016 blocks at diff 1, 2016 blocks at diff 2^2, .... , 2016 blocks at diff 2^44, and 2016 blocks at diff 2^46,
which takes the quantum computer 2016 * (2^16 + 2^17 + ... + 2^38 + 2^39) = about 2^51 steps.
Timestamps will just need to be close enough to force the maximum diff increase of 4x at each retargetting.

Oops; I had forgotten about the need to mine 2016 blocks at current difficulty before allowing it to quadruple (and I thought it could at most double). So correcting for both errors, the 10 hours becomes 10000 hours, or well over a year. Throw in more realistic quantum cycle times, constant factor overheads in Grover's algorithm, and quantum error correction slowdowns, and you're looking at many years...

Even a quantum computer takes over 2^45 operations to rewrite the chain which has accumulated work of 2^89 hashes. Even at a generous single cycle double SHA computation and 1 Ghz quantum cycle time this will take 2^15 seconds. That's about 10 hours rather than a nanosecond.

How are the above speedup numbers not accurate?
I rounded up the latter from sqrt(2^74) (iota paper's estimate of 2^68 is obsolete) to a multiple of 2^10.
Note that hese numbers are ignoring potentially FAR slower cycle times for quantum computers.

Bitcoin will have to move to a new post-quantum signature scheme long before they need to change to a post-quantum PoW.

    problem      quantum algorithm     rough speedup
    signatures   Shor's                       2^240
    PoW            Grover's                    2^40

Using quantum computers to mine doesn't make much sense, when they are WAY more efficient at just recovering private keys from public keys and stealing a good fraction of all BTC.

No; a larger curve doesn't help (much), since Shor's algorithm runs in (quasi) quadratic time.
That means that doubling the number of bits only causes a fourfold slowdown, and 10x as many bits only a factor 100x slowdown.

You'll need to move to some new post-quantum signature scheme to get the needed exponential lower bound on running time.

All modern outputs, including those used by exchanges, are protected by Pay to Public Key Hash, and are relatively immune from quantum attacks (a quantum computer cannot find hash pre-images in polynomial time).

Unspent outputs from the very early years of bitcoin, that expose the public key, will be the prime targets of attack.

What is the biggest quantum bounty in bitcoin?
I.e. what is the single largest output that is Pay to Public Key?
Is it one of Satoshi's early addresses?
The advent of feasible quantum computing may well be heralded by the claiming of such a bounty.

That was already implemented back in early 2014, even before the Cuckoo Cycle paper appeared in BITCOIN2015.

Talk about old!

The Cuckoo Cycle webpage lists several performance claims. Which of the claims does the strong analysis refute? And why haven't you claimed the corresponding large bounty?