J. Lopp's Post-Quantum Migration BIP

[ABCbits]

Focusing solely on the information from that chart, if you told me to pick one even if it is terrible I wouldn't be able to choose TBH right away because the tradeoffs are extreme in one thing or another. What about you ABCbits? @d5000 you too, which one would you chose if you had to?

Actually we've discussed this in past, https://bitcointalk.org/index.php?topic=5550298.msg65630757#msg65630757. I still think Falcon-512 is least worst option, regardless signature aggregation could happen (without new security issue or much higher computation) or not.

--snip--
But I think it is much more likely, that if 4 MB limit will be kept as it is, then people will do everything they can, to pick a signature, which will take the least amount of space. Because this is the thing, that is the easiest one to deploy in existing testnets, and because all old nodes could simply treat it as valid through OP_SUCCESS (so the whole cost will be paid only by new nodes, and everyone else will continue using secp256k1, for as long, as they can).

In such scenario, SQIsign would be most desirable choice based on table i shared earlier. But it would make spending Bitcoin from current hardware wallet and other device without fast/optimized CPU impractical since almost no one wants to wait that long for creating Bitcoin TX.

[Wind_FURY]

Are you actually trying to make a debate that the community shouldn't treat this as something urgent? Because people who know more than you have actually shortened the timeline for the arrival of the Quantum Threat.

People who have a financial interest and whose entire career depends on this, and people who have otherwise malicious motives -- Here, fixed that nonsense for you.

Your opinion, and you talk like you know better. You don't. You're merely a pleb in a signature campaign like the rest of us.

In my personal opinion, the Core Developers, the community including plebs like us should probably start to focus on learning/talking about the Quantum Threat and spend less time on foolish things like debating about BIP-110.

There is absolutely nothing to debate at this time with most people. The community has nothing to debate at all yet. Should I ask random internet plebs which signatures are the least likely to be compromised by some future QC breakthrough and which have the best engineering tradeoffs? Don't tell me that social media actually made you that retarded.

 

Plus the Core Developers should start working on it sooner rather than later, no?

Developers develop within their own competencies. Cryptographers do cryptography, learn the difference. 99.9% of developers are not cryptographers and do not know cryptography. So most developers are not going to be doing anything at all about this up until the point in time where there is something to review or code up, and we are far from this.

Justin Drake of the Ethereum Foundation has started to work with the leading researchers in Quantum Computing. The Monero Research Labs have also started doing their own initiative to make Monero Quantum Resistant. The Core Developers WILL NOT merely wait and do nothing.

[d5000]

-snip-

I read a bit more and there is actually a problem with the SHRINCS proposal that would make it unpractical to use for Bitcoin: It is a "stateful" method. If I interpreted ELI5-style explanations of that phenomenon correctly, the problem is the following:

Each time you sign a transaction, the "state" of the cryptosystem changes. The private key doesn't consist of a single number but of a tree of numbers. In each signature, other leaves of the tree are used.

The big problem is: If you use one of the leaves twice by accident, this can give an attacker enough information to get the whole key "tree" and then they can steal your coins. So this must be avoided at all cost.

This means that each time you sign a transaction you need to update all your backups with the "state" of the key tree. Effectively this would make it very unpractical to use on more than a single device, and saving the key isn't as simple as simply storing a seed phrase because you need the state too.

Thus Blockstream Research im March came up with an updated proposal called SHRIMPS which doesn't have that problem. It has smaller signatures than SPHINCS+ but much larger than the original SHRINCS (about 2500 bytes) which again would severely restrict the blockchain.

Regarding verification speed, some short info from Google confirms that the "stateless" SPHINCS+ is the most expensive and validation costs almost 20x more than for the "stateful" SHRINCS. SHRIMPS is on a middle ground (about 7x less validation cost than SPHINCS+).

We need someone to keep a table of these signature proposals updated, perhaps you could use another hobby project -- you definitely do not have many threads open.  

I'll try to gather more information about these proposals, and if I think I've a slightly more informed opinion I can start that thread.

[Satofan44]

-snip-

I read a bit more and there is actually a problem with the SHRINCS proposal that would make it unpractical to use for Bitcoin: It is a "stateful" method. If I interpreted ELI5-style explanations of that phenomenon correctly, the problem is the following:

Each time you sign a transaction, the "state" of the cryptosystem changes. The private key doesn't consist of a single number but of a tree of numbers. In each signature, other leaves of the tree are used.

