6 ms·

Timelock: time-release encryption incentivised by Bitcoins

70 points by roasbeef 12y ago

mrb 12y ago
This is an interesting concept and implementation. Allow me to re-explain how it works, because IMHO the documentation is a bit confusing and light on some details. Say an informant wants to time-lock a secret (eg. a key to decrypt an encrypted document) so that it must take the public approximately 32 days of compute time to be unlocked, regardless if the public has a super-computer or is Joe Six Pack with a typical home computer. Well, this informant has a 16-core machine. So he selects 16 random initialization vectors (chain{0,15}_iv0) and calculates in parallel 16 chains of serial SHA256 calls, thereby fully utilizing his CPU: SHA256(chain0_iv0) -> chain0_iv1; SHA256(chain0_iv1) -> chain0_iv2; ... SHA256(chain1_iv0) -> chain1_iv1; SHA256(chain1_iv1) -> chain1_iv2; ... ... SHA256(chain15_iv0) -> chain15_iv1; SHA256(chain15_iv1) -> chain15_iv2; ... After 2 days, the informant has spent 32 CPU-days of compute time calculating the chains, reaching the 200,000,000,000th node on each chain: chain0_iv200000000000 chain1_iv200000000000 chain2_iv200000000000 ... chain15_iv200000000000 Now he obfuscates the starting points of 15 of the 16 chains (keeping chain0_iv0 as is, but obfuscating chain{1,15}_iv0): chain0_iv200000000000 ^ chain1_iv0 -> chain1_obfuscated_iv chain1_iv200000000000 ^ chain2_iv0 -> chain2_obfuscated_iv ... chain14_iv200000000000 ^ chain15_iv0 -> chain15_obfuscated_iv (^ is the XOR operation) The informant is going to publish chain0_iv0 and chain{1,15}_obfuscated_iv so that the public is forced to fully calculate chain0, then XOR the result with chain1_obfuscated_iv to be able to calculate chain1, and so on, until chain15. This is a crucial aspect of the concept: the informant can parallelize work on the chains, while the public is forced to compute them serially. The informant uses the last node of the last chain (chain15_iv200000000000) as a Bitcoin private key (a 256-bit ECDSA key), and sends the bounty (a certain number of coins) to it. The informant calculates the corresponding ECDSA public key, and hashes it with SHA256: this is the secret (eg. a cryptographic key) that is time-locked. The informant also calculates the RIPEMD160 hash of the secret and publishes it: this is hashed_secret, which is a (public) Bitcoin address. This two-hash process is the standard algorithm by which Bitcoin calculates public addresses from private keys [1]. This two-hash process is re-used here so that the moment someone withdraws the bounty, the side-effect is that the Bitcoin blockchain automatically lets everyone instantly calculate the secret. Indeed: the bounty-claiming Bitcoin transaction itself reveals the ECDSA public key, so anybody who sees it can SHA256-hash the pub key to get the secret. All in all, the informant publishes: - Starting point for 1st chain: chain0_iv0 - Obfuscated starting points for 2nd-16th chain: chain{1,15}_obfuscated_iv - Number of nodes in each chain: 200,000,000,000 - Public key containing the bounty: hashed_secret At this point the public can see what the bounty is for unlocking the secret by seeing how many coins the informant sent to hashed_secret. The public can also voluntarily send more coins to the bounty address to entice people to unlock it! But, unlike the informant, the public has no way to parallelize the computation of the chains. They have to compute them sequentially using a single CPU core, hence taking approximately 32 days. We know it will take approximately 32 days for any single individual to unlock the secret, because the serial speed of a hash function is constrained to a narrow range and typically does not vary much from low-end to high-end CPUs. A top-of-the-line Intel 22nm Haswell 3GHz+ CPU core might do approximately 2 million SHA256 hash/sec, whereas a low-end laptop CPU will still perform decently at ~1 million hash/sec. So no matter what hardware a person attempting to unlock a secret has access to, it should take roughly 16-32 days. From what I have seen in the Bitcoin ASIC industry, a custom designed 22nm chip may do 10 million hash/sec serially (keep in mind most chips get their speed from many parallel SHA256 blocks), but even then, it is only a factor 10x off the speed of a low-end CPU. So the informant still has a pretty good control (within a 1x-10x range) on how long the secret will be remain locked. And again, it doesn't matter if you make 1 or 10,000 chips, the unlocking cannot be parallelized in any way. [1] https://en.bitcoin.it/wiki/Protocol_specification#Addresses https://en.bitcoin.it/wiki/Protocol_specification#Addresses
- schoen 12y ago
  Is there any way for the public to verify that the bounty can actually be claimed by doing the work? Or do they have to rely on the honesty of the person announcing the bounty? In other words, is there something that stops me from saying that a certain computation that I want people to do will allow claiming the bounty associated with a certain Bitcoin address, when in fact the private key is some completely distinct key that I control and that has nothing to do with the time-lock computation?
  - pacofvf 12y ago
    maybe you can split the bounty into 14 parts and use chain{1,15}_iv0 as secrete keys. So now is not a winner takes all. Also you create more competition to ensure your lock is opened.
    - mhei 12y ago
      I believe this is what Peter Todd did. At least his mail contains 32 bitcoin addresses, each with a balance of 10mBTC.
  - mrb 12y ago
    It is not possible to verify the bounty can be claimed. pacofvf's idea is good though: distribute the bounty across the chains. If you find that the first bounty is missing, assume the informant was dishonest and abandon the work.
