×
all 61 comments
sorted by:
best
topnewcontroversialoldq&a

[–]pinhead26 10 points11 points  (0 children)

I love how PT signs his emails with the latest block hash

[–]throwaway43572 3 points4 points  (17 children)

Is this supposed to be used by the likes of Journalists ?

[–]petertoddPeter Todd - Bitcoin Expert[S] 10 points11 points  (16 children)

Basically it's a way to encrypt a file with a weak key constructed so the key can be decrypted in a specified amount of time. The decryption process uses long chains of hashes so it can't be parallelized - one fast CPU can decrypt the file faster than a million slightly slower CPUs. Moores law long ago ended for scalar performance - CPU clock speeds haven't budged in years - so predicting how long it'll take for the decryption to happen is possible. Secondly since decrypting the timelock lets you also collect Bitcoins, unrelated third-parties are incentivized to do the decryption for you, and additionally, them doing that automatically makes the decrypted keys public.

To answer your question, it could be. For instance a journalist might want to make sure some documents get eventually leaked in a few years no matter what happens to them personally. A more prosaic use-case is something like greenaddress.it, where they might use timelock crypto on the secret keys they hold, to ensure that funds can always be recovered even if they suddely disappear. (they use nLockTime for that right now; timelock would give an additional "belt-and-suspenders" backup)

I'm working with the Zerocash team and we're thinking of using timelock crypto to create a testnet Zerocash chain. We'd timelock encrypt the private parameters used to initialize the chain, ensuring that in the future those parameters will be cracked and the testing chain become worthless no matter what.

[–]throwaway43572 1 point2 points  (13 children)

But in order to encrypt something in the first place one has to pre-calculate the whole chain yourself right? Say you only have a normal CPU available you will not be able to create a chain that is near long enough that a sha-256 ASIC wouldn't break in a fraction of the time. Have i misunderstood anything?

[–]petertoddPeter Todd - Bitcoin Expert[S] 4 points5 points  (12 children)

Correct. However the creator of the timelock gets to compute it in parallel by computing multiple chains. Each chain starts from an initialization vector (IV) and once a chain is computed the secret of one chain is used to encrypt the IV of the next. Only the first IV is released to the public, forcing everyone else to compute the chain the slow way, serially.

[–]throwaway43572 2 points3 points  (5 children)

Oh. So its actually a whole bunch of smaller chains which is then forged together by the creator. I would love to see some numbers on how much faster a parallelized creation of a chain on f.x. a GPU would be than a sha-256 ASIC. Even though most of the performance of an ASIC is from having thousands of cores it should still be faster serialized than a non-specific CPU

[–]Natanael_L 0 points1 point  (1 child)

An FPGA could compute at least dozens and probably hundreds of chains in parallel. Imagine a rack of FPGA:s doing that together!

[–]__Cyber_Dildonics__ 0 points1 point  (0 children)

Or one video card. Generating a chain in parallel just has to be a large factor faster, but not instant. A video card at 100x faster than a single core (although it could be 400x or more) would buy you 3 months for one day.

[–]__Cyber_Dildonics__ 0 points1 point  (2 children)

Why does an ASIC have to be factor? Litecoin has shown that even an overly small memory requirement on scrypt is very ASIC resistant. A better memory requirement should put it back on video cards.

[–]throwaway43572 0 points1 point  (1 child)

First of all because this is a chain of sha-256 hashes. And for your second point - the ASICs for scrypt is starting to come out now.

[–]__Cyber_Dildonics__ 0 points1 point  (0 children)

Right, but it isn't because of script that ASICS are possible, it is because litecoin had very conservative memory requirements. Heavier memory requirements on scrypt hashing would easily push it back to gpus.

[–]notreddingit 2 points3 points  (0 children)

Very clever stuff here.

[–]pinhead26 0 points1 point  (4 children)

If each chain starts with an IV computed from the previous chain - how is that parallel?

[–]petertoddPeter Todd - Bitcoin Expert[S] 1 point2 points  (3 children)

It's an IV encrypted with the previous chain.

[–]pinhead26 5 points6 points  (2 children)

