Parallel-resistant proof-of-work scheme?

I am looking for a proof-of-work scheme which cannot be effectively parallelized.

For example, in hashcash (and by extension bitcoin) you have some collision-resistant hash function $f()$, a target $T$ and some constant $C$. You obtain the proof of work by running $P=f(C, N)$ for some nonce $N$ which gets incremented with each iteration, untill $P\lt T$ (intuitive definition). The computee then publishes $C, N$ and the verifier verifies the condition by running the hash function once.

This can be easily parallelized by using multiple processors and assigning a portion of $N$ to each one.

I know scrypt aims to be memory-intensive and thus expensive and that bcrypt does something similar.

My approach so far is to use a secondary proof by obtaining $P$ as described above and then running $C' \gets P$ and $P'=f(C',N')$ untill $P'\lt T$ as above. This forces a parallel environment to do the same job as the first scheme, provided the adversary can only afford $max(N)$ processors. It also prohibits the use of single-processor systems (and it's kind of a dumb solution anyway).

I tried to look into literature but unfortunately I'm not mature enough for it. I also understand my question is borderline reference-request but I think I could argue it is acceptable. I leave judgement to you.

To conclude: Is there a proof-of-work scheme based on some hard-to-parallelize (P-complete) problem? Intuition tells me this is a problem based on work (repetition) so it is inherently parallelizable.

• In practice on big problem is that once there are multiple task you can work on at the same time you can parallelize again. I found that most things I want to protect with proof-of-work allow many parallel jobs, even when a job is sequential by itself. – CodesInChaos Jul 22 '13 at 18:53
• Such as? I don't care if the processor handles ie. independent additions in parallel somehow, or precomputes some values here and there, I only want a scheme that doesn't allow multiple processors to efficiently take advantage of it @CodesInChaos – rath Jul 22 '13 at 18:58

What I will describe is "the RSA timelock proof of work protocol",
which does not seem to have a canonical reference.

The server generates large random primes $\hspace{.02 in}p$ and $q$, then calculates
$M \: = \: \hspace{.02 in}p\hspace{-0.02 in}\cdot\hspace{-0.02 in}q \;\;$ and $\;\; L \: = \: \left\lfloor \sqrt{M}\right\rfloor\hspace{-0.02 in}+\hspace{-0.02 in}1 \;\;$ and $\;\; \lambda \: = \: \operatorname{Lcm}(\hspace{.03 in}p\hspace{-0.03 in}-\hspace{-0.04 in}1,\hspace{-0.01 in}q\hspace{-0.03 in}-\hspace{-0.04 in}1) \;\;\;$.
The server publishes $M\hspace{-0.02 in}$, stores $L$ (not necessarily secretly), and keeps $\lambda$ secret.
To give a challenge with difficulty paramter $T$, the server samples $n$ from $\{L,L+1,L+2,L+3,...,(M-L)-2,(M-L)-1,M-L\}$
and then sends $T$ and $n$ to the challenge's recipient.
To solve a challenge, the recipient iterates $\: n\mapsto \operatorname{mod}(n^2\hspace{-0.02 in},\hspace{-0.01 in}M\hspace{.02 in})$
$T$ times and then sends the result to the server.
The client (if honest) will end up with $\:\operatorname{mod}(n\text{^}\hspace{.01 in}(\operatorname{mod}(2^T\hspace{-0.02 in},\lambda)),M\hspace{.02 in})\:$, $\:$ which the server can easily calculate.

• If I understand your notation, you use $floor(\sqrt{M})+1$ which could be written as $ceil(\sqrt M)$ for a non-integer $M$? – rath Jul 20 '13 at 9:28
• Yes. $\:$ Of course, in this protocol, $M$ will always be an integer. $\;\;\;$ – user991 Jul 20 '13 at 9:53

Any chained task that takes as input the output of a prior iteration cannot be parallelized. PBKDF2 is an example of such an algorithm.

• That's an interesting take. This approach would require the verifier to spend exactly the same time on the problem as the computee, whereas verification should be cheaper than that. – rath Jul 20 '13 at 0:48
• @rath What about the RSA timelock proof of work protocol? It is also chained, believed as hard to cheat as integer factorization, and allows the verifier to check the result very efficiently, so that could work for you, perhaps. – Thomas Jul 20 '13 at 1:24
• I'll take a look at it tomorrow because I'm a bit tipsy but it definitely sounds like it fits the bill, +1 on that. Cheers – rath Jul 20 '13 at 1:28

I played with an idea for an asymmetric proof of work scheme that I put a small amount of thought into making parallel resistant.

I will explain the basic idea of the proof of work scheme first, followed by how I attempted to make it parallel resistant.

• The challenge creator hashes a small number of random bytes with a random iv.
• A desired number of challenges of a given difficulty weight are generated this way (i.e. 16 1 byte hashes, 4 2 byte hashes, 1 3 byte hash, x y byte hashes...) and sent to the solver with the random iv
• The solver cracks each hash individually. The length of time required to crack a hash scales exponentially with number of bytes needed to be cracked

Cracking the few unknown bytes takes significantly more work then hashing them did. Creating and verifying should be effectively constant time, as hashing N bytes is effectively a constant time operation. Cracking should be an exponential time operation.

Now, to make it parallel resistant. There are certain block cipher modes of operation which are not parallel friendly. The idea was to adapt and integrate these modes of operation with the series of hash inputs and outputs, as if the hash input was the plaintext and the ciphertext was the hash output.

A really simple example to demonstrate, not necessarily based on a block cipher mode of operation: when generating successive hashes, the recovered bytes of the previous hashes can be included as input to the current one:

• challenge1 = hash(random_bytes_1 + iv)
• challenge2 = hash(random_bytes_1 + random_bytes_2 + iv)
• challenge3 = hash(random_bytes_1 + random_bytes_2 + random_bytes_3 + iv)

Thus, in order for the solver to begin cracking challenge2 without accumulating extra work, challenge1 must be cracked first.

Note that with that example, if the solver is willing to forego the work reduction, they can start cracking whichever hash they want. So that particular example might not be very effective against GPU's, as brute forcing a 2 byte hash is probably more or less the same amount of time as brute forcing a 4 byte hash.

• Is verifying in your scheme constant time or feasible in regard to the work amount? – Marinus Freund Jan 28 '16 at 17:44
• Verification and challenge solving are asymmetric in this scheme. The amount of time taken for the creator to hash N bytes is effectively constant (creation and verification). The amount of time taken for the solver to crack N bytes is exponential (2 ^ N). Technically, with the parallel resistance, it is not "constant time", as the parallel resistance is gained via increasing the number of hashes to crack, which I think makes it linear in the number of hashes, but creation/verification per hash is effectively constant time. – Ella Rose Jan 28 '16 at 22:09
• Marinus Freund wrote: Admittedly, what I don't really get about puzzles that are created for the solvers, is that the solution could be transmitted instead of solved. With e.g. Bitcoin afaik no part of the protocol does create or transmit a puzzle, throw away a secret solution or anything like that. If it did, the system wouldn't work for long. This property seems always to go along with parallelism, sadly. Am I missing something? – CodesInChaos Jan 28 '16 at 22:49
• @E.Rose It's a comment by Marinus (written in his now deleted answer) to you. He seems to be worried that your scheme requires a trusted party to create the puzzle, instead of using a hash as seed, like it's required by bitcoin's proof-of-work. – CodesInChaos Jan 29 '16 at 8:13