Provable Sequential Hash Function

[spartacusrex]

In the current POW system, you have the blockheader and a nonce you can change. Then you SHA256 the lot.

This is obviously a task that can be run in parallel.

This way an ASIC can crunch through a 'Gazillion' different nonce values simultaneously. Using pipelines etc..

And, once a nonce that satisfies certain criteria is found, maybe more than one actually, the proof-of-work is still just a simple hash away.

Is there a construction that only works 'Sequentially', so that the task cannot be run in parallel, and yet STILL only a hash away from the proof ?

I know that Scrypt uses a memory hard function, so you would need a different block of memory per attempt, but you could still do this in parallel. As the GPU implementations do.

You could say that the hash is the Hash(prevHash + Blockheader), but this is then not provable in a single hash check as you would need to do all the work again running back through the previous hash values..

Is there a construction that does this ?  

[kjj]

no

[oakpacific]

http://www.cs.berkeley.edu/~daw/papers/timelock.pdf

[spartacusrex]

http://www.cs.berkeley.edu/~daw/papers/timelock.pdf

Modular Exponentiation!  Thought it might play a part.. 

'Time-Lock Puzzles' is a new term for me.. It's always in the name. Then you know what to look for on Google.

The idea seems that you can lock data up in such a way that it can be decrypted ONLY after a certain amount of sequential tasks are performed. And this task CANNOT be run in  parallel. Like it.. Seems the inverse of what i was looking for, but definitely in the same ball park.. Thanks

Could it be used as some form of Hash Function ? Or as a sort of POW system..

I am searching for more info now.. {..starts sucking the interweb..}

[oakpacific]

http://www.cs.berkeley.edu/~daw/papers/timelock.pdf

Modular Exponentiation!  Thought it might play a part.. 

'Time-Lock Puzzles' is a new term for me.. It's always in the name. Then you know what to look for on Google.

The idea seems that you can lock data up in such a way that it can be decrypted ONLY after a certain amount of sequential tasks are performed. And this task CANNOT be run in  parallel. Like it.. Seems the inverse of what i was looking for, but definitely in the same ball park.. Thanks

Could it be used as some form of Hash Function ? Or as a sort of POW system..

I am searching for more info now.. {..starts sucking the interweb..}

In principle you can transform just about any block cipher into a hash function using Merkle-Damgard construction.

[kjj]

You could just use a 256 bit block cypher and use exactly the system described in the PDF.  The validity of the working key can be confirmed in a single decryption step.

But a hashing system for proof of work needs more properties than just an asymmetry of solve/verify work.  For one thing, the "difficulty" of that system must be set in advance, and while the validity of the solution is easy to verify, verification of the difficulty requires difficulty work to be done.

Also keep in mind that in a system like this, the fastest computer solves all of the puzzles, and everyone else solves none.

[Crowex]

The validity of the working key can be confirmed in a single decryption step.

No

[kjj]

The validity of the working key can be confirmed in a single decryption step.

No

Yes.  The cypher is well known (always), the plaintext and the cyphertext have been published (unusual in cryptography, but necessary in this system).  The key is the unknown.  When found, it is trivial to verify that the key is valid (meaning that it really does decrypt the cyphertext into the plaintext).

[Crowex]

If the person who set the puzzle published the plaintext M it wouldn't really be a time lock puzzle. 
For it to function as a proof of work then everybody has to be able to quickly and independently (puzzle setter might lie about M) verify that the work had been done.
It's not designed as a POW but it could be turned into a deterministic POW if the message M contained p and q.