I'm looking for a non-interactive proof of work scheme. I want for it to (1) be faster to find solutions to if you're in the possession of an arbitrary secret, like a private key, and (2) for the domain of the solutions to be bounded, so that if you're in the possession of the key you can trivially enumerate the solution space.

For instance, a function $y = f(x)$ that takes T time to run where $x, y ∈ \{0, 1, 2, ... 2^{32}\}$, and has a fast inverse function $x = f(y)$ that takes $T'$ time to run would work. Then, if $T = 100\ ms$ and $T' = 10\ \mu s$ the solution set could be enumerated in 12 hours with the secret key, but 19 years without it. Of course, the higher $T/T'$, the better, but preferably at least above $10^3$.

An algorithm based on standard RSA or such satisfies (1), but not (2); the solution space is too big. Otherwise, the following algorithm would work: encrypt a nonce, if the ciphertext ends with sufficient zeroes it's a solution, else try again. The secret inverse function would just be decryption for every solution in the solution space.

A partial hash inversion puzzle satisfies (2), but not (1): try to hash a nonce $n$. If $H(n)$ ends with sufficient zeroes, $n$ is a solution, else try again. But you can't get any edge for enumerating the solution space with some given key as I see it.


Your Answer

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

Browse other questions tagged or ask your own question.