Got it, very clever. So the creator, in parallel, produces n chains. Then encrypts the IV of each chain in a quick serial process, and releases those encrypted IVs. The attacker, or I guess "treasure hunter" has to solve each chain one at a time in the right order to decrypt each IV

[–]petertoddPeter Todd - Bitcoin Expert[S] 2 points3 points  (1 child)

You got it.

[–]Natanael_L 0 points1 point  (0 children)

You can even amplify the difficulty by selectively removing a few bits here and there from the keys and forcing bruteforce guessing for some of the sub-chains. You could let the cracker check if he found the correct key at the end of each sub-chain by calculating a Merkle tree hash of the keys, to not make him waste more computational power than intended.

Edit: or maybe not, doesn't seem to work as intended. Either it adds too little or become parallelizable...

[–]BobAlison 0 points1 point  (1 child)

For instance a journalist might want to make sure some documents get eventually leaked in a few years no matter what happens to them personally. A more prosaic use-case is something like greenaddress.it, where they might use timelock crypto on the secret keys they hold, to ensure that funds can always be recovered even if they suddely disappear.

Do any other use cases come to mind?

[–]bruce_fenton 4 points5 points  (0 children)

Good job Peter!

[–]fts42 2 points3 points  (2 children)

Within 12 hours from publication the first chain has been unlocked and claimed by someone: https://blockchain.info/address/1ERvMr5J8FETF7zj4QM98u8ZANaL1o9XGZ

That someone must have at least 2 Mhash/second (scalar).

The first public key can be found in the input script (ScriptSig) of the sending transaction. It is: 03c95ef3f5fcbca7add01e070ec136e554e74531bbc3fa844234b7885cce7a6b9a

Anyone who has a greater scalar hashing power can try to get ahead in the race for the remaining locked chains using this public key (or any of the next ones that gets revealed).

[–]_anuj 0 points1 point  (1 child)

Here's the second: https://blockchain.info/address/18h7LwKpd9c6u8zJka3vMCASa8BfbiZFd4, in 6 hours

[–]fts42 1 point2 points  (0 children)

The fact that the second and the third one got unlocked in almost exactly the same amount of time (the third one took only about 0.57%, or 124 seconds longer, judging by the timestamps at blockchain.info) suggests that those two were most likely unlocked by the same machine and claimed by the same person.

Using the smallest difference in timestamps (first and second) we can make a rather precise estimate of the hashing power being used:

86400000000/((1401952479000-1401930562000)/1000) = 3 942 145 hashes/s

I have to say it is very nice that this scheme got implemented. Thanks Peter!

Edit 15.06.2014: The last addresses were claimed and the difference in timestamps suggests that the speed didn't increase along the way.

[–]gwern 2 points3 points  (2 children)

Very neat. I'll have to add this to http://gwern.net/Self-decrypting%20files#hashing

[–]petertoddPeter Todd - Bitcoin Expert[S] 2 points3 points  (1 child)

Thanks! That's the site where I learned about the idea in the first place.

[–]gwern 2 points3 points  (0 children)

Cool. I'm glad someone took the time to code my idea up and make it workable. I also like your Bitcoin twist on it.

[–]Introshine 1 point2 points  (0 children)

Interesting. Can a big Xeon multicore outperform a Singlecore - with the same Mhz?

[–]platypii 1 point2 points  (0 children)

INFO:root:chain #0: 37s elapsed, 5705264s to go at 0.4846 Mhash/s

I don't think I have a chance at this.

[–]Ape3000 1 point2 points  (7 children)

sha256module compilation succeeded without errors, but I get this when trying to use it:

Traceback (most recent call last):
  ...
  File "timelock/kernel.py", line 133, in run
    return timelock.kernels.sha256.run(nonce, n)
SystemError: error return without exception set

[–]petertoddPeter Todd - Bitcoin Expert[S] 0 points1 point  (6 children)

Curious! Does timelock work if you don't compile that module? (it should automatically fallback to a python implementation)

[–]Ape3000 0 points1 point  (5 children)

Yes, the python kernel works.

[–]petertoddPeter Todd - Bitcoin Expert[S] 0 points1 point  (4 children)

Strange. What OS, etc?

(also, open this as an issue on github!)

[–]Ape3000 0 points1 point  (3 children)

