Topic: Game theory involving Quantum Resistance protocol (Read 912 times)

Hi all guys and girls speaking in this exciting thread (finally someone speaking of QC!?!)

I will not actively step in to say more of what has been said but I would like to point you to https://faqq.info/

There you can find the Frequently Asked Quantum Questions, very informative

And last but not least an XMSS signature based cryptocurrency & blockchain exists and its running smoothly on mainnet for over 1 year now: www.theqrl.org

Cheers and keep this great discussion up, I will enjoy keeping read it. 

If Bitcoin wants to be digital gold, you can't be having arbitrary countdowns in which you are going to lose all of your affected funds unless you move them from A to B. That is what has been my point for a while.

However, what do you really and concisely propose? I have not seen convincing arguments, when it comes to avoiding the need for funds being moved in case of an exploit on the algorithm (QC attack or otherwise).

Perhaps it's something we can't avoid, and every generation or so, you will need to do this, at least once in your lifetime.
With gold, the analogy could be that you may need to reallocate all of your holdings... the place in which they are sitting isn't supposedly safe forever.

It is the true apples and oranges comparison, what you are doing. A digital asset, especially a cryptocurrency deposit is absolutely different artifact. I'm done rehashing the same argument over and over, it is the code, a constitutional right, for users not to be worried about developments and forks, their assets should be kept immune. period.

And it is not all about laziness (which is absolutely a right), people may be away for a long period of time from tech news, maybe they are paranoid about tracking/surveillance systems being watching them and trying to locate them, whales may feel uncomfortable with moving their strategic wallets, some may possibly lose their keys temporarily, others may have deposited their keys in a safe box to be handed to the heirs in a special occasion, ...

Plus, if missing a deadline should have a penalty it is not necessarily losing all funds. In my proposal users that you are calling them lazy have tp pay for it but in a reasonable way.

you are comparing apples and oranges!

your other arguments are like saying our browsers must not have stopped rejecting SHA1 SSL certificates because some people might be lazy in upgrading their certificate to a more secure hash algorithm even though there was a transition period given to everyone to move to new algorithms! instead they should have given the "lazy server" a workaround to push their SHA1 certificates as valid!!!

Firstly, it is a good compromise, not a bad one! Being rough and harsh against people because they have missed some deadline is neither a good practice nor a part of bitcoin culture.

Removing OP_CHECKSIGHASH is too harsh. Unlike what you say, people have no obligation to keep an eye on what pool operators and devs dictate. It is not part of the code, I've bought some coins as an eternally safe asset without signing any contract to be online or keeping an eye on anything. It is basic.

I think even talking about such a hypothetical fork hurts bitcoin and should be immediately stopped! No matter who first put it this way and in what condition such nonsense ideas have been formed in his mind (or probably he has been drunk or high?) but it is not what bitcoin is.
What if pools and wallet companies and devs decided (for the interests of their multi-billion business) to block terrorist wallets, e.g. because of US authorities threatening the whole community?  

if something were broken it must be removed right away. you can't compromise the entire multi billion dollar worth of system just because some people might be lazy!
when people enter bitcoin world the first thing they learn is that they are now responsible and in full control of their own money. that includes keeping an eye on development of bitcoin and changing directions if needed.

The protocol I suggested above, is safe and secure and a very good compromise saving everybody without taking rough measures against people who miss deadlines. You need to take another look at and sleep on it, imo.

I don't believe in antagonistic conflicts of interests between users but we all need to respect the code and destroying coins is not part of the code. I understand for exposed public keys there is no choice and should put the safety of the whole ecosystem first, but for unexposed ones, I see no justification for taking rough actions just because they are easier to implement.

you're missing the point. i've emphasized the relevant sentence in bold. we---the rest of the bitcoin economy---could theoretically pay for their carelessness. i find that unacceptable.

as a bitcoin holder, their interests are directly in conflict with mine. how do you plan to reconcile this? this network operates on the basis of economic rationality. you seem to expect us to embrace irrational behavior that threatens our financial interests. why?


what "deal"? what are you referring to as if some scripture exists re our duty of care obligations? at what point is putting the entire bitcoin economy's well being at stake not acceptable to you?

i don't believe duty of care implies the necessity to protect specifically irresponsible and unsafe behavior that can/will harm other people. it seems like you'd rather see bitcoin burned to the ground before budging on this. is that the case?

not sure, but maybe:

In the real world, trust works fine for many use-cases, it is one of them. It is the penalty a lazy or careless wallet owner or a paranoid one has to pay, her decision, not the community. We have already provided her with a free alternative approach (migrating to the new scheme) and she has refused or missed it and now she should pay costs to secure her funds but the good news is that she has not lost everything.

The way you formulate it is not fair  

The coins are not lost, they are deliberately destroyed by the majority (by a UASF for instance), it is not part of the deal and reminds me of Ethereum and its centralized ecosystem. Bitcoin is not about majorities neither whales nor celebrities, on the contrary, its strength is in the maximum protection of minorities.

there is a dilemma here. firstly, this scheme of yours involves too much trust---in miners to privately mine transactions without stealing and in p2pkh holders to properly secure their coins. they are theoretically a threat to us all.

secondly, bitcoin's economic design implies what satoshi said explicitly---"Lost coins only make everyone else's coins worth slightly more.  Think of it as a donation to everyone."

so it becomes a point of contention. whose interests are more important---
a. people who want to keep their outputs in vulnerable format for eternity (despite safe alternatives) and who will require trusted/centralized solutions to spend them, or
b. the rest of the bitcoin economy?

even if we table the discussion about needless complexity, bitcoin holders will not be interested in your way. they will prefer a predictable outcome that more reliably ensures that bitcoin's value remains intact.

Keeping bitcoin promise as far as it is possible and pushing to the limits, it is the point.
Disabling OP_CHECKSIG means destroying wallets that do not follow our orders, It wasn't part of the code, the contract bitcoin has "signed" with the user. You can't just show up with a new address scheme ordering people to migrate. They have a right not to follow, it is constitutional.

As of 2018 June 4, 19% of p2pkh addresses (4,204,148 of 22,275,753) holding 25% bitcoins (4,319,806 of 17,072,361) were revealing their public keys because of address-reuse.

Such addresses are in the most vulnerable state just like their p2pk counterparts and are indistinguishable from more secure p2pkh addresses with unexposed public keys. They should be blocked too but we want safer p2pkh addresses to be kept valid, burning such addresses by miners through an incentive mechanism is what I've recommended.

