Thursday, June 16, 2011

Explaining Bitcoin and Cryptography, Part 2

UDPATE: This was actually posted ~8:15 am CST, 6/25/11. For some reason, the date shown is that of an earlier draft. Blame blogger/blogspot.

Now that you've gotten your feet wet with my masterful explanations of some of the cryptographic pre-requisites of Bitcoin, you're ready for a more detailed explanation that removes some of the simplifications I used last time. But I will focus more on the cryptography here, telling it as I wish someone had told me when I was learning. So without further ado...

"Bitcoin really uses no encryption at all?"

The protocol itself does not involve encrypted messages, as many news outlets mistakenly report. Rather, the protocol is based on everyone seeing every message, unencrypted. However, some consider hashing a text to be encrypting it. And the address you use to send and receive is actually a hash of your public key rather than the public key itself (the signature protocol used only requires the verifier to have a hash of the public key). So, in that sense, there is encryption.

Also, as an optional (but recommended) technique, you can encrypt the "wallet file" that stores your private (and public) keys so that if someone gets control of your computer, they can't use your private keys to sign away your bitcoins.

So be careful: just because a protocol uses "cryptography" ("In cryptography we trust" being an unofficial motto of Bitcoin), doesn't mean it's actually encrypting anything, just that it's using a technique studied in the field of cryptography.

You don't usually sign an entire message in public key signatures.

I simplified: normally you just need to sign a hash of the message. Given the properties of hash functions, this is just as good as signing the message: it doesn't introduce a new weakest link, and signing a hash is computationally easier than signing the full message.

Now, you might argue that, "But there are infinitely many messages (preimages) that hash to the same digest! You said so yourself! How could I not be introducing a weakness by only signing the message digest? That allows someone to claim that I signed every preimage that hashes to that digest! I don't want to take responsibility for signing all those unknown messages!"

Calm down. For one thing, those second pre-images are, by design, very difficult to find, even despite the huge numbers of them (remember first and second pre-image resistance?). Don't let the infinite size deceive you. If the digest is 256 bits long (as in the case of the hash function bitcoin uses, SHA-256), then that means that only 1 in 2^256 (about 10^77) of all messages will "collide" with yours. That means that, on average, they have to look through 2^128 (about 3*10^38) candidate messages just to find one collision. That's a lot of work! (The "birthday paradox" ensures that you only have to search a space whose size is the square root of the space of digests: sqrt(2^256) = 2^128.)

And remember, cryptographic hash functions "look random" -- meaning there's no simple relationship between two preimages that collide. So let's say that your message is, "I hereby transfer $10 to Bob", and you sign the SHA-256 digest of that message. And let's even assume that an attacker did a lot of work and found their first collision, entitling them to claim you signed a different message, since it hashes to the same digest. Danger! Well, no, no danger. Because of the pseudo-randomness of hash functions, that "colliding message" won't be something neat and useful for the attacker, like "I hereby transfer $1 million to Bob."

Rather, in all likelihood, their second pre-image (i.e. purported alternate message) will look something like, "n02nS+TH/4dXcuPasQQn4". Doesn't seem to get the attacker very far, does it? All it lets them do is say, "Hey, I have proof that Silas sent the message 'n02nS+TH/4dXcuPasQQn4', and yes, I durn well do have have the signature, derived from Silas's public/private keypair, which matches the hash of that message. Checkmate!"

See the problem? "Um, excuse me Mr. Mallory, but what does 'n02nS+TH/4dXcuPasQQn4' actually mean? What is Silas transferring to you with that statement? It just looks like garbled text. I doubt Silas actually signed something like that ... hey, it looks like he *did* sign the hash of this other message, which actually makes sense. You can buzz off now, Mallory."

(Note: this may be a moot point, as I don't know if the Bitcoin protocol requires you to sign a hash or the original message, since the latter is already short.)

"But how do pubilc key signature algorithms actually work?"

Those of you with a scientific or rational mindset will rightly object that I didn't actually tell you how to digitally sign a message. I really just gave you the vocabulary for discussing public key signatures and asked you to take on faith my claim that the relationships hold (i.e. which parts of the protocol are "hard" and which are "easy"). I certainly didn't tell you enough to go out and create your own digital signature scheme (be it weak or strong), and this probably bothered some readers.

Well, I still won't! But I invite you to read about RSA, a commonly-used public key algorithm (with both an encryption and signature protocol). It's fairly easy to understand, and will shed some light on how it's possible for them to introduce the criticial asymmetries, such as how the private key can be difficult to infer from the public key, making it hard to generate a signature for anyone but the private key holder.

"And what do trapdoor functions have to do with public key signatures, again?"

When I mentioned the use of trapdoor one-way functions (TOWF) as underlying public key algorithms, I didn't make it clear how you turn a TOWF into a public key signature method. In the comment section of the last post, Boxo spelled out the mapping. I'll phrase it in a slightly different way. Remember that a TOWF is a function meeting the following criteria:

1) Given x, it's easy to compute f(x).

