Bitcoin Forum
December 02, 2021, 11:55:35 AM *
News: Latest Bitcoin Core release: 22.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Provable Sequential Hash Function  (Read 1302 times)
spartacusrex
Hero Member
*****
Offline Offline

Activity: 719
Merit: 539



View Profile
January 15, 2014, 11:38:48 AM
 #1

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.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1638446135
Hero Member
*
Offline Offline

Posts: 1638446135

View Profile Personal Message (Offline)

Ignore
1638446135
Reply with quote  #2

1638446135
Report to moderator
1638446135
Hero Member
*
Offline Offline

Posts: 1638446135

View Profile Personal Message (Offline)

Ignore
1638446135
Reply with quote  #2

1638446135
Report to moderator
1638446135
Hero Member
*
Offline Offline

Posts: 1638446135

View Profile Personal Message (Offline)

Ignore
1638446135
Reply with quote  #2

1638446135
Report to moderator
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1001



View Profile
January 15, 2014, 12:09:09 PM
 #2

no

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
oakpacific
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1000


View Profile
January 15, 2014, 12:57:34 PM
 #3

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

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
spartacusrex
Hero Member
*****
Offline Offline

Activity: 719
Merit: 539



View Profile
January 15, 2014, 01:53:10 PM
 #4


Modular Exponentiation!  Thought it might play a part..  Roll Eyes

'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
Hero Member
*****
Offline Offline

Activity: 784
Merit: 1000


View Profile
January 15, 2014, 02:53:21 PM
 #5


Modular Exponentiation!  Thought it might play a part..  Roll Eyes

'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.

https://tlsnotary.org/ Fraud proofing decentralized fiat-Bitcoin trading.
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1001



View Profile
January 15, 2014, 08:00:54 PM
 #6

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 Offline

Activity: 111
Merit: 10


View Profile
January 15, 2014, 08:51:40 PM
 #7

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

No
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1001



View Profile
January 16, 2014, 07:51:23 AM
 #8

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 Offline

Activity: 111
Merit: 10


View Profile
January 16, 2014, 10:31:51 AM
 #9

If the person who set the puzzle published the plaintext M it wouldn't really be a time lock puzzle.  Smiley
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.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!