It seems that the issue tracker feature is not enabled for that github repository. I actually checked that before using this reddit thread as the issue tracker.

I'm using 64-bit Arch Linux.

Building gives this output:

building 'timelock.kernels.sha256' extension
gcc -pthread -Wno-unused-result -Werror=declaration-after-statement -DDYNAMIC_ANNOTATIONS_ENABLED=1 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -march=x86-64 -mtune=generic -O2 -pipe -fstack-protector-strong --param=ssp-buffer-size=4 -fPIC -I/usr/include/python3.4m -c timelock/kernels/sha256module.c -o build/temp.linux-x86_64-3.4/timelock/kernels/sha256module.o
gcc -pthread -shared -Wl,-O1,--sort-common,--as-needed,-z,relro build/temp.linux-x86_64-3.4/timelock/kernels/sha256module.o -L. -lcrypto -lpython3.4m -o timelock/kernels/sha256.cpython-34m.so

EDIT: I am using Python 3.4.1 and OpenSSL 1.0.1.g.

EDIT2: And GCC 4.9.0.

[–]petertoddPeter Todd - Bitcoin Expert[S] 0 points1 point  (2 children)

Thanks, just fixed the issue tracker issue.

Hmm, I'm using Python 3.3.2, likely there's some incompatibility in the C extension API w/ 3.4. I'll have to look at it later when I get a chance. (I was feeling kinda sick yesterday so I took a day off from my usual job, replying to emails!)

[–]Ape3000 1 point2 points  (0 children)

I created an issue on github. We should move the discussion there.

https://github.com/petertodd/timelock/issues/1

[–]Ape3000 0 points1 point  (0 children)

Downgrading to Python 3.3.4 or GCC 4.8.2 didn't help.

[–]porqup1ne 1 point2 points  (0 children)

very clever

[–]The_Mastor 1 point2 points  (1 child)

I think I'm missing something here. Couldn't someone create a time-release which appears to have a large bounty but once solved doesn't provide the required private key.

Or spend the bounty bitcoins before the time lock chain is completed.

[–]petertoddPeter Todd - Bitcoin Expert[S] 2 points3 points  (0 children)

They sure could. In principle you can solve this issue with "moon-math" like ZK-SNARKS, but I know of no way to solve it in practice with sufficient efficiency unfortunately. That said for the solvers since the chain is linear, and payouts relatively frequent, at least the scheme can be setup such that they won't waste more than a few hours work.

[–][deleted] 1 point2 points  (2 children)

I get that you can't work on two "links" of the chain in parallel, because you need to crack the first link to decrypt the IV for the second link. But can't any given link be sped up via parallelisation? Like, why can't I use 10,000 CPUs to help search the search space for the first link?

[–]TitusDomitusCruentus 1 point2 points  (1 child)

As far as I know, you're correct.

Crypto isn't really my field, though, but it sounds like you could absolutely parallelize the search for each individual link.

If the individual links don't take that long for a single CPU, it wouldn't give much of a speedup, though (assuming a long chain).

[–][deleted] 1 point2 points  (0 children)

Oh, okay. I see. This is a neat idea.

[–]throwaway43572 1 point2 points  (0 children)

The person currently decrypting this chain has a MH/s of 3.94521 assuming 6h5m of decryption time. I can only get a speed of 1.54 MH/s and thus i would simply be wasting my time. Feels scuky to stand by and watch while 320 mbtc slowly gets taken :p

[–][deleted] 0 points1 point  (2 children)

The email is a little above my head but:

"This gives us a valuable chance to incentivize others to push the envelope of scalar performance - important knowledge if we are going to have any hope of knowing how soon our timelocked secrets will actually be revealed! ... Only a single algorithm - SHA256 - is supported by design"

so could bounties be created that test the strength of miners based on how long it takes to crack? if it disapears really fast you know a large entity controls a lot of power when compared to the whole bitcoin network?

[–]petertoddPeter Todd - Bitcoin Expert[S] 2 points3 points  (1 child)

Bitcoin mining is a highly parallel process, not serial, so no, this app has nothing to do with mining.

[–][deleted] 0 points1 point  (0 children)

Ah, thanks.

[–]pinhead26 0 points1 point  (10 children)

...and your estimate of time (~256 hours in your examples) is based on what hash rate?