The big problem is: If you use one of the leaves twice by accident, this can give an attacker enough information to get the whole key "tree" and then they can steal your coins. So this must be avoided at all cost.

This means that each time you sign a transaction you need to update all your backups with the "state" of the key tree. Effectively this would make it very unpractical to use on more than a single device, and saving the key isn't as simple as simply storing a seed phrase because you need the state too.

I was a bit more focused on the scaling metrics themselves or something fundamentally broken rather than the general practicability of the proposal when I wrote this, but I had not fully read it at the time. Absolutely this is a no-go for overall adoption as we do not have the level of urgency present that would require such a massive tradeoff (even though technically we could go with this), and it would be better to wait a few more years than to go with this proposal when it comes to that aspect. However, perhaps the reason for which they published it anyway was that it was an intermediary solution until they figured out a good way to make it stateless as it is worthwhile progress.

Thus Blockstream Research im March came up with an updated proposal called SHRIMPS which doesn't have that problem. It has smaller signatures than SPHINCS+ but much larger than the original SHRINCS (about 2500 bytes) which again would severely restrict the blockchain.

Regarding verification speed, some short info from Google confirms that the "stateless" SPHINCS+ is the most expensive and validation costs almost 20x more than for the "stateful" SHRINCS. SHRIMPS is on a middle ground (about 7x less validation cost than SPHINCS+).

Looks better, but based from the lack of comments and the date of posting it seems that this is still early but it is a good topic to follow. Nevertheless, these 2 proposals alone disprove any claims that nobody is working on it or that it is not being taken as seriously as it should be but not more than that (contrary to the anxiety-fueled crowd that keeps trying to create panic about this). As I keep saying, most developers are not going to be working on this --  heck most developers would not even be able to do a proper benchmark and comparison between these things^note.  Let's keep following and see what happens, hopefully nobody opens more threads about quantum bullshit in this section. The few users that contribute something to this section need to stick to 1 thread, either this one, or another one something like a "QC megathread" where everything relevant gets posted. It won't become a spam fest as long as it is kept in this section.

Note: People who barely have any skills at all are criticizing those who are slowly developing new cryptography, which for such idiots is essentially the same as magic. 

[Pmalek]

There is a recent video of Adam Back talking about quantum computers and whether or not they represent a threat to Bitcoin. He believes the current hardware that Google and other companies are currently researching is very basic and lacks error correction. Google hopes that with future research and development, these "supercomputers" will get better. He doesn't recognize an immediate threat, though.

However, he also says that it would be smart to start preparing Bitcoin for a quantum-safe algorithm ahead of time and before such a threat becomes imminent. He suggests that users should have a decade to perform the migration to a quantum ready system.

[Satofan44]

There is a recent video of Adam Back talking about quantum computers and whether or not they represent a threat to Bitcoin. He believes the current hardware that Google and other companies are currently researching is very basic and lacks error correction. Google hopes that with future research and development, these "supercomputers" will get better. He doesn't recognize an immediate threat, though.

How recent? There have been many advances in the last 2 years which involve all sorts of error correction, so therefore to claim that they do not have error correction at this time would be incorrect. Whether the error correction is sufficient for the large scale operations that are going to be needed in order to derive private keys accordingly is a different question. We do not know, nobody knows that is why things are all about "estimates" and there is no specific date that anyone can provide.

https://blog.google/innovation-and-ai/models-and-research/google-deepmind/alphaqubit-quantum-error-correction/
https://arxiv.org/html/2410.00917v1#S2
https://research.google/blog/making-quantum-error-correction-work/

Today we introduce Willow, the first quantum processor where error-corrected qubits get exponentially better as they get bigger.

Very old news for an industry like this though. Enjoy reading.

However, he also says that it would be smart to start preparing Bitcoin for a quantum-safe algorithm ahead of time and before such a threat becomes imminent. He suggests that users should have a decade to perform the migration to a quantum ready system.

As I have repeatedly written, and even quoted gmaxwell -- those that need to be working on this are working on it at the appropriate pace. That is all there is to it. Most users do not know enough about these things and are addicted to speed and gratification due to the negative impacts of modern society. You can't speed up "solving" this, you can only make it more error prone.

[BlackHatCoiner]

Another argument to consider, that may sound weak at first, but practically sound is that, whenever this quantum computer, with enough physical qubits is implemented, it does not mean that random entities will have access to it. It will probably be owned by Google or some tech giant, that has not built it for the purpose of attacking bitcoin. This matters because, long before it becomes a real threat, we will have already been forced to devise a solution.

[Satofan44]

