4 ms·

I only skimmed the post, but referring to the blackbox approach with some blockchain as trustless clock: Given the black box was created when block X was the c

I only skimmed the post, but referring to the blackbox approach with some blockchain as trustless clock: Given the black box was created when block X was the current one and is defined to release the key some N days later, so ca. (N * 144) blocks later, if the bitcoin blockchain with a block time of 10 minutes is used. Wouldn't an attacker be able to create an isolated network using the existing blockchain up to block X, push the difficulty in this "new" network artificially down and create the amount of required blocks much faster than the actual bitcoin network. Once the chain is calculated up to a specific point, the blackbox program can be executed in the emulated network and will release the key before the actual deadline. Am I missing something or is this conceptually broken?

progval 7y ago
This probably assumes you can't trick the program into connecting to the wrong bootstrap nodes.
- vbrandl 7y ago
  But this means that there is a trusted party involved: the bootstrap nodes. Those might not exist anymore in the future. If they don't, the key cannot be released anymore? In my opinion something like this must not depend on the online status of some nodes. I think, for the black box to be truly trust-less, it must be a `f: Blockchain -> Maybe DecryptionKey`. And then you can provide a specifically crafted blockchain to extract the key...
- DagAgren 7y ago
  Such a program would certainly not be connecting to any network itself.
