(Incidentally, as far as I know, I'm the first person to propose the basic 'chained hashing' scheme: http://gwern.net/Self-decrypting%20files#hashing I don't know if Todd or Taaki invented it independently or not.)
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.
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:
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.
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!
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?
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.
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.
Can't I check the blockchain for all transactions around the time that the informant sent the bounty and just brute-force that? One of them will be the secret, no?
Also, can you clarify the process a bit after arriving at the secret? That was a bit confusing, what with the public ECDSA key, the wallet address, and the multiple secrets.
>Can't I check the blockchain for all transactions around the time that the informant sent the bounty and just brute-force that
Do check in from your private island after you finish doing so, since the next transaction on the blockchain you will brute force is presumably this one:
Being more serious, it should be emphasized that you're not by any means brute forcing Bitcoin transactions when you're doing this. He's just using a clever technique composed of crypto hash chains to hide a Bitcoin private key. It just happens to use the same SHA256 algo as Bitcoin mining does.
You don't need to monitor all the transactions in the block chain. The attacker gives you the exact address containing the bounty (hashed_secret). There is no extra information in the block chain that would make brute forcing easier. And brute forcing the public key directly is computationally unfeasible (O(2^256) complexity).
A Bitcoin (ECDSA) private address is a 256-bit binary blob: priv_key
The corresponding ECDSA public key is either represented as <x><y> (curve coordinates, "uncompressed format") or <sign><y> ("compressed format"): pub_key
A Bitcoin address (eg. 1BGbGFBhsXYq6kTyjSC9AHRe1dhe76tD6i) is basically: base58(RIPEMD160(SHA256(pub_key))), plus a version byte, plus a 16-bit checksum
So the "secret" is: SHA256(pub_key)
And the "hashed_secret" is: RIPEMD160(SHA256(pub_key))
Unless I'm missing something, the person with the fastest hashing processor will usually win. Thus there is never any reason to use an average processor, and everyone is not on the same playing field.
> Unless I'm missing something, the person with the fastest hashing processor will usually win.
You have to factor in power usage as well. Unlocking a 0.1 BTC bounty while spending 0.2 BTC on electricity isn't wise.
I mean, we can easily get to the point where unlocking a secret can cost hundreds of thousands of dollars in electricity. At that point, it's not about who's fastest, but who can unlock the secret without spending too much money.
Why would I want to do that? Remember, I'm just trying to make timelock encryption practical, which means we want a good estimate on what's the fastest implementation of the underlying chain kernel that exists now and will in the future. I really don't care who collects the bounty; if it's the same small group of people over and over again, so what? I do care that the best implementation possible - probably a highly clocked custom ASIC with exotic cooling - isn't that much faster than the best implementation possible without too much capital investment - probably a high-end overclocked FPGA with exotic cooling built by some kid in university as a term project.
Why is this based on a symmetric problem (encoder solving the same problem as the decoder) requiring two days of crunching on a 16 core machine? Is it because all known asymmetric problems (factoring primes, etc.) allow large speed-ups with parallelism?
Here, as long as you can afford a near-optimal SHA256 processor, more computing power doesn't help.
In the "successive squaring" method (see the essay posted by gwern), as long as you can afford a near-optimal modular multiplier, more computing power doesn't help.
In both approaches there is a constant cost of the near-optimal hardware, and a confidence level that the hardware is actually near-optimal. In SHA256 the cost is probably lower and the confidence level probably higher, but the difference is quantitative, and not qualitative.
(Incidentally, as far as I know, I'm the first person to propose the basic 'chained hashing' scheme: http://gwern.net/Self-decrypting%20files#hashing I don't know if Todd or Taaki invented it independently or not.)