2) Given a value V equal to f(x1), it's hard to infer x1 (or any other x such that f(x) = V).

3) But if you have some "trapdoor knowledge", it's easy to find that x1 given V.

So if you have a TOWF, here's how you can sign a message. First you find a particular instance of the function class, f1(x) to which your TOWF belongs. The information that identifies f1(x) out of the function class is your public key. The trapdoor information is your private key.

One you generate a message M, you let that M (or some hash of M) take the role of V in item 2) of the description above. Because you have the "trapdoor knowledge" (item 3), you can find x1 easily, where f1(x1) = M. Then x1 is your signature, and you attach it to the message.

Others can very your signature by checking that f1(x1) really does equal M (or the hash of M). This is the "mathematical relationship for verifying a signature" that I kept mentioning in the last post. Per item 1, this computation is easy.

Hope you found this helpful!


digital certificates said...

I never knew that Bitcoin uses no encryption.The optional technique that you suggested of encrypting the wallet file seems useful but is their no other way?

thomblake said...

>The "birthday paradox" ensures that you only have to search a space whose size is the square root of the space of digests: sqrt(2^256) = 2^128.

This might be confusing - it looked to me on first reading like you were saying they'd only need to look through 2^128 messages to find one that matches with *your particular message*, while the birthday paradox merely entails that you should be able to find an arbitrary 2 matching messages in that time. Or am I mistaken?

Silas Barta said...

Yeah, I wasn't thinking there. THe point I was just trynig to get across is that the security of the hash is regarded has half the bitlength of its size.

Unknown said...

Cashout Bitcoin Money into your bank account directly. Contvert Bitcoin Funds into Real Cash. Exchange Bitcoin Payment into Bank Account with Highest Available Rate.
Bitcoin to bank transfer || Bitcoin|| Bitcoin to Bank wire


Goldman Sachs Is AFRAID Of This!

This Will Make Banks Obsolete!

Cryptocurrencies such as Bitcoin have taken over the world by storm.

Goldman Sachs and other central banks all over the world have realized they cannot fight against Bitcoin and other Alt coins.

They are especially afraid that you’ll see this SHOCKING video.

[Click Here To Watch The Video]

This is 100,000 times bigger than the tech boom.

Because it’s not only limited to US companies.

So what does this mean?

You can now make back the money back you didn’t get a chance to make during the late 90s and early 2000s tech boom.

The good news is that the vast majority of people out there have no idea what this is.

That’s why you can generate profits of over 10,000% ROI!

Just watch this shocking video and learn how you too can do it!

[Click Here To Watch The Video]

Speak soon!


sandeep saxena said...

I was so happy to read this article. Thankyou so much for good article.
Wordpress Training in Chennai
Wordpress Training in T Nagar
Wordpress Training in OMR
Wordpress Training in Velachery
Wordpress Training in Tambaram
Struts Training in Chennai
Spring Training in Chennai
Hibernate Training in Chennai

anushya said...

It’s a classic great for me to go to this blog site, it offers more helpful and wonderful suggestions.
Java Training in Bangalore
Java Training Institutes in Bangalore
Best Java Institute in Bangalore
Hadoop Training in Bangalore
Ethical Hacking Course in Bangalore
Selenium Training in Bangalore
Data Science Training in Bangalore
German Language Course in Bangalore
Best AWS Training in Bangalore

vinudevan said...

Thanks for sharing informative article with us..
Hibernate Training in Chennai
Hibernate Training
hibernate training in Velachery
hibernate training in Thiruvanmiyur
hibernate training in Tambaram
Spring Training in Chennai
clinical sas training in chennai
DOT NET Training in Chennai
QTP Training in Chennai
LoadRunner Training in Chennai

Riya Raj said...

Fantastic blog!!! Thanks for sharing with us, Waiting for your upcominga data.
Digital Marketing Course in Chennai
Digital Marketing Course
digital marketing classes in chennai
Digital Marketing Training in Chennai
Digital marketing course in Guindy
Digital marketing course in Tambaram
Python Training in Chennai
Big data training in chennai
SEO training in chennai
JAVA Training in Chennai

Anbarasan14 said...

Nice post. Thanks for sharing.
Spoken English Classes in Chennai
Spoken English Class in Chennai
Spoken English in Chennai
IELTS Training in Chennai
IELTS Chennai
Best English Speaking Classes in Mumbai
Spoken English Classes in Mumbai
IELTS Mumbai
IELTS Center in Mumbai
IELTS Coaching in T Nagar