- mrb 12y ago
  Additional thought: I would love to see an implementation of time-locked secrets for GPUs. They are such massively parallel architectures that this would allow the informant to spend very little time computing the chains, while requiring a lot of time for the public to unlock it. For concrete numbers: I wrote a Bitcoin miner for AMD GPUs (which was at some point the fastest available). A single ALU on the Radeon HD 6990 can do about 500k SHA256 hash/sec (~1/4 the speed of a high-end CPU core). But it has 3072 ALUs. So the informant could spend ~1 day GPU-time-locking a secret that would take ~2 years to CPU-unlock!
gwern 12y ago
For background on timelocks, I recommend my own essay on the topic: http://www.gwern.net/Self-decrypting%20files http://www.gwern.net/Self-decrypting%20files (Incidentally, as far as I know, I'm the first person to propose the basic 'chained hashing' scheme: http://www.gwern.net/Self-decrypting%20files#hashing http://www.gwern.net/Self-decrypting%20files#hashing I don't know if Todd or Taaki invented it independently or not.)
- petertodd 12y ago
  For the record, it was your essay which is where I first learned about the idea; I'll add a link to it in the README. My contribution to the idea is only the trick with Bitcoin addresses, and even that Takki deserves co-credit for as well.

70 points by roasbeef 12y ago

mrb 12y ago

