Blockchain from First Principles
This is a summary of the Blockchain Training Camp developed by the Hong Kong Blockchain Society and delivered across the world.
What is blockchain?
A blockchain is a magical immutable record-keeping system. Immutable means unchangeable, which means all records written in the blockchain are unalterable and accessible, forever. The core of the system is a magic ledger, a record-book. The magic links each line in the book with the previous line, and also links each page with the previous page, such that if the book has been tampered with, it would be very obvious to everyone.
This magical immutable record-keeping system is a distributed ledger, literally. More copies of the ledger makes the records more trustworthy than if just one person controls the record-keeping system through one ledger. And the more people that have a copy, the more trustworthy the records are, because bribery of ledger holders or other forms of collusion is more difficult.
The magic of the ledgers also helps people synchronise their ledgers. When a new record is made, the magic decides if it is valid or not before adding to the official record, and makes it prohibitively expensive for non-valid records to be added. So, not only can everyone have the same records within a short amount of time, everyone can easily check if their records are valid or not.
What is a blockchain, really?
Replace the following:
- “magic” with cryptography (where the ‘crypto’ term comes from)
- “people” with computers, run by individual or corporate persons
- “lines” with digital transactions
- “pages” with digital blocks
- “links between lines and pages” as digital chains
and reimagine the “ledgers” not as physical books, but digital ledgers, or “databases” (hint: they are not, but use this analogy for now), and that is what blockchain is: a type of immutable distributed ledger technology, and a tool for helping parties to interact without requiring full trust with each other.
This also implies no central control—otherwise the parties would have to trust this de facto authority—hence blockchain applications are called “decentralised applications”.
For students designing projects for the International Blockchain Olympiad, this information is already enough to build a decentralised application.
If you are still curious, read on for a very vague explanation of blockchain:
Why is it blockchain?
The concept of a block chain was first introduced in 1976, but the current definition of blockchain was popularised by the publication of Bitcoin: A Peer-to-Peer Electronic Cash System by Satoshi Nakamoto, in which numerous references to blocks and chains were made, although there were no explicit mentioning of the word “blockchain” — that was coined later (#pun).
What is not blockchain?
BLOCKCHAIN ≠ BITCOIN
Bitcoin is the first application of blockchain… Bitcoin is not blockchain.
BLOCKCHAIN ≠ CRYPTOCURRENCY
Cryptocurrencies like bitcoin have dominated the discussion of blockchain for the last several years, but now that the bubble has bursted, it’s clear that many blockchain associations are market-focused cryptocurrency associations rather than focusing on the application of blockchain itself.
BLOCKCHAIN ≠ DISTRIBUTED COMPUTING
Distributed computing has been around since the 1960s, but it cannot solve the double-spend problem without relying on centralised control.
BLOCKCHAIN ≠ DATABASE
Databases are not blockchains, because their records can be changed or destroyed, unlike the records on a blockchain, which can never be changed nor destroyed. A blockchain reflects changes in state by adding new records.
Blockchains are also not linked lists nor spreadsheets. Now that you know what blockchain is and is not, what is it good for? Between “absolutely nothing” and “pretty much everything” depending on trust…
When to use blockchain?
Blockchains may be useful where there are multiple parties that need to reconcile information in order to work together. When everyone has their own records, the problem with reconciliation is that it is continuous, costly, and error-prone. Duplication can also lead to inconsistencies. Also, even for more than two parties, the reconciliation is actually bilateral, i.e. between two parties at a time. This means mistakes may magnify over time.
An obvious solution is to have a reconciliation infrastructure that keeps track of everything with a so-called “master copy”. This has its own issues: who is running it (management), how is it run (governance), where is it run (jurisdiction), and so forth. A centralised setup also makes a tempting target for bad guys to hack at.
Decentralisation through distributed ledger technologies like blockchain offers an elegant solution to the drawbacks of a centralised solution, even though the technology is harder to set up.
Blockchain is most useful when there are trust issues. If the parties involved already have a high degree of trust, there is no need for a blockchain. If parties require some trust to work together, but do not have or want to invest resources to build that trust, then that is an excellent case for blockchain.
And speaking of trust…
Distributed Ledger Technology (DLT)
A distributed ledger or shared ledger is a family of technologies that facilitates a consensus or agreement of replicated, shared, synchronised digital data among parties who need not trust each other. Blockchain is one member of this family, among others such as direct acyclic graphs (DAG) and other newer hybrid protocols.
DLT removes the need for centralised administration and centralised storage. This lowers the requirement for co-operation, because parties can work together without “getting married” to each other, sharing everything and revealing everything, including risks and sensitive information.
DLT can be classified as either permissionless or permissioned, depending on who has permission to participate in the validation or consensus process of a blockchain, i.e. the rules for deciding what lines in the ledger book are legit.
In order for DLT to work, it needs cryptography for ensuring:
- Secure authentication of participants
- Secure access by participants
- Security of transactions
And DLT also needs a consensus protocol for ensuring:
- Validity of transactions
- Ordering of transactions
- Integrity of the Ledger
Which brings us to the next topic:
Cryptography
Cryptography is the magic of the magical ledger. Cryptography is fundamentally mathematics. There are two important concepts to understand: digital signatures and hashing.
Digital Signatures
A signature is a unique, undeniable, personal, permanent mark used a proof of identity and intent. A signature is signed on a document as evidence of that person’s witness and certification of the contents of that document.
Repudiation is the denial of the truth of validity of something; non-repudiation is the assurance that someone cannot deny the truth of validity of something. A signature is a non-repudiation device.
In the digital world, the equivalent to a signature is… a digital signature. Just as a physical signature is a unique, undeniable, personal, permanent mark, a digital signature does the same thing with “magic”, i.e. cryptography, i.e. mathematics. A valid digital signature is a non-repudiation device, so in addition to assuring that the signatory cannot deny signing something, it also assures that the something is from a known party, and it was not altered.
Digital signatures are represented by a private key for signing something and a public key for checking that something. A public key is 100% related to the private key, so if you know the public key and its owner, you can easily verify that the ownership. Meanwhile, it is impossible to forge a private key.
What is a key? It is actually just a bunch of letters and numbers:
So, how are keys created?
So, how are keys used?
So, how are keys used in blockchain?
Your public key is used to generate addresses, which are pseudonymous “identities” for one to interact with other on a blockchain. In the bitcoin blockchain, whoever controls the private key can send bitcoin from all addresses derived from it.
And this is why you never give away your private keys! But wait, what is hashing? Good question…
Hashing
A hash function is a “math equation” that produces the same results uniform every time for any input. The cyan (light blue) input is hashed by the yellow hash function to produce the pink output. Note that even a small change in the input results in a completely unrelated output.
The next important concept to understand is the hash tree, also known as a Merkle Tree, because it was invented by a Dr. Ralph Merkle. The idea is that the key input is hashed, and the results will be hashed again with adjacent outputs, and those results are hashed again… until there is one hash output as a final result (the Merkle root). It is very easy to see if anything was changed, because any changes will affect hashes downstream.
The hash tree is the magic that links previous things with the next things, whether the thing is a “line on the page” (transaction, T) or a “page in the book” (block). By comparing the “magic” between the “books”, the “people” can see who is different… and therefore which “books” are legitimate or not.
But wait a minute, how do the “people” agree who is right or wrong? They would need some sort of rule set, also known as a protocol or algorithm, to come to a consensus…
Consensus
Consensus is a generally accepted decision among a group of people.
The most important thing for everyone to agree on is whether there is double spending (hint: there should not be). But what is double spending?
When something is physical, it is not easily nor economically replicated. In the digital world, replication is perfect and easy. So replicating physical money or something valuable is difficult, but replicating digital money would be easy. If someone can send you $100, you don’t want that person to send the same $100 to someone else, otherwise, when you want to claim that $100, you may have a chance of not being able to claim it!
For a group with centralised administration, consensus is easy: everyone agrees because the admin says so! For example, the bank says your friend had $100 and now has $0 because you had $0 and now have $100. In a decentralised group, coming to an agreement requires some rules for everyone to follow. Who gets to say your friend now has $0 and you have $100? Consult the rules!
However, there may be issues within a group of people to worry about: what if they are bad people who purposely tampered with the ledger, and what if they also encouraged other people to be bad in unison? Or what if some people are just bad at recording stuff—the difference between mistakes and tampering is intent. Or what if some people fell asleep at the meeting, or did not make it to the meeting, so they could not participate in the decision-making process?
Computers and nodes on a blockchain network are like humans, and this problem is as old as distributed computing itself. This is the Byzantine General Problem:
The Byzantine Emperor and his armies have surrounded an enemy, and the only way to win is if the majority of his generals attacks at the same time. Assuming most of the army is loyal, the challenge is for the Emperor to communicate his intentions, but things can go wrong, namely if traitor(s) say their army will attack or retreat but have the intention to do the opposite, or if messengers are intercepted and killed, or if messengers deliver the wrong message (by accident or on purpose), or if messengers are late, and so forth.
How does this relate to blockchain?
- The Byzantine generals must agree on a strategy.
The book holders must agree on legitimate lines on a page.
The blockchain must agree on transaction validity. - The Byzantine generals are geographically dispersed.
The book holders are not in the same room or space.
The blockchain are distributed notes in a network. - The Byzantine generals have loyalists and traitors among them.
The book holders have honest and dishonest or incompetent people.
The blockchain have honest nodes and malicious or faulty nodes. - The Byzantine generals may receive corrupted messages.
The book holders may receive illegitimate information about new lines.
The blockchain may receive invalid transactions. - The Byzantine generals want to know if messages are true.
The book holders want to tell if lines on a page are legitimate.
The blockchain needs to show only valid transactions.
A system that is able to handle the types of failures described in the Byzantine Generals Problem is said to be Byzantine fault tolerant or BFT. It turns out that in order for the consensus protocol of a DLT to be BFT, either liveness or consistency has to be supported and the other relegated to lower priority.
- Liveness is one of the three properties in the FLP Impossibility (1985), which states that something good will eventually happen. In the context of consensus, liveness means participants eventually decide on a value, or will never be stuck without decision.
- Consistency is one of the three properties in the CAP theorem (2000), which states that something bad will never happen. In the context of consensus, consistency means participants will never decide on different values, or will always come to an agreement.
Depending on the blockchain or DLT, there are different ways for the network or “group of people who have the magic books” to achieve consensus.
Proof-of-Work
The oldest and most reliable is the Proof-of-Work (PoW) consensus protocol, also called the Nakamoto Consensus.
In simple terms, the Merkle root that is used to link blocks in a chain must be hashed again with a random input, so that the result contains some zeroes. The random input needs to be guessed randomly, so it’s a lot of work (hence the name), and more zeroes means more guess work.
The number of zeroes depends on how many computers are guessing together to arrive at a result within a certain time in order to generate a block or “to go to the next page of the ledger book”. For the bitcoin network, it’s 10 minutes to generate a block. This massive guessing work is what is known as mining. A chain of blocks represents a lot of work, and the longest chain requires the most work, so the longest chain is the most trusted and thus legitimate chain and official ledger.
There is also a rule that says “pages” are valid if the “team” can “write” two pages in succession .As long as there are more computers on the “good guys” side guessing—i.e. 51% of the network—then the “bad guys” would never win… the probability of getting lucky twice in a row is really low! So, the Nakamoto Consensus is a probabilistic solution to the Byzantine Generals Problem. This also means Nakamoto Consensus favours liveness (i.e. all transactions will be settled across all notes) over consistency (i.e. it is possible for nodes to not reach an agreement).
The advantages of Proof-of-Work consensus:
- Provably: the consensus protocol has proven resilience against internal and external attacks for 10 years and counting!
- PoW is highly scalable: the work is automatically adjusted based on size of network via hash-rate (the zeroes needed in the linking hash)
The disadvantages of Proof-of-Work consensus:
- PoW is environmentally disastrous: mining results in very high energy consumption and heat dissipation from the hard-working computers
- PoW is vulnerable to centralisation: due to the scarcity of specialist mining computers (ASIC), miners become de facto central authorities
- PoW is vulnerable to end-of-chain hijacking: formally called the 51% Attack, i.e. if the bad guys cut the queue and formed their own queue and convinced other innocent people that their fake queue is the real queue.
To address the specific drawbacks of Proof-of-Work protocols, a new class of consensus protocol was proposed:
Proof-of-Stake
A PoS algorithm chooses validators to write the next block. Each validator owns some stake in the network, and must lock it in order to be selected:
Some of famous PoS attempts are:
- Casper (Ethereum)
- Ouroboros (Cardano)
The advantages of Proof-of-Stake consensus:
- Speed: Provides faster processing of transactions
- Efficiency: Consumes less energy
- Less hardware: Doesn’t require ASIC
- Agile: Active punishment of dishonest validators
The disadvantages of Proof-of-Stake consensus:
- Lower barrier to attack: a malicious party only needs enough money, unlike PoW where time, expertise, hardware, and electricity are all additionally needed besides money.
- Centralisation & Plutocracy: over time, only the richest stakeholders are permitted to have control of consensus in the blockchain.
- Unknown unknowns: PoS has not existed long enough and thus no one fully understands all its vulnerabilities, such as a plethora of possible attacks—Nothing-At-Stake, Fake-Stake, Spent Stake, Amplified Stake, Long-Range Attack—and possibility that the consensus may not Byzantine fault tolerant under important assumptions (which makes or breaks a decentralised distributed ledger system).
But PoS is not the only one looking to replace PoW as the king of blockchain consensus protocols:
Other Consensus Protocols
A plethora of novel ideas sprung out of the euphoria in the cryptocurrency markets in the last few years:
- Proof-of-Activity
- Proof-of-Authority
- Proof-of-Believability
- Proof-of-Burn
- Proof-of-Capacity
- Proof-of-Caring
- Proof-of-Contribution
- Proof-of-Credit
- Proof-of-Elapsed-Time
- Proof-of-Existence
- Proof-of-History
- Proof-of-Importance
- Proof-of-Relay
- Proof-of-Reputation
- Proof-of-Retrievability
- Proof-of-Service
- Proof-of-Useful-Work
- Proof-of-Value
- Proof-of-Weight
- Delegated-Proof-of-Stake
Many of these are “working” in varying degrees, all of which have not been tried-tested-and-true. So, no one can really say what the disadvantages or vulnerabilities are, or how Byzantine fault tolerant they are under what assumptions.
The commonality of the aforementioned consensus protocols were designed for public blockchains, even if the design may result in a semi-permissioned or de facto permissioned blockchain.
For purpose-built permissioned blockchains (such as R3 Corda or the Hyperledger projects) and consortium blockchains, they can use other special types of consensus, such as pBFT (Practical Byzantine Fault Tolerance) or Raft consensus.
Here is a summary of what blockchains use which protocols for consensus:
Choose your Blockchain
Now that you have this information, what are you going to do with it? Even with the basic understanding of blockchain as a magic shared ledger, you can imagine all the possibilities in applying this magical technology for many of the world’s problems. But now that you had bravely chosen to read on, you are able to make an informed decision on which blockchain to choose for your decentralised application or dapp.
Define ‘Shared‘ in Shared Ledger
One of the most important choices to make as a dapp designer are about sharing and trust:
- Access:
Who can read? Who has permission to use the contents of the blockchain? - Validation:
Who can write? Who has permission to participate in the consensus?
Although permissioned ledgers seem paradoxical to the whole reason for blockchain — a decentralised censorship-resistant system — permissioned blockchains thrive because they are compliant with the strictest regulations. There may be some problem areas that are highly regulated, leaving you without much choice except choosing among the permissioned DLT platforms, but if your problem area is [relatively] lightly regulated, consider a public chain.
Even more Magical Cryptography
The fundamental magic is largely the same for all blockchains. What should be considered is support for privacy preserving cryptography, some next-level magic whose importance will be covered in a summary of the legal and compliance module:
- Commitment Schemes: one can commit to ‘something’ while keeping it hidden, with the ability to reveal this ‘something’ later.
- Ring Signatures: participants can participate in some activity together without revealing their identities.
- Secure Multiparty Computation: participants pass around information to calculate something together without revealing what they are passing around to do the calculation.
- Homomorphic Encryption: a way to do stuff with encrypted data and have the same results as if the data was not encrypted, e.g. perform calculations without passing information around.
- Zero-Knowledge Proofs: a way to prove something without revealing the details needed to make the proof, e.g. being able to prove one is over 18 without revealing one’s birthday.
When choosing a blockchain, consider the support or compatibility for which cryptography you need to work with. For example, it is much easier to implement privacy features for blockchains that use the UTXO model versus the accounts model.
Does the Consensus make sense?
For permissioned blockchains, consensus is relatively simpler because of the setup. For permissionless blockchains, the consensus protocol makes or breaks a dapp. Objectively speaking, the boring and wasteful PoW consensus is the most dependable of public blockchain protocols, with PoS coming in a far second. If choosing a blockchain with an exotic consensus protocol, you must outweigh the risks of working with a protocol that is not widely accepted as secure with the potential of a great fit for your dapp.
What’s next?
Apply what you learned into designing (a) project(s) for the International Blockchain Olympiad. Submit a paper between April 21 and June 9.