Pages:
Author

Topic: Game theory involving Quantum Resistance protocol - page 2. (Read 877 times)

staff
Activity: 3458
Merit: 6793
Just writing some code
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?

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?
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.
legendary
Activity: 3430
Merit: 3080
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?

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?
staff
Activity: 3458
Merit: 6793
Just writing some code
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.
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).

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?
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.
legendary
Activity: 3430
Merit: 3080
We are not expecting large QCs showing up out of nowhere, breaking sec256k1 keys in few seconds.

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


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?

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 Smiley ) 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...
legendary
Activity: 1666
Merit: 1196
STOP SNITCHIN'
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.

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.

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.

These sorts of arrogant assumptions are dangerous. You have no idea what kind of breakthroughs could be made in the future.
legendary
Activity: 1456
Merit: 1175
Always remember the cause!
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?
newbie
Activity: 21
Merit: 1
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).

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

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

Our guess is that he knew that the early mined coins will be moved one day. So he created a 'prize competition'. Otherwise he could move the coins to quantum resistant P2PKH addresses, but he did not and is not doing.

The only question is:
Who will win the race and get the early coins?

Quantum computing or solving the "Satoshi Prize Competition".

Nobody can stop that race.
legendary
Activity: 3430
Merit: 3080
The public key you see in a taproot output is still a public key.

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?


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).

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 Smiley I know the words, but I can't hear the music



ah, now that's I was hoping for, something definitive
staff
Activity: 3458
Merit: 6793
Just writing some code
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 Cheesy
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
legendary
Activity: 3430
Merit: 3080
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

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


The public key is directly included in the output in contrast to typical earlier constructions which store a hash of the public key or script in the output.


...however, the whole point of Taproot is to make P2PKH and P2SH indistinguishable on the blockchain Smiley (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 Cheesy

staff
Activity: 3458
Merit: 6793
Just writing some code
"We will know when quantum computers exist when Satoshi’s coins move." https://marketrebellion.com/why-quantum-computing-is-not-a-threat-to-bitcoin/
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.
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).
legendary
Activity: 1232
Merit: 1080
"We will know when quantum computers exist when Satoshi’s coins move." https://marketrebellion.com/why-quantum-computing-is-not-a-threat-to-bitcoin/
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.
newbie
Activity: 21
Merit: 1
"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 knew that one day quantum computers will exist and will be able to move the early mined coins (P2PK) and created an unofficial prize competition to accelerate the development.

Maybe 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

Satoshi:
However, if something happened and the signatures were compromised (perhaps integer factorization is solved, quantum computers?), then even agreeing upon the last valid block would be worthless.
True, if it happened suddenly.  If it happens gradually, we can still transition to something stronger.  When you run the upgraded software for the first time, it would re-sign all your money with the new stronger signature algorithm.  (by creating a transaction sending the money to yourself with the stronger sig)

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

Our guess is that he knew that the early mined coins will be moved one day. So he created a 'prize competition'. Otherwise he could move the coins to quantum resistant P2PKH addresses, but he did not and is not doing.

The only question is:
Who will win the race and get the early coins?

Quantum computing or solving the "Satoshi Prize Competition".

Nobody can stop that race.
legendary
Activity: 3430
Merit: 3080
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)

Only applies for Bitcoin address where it's public key is known

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
full member
Activity: 350
Merit: 144
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.

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.

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.
legendary
Activity: 1666
Merit: 1196
STOP SNITCHIN'
...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

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.
legendary
Activity: 3430
Merit: 3080
How about in a decade or two, when Bitcoin's market capitalization might be in the trillions, or tens of trillions? Valuable enough?

sure, but...


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.

...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 Grin ) out of it, while the economists and policy advisers desperately try to appear to be correcting the situation Cheesy


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.

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. Smiley
legendary
Activity: 1666
Merit: 1196
STOP SNITCHIN'
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.

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.
jr. member
Activity: 48
Merit: 1
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.



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)
Banks can freeze accounts, rewind, correct it.
But Bitcoin can't.
full member
Activity: 350
Merit: 144
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.

Pages:
Jump to: