The Byzantine Generals’ Problem & The Bitcoin Solution [Session 2 - MOOC by UNIC]

in #education6 years ago

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


session2.jpg

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

  1. Assets and Transaction Ledgers
  2. The Byzantine Generals’ Problem
  3. The Bitcoin Approach to the Byzantine Generals’ Problem
  4. Bitcoin: Some Key Metrics
  5. Conclusions
  6. 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.

Let's take a look at the theory behind it!


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.


Image CC0 Licensed

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:

  1. All generals decide for the same action and
  2. 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?

Quick reference: The Bitcoin Ledger
  • 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
A

The Miners broadcast the transactions in a block

B

A cryptographic hash function of the previous block header is applied to the new block

C

The Miner tries to solve the Proof-of-Work:

  1. Creates a hash of Last Block Header + Block of New Transactions + Random Number
  2. Applies SHA-256 to the above
  3. 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

source


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


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

Sort:  




This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @curie.

If you appreciate the work we are doing then consider voting both projects for witness by selecting stem.witness and curie!

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

It's great to see that the course I registered last month even has a steemit account now!!
I'm wondering if I post some learning experience about your course, can I get a little vote from you?haha
Or maybe you can hold such a event to let more steemians to join the community!!

Thank you!
We will appreciate your feedback on our course!

Congratulations @mscdigital! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You made more than 10 comments. Your next target is to reach 50 comments.

Click here to view your Board of Honor
If you no longer want to receive notifications, reply to this comment with the word STOP

Do not miss the last post from @steemitboard:

SteemitBoard notifications improved

Support SteemitBoard's project! Vote for its witness and get one more award!