Another argument to consider, that may sound weak at first, but practically sound is that, whenever this quantum computer, with enough physical qubits is implemented, it does not mean that random entities will have access to it. It will probably be owned by Google or some tech giant, that has not built it for the purpose of attacking bitcoin. This matters because, long before it becomes a real threat, we will have already been forced to devise a solution.

I wrote about this on the past 2 pages, but some shitposters dismissed it because they are unfamiliar with the concept called rule of law. The timeline of this becoming an issue is completely different if it is only Google who manages to achieve this by 2030. If it is not only Google but instead multiple parties around the whole world, then we may have an issue. However, read also the discussion with gmaxwell and me -- he raises a good point. There will be countless money-raising scams associated with this because scammers will sell the ability of being able to unlock satoshi's coins as we are "almost there yet". It is a clusterfuck like most "innovations" in recent years, there was almost not a single case where the actual achievements and benefits were as they the investors claimed they would be. Again, this even includes a huge assumption that Google will be able to do it by then -- they do not know, we do not know, nobody knows. We will see.

Whether it is shitcoins with their hundreds of random buzzwords in the last 10 years, machine learning, "AI", LLMs or whatever other fuckery happened in the last 10 years. But but this is different, these researchers are serious people whose job and whole career definitely does not depend on the success of the quantum research. I guess Scam Altman also does not depend on the success of his "AI" either.  

Of course it does, learn how to world works. This is very different from just anyone can do it -- it gives us a significant amount of extra time to do something about this. If only Google is able to do this in 2030, that also means that no nefarious entity will be able to do it until 2035, 2040, 2050 or even beyond. We do not KNOW the exact timeline. Stop pretending like someone knows, they fucking don't.

Here it is, you can read some responses before and after. Google would not be legally allowed to steal these coins under any circumstance. A trillion dollar company would risk itself over a couple billions? People need to stop watching Netflix so much, their brains are fried with imaginary bullshit scenarios.

[fillippone]

Another argument to consider, that may sound weak at first, but practically sound is that, whenever this quantum computer, with enough physical qubits is implemented, it does not mean that random entities will have access to it. It will probably be owned by Google or some tech giant, that has not built it for the purpose of attacking bitcoin. This matters because, long before it becomes a real threat, we will have already been forced to devise a solution.

Not corporations, rather governments.
The amount of research, energy, and resources needed to research, build, and operate a CRQC is well outside the possibilities of any corporation. Think about the Fusion reactor being built in France.

Something that wasn't adequately analysed in the latest Bernstein research paper.

Bernstein says quantum is a 'manageable upgrade cycle' for Bitcoin, not an existential threat

[She shining]

I'll try to gather more information about these proposals, and if I think I've a slightly more informed opinion I can start that thread.

It has some gaps but a proposal nonetheless. You can check it out here. https://groups.google.com/g/bitcoindev/c/Q06piCEJhkI. The biggest issue is that it would change the current verification method.

[Pmalek]

How recent? There have been many advances in the last 2 years which involve all sorts of error correction, so therefore to claim that they do not have error correction at this time would be incorrect. Whether the error correction is sufficient for the large scale operations that are going to be needed in order to derive private keys accordingly is a different question. We do not know, nobody knows that is why things are all about "estimates" and there is no specific date that anyone can provide.

He mentioned that the computers don't have sufficient error correction. That's what he was trying to say. The video is fairly recent because he also discusses Blockstream's new and allegedly quantum-safe system on the Liquid L2 layer, and this is no more than a couple weeks old news. Therefore, the video interview was conducted after it was made public.

[Satofan44]

Robustness against cryptosystem breaks-- quantum or otherwise-- is a prudent and reasonable concern, and it's good to let people decide how to secure their own coins even if you don't share the same security concerns as them.  Keeping someone who wants their coins secured by something other than just ECC having an option would be incompatible with Bitcoin's ethos exactly like the knotzis trying to kneecapp multisig and descriptor wallets.  It's just a question of constructing a scheme that is efficient enough in the right ways that it won't have a big adverse impact on those who don't care about it, and I think progress in that direction looks pretty good.

Here is an authority that was more active in the past, basically confirming what I have said numerous times.

It is not a reversible computation.

Yes it is, but it is considered unfeasible.

Elliptic curve point addition is claimed (ZK-proved) to be REVERSIBLE in a CLASSICAL COMPUTING way. Is no one bothered at all?

