I know the line: explaining a joke is like dissecting a frog; you understand it better, but it dies. Still, not everyone will get these, and I figure I might as well have a place where you at least get a chance. So here are some of my own creations, explained.
Girl, you make me feel like a fraudulent prover in a stochastic interactive zero-knowledge proof protocol ... because I really wish I had access to your random private bits!
Explanation: In a stochastic zero-knowledge proof protocol, there is a prover and a verifier, where the former wants to convince the latter of something. But for proof to work, the verifier must give the prover unpredictable challenges. Think of it like a quiz in school -- it's not much of a quiz if you know the exact questions that will be on it.
The information to predict the challenges is known as the verifier's private random bits Those with a legit proof don't need this, but a fraudulent prover does. Thus, a fraudulent prover in a stochastic interactive zero-knolwedge proof protocol wants access to the verifier's "random private bits".
A historian, a geologist, and a cryptographer are searching for buried treasure. The historian brings expertise on practices used by treasure hiders, the geologist brings expertise on ideal digging places, and the cryptographer brings expertise on hidden messages.
Shortly after they start working together, the cryptographer announces, "I've found it!!"
The others are delighted: 'Where is it?'
The cryptographer says, "It's underground."
'Okay, but where underground?'
"It's somewhere underground!"
'But where specifically?'
"I don't know, but I know it's underground!"
'Slow down there. If all you know is that it's underground, then in what sense did you "find" anything? We're scarcely better off than when we started!'
"Give me a break! I just gave you an efficiently-computable distinguishing attack that separates the location of the treasure from the output of a random oracle. What more could you want?"
Explanation: In cryptography, an encryption scheme is considered broken if an attacker can find some pattern to the encrypted message -- i.e. they can identify telltale signs that it wasn't generated by a perfect random number generator, a "random oracle". Such a flaw would be called a "distinguishing attack". So in the cryptography world, they don't care if the attack actually allows you to decrypt the message; they stop as soon as they find non-randomness to the encrypted data. Applied to a treasure hunt, this means they would give up as soon as they conclude that the treasure location is non-random, which the cryptographer here things s/he's done simply by concluding that it's "underground".
So, 16-year-old Johnnie walked into an Amazon Web Services-run bar...
"Welcome," said the bartender. "What are you drinking?"
Johnnie replied, 'What've you got?'
"Well, we have a selection of wines and the beers you see right here on tap. But if you prefer, we also have club soda and some juices."
Johnnie thought, Wait a second. Why is he telling me about the wines and beers? Does he even realize ... ?
'Okay, I'll take the Guinness.'
"Bottle or draft?"
'Draft.'
"Alright, and how will you be paying?"
Johnnie only had large bills from his summer job and gave the bartender a C-note.
"Sorry, but I gotta check to make sure this is real." The bartender took out a pen and marked it, then counted out the change. Johnnie reached for the beer.
"Hold on a second! Make sure to use a coaster!" The bartender slipped one under the glass. "Okay, now enjoy!"
Johnnie lifted up the glass to drink. Before he was able to sip, the bartender swatted it out of his hand.
"WHAT ARE YOU THINKING!?! Don't you know 16-year-olds can't drink!"
Explanation: On the AWS site, they will gladly let you click on the "Launch server" button and go through numerous screens and last-minute checks to configure it, and only at the very last stage does it say, "oops, turns out you don't have permission to do that" -- so it's like a bartender that takes you through a entire transaction, even verifying irrelevant things (like whether the money is real), while knowing the whole time he can't sell to you.
How is a Mongo replica set like an Iowa voter?
In primary elections, they only vote for candidates they think are electable!
Explanation: Databases can have "replica sets" where there are multiple servers that try to have the same data; secondary servers depend on an agreed-upon "primary" to be the "real" source of data. Often times, the primary server goes down, so they have to decide on a new primary, known as a "primary election". But there are some restrictions on who they will vote for -- if they e.g. have reason to believe that a server can't be seen by other members, and in those cases it will regard that server as unelectable. So you can get funny messages about "server42 won't vote for server45 in primary election because it doesn't think it's electable".
A blog by Silas Barta
Showing posts with label cryptography. Show all posts
Showing posts with label cryptography. Show all posts
Saturday, February 27, 2016
Thursday, July 11, 2013
My discovery of "semantic security"
One interesting thing I forgot to mention in the previous post about homomorphic encryption: the concept of semantic security.
It was actually a major stumbling block for me. When I got to the passage that mentions the concept, the author casually remarks that "semantic security is an expected feature of public key cryptosystems", and then defines the term as follows: a system is semantically secure if, given two plaintexts and the ciphertext of one of them, an attacker cannot do better than chance in guessing which plaintext goes with that ciphertext.
That didn't make sense because I had always assumed that the defining feature of public key cryptography was that the attacker is permitted unlimited chosen-plaintext attacks, which -- I thought -- means that the attacker always gets to know what ciphertext goes with any plaintext. So how can you make it so that the attacker can -- as required for public key encryption -- produce valid ciphertexts from arbitrary plaintext, and yet still have a semantically secure cryptosystem? Couldn't the attacker just encrypt both plaintexts to figure out which one corresponds to the given ciphertext?
What I missed was that you can use a one-to-many cipher: that is, the same plaintext corresponds to many ciphertexts. What's more, it's actually trivial to convert a plain-vanilla one-to-one public key cipher into a one-to-many semantically secure version. Here's how: just before applying the encryption step, generate a random number (a "nonce") and append it to the plaintext, with the proviso that the recipient with look for it in that position and strip it off after decryption.
This way, in order for an attacker to try to guess the plaintext in the game above, it's no longer enough for them to simply encrypt both plaintexts: a random number was inserted in the process. This means that in order to find a match between a plaintext and a ciphertext, the attacker must encrypt each plaintext with every possible nonce, which requires resources that increase exponentially with the size of the nonce used. (That is, an n-bit nonce can have 2^n possible values.)
The more you know (tm).
It was actually a major stumbling block for me. When I got to the passage that mentions the concept, the author casually remarks that "semantic security is an expected feature of public key cryptosystems", and then defines the term as follows: a system is semantically secure if, given two plaintexts and the ciphertext of one of them, an attacker cannot do better than chance in guessing which plaintext goes with that ciphertext.
That didn't make sense because I had always assumed that the defining feature of public key cryptography was that the attacker is permitted unlimited chosen-plaintext attacks, which -- I thought -- means that the attacker always gets to know what ciphertext goes with any plaintext. So how can you make it so that the attacker can -- as required for public key encryption -- produce valid ciphertexts from arbitrary plaintext, and yet still have a semantically secure cryptosystem? Couldn't the attacker just encrypt both plaintexts to figure out which one corresponds to the given ciphertext?
What I missed was that you can use a one-to-many cipher: that is, the same plaintext corresponds to many ciphertexts. What's more, it's actually trivial to convert a plain-vanilla one-to-one public key cipher into a one-to-many semantically secure version. Here's how: just before applying the encryption step, generate a random number (a "nonce") and append it to the plaintext, with the proviso that the recipient with look for it in that position and strip it off after decryption.
This way, in order for an attacker to try to guess the plaintext in the game above, it's no longer enough for them to simply encrypt both plaintexts: a random number was inserted in the process. This means that in order to find a match between a plaintext and a ciphertext, the attacker must encrypt each plaintext with every possible nonce, which requires resources that increase exponentially with the size of the nonce used. (That is, an n-bit nonce can have 2^n possible values.)
The more you know (tm).
Friday, May 24, 2013
"I added your numbers, and I have no idea what they are."
So it turns out there's a thesis arguing that polynomial-time, fully homomorphic encryption is possible. (Link is to the dumbed-down -- but still journal-published -- version that mortals like me are capable of understanding.)
It's hard to understate the significance of this. This means that it's possible for you to give someone your data in encrypted form, and for them to execute arbitrary operations and give it back to you, without ever knowing what the data is. That is, they transform an input ciphertext to and output ciphertext such that when you decrypt the output, you have the answer to your query about the data, but at no point did they decrypt it or learn what was inside.
In other words: "I just calculated the sum of the numbers you gave me, but I have no idea what the sum is, nor what any of the numbers are."
If it sounds impossible, it's not because you misunderstand it, but because that kind of thing shouldn't be possible -- how can you perform arbitrary operations on data without learning something about it? Sure, maybe there are edge cases, but a rich, Turing-complete set?
It would mean that "the cloud" can ensure your privacy, while *also* doing useful operations on your data (as the author, Craig Gentry, goes at great length to emphasize).
As best I can tell from the paper, here's the trick, and the intuition why it's possible:
1) The computation must be non-deterministic -- i.e. many encrypted outputs correspond to the correct decrypted output. This is the key part that keeps the computation provider from learning about the data.
2) The output must be fixed size, so you have a sort of built-in restriction of "limit to the first n bytes of the answer".
3) It does require a blowup in the computational resources expended to get the answer. However, as noted above, it's only a polynomial blowup. And thanks to comparative advantage, it can still make sense to offload the computation to someone else, for much the same reason that it makes sense for surgeons to hire secretaries even when the surgeon can do every secretarial task faster. (Generally, when the provider's opportunity cost of performing the task is less than yours.)
4) Finally, to be fully homomorphic -- capable of doing every computation, not just a restricted set of additions and such -- the encrypted computation has to find a way around the buildup of "noise" in the computation, i.e. properties of the output that put it outside the range of what can be decrypted (due to exceeding the modulus of the operation needed to extract the output). And to do that, in turn, its operation set must be sufficient to perform its own decryption.
I'm only about halfway through the paper, but it's been really enlightening to get the intuition behind why this kind of thing can work.
It's hard to understate the significance of this. This means that it's possible for you to give someone your data in encrypted form, and for them to execute arbitrary operations and give it back to you, without ever knowing what the data is. That is, they transform an input ciphertext to and output ciphertext such that when you decrypt the output, you have the answer to your query about the data, but at no point did they decrypt it or learn what was inside.
In other words: "I just calculated the sum of the numbers you gave me, but I have no idea what the sum is, nor what any of the numbers are."
If it sounds impossible, it's not because you misunderstand it, but because that kind of thing shouldn't be possible -- how can you perform arbitrary operations on data without learning something about it? Sure, maybe there are edge cases, but a rich, Turing-complete set?
It would mean that "the cloud" can ensure your privacy, while *also* doing useful operations on your data (as the author, Craig Gentry, goes at great length to emphasize).
As best I can tell from the paper, here's the trick, and the intuition why it's possible:
1) The computation must be non-deterministic -- i.e. many encrypted outputs correspond to the correct decrypted output. This is the key part that keeps the computation provider from learning about the data.
2) The output must be fixed size, so you have a sort of built-in restriction of "limit to the first n bytes of the answer".
3) It does require a blowup in the computational resources expended to get the answer. However, as noted above, it's only a polynomial blowup. And thanks to comparative advantage, it can still make sense to offload the computation to someone else, for much the same reason that it makes sense for surgeons to hire secretaries even when the surgeon can do every secretarial task faster. (Generally, when the provider's opportunity cost of performing the task is less than yours.)
4) Finally, to be fully homomorphic -- capable of doing every computation, not just a restricted set of additions and such -- the encrypted computation has to find a way around the buildup of "noise" in the computation, i.e. properties of the output that put it outside the range of what can be decrypted (due to exceeding the modulus of the operation needed to extract the output). And to do that, in turn, its operation set must be sufficient to perform its own decryption.
I'm only about halfway through the paper, but it's been really enlightening to get the intuition behind why this kind of thing can work.
Monday, April 15, 2013
Our latest work on Bitcoin
Bob Murphy and I have collaborated on an attempt to explain Bitcoin -- and its economic implications -- for the masses.
For the three of you still following this blog, check out the link.
For the three of you still following this blog, check out the link.
Saturday, November 12, 2011
Another explanation of hash functions
I think I've found a new way to explain hash functions and convey the intuition behind them.
First, think back to the classic problem from grade school: a farmer raises cows and chickens. His animals have a total of, say, 10 heads and 22 feet. How many cows and chickens does he have?
If you know algebra, you probably laugh at how easy the problem is, though it's still interesting for kids, who generally have fun with it. Now, you can either solve it the kid way, or the algebraic way. The kid way is to "guess and check": that is, guess a number of chickens and of cows, find the corresponding number of heads and feet, and check if it matches that given in the problem. The algebraic way is to let x be the number of chickens, y the number of cows, and write:
x + y = 10
2x + 4y = 22
And then solve for x and y the standard way. (In case it needs to be said, chickens have one head and two feet while cows have one head and four feet.)
What does this all have to do with hash functions, though? Glad you asked.
A cryptographic hash function for 10,000 BC
Recall the requirements for a cryptographic hash function: it must be easy to compute the output (digest) for any input (preimage), but hard to compute the input for any output (other than by trying every preimage). In other words, a one-way function (or trapdoor one-way function without the trapdoor).
So, here's a hash function for a mathematically backward world: First, it takes two integers as input. You let the first be number of chickens, and the second be the number of cows. Then, output the total number of heads and feet (perhaps with a simple separator, like "10:22" for the above example).
It works as a hash function for the people of 10,000 BC precisely because of their (relatively) poor mathematical understanding. Since they don't know to express it as a system of linear equations, or otherwise derive a simple general solution, someone trying to "crack" a given hash digest (output) would have no choice but to guess and check a bunch of chicken/cow possibilities. This method is referred to as "brute force" in cryptography, and as long as a hash function hasn't yet been "broken" (by a better understanding of the math theory involved), it's the only option available.
Though this situation may seem contrived to us now, the same dynamic is at play in modern, military grade cryptographic hash functions: so long as people lack sufficient mathematical understanding, it is impossible to invert a hash digest except by brute force. The only difference between now and then is that the math and computations are harder.
In the previous post, I mentioned how hash functions can be used to protect stored passwords while still allowing password-based authentication. Let's go over how this would work.
An encrypted password system for 10,000 BC
Let's say Mike the Merchant wants to set up a service of warehousing people's valuables. He'll deal with many customers and doesn't want to count on remembering their faces when they come to reclaim their stuff. So, he'll give each customer a unique password they must use to get in. This will be a stronger authentication system than just trying to remember every customer.
Like modern website owners, Mike also wants to keep his password records from being stolen or misused (say, to steal his customers' stuff). If he simply kept the passwords in a book, someone who gained access to it could copy them and then come one by one to illicitly claim the goods in the warehouse. (Though of course, Mike can always use common sense security measures, like noticing something is fishy when the same customer one day claims to know all the passwords!)
So, rather than store the passwords, he converts them into two integers (if the password isn't already in that form) and stores the digest from putting them through the hash function described above. So, if Harry the Hoarder's password were 100:350, Mike would store Harry's password as 450:1600. (That is, interpret the number before the colon in the password as chickens and the latter as cows, and then store the number of heads [100 + 350 = 450] and number of feet [2*100 + 4*350 = 1600], separated by a colon.)
Then, when someone comes in claiming to be Harry, Mike asks for the password. Next, instead of comparing Harry's password (100:350) to an entry in his book, he first computes the hash digest (450:1600), and compares that number with his entry for Harry. So, he still has a working system to authenticate people by password.
What protection does this offer Mike if someone gains access to his password book and copies the entries? Well, remember, like with modern systems, all they get are the digests that result from putting the passwords through the hash function, not the passwords themselves. And knowing a digest won't convince Mike that you're the account holder: remember, he's checking for a pair of numbers that hash to your entry, not the entry itself.
Could the attacker infer the passwords from the digests listed in Mike's book? Yes, but it would take infeasibly long to do so -- that's the role of the hash function. Going from cows/chickens to heads/feet is easy, but going the other way is hard (for a mathematically backward society, at least). To make any use out of Mike's hashed-password book, an attacker would have to guess a huge number of passwords and see if their digests match any in the book. As long as the password space is big enough, and the society remains mathematically backward enough, it's just not feasible for an attacker to guess and check enough passwords to find a match in the book.
And like in the previous section, this is the same position we are in with respect to hashed password storage today: with a good enough mathematical breakthrough, it might become feasible to quickly invert a hashed password, but as it stands now, the hash functions used are enough to render such databases useless to attackers (though obviously some attacks still get through, such as when a website continues to use a long-broken hash function). The only difference is the complexity of the math.
Of course, Mike still has to make sure his customers don't give out their passwords or store them insecurely ... a problem we still grapple with, twelve thousand years later.
First, think back to the classic problem from grade school: a farmer raises cows and chickens. His animals have a total of, say, 10 heads and 22 feet. How many cows and chickens does he have?
If you know algebra, you probably laugh at how easy the problem is, though it's still interesting for kids, who generally have fun with it. Now, you can either solve it the kid way, or the algebraic way. The kid way is to "guess and check": that is, guess a number of chickens and of cows, find the corresponding number of heads and feet, and check if it matches that given in the problem. The algebraic way is to let x be the number of chickens, y the number of cows, and write:
x + y = 10
2x + 4y = 22
And then solve for x and y the standard way. (In case it needs to be said, chickens have one head and two feet while cows have one head and four feet.)
What does this all have to do with hash functions, though? Glad you asked.
A cryptographic hash function for 10,000 BC
Recall the requirements for a cryptographic hash function: it must be easy to compute the output (digest) for any input (preimage), but hard to compute the input for any output (other than by trying every preimage). In other words, a one-way function (or trapdoor one-way function without the trapdoor).
So, here's a hash function for a mathematically backward world: First, it takes two integers as input. You let the first be number of chickens, and the second be the number of cows. Then, output the total number of heads and feet (perhaps with a simple separator, like "10:22" for the above example).
It works as a hash function for the people of 10,000 BC precisely because of their (relatively) poor mathematical understanding. Since they don't know to express it as a system of linear equations, or otherwise derive a simple general solution, someone trying to "crack" a given hash digest (output) would have no choice but to guess and check a bunch of chicken/cow possibilities. This method is referred to as "brute force" in cryptography, and as long as a hash function hasn't yet been "broken" (by a better understanding of the math theory involved), it's the only option available.
Though this situation may seem contrived to us now, the same dynamic is at play in modern, military grade cryptographic hash functions: so long as people lack sufficient mathematical understanding, it is impossible to invert a hash digest except by brute force. The only difference between now and then is that the math and computations are harder.
In the previous post, I mentioned how hash functions can be used to protect stored passwords while still allowing password-based authentication. Let's go over how this would work.
An encrypted password system for 10,000 BC
Let's say Mike the Merchant wants to set up a service of warehousing people's valuables. He'll deal with many customers and doesn't want to count on remembering their faces when they come to reclaim their stuff. So, he'll give each customer a unique password they must use to get in. This will be a stronger authentication system than just trying to remember every customer.
Like modern website owners, Mike also wants to keep his password records from being stolen or misused (say, to steal his customers' stuff). If he simply kept the passwords in a book, someone who gained access to it could copy them and then come one by one to illicitly claim the goods in the warehouse. (Though of course, Mike can always use common sense security measures, like noticing something is fishy when the same customer one day claims to know all the passwords!)
So, rather than store the passwords, he converts them into two integers (if the password isn't already in that form) and stores the digest from putting them through the hash function described above. So, if Harry the Hoarder's password were 100:350, Mike would store Harry's password as 450:1600. (That is, interpret the number before the colon in the password as chickens and the latter as cows, and then store the number of heads [100 + 350 = 450] and number of feet [2*100 + 4*350 = 1600], separated by a colon.)
Then, when someone comes in claiming to be Harry, Mike asks for the password. Next, instead of comparing Harry's password (100:350) to an entry in his book, he first computes the hash digest (450:1600), and compares that number with his entry for Harry. So, he still has a working system to authenticate people by password.
What protection does this offer Mike if someone gains access to his password book and copies the entries? Well, remember, like with modern systems, all they get are the digests that result from putting the passwords through the hash function, not the passwords themselves. And knowing a digest won't convince Mike that you're the account holder: remember, he's checking for a pair of numbers that hash to your entry, not the entry itself.
Could the attacker infer the passwords from the digests listed in Mike's book? Yes, but it would take infeasibly long to do so -- that's the role of the hash function. Going from cows/chickens to heads/feet is easy, but going the other way is hard (for a mathematically backward society, at least). To make any use out of Mike's hashed-password book, an attacker would have to guess a huge number of passwords and see if their digests match any in the book. As long as the password space is big enough, and the society remains mathematically backward enough, it's just not feasible for an attacker to guess and check enough passwords to find a match in the book.
And like in the previous section, this is the same position we are in with respect to hashed password storage today: with a good enough mathematical breakthrough, it might become feasible to quickly invert a hashed password, but as it stands now, the hash functions used are enough to render such databases useless to attackers (though obviously some attacks still get through, such as when a website continues to use a long-broken hash function). The only difference is the complexity of the math.
Of course, Mike still has to make sure his customers don't give out their passwords or store them insecurely ... a problem we still grapple with, twelve thousand years later.
Saturday, July 16, 2011
Bitcoin overview: proofs and common knowledge
In previous posts, I gave an explanation of the cryptographic building blocks of Bitcoin. Now I'll give a more "big picture" overview of how the overall system works. As before, I expect this to be easier to follow than the explanations I had to read to get to my current level of understanding.
Let's start from the general problems that a decentralized, anonymous (or pseudonymous) currency system has to solve. The most fundamental problem, is that of achieving "common knowledge" of the currency ownership. Specifically, everyone has to know not only who is the valid owner of any currency unit (so as to prevent double-spends); they must also know that everyone else knows the same answer. And they must know that you know that they know (and so on) this information. (This level of knowledge is known in the literature as common knowledge, but with the definition I just gave, not the conventional one.)
In other words, it's not enough that I know the current ownership status of any coin; I must count on others agreeing with me and knowing I agree with them. If you could accomplish this, you could get everyone to use and depend on the same record, thereby resolving disagreements about who is the current owner of what -- without trusting any one person. It is this problem that required the "key" innovation behind Bitcoin, as it has normally needed a trusted authority to solve it.
So what is this key innovation to solving that problem? The first insight is that it's possible to prove how many computing cycles were spent working on something. And with a system that implements such a "proof protocol", you can have a transaction record that provably has a certain number of past computing cycles spent on it. Then, you just need most of the users of a system to agree that they'll "go along with" whatever transaction record has the most computing cycles spent on it. Then, you know what the "real" global ledger is -- and you can trust that everyone else is using it too! (And they can trust that you're using it, etc.)
And there you have it: proof of ownership, without a central authority.
With that problem and solution in mind, a lot of the complexity of Bitcoin starts to make sense.
Remember how I had previously mentioned that bitcoins are initially doled out based on who can solve complex mathematical problem? Well, that math problem doesn't just exist to get initial bitcoins widely distributed -- that's not even the most important function of the problem. The main purpose, rather, is to prove that the the largest number of computer cycles were spent on a given transaction record. You see, if you start from the last known solution (which itself has the transaction record up to a point in time), you are starting from a record with, so far, the biggest number of cycles spent on it. (And the Bitcoin protocol specifies that you should start from the biggest one, though its in your own interest, as you will see.)
If you publish an "update" -- the previous ledger plus more recent transaction -- with the next solution, then the other users know that your purported ledger has all the cycles you spent on it plus all the cumulative cycles spent up to the last solution. Therefore, if you want to claim credit for the latest solution (entitling you to the 50 BTC bounty), you should start from the ledger in the latest solution.
So, let's step back and summarize. Here is a simplified version of what goes on in the Bitcoin network:
1) Whenever users want to transfer their bitcoins over to someone else, they broadcast a message describing the transfer and sign it with their private key.
2) Whenever a user receives a message indicating a transfer, they first check that the signature is valid (see previous post on digital signatures), and that the address doesn't spend more than the latest "confirmed" ledger shows it as having. If it checks out, they keep the message and propagate it to others.
3) All users wishing to claim the reward for a solution (aka "miners") bundle up all transactions they know of (i.e., new ones plus those in the latest confirmed ledger), and convert it into a math problem unique to that transaction set. They then work on solving that problem.
4) When someone finds a solution, they broadcast it, with their bundle of known transactions (new latest ledger), to all other users. Like with individual transactions, anyone who receives one of these checks it, and if valid, broadcasts it to others.
5) Miners who receive a new valid solution quit their current search for a solution, then take the latest ledger as definitive. Again, as in 3), they bundle up new transactions they hear of, add them to this new ledger, and try to solve a new math problem unique to the new transaction set, and the process begins anew.
In practice, sometimes different users will simultaneously find a solution, or solutions will propagate through different parts of the network at different speed. So miners will typically hold on to the 4-5 last latest ledgers, in case one of them is extended and becomes definitive. Users, for their part, will wait for several new ledger solutions before accepting their transaction is firmly in the network.
Oh, and as for the relevant jargon? A new solution, with its bundle of old and new transactions, is called a block. The complete transaction record, with each solution along the way, showing how the build off of each other, is called the block chain -- because each block "chains" off a previous ledger.
Now, I'm leaving out a lot of details, but I hope that explains the overall system and the different roles played. In the future, I'll go into more detail on:
- How you prove you spent X computing cycles on something.
- How you prevent situations where miners constantly find solutions at the same time.
- How you minimize storage requirements for the transaction record.
- How overlapping solutions get resolved.
- And much more.
Let's start from the general problems that a decentralized, anonymous (or pseudonymous) currency system has to solve. The most fundamental problem, is that of achieving "common knowledge" of the currency ownership. Specifically, everyone has to know not only who is the valid owner of any currency unit (so as to prevent double-spends); they must also know that everyone else knows the same answer. And they must know that you know that they know (and so on) this information. (This level of knowledge is known in the literature as common knowledge, but with the definition I just gave, not the conventional one.)
In other words, it's not enough that I know the current ownership status of any coin; I must count on others agreeing with me and knowing I agree with them. If you could accomplish this, you could get everyone to use and depend on the same record, thereby resolving disagreements about who is the current owner of what -- without trusting any one person. It is this problem that required the "key" innovation behind Bitcoin, as it has normally needed a trusted authority to solve it.
So what is this key innovation to solving that problem? The first insight is that it's possible to prove how many computing cycles were spent working on something. And with a system that implements such a "proof protocol", you can have a transaction record that provably has a certain number of past computing cycles spent on it. Then, you just need most of the users of a system to agree that they'll "go along with" whatever transaction record has the most computing cycles spent on it. Then, you know what the "real" global ledger is -- and you can trust that everyone else is using it too! (And they can trust that you're using it, etc.)
And there you have it: proof of ownership, without a central authority.
With that problem and solution in mind, a lot of the complexity of Bitcoin starts to make sense.
Remember how I had previously mentioned that bitcoins are initially doled out based on who can solve complex mathematical problem? Well, that math problem doesn't just exist to get initial bitcoins widely distributed -- that's not even the most important function of the problem. The main purpose, rather, is to prove that the the largest number of computer cycles were spent on a given transaction record. You see, if you start from the last known solution (which itself has the transaction record up to a point in time), you are starting from a record with, so far, the biggest number of cycles spent on it. (And the Bitcoin protocol specifies that you should start from the biggest one, though its in your own interest, as you will see.)
If you publish an "update" -- the previous ledger plus more recent transaction -- with the next solution, then the other users know that your purported ledger has all the cycles you spent on it plus all the cumulative cycles spent up to the last solution. Therefore, if you want to claim credit for the latest solution (entitling you to the 50 BTC bounty), you should start from the ledger in the latest solution.
So, let's step back and summarize. Here is a simplified version of what goes on in the Bitcoin network:
1) Whenever users want to transfer their bitcoins over to someone else, they broadcast a message describing the transfer and sign it with their private key.
2) Whenever a user receives a message indicating a transfer, they first check that the signature is valid (see previous post on digital signatures), and that the address doesn't spend more than the latest "confirmed" ledger shows it as having. If it checks out, they keep the message and propagate it to others.
3) All users wishing to claim the reward for a solution (aka "miners") bundle up all transactions they know of (i.e., new ones plus those in the latest confirmed ledger), and convert it into a math problem unique to that transaction set. They then work on solving that problem.
4) When someone finds a solution, they broadcast it, with their bundle of known transactions (new latest ledger), to all other users. Like with individual transactions, anyone who receives one of these checks it, and if valid, broadcasts it to others.
5) Miners who receive a new valid solution quit their current search for a solution, then take the latest ledger as definitive. Again, as in 3), they bundle up new transactions they hear of, add them to this new ledger, and try to solve a new math problem unique to the new transaction set, and the process begins anew.
In practice, sometimes different users will simultaneously find a solution, or solutions will propagate through different parts of the network at different speed. So miners will typically hold on to the 4-5 last latest ledgers, in case one of them is extended and becomes definitive. Users, for their part, will wait for several new ledger solutions before accepting their transaction is firmly in the network.
Oh, and as for the relevant jargon? A new solution, with its bundle of old and new transactions, is called a block. The complete transaction record, with each solution along the way, showing how the build off of each other, is called the block chain -- because each block "chains" off a previous ledger.
Now, I'm leaving out a lot of details, but I hope that explains the overall system and the different roles played. In the future, I'll go into more detail on:
- How you prove you spent X computing cycles on something.
- How you prevent situations where miners constantly find solutions at the same time.
- How you minimize storage requirements for the transaction record.
- How overlapping solutions get resolved.
- And much more.
Monday, June 27, 2011
Setting professional Bitcoin traders straight
It's bothered me how a lot of the people posting criticisms of Bitcoin manage to get their facts wrong. But apparently, even people with a giant financial incentive to get them right ... still get them wrong.
At this point, I think it's only fair to post disclosures: I hold a portfolio that is long Bitcoin.
Anyway, I saw an (unintentionally) funny post on the blog at the Financial Times's Alphaville.
According to the post, a trader found out about Bitcoin and, based on technical analysis (chart-reading), he judged that Bitcoin was in a bubble and wanted to short. Okay, fair enough, we have someone entering the marketplace and tendering his judgment through the price system. So, you would think he would do his diligence and have some clue about what he was trading before trying to make a big bet on it, right?
Well ... I'll just quote him:
See the rookie mistake there? (If you don't, that's okay. After all, you weren't about to bet $50,000 on your incomplete understanding.) Bitcoin is a open source project that uses protocol that implements a currency. That's all it does: make sure that the ability to use Bitcoins, per its own published protocols, works. The people at Bitcoin.org -- the development team and volunteers updating the wiki -- don't run exchanges (like Mt. Gox) where you can convert bitcoins into dollars. Those are independently run by people who use Bitcoin.
In short, MT. GOX IS NOT THE SAME AS BITCOIN!
So, this trader just did the equivalent of "trying to contact" the U.S. Mint to "ask if they intended to implement a possibility to short the US dollar", and then speculating that they must have been unable to answer his inquiry "due to the overload in mails they must have had" in this oh-so-heated market.
No, bright guy, they probably just didn't have time to talk to someone who didn't even understand the difference between a Bitcoin exchange (like Mt. Gox) and the Bitcoin project. Just like, I suppose, the U.S. Mint doesn't respond to inquiries misdirected people who ask them when they can short the dollar. (Note: it's not shorting the US dollar that's necessary misdirected, but asking the U.S. Mint about it.)
The blogger, Tracy Alloway, didn't seem to do any better. He added:
Nuanced? Yikes. I just hope traders -- and financial journalists -- have a better understanding of their normal playground than they do about Bitcoin.
At this point, I think it's only fair to post disclosures: I hold a portfolio that is long Bitcoin.
Anyway, I saw an (unintentionally) funny post on the blog at the Financial Times's Alphaville.
According to the post, a trader found out about Bitcoin and, based on technical analysis (chart-reading), he judged that Bitcoin was in a bubble and wanted to short. Okay, fair enough, we have someone entering the marketplace and tendering his judgment through the price system. So, you would think he would do his diligence and have some clue about what he was trading before trying to make a big bet on it, right?
Well ... I'll just quote him:
I've done some research, read through the concept [of Bitcoin] and quickly got to the point where I felt that the only reasonable position would be to short such a bull market. [...]
... so I tried to contact Adam at Bitcoin.org to ask if they intended to implement a possibility to short the BTC. Due to the overload in mails they must have had, I never got an answer on my inquiry.
See the rookie mistake there? (If you don't, that's okay. After all, you weren't about to bet $50,000 on your incomplete understanding.) Bitcoin is a open source project that uses protocol that implements a currency. That's all it does: make sure that the ability to use Bitcoins, per its own published protocols, works. The people at Bitcoin.org -- the development team and volunteers updating the wiki -- don't run exchanges (like Mt. Gox) where you can convert bitcoins into dollars. Those are independently run by people who use Bitcoin.
In short, MT. GOX IS NOT THE SAME AS BITCOIN!
So, this trader just did the equivalent of "trying to contact" the U.S. Mint to "ask if they intended to implement a possibility to short the US dollar", and then speculating that they must have been unable to answer his inquiry "due to the overload in mails they must have had" in this oh-so-heated market.
No, bright guy, they probably just didn't have time to talk to someone who didn't even understand the difference between a Bitcoin exchange (like Mt. Gox) and the Bitcoin project. Just like, I suppose, the U.S. Mint doesn't respond to inquiries misdirected people who ask them when they can short the dollar. (Note: it's not shorting the US dollar that's necessary misdirected, but asking the U.S. Mint about it.)
The blogger, Tracy Alloway, didn't seem to do any better. He added:
We like the currency trader’s rather more nuanced take ...
Nuanced? Yikes. I just hope traders -- and financial journalists -- have a better understanding of their normal playground than they do about Bitcoin.
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.
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:
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!
Hope you found this helpful!
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.
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.
Subscribe to:
Posts (Atom)