gwern 7y ago
> Wouldn't an attacker be able to create an isolated network using the existing blockchain up to block X, push the difficulty in this "new" network artificially down and create the amount of required blocks much faster than the actual bitcoin network. You would need to invest an enormous amount of hashpower to create so many blocks that the difficulty adjustment could ratchet down (and if you don't, it's an invalid blockchain period), and this expensive attack can be blocked simply by changing the witness proof to require blocks have a certain minimum hashpower on average, which will be safe since hashpower has historically only gone up, and lets you specify the total cost of unlocking for anyone, which, like PoW, is your security factor.
- vbrandl 7y ago
  > You would need to invest an enormous amount of hashpower to create so many blocks that the difficulty adjustment could ratchet down Thanks for the clarification. I don't know much about the difficulty adjustment algorithm of bitcoin so that's the point I was missing. So I guess there are some mechanisms like "the difficulty can only be adjusted every N blocks" and "the difficulty can only rise/sink by X%"? If that's it and the deadline for when the key should be released is far enough in the future (e.g. 50 years?), it might still be feasible for an attacker to implement such an attack? > simply by changing the witness proof to require blocks have a certain minimum hashpower on average This assumes, bitcoin is an ever growing network and will never loose miners below a certain point. Depending on how long the key should be secret, this assumption might not hold true and I wouldn't depend on it.
  - gwern 7y ago
    > So I guess there are some mechanisms like "the difficulty can only be adjusted every N blocks" and "the difficulty can only rise/sink by X%"? Yes. So you can manufacture your own blockchain, but you can't simply mint 1 block, declare difficulty just dropped 99.999%, and mint a bazillion more blocks after that. I never worked it out but you'd need to invest like months of current blockchain hashpower to make a pseudo-chain which would do nothing but unlock some timelocks (you can't even try to double-spend anyone, because their clients will follow the heavier chain, which will be the public one). > If that's it and the deadline for when the key should be released is far enough in the future (e.g. 50 years?), it might still be feasible for an attacker to implement such an attack?...Depending on how long the key should be secret, this assumption might not hold true and I wouldn't depend on it. Yes. This is an inherent feature of all work-based timelocks: the further out you go, the more uncertain things are. Rivest's timelock contest is a good demonstration of the empirical difficulties - the squaring timelock looked like it wasn't going to be unlocked on schedule until, out of nowhere, two different groups unlocked it with different approaches. So, you decide what your tradeoff is. Do you want to make as sure as possible that it doesn't unlock early, because too early is catastrophic? Then you require a lot of hashpower and you set a very high minimum hash per block, at the risk of hashpower slowing down and your timelock taking much longer than you expected. Are you worried about it not being unlocked on time? Then you require relatively less hashpower and have looser constraints. It's like PoW: how many transactions do you wait before deciding a transaction is 'real'? If you're in a hurry, maybe you use 0-conf; if you're an exchange transacting $1b in a single block, perhaps you'd better wait a few hundred blocks just to be absolutely certain.
rocqua 7y ago
It seems that bitcoin doesn't have limits in the difficulty adjustment, but I am pretty sure Monero does. If your black box checks these limits, that sets up a hard limit on how low you can get the difficulty. Which means that (over sufficiently short times) you'd still need a significant fraction of the publicly available hashing power to create such a forged chain. As an alternative, you could set a limit of 'at least N blocks, and at least X accumulated difficulty'. This way any forks with reduced hashing power wouldn't reach the accumulated difficulty requirement. Edit: I was wrong, bitcoin has a maximum difficulty factor of 4. So you could decrease the difficulty by 4 every 2 weeks.

progval 7y ago

This probably assumes you can't trick the program into connecting to the wrong bootstrap nodes.

vbrandl 7y ago
But this means that there is a trusted party involved: the bootstrap nodes. Those might not exist anymore in the future. If they don't, the key cannot be released anymore? In my opinion something like this must not depend on the online status of some nodes. I think, for the black box to be truly trust-less, it must be a `f: Blockchain -> Maybe DecryptionKey`. And then you can provide a specifically crafted blockchain to extract the key...
DagAgren 7y ago
Such a program would certainly not be connecting to any network itself.

gwern 7y ago

> Wouldn't an attacker be able to create an isolated network using the existing blockchain up to block X, push the difficulty in this "new" network artificially down and create the amount of required blocks much faster than the actual bitcoin network. You would need to invest an enormous amount of hashpower to create so many blocks that the difficulty adjustment could ratchet down (and if you don't, it's an invalid blockchain period), and this expensive attack can be blocked simply by changing the witness proof to require blocks have a certain minimum hashpower on average, which will be safe since hashpower has historically only gone up, and lets you specify the total cost of unlocking for anyone, which, like PoW, is your security factor.

vbrandl 7y ago
> You would need to invest an enormous amount of hashpower to create so many blocks that the difficulty adjustment could ratchet down Thanks for the clarification. I don't know much about the difficulty adjustment algorithm of bitcoin so that's the point I was missing. So I guess there are some mechanisms like "the difficulty can only be adjusted every N blocks" and "the difficulty can only rise/sink by X%"? If that's it and the deadline for when the key should be released is far enough in the future (e.g. 50 years?), it might still be feasible for an attacker to implement such an attack? > simply by changing the witness proof to require blocks have a certain minimum hashpower on average This assumes, bitcoin is an ever growing network and will never loose miners below a certain point. Depending on how long the key should be secret, this assumption might not hold true and I wouldn't depend on it.
- gwern 7y ago
  > So I guess there are some mechanisms like "the difficulty can only be adjusted every N blocks" and "the difficulty can only rise/sink by X%"? Yes. So you can manufacture your own blockchain, but you can't simply mint 1 block, declare difficulty just dropped 99.999%, and mint a bazillion more blocks after that. I never worked it out but you'd need to invest like months of current blockchain hashpower to make a pseudo-chain which would do nothing but unlock some timelocks (you can't even try to double-spend anyone, because their clients will follow the heavier chain, which will be the public one). > If that's it and the deadline for when the key should be released is far enough in the future (e.g. 50 years?), it might still be feasible for an attacker to implement such an attack?...Depending on how long the key should be secret, this assumption might not hold true and I wouldn't depend on it. Yes. This is an inherent feature of all work-based timelocks: the further out you go, the more uncertain things are. Rivest's timelock contest is a good demonstration of the empirical difficulties - the squaring timelock looked like it wasn't going to be unlocked on schedule until, out of nowhere, two different groups unlocked it with different approaches. So, you decide what your tradeoff is. Do you want to make as sure as possible that it doesn't unlock early, because too early is catastrophic? Then you require a lot of hashpower and you set a very high minimum hash per block, at the risk of hashpower slowing down and your timelock taking much longer than you expected. Are you worried about it not being unlocked on time? Then you require relatively less hashpower and have looser constraints. It's like PoW: how many transactions do you wait before deciding a transaction is 'real'? If you're in a hurry, maybe you use 0-conf; if you're an exchange transacting $1b in a single block, perhaps you'd better wait a few hundred blocks just to be absolutely certain.

rocqua 7y ago

It seems that bitcoin doesn't have limits in the difficulty adjustment, but I am pretty sure Monero does. If your black box checks these limits, that sets up a hard limit on how low you can get the difficulty. Which means that (over sufficiently short times) you'd still need a significant fraction of the publicly available hashing power to create such a forged chain. As an alternative, you could set a limit of 'at least N blocks, and at least X accumulated difficulty'. This way any forks with reduced hashing power wouldn't reach the accumulated difficulty requirement. Edit: I was wrong, bitcoin has a maximum difficulty factor of 4. So you could decrease the difficulty by 4 every 2 weeks.