Bitcoin Forum

...

I'm new just today, but have really been very happy with the quality of replies I am seeing and getting, a great community you guys have built! 

So, let me move on to a more complex set of subjects for me to learn about.  My understanding is that the Bitcoin Ecosystem uses three encryption methods:

-- SHA256, a hash-function, see link for what I know (not much) here: /lq667xz]http://[Suspicious link removed]/lq667xz (http://[Suspicious link removed).  Play with that hashing function here at this fun little place: http://www.xorbin.com/tools/sha256-hash-calculator (http://www.xorbin.com/tools/sha256-hash-calculator).  (I will learn some more about hash functions as time permits.)

-- I believe an Elliptic Curve Encryption method is used as well: http://kakaroto.homelinux.net/2012/01/how-the-ecdsa-algorithm-works/ (http://kakaroto.homelinux.net/2012/01/how-the-ecdsa-algorithm-works/), this link was given to me by zerohedge.com (http://zerohedge.com) member "zaphod", but I have not had a chance to go look into it, zaphod said it was complicated...

-- "RIPEMD160" (which I believe is another hashing function) is also used, but I know essentially nothing about it other than wikipedia's entry.

***

1)  Is my information correct?

2)  How do those pieces all fit together?  (Or is this question waaaay complicated ??)

3)  Is there a nice tidy little place where I can read up on these three?

Those are all used in Bitcoin however none of them are encryption methods.  Hashing algorithms, digital signature algorithms, and encryption algorithms are all cryptography. 

There is actually no encryption used in the Bitcoin protocol although many wallets do employ encryption (most commonly AES) to protect the keys from being stolen.

As for how do they all fit together ... that is a long topic and I have drunk too much port.  Start looking at the bitcoin wiki.

For general information on SHA-256, RIPEMD-160, and ECDSA (or ECC in general) wikipedia will give you some basic background information.

Bottom line is Bitcoin can be cracked with a future quantum computer (because it is based on number-theoretic assumptions cryptography, e.g. destruction factoring from a constructed whole, instead of Random oracle style cryptography, e.g. construction of deconstruction into partitions).

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.

• 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 (https://www.schneier.com/blog/archives/2013/10/how_the_nsa_att.html) (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 (https://bitcointalk.org/index.php?topic=498002.msg5501014#msg5501014).
• 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 (https://bitcointalk.org/index.php?topic=495527.msg5508024#msg5508024) 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.

And people wonder why I think Bitcoin is piece-of-shit.  ::) (and this is only 10% of the technical problems I see in Bitcoin)

The worst would be if the current ECDSA variant chosen was seeded by the NSA. There is some speculation about that yet apparently Bitcoin's choice was not one of the ones seeded opaquely by NIST or other potential surrogate (although I haven't dug in and don't trust the summaries I've seen to do my homework for me).

I think the OP wanted to know how to find out more technical information, not get brainwashed by crackpot conjecture.

The only thing debatable about what I wrote is when the quantum computer will be a reality. Whether you believe or not the NSA (or others) would abuse their power is subjective of course.

OP, please note: There is a reason that AnonyMint's "ignore" button is a bright orange.
Edit: Just discovered that the highlighted "ignore" link has been temporarily disabled.


I don't drink port.  I'll have a go at it:

Bitcoin uses sha256 to generate a unique ID to reference two important types of data.  Indexing these IDs in a database makes searching for them much faster/easier.

A block can be identified by its sha256 hash
A transaction can be identified by its sha256 hash. The transaction hash is only a reliable method of lookup after the transaction is confirmed. Until then, then transaction hash can be modified.
sha256 hashes are used to generate a merkle tree identifying the ordered list of transactions in a block.
The merkle root (also a sha256 hash) is used to prove that a merkle tree for a particular block is valid.

Bitcoin also uses sha256 as a proof-of-work system to make it difficult for an attacker to modify the blockchain.  The result of the sha256 proof-of-work hash is the block hash.

ECDSA (using the Secp256k1 curve) is an Elliptic Curve Digital Signature Algorithm used to provide proof that a spender is authorized to spend the bitcoins that they use to fund a transaction.

ECDSA depends on a mathematically linked pair of keys ( a private key used for creating the signature, and a public key used to verify the signature)  To increase security, and shorten the size of the address, bitcoin passes the public key first through sha256, and then the result of that is passed through RIPEMD160 (another hashing algorithm).  The result of the ripemd160 hash is concatenated with a 4 byte checksum and a version number.  This value is then encoded using a special base58 encoding.  The result of that is that bitcoin address.

This means that if you are given a public key, then you can repeat the base58(ripemd160(sha256(public key))) process to verify that the given public key corresponds to a given bitcoin address.  If you are given a digital signature AND a public key, then you can use the public key to verify the signature, and then repeat the base58(ripemd160(sha256(public key))) to verify that the signature corresponds to a particular address.

These are the only places I can think of that the protocol uses any of these cryptographic functions.  I suppose it's possible that I've somehow missed something.

And note he hasn't dared tried to refute what I wrote, because he can't.

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.

AnonyMint and Come-from-Beyond please note: the haterz are gonna hate.  You guys just keep on preaching the truth and earning those bright orange ignore banners!  

My physicist friend from D-Wave here in Vancouver says they crack Secp256k1 for breakfast.  Muthaf*%#n Q-bits, yo.  

