Friday, June 10, 2011

Explaining – not setting – Bitcoin straight

Okay, I had some spare time last night, so I figured I’d sit down and write up an explanation of some of Bitcoin’s workings. The chief problem in explaining this to the layman is that, as a prerequisite, you need to understand the basics of public key cryptography (aka asymmetric cryptography), which, for the average person, is quite a tall order in itself. But since I’m the master at this kind of thing, here’s how I would put it:

First, to get something out of the way: nothing in Bitcoin is actually encrypted. Rather, it works, and works robustly, without centralization, specifically because all transactions are visible. The privacy comes in how the entities trading the coins are referred to in this transaction database, purely by their Bitcoin address (a string of numbers and letters, like 1mVQtx6rn…), which is like one of those supposed Swiss bank accounts you hear about that are only known by a number. (So yes, if you publicly and believably reveal that, "Hey, I own address 152zpfu5b20gh29...!", then people can see what you do via the address 152zpfu...) So rather than anonymous, Bitcoin is best described as pseudonymous (sue-DONN-i-MUS).

The reason that you need to know the basics of public key cryptography, rather, is that a lot of its "primitives" (building blocks) are used in Bitcoin, and the protocols used are heavily studied by professional cryptographers.

First primitive: public key-based digital signatures

How do you accomplish signatures in a digital world, where anyone can put any data on any storage medium? Like a physical signature, a digital one needs to meet the following characteristics:

A) Proof of identity: only you can produce your signature, so seeing your signature is proof that you endorse what you signed.
B) Non-repudiation: after giving your signature, you can't plausibly deny having signed it.
C) Non-transferability: your signature on Document1 can't be "moved" to a different Document2, implying your endorsement of the latter

Quite surprisingly, you can accomplish these goals with a kind of signature in the digital world. Here's the trick: you generate a keypair -- a "public key" and a corresponding "private key". You keep the private key secret, and tell everyone in the world your public key. You then use a "public key algorithm" (PKA) that takes as an input:

1) the message, M1, that you want to sign
2) your private key, SK1

and outputs a signature, SIG1. PKAs are designed so that computing this algorithm and generating this signature is quick and easy.

Then, if someone wants to verify that you really did sign message M1, they just verify that a certain mathematical relationship (corresponding to the particular PKA used) holds among your public key (which, remember, they know), your message M1, and your signature SIG1. Again, this process is designed to be quick and easy for the verifier.

So, how does this provide the desired qualities A through C above? A and B are satisfied by the fact that it is extremely difficult and time-consuming to produce SIG1 *unless* you know the private key SK1. (Inferring the private key from the public key is likewise too time-consuming to be finished anytime in the next few centuries.) So, the fact that you were able to (quickly) compute SIG1 is proof that you hold the private key corresponding to the public key, AND that (with a few caveats) you chose to use that key to generate the signature for M1.

This protocol satisfies criterion C (non-transferability) because, as you recall, SIG1 is partly a function of the message itself. This means that your signature will be different for each message you could conceivably want to sign. So someone can't take SIG1 and cite it as proof that you signed a different message M2 -- because the protocol's specified mathematical relationship will *not* hold for {M2, SIG1, public key} -- it will only hold for {M1, SIG1, Bob's public key}. To "forge" a signature, they would need to produce {M2, SIG2, Bob's public key}. But like I said above, it's way too hard for them to figure out what SIG2 would be unless they know your private key.

I'm deliberately leaving off the specific algorithms used for such systems so that this does not become unbearably long. Suffice to say, there are algorithms that accomplish this, and they mainly rely on modular arithmetic and prime numbers. I will only add that the class of function needed to produce such a PKA is known as a "trapdoor one-way function". That is any function f(x) such that:

- Given x, it's easy to compute f(x).
- Given a value V equal to f(x) for some unknown x, it's hard to find an x such that f(x) = V. (i.e., it's hard to invert f)
- But, if you know a specific piece of information particular to f, called the "trapdoor knowledge" (in the exposition above, this is the part played by the private key), it is *easy* to invert f

What role do public key signatures play in Bitcoin? They are used to prove to the network that the owner of address A1 (A1 also functioning as a public key!) really did authorize the transfer of certain coins to the next address. Other nodes in the network, in turn, are able to easily verify that the owner of A1 signed off on the transfer by checking that the mathematical relationship I mentioned above holds among the A1 public key, the message indicating the transfer, and the signature on the transfer. And if this relationship doesn't hold, the other nodes (per the Bitcoin protocol) ignore the purported transfer, acting like it didn't exist, and refuse to tell other nodes about it.

Second primitive: (cryptographically secure) hash functions

