Everybody is talking about Bitcoin. But how does it actually work?
It is very likely that you have heard of Bitcoin in the media or through friends. You have probably heard that it is some sort of internet-money. What you probably have not heard, is that the underlying technology (the blockchain) is actually a queueing system, which can be analyzed mathematically. In this article I will start with an example explaining how bitcoin transactions work and then proceed to a description of the queueing system hidden behind the blockchain.
Bitcoin transactions
Let me introduce you to Joe, who wants to buy a pizza by using Bitcoin. Unfortunately, he currently does not own any Bitcoin. Joe has two options to proceed:
(1) Joe exchanges his local currency (Euro) for Bitcoin.
(2) Joe buys a "mining rig", which he connects to the Bitcoin network, which he uses to mine Bitcoins.
The first option is by far the easiest way to obtain Bitcoin. The second option requires much more technical knowledge, and is typically only done by professional parties. Nonetheless, I will explain how mining works on a high level.
Mining Bitcoins
As the name suggests, a blockchain is a chain of blocks. Each block contains past transaction data. For example, block #143 states (amongst other things) that Alice sent 3 Bitcoins to Bob. Block #149 states: "Bob sent 1 Bitcoin to Cedric", etc). Every block is linked to an older block in the blockchain. Together, the whole chain records the whole history of each coin. Thus by scrutinizing the blockchain, each coin can be traced back to the origin (in this case, Cedric received a coin from Bob, who got it from Alice, who mined the coin).
When new blocks are linked to the blockchain, someone needs to be responsible for actually checking that the transactions are valid. By that, I mean that the spender actually owned the coin that he spent (and the same coin was not send from the same address multiple times… "double-spending" is not allowed). Alice, who is technically savvy, has bought a heavy machine and connected it to the Bitcoin network. The machine quickly generates random numbers, until it finds one that solves a particular cryptographic puzzle defined by the current state of the blockchain. If Alice is the first one in the Bitcoin network to find a solution, she can generate a block with transactions that have been waiting to be verified. This procedure is called mining, as it is very hard to find a block, but once you succeed you are rewarded with a nice handful of Bitcoins. In that sense, it has some similarities with gold mining. This is the origin of a Bitcoin: no one else has ever received or spent the Bitcoins that Alice got as a reward for mining.
Joe is still a bit puzzled by the technical complications of mining coins, and he doesn't have the computational power nor patience to go that route. He decides to directly swap some Euros for some Bitcoins. Now that he has some electronic cash in his electronic wallet, he is finally ready to buy the pizza!
Joe sends the 0.002 Bitcoin (BTC) to the wallet of Pizzeria Mario. As Mario is also connected to the Bitcoin peer-to-peer network, he immediately sees that a new transaction arrives in the "memory pool" (also abbreviated to mempool), which is essentially a queueing system consisting of transactions that are waiting to be verified (verified means that it has been put into a block which is linked to the blockchain). Mario may accept the transaction, trusting that it will be verified at some point in the future, so that he will be able to spend the electronic cash himself. However, it is possible that Joe tricked Mario, because he may have spend the 0.002 BTC before to someone else. If Mario wants to be certain that it is not the case, he has to wait until the transaction is verified by a miner and put in a block (or even better: until several other blocks have been added on top of that). If you want to get a better understanding of how this works I would recommend to read Satoshi Nakamoto's whitepaper [1] (with corrections in [2]) on Bitcoin.
In the remainder of this post, I would like to focus on the queueing aspect of Bitcoin. As I mentioned, when Joe sent 0.002 BTC to Mario, his transaction entered a queue. The time until the next block is mined, is independent of the time at which all other previous blocks were mined. Blocks are mined at random points in time, but at an (approximately) fixed rate. Mathematicians describe such arrival processes with a "Poisson process", which is often used in studying queueing systems. One peculiarity about this queue, is that when people transact Bitcoin between each other, they pay a (small) fee to the miner. Miners have the freedom which transactions to include in a block (a block may contain at most 1 Megabyte of transaction data). If the mempool currently has more than 1 Megabyte of transactions waiting to be mined, then the miner will typically prefer to take the transactions with the highest fee per amount of data. (Note that this is exactly the "Knapsack problem", if the miner wants to maximize his profits.)
Summarizing: the mining process involves a queueing system, where transactions are processed in batches of at most 1 megabyte, at Poissonian time epochs, according to a priority determined by the fee level. A very relevant questions could be: how much fee should I pay if I want my transaction to go through quickly? Or, to be more precise, how much should I pay if I would like my transaction to be validated in a block within the next 30 minutes with 95% certainty? Such questions can be answered by using probability theory, as I have described in [3]. Currently, some students are working on applying the model to real blockchain data. It will be interesting to see if the model is able to give proper fee recommendations. To be continued!
In February 2014, a big bank in the Netherlands suffered from an internet banking malfunction which led many costumers to accidentally perform duplicate bank transfers.
This article discusses a fun puzzle that illustrates a beautiful open problem in this area: queueing theorists are trying to figure out how the structure of a network impacts its ability to distribute work among the nodes.
Prof. dr. ir. Hans Heesterbeek, one of the leading infectious disease epidemiologists in the Netherlands, is a busy man. Fortunately for us, Hans Heesterbeek had a gap in his schedule to yet again answer some questions, this time not asked by professional journalists, but by us, four students from the Technical University in Eindhoven.
An echo chamber is a community wherein the same opinions are bounced around, endlessly ‘echoing’ with barely any change. And as they do, any other opinion is shunned, pushed aside, and eventually just rejected without consideration.
