constructive mathematics, realizability, computability
propositions as types, proofs as programs, computational trinitarianism
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.
The key idea is that of proof of work. Think of a blockchain simply as a list of ‘blocks’. A block 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.
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’.
The hash of depends on the hash of .
The hash of a block depends exactly on its contents: any change in contents will lead to a significantly different hash.
It is easy (requires little resources and time) to check that a particular hash has the required properties.
Suppose that we have nodes in a network. Each node accepts as the current blockchain the longest valid blockchain which it knows of. If a node adds a block to a blockchain , i.e. succeeds in a creating a hash of some unencrypted block of content, it sends out to all nodes listening to/connected to it. If the longest blockchain which a node knows of has length , then upon receiving it drops any attempts it is currently making to add a block to , checks the validity of , 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.
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)
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
A comprehensive guide for architects of blockchain applications with an attempt at certain level of abstraction of central concepts is
The following systematic book written by a several authors offers pretty rigorous handbook on blockchain security issues
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
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).
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)
Last revised on July 14, 2023 at 15:55:15. See the history of this page for a list of all contributions to it.