Of course it is reversible, because you have 1:1 mapping between private and public keys. If you use some weaker elliptic curve, and you start using bigger and bigger numbers, then you will see, that each and every valid public key has exactly one matching private key.

If this is what you were trying to talk about, my bad -- though nothing groundbreaking. We knew this was coming, so I still don't get what the so called big deal is supposed to be according to you kTimesG.

@d5000 you too, which one would you chose if you had to?

Ugh. I'm not an expert of this at all, but as I'm not that bad at googling, here's my (only slightly "informed") opinion:

As you can see here by some members and in many other threads, people want random "community members" to give their "expert" opinion on this -- so why the hell not, we might as well join their game. 

- For now, hash based schemes like SPHINCS+ seems to be the safest option. They're based on well known mathematical properties, and hashes are also "holding the blockchain together". Jonas Nick has proposed a variant called SHRINCS with signature sizes of 272 bytes, which is even better than FALCON. FALCON and lattice-based systems seem more experimental and complex.
- For the long term, SQIsign looks nice, but it seems it's the most experimental and untested of all these variants. I think the main problem, the cost of creating a signature, is not that much of a bottleneck than block sizes. The verification cost could however increase the cost of running a full node. If my googling results are correct, if the current Bitcoin blockchain was based on SQIsign, the initial blockchain download would take about 6 months with consumer hardware. The bottleneck seems to be mainly the CPU.

Thanks for the link, that variant solves the issue of signature sizes for SPHINCS. What about the verification and signing cost? We need someone to keep a table of these signature proposals updated, perhaps you could use another hobby project -- you definitely do not have many threads open. 

Signing and verification time:

    Stateful signing time:                  3742.92 ms
    Stateful verification time (local):     0.015506 ms
    Stateless signing time:                 17974.8 ms
    Stateless verification time (local):    0.073762 ms

Machine: Intel Core i5, 16 GB RAM (one thread, w/o parallelization)

Someone posted this in there. While it does not directly translate into the overview post that we have, if we extrapolate from it then it seems that it constitutes a massive improvement over the issues that SPHINCS has for our context.

Focusing solely on the information from that chart, if you told me to pick one even if it is terrible I wouldn't be able to choose TBH right away because the tradeoffs are extreme in one thing or another. What about you ABCbits? @d5000 you too, which one would you chose if you had to?

Actually we've discussed this in past, https://bitcointalk.org/index.php?topic=5550298.msg65630757#msg65630757. I still think Falcon-512 is least worst option, regardless signature aggregation could happen (without new security issue or much higher computation) or not.

Good find, I honestly do not remember that anymore -- the forum is terrible at moderating, and allows any amount of duplicate topics as long as there is a public person/entity that said anything "new" so I have quantum fatigue.  Check out the modified SPHINCS proposal that d5000 linked to. Unless there is some major issue with it that I am not seeing right now / or that has not been found yet, it seems to me that it would be the best choice from what we have at this moment (at least from the ones presented here).

Some user here even recently argued against preventing the creation of new P2PK outputs, which is an opposition as stupid and ridiculous as it gets.

You probably underestimate, how hard it would be, to actually abandon secp256k1. I think many people would agree to drop P2PK support entirely, if it could be done easily. However, it has some consequences, for example: there could exist some pre-signed, timelocked transactions, which would use it. And then, if you block it on consensus level, then these transactions would be turned from valid into invalid, and they could no longer be included later. Even for things like P2SH, old outputs were not blocked just like that: the old way of moving coins was only made non-standard, but not invalid.

I definitely am underestimating it, but the reasoning provided was not technical difficulty but some normie bullshit about never removing anything that was introduced into Bitcoin -- which is not a good approach long term. If something bad happens down the road because of technical debt, they would blame the developers, reviewers, or whoever else except themselves and those who favored such views.

Also, as mentioned previously by Saint Wenhao, we have an example of a cryptographic primitive, where people thought, that it would be just "replaced", but the reality proven otherwise: SHA-1. When Git will migrate from SHA-1 to SHA-256, or anything else? Never? Because now, they migrated only to "hardened SHA-1", as well as many other entities. Before 2017, people thought, that if some hash function will be broken, then it will be simply replaced. But in case of SHA-1, it didn't happen: old systems just received some "patches", and now we know, that if something is heavily used in many places, then it will be endlessly "hardened", instead of being "replaced", because this is just how the backward compatibility works in our world.

I am not a big fan of endless backward compatibility. Fairly long compatibility like Bitcoin has is great, extremely long or until something breaks is not in my view.

