Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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. $\;\;\;$ –  Ricky Demer Jul 20 '13 at 9:53
add comment

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

share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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