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!

48 comments:

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

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

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

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

Max 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

Aparna said...

Nice Article and Thanks for sharing the useful post looking really so great. Keep doing...!
Social Media Marketing Courses in Chennai
Social Media Training
Oracle Training in Chennai
Pega Training in Chennai
Linux Training in Chennai
Tableau Training in Chennai
Spark Training in Chennai
Graphic Design Courses in Chennai
Placement Training in Chennai
Unix Training in Chennai
Power BI Training in Chennai

bairav said...

The blog is very informative.Keep posting like this.
Spoken English & Communication Coaching Classes Training in Chennai | Certification | Online Courses

German Classes in Chennai | Certification | Language Learning Online Courses | GRE Coaching Classes in Chennai | Certification | Language Learning Online Courses | TOEFL Coaching in Chennai | Certification | Language Learning Online Courses | Spoken English Classes in Chennai | Certification | Communication Skills Training

bairav said...

The blog is very informative.Keep posting like this.
Spoken English & Communication Coaching Classes Training in Chennai | Certification | Online Courses

German Classes in Chennai | Certification | Language Learning Online Courses | GRE Coaching Classes in Chennai | Certification | Language Learning Online Courses | TOEFL Coaching in Chennai | Certification | Language Learning Online Courses | Spoken English Classes in Chennai | Certification | Communication Skills Training

Aishu said...

Thank you for sharing this article. it was very useful
German Classes in Chennai | Certification | Language Learning Online Courses | GRE Coaching Classes in Chennai | Certification | Language Learning Online Courses | TOEFL Coaching in Chennai | Certification | Language Learning Online Courses | Spoken English Classes in Chennai | Certification | Communication Skills Training

bill.wood said...

Very effective and communicative platform to discuss customer issues within a short span of time digital marketing training in hyderabad

stevencombs said...

Pretty! It was really a wonderful blog. Thanks for the provided information.
bitcoin era

Babu said...

Very Nice article, thanks for sharing the article.
devops methodology
habits of success
mobile application testing tools
why web development is important
advanced excel interview questions

vé máy bay đi Canada said...

Mua vé máy bay tại Aivivu, tham khảo

gia ve may bay di my

chuyến bay về việt nam từ mỹ

giá vé máy bay đi nhật vietjet

đặt xe taxi sân bay

bamgosoo said...


I seriously love your website.. Excellent colors & theme.
Did you create this amazing site yourself? Please reply back as I’m attempting to create my own site
and want to know where you got this from or just what the theme is named.
Cheers!

Review my webpage - 오피사이트


opbestcom7 said...

Hey I'm at work surfing around your blog from my new iphone 3gs! Just wanted to say I love reading through your blog and look forward to all your posts! Carry on the superb work!

Review my page please: 오피
(mie)

Turkish e visa said...

I just wanted to thank you very much once again. Thank you for all your work on this website. You can get a Turkey e visa anywhere with an internet connection and computer , laptop in less than 1 hour quick processing, your Turkish e visa should be ready.

Kenya online visa application said...

Thank you The international travelers traveling to Kenya need to check the Kenya online visa application information online. However, the online visa application offers you the best, fastest online visa services. Thank you

kenya health form said...

Nice work.. Thank you :) The foreign tourist who are traveling to Kenya must vaccinate themselves with yellow fever vaccine. To prevent this diseases vaccinate and enjoy your trip

메리트카지노 said...

Looking at this article, I miss the time when I didn't wear a mask. 메리트카지노 Hopefully this corona will end soon. My blog is a blog that mainly posts pictures of daily life before Corona and landscapes at that time. If you want to remember that time again, please visit us.


Tamil novels said...

Very informative post. Thank you for sharing with us.
Tamil novels pdf download
Ramanichandran novels PDF
srikala novels PDF
Mallika manivannan novels PDF
muthulakshmi raghavan novels PDF
Infaa Alocious Novels PDF
N Seethalakshmi Novels PDF
Sashi Murali Tamil Novels PDF

apply for Indian visa said...

Thanks for sharing excellent information. Keep sharing such useful information.. To apply for Indian visa, the applicant just needs his/her valid passport, debit or credit card and an email address. Once approved, the electronic visa to India is sent to the applicant's email. To travel to India, the applicant must print a copy of his e-Visa to take with him during his stay in the country.

Indian 30 Days Tourist eVisa from USA said...

