|
spartacusrex (OP)
|
 |
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 ?
|
Life is Code.
|
|
|
|
|
|
|
|
|
|
|
|
The grue lurks in the darkest places of the earth. Its favorite diet is adventurers, but its insatiable appetite is tempered by its fear of light. No grue has ever been seen by the light of day, and few have survived its fearsome jaws to tell the tale.
|
|
|
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
|
|
|
|
|
|
|
kjj
Legendary
 Offline
Activity: 1302
Merit: 1024
|
|
January 15, 2014, 12:09:09 PM |
|
no
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
|
|
|
spartacusrex (OP)
|
|
January 15, 2014, 01:53:10 PM |
|
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..} |
Life is Code.
|
|
|
|
oakpacific
|
|
January 15, 2014, 02:53:21 PM |
|
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
Legendary
Offline
Activity: 1302
Merit: 1024
|
|
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.
|
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
Crowex
Member
Offline
Activity: 111
Merit: 10
|
|
January 15, 2014, 08:51:40 PM |
|
The validity of the working key can be confirmed in a single decryption step.
No |
|
|
|
|
kjj
Legendary
Offline
Activity: 1302
Merit: 1024
|
|
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). |
17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs. You should too.
|
|
|
Crowex
Member
Offline
Activity: 111
Merit: 10
|
|
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. |
|
|
|
|
|