It can be a service with a very low fee, centralized and based on trust. The owners of abandoned, expired p2pkh give both their public and private keys to a trusted solo-miner/pool to include it directly in the blocks. lease note that mining is permissionless in bitcoin and there is always a possibility for paranoid minted owners of very fat wallets to lease power and mine their transactions privately.

Forcing people to move their funds and threatening to announce those funds void otherwise? Believe me it is a mess.


Disagree.
Storing state in a single thread of execution of a single script is required and it is nothing more than playing around with one or two booleans and I've explicitly described the rules. This is not dark magic.

What is the point of that? Instead of having two forks, why not just have the one fork have the deadline be farther away so that people have more time to migrate. The point is that during the migration period, ECDLP is still not broken yet.

What is the point of burning the coins? Why would anyone even want to reveal their pubkeys to a miner just to gain nothing? Only the miners benefit from that, it's completely pointless to anyone else. it's the equivalent of just having a fork that completely disallows OP_CHECKSIG.

I disagree. It isn't a mess until QCs actually show up. Migration to PQC is pretty straightforward and non-messy, just needs a lot of time and warning.

The two forks are just so much more complex than a single fork which disallows OP_CHECKSIG and OP_CHECKMULTISIG after a deadline. And I don't think they're any easier than they seem, consensus and the script interpreter and far more complicated than you think, especially with anything that requires storing state or remembering previously executed scripts.

Oh, thank you for being so specific, it is what I always expected from you.  

unlike what it looks like the strategy is not that complicated, it is about two deadlines instead of just one, this is it!

We need two deadlines because we should deal with three radically different cases:

Case #1: P2PK UTXOs (including multisigs); they are exposed to the first wave of commercially available QCs that are able to break ECDSA in feasible time.

Case #2: Compromised P2PKH and P2SH UTXO; they are compromised in the sense that their corresponding raw counterparts are leaked either because of address re-use or other reasons like transaction generation process, wallets being implemented with loose security considerations, ...

Case #3: Abandoned P2PKH and p2SH UTXos; they are wallets that do not follow the recommended practice of migrating to the new PQC scheme and are vulnerable to hijacking by scalable and commercialized QCs capable of breaking secp256k1 keys on the fly.  

In the big picture, each of the above cases is radically different and deserves special treatment. My proposed strategy covers this situation by 2 soft forks or a two-phase fork.

Fork #1: Implement a PQC scheme, set a deadline for P2PK and multisigs to migrate, announce them void thereafter (kick them out of the UTXO set practically)

Fork #2: Up to a deadline, simulate an advanced zero-cost QC attack by letting any miner who has access to the corresponding public key of the address is authorized to spend it into a null address deducting a fixed fee. After the deadline, we are back to the normal situation.


As of implementation considerations:

I understand the second fork is messy but we are dealing with a mess, aren't we? Noways to minimize the damage unless you get hands dirty, no choice. And yet it is not too much, implementing both forks is easier than what they look like in the first glance:

Fork #1: besides the PQC scheme, the script processing engine should fail OP_CHECKSIG after the deadline whenever an OP_HASH160 or OP_HASH256 is not executed freshly and followed by an OP_EQUALVERIFY. Script processing engine can take care of this by maintaining a flag that is set with OP_HASHxxx and reset after the execution of any OP_CODE other than OP_EQUALVERIFY while OP_CHECKSIG checks whether this is flag is set before doing anything, easy.

Fork #2: Before the second deadline OP_CHECKSIG  always pushes 1 (true) if a special flag is set. This flag is set if the transaction follows a defined format which guarantees that after deducting a predefined amount it is burning its (single) input to a specific (void) address. This behavior is reset to default after the deadline.

Interestingly, unlike what happens with your, rough approach, p2pkh legacy wallets that are not been moved for any reason are expendable for eternity as long as they are privately mined (not being relayed in the public network before being confirmed) in the presence of QC equipped thieves.  