A hash function (in cryptography) is a function that takes an input of any length, and deterministically computes a fixed-length output based on it, such that the relationship between input and output "seems random", and there's no quicker way to compute the output, or otherwise learn *anything *about what the output will look like, than to churn through the hash function itself. I will make this make a bit more sense. For simplicity, call the input to a hash function its "preimage", and the output of a hash function its "digest" (the output is also referred to as the checksum or the [digital] fingerprint).

An example of a (weak) hash function most people are familiar with is the kids' game where you find out your "Star Wars" name or your "stage name” by doing something like, "Take the first syllable of the street where you grew up, and add on the last syllable of your middle name, plus the first syllable of where you were born." This name is a hash of all that data about yourself.

However, cryptographically-secure hash functions have to meet more stringent requirements. Like I said above, it must be really hard to make inferences about the relationships between classes of input and classes of outputs without actually grinding through the function for each input in the class. So, for example, you can't have a hash function where "small changes in the input (preimage) lead to small changes in the output (digest)". Rather, they are designed so that a tiny change in the preimage will *significantly *change the digest. More formally, cryptographically secure hash functions must meet the following characteristics:

- Given a digest, it's hard to find a preimage that hashes to that digest. This is called "[first] preimage resistance". (Note: because preimages can be any length and the hash length is fixed, there are an infinite number of preimages that hash to any given digest.)

- Given a preimage, it's hard to find another preimage that hashes to the same digest. This is called "second preimage resistance".

- It's generally hard to find *any* preimages (given or not), that hash to the same digest. Such instances are known as "collisions", and this trait is called, obviously, “collision resistance”.

(Exercise for the reader: how the Star Wars name game described above fail all of these?)

The function of hashes: in everyday data security, they serve the function of obscuring data in a way that limits its malicious uses. For example, websites don't actually store your password (if they know anything about security whatsoever). Rather, they store a *hash* of your password. That way, they can still verify you by password (Check: does the hash of the password given match the hash we have on record?), but if someone breaks into their database, all they get are the hashes. Because the hash function has first preimage resistance
(see above), the list is much less useful to the attacker because they have to accomplish the difficult task of finding preimages for the hashes they found.

Hashes are where the "miners" come into play: initial bitcoins are generated and allocated (and still are) based on who can solve a mathematical problem. That problem is similar to the one of breaking a hash function's (first) preimage resistance. But rather than having to find a preimage with a *specific* digest, the problem is to find a preimage whose hash is a *partial* match (for some specific number of digits) with a target digest string. So, it's like an easier version of breaking preimage resistance, though still requiring the ability to do lots of (parallel) calculations – because there is, by design, no shortcut to solving this but to try as many preimages as you can.

Anyway, that's about all for now, something for you to chew on and get some understanding of the whole thing. There’s still a lot left, but that should cover the pre-requisites.

58 comments:

Ruth said...

good explanation- thanks

Ruth said...

good explanation, thanks

Anonymous said...

This is good stuff. Bookmarked and I'll be spreading it around.

Anonymous said...

You mentioned ineverting the crypto function, but what would that accomplish? M1 and PublicKey are already known to everyone. If you have the private key, there is no reason to invert the function since you already know all its variables. Isn't inverting the function difficult no matter if you know the private key or not?

Silas Barta said...

@Latest anonymous: Good catch. I was simplifying a bit there. The purpose of mentioning trapdoor one-way functions was only to refer the reader to the relevant mathematical concept needed to develop public key cryptographic protocols. The actual mapping between trapdoor one-way functions and authentication (signing) is more complicated, and I didn't describe it.

However, the relationship to encryption (rather than signing) is simpler, as you noticed:

x is the text you want to encrypt;
f(x) is the encrypted text;
the trapdoor knowledge is the private key;
the function class to which f belongs is the encryption protocol;
and the public key specifies which specific instances of that class you're using to encrypt.

Since there's a duality/complementarity between authentication and encryption, then primitives (such as trapdoor one-way functions) that are useful for the former will also be useful for the other. (I don't know the mapping offhand though.)

Perhaps I'll go over this in more detail in follow-ups. Good question.

Boxo said...

I was confused by the mention of trapdoor functions, as I couldn't see how you could get from them to signing. But I think I've got it now.

Alice wants to sign message M. Let f be a trapdoor function. Let h be a hash function. Notice that one needs Alice's public key to compute for some x, f(x); and Alice's private key to compute for some y, the x for which f(x)=y. Alice uses her private key to compute the x such that f(x)=h(M). Now x is the signature. Hence Alice sends out M and x. If Bob wants to verify that M is Alice's message, knowing only M, Alice's public key, and x, he computes h(M) and compares it with f(x). If they're equal, it has to be Alice's message.

