nLab blockchain

Idea

In computer science, the notion of blockchains — originating in concepts of cryptocurrency, with Wei Dai (1996) (B-money) and Nakamoto (2008) (bitcoin) — refers to linearly ordered log files shared in a network with multiple nodes and without any central authority, which can be added to but are extremely difficult to otherwise modify — as long as a majority of nodes act non-maliciously (see below).

Blockchain can be considered as certain data structure – chain of blocks – which are cryptographically “sealed” by hashes which are for each block added to the next block and which is incremented by one of many parties called nodes which follow a commonly accepted algorithm and each contains a copy of the blockchain (full node) or its essential part. Who adds a block, or whose added block is respected by other nodes is a part of the algorithm (blockchain protocol) and is desirable to be byzantine fault tolerant. The securest algorithm in nontrusted environment (public blockchain) is the proof of work algorithm. Regarding that blockchain is a tool to establish noncentralized record verification it is common to use blockchains to carry records of assets, including cryptocurrencies and other token, off chain assets, credential records, verification proofs and so on. These data and transaction steps belong and are authorized by accounts. Modern blockchain protocols assume also that code handling assets in deterministic manner may be part of the account, when the nodes add new blocks they should also execute the code of the contract, within a blockchain virtual machine; such accounts are called smart contracts and realize in a specific way the idea of smart contracts outlined in theoretical computer science before the blockchain era.

The phrase distributed ledger is sometimes viewed as a synonym. Technically, distributed ledger is the same idea realized in a more general setup where the record may be organized in non-linear structure, for example when the blocks form a DAG (directed acyclic graph) rather than a single chain, with appropriate protocol.

Proof of work

The key idea is that of proof of work. Think of a blockchain simply as a list $[ B_{1}, B_{2}, \ldots ]$ of ‘blocks’. A block $B$ is an unencrypted block of content, which could be anything, together with a cryptographic hash of it (‘signature’) with certain properties.

The key points are the following.

1. The cryptographic hash with the required properties is hard to create, where ‘hard’ means requiring significant computational resources and taking time (e.g. something like prime factorisation). Use of these computational resources to create the hash is referred to as ‘proof of work’.

2. The hash of $B_{i+1}$ depends on the hash of $B_{i}$.

3. The hash of a block depends exactly on its contents: any change in contents will lead to a significantly different hash.

4. It is easy (requires little resources and time) to check that a particular hash has the required properties.

Suppose that we have $n$ nodes in a network. Each node accepts as the current blockchain the longest valid blockchain which it knows of. If a node $X$ adds a block $B$ to a blockchain $L = [ B_1, \ldots, B_m ]$, i.e. succeeds in a creating a hash of some unencrypted block of content, it sends $L' = [B_1, \ldots, B_m, B]$ out to all nodes listening to/connected to it. If the longest blockchain $L''$ which a node $Y$ knows of has length $m$, then upon receiving $L'$ it drops any attempts it is currently making to add a block to $L''$, checks the validity of $L'$, and if it is valid accepts it as the current blockchain.

In such a system, it is extremely difficult for any node to tamper with the blockchain. This is because if it wishes to change the content of a particular block, then because of 2. and 3. it must not only re-create the hash of the tampered block, but also the hash of all blocks after it, as well as the hash of a new block. If any honest node creates the hash of just one new block in the meantime and sends it out to the network, the tampering attempt now has still another block to hash. Because of the computational resources required to create even one valid hash, it is thus highly unlikely that tampering will succeed, and thus a tamperer may soon use up great amounts of resources for no gain. If successful adding of blocks is incentivised appropriately, it is thus more sensible to act honestly.

There are various further details, but this is the rough idea.

Fault tolerance

The intended functioning of blockchain networks relies on most but not necessarily all actors acting reliably/non-maliciously towards the protocol, a situation known as Byzantine fault tolerance (BFT), see eg. Wang et al (2022)

Related concepts

• distributed computing

• smart contract

• Ethereum

• computer science

• high performance distributed ledger

• Telegram Open Network

• virtual machine

References

General

The idea originates with:

• Wei Dai bmoney (1996) [web]

• Satoshi Nakamoto, Bitcoin: A peer-to-peer electronic cash system, 2008 pdf

A foundational/mathematical introductory book from the point of view of (building) a distributed computing system is

• Roger Wattenhofer, The science of the blockchain, Inverted Forest Publishing (2016)

A comprehensive guide for architects of blockchain applications with an attempt at certain level of abstraction of central concepts is

• Xiwei Xu, Ingo Weber, Mark Staples, Architecture for blockchain applications, Springer 2019

The following systematic book written by a several authors offers pretty rigorous handbook on blockchain security issues

• Sachin S. Shetty, Charles A. Kamhoua, Laurent L. Njilla (eds.) Blockchain for distributed systems security, 324 pp. IEEE Press, SMTE Books 2019

