Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: spartacusrex on January 15, 2014, 11:38:48 AM



Title: Provable Sequential Hash Function
Post by: spartacusrex on January 15, 2014, 11:38:48 AM
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 ?  


Title: Re: Provable Sequential Hash Function
Post by: kjj on January 15, 2014, 12:09:09 PM
no


Title: Re: Provable Sequential Hash Function
Post by: oakpacific on January 15, 2014, 12:57:34 PM
http://www.cs.berkeley.edu/~daw/papers/timelock.pdf


Title: Re: Provable Sequential Hash Function
Post by: spartacusrex on January 15, 2014, 01:53:10 PM
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..}


Title: Re: Provable Sequential Hash Function
Post by: oakpacific on January 15, 2014, 02:53:21 PM
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.


Title: Re: Provable Sequential Hash Function
Post by: kjj on January 15, 2014, 08:00:54 PM
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.


Title: Re: Provable Sequential Hash Function
Post by: Crowex on January 15, 2014, 08:51:40 PM
The validity of the working key can be confirmed in a single decryption step.

No


Title: Re: Provable Sequential Hash Function
Post by: kjj on January 16, 2014, 07:51:23 AM
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).


Title: Re: Provable Sequential Hash Function
Post by: Crowex on January 16, 2014, 10:31:51 AM
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.