Distributed ledgers as middleware

Middleware: what sits in the middle

Development is hard, good designers rare, applications ever more complex. Middleware is built once for many applications (affording better designers), provides services, and abstracts from the OS.

Its key feature is interoperability: applications on the same middleware work together. But middleware systems are many and incompatible, and making A-applications work with B-applications is the Enterprise Application Integration (EAI) task, with the emphasis on horizontal communication (application-to-application, middleware-to-middleware). Integration is unavoidable: every project inherits legacy systems and adds features without modifying them. The first casualty is conceptual integrity.

Piecemeal growth stays popular (asymptotically cheapest as development time goes to zero). Middleware is an integration technology: to limit conceptual drift it casts a model on heterogeneous applications.

For infrastructure the key issue is the network effect: the value of a technology grows with the number of its adopters. Hence standards consortia (OMG, FIPA, OSGi, W3C) and players pushing de facto standards. The slides then ask: beyond authentication, authorisation, security and shared resources, what about consensus? Should every application write it from scratch (Ch. 6), or should middleware provide it?

DLT as a synchronising layer

Where is synchronisation? The ledger is synchronised, whereas nodes and network are not required to be synchronous. So DLT is expected to work as a synchronising layer for the processes, as middleware can be expected to do.

Open systems rest on shared standards, most generally at the middleware level. ITU (Focus Group on DLT) and ISO (TC 307) produced them, including actors and a reference architecture covering public chains (Ethereum, Bitcoin), private chains (Hyperledger Fabric) and non-blockchain ledgers. Use cases span finance, pharma, medicine, ICT and energy [FG DLT, 2019c]. General benefits:

1. Secure and cost-effective, enabling globally-scalable services.
2. Tamper-resistant and auditable, resistant to systemic failures.
3. Effective at detecting and mitigating fraud.
4. A General Purpose Technology: as a middleware instance it brings gains to other sectors; mass adoption may be slow, but then yields productivity gains across industries.

Specific benefits: transparency and trust among untrusted users, security, disintermediation. ACM has a dedicated journal, Distributed Ledger Technologies.

Blockchain sat in Gartner's Hype Cycle for Emerging Technologies from 2016 and vanishes after 2018, as ITU (2019) and ISO (2020) complete their standards: a sign, for the slides, of maturity and industrial exploitation.

DLT ⊃ BCT (blockchain technology): a blockchain is one way to implement a ledger, and IOTA, Hedera Hashgraph and Corda use none. And blockchain ≠ Bitcoin: the blockchain is a model for distributed, decentralised computation, with diverse implementations, domains and goals; Bitcoin is one implementation, for cryptocurrencies, digitalising and decentralising fiat currency.

From hash chains to a replicated notary

A hash chain keeps track of a sequence of events: event i goes in block b_i, and b_i+1 records H(b_i), so the sequence cannot be altered unnoticed.

Add timestamps and you get a timestamping service: blocks appended (almost) periodically, possibly several events per block, recording what happened and when. Accept only correctly signed events and you get a notary service: who did what and when, with non-repudiation. The slides' applications:

1. orders, shipments and payments between companies (a supply chain);
2. open voting, tracking who voted what;
3. an open registry of public calls and applications;
4. a registry of building ownership and transfers;
5. punching in/out for employees;
6. a cryptocurrency.

In general: whenever parties may want to lie about what they did or when. After each block a resulting state can be computed (in the punch-in example, who is inside).

Run as one logically centralised server (validating events, keeping the chain, storing data), even a redundant one, the notary has a single point of trust: its owner may alter the ordering or timing of events, or exclude someone, with no defence. Hence replication:

1. replicate the notary, each replica controlled by a different party;
2. an event sent to one replica is propagated to all;
3. each replica stores the hash chain and the events;
4. as long as most replicas are not corrupted, tampering is detected (how many? §4);
5. we are replicating the software that validates events: state machine replication.

State machine replication

Computation is stateless when output depends on input only (functions), stateful when (Input, State) → (Output, State′) (objects). A machine is deterministic if its state depends only on the initial state and the input sequence. Randomisers and concurrency break this, and a deterministic machine plus its environment is still non-deterministic overall [Wegner & Goldin, 1999]. Deterministic stateful machines can be arbitrarily replicated and run concurrently if

1. every replica starts from the same initial state, and
2. every replica processes inputs in the same order.

All then move through the same states: notary + replication + a ledger class ≈ a simple cryptocurrency. Condition 2 is the bank-account problem of Ch. 2.

On CAP (Ch. 5): the blockchain basically chooses P and A. Like NoSQL databases (e.g. MongoDB) it provides eventual consistency, “sooner or later, in finite time”, often governed by probabilistic rules (§7).

Why consensus? Alice and Bob update simultaneously through different replicas; the result depends on order, so replicas must agree on one. Byzantine faults (inconsistent views, deliberate lies) can block agreement: three replicas reach an impasse, a fourth may break it. Bad actors have economic incentives; without BFT a replica can alter ordering, exclude events, or block agreement forever.

Consensus is impossible under either assumption:

