So let's now dig into the technical details of Bitcoin's consensus algorithm.
And while we're looking at that, we should keep in mind that Bitcoin does all of this
without nodes having any persistent long term identities.
This is, yet again, a difference from how traditional distributive consensus
algorithms operated and if nodes did have identities,
it would make things a lot easier for a couple of reasons.
One is a pragmatic reason.
It would allow you to put into your protocol things like, now the node
with the lowest numerical ID should take some step or something like that.
So that's a simple pragmatic reason which, already if nodes are completely anonymous,
becomes harder to do.
But a much more serious reason for nodes to have identities, is for security,
because if nodes were identified,
and they weren't attribual to create new node identities, then we could
make assumptions like, let's say that less than 50% of the nodes are malicious.
And we could derive security properties out of that.
So for both of those reasons,
the consensus protocol in Bitcoin is a bit harder.
But why is it exactly that Bitcoin nodes don't have identities?
Well, it's for a couple of reasons.
One is that if you're in a decentralized model in a peer-to-peer system,
there is no central authority to give identities to nodes and
verify that they're not creating new nodes at will.
And, in fact, the technical term for this is a Sybil attack.
Sybils are just copies of nodes that a malicious adversary can create
to look like there are a lot of different participants, when in fact,
all those pseudo participants are really controlled by the same adversary.
The other reason is that pseudonymity is inherently a goal of Bitcoin.
Even if it were possible or easy to establish identities for all nodes or
all participants, we wouldn't necessarily want to do that.
So, Bitcoin doesn't give you strong anonymity guarantees out of the box,
in that the different transactions that you make can probably be linked together,
but at the same time nobody is forcing you to put your real life identity,
like your name or IP address or anything like that, in order to participate in
the peer-to-peer network and in the block chain, and that's an important property.
So, what we can do instead is we can make a weaker assumption.
And I kind of wanted you to take a leap of faith with me here
that this weaker assumption is something that is going to be feasible.
And I'm gonna make this assumption here, and
later show you how this is actually accomplished.
And what this weaker assumption is, is that we're gonna assume that there is some
ability, somehow, to pick a random node in the system.
And a good motivating analogy for this, is a lottery or
a raffle, where any number of real life systems, we're tracking and
verifying people and giving them identities.
And verifying those identities is pretty hard and so what we do in those contexts
is we might give them tokens or tickets or something of that sort and
that then enables us to later pick a random token ID and call upon that person.
So we're gonna do something similar with respect to these Bitcoin nodes, and
further assume, for the moment, that this token generation and
distribution algorithm has enough smarts so that, if the adversary is going to try
to create a lot of civil nodes, together, all of those civils just get one token, so
the adversary is not able to multiply his power that way.
So let's make this assumption for now, and
let's see what becomes possible if we make this assumption.
Here's the key idea.
What becomes possible under this assumption of random node selection and
something called implicit consensus.
So what is implicit consensus?
In each round, and there are gonna be multiple rounds,
each round corresponding to a different block in the block chain,
in each round a random node is somehow selected, magically for the moment.
And this node gets to propose the next block in the chain.
There is no consensus algorithm.
There is no voting.
This node simply unilaterally proposes what the next
block in the block chain is going to be.
But what if that node is malicious?
Well, there is a process for this, but it is an implicit one.
Other nodes will implicitly accept or reject that block.
And how will they do that?
If they accept that block, they will signal that acceptance
by extending the block chain starting from that block, or if they reject that block,
they will extend the chain by ignoring that block and
starting from whatever was the previous, latest block in the block chain.
And technically, how is that implemented?
Recall that each block contains a hash of the block that it extends and
this is the technical mechanism that allows nodes to signal
which block it is that they are extending.
So, given this, this is what the overall consensus algorithm in Bitcoin is
going to look like.
Now this is a little bit simplified and the reason it's simplified is again that
I'm assuming sort of this magic random node selection process.
But except for
that simplification, this is pretty close to how Bitcoin actually works.
So whenever Alice wants to pay Bob, she will create a transaction, and
she will broadcast it to all of the nodes.
And any one of these nodes is constantly listening to the network and collecting
a list of outstanding transactions that have not yet made it into the block chain.
At some point,
one of these nodes is going to be randomly called upon to propose the next block.
It's going to round up all of the outstanding transactions that it's heard
about and propose that block.
Now presumably, that node was honest, but it could also be a malicious node or
a faulty node and propose a block that contains some invalid transactions.
Invalid transactions are those that don't have the right crypto signature or
where the transaction is already spent, in other words, an attempt to double spend.
So if that happens, other nodes are going to signal their acceptance or
rejection of the block, as we saw in the last slide, by either including the hash
of this latest block in their next block or ignoring this block and including
the hash of whatever was the previous block that they considered to be valid.
Right, so now let's try to understand why this consensus algorithm works.
And the way I like to understand this is instead of asking why this works,
let's try to ask how can a malicious adversary try to subvert this process.
So let's look at that for a second.
So here we have a couple of blocks in the block chain.
Assume that this extends to the left a long way back,
all the way to what is called the genesis block.
But here, I'm only showing you a couple of blocks in the block chain.
And that pointer that you see over there is
a block referring to what is the previous block that it extends,
by including a hash of that previous block within it's own contents.
So, a malicious attacker, let's call her Alice.
What might she try to do?
Can she simply steal Bitcoins belonging to another user at a different address that
she doesn't control?
Now, even if it is now Alice's turn to propose the next block in this chain,
she cannot steal other user's Bitcoins.
Why?
Because she cannot forge their signatures, so
as long as the underlying crypto is solid, she's not able to simply steal Bitcoins.
Another thing she might try to do, is if she really, really hates some other user,
Bob, then she can look at Bob's address and
she can decide that any transactions originating from Bob's address, she will
simply not include them in any block that she proposes to get onto the block chain.
In other words, she's denying service to Bob.
So this is a valid attack that she can try to mount.
But luckily, it's nothing more than a little annoyance,
because if Bob's block doesn't make it into the next block that Alice proposes,
he will just wait another block until an honest node gets the chance to propose
a block and then his transaction will get into that block.
So that's not really a good attack, either.
So the only one that we're really left with, for
what a malicious node can try to do here, is called a double spending attack.
So how might a double spending attack work?
To understand that, let's assume that Alice is a customer of some online
merchant or website run by Bob, who provides some online service,
in exchange for payment in Bitcoins.
Let's say he allows the download of some software.
So here's how a double spending attack might work.
Alice goes to Bob's website and decides to buy this item, pays for
it with Bitcoins, and what that means, in technical terms, is that she's
going to create a Bitcoin transaction from her address to Bob's address.
She broadcasts it to the network.
And let's say that some honest node creates the next block,
listens to this transaction, and includes it in that block.
So, what is going on here?
So, there is this block that was created by an honest node that contains
a transaction that represents a payment from Alice to the merchant, Bob.
By C subscript A, I mean, a coin belonging to Alice, and
that is now being sent to Bob's address.
Let's zoom into this in a little bit more technical detail.
A transaction, as we saw earlier, is a data structure that contains Alice's
signature here, and an instruction to pay to Bob's public key, and also a hash.
What is this hash?
This hash represents a pointer to the transaction where Alice,
in fact, received that coin from somebody else.
And that must be a pointer to a transaction that was included
in some previous block in the consensus chain.
So visually, it's going to look something like this.
Let's pause for a second here, because there's something subtle going on.
There are at least two different types of pointers
in this diagram that I've showed you.
There is, in fact, a third one corresponding to Merkle trace, but
we're not gonna look at that, at the present moment.
But this two types of pointers that I refer to, are blocks that include a hash
of the previous block that they're extending, and transactions that
include a pointer to whatever the previous transaction that where the coin came from.
Right, so this is the situation, and this block was now generated by an honest node,
and now let's assume that the next time a random node is called,
that node is a malicious node controlled by Alice.
Right, so this is the block chain as it stands right now.
Bob has already looked at this block chain, decided that Alice has paid him,
and has allowed Alice to download the software or
whatever it is that she was buying on his website.
Right, so as far as Bob is concerned, he is satisfied, the transaction is
completed, Alice has now received her goods in exchange for the payment.
Now what might happen, is if Alice now gets to propose the next block,
she could propose a block that looks like this.
Ignores altogether this valid block over here, and
instead, contains a pointer to the previous block.
And furthermore,
it's going to contain a transaction that contains a transfer of coins,
of Alice's coins to another address, A prime, that's also controlled by Alice.
So this is a classic double-spend pattern.
What is going on here, is Alice now creates a new transaction that
transfers that coin, instead of to Bob's address, to another address owned by her.
And visually it's gonna look like this.
This is a completely different transaction,
also with the hash pointer going back to same transaction referred to earlier.
Right, so this is what an attempt at a double-spend look like.
And how do we know if this double-spend attempt is going to succeed or not?
Well, that depends on whether this green transaction here or this red transaction
is going to ultimately end up in the long term consensus chain.
So what determines that?
That is determined by the facts that honest nodes
are always following the policy of extending the longest valid branch.
So now, which of these is the longest valid branch?
You might look at this and say, a-ha, the first one is the longest valid branch,
not the second one, because it's a double-spend attempt.
But here's a very subtle point that I want you to appreciate, from sort of a moral
point of view, this transaction in green and the transaction in red might look very
different, because based on the explanation that I've given you,
the first one is an attempt by Alice to pay Bob, whereas the second one
is an attempt by Alice to defraud Bob and pay coins back to herself.
But from a technological point of view,
these two transactions are completely identical.
The nodes that are looking at this,
really have no way to tell which one is the legitimate transaction.
I'm putting legitimate in air quotes,
because it's a moral judgment that we apply to it,
it's not a technical distinction, versus which one is the attempted double-spend.
It could easily be the other way around.
Now, nodes often follow a heuristic of extending the block that they first
heard about on the peer-to-peer network, but it's not a solid rule.
And in any case,
because of network latency, that could easily be the other way around.
So now there is at least some chance that the next node
that gets to propose a block will extend this block instead of this one.
Or it could be that even if it's an honest node, Alice could try to bribe that node
or try to subvert the process in a variety of ways.
So for whatever reason, without going too much into the details, let's say that
the next node extends the block with the red transaction instead of the green one.
What this means is that at this point,
the next honest node is much more likely to extend this block instead of this
one because now this has become the longest valid chain.
So let's say that after one more block, the situation looks like this.
Now it's starting to look pretty likely that this double-spend has succeeded,
in fact, what might happen is that this ends up the long term consensus chain and
that this block gets completely ignored by the network, and this is now called
an orphan block, and this is an example of a successful double-spend.
So now let's look at this whole situation from Bob, the merchant's point of view,
and understanding how Bob can protect himself from this double-spending attack,
it's really gonna be a key part of understanding Bitcoin security.
So let's look at what happened here again.
We have a couple of blocks in the block chain.
And at this point,
Alice broadcasts a transaction that represents her payment to Bob.
And so Bob is going to hear about it on the peer-to-peer network right here,
even before the next block gets created.
And so, Bob can do something even more foolhardy than what he did in the previous
light which is, that as soon as he hears about the transaction on the peer-to- peer
network, he can complete the transaction on the website and
allow Alice to download whatever she's downloading.
That's called a zero confirmation transaction.
Or, he could wait until the transaction gets one confirmation in the block chain,
which means that at least some node has created a block and has proposed
this transaction and that has gone into the block chain, but as we saw earlier,
even after one confirmation, there could be an attempt at a double-spend.
So let's say that this actually happens.
If, as in the previous slide, the double-spend attempt succeeds,
what Bob should do is to realize that the block that he though represented
Alice paying him has now been orphaned, and so he should abandon the transaction.
Instead, if it so happens that despite this double-spend attempt, the next block
that's generated turns out to extend the block that he's interested in,
now he sees that his transaction has two confirmations in the block chain.
Now he gets a little more confidence that his transaction is going to end up
on the long term consensus chain.
So let's say there's one more, and now there are three confirmations, in general,
the more confirmations your transaction gets, the higher the probability
that it is going to end up on the long term consensus chain.
Because if you recall, the honest node's behavior,
that they will always extend the longest valid branch that they see, the chance
that this one is going to catch up to this longer branch is now very minuscule,
especially if only a minority of the nodes are malicious.
Right, because, typically, the only reason that this double-spend attempt block would
be extended at this point, is if the next node to be picked randomly was a malicious
node, and then you'd need another malicious node and
then another for this shorter branch to then become the longer branch.
In general, the double-spend probability decreases exponentially with
the number of confirmations.
So, if the transaction you're interested in has received k confirmations,
then the probability that this other transaction is going to end up on the long
term consensus chain, goes down exponentially as a function of k.
And the most common heuristic, that's used in the Bitcoin ecosystem,
is that you wait for six confirmations.
There is nothing really special about the number six.
It's just a good trade-off between the amount of time you have to wait and
your guarantee that the transaction you're interested in
ends up on the consensus block chain.
So let's recap what we saw here.
Protection against invalid transactions,
that is protection against a malicious node, simply making up a transaction to
steal someone's Bitcoins, is entirely cryptographic.
But it is enforced by consensus, which means that if a node does attempt that,
then the only reason that that transaction won't end up in the launch group consensus
chain is because a majority of the nodes are honest and
will treat that transaction as invalid.
On the other hand, protection against double-spending is purely by consensus.
Cryptography has nothing to say about this and true transactions that represent
a double-spending attempt, kind of look identical
from the prospective of signatures, and so on, but it's the consensus that determines
which one will end up on the long term consensus chain.
And finally, you're never 100% sure that a transaction you're interested in is on
the consensus branch, but this exponential probability guarantee is pretty good.
After about six transactions,
there's virtually no chance that you're gonna go wrong.
No comments:
Post a Comment