What an outstanding post! “I'll be back” (to read more of your content). Thanks…Indian 30 Days Tourist eVisa from USA or eTV for India is an online travel authorization. USA citizens whose sole purpose of visiting India is for leisure, sightseeing, religious work or casual travel to visit their friends or relatives can apply for an Indian 30 days tourist visa through the online India visa application system.

Jack allison said...

This is such worthwhile material. You are saying very nice words. I feel very happy to read this. I suggest people must read it once. It is really helpful on how to apply for an India business visa for foreigners who wish to come to India for business meetings, startup, seminar, sale/purchase etc.

FIFA said...

온라인카지노사이트 Woah! I'm really enjoying the template/theme of this
blog. It's simple, yet effective. A lot of times it's difficult to get that "perfect balance" between user friendliness and appearance.
I must say you have done a awesome job with this.
In addition, the blog loads extremely fast for me on Internet
explorer. Outstanding Blog!

FIFA said...

스포츠토토티비 I constantly emailed this web site post page to all my friends, for the reason that if like to read it after that my friends will too.

japanyadongcom said...

Greetings! Very useful advice within this article! It’s the little changes which will make the largest changes. Thanks for sharing! 국산야동

Please visit once. I leave my blog address below
야설
국산야동

chinayadongnet said...

You're so interesting! I don’t think I've truly read through a single thing like this before. So wonderful to discover another person with genuine thoughts on this subject. Seriously. 중국야동넷

Please visit once. I leave my blog address below
야설
중국야동넷

Indian visa said...

Wow! This blog is very nice. Now foreign travelers from over 160 nations can apply for Indian visa online.

India e business visa said...

This is a very useful article. India e business visa, You can read all requirement info related to business invitation letter for Indian visa via India visa website.

Robert smith said...

Information that is useful and appealing. This blog is really rocking... Yes, I like the post very much. Indian visa for United Kingdom citizens, apply India regular visa from United Kingdom online via India visa website within 5minutes you can fill your visa form.

CasinoMecca said...

CasinoMecca

Noah Ava said...

I am sure this article has impressed all internet users, it is a really great article.. You can come to India but you will need a visa. You can apply online visa for India. You can read all the info about Indian visas via our website.

henry milton said...

Hello friends, Many people ask, How can I apply for a Visa? You can apply for e visa online. And your visa processing time depends on your nationality and your visa type.

places to visit in Turkey other than Istanbul said...

The best places to visit in Turkey other than Istanbul. One such place is Cappadocia, renowned for its surreal rock formations and cave dwellings. Travelers can enjoy hot air balloon rides, explore ancient underground cities, and hike through breathtaking valleys. Pamukkale is another must-visit destination, featuring stunning terraces of mineral-rich thermal waters.

henryisabella said...

You must submit an India visa application Kenya, if you are an Indian national planning a trip there. There are a few crucial phases in the application procedure for an Indian visa Kenya. Applying far enough in advance to give enough time for processing is advised.

Mark Wood said...

We would like to extend our sincere appreciation for your invaluable contribution, which has greatly enhanced the overall experience for everyone involved. Singapore, transit passengers, free tour, Changi Airport, restarts, 2 years. After a two-year hiatus, Singapore has recently resumed its free tour programme for transit travelers at Changi Airport. Through this programme, travelers who have a stopover in Singapore may benefit from a free city tour that gives them an overview of the sights and culture of the city. By encouraging travelers to explore Singapore during their layover and make the most of their time at the airport, the project hopes to improve the transit experience.

Rupesh kumar said...

Thank you for sharing such kind of precious information with us.It really useful for many of them like me. Ziyyara Edutech offers comprehensive online tuition for CBSE board students, ensuring academic excellence from the comfort of home.
For more info contact +91-9654271931 or visit Online tuition for cbse board

Ethiopia e Visa for Switzerland Citizens said...

Hello! Thanks for this useful article, expecting this text related to this taking into account once more. Ethiopia e Visa for Switzerland Citizens, explore Ethiopia hassle-free with an e-Visa! Streamlined online application process for your convenience. Embark on an unforgettable Ethiopian adventure today.

Farhan Zaidi said...

The given information was excellent and useful. This is one of the excellent blog, I have come across. Do share more. Explore our curated list of high-authority Article Submission Sites.
Visit for Site list Article Submission Sites list