1. asynchronous network [Fischer et al., 1985], messages arbitrarily reordered or delayed: hence protocols proceed in periodic rounds;
2. f ≥ N/3 Byzantine replicas [Lamport et al., 1982]: hence the fourth replica (N = 4 tolerates f = 1).

Universal SMR

The slides' analogy: UTM : TM = Interpreter : Program = ??? : SMR. Instead of a deterministic program with one business logic (say a bank ledger), replicate an interpreter, a program that executes other programs: Universal State Machine Replication (USMR), whose operations let users deploy, undeploy or invoke programs. Smart-contract-enabled blockchains act as replicated universal state machines (§8).

The blockchain, formally

Replicas R₁…R_N store the ledger; clients C₁…C_M propose updates to any. Users are identified by f(K_pub) (a hash or a CA certificate), their address. Many non-intelligible addresses per user give pseudonymity and decentralisation but invite the Sybil attack; one certified address makes the CA a single point of failure and trust.

The world state is a set of assets with owners; AssetState is application-specific (a balance, custom data). Implementations: account-based (Ethereum), UTXO (Bitcoin), versioned key-value store (Fabric).

A transaction is a proposed state change. Operations are application-specific, but must at least create and update assets; a cryptocurrency has deposit, Value and transfer, UserID, Value.

Blocks are timestamped, hash-linked lists of transactions and (hashes of) their resulting states. A block is a 5-tuple of previous hash, height, timestamp, metadata and transactions:

where r_i^j is the state after tx_i¹…tx_i^j.

What blocks buy

1. replication + hash-chaining ⇝ untamperability of the past;
2. hash-chain + time + ordering ⇝ timestamping/notary service [Haber & Stornetta, 1991];
3. hash-chain + signatures ⇝ accountability, non-repudiation;
4. blocks are published (almost) periodically, every Δt.

In general, lim_n→∞ P[inconsistent(B_i)] = 0: as the number n of successors of block B_i grows, the probability that nodes disagree on its content vanishes.

The first, genesis block is assumed shared by all replicas.

Transaction life-cycle

0. a user U wants to update the system state;
1. compiles the transaction with operation and arguments;
2. signs it with K^U_pr;
3. spreads it to one or more replicas;
4. peers validate it on reception, dropping it if invalid;
5. it is eventually executed, producing an intermediate state;
6. both are included in some block;
7. the block is eventually appended: consensus confirms it, with its transactions.

Block life-cycle · each node, every Δt

1. listens for transactions published by clients;
2. validates and executes them, dropping invalid ones;
3. compiles its local candidate block;
4. takes part in consensus, negotiating the next block with its peers.

Step 4 exists because replicas may be corrupted, or have seen transactions in different orders.

Consensus in blockchains

Identity management decides which consensus is possible:

PBFT [Castro & Liskov, 2002] is the classical answer. An elected leader multicasts each client request; replicas agree in two rounds, prepare and commit; the client waits for f + 1 replies (f = maximum faulty replicas). A suspect leader (timeouts) is replaced by negotiation. The slides' questions: N = 1000 needs order N² messages (all-to-all rounds); fictitious IDs let a Sybil attacker own the quorum. Open systems need something else. Paxos and Raft are in Ch. 6.

Proof-of-Work

Proof-of-Work (PoW), or mining, was conceived against email spam [Back, 2002]; nowadays it endows cryptocurrencies with their value. PoW = computational puzzle + branch resolution strategy.

The computational puzzle

1. miners compete to solve it first, about once every Δt ± ε seconds;
2. the proof is easy to verify and included in the block;
3. only blocks with the proof are valid;
4. the first solver mines the next block;
5. difficulty is variable and controllable.

Bitcoin: from b_i = (ph_i, h_i, ts_i, m_i, tx̄_i) with m_i = 0, while H(b_i) ≥ h_threshold, increase m_i: a hash starting with enough zeros. Ethereum: the block selects parts of a reproducible ∼1 GiB pseudo-random graph, hashed into the block.

Propagation takes time: while honest replicas adopt a block, another replica, uninformed or malicious, may mine a competitor. That is a branch: several versions of the ledger, an inconsistency. Branches are unavoidable, so each replica applies a local rule to pick the true one; if the majority follows it, all eventually select one branch: eventual consistency. Bitcoin uses the longest chain rule: honest replicas consider the longest chain they heard about first. Branches never grow at the same speed, so one gets longer and the other is abandoned, its blocks becoming orphans. Ethereum uses GHOST, Greedy Heaviest Observed SubTree [Sompolinsky & Zohar, 2013].

How likely is an adversary to produce a longer branch faster than everyone else? With r = adversary CP / honest CP (computing power) and n blocks to catch up [Nakamoto, 2008]:

Bitcoin waits n_threshold = 6 blocks, ≈ 1 hour since E[ΔT] = 10 min. The slides: 99.999% secure if the adversary has less than 13% of the total CP.

PoW features