See also:

• Wang et al., BFT in Blockchains: From Protocols to Use Cases, ACM Computing Surveys 54 10s (2022) 209 1–37 [pdf, doi:10.1145/3503042]

• Melanie Swan, Renato P dos Santos, Frank Witte, Between Science and Economics, Volume 2: Quantum Computing Physics, Blockchains, and Deep Learning Smart Networks, World Scientific 2020 (doi:10.1142/q0243)

Some key papers in distributed consensus include

• M. J. Fischer, N. Lynch, M. S. Paterson, Impossibility of distributed con- sensus with one faulty process, JACM 32:2, 374-382 (1985)
• M. Castro, B. Liskov, et al., Practical byzantine fault tolerance, Proc. 3rd Symposium on Operating Systems Design and Implementation (1999) 173–186.
• L. Lamport, R. Shostak, M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems, 4/3 (1982), p. 382–401.

Other references on distributed ledgers

• Vitalik Buterin, Ethereum: A next-generation smart contract and decentralized application platform, pdf

• Gavin Wood, Ethereum: a secure decentralised generalised transaction ledger, Ethereum, Tech. Rep. 2017

• Gavin Wood, PolkaDot: vision for a heterogeneous multi-chain framework pdf

• Joseph Poon, Vitalik Buterin, Plasma: scalable autonomous smart contracts, pdf

• Joseph Poon, Tadge Dryja, Lightning network, pdf Mar 2015.

• Vitalik Buterin, Chain interoperability, R3 reports, Sep 2016 pdf

• Tier Nolan, Re: Alt chains and atomic transfers, 2013, bitcointalk discussion post

• Nikolai Durov, Telegram Open Network, 132 pp. Dec 2017 pdf, mirror pdf; Telegram Open Network Blockchain, Sep 2018, 121 pp. pdf; Telegram Open Network Virtual Machine, Sep. 2018, 148 pp. pdf; Fift: a brief introduction (about a new programming language on TON), May 23, 2019, 87 pp. pdf is at channel t.me/Tgram/170

• L. Baird, The Swirlds hashgraph consensus algorithm: fair, fast, byzantine fault tolerance, pdf (May 2016); Hashgraph consensus: detailed examples pdf; Overview of Swirlds Hashgraph: An Introduction To The Hashgraph (SDK Available Now) online; Hedera Hashgraph whitepaper pdf; intro to whitepaper web

• Aggelos Kiayias, Andrew Miller, Dionysis Zindros, Non-interactive proofs of proof-of-work, IACR preprint 2017 pdf (see also here and Cardano, IOHK)

• Mike Hearn, Corda – a distributed ledger (technical whitepaper, 2016) pdf; Brown et al. Corda - an introduction, whitepaper 2016, pdf; Brown, Corda - an introduction platform whitepaper 2018 pdf

• Ittay Eyal, Emin Gün Sirer, Majority is not enough: Bitcoin mining is vulnerable, in: Financial Cryptography and Data Security 436–454, Springer 2014 pdf

For an extended list of references see blockchain (at zoranskoda).

Formal verification

On formal methods for verification of blockchain consensus algorithms (with proof assistants such as Coq or Agda):

• Hedera blog: Formal Methods: The Importance of Being Fault Tolerant in a World with Bad Actors (2018)

• 1st Workshop on Formal Methods for Blockchains (October 2019)

• Musab A. Alturki, Jing Chen, Victor Luchangco, Brandon Moore, Karl Palmskog, Lucas Peña, Grigore Roşu, Towards a Verified Model of the Algorand Consensus Protocol in Coq, Formal Methods. FM 2019 International Workshops. Lecture Notes in Computer Science 12232 (2019) 362-367 [arXiv:1907.05523, doi:10.1007/978-3-030-54994-7_27]

• Quantstamp blog: Formally Verifying Hedera Hashgraph’s Stablecoin Framework (2020)

• Karl Crary, Verifying the Hashgraph Consensus Algorithm [arXiv:2102.01167, pdf]

• Harold Carr, Christopher Jenkins, Mark Moir, Victor Cacciari Miraldo, Lisandra Silva, Towards Formal Verification of HotStuff-based Byzantine Fault Tolerant Consensus in Agda: Extended Version, in: NASA Formal Methods: 14th International Symposium, NFM 2022 Proceedings (2022) 616–635 [doi:10.1007/978-3-031-06773-0_33, arXiv:2203.14711]

• Sudhani Verma; Divakar Yadav; Girish Chandra, Introduction of Formal Methods in Blockchain Consensus Mechanism and Its Associated Protocols, IEEE Access 10 (2022) [doi:10.1109/ACCESS.2022.3184799, pdf]

• Quantstamp blog: Applying lightweight formal methods and SAT solvers to build better blockchain applications (July 2023)

category: computer science, applications