dhivya said...

I would definitely thank the admin of this blog for sharing this information with us. Waiting for more updates from this blog admin.
RPA Training in Chennai
Robotic Process Automation Certification
Robotic Process Automation Training
DevOps Training in Chennai
Azure Training in Chennai
VMware Training in Chennai
RPA Training in Porur
RPA Training in OMR
RPA Training in Adyar
RPA Training in Anna Nagar

Manisha Sudha said...

Nice blog....waiting for next update....
Struts Training in Chennai
Best Struts Training in Chennai
Best Struts Training institute in Chennai
struts Training in OMR
struts Training in Porur
Wordpress Training in Chennai
SAS Training in Chennai
Spring Training in Chennai
Photoshop Classes in Chennai
DOT NET Training in Chennai

Prakash said...

More impressive blog!!! Thanks for shared with us.... waiting for you upcoming data.
Software Testing Training in Chennai
software testing course in chennai
testing courses in chennai
software testing training institute in chennai
Software testing training in Thiruvanmiyur
Software testing training in Velachery
Python Training in Chennai
Digital marketing course in chennai
Python Training in Chennai
JAVA Training in Chennai

Nannie Co Pam said...

Great Article. Thank you for sharing! Really an awesome post for every one.

IEEE Final Year projects Project Centers in Chennai are consistently sought after. Final Year Students Projects take a shot at them to improve their aptitudes, while specialists like the enjoyment in interfering with innovation. For experts, it's an alternate ball game through and through. Smaller than expected IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble. Final Year Project Domains for IT It gives you tips and rules that is progressively critical to consider while choosing any final year project point.

Spring Framework has already made serious inroads as an integrated technology stack for building user-facing applications. Spring Framework Corporate TRaining the authors explore the idea of using Java in Big Data platforms.
Specifically, Spring Framework provides various tasks are geared around preparing data for further analysis and visualization. Spring Training in Chennai

amit tavva said...

keep up the good work. this is an Assam post. this to helpful, i have reading here all post. i am impressed. thank you. this is our digital marketing training center. This is an online certificate course
digital marketing training in bangalore |

janani ram said...

Thanks for updating this information. Good job.
content writing course in chennai
content writing training in chennai
French Classes in Chennai
pearson vue test center in chennai
Informatica Training in Chennai
Data Analytics Courses in Chennai
Spoken English in Chennai
German Classes in Anna Nagar
Spoken English Classes in Anna Nagar

Reshma said...

Such a great blog. I Got Lots of informations about this technology.Keep update like this....
Tally Course in Chennai
Tally Course in Hyderabad
Tally training coimbatore
Tally Course in Coimbatore
Tally course in madurai
Tally Training in Chennai
Tally Institute in Chennai
Tally Classes in Bangalore
Best tally training institute in bangalore
Ethical hacking course in bangalore

sasi said...

Great experience for me by reading this blog. Thank you for wonderful article.
Angularjs Training in Chennai
Angularjs Training in Bangalore
angularjs training institute in bangalore
Angular Training in hyderabad
best angularjs training in bangalore
angular training in bangalore
Salesforce Training in Bangalore
Hadoop training in bangalore
angular course in bangalore
angularjs training in marathahalli

yadav said...

Nice Blog. Keep update more information about this..
IELTS Coaching in Chennai
IELTS coaching in bangalore
IELTS coaching centre in coimbatore
IELTS coaching in madurai
IELTS Coaching in Hyderabad
Best ielts coaching in bangalore
ielts training in bangalore
ielts coaching centre in bangalore
ielts classes in bangalore
ethical hacking course in bangalore

Anonymous said...

Thank you so much for sharing this great blog.Very inspiring and helpful too.Hope you continue to share more of your ideas.I will definitely love to read. antminer s17 tutorial

sasi said...

The blog you shared is very good. I expect more information from you like this blog. Thank you.
Web Designing Course in chennai
Web Designing Course in bangalore
web designing course in coimbatore
web designing training in bangalore
web designing course in madurai
Web Development courses in bangalore
Web development training in bangalore
Salesforce training in bangalore
Python training in Bangalore
Web Designing Course in bangalore with placement

subha said...

Thank you so much for updating the useful blog. I liked this blog..
Spoken English Classes in Bangalore
Spoken English Classes in Chennai
Spoken English Classes in BTM
Spoken English Classes in Marathahalli
Spoken English Classes near Marathahalli
Spoken English Marathahalli
DevOps Training in Bangalore
PHP Training in Bangalore
Data Science Courses in Bangalore
English Speaking Course in Bangalore

info said...

After going over a few of the blog articles on your site, I seriously appreciate your technique of blogging. I added it to my bookmark webpage study list and will be checking back in the near future. Please visit my web site too and tell me what you think.