DFIN-511: Introduction to Digital Currencies
Session 2: The Byzantine Generals’ Problem & The Bitcoin Solution
During Session 1, a Brief History of Money was presented.
We learned about the main characteristics of currencies, and about how economy evolved from barter exchanges, to coinage, to fiat money and recently to digital assets.
We referred to new kinds of currencies and to the decentralization of currencies such as Bitcoin, which exists only in digital form and is created with secure cryptographic functions.
Objectives of Session 2
The second session is considered to be a challenging session, and the students are advised to invest as much time is needed in order to comprehend the theory behind it.
You will learn how to recognize centralized asset & transaction ledgers
You will learn what the Byzantine Generals' Problem is
You will understand how Bitcoin addresses the Byzantine Generals' Problem
You will get a chance to review Bitcoin metrics
Contents
- Assets and Transaction Ledgers
- The Byzantine Generals’ Problem
- The Bitcoin Approach to the Byzantine Generals’ Problem
- Bitcoin: Some Key Metrics
- Conclusions
- Further Reading
1. Asset and Transaction Ledgers
An asset is any resource owned by a business. Anything tangible or intangible that can be owned or controlled to produce value and that is held by a company to produce positive economic value is an asset. Simply stated, assets represent value of ownership that can be converted into cash (although cash itself is also considered an asset)1
Ledger is defined as a complete record for a business's economic activities, usually tracks all transfers of money or assets.
Blockchain is a shared, digital ledger that records transactions in a peer-to-peer network. The network is decentralized, it records transactions permanently and it is considered to be tamper-proof (unchangeable)
Source: Lecture Notes
A few typical examples of centralized ledgers are financial services, medical institutions, voting systems and more. In the above cases, a single authority keeps and is responsible for the integrity of everyone's information.
The trustworthiness of centralized ledgers has been questioned. Some worth-to-be-mentioned examples include fake academic certificates, loss of records of land registries and more.
When decentralized ledgers (blockchain applications) were introduced, technologists were excited to see practical use of what was considered to be used in theory only.
A decentralized ledger would be able to solve a number of problems such as vulnerability to censorship, malfeasance, loss of records, loss of integrity.
2. The Byzantine Generals’ Problem (BGP)
The Byzantine Generals’ Problem (BGP) is a common issue faced by any distributed computer network. In such networks participants are autonomous computational entities that communicate with each other by exchanging information (aka message passing). A challenge is faced where such networks need to reach agreement (aka consensus) on the information that is exchanged/transmitted in the network for reaching a common goal (e.g., solving a computational problem). Under this setup it is often the case that participating entities may fail, and share imperfect/conflicting information.
Despite the conflicting information, the network needs to find a solution and this is what is being described in detail, at the Original 1982 Paper by L. Lamport, R. Shostak, and M. Pease.
The BGP is simulated by an army that is camped outside an enemy city, where each group is lead by its general. The gererals can only communicate with messengers and then they should decide their next actions, according to the messages conveyed by the messengers. Some of the generals though, may be traitors. It is important that a way/algorithm is found in order to be guaranteed that:
- All generals decide for the same action and
- A number of traitor generals will not cause the loyal ones to decide for the wrong action plan
3. The Bitcoin Approach to the Byzantine Generals’ Problem
What is the approach of Bitcoin to the BGP?
- The user will need to download the Bitcoin's 'client' software
- The software will download/synchronize the whole blockchain i.e., all transactions recored in the history of Bitcoin
- All Bitcoin clients store all records of all transactions (a copy of the ledger)
Some questions that may arise are:
- How are the copies of the ledger synchronized?
- If conflicting messages regarding a transaction are received, how does the client recognize which is the correct and which the fraudulent is?
Would that by now remind you of the Byzantine Generals' Problem?
To make the analogy to BGP and assuming a distributed ledger, any input data (i.e., the messages) to the ledger (relating the ledger as the agreed action i.e., the time of attack) must be trusted by everyone. In distributed networks though, participating entities are dispersed with an uncertain level of trust. Thus, making it impossible to assume that all entities are trustworthy without the existence of a central governance (aka centralized authority).
So, how can you ensure that all autonomous entities agree upon the same task (e.g, exact time to attack)? In distributed ledger terms we need to make sure that:
- the inputs to the distributed ledger are accurate, and
- the ledger itself contains (records) accurate information (encoded as transactions and bundled together into what we call a block)
How are transactions confirmed?
A process called mining, is what verifies a transaction, by solving a problem called as 'proof-of-work'.
As a reward for verifying the transactions & creating new blocks, the miners receive new bitcoins. An incentivised mechanism for people to allocate computational power to the network. As more participants join the network the more secure it becomes.
Let's take a quick look at the process
The Miners broadcast the transactions in a block
A cryptographic hash function of the previous block header is applied to the new block
The Miner tries to solve the Proof-of-Work:
- Creates a hash of Last Block Header + Block of New Transactions + Random Number
- Applies SHA-256 to the above
- The hash is reviewed against a predetermined value and if it is greater than the value, the process is repeated. If it is less than the above value, then prize is awared to the miner that first found the solution to the problem.
Only when a block is verified, is it broadcasted to the Bitcoin Network
In February 2018, the block reward is 12.5 bitcoins. This amount far outweighs the reward from transaction fees. The next halving will take place in2020. Block rewards will stop once the network reaches Block 6.930.000 (sometime around the year 2140). The total number of bitcoins issued by then will be about 21 million
4. Bitcoin: Some Key Metrics
You can find some interesting stats at:
https://www.blockchain.com/charts
At the moment this article is written, the following numbers have been noted:
10 October 2018 - 17.315.318 BTC in Circulation
Market Price - Average USD market price across major bitcoin exchanges.
Difficulty
A relative measure of how difficult it is to find a new block. The difficulty is adjusted periodically as a function of how much hashing power has been deployed by the network of miners.
5. Synopsis
The centralized nature of all ledgers throughout history might constitute security; however due to the central authority controlling all information, centralized ledgers are subject to corruption and potential technical failures.
A study in the area of fault-tolerance, described as the Byzantine Generals' Problem was utilized by and applied to a decentralized ledger, called the Bitcoin.
This application of a tamper-proof ledger, a cryptographically secure blockchain, the Bitcoin has found a number of increasing adopters.
The technology is considered to be a breakthrough and its implications are expected to extend beyond the field of digital currency in the next years.
6. Further Reading
http://pages.cs.wisc.edu/~sschang/OS-Qual/reliability/byzantine.htm
https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf
L. Lamport, R. Shostak, and M. Pease @ SRI International - ACM Transactions on Programming Languages and Systems, July 1982https://pdfs.semanticscholar.org/0d82/a314dd96265ac8542a9ca80e5c7db09594d2.pdf
Transcription of Mr A. Antonopoulos Video regarding proof of work & immutability
Lecture Notes - MOOC University of Nicosia / Master of Digital Currencies (2018)
Bitcoin Series (AntonisPolemitis, LedraCapital)
http://ledracapital.com/blog/2014/1/4/bitcoin-series-14-our-robot-overlords-will-use-bitcoin
http://ledracapital.com/blog/2014/3/11/bitcoin-series-24-the-mega-master-blockchain-list
(a group brainstorming of different places blockchain based technologies can be used)The Economics of Cryptocurrencies –Bitcoin and Beyond
https://www.chapman.edu/research/institutes-and-centers/economic-science-institute/_files/ifree-papers-and-photos/koeppel-april2017.pdf
This is a synopsis of what is presented at the 2nd Session of the MOOC - Introduction in Digital Currencies.
In the next session we will discuss the Basics of Cryptocurrency
For more detailed information & session slides, enroll now for the Free MOOC
Watch the 2nd video session of MOOC10 by Mr Andreas Antonopoulos
Overview of the 12-week FREE MOOC - Introduction to Digital Currencies
Disclaimer: This post is written by student of MOOC 9 & steemit user @katerinaramm. Approved by @mscdigital prior to its publication