Executing large-scale processes in a blockchain

1.1 Auditing the ledger

A blockchain network can be justifiably regarded as a universally trusted platform for executing processes, as the trust is based solely on good cryptographic assumptions, namely, the quantifiable preimage and/or collision-resistance strength of a cryptographic hash function h( ). Blockchain ledger entries are a record of progression of states of the process. Protocols constructed using a standard cryptographic hash function h( ) make it possible to create an open, distributed, immutable (for past entries), append-only ledger that can be audited by anyone. In other words, the integrity guarantees regarding a process executed on a blockchain network stem from the fact that anyone can reliably audit the entire history of all process states.

However, the fact that anyone can audit a blockchain ledger does not imply that everyone will. To address this issue, some participants are explicitly incentivised to do so. In other words, blockchain participants can be seen as belonging to two broad categories:

1. a small number of incentivised participants, who take an active part in making ledger entries; and

2. a much larger number (typically) of passive participants, who do not take part in the process of making ledger entries, but can nevertheless audit the ledger, if they choose to do so.

Typically, every participant in a blockchain network maintains a copy of the ledger. Periodically, after a set of transactions have been processed, an incentivised user “makes a motion” to add a block to the blockchain. Most often, such a motion passes, and every participant updates their copy of the ledger. The reason that incentivised users do not make motions to add blocks with ill-formed transactions is due to the fact that they have a stake in the correctness of their ledger entries. Two common types of incentive mechanisms (Bentov et al., 2014) include Proof-of-Stake (PoS) and Proof-of-Work (PoW).

In PoS-based (Kiayias et al., 2017) incentive systems, incentivised participants are required to explicitly stake some amount on the correctness of their ledger entries. Any error (deliberate or otherwise) will result in loss of stake.

In PoW schemes (Nakamoto, 2008), the stake is in the form of expensive energy invested by incentivised participants (“miners” in Bitcoin) to solve a computationally intensive puzzle. In general, the puzzle itself has nothing to do with the process executed in the Blockchain. The incentive for miners to ensure correctness of entries is that a miner’s expensive work may be rendered moot if they make an erroneous entry. More specifically, in Bitcoin, solving the puzzle has two purposes: to gain the privilege of adding a block to the Bitcoin ledger; and “mine” a certain number of new Bitcoins. The main shortcoming of PoW incentives stems from growing sustainability concerns (Digital Trends) – the annual energy cost for mining Bitcoins is estimated to be already over a billion dollars (Digiconomist).

While regular Bitcoin users may not solve puzzles, they are expected to audit the well-formedness of every ledger entry. Users who interact only intermittently with the blockchain network can still sync their copy of the ledger by downloading and examining all transactions that occurred since their last sync.

1.2 Cryptographic hash functions

Central to blockchain networks is a cryptographic hash function h( ) for computing a succinct commitment to the ledger. The power of a cryptographic one-way hash function h( ) is deceptively simple – it is simply a mechanism to quantify certainty in the chronological order in which two events occurred. Specifically:

More specifically, given two sequences of bits (or bit-strings) x, y, where h( ) transforms a preimage x∈{0, 1}* (bit-string of any length), to a digest y∈{0, 1}ⁿ (bit-string of fixed length n), one can conclude with a very high degree of certainty that “x existed before y.” More specifically, the uncertainty in such a claim is𝕆 (2⁻ⁿ). In other words, for large enough n (say, n⩾128 bits) it is impractical to choose a digest first, and determine a suitable preimage later.

In current blockchain networks the most commonly employed hash function h( ) is the hash standard SHA-2 with 256-bit digests. The specific utility of the hash function h( ) in a blockchain is that it enables computation of a single hash (a 256-bit SHA-2 hash) α, as the commitment to the entire ledger. More specifically:

1. a Merkle (1987) hash tree is used to compute a commitment (a hash) v_i to each block; and

2. a hash accumulator (Bayer et al., 1993) is used to compute the commitment α to a chain of values v₁, v₂, ….