This is an interesting concept and implementation. Allow me to re-explain how it works, because IMHO the documentation is a bit confusing and light on some details. Say an informant wants to time-lock a secret (eg. a key to decrypt an encrypted document) so that it must take the public approximately 32 days of compute time to be unlocked, regardless if the public has a super-computer or is Joe Six Pack with a typical home computer. Well, this informant has a 16-core machine. So he selects 16 random initialization vectors (chain{0,15}_iv0) and calculates in parallel 16 chains of serial SHA256 calls, thereby fully utilizing his CPU: SHA256(chain0_iv0) -> chain0_iv1; SHA256(chain0_iv1) -> chain0_iv2; ... SHA256(chain1_iv0) -> chain1_iv1; SHA256(chain1_iv1) -> chain1_iv2; ... ... SHA256(chain15_iv0) -> chain15_iv1; SHA256(chain15_iv1) -> chain15_iv2; ... After 2 days, the informant has spent 32 CPU-days of compute time calculating the chains, reaching the 200,000,000,000th node on each chain: chain0_iv200000000000 chain1_iv200000000000 chain2_iv200000000000 ... chain15_iv200000000000 Now he obfuscates the starting points of 15 of the 16 chains (keeping chain0_iv0 as is, but obfuscating chain{1,15}_iv0): chain0_iv200000000000 ^ chain1_iv0 -> chain1_obfuscated_iv chain1_iv200000000000 ^ chain2_iv0 -> chain2_obfuscated_iv ... chain14_iv200000000000 ^ chain15_iv0 -> chain15_obfuscated_iv (^ is the XOR operation) The informant is going to publish chain0_iv0 and chain{1,15}_obfuscated_iv so that the public is forced to fully calculate chain0, then XOR the result with chain1_obfuscated_iv to be able to calculate chain1, and so on, until chain15. This is a crucial aspect of the concept: the informant can parallelize work on the chains, while the public is forced to compute them serially. The informant uses the last node of the last chain (chain15_iv200000000000) as a Bitcoin private key (a 256-bit ECDSA key), and sends the bounty (a certain number of coins) to it. The informant calculates the corresponding ECDSA public key, and hashes it with SHA256: this is the secret (eg. a cryptographic key) that is time-locked. The informant also calculates the RIPEMD160 hash of the secret and publishes it: this is hashed_secret, which is a (public) Bitcoin address. This two-hash process is the standard algorithm by which Bitcoin calculates public addresses from private keys [1]. This two-hash process is re-used here so that the moment someone withdraws the bounty, the side-effect is that the Bitcoin blockchain automatically lets everyone instantly calculate the secret. Indeed: the bounty-claiming Bitcoin transaction itself reveals the ECDSA public key, so anybody who sees it can SHA256-hash the pub key to get the secret. All in all, the informant publishes: - Starting point for 1st chain: chain0_iv0 - Obfuscated starting points for 2nd-16th chain: chain{1,15}_obfuscated_iv - Number of nodes in each chain: 200,000,000,000 - Public key containing the bounty: hashed_secret At this point the public can see what the bounty is for unlocking the secret by seeing how many coins the informant sent to hashed_secret. The public can also voluntarily send more coins to the bounty address to entice people to unlock it! But, unlike the informant, the public has no way to parallelize the computation of the chains. They have to compute them sequentially using a single CPU core, hence taking approximately 32 days. We know it will take approximately 32 days for any single individual to unlock the secret, because the serial speed of a hash function is constrained to a narrow range and typically does not vary much from low-end to high-end CPUs. A top-of-the-line Intel 22nm Haswell 3GHz+ CPU core might do approximately 2 million SHA256 hash/sec, whereas a low-end laptop CPU will still perform decently at ~1 million hash/sec. So no matter what hardware a person attempting to unlock a secret has access to, it should take roughly 16-32 days. From what I have seen in the Bitcoin ASIC industry, a custom designed 22nm chip may do 10 million hash/sec serially (keep in mind most chips get their speed from many parallel SHA256 blocks), but even then, it is only a factor 10x off the speed of a low-end CPU. So the informant still has a pretty good control (within a 1x-10x range) on how long the secret will be remain locked. And again, it doesn't matter if you make 1 or 10,000 chips, the unlocking cannot be parallelized in any way. [1] https://en.bitcoin.it/wiki/Protocol_specification#Addresses https://en.bitcoin.it/wiki/Protocol_specification#Addresses

schoen 12y ago
Is there any way for the public to verify that the bounty can actually be claimed by doing the work? Or do they have to rely on the honesty of the person announcing the bounty? In other words, is there something that stops me from saying that a certain computation that I want people to do will allow claiming the bounty associated with a certain Bitcoin address, when in fact the private key is some completely distinct key that I control and that has nothing to do with the time-lock computation?
- pacofvf 12y ago
  maybe you can split the bounty into 14 parts and use chain{1,15}_iv0 as secrete keys. So now is not a winner takes all. Also you create more competition to ensure your lock is opened.
  - mhei 12y ago
    I believe this is what Peter Todd did. At least his mail contains 32 bitcoin addresses, each with a balance of 10mBTC.
- mrb 12y ago
  It is not possible to verify the bounty can be claimed. pacofvf's idea is good though: distribute the bounty across the chains. If you find that the first bounty is missing, assume the informant was dishonest and abandon the work.
mrb 12y ago
Additional thought: I would love to see an implementation of time-locked secrets for GPUs. They are such massively parallel architectures that this would allow the informant to spend very little time computing the chains, while requiring a lot of time for the public to unlock it. For concrete numbers: I wrote a Bitcoin miner for AMD GPUs (which was at some point the fastest available). A single ALU on the Radeon HD 6990 can do about 500k SHA256 hash/sec (~1/4 the speed of a high-end CPU core). But it has 3072 ALUs. So the informant could spend ~1 day GPU-time-locking a secret that would take ~2 years to CPU-unlock!

gwern 12y ago

For background on timelocks, I recommend my own essay on the topic: http://www.gwern.net/Self-decrypting%20files http://www.gwern.net/Self-decrypting%20files (Incidentally, as far as I know, I'm the first person to propose the basic 'chained hashing' scheme: http://www.gwern.net/Self-decrypting%20files#hashing http://www.gwern.net/Self-decrypting%20files#hashing I don't know if Todd or Taaki invented it independently or not.)

petertodd 12y ago
For the record, it was your essay which is where I first learned about the idea; I'll add a link to it in the README. My contribution to the idea is only the trick with Bitcoin addresses, and even that Takki deserves co-credit for as well.