Topic: The Three Encryption Methods Used by Bitcoin (Read 3777 times)
FYI the prior related discussion where gmaxell censored me:
https://bitcointalksearch.org/topic/m.3337585
Other:
https://bitcointalksearch.org/topic/m.3328064
https://bitcointalksearch.org/topic/m.3337585
Other:
https://bitcointalksearch.org/topic/m.3328064
How dare you speak such ghastly truths C-F-B.
Speculation: Don't ya know "we" (Bitcoin core developers) are supposed to be pretending to be working on pruning the UXTO but never release that. And we must keep these weaknesses in Bitcoin, because you can clearly see "we" attend our CIA and CFR appointments. An "No" "we" are not under an NSA gag order ourselves which prevents us from telling you this.
Message From Anonymous.
Speculation: Don't ya know "we" (Bitcoin core developers) are supposed to be pretending to be working on pruning the UXTO but never release that. And we must keep these weaknesses in Bitcoin, because you can clearly see "we" attend our CIA and CFR appointments. An "No" "we" are not under an NSA gag order ourselves which prevents us from telling you this.
Message From Anonymous.
@Newbies:
kjj is very biased, just like most of early adopters and Bitcoin hoarders are. The fact that he put AnonyMint into the ignore list proves that kjj is not an open-minded person. Even more,
kjj is very biased, just like most of early adopters and Bitcoin hoarders are. The fact that he put AnonyMint into the ignore list proves that kjj is not an open-minded person. Even more,
Quote
Note that 264 is still a huge number, and it is not at all a given that a real world system can accomplish it in 10 minutes.
is a plain lie. QCs can crack Bitcoin keys as fast as legit owners can sign transactions.
Hahaha, he made a fool of himself because he thought ECDSA was subject only the Grover's algorithm (thus his claim of only a reduction from 128 to 64 bit security). Now he pretends he didn't read my rebuttal, so he doesn't have to face his egregious technical mistake.
(apparently he conflated the security of the hash of ECDSA which is only subject to Grover's, with the ECDSA public key inside the hash which is revealed on spending, and which is subject to Shor's not Grover's)
Btw, my private message to him was "your turn dufus" with a link to my rebuttal above.
Any more pesky nincompoops want to take their turn at being skewed on the logic tree?
(apparently he conflated the security of the hash of ECDSA which is only subject to Grover's, with the ECDSA public key inside the hash which is revealed on spending, and which is subject to Shor's not Grover's)
Btw, my private message to him was "your turn dufus" with a link to my rebuttal above.
Any more pesky nincompoops want to take their turn at being skewed on the logic tree?
This user is currently ignored.
Sending me PMs won't get me to read your posts. I already wasted just about as much time on you as I'm willing to spend.
No one has provided any argument against my upthread point about Zerocoin (if it were added to Bitcoin or an altcoin):
And he still hasn't refuted what I asserted upthread as re-quoted as follows.
He is speculating on what science knows now and what it can do in the future (and I don't even agree with his speculation but any way speculation is speculation, not fact). Due to National Security gag orders we can't even be sure we know what the current science is. The USA's covert agencies including the NSA have a $52 billion ANNUAL budget. And this doesn't include the black budget which Secretary of Defense Donald Rumsfeld admitted the day before 9/11 on national TV was $3 trillion unaccounted for in the defense budget (over the years), then the relevant records were conveniently destroyed when the Pentagon was hit by an "airplane" the next day. No backup copies of the records.
And his is ignoring the fact of history of what happened in the 1970s and 1980s (see what I wrote before as quoted above) which is an example that we can't always know.
Don't forget that Edward Snowden leaked (Washington Post) that the NSA is actively attempting to build a quantum computer.
Why risk it? Why not switch to Lamport signatures so no more risk at all.
The reason is because Bitcoin's blockchain is design in a way that switching to Lamport probably won't scale well. But an altcoin can fix this. Bitcoin probably can't, although maybe if they get off their lazy arse and finish the UXTO pruning, they might be able to do it.
Here is an excellent article on this quantum computing topic and also explains how Bitcoin's three encryption methods are combined, so it is relevant to this thread's title as well:
http://www.bitcoinnotbombs.com/bitcoin-vs-the-nsas-quantum-computer/
There are two things I dispute from the article.
http://crypto.stackexchange.com/a/2642
Here we go again depending on miners which are now becoming very centralized.
If anything that is argument for using cryptographic hashes such as Lamport for public key cryptography. You are reinforcing my point.
You are talking about conventional computers. My point above is we might not know the progress of quantum computers or mathematical attacks not released to the public.
Here we go again depending on miners which are now becoming very centralized.
I thought we were supposed to have a decentralized paradigm in play yet the Bitwards always fall back to centralization when ever they lose the technical argument...
- If we adopt something like Zerocoin to add more anonymity to the tracing of trail of ownership of a coin, these signatures can't be retroactively hardened later, thus all that history of anonymity is suddenly lost once the adversary gains a quantum computer.
If you aren't interested in looking up any of the many, many threads on QC, but still want to know about it, I'll give you the very short version. QC is hard to scale up. At the moment, it looks like QC devices will not be following Moore's law because the difficulty of retaining coherence appears to scale close to linearly with the number of gates, rather than inversely with the feature size like in classical devices. Even in the worst case, we should have years of warning before devices capable of breaking ECDSA are created, with decades much more likely.*
And he still hasn't refuted what I asserted upthread as re-quoted as follows.
- How do we know when the adversary has a quantum computer, given the capability of the NSA to issue national security letter gag orders? They had differential analysis to break cryptography in the 1970s and 80s and the public was unaware.
He is speculating on what science knows now and what it can do in the future (and I don't even agree with his speculation but any way speculation is speculation, not fact). Due to National Security gag orders we can't even be sure we know what the current science is. The USA's covert agencies including the NSA have a $52 billion ANNUAL budget. And this doesn't include the black budget which Secretary of Defense Donald Rumsfeld admitted the day before 9/11 on national TV was $3 trillion unaccounted for in the defense budget (over the years), then the relevant records were conveniently destroyed when the Pentagon was hit by an "airplane" the next day. No backup copies of the records.
And his is ignoring the fact of history of what happened in the 1970s and 1980s (see what I wrote before as quoted above) which is an example that we can't always know.
Don't forget that Edward Snowden leaked (Washington Post) that the NSA is actively attempting to build a quantum computer.
Why risk it? Why not switch to Lamport signatures so no more risk at all.
The reason is because Bitcoin's blockchain is design in a way that switching to Lamport probably won't scale well. But an altcoin can fix this. Bitcoin probably can't, although maybe if they get off their lazy arse and finish the UXTO pruning, they might be able to do it.
Here is an excellent article on this quantum computing topic and also explains how Bitcoin's three encryption methods are combined, so it is relevant to this thread's title as well:
http://www.bitcoinnotbombs.com/bitcoin-vs-the-nsas-quantum-computer/
There are two things I dispute from the article.
- When you spend, the quantum computing adversary could sniff your spend before it propagates sufficiently on the network and insert a double-spend that reaches more mining nodes faster than yours. In particular a powerful entity such as the NSA is already admitted to be capable of propagation attacks (see "The Quantum system" section at linked article).
- How do you ever get everyone to do the same human action in large distributed systems? There isn't even an official Bitcoin client any more.
And Shor's does not magically provide instant answers to questions posed, it allows a reduction in the search space, to the square root. sqrt(xy) = xy/2, so it will reduce the strength of our keys from 2128 to 264**. Note that 264 is still a huge number, and it is not at all a given that a real world system can accomplish it in 10 minutes.***
http://crypto.stackexchange.com/a/2642
So, hardly the end of the world. And that isn't even considering non-technical solutions, like a mining service that cultivates a reputation for safely embedding transactions into the blockchain in exchange for fees****.
Here we go again depending on miners which are now becoming very centralized.
* It is not clear whether or not it is possible to apply Grover's algorithm to hashing in reality. Grover's works on quantum circuits, and we can't even design a classical circuit for single SHA-256, much less double, and vastly much less for a quantum version. Note that I said circuit. The distinction is important, it isn't that I'm unaware of FPGAs and ASICS.
If anything that is argument for using cryptographic hashes such as Lamport for public key cryptography. You are reinforcing my point.
** ECDSA has a work factor of 1/2, so 256 bit ECDSA is as strong as an ideal 128 bit crypto system.
*** Incidentally, 264 falling down to the hour-or-two range is likely to trigger a crypto upgrade, in my opinion. Assuming, of course, that we haven't done so already for aesthetic reasons.
*** Incidentally, 264 falling down to the hour-or-two range is likely to trigger a crypto upgrade, in my opinion. Assuming, of course, that we haven't done so already for aesthetic reasons.
You are talking about conventional computers. My point above is we might not know the progress of quantum computers or mathematical attacks not released to the public.
**** The service would solicit transactions spending from old keys into new keys and would only accept transactions that met their fee structure. They would then mine internally, without revealing the pubkey to the rest of the network. Presumably for large enough transactions, they could even be convinced to mine at a loss by discarding blocks until they had two that they could publish at once. I leave the rest of the details as an exercise for the reader.
Here we go again depending on miners which are now becoming very centralized.
I thought we were supposed to have a decentralized paradigm in play yet the Bitwards always fall back to centralization when ever they lose the technical argument...
I feel bad for those of you that don't yet have annoyment on your ignore list. Apparently you'll just have to ignore him the hard way for now.
Based on the quotes and references in this thread, I find it likely that he is talking about quantum cryptography in here. If you head over to dev&tech and search for Quantum, you'll find lots of actual information about quantum computing and how it relates to bitcoin. In particular, you'll find refutations to whatever nonsense the tool is spewing now. I can say that with a decent level of confidence because he tends to repeat himself. His notion of debate is to say "Nuh-uh" to anything contrary to his gibberish and repeat himself. Also, when he finds a new audience (this is where you all come in), he likes to pretend that no one has ever refuted his insane claims. In short, he earned his glowing red ignore button.
If you aren't interested in looking up any of the many, many threads on QC, but still want to know about it, I'll give you the very short version. QC is hard to scale up. At the moment, it looks like QC devices will not be following Moore's law because the difficulty of retaining coherence appears to scale close to linearly with the number of gates, rather than inversely with the feature size like in classical devices. Even in the worst case, we should have years of warning before devices capable of breaking ECDSA are created, with decades much more likely.*
And Shor's does not magically provide instant answers to questions posed, it allows a reduction in the search space, to the square root. sqrt(xy) = xy/2, so it will reduce the strength of our keys from 2128 to 264**. Note that 264 is still a huge number, and it is not at all a given that a real world system can accomplish it in 10 minutes.***
So, hardly the end of the world. And that isn't even considering non-technical solutions, like a mining service that cultivates a reputation for safely embedding transactions into the blockchain in exchange for fees****.
* It is not clear whether or not it is possible to apply Grover's algorithm to hashing in reality. Grover's works on quantum circuits, and we can't even design a classical circuit for single SHA-256, much less double, and vastly much less for a quantum version. Note that I said circuit. The distinction is important, it isn't that I'm unaware of FPGAs and ASICS.
** ECDSA has a work factor of 1/2, so 256 bit ECDSA is as strong as an ideal 128 bit crypto system.
*** Incidentally, 264 falling down to the hour-or-two range is likely to trigger a crypto upgrade, in my opinion. Assuming, of course, that we haven't done so already for aesthetic reasons.
**** The service would solicit transactions spending from old keys into new keys and would only accept transactions that met their fee structure. They would then mine internally, without revealing the pubkey to the rest of the network. Presumably for large enough transactions, they could even be convinced to mine at a loss by discarding blocks until they had two that they could publish at once. I leave the rest of the details as an exercise for the reader.
Based on the quotes and references in this thread, I find it likely that he is talking about quantum cryptography in here. If you head over to dev&tech and search for Quantum, you'll find lots of actual information about quantum computing and how it relates to bitcoin. In particular, you'll find refutations to whatever nonsense the tool is spewing now. I can say that with a decent level of confidence because he tends to repeat himself. His notion of debate is to say "Nuh-uh" to anything contrary to his gibberish and repeat himself. Also, when he finds a new audience (this is where you all come in), he likes to pretend that no one has ever refuted his insane claims. In short, he earned his glowing red ignore button.
If you aren't interested in looking up any of the many, many threads on QC, but still want to know about it, I'll give you the very short version. QC is hard to scale up. At the moment, it looks like QC devices will not be following Moore's law because the difficulty of retaining coherence appears to scale close to linearly with the number of gates, rather than inversely with the feature size like in classical devices. Even in the worst case, we should have years of warning before devices capable of breaking ECDSA are created, with decades much more likely.*
And Shor's does not magically provide instant answers to questions posed, it allows a reduction in the search space, to the square root. sqrt(xy) = xy/2, so it will reduce the strength of our keys from 2128 to 264**. Note that 264 is still a huge number, and it is not at all a given that a real world system can accomplish it in 10 minutes.***
So, hardly the end of the world. And that isn't even considering non-technical solutions, like a mining service that cultivates a reputation for safely embedding transactions into the blockchain in exchange for fees****.
* It is not clear whether or not it is possible to apply Grover's algorithm to hashing in reality. Grover's works on quantum circuits, and we can't even design a classical circuit for single SHA-256, much less double, and vastly much less for a quantum version. Note that I said circuit. The distinction is important, it isn't that I'm unaware of FPGAs and ASICS.
** ECDSA has a work factor of 1/2, so 256 bit ECDSA is as strong as an ideal 128 bit crypto system.
*** Incidentally, 264 falling down to the hour-or-two range is likely to trigger a crypto upgrade, in my opinion. Assuming, of course, that we haven't done so already for aesthetic reasons.
**** The service would solicit transactions spending from old keys into new keys and would only accept transactions that met their fee structure. They would then mine internally, without revealing the pubkey to the rest of the network. Presumably for large enough transactions, they could even be convinced to mine at a loss by discarding blocks until they had two that they could publish at once. I leave the rest of the details as an exercise for the reader.
said that even if a quantum computer were to be invented, that the other equipment would still not be able to process all the information needed to crack BTC..., or words to that effect.
Please do post the paper if you find it. Probably that is referring to the fact that all ECDSA public keys are hashed before sent to the blockchain, thus quantum computing can only apply Grover's algorithm to those hashes (as I wrote upthread only effectively halves the bit length of the hashes) thus probably can't "crack" (actually invert) them to reveal the ECSDA "inside" of the hash. But as I wrote upthread, that might be an irrelevant point, because the ECDSA public key is revealed when one of those hashed addresses is spent:
It is argued this won't matter because the public key addresses are hashed on the blockchain until the balances are spent. (that is if you follow best practices and don't resend the change back to same public key address spent from) And that everyone can spend their balances to a new quantum-proof encryption method (e.g. Lamport) if ever quantum computers are known to be created.
However that erroneous argument has at least 4 flaws.
However that erroneous argument has at least 4 flaws.
- When you spend, the quantum computing adversary could sniff your spend before it propagates sufficiently on the network and insert a double-spend that reaches more mining nodes faster than yours. In particular a powerful entity such as the NSA is already admitted to be capable of propagation attacks (see "The Quantum system" section at linked article).
- How do you ever get everyone to do the same human action in large distributed systems? There isn't even an official Bitcoin client any more.
- ...
Also those hashes do not nothing to protect Zerocoin.
- How do we know when the adversary has a quantum computer, given the capability of the NSA to issue national security letter gag orders? They had differential analysis to break cryptography in the 1970s and 80s and the public was unaware.
- If we adopt something like Zerocoin to add more anonymity to the tracing of trail of ownership of a coin, these signatures can't be retroactively hardened later, thus all that history of anonymity is suddenly lost once the adversary gains a quantum computer.
P.S. I generalized that improvement (I mentioned upthread) to Lamport signatures and showed that Lamport is a degenerate case.
...
I would like to thank all of you for providing insights into the cryptography behind Bitcoin. I will now have to digest what you all wrote and look into this more. Thanks again.
I did receive a paper sent to me from my "Bitcoin Insider" ("B.I"), my handy pseudonym for the guy helping me write my "Bitcoin for Beginners" series at my blog (the paper is locked away in my emails somewhere) that said that even if a quantum computer were to be invented, that the other equipment would still not be able to process all the information needed to crack BTC..., or words to that effect. If I can find the paper (or if I can get "B.I." to resend it), I will post the link here. The last 2/3rds of the paper was way beyond me.
I am not going to block ANYONE while I am still learning...
I would like to thank all of you for providing insights into the cryptography behind Bitcoin. I will now have to digest what you all wrote and look into this more. Thanks again.
I did receive a paper sent to me from my "Bitcoin Insider" ("B.I"), my handy pseudonym for the guy helping me write my "Bitcoin for Beginners" series at my blog (the paper is locked away in my emails somewhere) that said that even if a quantum computer were to be invented, that the other equipment would still not be able to process all the information needed to crack BTC..., or words to that effect. If I can find the paper (or if I can get "B.I." to resend it), I will post the link here. The last 2/3rds of the paper was way beyond me.
I am not going to block ANYONE while I am still learning...
For the laymen, most public key cryptography (e.g. RSA and Bitcoin's ECDSA and Zerocoin) is based on number theoretic assumptions such as the difficulty in factoring discrete logarithms which makes them impossible to crack (at sufficient bit lengths) with current computers. However, quantum computing would (in theory) enable Shor's algorithm which reduces these factoring problems from exponential to polynomial time. Thus what would have required a zillion years to crack can be cracked in reasonable time to make it practical.
Ahaha. For the laymen. Hahahahaha.
Let me try again.
For the laymen, most public key cryptography (e.g. RSA and Bitcoin's ECDSA and Zerocoin) is based on number theoretic assumptions such as the difficulty in factoring certain difficult to factor algebraic expressions (e.g. discrete logarithms) which makes them impossible to crack (if the key bit lengths are long enough) with current computers. However, quantum computing would (in theory) enable Shor's algorithm which reduces these factoring problems from exponential to polynomial time, i.e. reduced from O(2N) to O(Nk) so for example if N = 128 and k = 3, then reduced from 3.4e+38 (number with 38 trailing zeros) to 2,097,152. Thus what would have required a zillion years to crack can be cracked in reasonable time to make it practical.
However, cryptographic hash functions do not rely on number theoretic assumptions, and instead of being closed-form algrebraic expressions are a chaotic mix of confusion and diffusion (that breaks the ability to express algebraically over all number groups). They instead rely on the assumption of asymptotically perfect random distribution of the input to the output, which can be somewhat verified like this. Thus they can't be cracked with Shor's algorithm and only Grover's algorithm can be applied with a quantum computer. Thus they remain exponential time, and only the bit lengths (exponents) get effectively halved.
Note a specific numerical example for time complexity as I've shown above is not formally the correct way to think about it, but this is for a non-mathematical audience.
For the laymen, most public key cryptography (e.g. RSA and Bitcoin's ECDSA and Zerocoin) is based on number theoretic assumptions such as the difficulty in factoring discrete logarithms which makes them impossible to crack (at sufficient bit lengths) with current computers. However, quantum computing would (in theory) enable Shor's algorithm which reduces these factoring problems from exponential to polynomial time. Thus what would have required a zillion years to crack can be cracked in reasonable time to make it practical.
Ahaha. For the laymen. Hahahahaha.
Quantum is useless.
This really isn't true. It's hard to gauge how useful and how soon, but if ever practical, it is definitely not useless. Many of the early unspent coins aren't even protected by RIPEMD-160, so that would be a plentiful place to start.
OP, please note: There is a reason that AnonyMint's "ignore" button is a bright orange.
Had to intrude since some newbies will be confused since you guys keep pointing out the orange ignore being highlighted
The orange ignore highlights are disabled until we switch over to the new forums
So we all look the same (Noticed when Mircea suddenly lost her orange shine)
I opened that thread a while back so I distinctly recall this as a fact
https://bitcointalksearch.org/topic/m.4378369
For the laymen, most public key cryptography (e.g. RSA and Bitcoin's ECDSA and Zerocoin) is based on number theoretic assumptions such as the difficulty in factoring discrete logarithms which makes them impossible to crack (at sufficient bit lengths) with current computers. However, quantum computing would (in theory) enable Shor's algorithm which reduces these factoring problems from exponential to polynomial time. Thus what would have required a zillion years to crack can be cracked in reasonable time to make it practical.
However, cryptographic hash functions do not rely on number theoretic assumptions. Instead they rely on the assumption of asymptotically perfect random distribution of the input to the output, which can be somewhat verified like this. Thus they can't be cracked with Shor's algorithm and only Grover's algorithm can be applied with a quantum computer. Thus they remain exponential time, and only the bit lengths (exponents) get effectively halved.
Lamport signatures use only cryptographic hashes. One of the problem with employing them in a blockchain has been they take up much space (either for the public key or the signature or both), but I just published a discovery in my prior post which enables making them smaller in exchange for more computation.
This discovery makes Lamport signatures more practical for blockchains than they were before, but still they are not as small as number theoretic public key cryptography.
Unfortunately I don't think this will work for Bitcoin, at least not until they implement pruning of the UXTO, but it can work in an altcoin.
I currently see no way to make Zerocoin resistant to Shor's algorithm, but I am still researching this. But Zerocoin is mostly useless any way because of pattern analysis on coin amounts.
However, cryptographic hash functions do not rely on number theoretic assumptions. Instead they rely on the assumption of asymptotically perfect random distribution of the input to the output, which can be somewhat verified like this. Thus they can't be cracked with Shor's algorithm and only Grover's algorithm can be applied with a quantum computer. Thus they remain exponential time, and only the bit lengths (exponents) get effectively halved.
Lamport signatures use only cryptographic hashes. One of the problem with employing them in a blockchain has been they take up much space (either for the public key or the signature or both), but I just published a discovery in my prior post which enables making them smaller in exchange for more computation.
This discovery makes Lamport signatures more practical for blockchains than they were before, but still they are not as small as number theoretic public key cryptography.
Unfortunately I don't think this will work for Bitcoin, at least not until they implement pruning of the UXTO, but it can work in an altcoin.
I currently see no way to make Zerocoin resistant to Shor's algorithm, but I am still researching this. But Zerocoin is mostly useless any way because of pattern analysis on coin amounts.
PS: AnonyMint is right, once QCs appear Bitcoin will be f***ed. At least noone has offered a good solution to avoid this.
I think the community has grown tired of hearing me say I know solutions but haven't released them yet. I will give a small tidbit gift (giving away my secrets before I can implement them) to the community now, so they will realize I am not all talk and no action.
I added the following partial "solution" to Wikipedia yesterday:
https://en.wikipedia.org/wiki/Lamport_signature#Short_keys_and_signature
Now I go quiet if I can.
This is incorrect. We should ignore you too.
Incorrect? OK, keep following ostrich policy...
This is incorrect. We should ignore you too.
Incorrect? OK, keep following ostrich policy...
OP, please note: There is a reason that AnonyMint's "ignore" button is a bright orange.
OP, please note: The most valuable info is obtained from people with bright orange "ignore" button. Because they don't lick someone's arses and don't repeat mantras that 1 BTC will be worth 1 million dollars.
PS: AnonyMint is right, once QCs appear Bitcoin will be f***ed. At least noone has offered a good solution to avoid this.
Jump to: