Because of the virus we had to hold this meetup virtually, and I was slated to present there for the Evening of Python Coding. Since we made a recording of it, I can now share. Enjoy my not-ready-for-prime-time voice! (Yes, I need to update my profile picture ... badly.
A blog by Silas Barta
Showing posts with label math. Show all posts
Showing posts with label math. Show all posts
Wednesday, March 18, 2020
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, December 14, 2009
Silas Barta, information theorist by night
UPDATE 12/17/09: Steven Landsburg, after responding several times in the comments section here, posts a defense of his position on his blog, although without mentioning me or Bob Murphy. Hey, I can understand: if I were in his position, I'd hide the existence of me and Bob too!
***
Bob Murphy invokes my expertise on information theory to criticize (yet) another bizarre argument from Steven Landsburg, that the natural numbers are more complex than human life. Here's the mistaken part of Landsburg's reasoning:
Naturally, I don't necessarily agree with the broader theological points Bob makes in his reply, and such issues will remain even scarcer on this blog than on his. However, I will expand on point I made in discussion with Bob.
The error in Landsburg's line of reasoning is: the fact that you can use instances of X to build Y does not mean X is more complex than Y. Just the opposite, in fact: in order to describe Y, you must describe X as a substep. Like in the analogy I gave, you can use bricks and mortar to build a house, but that means it's the house that's more complex. To fully specify the house you must describe not only the bricks and mortar, but the form they take as a house -- how they're supposed to be put together.
As for arithmetic and natural numbers, it's their lack of complexity that makes them so useful. By appealing to it, you can make sense of a diverse array of phenomena. The more complex arithmetic were, the less helpful it would be in making sense of things.
Just to be clear, this doesn't mean it's easy to learn math (different people have different problems in different topics and levels), or that you can't do anything complex with math. The point is that no amount of complexity produced in using arithmetic could ever imply arithmetic's complexity, for the same reason that no matter how complex a house you make with one kind of brick, you can't make the brick more complex.
But of course, Landsburg's errors don't end there. He wants to go so far as to say that by merely encoding the genome in base 4, you've described human life. That's certainly the impression people get from discussions of DNA in the popular media and movies like Jurassic Park. Hey, all you need is a string of letters made up of A,G,C,T, and you've described someone completely!
To put it mildly: that's not how it works. First of all, you need to say what the letters actually mean. And then, even if you know that much, all you have are empty labels -- suggestively named LISP tokens. So you know that C is cytosine? Okay, but what's that? Now you need to describe where the carbons and nitrogens and oxygens go to make up cytosine. But wait -- what's this "nitrogen" thing, anyway? And so on.
Don't worry -- the process terminates: once you've described the generative model that puts all of these concepts together in a way that yields a description of human life as its output.
Needless to say, you're using more than a few integers by that point!
***
Bob Murphy invokes my expertise on information theory to criticize (yet) another bizarre argument from Steven Landsburg, that the natural numbers are more complex than human life. Here's the mistaken part of Landsburg's reasoning:
...the most complex thing I’m aware of is the system of natural numbers (0,1,2,3, and all the rest of them) together with the laws of arithmetic ...
If you doubt the complexity of the natural numbers, take note that you can use just a small part of them to encode the entire human genome. That makes the natural numbers more complex than human life. Unless, of course, human beings contain an uncodable essence, like an immortal soul
Naturally, I don't necessarily agree with the broader theological points Bob makes in his reply, and such issues will remain even scarcer on this blog than on his. However, I will expand on point I made in discussion with Bob.
The error in Landsburg's line of reasoning is: the fact that you can use instances of X to build Y does not mean X is more complex than Y. Just the opposite, in fact: in order to describe Y, you must describe X as a substep. Like in the analogy I gave, you can use bricks and mortar to build a house, but that means it's the house that's more complex. To fully specify the house you must describe not only the bricks and mortar, but the form they take as a house -- how they're supposed to be put together.
As for arithmetic and natural numbers, it's their lack of complexity that makes them so useful. By appealing to it, you can make sense of a diverse array of phenomena. The more complex arithmetic were, the less helpful it would be in making sense of things.
Just to be clear, this doesn't mean it's easy to learn math (different people have different problems in different topics and levels), or that you can't do anything complex with math. The point is that no amount of complexity produced in using arithmetic could ever imply arithmetic's complexity, for the same reason that no matter how complex a house you make with one kind of brick, you can't make the brick more complex.
But of course, Landsburg's errors don't end there. He wants to go so far as to say that by merely encoding the genome in base 4, you've described human life. That's certainly the impression people get from discussions of DNA in the popular media and movies like Jurassic Park. Hey, all you need is a string of letters made up of A,G,C,T, and you've described someone completely!
To put it mildly: that's not how it works. First of all, you need to say what the letters actually mean. And then, even if you know that much, all you have are empty labels -- suggestively named LISP tokens. So you know that C is cytosine? Okay, but what's that? Now you need to describe where the carbons and nitrogens and oxygens go to make up cytosine. But wait -- what's this "nitrogen" thing, anyway? And so on.
Don't worry -- the process terminates: once you've described the generative model that puts all of these concepts together in a way that yields a description of human life as its output.
Needless to say, you're using more than a few integers by that point!
Friday, September 19, 2008
Time to review the Put-Call Parity Theorem
With the SEC's recent move to ban short-selling of politically-important securities, it's time to review the beautiful Put-Call Parity Theorem to understand the futility of doing so. Here's my phrasing and elegant explanation of it:
B(t,$X) = S + P(t,$X) - C(t,$X)
B is the value of a bond maturing at time t for $X.
S is the value of some asset, it doesn't matter which.
P is the value of right to sell the above asset at time t for $X. (In financial terminology, a put option dated at t with a strike price of $X.)
C is the value of the right to buy the above asset at time for $X. (In financial terminology, a call option dated at t with a strike price of $X.)
In this sign convention, negative means the counterparty to the security, so for example, if the bond term were negative, it would refer to the value to the borrower on that loan, while the negative call option refers to the person having the obligation to sell at $X to the call owner.
So, the equation means that, for some time t and some money amount $X, a bond maturing at t for $X is equal in value to some asset, plus the right to sell the asset at time t for $X, plus the obligation to sell it at time t for $X.
Proof: the left-hand side of the equation is worth $X at time t. The right-hand side is also worth $X at time t because if S were worth less than $X, the holder of the put could sell it for $X, while if it were worth more, the holder of the call could buy it for less. Q.E.D.
Note that if you find a case where the two sides are not equal, you profit through arbitrage buy buying the cheaper side and selling the more expensive side. In a discussion a few years ago, Gene Callahan claimed this was how he made money. You also might be interested to know that this theorem -- though of course it wasn't referred to in such terms -- was historically used to circumvent financial regulations such as bans on usury, since through clever rearrangement of the equation you can recreate any financial security. Here is a neat paper on that history.
Anyway, the point to remember is, let's say I want to take a short position in a stock. That would be represented by "-S" in the above equation. But let's say you found out that was banned! No problem. Just rearrange the equation! With the function arguments suppressed:
-S = -B + P - C
So, borrow money, buy a put, and write (sell) a call. Problem solved! (Except for the cost of fending off the SEC guy giving you an intimidating stare, of course.)
B(t,$X) = S + P(t,$X) - C(t,$X)
B is the value of a bond maturing at time t for $X.
S is the value of some asset, it doesn't matter which.
P is the value of right to sell the above asset at time t for $X. (In financial terminology, a put option dated at t with a strike price of $X.)
C is the value of the right to buy the above asset at time for $X. (In financial terminology, a call option dated at t with a strike price of $X.)
In this sign convention, negative means the counterparty to the security, so for example, if the bond term were negative, it would refer to the value to the borrower on that loan, while the negative call option refers to the person having the obligation to sell at $X to the call owner.
So, the equation means that, for some time t and some money amount $X, a bond maturing at t for $X is equal in value to some asset, plus the right to sell the asset at time t for $X, plus the obligation to sell it at time t for $X.
Proof: the left-hand side of the equation is worth $X at time t. The right-hand side is also worth $X at time t because if S were worth less than $X, the holder of the put could sell it for $X, while if it were worth more, the holder of the call could buy it for less. Q.E.D.
Note that if you find a case where the two sides are not equal, you profit through arbitrage buy buying the cheaper side and selling the more expensive side. In a discussion a few years ago, Gene Callahan claimed this was how he made money. You also might be interested to know that this theorem -- though of course it wasn't referred to in such terms -- was historically used to circumvent financial regulations such as bans on usury, since through clever rearrangement of the equation you can recreate any financial security. Here is a neat paper on that history.
Anyway, the point to remember is, let's say I want to take a short position in a stock. That would be represented by "-S" in the above equation. But let's say you found out that was banned! No problem. Just rearrange the equation! With the function arguments suppressed:
-S = -B + P - C
So, borrow money, buy a put, and write (sell) a call. Problem solved! (Except for the cost of fending off the SEC guy giving you an intimidating stare, of course.)
Subscribe to:
Posts (Atom)