[–]Ape3000 0 points1 point  (9 children)

3.0 Mhash/s. You can calculate it from the "n" value on the chain definition.

[–]pinhead26 0 points1 point  (8 children)

Right, thanks I guess that was self explanatory - help out a non-miner though, is that in the range of a CPU or ASIC?

[–]Ape3000 0 points1 point  (7 children)

Note that this is not a bitcoin mining hash rate.

I guess you could get around this rate with a decent CPU. I'm not sure how much dedicated hardware would help in this case, but you could probably get higher rates with a timelock ASIC.

[–]pinhead26 0 points1 point  (6 children)

How is the sha256 in timelock different from the sha256 used by asic miners?

[–]Ape3000 0 points1 point  (5 children)

The sha256 function itself should be exactly the same, but it's not used the same way in timelock. GPUs and Bitcoin ASICs are good for bitcoin mining because they can execute the sha256 operation so many times concurrently. Timelock computing doesn't benefit anything from that concurrency. It just needs one execution to finish as quickly as possible.

[–]pinhead26 0 points1 point  (4 children)

OK, I see, ASIC-resistance via serialization. Miners hash in parallel, but in timelock, each has to be completed before the next one can begin.

[–]Ape3000 0 points1 point  (3 children)

The main point in using this serialized hashing is not prevent ASICs. It is to make the hashing times predictable.

[–]petertoddPeter Todd - Bitcoin Expert[S] 2 points3 points  (0 children)

Correct.

I fully expect someone to implement the algorithm in a purpose built overclocked and liquid cooled FPGA at the very least if it gets used. That's a good thing! They're still forced to "tip their hand" and prove to the world how fast they can hash - as well as decrypt the secret - because collecting the bounty is made public by the Bitcoin blockchain.

[–]pinhead26 0 points1 point  (1 child)

Thanks! 1 happydance /u/changetip

[–]changetip 0 points1 point  (0 children)

The bitcoin tip for 1.554 mBTC ($1.00) has been collected by Ape3000.

What's this?

[–][deleted] 0 points1 point  (3 children)

I'm not sure I understand this.. There is an address at the end of each chain, or do they collect the bounty after completing all the chains?

EDIT: Also, why did you choose hash chains over something like a timelock puzzle based on RSA, where there is no overhead for the party creating the timelock?

[–]gwern 1 point2 points  (2 children)

EDIT: Also, why did you choose hash chains over something like a timelock puzzle based on RSA, where there is no overhead for the party creating the timelock?

What do you mean by RSA? If you mean simply public-key crypto with a short/weak key, that's parallelizable and so is no good for time-locks: powerful adversaries can crack it faster, and the unlock time can be any time if one is (un)lucky.

[–][deleted] 0 points1 point  (1 child)

I was referring to something like #2 in this paper:

http://cs.brown.edu/~foteini/papers/MathTRE.pdf

Squaring is not parallelizable.

The idea is to choose a decryption exponent in the form d = 22t (mod phi(n)).

To decrypt the message, the receiver needs to perform 2t squarings.

Example:

You want the recipient to do 240 (~1 trillion) squarings before reading the message:

n = (p - q)(q - 1)

d = 2240 (mod phi(n))

e = d-1 (mod phi(n))

C = Me (mod n)

To decrypt, the receiver must compute:

Cd = C2240

That is, they must square C 240 times before recovering the message.

[–]gwern -1 points0 points  (0 children)

The problem with squaring and Rivest's original time-lock approach is that we don't know how well squaring resists approaches like ASICs, and it doesn't involve one of the great equalizers, the memory hierarchy.

We have a pretty good idea of the limits of serial SHA because of all the Bitcoin-related work that has gone into optimizing SHA hashing, which makes it much less likely we'll be surprised by, say, someone cracking a time-lock in a tenth of the time we expected it to take. Even better would be to use a memory-bound hash like scrypt or something, but beggars can't be choosers.

(This lesser predictability has actually been a problem for Rivest's squaring challenge: he set the difficulty based on an extrapolation of Moore's law for serial performance which broke down a few years ago, so it'll take years longer to unlock than he expected.)

[–]nybe 0 points1 point  (0 children)

goddamn that hurt my head.