1. competition-based, local, eventually-consistent, stochastic;
2. self-adaptive difficulty, E[Δt] = const, compensating changes in CP (Bitcoin updates h_threshold; Ethereum similarly, plus ASIC-resistance);
3. only CP matters, so it is Sybil-resistant;
4. CP distribution and the majority rule: the 51% attack, and “majority is not enough” [Eyal & Sirer, 2014];
5. E[Δt] = const implies a maximum update frequency 1 / E[Δt].

Why would rational, i.e. selfish miners pay to validate others' transactions? Incentives: the winner gets money created ex nihilo by the protocol. Disincentives: attacks like deliberate branching are not prevented but made extremely costly. PoW, value and security are strictly related:

1. PoW endows the cryptocurrency with its economic value;
2. miners require economic compensation;
3. miners' job is the gasoline of a blockchain system;
4. miners behave honestly as long as it is convenient;
5. it is convenient as long as the cryptocurrency has value.

Swan [2015] names three generations: 1 cryptocurrencies, 2 custom assets, 3 smart contracts. The model so far covers 1–2, with expected applications such as online payments in place of PayPal, smart property, unified medical records, non-censurable social media and news, shared balances among companies, public tenders, naming and access control, voting. Generation 3: data is now stored without single points of trust, but who trusts its producers? Software automation just moves trust to developers; we need trustable agents managing assets automatically.

Smart contracts: programs on the universal machine

SCs act as intermediaries in multi-party workflows, reducing failures from corrupt or selfish operators. Immutability + inspectability + accountability + replication make them trustworthy with critical assets: “the code is always right, the true history is on the blockchain”, fewer disputes, no arbitration. They lack situatedness: data and computation are totally disembodied [Mariani & Omicini, 2013], like the cloud with no single point of trust. N copies of an SC exist, one per replica, but they always compute as one.

Clients get two operations, deploy and invoke:

Deployment

0. initially there are no SCs;
1. a deployment TX carries the source or byte-code and initialises the state; the protocol assigns an address;
2. once confirmed, an instance runs on all replicas, just listening for invocations.

Invocation

1. an invocation TX names the SC address as recipient, with input data;
2. each replica eventually receives and executes it;
3. without exceptions, side effects enter the new intermediate state; otherwise they are dropped;
4. once consensus confirms the block, the computation is actually executed.

Storage is like an object's fields, code like its methods. γ now creates an SC on deploy, updates its state on invoke, updates both balances on transfer; Γ still executes a block's transactions sequentially. This is the Order-Execute architecture [Androulaki et al., 2018].

What about non-terminating programs? The halting problem forbids filtering them, and open systems cannot assume good behaviour, so long computations must be discouraged. Ethereum uses gas; Hyperledger Fabric the Execute-Order-Validate architecture.

1. transactions carry gasLimit and gasPrice;
2. miners may delay low-gasPrice transactions, so users raise gasPrice for priority;
3. each bytecode instruction increases a counter g per a price list [Wood, 2014];
4. if g > gasLimit, an exception reverts the side effects;
5. in any case the issuer pays ΔETH = gasPrice · g;
6. the winning miner redeems ΔETH for its effort.

Computation's economics enter SC design, and SCs are not really Turing-complete: quasi-Turing-complete [Wood, 2014].

The slides' Solidity example:

contract Counter {
  event Increased(uint oldValue, address cause); // event definition
  address owner;
  uint value;
  function Counter() public { owner = msg.sender; }  // constructor
  function inc(uint times) public {                   // API
    for (uint i = 0; i < times; i++) {
      emit Increased(value++, msg.sender);
    }
  }
}

On the chain, Alice deploys it; Bob, Dan and Carl call inc; states show value going 0, 3, 5, events emitted; callers pay gas to each block's miner. SCs are expected to mediate money management (bills, insurance, shares), shared governance (DAOs) and supply-chain tracking, e.g. with IoT:

1. interacting SCs track movements of goods automatically;
2. IoT sensors detect departures and arrivals, so nobody can lie about quantities or timings;
3. SCs pay as soon as movements are detected, or refund if not;
4. founders, creditors, inspectors, end users always know the distribution path, agreeing only on the SC's policy.

The idea: delegate trust-critical decisions to transparent, trustable software agents.

Open issues: an early technology

1. No privacy or secrets. Everything published stays public, SC state included; pseudo-anonymity yields to statistics or machine learning. No secret voting?
2. No randomness. Real randomness makes replicas diverge; block data (timestamp, height, hash) is miner-manipulable. No lottery?
3. Inter-SC communication and re-entrancy. SCs call each other synchronously; non-reentrant code called back can fail, enabling fraud (The DAO [Dupont, 2017]). Is OOP right?
4. Immutability. Buggy or fraudulent contracts cannot be fixed or undeployed, so correct design and formal validation are paramount (and hard with Turing-complete languages).
5. Pure reactiveness. SCs borrow a user's control flow; time-aware but not time-reactive, they cannot schedule computations (no periodic payments).
6. Disembodiment, no concurrency. Computation is logically everywhere and strictly sequential; local computations get replicated globally; SCs cannot parallelise.
7. Cost granularity. Pricing computation is not new (cloud, XaaS), but is per-instruction right? In Ethereum publish-subscribe the publisher pays more [Ciatto et al., 2018].