Am I right?

Silas Barta said...

That's exactly right, Boxo. If you duduced that out yourself rather than learning it from a crypto guide, I'd say your brain was "designed" for cryptography, and the rest will be a walk in the park for you!

I have a post coming up that elaborates on cryptographic protocol, btw.

Silas Barta said...

Looking back, Boxo, it seems I could have added that explanation of the "mathematical relationship" a signature must meet and which can be verified, and without adding much length or difficult to my text. (Then again, I wasn't sure of the exact mapping from trapdoor OWFs to public key signing at the time...)

Rewriting upcoming post...

Anonymous said...

hi

electronic signature software said...

Its really nice and informative to read about Bitcoin’s workings.As you said that to understand this we need to know about basics of public key cryptography.It means that public key cryptography is needed for its working?It seems like that.

Anonymous said...

I am building a bitcoin library with C language.Can any one give me the best cryptography algorithm ???

thomblake said...

Excellently done.

bitjack21.com said...

I would like to thank you for the efforts you have put in writing this blog. I’m hoping
the same high-grade web site post from you in the future also. Actually your
creative writing abilities has encouraged me to get my own web site going now.
Really blogging is spreading its wings and growing fast. Your write up is a great example.

Unknown said...

Bitcoin has almost become a household name with ever increasing coverage in the media, and fair to say its notoriety continues to increase and where to spend bitcoin

Unknown said...

Thank you for the helpful information. I also think that exkash.com is a good website, it has very helpful information for Bitcoin to bank transfer news, bitcoin exchange, foreign exchange brokers, buying bitcoins, etc.
Bitcoin to Bank|| Bitcoin

Blogger said...

If you are searching for the #1 Bitcoin ad network, take a look at MellowAds.

Blogger said...

Did you consider exchanging with the best Bitcoin exchange company: YoBit.

Unknown said...

Bitcoin has been popular in Japan for quite some time. A lot of Japanese companies are now paying salaries in Bitcoin. And now, as of January 2018, Yamada Denki, one of the biggest consumer electronics chains in Japan, announced that it is going to start accepting bitcoin payments at two of its largest stores in Tokyo.

While the payment method is still in trial, the option is going to go nationwide once everything is going smoothly with the trial. The company said:

“We will implement initiatives to improve bitcoin recognition and usage promotion. With the introduction of bitcoin payment service, we respond to the diverse needs of our customers both in Japan and overseas. We believe that we can provide improved service and convenience.”

Here

gautham said...

Advantages of hash search are
hash provides a more reliable and flexible method of data
it is generally faster than any searching arrays and lists. learn more in bitcoin course

gautham said...


In business intelligence cognos tool is reporting tool for making reports Cognos tm1 online training india

gautham said...

Very nice explanation big data hadoop training

gautham said...

I successfully completed the post in reading a wonderful post ui online training hyderabad

svrtechnologies said...

Whatever we gathered information from the blogs, we should implement that in practically cognos training then only we can understand that exact thing clearly, but it’s no need to do it, because you have explained the concepts very well. It was crystal clear, keep sharing..

Arslan Saleem said...

Very interesting blog. A lot of blogs I see these days don't really provide anything that I'm interested in, but I'm most definitely interested in this one. Just thought that I would post and let you know. askari credit card | bank alfalah car loan

Jason Miler said...

Crypto robots are instruments utilized by traders to remove anxieties and also emotions from their trading. These bots will certainly allow you to run techniques usually offered in hedge funds. A Crypto Auto bitcoin bot essentially is a software that immediately evaluates market data as well as makes trading operations based on indicators developed with these data.

Jason Miler said...

NapBots offers mathematical crypto trading crawlers that are powered by AI as well as artificial intelligence engines. It focuses on brief, medium or long-term perspectives. This method allows us to lessen functional threats as well as to attain an extremely robust backtests with minimal drawdowns. Crypto bot

SEO Service said...

I enjoy every one of the posts, I must say i adored, I want more details with this, mainly because it is rather excellent., Thanks pertaining to speaking about. satta king

ROFF ROFF 7 said...

Bruc Bond endeavor to lead the financial sector with sustainability, customizable product offering, and open communication. At Bruc Bond we aim to make 21st century banking straightforward, simple, and transparent.

ROFF ROFF 7 said...
This comment has been removed by the author.
jamuna said...

Innovative blog thanks for sharing this inforamation.
Blockchain Training in Chennai
Blockchain courses in Chennai
french classes
spoken english centre in chennai
German language training in chennai
TOEFL Coaching Centres in Chennai
Ionic Training in Chennai
ielts best coaching in chennai
spanish language in chennai 
content writing course in chennai
Blockchain Training in Tambaram
Blockchain Training in Adyar

Online training portal said...


That is nice article from you , this is informative stuff . Hope more articles from you . I also want to share some information about cognos analytics 11 and sap abap training videos

sushmi reddy said...

I like this one...more helpful information provided here.I am quite sure I will learn much new stuff right here! Good luck for the next!
Oracle Training | Online Course | Certification in chennai | Oracle Training | Online Course | Certification in bangalore | Oracle Training | Online Course | Certification in hyderabad | Oracle Training | Online Course | Certification in pune | Oracle Training | Online Course | Certification in coimbatore

Devi said...

8)GREAT topic! It is really interesting to read from the beginning & I would like to share your blog to my circles, keep sharing…. oracle training in chennai