There's no reason to take so many steps and add even more special cases to the scripting system. To allow P2PKH but not P2PK requires adding special cases to OP_CHECKSIG which then needs to inspect the script to check whether it was P2PKH. And then you aren't covering things like multisigs or any complex script that uses OP_CHECKSIG. What about if the P2PK was nested inside of P2SH (because that's allowed)? Or people using bare multisig? So now we need to have tons more logic to handle all the weird things people can do with scripts? That's completely unnecessary.

The simpler and easier, and just as safe solution is to soft fork in a hard deadline (that can be several years in the future) where OP_CHECKSIG and OP_CHECKMULTISIG both become immediate script failures thus outlawing ECDSA. People can move their coins to whatever PQC signature scheme is introduced up until that deadline, regardless of script type, and then after the deadline, any usage of OP_CHECKSIG and OP_CHECKMULTISIG is disallowed.

I don't see why it is necessary at all to roll out such a migration so slowly with different script types getting different treatment. And it really doesn't generalize at all.

there is zero evidence of that



and there is also zero evidence of that



and there is also zero evidence of any of that

in particular, all of the above would be crazy (assuming that satoshi is/was not crazy) if the intention was for Bitcoin to ever succeed. The uncertainty could potentially cause alot of chaos in the Bitcoin economy, it makes little sense to store up such a problem just so Bitcoin might one day catch on fire, for what reason? To enjoy watching it burn? (<--- rhetorical question, although I have this funny feeling some joker in the pack is going to try answering it anyway )

He can but he will not. We think that the early mined coins of Satoshi are created as a prize competition (Re: Maybe Satoshi created the greatest prize competition https://bitcointalksearch.org/topic/maybe-satoshi-created-the-greatest-prize-competition-5150688) and that Satoshi is waiting this coins to be moved. We also think that he will not respond when somebody moves the first coins but it will be a message to the Bitcoin community that the private keys are somehow on the blockchain. Satoshi could move the coins (2009/2010) to P2PKH addresses but did not.

assuming satoshi can still move their/his coins, this is a likely reason why it's not happening. Although we shouldn't discount the most conservative thing that all 2009 era mined BTC key holders could do; start by moving their BTC with the highest block number, and do it very very slowly. Satoshi could potentially do so too (we have zero clue what's going on with satoshi in so many ways), so assuming that chaos was not the intention, I expect that if those coins ever did move, that's what would happen; starting at block ~50,000, then working backwards from there.

In such a sequence of events, it could be interpreted as a signal that those early miners are losing confidence in the safety of ECDLP protected coins. Of course, those people may have other reasons to not publicly announce why they're moving to different keys (which are not necessarily anything to do with the safety of the public key cryptography), so you are indeed correct; the lack of information will cause uncertainty, and the uncertainty will rock the Bitcoin ecosystem.

I hope such people (whether satoshi or not, there are others) are reading some of these discussions (it would surely be prudent to do so). If so, I also hope they will consider a slow and orderly move to new key types, and act sooner rather than later.

Yes, it is. It is how we do our job in technology fields: We study trends and speculate developments then decide. We don't take fiction about a monster that suddenly shows up with super-power, as being serious.

It will be long enough: When a technology is in its infancy, i.e. it is not scalable, doubling the speed needs quadratic or higher costs, QC is in such a phase, it is definitively not scalable right now.
If a breakthrough happens in the future and scalable QC technology becomes available, it won't be commercialized for a long time because of governments and military and corporates who need it for their devious plans. It would be very unlikely to be used against the day to day bitcoin transactions. It is also worth mentioning that scalable technology needs time to mature. We are talking about a few years for the least, to be very paranoid.

You need a non-Interactive zero-knowledge proof protocol which is not a piece of cake, it is complicated and both time and space consuming. I don't think it will be ever used in a performance-hungry system like bitcoin. Forget about it.

Why should you show your trolling face once a week to me?  

For my line of research, the main challenge, regarding this issue, is a time&space efficient QC resistant signature algorithm which is an open problem for the whole cryptography community. Although I don't think it would be a wise decision for me to focus on such an algorithm, I wouldn't hesitate to take part and implement it in my proposal, at any point that we might have become close enough to a consensus about a superior algorithm.

@achow101,
Above thread, I've suggested a strategy for different stages of the QC evolution it includes measures and actions to be taken:

1- Implement a new QC resistant signature and install/promote it in bitcoin.

2- starting from the p2pk group of the UTXOs, because they are the most vulnerable segment. It is mandatory for this group to migrate, If they wouldn't, their coins will be announced void after a deadline. More propaganda for convincing p2pkh owners to take actions, no obligations tho.

3- When we are closer to the doomsday, we give anybody with access to the public key behind a hashed address, a right to claim a very tiny and fixed portion of the UTXO just like a txn fee, destroying the remainder. Practically it may be just miners who take advantage of this feature, we don't care.

4- After the QC apocalyptus, we will have a percentage of untouched p2pkh addresses that their public keys are not exposed to the public. For the owners of such UTXOs, there will be still a chance to privately mine their transactions or buying such a service from a trusted pool or mining farm.

The only argument against this strategy, from your side, would be the chaos thing:
While I agree there will be some turbulence but I think it is too much to consider it as chaos. Prices will fluctuate but game theory will work eventually and there will be no catastrophe.

Back to taproot proposal, how do you put it in the context of such a strategy? I'm assuring you right here, right now: this is a must-go strategy.

It's not even just the high proportion, it's also the visibility of some of the coins. In particular, all coins suspected to be Satoshi's are in P2PK outputs. If those moved ever, even to a different sig algo, it would cause enormous chaos. If those are stolen, there would be even more chaos. And those coins are just ~4% of the final money supply. So even if everyone else moved to non-ECDLP keys, the fact that those high profile coins are still secured by ECDLP poses a huge problem.

that's the killer argument

But it makes the case, IMO, for setting a long (several years perhaps) timescale for invalidating P2PK outputs, giving everyone holding BTC at those pubkeys a chance to move funds to hashed pubkeys.

If you believe that the salient factor is how high the proportion of the supply getting stolen by something (not necessarily a QC either) that can solve the discrete logarithm of an exposed public key, then surely if that vast percentage (is it ~20-25%?) of BTC could be encouraged into hashed public keys, then your argument that hashed public keys being safe does not hold, assuming that say 90-95% of public keys are kept safe till being spent? What is the real cost to not hashing taproot keys onchain, just saving space?

I agree, and it is mentioned in the article that what is most likely to happen is that we see QCs evolve and get better and better over time. By watching their evolution and planning ahead, we can move to post quantum cryptography before quantum computers even get to the point that they can break ECDLP in feasible time. It is highly unlikely that a QC would show up overnight that can break ECDLP. However, the point of the article is to discuss hashing in the worst case scenario: QCs magically appear and can break ECDLP in feasible time (not minutes, seconds, or at a glance, feasible time is the worst case scenario).

There won't be a transient phase. Either we have moved onto PQC by the time QCs can break ECDLP in feasible time, or Bitcoin is doomed.

The reason there is no transient phase and why "feasible time" is the worst case, we need to consider the fact that there are already millions of Bitcoin in outputs with their public keys exposed. They don't need to target new outputs with hashed pubkeys, there are millions of exposed pubkeys already in the blockchain that are with outputs that haven't been touched in years, such as Satoshi's outputs. They could just spend a lot of time cracking those keys, and then at some point in the future after the machine was created, they use all those private keys at once to move a bunch of coins. This would devastate the Bitcoin economy and kill it, unless we move to PQC before that happens (but the attacker would know, and could attack earlier). Either way, hashing did nothing.

If the attacker decides to just slowly steal old outputs that have had their pubkeys exposed, then he's slowly destroying Bitcoin and its value because people's money is being stolen. By the time it's realized, the damage would be done and people would probably panic to get out of Bitcoin before their coins are stolen too. It's extremely probably that the fear that a QC exists that can just steal millions of old coins would kill Bitcoin itself (cause the value to plummet, and people to rightfully no longer trust the cryptography). Either way, Bitcoin is killed.

And of course, in both of these, the attacker has time to just stockpile cracked private keys. During that time, QCs will also improve, so the attacker could get newer and better ones that crack even faster. Or he could just build more of them and crack in parallel. And so long as QCs can break ECDLP in reasonable time, it's only a matter of time before it gets to the point that they can break them very very quickly.

The point of the article is to say that while hashed public keys protects your coins specifically, they do nothing against the millions of already exposed public keys from which an attacker with an ECDLP break can use to wreak havoc and destroy the value of Bitcoin. Yes, your coins will be safe, but they won't have any value, so what's the point?

And all of this was just to say that there won't be a transient phase where hashing matters at all. The attacker will just target the already exposed pubkeys in outputs that haven' been touched in years.

Either we move to PQC before QCs can break ECDLP, and hashing didn't do anything. Or a QC comes along and can break ECDLP, and hashing did nothing because there are millions of available pubkeys with outputs that they can target, and hashing did nothing.

---

It would be a completely different story if Bitcoin had hashed pubkeys in everything since the beginning (but it did not, pay to pubkey was the expected method of usage) and no one ever reused addresses (so pubkeys were only exposed once and had no value afterwards). If those things were true, then I would say that there is a transient period and hashing does help protect against QCs. But that didn't happen.

That's not a reasonable expectation, when you consider the range of adversaries



That depends massively on how long this transient phase lasts.

The safest thing to do is as suggested in the stackexchange article: soft fork to prevent ECDSA transfers, but invoke zero knowledge proofs of BIP32 seeds to indirectly spend them to QC resistant keys.

maybe if you find this so compelling, you could start working on the zero-knowledge proofs to spend ECDSA outputs to QC resistant keys? Like, today for instance? (you'll be busy a while hopefully ) Won't your super coin (or is it a Bitcoin fork, I forget) need it, or will you stick with hashed public keys? We don't want to hold you back, off you go...

How is 30% of the existing supply irrelevant?

He didn't suggest miners had mysterious privileges, just that they could censor transactions that don't meet their criteria -- same as today.


These sorts of arrogant assumptions are dangerous. You have no idea what kind of breakthroughs could be made in the future.

I afraid, what you have said there is not persuasive. It seems to me that you have chosen not to use hashed keys in taproot and you are just justifying it.

Besides the irrelevance of some points that you have made about the existing exposed public keys and your highly suspicious assumption about miners having mysterious privileges in the presence of QCs, the most confusing part is still your misrepresentation of the main problem.

At the time of this writing, QC is a very expensive technology and it is not scalable, i.e. costs grow exponentially by the scale of the system (number of qubits, number of gates and their resistance level to decoherence, ... ). We are not expecting large QCs showing up out of nowhere, breaking sec256k1 keys in few seconds. Rather there will be generations and development phases and it is highly expected that we will have machines that are able to break bitcoin public keys in feasible time but not in a glance or in few minutes.

Hashed public keys are safe in such a transient phase and what I absolutely don't understand is why we should include a proposal about public keys being exposed for an eternity waiting for their turn to be destroyed by any innovation or technology that shows up?

His coins or the 'Shalecoins' (coins with no owner ' https://bitcointalksearch.org/topic/bitcoin-as-shalecoin-5134441) moving would actually be an indication that

1. Quantum computers exist

2. ECDLP has been broken in some way

or

3. Satoshi created the greatest prize competition and the privatekeys are somehow within the blockchain. https://bitcointalksearch.org/topic/maybe-satoshi-created-the-greatest-prize-competition-5150688 and someone solved it

ok, it's a cryptographic key, and it's publicly exposed. But it's not the keypair counterpart to the private spending key, right? Or is "keypair" not meaningful in taproot?



Well when it's explained like that, it seems that I am at least understanding something: there are 2 keys related to the spending (private) key in taproot; the internal key and the "actual" pubkey (by "actual" I mean publicly exposed on the chain). I don't think about this kind of math often enough to really comprehend the relationships between them, despite you having just written it out I know the words, but I can't hear the music



ah, now that's I was hoping for, something definitive

No, that's wrong.

The public key you see in a taproot output is still a public key. It has a discrete logarithm (aka a private key) and anyone who is able to find it will be able to spend the coins regardless of any internal pubkey or script. The private key for a taproot pubkey (assuming a script) is the private key of the internal key + the hash of the script. The public key itself is computed by the sum of the internal pubkey and the "pubkey" of the hash of the script (i.e. multiply the hash by the curve generator).

For QC resistance and why hashing doesn't matter, see: https://bitcoin.stackexchange.com/questions/91049/why-does-hashing-public-keys-not-actually-provide-any-quantum-resistance

So, it seems my recollection was right, but I got the implications wrong:




...however, the whole point of Taproot is to make P2PKH and P2SH indistinguishable on the blockchain (at least in most typical cases?) And so the actual public key for the private key that can spend an output is either another hashed script, or is provided to taproot's compute pubkey function such that no script path can be used. This still permits using the underlying "real" pubkey (which I think is defined as internal_pubkey in the Taproot BIP docs) to execute a spend of the output.

So, the spending pubkey is actually redefined as a key internal to the taproot script, and the pubkey for the overall taproot script tree is the "real" pubkey, as it is now the key that's actually publicly available! The whole notion of what public key means is therefore not the same in taproot outputs...phew!


Anyone have any idea if this has any implications for QC resistance? My instinct is to say that the internal key is never revealed, because the taproot magic keeps it forever hidden. I expect to be wrong

Given that Satoshi's coins are in Pay to public key outputs, the pubkeys are publicly available already. So if we assume Satoshi is dead or otherwise gone, his coins moving would actually be an indication that Quantum computers exist because the only way for them to move (assuming he is no longer around) is for someone to have been able to compute the private keys to those exposed public keys, presumably via quantum computer. In general, it would mean that the ECDLP is has been broken in some way (regardless of QCs) and should no longer be relied upon (i.e. we should move off of ECDSA and Schnorr).

This is just inaccurate fud. We have no reason to believe that Satoshi is still active in the community its been years since he has been involved and Bitcoin has developed without him for a long time. Yes he is someone to be respected but for all we know Satoshi could well be dead or imprisoned. We will know when to make the changes that are needed for quantum computing by monitoring the development of quantum computers and not because someone decides to move their coins.

"We will know when quantum computers exist when Satoshi’s coins move." https://marketrebellion.com/why-quantum-computing-is-not-a-threat-to-bitcoin/



Satoshi:

Nobody is asking why he did not move and is not moving these early mined unmoved P2PK coins:
https://bitslog.com/2013/04/17/the-well-deserved-fortune-of-satoshi-nakamoto/
https://bitcointalksearch.org/topic/satoshis-fortune-lower-bound-is-100m-usddebate-going-on-do-not-tweet-175996

something has occurred to me since this all started

is it not the case that Taproot/tapscripts output would expose it's public key in it's pubkey script on the chain before it is spent? I'm gonna have to check that out today, I'm not certain

If so, I don't think this is some kind of oversight on the part of Taproot's design; as was pointed out upthread, if a QC-based attacker scans the mempool for inflight transactions, the hashed public key offers them zero protection during the time between broadcasting a tx and it getting confirmed. That amount of time could easily be long enough to use the QC to resolve the private key from the (briefly exposed) public key.

This post is subject to change if I'm wrong! Re-reading the Taproot/Tapscript BIPs right now...

https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki

https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki

I like your enthusiasm, and I hope Bitcoin will hit tens of trillions in value.

"Valuable enough?"
- No. Not more valuable than a human life, at least for me.

As for the Quantum Computers, if this will happen of course Bitcoin will be worthless like everything out there using encryption, but I'm sure Bitcoin developers will launch a new Quantum Resistant Bitcoin maybe called qBitCoin.

Don't be afraid, we will adapt like we always do, as humans.

Fair point. If one had access to this technology, the rational approach would be to slowly siphon off bitcoins in a way that would be extremely difficult to detect, maintaining the market value. 

I'm mainly thinking about the arson scenario. If adversaries were able to destroy faith in Bitcoin this way, I'm not sure how much confidence would be left in any cryptocurrencies.

sure, but...



...the greater percentage of the total BTC supply someone can steal using any exploit:

• The more BTC's market value will crash, meaning the attack's purpose changes from profit to an arson-like motive
• The more likely that a majority of previous holders reject BTC in favor of a resistant new coin, even if a fix for the exploit is discovered

The last point (ironically) resembles what's actually happening with central bank money today; people rejecting it for alternative assets because knowledgeable abusers of the system are being allowed to over-aggressively suck all the value (as well as any remaining credibility ) out of it, while the economists and policy advisers desperately try to appear to be correcting the situation



this is very true, and so credit to the developers who have the sense to move slowly and carefully with changes/additions (even competitors to Bitcoin have behaved very responsibly, e.g. the reporting for the inflation bug, or the handling of the recent channel spoofing bug in Lightning). But we're in a virtuous circle here; very talented software developers and computer scientists were attracted to Bitcoin when it was still experimental, and now many of those same people are as motivated to contribute to furthering it's viability as they are invested. Brilliant.

How about in a decade or two, when Bitcoin's market capitalization might be in the trillions, or tens of trillions? Valuable enough?

We're also talking about much more than 1 million bitcoins. It's 5 million+ that have exposed public keys and theoretically the entire supply if QC is capable of breaking transactions in flight.

Centralized infrastructure also requires far less coordination to secure. In a zero-day situation, governments and banks could react far more effectively than the decentralized Bitcoin network ever could. If QC broke ECDSA in the wild today, I don't think Bitcoin would ever recover.

They would build a quantum computer intentionally for Bitcoins case to frack the 'Shalecoins'. ('Shalecoins', coins with no owner ' https://bitcointalksearch.org/topic/bitcoin-as-shalecoin-5134441)

I personally don't bother too much just because if someone Google, 3 letter agency or even aliens will come up with a quantum computer satoshi's funds will be the last thing that we'll need to worry about.
Just think about all the "password protected" (encrypted) things that are out there, like: financial system servers , electricity servers, medical care servers, airplanes servers, nuclear missile codes. These are things much more valuable and important than 1M bitcoins.

This trade-off is a middle ground between two options. Let quantum computing flood the market in a short period of time (freedom approach) or destroy these coins because it's an easy way to preserve and even increase a bit our wealth.

That is not breaking the rules of Bitcoin or how I would prefer to look at it Bitcoins philosophy. Bitcoin was proposed to have a limited amount of Bitcoin to prevent inflation and other issues in the long term however that only includes disallowing new coins from being generated after 21 million and at no point was it proposed that destroying coins would not be allowed. Of course it is allowed and in theory the more Bitcoin that are lost the more valuable and limited it will be. Bitcoin does not have many hard set rules in terms of what you are suppose to do with your money. If you want to destroy coins you can the only limit is you can't generate anymore after 21 million coins has been reached.

If you want to severely limit Bitcoin's potential then you could do this but I would and many others would advise putting any sort of limitations on the Bitcoin technology. Limiting it shows that there is a centralised force trying to control Bitcoin despite it being for a good cause. If you want to transact more than a couple million dollars in Bitcoin in an hour then you should be allowed to do that. Freedom is the best approach here.

That sounds like a real kludge. The idea probably wouldn't gain traction. Theoretically it's also not just unhashed public keys that are vulnerable, but all public keys as they currently exist.

The solution seems rather binary to me. We either lock/destroy vulnerable outputs or we let them wreak havoc on the market. Whether the first option is ethical seems like an issue of time -- how long is long enough?

We have some duty of care not to deprive people of their money, but does that entail going down with the ship?

A possible trade-off would be to limit transaction amounts from unhashed public keys to few million USD per day.

it doesn't. the rule is there can't be more than 21 million coins.

due to the nature of private keys, there was always an implicit assumption that lost coins deplete the supply. i've been operating under that assumption since i arrived 7 years ago. in fact, satoshi explicitly said as much in 2010.

you're telling me that entire monetary philosophy just goes in the trash bin now? lost coins aren't a donation to holders, but rather those with quantum computers?


if QC can break ECDSA, then ECDSA secured outputs should not exist, period. "people should be free to have their coins stolen!!!11!!1!" is not a compelling answer. it's completely against the interest of all bitcoin holders.

destroying coins?? (facepalm)

not only does that break the rules of the whole 21m coin 'there will be 21m coins in the future .. oh wait we meant 15mill, now 14m'

not only does that break the 'trust math' theology. because now devs decide they want to go against the rules, so people cant trust that they will always have coins if they just locked their only copy of a private key in a time capsule. they have to trust and hope devs dont go barbaric on code rules

not only does destroying coins destroy many aspects of bitcoin.but the social drama impact of such an act would effect the markets more so than just letting a theif sell coins

think about it once brute forced coins are sold or moved out of insecure keys. drama is over.
its far better to let someone waste their life brute forcing a private key for 50btc and sell them, then repeat 20,000 times until 'satoshi stash' is no longer on insecure addresses... than it is to let devs manipulate the rules to declare more than 1m coined defunct and destroyed in on go. whats next if p2pk keys need destroying, do devs wait a month and declare war on p2pkh p2sh. then when they find an issue with segwit declare a war on p2wpkh. would it ever end

people would prefer to know if they leave their coins its their fault for not loking after them, if they care and there is a output format that is genuinely more secure they can move them. if they dont then they are at risk of someone else spending them.. but never ever should devs ever consider destroying coins..

in business terms. imagine thre is a company in the middle of a merger/liquidation buyout/hostile takeover. is it more beneficial to just let it happen as you know its only a 15minute news item that passes as fast as a price dip would.. or would you call in the military and nuke the facility and shout 'ha ha ha no one gets it' and then go on a mission where nuking businesses is standard practice

the price drama of a user selling 50btc a day is small if they brute forcd a satoshi stash address each day. and it would take 20,000 of thos days to do it to 1m coins.
just think about how little effect on the price 50btc is in comparison to average daily volume.
just think about how little drama it would realistically create compared to breaking some of bitcoins fundemental rules.

more people would be more concerned that devs are coming to dstroy their coins next compared to the worry of someone spending 50btc of satoshi stash a day

I'm not proposing anything, just reminding a possibility.

A few decades later, probably, when QC is no longer sci-fi and bitcoin has successfully implemented QC resistance and most wallets have migrated to the new scheme, there will be a hopefully small fraction of p2pkh UTXOs still untouched. In such a situation, commercially cheap QCs lurking around in shadows, if an owner of such a wallet tries to access his funds by publishing a transaction, the funds are being put in risk in the unconfirmed minutes of the transaction lifecycle. Hence they are practically lost already.

What I'm suggesting is that in such a marginal situation, the poor owner of the wallet who secretly has access to both public and private keys matching the wallet's unused RIPEMD-160 address, still has this option, privately mining her txn, either directly or by buying third party services. Sure it is not ideal but it works and is much more preferred than risking public disclosure of his unconfirmed txn and putting not only his funds but also the ecosystem in danger. Bitcoin will suffer from any kind of robbery as well as lost funds; we all know.

I'm not pushing. Just trying to show that we are ahead of QC threat and there is a lot of possibilities to keep the risks involved very low in the next couple of decades 

What you are proposing is the most popular option I would say at this moment and I think its the only logistical one that I have heard of but I don't understand why you are pushing for it to be done so soon. The second deadline does not need to be months after and could instead be a couple of years to allow those that are less security conscious. The elitist attitude of "that is their problem for not listening" is invalid if we wish for mass adoption of Bitcoin. The decisions made for Bitcoin should appeal to the majority of members and not blame it on them if they are not up to date as we are. Quantum computers capable of threatening Bitcoins algorithm will be around the year 2025 at the earliest. This means we have several years to implement the first stage and then several years to allow for people to change on the second deadline. Moving this along to quickly is not an effective way of making a big change like this.

If this is true like we are both predicting then the second stage can be rolled out over a couple of years and not a few months.

No! 25% is not invented:

https://medium.com/@sashagnip/how-many-bitcoins-are-vulnerable-to-a-hypothetical-quantum-attack-3e59e4172e8

QC resistance cryptography is new just like QC itself and it is already ahead of the enemy by any measures, I think long before QC is ready to attack we will be ready to fork.

I totally agree with your concerns about how bad the QC issue is treated by the community, it is not the only issue that is open in bitcoin to be fair.
But for now, let's forget about governance problems for the time being and be optimistic about some sort of consensus being reached to handle QC problem, the question would be whether we could do anything serious about it?

My answer is definitively YES:
1- Implement a QC resistant digital signature algorithm in bitcoin with a soft fork.

2- Draw two deadlines in the fork for wallets to migrate:

• ِFirst deadline(n blocks after the fork):
  
  • No legacy format outputs will be included in the blockchain after the n_th block.
    
  • All P2PK outputs should migrate to new addresses within n blocks, otherwise, they are considered void and no miner would confirm transactions with such inputs after n blocks.
• Second deadline(m>n blocks after the fork):
  
  • p2pkh wallets should migrate, otherwise, after m blocks, anybody who has access to public keys corresponding to such a UtXO has a right to nulify it with a fixed satoshi/Byte fee rate by means of generating and relaying a transaction.

3- Let people with abandoned p2pkh UTXOs with an uncompromised public key that are still active after the second deadline to mine their transactions privately by leasing/installing hash power or by buying private service from known responsible miners/pools.

As of your perception of miners as being anonymous, actually most of the largest mining farms/pools are anything other than anonymous and your point about ordinary people not being able to leas such a hash power can be fixed with providing something like a private transaction confirmation service by pools/miners.

I'm sick to death with these "quantum computers is the end of Bitcoin" type posts. The community is so misinformed about how quantum computers works its very worrying because if quantum computers does not destroy Bitcoin which it wont I think this false propaganda from so called experts will destroy the public opinion about Bitcoin.

If it comes a time where Bitcoin is under threat from quantum computers we will have multiple forks in the chain no doubt because the difference of opinion from the members of the Bitcoin community as well as the miners will cause uncertainty. This will  be problematic in the short term and depending on public perception after the media reporting on it could have a medium effect on Bitcoin acceptance.  
No one on this forum has a clear vision of how we are going to deal with it because there are multiple different routes to take all with their own little side effects on the community and Bitcoin but one thing is for sure we have multiple years to figure this out. This talk about quantum computers destroying Bitcoin and asking what are the steps to countering quantum computers is discussed at least weekly on this forum so there definitely is enough discussion about it.
Force people who use Bitcoin wallet software which is connected to the internet to update to the chain with quantum resistant signatures. However this is not a perfect solution to those that are holding their coins in cold storage and might not follow Bitcoin news regular enough.

Why would we want to emulate gold and become gold 2.0? Quantum computers is a once in life time event and will probably not be an issue for many people because they can simply switch with the chain once all the hard work has been done by the developers. I'm calling it now there will be a massive divide between the developers and each developer will be pushing their own motive induced way of dealing with this and that is the biggest threat of them all and not these quantum computers.

Very good point and thats the only argument I see about quantum computers not being a problem right now and does persuade we a little bit to consider starting the development towards a quantum resistant Bitcoin earlier than I had in my head.  I still think the perfect solution does not exist and whatever way we go there will be instability in Bitcoin and people will lose their coins but I'm talking way in the future.

Those numbers are completely invented. If my time in this space has taught me anything, it's that most people are overwhelmingly careless about their security and don't keep up with Bitcoin development. One of the reasons a fork like this should be done over several years is because it'll take that long just for people to gradually update their nodes. If a QC broke Bitcoin tomorrow, no emergency fork could repair the harm done by today's key practices.

This problem is compounded by the fact that quantum resistant signatures Like Lamport are extremely heavy, so we have incentive to delay a fork as long as possible:

I'm not sure what alternatives there are.

Relax, people. No need to build the mining farm yet.

https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410

I get your point but mining is supposed to be a neutral thing where you don't have to worry about "picking the correct miner", it should be as simple as sending the transaction, but with a QC machine out there lurking in the shadows you can no longer do this. The problem is miners are anonymous, I can't see a way to rank "good miners" from bad miners. Nobody really has connections with CEOs of big mining farms to really know their agenda. Mining your own transactions is obviously not an option for 99% of users. There's also the theoretical scenario in which miners sense too much of a menace and decide to become bad actors while shorting Bitcoin's price. If we act and plan ahead those cannot happen because the incentives model would still be in place but in a moment of confusion and chaos and the fears of millions of BTC being or not compromised we may see miners freaking out, hence the whole thing must be ready before it happens. The question is right now this is probably sci-fi tier so just like climate change, you'll have a case for both "no need to do anything drastic now" and "start acting now". Result = no consensus, and no planning ahead.

ASICs didn't break sha2 they broke bitcoin PoW, there is a difference that its understanding is beyond your expertise in the field.

Are you a stalker of me?  

No exaggerations there. Any single cryptographer on the planet have been always aware of the vulnerability of ECDSA to technology advancements not mentioning implementation backdoors and the fact that it was originally an NSA product. Actually, instead of bitcoin getting credit from ECDSA, it was bitcoin that promoted it as a reliable digital signature algorithm by providing a huge incentive and tempting adversaries for breaking its secp256k1 implementation of ECDSA.

As you you've correctly mentioned in your post, ECDSA-secp256 has always been understood as a few decades reliable signature scheme and it is why I think that destroying Satoshi's P2PK coins in case s/he wouldn't migrate them to safe wallets in due time, shouldn't be considered unfair. As a cryptographer, he should have been aware of the existence of an "expire-date" for his public keys.

This is an exaggeration because for encryption to work you have to be confident that it will do the job for a number of years and that was true when ECDSA was developed and when it was implemented into Bitcoin. It is currently 'bullet proof' even if quantum computing is making some significant gains in the last couple of years it is still currently bullet proof and saying that cryptographers were never really confident in the protocol used inside Bitcoin is a bit of a overstretch.

you are speaking as the person who infamously claimed that SHA-2 ASICS broke SHA-2:



have you forgot which account you're logged into??

Edit: the above quote demonstrates @aliashraf is a (lazy) liar

Above, Pooya has excelently described why sha is different essentially being a hash function and not a number theory problem in NP not solvable by deterministic sequential machines e.g. Turing machines and vulnerable to quantum computers and Shor algorithm, just a category that  ECDSA belongs to. It is just wrong to compare sha256 with ECDSA.

Please stop posting about topics you have no clue about. If it was ever possible to break sha, bitcoin wouldn't worth thousands of dollars because it would look just stupid to rely on an asset that is subject to a mathematical or technological  development which could occur every moment. To make it crystal clear: Bitcoin will be totally destroyed by such a hypothetical (surely impossible) development.  

On the other side, cryptographers never have been confident about ECDSA to be bullet proof and quantum computing was a surprise just for ordinary users.

^^^ trolling ^^^

you don't really expect me to reply to your out-of-context weak BS, right?


there's a good reason to do it, but I _did not_ even commit myself to it, I presented both sides, calmly

you started an argument, deliberately, where there was no argument.

Really? and who would give you the permissions to do such a thing?

Lets just think for a second what is satoshi is not dead? and actually the coins ARE spendable.

There is so much assumption around the coins but one key thing to remember is if you don't hold it you don't own it.

No one has the right to touch the satoshi coins other than the owner this is not the first topic that has made comments to the effect of lets just burn or revoke the from the chain.

If satoshi coins ever are community moved / revoked some how then bitcoin will fail. no if's no but's it will be a community based attack in my view.

I'm very surprised to see this comment from you Carlton Banks.

yep, although there's at least 1 solution I can think of:

assuming you trust a miner (and it could be yourself if you have the hashing power, of course), you can give your transaction to a miner out of band, then the public key is never exposed until the tx moving your funds to a QC resistant keypair is already confirmed in a block. That would (hopefully!!!) be a one-off event, but hair-raising (and potentially expensive) all the same



I think the only solution is to render the whole P2PK supply unspendable, and to do that with a the longest possible period of advanced warning to give the holders of those private keys sufficient time to move their money. See, we're having a civil conversation about this, yet we already disagree!!! tough call indeed.



okay, I am aware of the logic underlying all of this, although you are more familiar with the details.

consider though: mathematicians/computer scientists/cryptographers working for powerful companies/organizations are not compelled to release every breakthrough they discover publicly. What if an efficient solution to what appears to be a brute forcing problem has in fact been discovered? Is that not the point of QC's anyway, to provide efficient solutions for which binary arithmetic Von Neumann machines cannot? Maybe some class of hashing algorithm could be developed to be resistant to such a thing, I simply do not know, but it seems to me that few others can really claim to _know_ either.

People always say "that's impossible", until someone pitches up one day and provides the solution. The fact that we are on this forum having this discussion is the result of exactly that happening: cypherpunks tried to create a Bitcoin, and their imagination for designing it failed several times until satoshi. People literally _couldn't_ believe satoshi initially, Hal Finney hung out with satoshi for a while, contemplating the details of his design, in a way to convince himself that there was not something satoshi was missing. Only once people like Wuille, Maxwell and Todd (as well as Szabo, Dai, and Back on the sidelines) arrived on the scene to contribute to validating the concept did people really begin to get over the disbelief.

*** the following is, to the best of publicly available knowledge, NOT POSSIBLE ***
There would be no such luxury under a "SHA reversed by quantum computers" scenario, one minute a single Bitcoin blockchain would exist, the next there would be infinite Bitcoin blockchains, and every Bitcoin client would have their poor little CPUs overloaded trying to figure out which one was the most-worked valid chain
*** the above is to the best of publicly available knowledge, NOT POSSIBLE ***

Most of them, wallets with exposed public keys, will migrate to the new scheme before the catastrophe and after the QC resistant fork. At the End of the day, we are left with a (tiny, IMHO) fraction of bitcoin wallets being abandoned by their owners for some reason, which I suppose less than 10% of them would have exposed keys and P2PKH addresses. My estimation is based on their current 25% ratio and the fact that such wallets are used to be more active compared to untouched wallets that are more suspicious to be abandoned.

I could even propose to pre-empt exposed public keys after a deadtime once the QC resistant fork is activated. It may look reasonable to mitigate the chaotic side-effects of such a robbery and a strengthening measure for bitcoin.

There are quite a lot, actually:


I can't begin to verify the numbers but it sounds like 30-50% of the existing supply could still be vulnerable even if unused P2PKH addresses are safe. With that much loot on the table -- an amount that surpasses the entire global bid side many times over -- anyone with access to this powerful of QC would have incentive to crack and sell outputs as quickly as possible.

OP,

I think there is and there will be no solution regarding funds in addresses with already exposed public keys in case of a QC cryptographic disaster. Such addresses are not too many thanks god.

Implementing an efficient QC resistant signing algorithm is not much of a hurdle but the problem of 'old' wallets and their owners failing to 'migrate' to brand new QC resistant addresses is a serious one.

I think I have a solution for this later problem which covers the case with Satoshi coins:

The problem
Given the following conditions, find a way to protect people from losing their money:
1-An established QC resistant algorithm being implemented in bitcoin and ready to accept funds from legacy addresses.

2-A number of 'old' wallets with a considerable amount of bitcoins still not migrated to the new scheme.

3-QC technology being matured enough to put wallets with exposed public keys in serious risk even in their transient state of exposure in an unconfirmed txn.


For such a hypothetical situation which by no means is expected to be met in the next couple of decades, I have an idea: Mine Your Own Transaction.

Owners of big enough wallets better rent a hash power and start solo mining bitcoin waiting for a hit in real-time and owners of wallets with fewer coins can simply find a farm with enough hash power and pay them for privately mining his transaction.

hashes could never be "reversed" and it is not exactly about efficiency it is about virtually unlimited solutions. think of it like this, if i say i have a big number that is the sum of 10 other numbers you will never be able to guess what those 10 values were because there simply is too many possibilities.

the difference between hashing and ECC is that ECC is pure math so there could some day be a solution to solve that reverse mathematical problem (ECDLP) in a faster way but hashing is a complete chaotic algorithm where we take an input "mutate" it, toss the bits around and come up with a neat result. so the only way to attack hashing algorithms has always been to find collision meaning if i said "a85845e696ee7aac1b012d611edcbd6fbf1884c5" is my SHA1 hash you will never be able to find out what message i hashed but you could find another message some day (you still can't do it today even for SHA1) that could give the same result.

I think you are talking about Peter Wiulle:



Yeah it was theymos and he got hated bigly with his approach. The way I see is that the stash should be re-introduced slowly as mining rewards, or at least that's how I should have coded it since day 1, since if you are the only guy mining in the world, there isn't even a network and you would get a disproportionate amount of coins as the single participant on the system. At the same time I also think he took the bigger risk, so it should be rewarded... tough call.

really?



supposedly there is no possible way of using quantum computing algorithms to find an efficient solution for reversing hash algorithm outputs. I think that because hashing involves destroying such a large quantity of the original data input, that's a reasonable assumption. I know almost nothing about cryptography though.

That's the reason why Bitcoin "addresses" are not the ECDSA public key, but a RIPEMD160 hash of the public key. Until the BTC is spent, the public key is protected from actual publicity, but spending involves revealing the public key in order to validate the transaction.

So, in the event of QC blockchain-ogeddon, funds stored at addresses that have never been spent from will not (theoretically) be vulnerable. However, at least 1 developer has suggested this assumption is not as safe as was assumed when this was devised, I do not remember the details however



I think @theymos actually did bring this up some time ago (and people mostly didn't see what the point was, and accused him of being jealous of satoshi or something or other)

The fact is, early BTC from ~ 2009 did not have a hash to protect the public key, those mined coins have their public key directly exposed on the blockchain right now. A known quantum computing algorithm can be used to efficiently spend those coins, which includes satoshi's stash (it's a guess who it all belongs to, certainly satoshi must own some though). The only thing stopping this is that the hardware doesn't exist. Yet.

which is why making satoshi's coins unspendable has merit, to anyone developing QC's, 1,000,000 BTC is effectively the bounty for keeping the details of progress in their work very quiet. If anyone is in the race to develop cutting edge QCs, the sort of people who ought not to have that much power are definitely in contention. Of course, there will always be loud screeches that "satoshi should be allowed to keep his/their BTC", but in this scenario, satohsi loses it either way if action is not taken well in advance. because the coins haven't moved, one could argue satoshi is either dead or confident it won't happen.

1. implement quantum resistant signatures
2. give people 5-10 years to move their coins
3. destroy all non quantum resistant outputs

move 'em or lose 'em! once the fork occurs, all previously lost coins would be permanently destroyed. this provides the added bonus of being a one-time audit of the active supply.

do i see this actually happening? not really, i just think that's the best case scenario. there seems to be a lot of inertia around this issue. a lot people seem to think "no biggie" about a huge chunk of the supply being vulnerable, which boggles my mind.

Let's say Google or your favorite triple letter agency (same thing?) come up with a computer of quantum nature which is able to move funds of our guy satoshi. Everyone starts tripping, headlines everywhere, mass hysteria. How would the game theory involved in the necessary changes to protect from this unfold?

Forget about what to do specifically, just think, of all possible candidates, how would the one that gets selected as the fit candidate become the winning fork? We would have people arguing this or that method is the way to go until we are pushed to the limit? It would be segwit on steroids.

I really wonder about this pretty much daily and I don't have the answers. Not only we would have a problem changing hashing algos, eliptic curves and whathaveyou, but we would need to do something about funds which are no longer safe. What do you do with satoshis stack? How does this resolve? There would be people claiming "do nothing with satoshis coins, they are his coins after all" while others will argue the coins are basically a big vulnerability for the ecosystem at that point. Do you have any clear vision of how things would turn out? These things need to be planned ahead and I don't see enough discussion tbh.