I see u can say only "blah-blah-blah". Care to say anything valuable? Prove AnonyMint wrong or something.

PS: Yes, I said that u r just a troll.

That's a relief.  I was worried I wasn't being obvious enough and people might have thought that the D-Wave Quantum Computing Company (http://www.dwavesys.com) actually had a quantum computer, let alone one that could crack Secp256k1.  When do D-Wave insiders expect to be able to crack Secp256k1?  Answer: never.  



I did provide something valuable: accurate ridicule.  It was the ridicule of MtGox that prevented even more people from losing money there (the "goxxing" meme, people making fun of MK [although I do not believe he was incompetent (https://bitcointalk.org/index.php?topic=497289.0)]). We are all operating in an unregulated economy and people are waking up to the fact that trust and reputation are important.  

Debating with either of you has shown time and time again to be fruitless.  New readers can check your post histories to see that:

- You are a large stakeholder in NXT and use any opportunity to push this agenda.  You are looking for a platform right now to talk about some disingenuous advantage of NXT over bitcoin.  I went to the Wiki (http://wiki.nxtcrypto.org/wiki/Current_Features) and found one already: "Nxt's PoS mining does not cause monetary inflation."  This implies disingenuously that distributing coins by mining is somehow unfair and NXT came up with a better system.  But another way of describing the NXT coin distribution model is that the original stakeholders started with control of 100% of all coins that will ever be in existence!

- AnonyMint is a notorious thread derailer, who--with great verbosity--will use any platform he can to paint his fear-based image of a dystopian future if we don't all adopt his completely anonymous coin [which we've been waiting to see for for quite some time now].

By discussing personality of ur opponents u proved that u have no real counter-arguments. Not gonna waste my time on u anymore.

Succinctly:

Each private key in your wallet is a 256-bit number. ECC (yes, it is complicated) is used to create a corresponding public key for each private key.

Both SHA-256 and RIPEMD-160 hashing are used together to derive the corresponding bitcoin address from each public key.

Public-key signing (making use of the ECC-generated public and private keys) is used to sign and verify each transaction sending bitcoins from an address.

SHA-256 hashing is also used to bundle up transactions broadcast on the network into blocks that are verified as legit, and with each block containing a reference to the previous block for added security. Creating these blocks is called "mining".

This is incorrect. We should ignore you too.

Incorrect? OK, keep following ostrich policy...

Quantum is useless.

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.

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 (http://cr.yp.to/snuffle/diffusion.html). 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.

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://bitcointalk.org/index.php?topic=404354.msg4378369#msg4378369

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.

Ahaha. For the laymen. Hahahahaha.

 :D

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(2^N) to O(N^k) 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 (http://cr.yp.to/snuffle/diffusion.html). 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.

...

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

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:


Also those hashes do not nothing to protect Zerocoin.


P.S. I generalized (https://gist.github.com/karlgluck/8412807/#comment-1185752) that improvement (I mentioned upthread) to Lamport signatures and showed that Lamport is a degenerate case.

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(x^y) = x^y/2, so it will reduce the strength of our keys from 2¹²⁸ to 2⁶⁴**.  Note that 2⁶⁴ 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, 2⁶⁴ 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.

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 (http://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html) (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.


Nonsense. Shor's algorithm is not a brute force attack. The author inserted this disinformation into his otherwise good article, because most users don't understand that Shor's algorithm doesn't require a brute force capability (http://www.askamathematician.com/2011/02/q-how-can-quantum-computers-break-ecryption/).


I already refuted that upthread:

---

http://crypto.stackexchange.com/a/2642


Also I think you are wrong. Grover's algorithm is what halves the effective bit length, i.e. square root of the solution space. As I explained upthread, Grover's algorithm applies (in theory) to cryptographic hashes, but for ECDSA and RSA the much more powerful Shor's algorithm applies. Shor's algorithm reduces to polynomial time as I explained upthread. If I am not mistaken, you've just shown yourself to be incompetent and not worth listening to.

http://security.stackexchange.com/a/37638
http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_computing_attacks_on_key_strength
http://crypto.stackexchange.com/a/9940

---

Also note I wrote upthread that in addition to the quantum computing threat, we can't be sure that the curve chosen for ECDSA isn't backdoored or that some mathematical algorithm couldn't be discovered secretly by the NSA, as they did with differential cryptographic analysis in the 1970s and 1980s and they could crack everyone, but no one knew.

Cryptographic hashes are much less likely than mathematical group algorithms (e.g. RSA and ECDSA) to fall to mathematical cryptographic analysis if they are designed correctly (http://cr.yp.to/snuffle/design.pdf) to break algebraic linearity over all mathematical groups.


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

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.

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?

@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, is a plain lie. QCs can crack Bitcoin keys as fast as legit owners can sign transactions.

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" (http://www.youtube.com/watch?v=dGMPDBITApQ) "we" are not under an NSA gag order ourselves which prevents us from telling you this.

Message From Anonymous (http://www.youtube.com/watch?v=eG5PUMDRfGI).

FYI the prior related discussion where gmaxell censored me:

https://bitcointalk.org/index.php?topic=289795.msg3337585#msg3337585

Other:

https://bitcointalk.org/index.php?topic=309594.msg3328064#msg3328064

The discussion continued in another thread:

https://bitcointalk.org/index.php?topic=548418.msg5975715#msg5975715

http://pqcrypto.org/