Satta King said...

Your work is very good and I appreciate you and hopping for some more informative posts. Security License Ontario

Pankaj Singh said...

Thank you so much for sharing your brilliant thoughts with us. Visit Ogen Infosystem for creative Website Designing and SEO Services in Delhi, India.
Top 5 Website Designing Company in India

Unknown said...

visit here
iso certification in delhi
CE Certification in Delhi
iso certification in gurgaon
iso certification in faridabad

Unknown said...

visit
Freight Forwarder in Vietnam
Shipping Company In India

arshiya said...

Excellent article for the people who need information about this course.
machine learning vs ai
features of react js
amazon services list
why to use angularjs
aws interview questions and answers for experienced pdf

stevencombs said...

Personally I think overjoyed I discovered the blogs.
bitcoin trading platform

Saurav said...

Super site! I am Loving it!! Will return once more, I’m taking your food additionally, Thanks. Oregon Business Registry

Pathway for German Language said...
This comment has been removed by the author.
Vietnam Airline said...

Đặt mua vé tại Aivivu, tham khảo

mua ve may bay di my

săn vé tết 2021

giá vé máy bay eva đi canada

vé máy bay đi Pháp giá rẻ

vé máy bay đi Anh quốc

mua vé máy bay giá rẻ

combo du lịch đà nẵng hội an

combo nha trang tháng 7

Unknown said...

Thank you for the helpful information. I also think that exkash.com is a good website,
angular js Training in bangalore

angular js Training in hyderabad

angular js course in bangalore

angular js course in hyderabad


Anonymous said...

Very nice article. I enjoyed reading your post. very nice share. I want to twit this to my followers. Thanks !. bitcoin casinos

jhansi said...

Hadoop is an open-source software framework for storing data and running applications on clusters of commodity hardware. It provides massive storage for any kind of data, enormous processing power and the ability to handle virtually limitless concurrent tasks or jobs.
tally training in chennai

hadoop training in chennai

sap training in chennai

oracle training in chennai

angular js training in chennai

jhansi said...

Really, this article is truly one of the best, information shared was valuable and resourceful Very good work thank you.
tally training in chennai

hadoop training in chennai

sap training in chennai

oracle training in chennai

angular js training in chennai

Anonymous said...

I am hoping the same best effort from you in the future as well. In fact your creative writing skills has inspired me. koers bitcoin

siva said...

I like to read your blog, this bog is valuable to us.
applications of python
ccna training
php vs python
scope of machine learning
data science interview questions and answers
data science interview questions and answers

meritstep Technology said...

Meritstep is the Top & Best Software & IT Training Institute for Workday Online Training Course & Learning Organizations India, USA, UK. Enroll Now for Workday Online Training Classes.

meritstep Technology said...

Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
workday online training

Unknown said...

This is an excellent post I seen thanks to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post.
토토사이트

Anonymous said...

It should be noted that whilst ordering papers for sale at paper writing service, you can get unkind attitude. In case you feel that the bureau is trying to cheat you, don't buy term paper from it. обмен биткоин на сбербанк

Screen Mirror App said...

Did you know that you can easily view the contents of your phone on your TV without a cable? With a screen mirror app you can easily do the screen mirroring from Android to TV. Check out www.screenmirroring.me to find out more.

Daily Satta King said...

Thanks for your marvelous posting! I really enjoyed reading it, you happen to be a great author. I will remember to bookmark your blog and may come back in the foreseeable future.

Read More:-

Satta King

Satta king

tarin said...

I truly like you're composing style, incredible data, thankyou for posting. 먹튀검증

Unknown said...

This website and I conceive this internet site is really informative ! Keep on putting up! 토토사이트 추천

Unknown said...

A round of applause for your article.Much thanks again. Really Cool 먹튀검증

tarin said...

The web site is lovingly serviced and saved as much as date. So it should be, thanks for sharing this with us. 토토사이트