Hacker News new | ask | show | jobs
by amluto 81 days ago
That’s kind of adorable. Would you need to pay to record a commitment? If so, how? If not, what stops someone from DoSing the whole scheme?
2 comments

I don't think you're understanding how cryptography works. A commitment is basically a hash that is both binding and hiding. In this example it's probably easiest to think of it as a hash. So you hash your post-quantum public key (something like falcon-512) and then sign that hash with your actual bitcoin private key (ecdsa, discrete-log, not quantum safe) and then publish that message to the bitcoin network. Then quantum happens at some point and bitcoin needs to migrate but where do funds go? Well you reveal the post-quantum public key and then you can prove that funds from the ecdsa key should go there. From a technical perspective, this is a complete and fool proof system. DoSing isn't really a concern if you publish to the actual bitcoin network and it's impossible for someone to use up the key space (2^108 combinations at least).

The reason this is a dumb idea is because coordination and timing. When does the cutover happen? Who decides which transactions no longer count as they were "broken" b/c of quantum computing? The idea is broken but not from technical fundamentals.

The DoS attack in this scenario is someone just submitting reasonable-looking but ultimately bad precommitments as fast as possible. The intuition is that precommitments must be hard to validate because, if there was an easy validation mechanism, you would have just used that mechanism as the transaction mechanism. And so all these junk random precommitments look potentially legitimate and end up being stored for later verification. So all you have to do to take down the system is fill up the available storage with junk, which (given the size of bot networks and the cost of storing something for a day) seems very doable.
If the question is storage, bitcoin itself provides a perfectly good mechanism. idk the exact costs but it'd be in the range of ~$0.45 to store a commitment. That's cheap enough to enable good users with small numbers of keys but also expensive enough to prevent spam. It's kind of the whole point of blockchains.

As for verification being expensive, it sounds like you don't know the actual costs. It's basically a hash. Finding the pre-image of a hash is very expensive to the point of being impossible. Verifying a pre-image + hash function = a hash is extremely cheap. That's the whole point of 1-way functions. Bitcoin itself is at ~1000 EH/s (exahashes per second)

Again, this isn't a technical problem. It's a coordination problem.

Commitment validation would indeed be trivial.

This whole scheme fails if an attacker can manage to delay a transaction for a day, and if the commitment also commits to a particular transaction fee, then the user trying to rescue their funds can’t easily offer a larger transaction fee if their transaction is delayed. But if the commitment does not commit to a transaction fee, then an attacker could force the transaction fee to increase arbitrarily.

Maybe the right strategy would be commit, separately, to multiple different choices of transaction fee.

Yes, that would be a concern. You could require a proof of work to submit a precommitment, so that DoSing was at least expensive to do. You could have some sort of deposit mechanism, where a precommitment would lock down 0.1 bitcoins (from a quantum-secure wallet) until the precommitment was used. I admit I'm glad I don't have to figure out those details.