The explicit consensus between all users (at any specific time) is on the precise value of α. Due to the properties of h( ) (and more complex constructions using h( )), an explicit consensus on α is an implicit consensus on every ledger entry.

1.3 Scalable blockchain processes

The practical utility of executing processes on a universally trusted platform (like a blockchain network) is that such as platform can eliminate, or substantially reduce the scope of, expensive infrastructures in the form of organizations like banks, insurance companies and even governments. However, real-world processes needed to replace such infrastructures may have possibly billions or even trillions of process states. For such large-scale processes, it is impractical for every blockchain participant to audit the complete history of all process states. More specifically, while some active participants may be incentivised (or paid) to audit every transaction, it is impractical to expect passive users, who may only participate intermittently, to do so.

Realizing scalable blockchains calls for strategies that permit passive users to selectively audit the correctness of any specific ledger entry. More specifically, scalable blockchains should strive to reduce the overhead necessary for passive and intermittent participants to perform selective audits.

Second, proactive strategies to eliminate ambiguities are essential for universal consensus, and thus, prevent forking of the blockchain. Consider a scenario where two miners A and B provide two different correct solutions to a puzzle (for adding a block). Such a state can cause forking of the blockchain, where different users may sync up with different forks. The practical implication of a forked ledger is that users following different forks have different interpretation of the truth, namely, the actual state of the process. For example, the state of wallet A and B will be different in both forks (A is the beneficiary of the mined Bitcoins in one fork and B in the other). If the reason for forking is due to an erroneous entry in one fork (e.g. inclusion of an ill-formed transaction), reducing the overhead for selective audits enables passive users to readily identify and follow the correct fork. Reasons for multiple forks without ill-formed transactions can be due to ambiguities in the order of transactions, and possibly even the interpretation of the process.

Third, it is essential to reduce the susceptibility of the blockchain broadcast network to clogging attacks (Oppliger, 1999). One common form of clogging attack involves an attacker sending a transaction with random bits as “signature.” Only after performing expensive asymmetric cryptographic computations to verify the “signature,” will verifiers realize that the signature is invalid. Clogging attacks are an especially serious concern in broadcast networks, as it takes very little effort for an attacker to send random bits, to expend computational resources of a large number of receivers.

This paper proposes multiple strategies aimed at addressing the three requirements above. Specifically:

1. Toward reducing overhead for intermittent passive users to sync up with the current state of the ledger, a hash calendar (Buldas and Saarepera, 2014) is proposed as a better alternative to the hash accumulator.

2. Toward reducing the overhead for selective audits, an ordered Merkle tree (OMT) (Ramkumar, 2014) is used to capture succinct commitments to process states.

3. Two strategies are proposed for eliminating ambiguities that may lead to forking:

   • the first is the use a separate timestamp ledger (TSL); and

   • the second is to interpret any blockchain process as a finite state machine (FSM), where every blockchain transaction is associated with an unambiguous next-state function.

4. Finally, to address clogging attacks, the use of expensive asymmetric cryptography-based digital signatures is eliminated.

The rest of this paper is organized as follows. Section 2 outlines cryptographic protocols for scalable blockchains. Section 3 outlines strategies for:

1. introducing checkpoints in ledger entries to enable selective audits; and

2. unambiguous description of (FSM) next-state functions as explicit predicates – in the form of:

   • preconditions (predicates to commence the state transition); and

   • postconditions (predicates on completion of the transition).

Section 4 outlines the architecture for a scalable blockchain that takes advantage of strategies outlined in Sections 2 and 3. Conclusions are offered in Section 5.

2.1 Merkle hash tree

A binary Merkle (1987) hash tree (Merkle, 1987) of depth d has 2ⁱ nodes at each of the depths 0⩽I⩽d nodes. Figure 1 depicts a tree with depth d = 3. The N = 2³=8 nodes at depth d = 3 are leaf nodes. Internal nodes have two child nodes – a left child and a right child. Specifically, an internal node u i k at depth k is related to its two child nodes u 2 i k + 1 and u 2 i + 1 k + 1 at depth k+1 as follows:

Corresponding to every leaf (non-internal) node at depth d, are d verification objects (VOs), one in each of the levels d, d−1, …, 1. The sets of d VOs u_i of a leaf node u i d are nodes complementary to u i d , as they are commitments to all leaf nodes except u i d .

Typically, a leaf node u i d = h ( L ) , where L is a leaf. Thus, for any leaf L there is a sequence of d hash operations f_bt( ), namely:

In Equation (4), the fact that the output of f_bt ( ) is r is proof that “the leaf L (and the VOs u_i of L) should have existed before the root r was computed.” In other words, given (a tree with) root r, this constitutes proof of existence of the leaf L and its VOs u_i in the tree.

In most blockchain networks, N⩾1 well-formed transactions included in a block are leaves of a Merkle hash tree. The root of the tree v_i is a commitment to the entire block. Existence of the leaf L in the block can be demonstrated by providing a set of log₂ N VOs u that satisfy f_bt (h(L), u = v_i.

In addition, the tree structure also permits efficient incremental updates to the leaves, which is a feature that is not taken advantage of in most blockchain networks. Specifically, given that r = f_bt (h(L), u, proving existence of leaf L, two kinds of incremental updates are possible:

1. leaf update: corresponding to an update of the verified leaf L to L′, the new root is r′ = f_bt (h(L), u; and

2. insertion/deletion of leaves: if a new leaf L_n is inserted to the right of existing leaf L, the new root is r′ = f_bt (h(h(L), h(L_n))), u; if root update r→r′ can be demonstrated to be consistent with inserting a leaf, then an update r′→r is for deleting a leaf.

Thus, a Merkle hash tree permits efficient computation of a commitment (root) to a dynamic set of leaves with practically unrestricted cardinality. For a tree with a billion leaves, 30 hash operations using 30 VOs will be required to verify the existence of a leaf. An additional 30 hash operations (using the same VOs) will be required to update the leaf, or insert a new leaf, or delete a leaf.

2.2 Ordered Merkle tree

In an OMT (Ramkumar, 2014), proof of existence of a leaf can simultaneously convey existence of key-value pairs, nonexistence of key-value pairs and possibly highest/lowest keys.

Each leaf in an OMT is a three-tuple of the form {i, i_n, v_i}. Together, all leaves form collection of key-value pairs with unique keys. In a leaf {i, i_n, v}, i is the unique key in the collection, i_n is the next-key and v_i is the value of the item with key i. For a lone item in the collection with i_n⩽i, i and i_n are respectively the highest and lowest keys (i = i_n for a collection with a single item).

An item with key j can be inserted only if no item with key j currently exists. Nonexistence of key j can be demonstrated by demonstrating existence of a leaf {i, i_n, v_i} such that:

2.3 Hash accumulator

A hash accumulator (Bayer et al., 1993; Ramkumar, 2014) is a dynamic commitment to a growing list of values v₁ … v_n, and is computed as follows:

Specifically, the accumulated hash α_i is a commitment to all values v₁ … v_i accumulated thus far, and the chronological order in which they were accumulated. From the properties of h( ), it is impractical to determine any sequence of values different from v₁ … v_i, for which the accumulated hash is α_i.

In most blockchains, values like v₁, v₂, … are commitments (Merkle tree roots) of blocks. The accumulated hash α is a commitment to the entire ledger.

Given the value of the current accumulated hash α, all values v₁ … v_n are necessary to determine if a specific v_j exists in the list.

2.4 Hash calendar

A hash calendar (Buldas and Saarepera, 2014) can be used to compute a dynamic commitment to growing list of values v₁…v_n…, if new values are added at a constant rate (e.g. v_i is added at time iΔ + τ where τ is the calendar start-time, and Δ is a fixed interval).

The hash calendar is implemented as a Merkle hash tree where leaves v₁…v_n… are added from left to right. In general, when n is not a power of 2, the tree may be seen consisting of up to log₂ n complete subtrees. For example, after 18 intervals (n = 18), the tree can be seen as consisting of two complete subtrees – a tree with 16 leaves, and a tree with 2 leaves. Note that the number of ones in the binary representation of n is the same as the number of complete subtrees. If n = 22=10,110_b the tree will have three complete subtrees with 16, 4 and 2 leaves, respectively.

The dynamic commitment γ to a calendar is the accumulated hash of the roots of all (maximum of log₂ n) complete subtrees.

2.5 TESLA

In the TESLA (Perrig et al., 2000) broadcast authentication protocol, the sender A of a broadcast stream chooses a random value (say) K 0 A , and creates a hash chain { K 0 A ⋯ K L A } , where:

From the properties of h( ), given K i A it is trivial to compute K j ⩾ i A (by repeated hashing j−i times), but impractical to compute K j < i A .

The tail value of the chain K L A is the “public key” of A. It is associated with two additional values: an absolute value of time T and a time interval Δ. The interpretation of this association is that “ K L − i A will remain A’s secret until time T+iΔ.”

A hashed message authentication code (HMAC) for a message M and secret K, namely, μ = HMAC(M, k), is typically a token accompanying a message M. The receiver with knowledge of K on verifying that HMAC(M, k) is the same as the token accompanying the message can safely conclude that the token μ could have been computed only by an entity with the knowledge of the key K.

Consider a scenario where an HMAC σ M = H M A C ( M , K L − i A ) for a message M using value K L − i A from the hash chain was seen before time t = T + iΔ. Later, after time T + iΔ, the value K L − i A from the chain is disclosed, satisfying σ M = H M A C ( M , K L − i A ) . This is proof that σ_M could have been computed only with the knowledge of K L − i A (and only the creator of the chain A could have had knowledge of K L − i A before time t = T + iΔ).

In other words, as long as it is possible for everyone to establish that σ_M was “seen” before time t, everyone can be convinced that the message was sent by A. In such a scenario, σ_M is a digital signature for the message M by A. As we shall see later, one possible approach to ensure that “σ_M was seen before time t” is by employing a timestamping service (TSS) to timestamp the value σ_M. Thus, in conjunction with a TSS, TESLA broadcast authentication becomes a non-reputable digital signature scheme.

In theory, digital signatures based on asymmetric cryptographic primitives do not need to rely on an additional infrastructure for timestamping. In practice, timestamps for signatures are required in any case in scenarios where we need to cater for revocation of keys. Specifically, timestamping is required to ensure that a signature was computed before the key was revoked. Another advantage of asymmetric cryptography-based digital signatures is that they are instantly verifiable. Note that TESLA signatures have to be computed when the key used for computing the HMAC was a secret that can be verified only after the key used for HMAC is made public (along with the signed message/transaction).

This disadvantage of TESLA is perhaps more than offset by its advantages. First, clogging attacks can be effectively addressed. Second, in several evolving blockchain-based application scenarios, transactions may be measurements from sensors or severely resource-limited Internet of Things devices (Xu et al., 2016) that may not be capable of performing asymmetric computations. Third, in the emerging post-quantum computing (Chen et al., 2016) world, asymmetric cryptography may no longer be a viable option anyway.

3.1 Checkpoints

As we saw in the previous section, it is sufficient for ledger entries to be a sequence as transactions as in Equation (9). With this information, while anyone can determine the state of the system S n following n transactions, the overhead may be prohibitive for regular users, especially for large-scale systems with billions of process states.

If it is possible to introduce “checkpoints” corresponding to process states like S i , S i + 1 before and/or after each transaction, then verification of correctness of any specific transaction will involve verification of correctness of the single state change:

An OMT is useful for creating such checkpoints. Specifically, if all process states are considered as leaves of an OMT, then two values s_i and s_i+1 can be seen as commitment to process states before and after the transaction. More specifically, s_i is the root of an OMT whose leaves represent process state S i ; s_i+1 is the root of an incrementally updated OMT, whose leaves represent process states S i + 1 .

In the proposed approach, process states, and all nodes of the OMT with process states as leaves, need to be maintained only by incentivised users. Ledger entries corresponding to every transaction include OMT roots like s_i and s_i+1.

As long as regular users have reliable access to any ledger entry, and if it is possible for users to determine which specific process states were implicated (read/updated or inserted/deleted) in the transaction, they can check the correctness of the state change, by obtaining O ( log 2 N ) VOs from incentivised users.

3.2 An example

As an example, consider a ledger entry:

1. a leaf L_A = {A, A_n, a} showing current balance a in account A, and A_n as the next account number; and

2. a leaf L_B = {B, B_n, b} showing current balance b in account B.

A state-change function is f( ), where s ⟶ f ( T ) s ′ checks if the transaction is well-formed. According to f( ), transaction T = [B, x]_A is considered well-formed only if it is signed by A, and if the balance in account A, a ⩾ x + m + f, where m is a minimum balance requirement, and f is a transaction fee.

Following the transaction, the two leaves need to be updated to (A, a′) and (B, b′), respectively, where a′ = a − x − m − f and b′ = b + x. In other words, using:

1. values A, B included in the transaction T; and

2. auxiliary values I = {a, A_n, b, B_n, VOs} provided by an incentivised user (from leaves and nodes of the OMT maintained by the incentivised user).

1. leaves L_A = {A, A_n, a} and L_B = {B, B_n, b} exist in a tree with root s; and

2. leaves L A ′ = { A , A n , a ′ } and L B ′ = { B , B n , b ′ } exist in a tree with root s′.

4.1 Timestamp ledger

Two types of broadcasts that are timestamped include:

1. [μ, t′]: a TESLA signature (MAC) μ along with an expected time t′ when a transaction (for which μ is a signature) will be sent; and

2. [T, ∑]: a signed transaction T along with signature ∑; in the signature ∑ = {S, K, j, n, t_mac}, K is jth value in the nth TESLA chain of sender S; t_mac is the time at which the MAC was timestamped earlier.

The operator of each portal batches the requests into regular intervals. The operator timestamps each request, and computes an accumulated hash of all (now timstamped) requests received during the current interval. At the end of the current interval, the operator signs the accumulated hash as proof of acceptance of all requests during the interval. The portal broadcasts the stream of all timestamp requests received during the interval along with the accumulated hash and signature for the interval.

The process for creating the TSL involves collating all timestamp requests from possibly multiple portals, and creating blocks corresponding to uniform intervals of time, say Δ_tl. Each entry in a block (a Merkle tree leaf) can be a timestamped TESLA MAC (t_μ, μ, t′), or a timestamped transaction (t_T, T, ∑).

For creation of the TSL one entity is declared to have the power to resolve ambiguities in consensus. Merkle tree roots v 1 t l , v 2 t l , … of blocks created in this fashion (at a fixed rate) are used to construct a hash calendar with dynamic commitment γ t l .

4.2 Blockchain processes and PL

Timestamped signed transactions (t_T, T, ∑) in the TSL are processed by incentivised users to create PL entries. The first step toward this is the verification of signature ∑ = {S, K, j, n, t_mac}, using TSL entry (t_mac, μ, t′≈t_T). Incentivised users, who continuously monitor the broadcast channel, may simply cache broadcasts like (t_T, T, ∑), (t_mac, μ, t′) that are intended to be added to TSL to avoid the overhead of actually accessing the TSL. The process for signature verification using ∑ and μ is outlined later in Section 4.3.

Transactions with good signatures are processed to create PL entries. Every process has a unique identifier Θ. Every process is defined by a set of m state-change functions δ 1 Θ ( ) … τ m Θ ( ) . Broadcast transactions T that trigger a state-change function δ i Θ ( ) explicitly identify the process Θ, function index i and the sender (who signed the transaction), in addition to other process specific values.

The unique process identifier Θ is the root of a static hash tree. The leaves of the static tree are static descriptions of state-change functions δ 1 Θ ( ) … τ m Θ ( ) . Each δ i Θ ( ) can be seen as a mapping:

1. T is the triggering transaction with a timestamp t_T;

2. I are auxiliary values that are not included in the transaction, but are available to incentivised users who maintain all OMT leaves and nodes;

3. the OMT root s is the commitment to the process states before the transaction T; and

4. the OMT root s′ is the commitment to the process states after the transaction T.

Successful execution of a state-change function results in the creation of an entry in the PL. More specifically, the PL consists of blocks created at regular intervals of time, where each block consists of multiple entries of the form:

All well-formed transactions occurring in a specific interval of time are added to a single block as leaves of a hash tree. The sequence of roots of such trees v₁, v₂, v₃, … (one corresponding to each block) is added to the ledger at regular intervals of time using a hash calendar.

Incentivised users may choose to maintain an additional log of auxiliary values I necessary to verify preconditions and postconditions for every transaction.

Given a ledger entry, {t_T, T, s, s′} any user can verify the validity of the signature ∑ by fetching the timestamped MAC μ from the TSL. The user can then proceed to verify the correctness of the state change in exactly the same manner as an incentivised user, except that auxiliary values I necessary to verify that preconditions and postconditions are demanded from an incentivised user.

4.3 Infrastructure for digital signatures

Timestamped transactions of the form (t_T, T, ∑) in the TSL are first verified for a consistent signature ∑ = (S, K, j, n, t_mac). The process for verifying a signature utilizes another TSL entry – a timestamped MAC of the form (t_mac, μ, t′) where t′≈t_T was the expected timestamp of the transaction T. Conveying the expected time t′ is merely to permit incentivised used to cache MAC μ in anticipation. Regular users, however, have the additional overhead for fetching a TSL entry.

The signature ∑ = (S, K, j, n, t_mac) for T is deemed legitimate only if the following predicates are true:

1. the nth chain of user S, associated with a commitment c, start-time T and interval Δ, has not been revoked;

2. μ = h (T, K) and t_mac < T + jΔ, where (t_mac, μ, t′) exists in the TSL; and

3. the result of hashing K repeatedly, j times, is c.

The infrastructure for maintaining parameters associated with different chains of users is itself a blockchain process/application with a unique identifier, say Θ_∑.

4.4 Selective audits by regular users

Let T_b be the start-time of the both blockchain ledgers (TSL and PL). As users know the current time, they are aware of the current number of blocks (say n_t, n_p) in both TSL and PL.

If, for example, n = 274=100,010,010_b (where bits 9, 5 and 2 are one) the user expects a calendar hash γ n to be accompanied by two values r₅ and r₉, satisfying:

If the next time the same user utilizes the ledger is at a time when n′ = 308 = 100,110,100_b the user expects γ n ′ along with values r 3 ′ , r 5 ′ , r 6 ′ and r 9 ′ where r 9 ′ = r 9 , r 5 ′ = r 5 , and r 5 = r 5 ′ and r₃ should be nodes in a tree with root r 6 ′ . VOs for verifying this fact can also be demanded from active users.

Thus, using a calendar hash permits intermittent users to check the validity of the current calendar hash against previously known values. Consequently, passive users store only minimal state information (past commitments to log₂ n calendar hashes), and are not required to fetch every single block to verify the validity of the current calendar hash γ n .

The trust in the correctness of γ n can be leveraged verifying the commitment v_i to any block in the past, by requesting up to log₂ n VOs. With trust in the correctness of v_i, the user may demand the entire block, or a specific entry, or the last m entries, etc., along with VOs for existence proofs in a tree with root v_i.

Once users have authentic copy of a specific leaf in a specific PL block, namely, a PL entry {t, T, s, s′}, they can proceed to check the correctness of the state change s→s′ triggered by transaction T as described in Section 4.2.