But I think it is much more likely, that if 4 MB limit will be kept as it is, then people will do everything they can, to pick a signature, which will take the least amount of space. Because this is the thing, that is the easiest one to deploy in existing testnets, and because all old nodes could simply treat it as valid through OP_SUCCESS (so the whole cost will be paid only by new nodes, and everyone else will continue using secp256k1, for as long, as they can).

Why not both though? We should pick the signatures that come with the best balance of the least cost across all the 3 main metrics, size, signing and verification and couple it with a small discount?

Which means, that the answer to the question "which signatures" is simple: anything, that could be deployed faster, than other competitors. If you want to join that race, then just pick anything you like, and push things forward. Because in the open-source world, things are not picked, because they are better: for many things we use, there are cheaper, faster, and better alternatives. But Bitcoin Core is not written in C++, because it is the best language: it is written in that way, just because Satoshi decided to do so, and deployed the first working client faster, than other mailing list readers, who also read the whitepaper. Which also means, that we won't necessarily have "the best possible thing in existence". Instead, we will have "the earliest deployed thing", and we will be stuck with it for years or decades.

Well, the question is always is there are race yet. If we create a false urgency at a time where it is not required, we run into a risk of deploying something that is terrible and is going to bite us in the long run. That is why panic and urgency are always wrong when it comes to these things. Any amount of extra time that can assuredly be utilized for research and during which there is no risk is extremely beneficial. If we had decided on a candidate and deployed it some years ago we would have picked something that is much worse than what is available now. Balanced approach is what we need, not anxiety over media PR.

By the way: do I like, that our world is constantly patched? Of course I don't. And many other people would happily replace old systems with new inventions, if it would be simple. But this is not how the world works, and there are many examples, where things are not replaced, unless you find a very critical vulnerability, where everything fully collapses instantly, like in Value Overflow Incident. Only then you can hard-reject old things: because the old system is no longer usable.

The reason why we end up in very critical vulnerabilities that make things completely collapse anyway is primarily because we don't replace systems with things that are much better beforehand. Excellent post by the way.

[tbtftg]

Google would not be legally allowed to steal these coins under any circumstance. A trillion dollar company would risk itself over a couple billions?

Of course, when they announce they are able to steal those coins, and the network is still not quantum-safe, the price of bitcoin will be zeroed overnight, and it won't ever recover. That's how the world works. They don't have to actually steal anything.

[Satofan44]

Google would not be legally allowed to steal these coins under any circumstance. A trillion dollar company would risk itself over a couple billions?

Of course, when they announce they are able to steal those coins, and the network is still not quantum-safe, the price of bitcoin will be zeroed overnight, and it won't ever recover^note. That's how the world works. They don't have to actually steal anything.

Bitcoin does not stop working because quantum computers exist. You watch way too many TV shows and movies like most people here, and you are biased towards inventing all sorts of unrealistic scenarios because of that. I will announce tomorrow that I can steal those coins. Will you dump the Bitcoin that you don't own anyway? Why won't you? What is the difference between me and Google? Now you want to trust an entity when others here say they "shouldn't be trusted" (even if it is was not a question of trust)?

An announcement of ability whether by Google or someone else is useless, it is the equivalent of a scam or grift and there will be plenty relating to quantum computers. A simple demonstration of the ability is needed for it to be absolutely provably true, everything else is bullshit by various biased parties -- whether they are amateurs or proclaimed "experts" does not matter, most of them are biased in one way or another. Once this simple demonstration is done by a legal entity on someone else's address say satoshi's, it will be served lawsuits the day after. Congrats, you played yourself.    The irony here is that this ability does not change anything at all whether Bitcoin is "ready or not", in both cases Google is not able to take the coins from anyone -- neither satoshi, nor me or any other user. When this does eventually happen, many users will not be upgraded to the adequate addresses in time. Does Bitcoin stop working for them? Will they dump it to zero?
Note: Bitcoin obituary number 5483.  

It is time for many of you to grow up.

[She shining]

Google would not be legally allowed to steal these coins under any circumstance. A trillion dollar company would risk itself over a couple billions?

Of course, when they announce they are able to steal those coins, and the network is still not quantum-safe, the price of bitcoin will be zeroed overnight, and it won't ever recover. That's how the world works. They don't have to actually steal anything.

A shitcoiner would always be a shitcpiner. How you thought of this is beyond me. The envisioned risk is on a specific type of address and people that reuse addresses not Bitcoin itself. Here we assuming Bitcoin is stagnant. Bitcoin has an higher chance of hitting a million dollar than zero.