BlockGraph: a scalable secure distributed ledger that exploits locality

Abstract

Distributed public ledgers, the key to modern cryptocurrencies and the heart of many novel applications, have scalability problems. Ledgers such as the blockchain underlying Bitcoin can process fewer than 10 transactions per second (TPS). The cost of transactions is high, and the time to confirm a transaction is in the minutes. We present the BlockGraph, a scalable distributed public ledger inspired by principles of computer architecture. The BlockGraph exploits the natural locality of transactions to allow publishing independent transactions in parallel. It extends the blockchain with three new transactions to create a unified consistent ledger out of essentially independent blockchains. The most important change is the introduction of the blockstamp transaction, which essentially checkpoints a local blockchain and secures it against attack. The result is a locality-based, simple, secure, sharding protocol which keeps all transactions readable. This paper introduces the BlockGraph protocol, proves that it is consistent and can achieve many thousands of TPS. Using our implementation (a small extension to Bitcoin core) we demonstrate that it, in practice, can significantly improve throughput.

Introduction

Bitcoin [1] has proven to be a successful cryptocurrency using a distributed public ledger. It has spawned significant interest, research, and investment with new applications constantly appearing. However, there are several issues holding it back, particularly with respect to applications which require significant throughput. Some of the most important limitations are:

• A low ceiling on transactions per second (TPS). By design [1], stability in the ledger is maintained by limiting the number of TPS to ~10/sec.

• The cost per transaction is quite high—costing more than a dollar per transaction [2]—and consuming a measurable portion of the world’s energy output [3].

• The time to confirm or finalize a transaction is on the order of many minutes.

Our goal is to tackle the above limitations without sacrificing any of the positives, i.e., its stability, security, transparency, and no required central authority.

We propose the BlockGraph, a distributed public ledger which extends the blockchain and exploits the natural locality involved in transactions between parties. The BlockGraph is motivated by the observation that most transactions between parties occur within a community. If I do business with someone in Pittsburgh, there is generally no need for someone in Beijing to keep track of my transaction in Pittsburgh. Occasionally, I might travel to China in which case I might want to take the output of a transaction that originated in Pittsburgh and spend it in Beijing, but that is rare. The BlockGraph makes the common case, transaction in a locality, fast and inexpensive, while easily supporting the less usual case of transferring tokens from one locality to another. This locality of spending is analagous to temporal and spatial locality in memory systems [4]. It led us to borrow three of the great ideas from computer architecture [5]:

• The principle of locality: with respect to the blockchain, parties to a transaction are likely to repeat (i.e., temporal locality) and parties they transact with are also likely to interact with each other (i.e., spatial locality).

• Make the common case fast and rare case correct: to exploit locality we partition the public ledger into sub-ledgers where transactions within a locality do not need to be broadcast outside the locality. The less common case of globe-spanning transactions is handled by a series of transactions that keep the sub-ledgers consistent and result in a consistent global ledger.

• Performance from parallelism: since transactions in one locality do not interfere with other localities, the sub-ledgers can be maintained in parallel; resulting in a significant increase in system-wide throughput.

There have been many proposals to scale distributed public ledgers (see Sect. 2 for a review). Common to all the approaches which preserve world readability of all transactions is that they require transmitting all transactions across the entire network and require verification to potentially access all previous transactions. Our approach is to weave together a consistent ledger from separate ledgers using a protocol similar in spirit to cache coherence protocols used on multi-processor systems. We introduce a pair of transactions which together “invalidate” tokens on one sub-chain and safely include them on another. These are tied together with a checkpoint-like transaction which both secures sub-chains and provably ensures that the entire ledger remains consistent and tokens never get lost, even if large parts of any sub-chain get orphaned. The new protocol creates a consistent global ledger even when most transactions are transmitted to a subset of the network and verification is provably only required to inspect a subset of the transaction history. In this paper we show how this protocol can be applied to the blockchain, but it could also enable other types of distributed public ledgers to improve performance by exploiting locality.

The blockGraph overview

The BlockGraph is organized as a tree of blockchains. All transactions are either intra-chain, i.e., both parties are on the same blockchain, or between two chains where the two chains are on levels d and $d+1$ in the tree. All blocks in the BlockGraph, along with their implied edges, form a semi-lattice. To keep things clear and simple for this paper we will generally refer only to a 2-level system with a root chain at level 0 (which we will call the global chain) and children at level 1 (which we will call local chains). In this simplified system all transactions are either within a chain, or between a local chain and the global chain. Our protocol allows blocks to be added to a local chain independently of all the other local chains. In principle, miners on a local chain only have to keep a history of their own chain. Though, in practice, they will want to track the global chain.

The throughput of the BlockGraph is highly dependent on the amount of locality exhibited in the transactions. When a significant percentage of transactions are intra-chain, then N local chains will support a distributed public ledger with almost N-times as many TPS as the blockchain. When the intra-chain transactions are also all between parties that are close together in network space (e.g., all in the same geographical area), then the latency across the network diameter will be smaller than the entire Internet and thus the inter-block time can shrink significantly without sacrificing robustness as compared to the blockchain. Thus, a BlockGraph with N local chains which divide the network into N equal-sized pieces and a significant locality could support more than N-times speedup over the blockchain. We analyze the exact limits in Sect. 6.

The key to the feasibility of the BlockGraph is the protocol which keeps the various local chains consistent with each other. There are two pieces to this protocol. The first is a method of transferring tokens between chains. It involves notifying the source chain of an intent to transfer (ITT) to another chain (which invalidates the address on the source chain so it cannot be double-spent) and a cross-domain payment (XDP) on the destination chain which makes the address valid on that chain. The second addition to the protocol, the blockstamp (BSP), is a method of checkpointing a block (and all its ancestors) on a child chain so that the only way the checkpointed block can be orphaned is if the history of the parent chain is also re-written. This ensures the safety of small localities with limited hashpower since the BSP lends them all the hashpower of their parent chain as well.

Scaling with transparency

One advantage of the BlockGraph over other methods of scaling the blockchain is that even though local transactions can proceed to be written independently of other local chains, the transactions are still part of the entire public record. This is in sharp contrast to, for example, protocols built around micro-payment channels [6]. Consider a public ledger for prescription drugs. In this application, the prescriber would create a prescription for a patient using the patient’s public key. In addition to the amount of medicine and number of refills, the dosage and instructions on how often to take the medicine could be included in the transaction that is recorded on the ledger. The patient would fill their prescription by transferring one refill to the pharmacy. The remaining amount remains under the patient’s control. In most cases, all of these transactions would happen on a local chain which no one ever need see outside of the local area.

However, if the patient is in another city, or state, and needs to refill the remaining part of their prescription, they can use an ITT on their local chain to indicate they are moving part of their prescription to the global chain. Then, they may add an XDP on the global chain to actually move the prescription to the global chain, followed by an ITT on the global chain to indicate they are moving it to another local chain, and finally, an XDP on the chain in their new city to move the prescription to the local chain where they want to fill their prescription. The transparency between all chains allows this movement between chains, while still supporting many concurrent and fast transactions. In fact, with more than 120 prescriptions filled per second [7] in the United States, a public ledger modeled on Bitcoin would clearly not work. However, using a local chain per metropolitan area, a BlockGraph based ledger could easily handle the traffic.

Outline

We start with a review of the related work in the next section. We describe the BlockGraph Protocol in Sect. 3 and then describe the new verification procedures in Sect. 4. We demonstrate that these rules ensure that the separate local chains create a consistent unified ledger. In Sect. 5 we show that the new blockstamp transaction can make local chains as secure as today’s single blockchain. We discuss the theoretical bounds on throughput in Sect. 6 and the actual implementation and its throughput in Sect. 7.

Related work

Many blockchain designs and proposals over the last decade have sought to support both a higher verification rate and a higher transaction rate. Many of these proposals increase throughput by increasing overall work (and/or storage costs), hiding information, or using some form of admission control for miners. None of them exploit locality or provide security through a checkpoint mechanism. We group these proposals into four areas: extending the ledger data structure beyond a chain, adding side-chains (e.g., a second layer), making the ledger permissioned, and finally, sharding.

Trees and DAGs

DAG-based blockchains aim to increase throughput and decrease block intervals via explicitly allowing forked blocks to coexist and envisioning various consensus algorithms. Some improvements include GHOST [8] protocol’s heaviest subtree rule, original Ethereum’s version of GHOST [9] that accepts limited ancestry, Inclusive Blockchain’s [10] modification to allow transactions in uncle blocks, SPECTRE’s [11] total ordering of blocks and transaction inclusion algorithms, and IOTA’s [12] application of DAG to single transactions rather than blocks. These approaches all permit fast production of blocks without losing security, but they are limited by the network’s ability to support high volumes of blocks. As blocks arrive at higher frequencies and forks become more prevalent, it would be inevitable for multiple blocks extending the same parent to include repeated information, hence preventing unbounded scalability for the system. Furthermore, they do not reduce verification effort (some even increase it) nor communication costs.

The BlockGraph takes a different approach by increasing parallelism without duplicating information and limiting the structure of the ledger to a lattice. Furthermore, it is agnostic to the consensus mechanism so it could be integrated into the above DAG-based systems.

Off-chain transactions and sidechains

The idea of increasing throughput by allowing transactions that are not on the main chain is not new. Off-chain micropayment channels achieves this by hiding some transactions from the main chain. For example, the Lightning Network [6] uses these channels to enable high transaction rates between pairs of users. The Plasma blockchain [13], designed originally to supplement Ethereum, uses complicated proofs of fraud to avoid having to reveal all information happening on sidechains. Orthogonal work on cross-chain swaps [14, 15–16] handles token exchanges between different kinds of blockchains. In some sense, these examples exploit division of responsibility or temporal locality to increase throughput between a portion of the parties, but at the cost of hiding information from the public ledger.

Sidechains establish chains additional to the main chain. The “Pegged" sidechains [17] explores mostly symmetric two-way pegs where security relies on a contest period of a day or two, introducing significant cost to finalizing transactions. Another sidechain approach is to introduce some form of control in who is allowed to mine/validate certain transactions. The Liquid [18] sidechain to Bitcoin makes use of Strong Federations, and blocks are produced by a group of signers who are incentivized to cooperate in the blockchain. The Cosmos [19] blockchain uses sidechains safeguarded by variants of Byzantine Fault Tolerance (BFT) methods and a maximum of a few hundred mostly initially known validators per sidechain.

Permissioned blockchains

Scalability of blockchains is heavily researched also under a permissioned model, where participants are known and identities are generally dealt with via Membership Service Providers (MSP) and Public Key Infrastructures (PKI). Some related systems include Hyperledger Fabric [20], Vegvisir [21], CAPER [22], and SharPer [23]. As an example, SharPer treats its overall ledger as a union of its clustered views and applies Paxos and BFT for consensus under crash-only and malicious settings, respectively. However, the critical paths of consensus protocols using a similar class of techniques only scale well to hundreds of nodes [24]. This makes them more applicable for permissioned blockchains or committee-voting permissionless blockchains. The BlockGraph instead focuses on the large-scale permissionless setting without relying on voting algorithms within limited committees.

Sharding

Sharding approaches are generally identified by the technique of splitting the processing of transactions among smaller sections of nodes known as shards or committees. The BlockGraph appears at first glance to be just another sharding proposal in that they share the idea that validators work on only a portion of the ledger. However, with traditional sharding the validators of transactions are assigned without regard to the inputs or outputs of each transaction and they are changed periodically. In fact, validator assignments usually assume the random oracle model for security analysis. The BlockGraph instead assigns validators to the same chain, and the transactions they are responsible for remain determined by the inputs and outputs. In sharding the relationship between the shards is that of peers, and transactions can flow from any shard to any shard. The BlockGraph restricts the different chains to be organized as a tree and the graph of blocks forms a lattice. In the general case, sharding does not restrict the graph of transactions, so storage and communication costs scale with the size of the entire network. And, depending on the number of shards, cross-shard communication overhead on the network can become heavy and costly [25]. Furthermore, it can be problematic to ensure that all data is available to everyone [26]. In the BlockGraph, on the other hand, communication and storage costs for local chains scale with the size of the local chain network. When a local chain is formed around a geographical area, communication latency can also be reduced.

As a result of our protocol to coordinate between chains, the BlockGraph also carries different security implications from other sharding protocols. Some recent approaches to solving these problems include ELASTICO [27], RapidChain [28], and Ethereum 2.0 [29]. These approaches discuss adaptive adversaries to different degrees (e.g., slowly adaptive adversaries for RapidChain and round-start adaptive adversaries for ELASTICO), but the problem of fully adaptive malicious actors remains unsolved. One other consideration is that of incentives. In ELASTICO and RapidChain, each participant solves a PoW per epoch; in Ethereum 2.0, each participant stakes a constant number of ethereum tokens per round. Honest players are not incentivized to contribute as much PoW or PoS as possible, whereas malicious may have the incentives. A consequence is that Sybil attacks are mitigated but not eliminated. On the other hand, due to the lattice structure of the chains and the blockstamp protocol, The BlockGraph does not introduce any additional concerns about adaptive adversaries and Sybils on top of its global chain.

Summary

The BlockGraph we present here offers a perspective on the blockchain’s scalability problems that is different from the above proposals. It harnesses locality to increase parallelism, decreases communication costs, decreases storage costs, and decreases verification work. It allows the entire hashpower of the global chain to be used to protect the smaller local chains. It avoids requiring admission control and ensures that all transactions remain public. It may also, by supporting smaller local chains with smaller inter-block gaps, slow down the increasing tendency towards centralization [30].

The BlockGraph protocol

In this section, we detail extensions to the blockchain that enable it to support a BlockGraph. There are three new transactions which are used to create a consistent single logical ledger out of the tree of ledgers. In addition, we extend the nameserver architecture so users and miners can locate chains.

Local chains and localities

The BlockGraph is a distributed public ledger organized as a tree of blockchains. Each individual chain behaves essentially the same as the blockchain used in Bitcoin, i.e., it behaves similarly to how it was original described in [1]. The three new transactions are the Intent To Transfer (ITT) transaction, the Cross Domain Payment (XDP) transaction, and the blockstamp (BSP) transaction. With two exceptions (XDPand BSP), each chain in the BlockGraph records transactions between parties where all the inputs to the transaction are outputs of a previous transaction on the same chain. And, with one exception (the ITT), all the outputs of a transaction on a particular chain will be consumed within that chain.

We think about each chain as the ledger for a particular locality or community whose members are expecting to do business with one another. As long as transactions happen among members of a community, they stay on the same chain, which we refer to as the local chain. While the BlockGraph protocol is agnostic about the use of a local chain, we envision two common scenarios:

1. Geographic localities: a chain for a geographic locality will be used to record all the transactions between parties within a physical area. These areas are likely to be, but do not have to be, political entities, such as Europe, New York State, Pittsburgh, or even smaller units such as Peking University.

2. Interest-based communities: any group of users who are likely to interact could form a locality, e.g., players of an MMORPG, fans of a sports league, employees of a company, etc.

[See PDF for image]

Fig. 1

A set of blockchains comprising a BlockGraph. Dotted lines indicate a reference from the genesis block of a child chain to the genesis block of its parent

Each locality is represented by a separate chain with its own genesis block, as shown in Fig. 1. The genesis block of a local chain contains a reference to its parent chain. The last difference between a local chain in the BlockGraph and the blockchain as used in Bitcoin is that there are no coinbase transactions for blocks in the local chain. All tokens on a local chain originate on the parent chain and will have been moved to the local chain using an XDP transaction, as described in Sect. 3.3.

[See PDF for image]

Fig. 2

Interaction between blockstamps and the longest-chain rule on local chains. Even though the chain ending in A is longer, the chain ending with B is blockstamped by the global chain and thus it is the consensus chain

Consensus

Just as in Bitcoin today, consensus is recognized using the longest chain rule. However, to ensure consistency between all the local chains and their parent chains, the consensus rule is augmented for a local chain: the consensus chain is the longest chain that includes the block referenced by the most recent BSP on the parent chain. See Fig. 2 for an example. This requirement ensures that there will never be transactions on the parent chain which reference a transaction in a block that was orphaned on a local chain. This rule also reduces the verification work since miners on one local chain never need to validate another local chain1. Furthermore, as we explain in Sect. 3.3, this implicitly adds the hashpower of miners on the parent chain to the local chain, ensuring that even small communities remain secure from double-spend attacks.

New transactions

Here we describe the three new basic transaction types and introduce a compound transaction as a further optimization.

Intent To transfer (ITT) On any chain, in order to move tokens to a different chain, an ITT transaction must be included in a block on the source chain to indicate the intent to move a token off the chain to another chain. The ITT has three types of outputs: local fees, parent fees, and transfer amount. The local fee goes to the local miner which includes the ITT on the local chain. If the ITT is moving money up the tree, i.e., from a local chain to a parent chain, then the parent fee goes to the miner of the parent chain who includes a BSP(see below). Finally, the transfer amount specifies the amount of tokens being transferred to the destination chain. Unlike traditional Bitcoin transactions, the parent fee and transfer amount are considered spent on the chain on which the ITT is published, but unspent on the destination chain. A reference to the destination chain is included in the ITT.

X-Domain payment (XDP) An XDPtransaction moves tokens from another locality to the chain on which it is included. The inputs to an XDP are outputs from one or more ITTs that are on another chain. If the XDP is moving tokens from a child to a parent chain, then the source ITTs must all be in an ancestor-or-self2 of a block that has been blockstamped. Once the XDP is included on a chain, then its outputs can be used on that chain.

Blockstamp (BSP) A parent chain can checkpoint a child chain by including a BSP transaction on the parent chain which references a block on the child chain. We call the referenced block a stamped block. The BSP marks the stamped block and all of its ancestors as valid with respect to the block in which the BSP is included on the parent chain. In other words, as long as the block containing the BSP is not orphaned, the stamped block on the child chain cannot be orphaned. Miners of any local chain will ignore forks not containing the most recently stamped block.

To ensure consistency and reduce validation work, the protocol requires that inputs referred to on a child chain in an XDP be an ancestor-or-self of a blockstamped block. (See, for example, the situation in block D in Fig. 3.) To create an incentive to create BSP transactions, the miner that includes a BSP will collect the parent fees in all the ITTs that occur in all the blocks following the previously stamped block up to and including the block being stamped by the BSP.

X-Domain and transfer (XAT) The XAT combines an XDP and an ITT to take an input from another chain and immediately signal an intent to transfer it to another chain. This combined transaction is used to decrease the overhead of transfering tokens from one local chain to another, by requiring only a single transaction on the global chain. Thus, ITT and XDP will only be needed at the source or destination chain respectively. For example, XDP#1 and ITT#2 on the global chain in Fig. 3 could be combined into a single XAT.

[See PDF for image]

Fig. 3

Example of moving tokens from one locality (#1) to another (#2)

Example cross-chain transaction

All the standard transactions on the blockchain work as they do today for intra-chain transactions. The interesting case, introduced by the BlockGraph, is a transaction between chains. As an example, let us consider the situation in Fig. 3 where Alice is transferring a token on the chain for Locality 1 to Bob on the chain for Locality 2.

1. Alice signals her intent to transfer a token from Locality 1 by issuing an ITT, which is included in block A. This marks the inputs to the ITT as spent. Additionally, the parent fee and transfer amount are also marked as spent in Locality 1, but unspent in the Global locality.

2. In block C, a global miner includes a checkpoint to block B from Locality 1, a descendant of block A. This transaction “locks in” all transactions that happened before block B. (And, the miner of block C collects the parent fee from ITT#1.)

3. A global miner can now include Alice’s XDP in global block D. Alice’s XDP has as inputs, the transfer amount from ITT#1.

4. Alice then issues ITT#2 using the outputs of XDP#1 which is included in Block E.

5. Finally, a local miner in Locality 2 will be willing to include XDP#2 (shown in block F) which effects the transfer of the outputs of ITT#2 to the local chain for Locality 2.

Notice that because of our augmented local chain rule, if block A is orphaned (causing ITT#1 to disappear), then so will all references to the outputs of ITT#1 since orphaning block A requires the orphaning of block C (since it contains a BSP to a descendant of block A). We discuss the new verification rules introduced by the BlockGraph more completely in Sect. 4.

Incentives

The BlockGraph protocol is set up so that miners are partitioned between local chains and parent chains. (Of course, a single entity could mine blocks on multiple chains.) By dividing up the pool of miners we have reduced the total hashpower available on any one chain. To make this protocol work, it is essential that global miners include BSP transactions to local chains. Without the BSPtransactions the tokens on the local chains cannot be moved off the chain and are also more easily attacked. To address this the parent fee goes to the global miner that creates the first BSP to a block that is a descendant-or-self of the block containing the ITT. As more and more outstanding ITTs accumulate, the incentive to mine a BSP becomes greater, which matches up perfectly with more and more requests to move tokens off the chain.

Even if no one wants to move tokens off the local chain, it is in the interest of the users of the chain to get a BSP to their chain to make it more secure. In this case, someone might include an ITT with a parent fee (but no transfer amount) to encourage a global miner to create a BSP to their chain. Local miners are the most likely party to do this since it is in their interest to maintain the security and liquidity of the chain on which they mine.

Network

Transactions and blocks in the BlockGraph are broadcast on peer-to-peer networks, where each chain is associated with a single network. Thus, there is a global network for the global chain, and a local network for each local chain. Furthermore, both local and global miners will need information from more than one network. So, they will have to listen in on multiple networks.

[See PDF for image]

Fig. 4

An example of how miners might participate on the various overlapping peer to peer networks involved in maintaining the BlockGraph. Each rectangle represents one node. The filled in square indicates the primary network on which the node is mining, the white square indicates which additional network(s) it is listening to

In addition to full nodes and lightweight nodes we introduce the listening node, which maintains enough information about another chain to do the proper validation for the primary chain with which it is concerned. It is somewhere between a full node and a lightweight node in terms of what it must store. In most cases, nodes mining a local chain will maintain a full node for the locality and a listening node for their parent chain. This is the case for the local miners shown in Fig. 4. They need the listening node in order to correctly validate XDPs and check for BSPs to their chain. Global miners that are full nodes today would have to have at least a listening node for each locality for which they publish XDPs and BSPs . They also need to maintain information back to previously validated BSP from all other localities to validate new BSPs into those chains, i.e., the easiest way to do this would be to maintain listening nodes for all localities. Since the percentage of transactions that appear on any chain (global or local) shrinks significantly compared to a system where all nodes verify all transactions, the total storage cost for all types of nodes will decrease.

In order for nodes to find the network for each locality, we extend the nameserver to include a way to register and find IP-addresses for miners in each locality. The hash of the genesis block for the locality is used to locate a subset of the current miners. Since the network is now divided the nameservers become more important to the system as a whole. We recognize that the extensions to the nameserver inevitably amplifies the importance of its security and reliability. One approach would be for nameservers to act as listening nodes for the global chain as well as local chains. This would allow them to automatically track the creation of new localities by reading ITTs from the published blocks and the IP addresses of the local miners for each locality. In this way, the nameserver could detect malicious requests to register local chains.

Genesis

Creating a new local chain is a matter of creating a genesis block with a reference to the new chain’s parent chain. The new locality is registered with a nameserver which maps the hash of the genesis block to the IP-address of the initial miner. Then, the creator of the genesis block sends, to the parent chain, an ITT with its destination set to the new chain. Once the ITT has been published on the parent chain, the local miner can create the second block on the new chain with an XDP whose inputs are the outputs from the above ITT published on the parent chain.

Verification on the BlockGraph

In this section we describe the new validation procedures required of both local and global miners. We then show that these procedures, along with the new transactions, are sufficient for creating a single consistent ledger from all the chains in the BlockGraph.

Notation

A transaction, $\tau$ , has the following properties:

• $type(\tau )$ refers to the type of $\tau$ and it is one of $\{\text{P2PKH},\text{ITT},\text{XDP},\text{BSP}\}$.3

• $inputs(\tau )$ refers to the set of input transactions of $\tau$ .

• $block(\tau )$ refers to the block that includes $\tau$ .

• $stamp(\tau )$ refers to the block that $\tau$ stamps if $type(\tau )=\text{BSP}$.

A Block, B, has the following properties:

• $C=(B_0,\cdots ,B_h)$ denotes a blockchain, where $B_i$ is a block and $B_0$ is the genesis block. A correct chain will have $\forall 0\le i\le h,Verify(B_i)$. $\mathit{Verify}$ is described in Algorithm 1.

• We write $\tau \in B$ if $\tau$ is a transaction included by block B, and we write $\tau \in C$ if $\exists B_i$ included on chain C such that $\tau \in B_i$.

• For referencing ancestor blocks on the same chain: $$parent(B_i)=\left\{\begin{array}{cc}0,\hfill & i=0\hfill \\ B_{i-1},\hfill & i>0\hfill \end{array}\right)$$

• We write $B_1\prec B_2$ if $B_1$ is one of the ancestors of $B_2$ and $B_1\preccurlyeq B_2$ if $B_1$ is an ancestor-or-self of $B_2$, i.e., $B_1\prec B_2$ or $B_1=B_2$.

• $G=(C_0,\{C_i\}),1\le i\le n$ denotes a BlockGraph, where $C_0$ denotes the global chain, and $C_i,1\le i\le n,$ each denotes a local chain.

• $isStamped(B)$ if $\exists \tau \in C_0:stamp(\tau )=B$.

Block verification

The original global blockchain is able to verify new blocks as they form or arrive without having to revisit previously verified blocks. Similarly, with our specification of verifying the new transactions, we may show correctness of an entire chain based on verification of the latest block, stated as follows.

Theorem 1

Let $B_i,B_j$ be two blocks such that $B_i\preccurlyeq B_j$, then $Verify(B_j)\Rightarrow Verify(B_i)$

Proof

This is true by an inductive argument with respect to the height of $B_j$. In the base case, $B_j$ is a genesis block and its only predecessor is itself, so the implication must be true. In the inductive step, we assume that

$\forall B_k\prec B_j,\forall B_i\preccurlyeq B_k,Verify(B_k)\Rightarrow Verify(B_i)$

With the block verification algorithm, we know that since $Verify(B_j)$ and it is not a genesis block, we have either $Verify(parent(B_j))$ or $isStamped(parent(B_j))$. In the case of $isStamped(parent(B_j))$, let $\tau \in C_0$ such that $stamp(\tau )=parent(B_j)$. We know that $Verify(block(\tau ))$ is true, verified by the global miners who confirmed the $\text{BSP}$ transaction. It then follows that $Verify(\tau )$ and thus $Verify(parent(B_j))$ by Algorithm 2. The local verifier can choose to believe this is indeed verified based on the depth of this blockstamp transaction, or verify again the block that $\tau$ points to, $parent(B_j)$, is valid. Either way, we arrive at

$Verify(parent(B_j))$

Since $parent(B_j)\prec B_j$, we can conclude by induction hypothesis that $\forall B_i\preccurlyeq parent(B_j),$$Verify(B_i)$. Also, since $Verify(B_j)\Rightarrow Verify(B_j)$, we have $\forall B_i\preccurlyeq B_j,Verify(B_j)\Rightarrow Verify(B_i)$. $\square$

Theorem 2

Let $\tau$ denote a transaction on $C_0$ with $type(\tau )=\text{BSP}$. Then, $\forall B\preccurlyeq stamp(\tau ),$$Verify(\tau )\Rightarrow Verify(B)$

Proof

Let $\tau$ be such that $type(\tau )=\text{BSP}$ and $Verify(\tau )$ is true. By Lines 10–15 of Algorithm 2 we then have $Verify(stamp(\tau ))$. By Theorem 1 we conclude $\forall B\preccurlyeq stamp(\tau )$, $Verify(\tau )\Rightarrow Verify(stamp(\tau ))\Rightarrow Verify(B)$. $\square$

From this we may also see the importance of the BSP as it demonstrates the global approval of the stamped block and all of its ancestors.

Transaction verification

Transaction verification on the BlockGraph is essentially similar to the blockchain with the caveat that the inputs to all existing transactions must come from the chain on which they are published. Likewise, verifying an ITT is the same as verifying an existing transaction. This is shown in Lines 2–8 of Algorithm 2.

Differences come in when verifying XDP and BSP transactions. There are two cases for the XDP: (1) when its inputs come from a local chain as in Lines 17–24 and (2) when its inputs come from the global chain (see Lines 26–27). In the former case, it is required that the inputs to the XDP being verified must be on the same local chain and in blocks that are an ancestor-or-self of a block that has been blockstamped. Notice, that because of Thm 2, there is no need to re-verify that the ITT transaction itself is valid, since that is guaranteed by the BSP (as shown in Lines 10–15).

Theorem 3

Let $\tau$ be a transaction in a BlockGraph, then $\forall {\tau }^{\prime }\in inputs(\tau ),Verify(\tau )\Rightarrow Verify({\tau }^{\prime })$

Proof

To show this we only need to consider the case when $type(\tau )=\text{XDP}\wedge \tau \in C_0$, since the other types of transactions already require the validity of previous transactions.4 We may first let ${\tau }^{\prime }$ denote the input transaction such that$$\begin{array}{c}\hfill \left\{\begin{array}{c}\{{\tau }^{\prime }\}=inputs(\tau )\hfill \\ type({\tau }^{\prime })=\text{ITT}\hfill \end{array}\right)\end{array}$$Suppose $Verify(\tau )$, then we know there exists a global blockstamp into the locality containing ${\tau }^{\prime }$. Let this blockstamp transaction be denoted ${\tau }_b$, then we know the following from our algorithm:

$block({\tau }_b)\prec block(\tau )$

$block({\tau }^{\prime })\preccurlyeq stamp({\tau }_b)$

Using our previous conclusions, since the previous block of the new block must already be valid, we have the following:$$\begin{array}{cc}& \text{Verify(parent(block(}\tau \text{))}\hfill \\ \hfill & \Rightarrow \text{Verify(block(}{\tau }_{\text{b}}\text{)) by ancestry relation}\hfill \\ \hfill & \Rightarrow \text{Verify(}{\tau }_{\text{b}}\text{) by block verify}\hfill \\ \hfill & \Rightarrow \text{Verify(stamp(}{\tau }_{\text{b}}\text{)) by BSP verify}\hfill \\ \hfill & \Rightarrow \text{Verify(block(}{\tau }^{\prime }\text{)) by ancestry relation}\hfill \\ \hfill \end{array}$$This confirms that the input ${\tau }^{\prime }$ to the XDP transaction $\tau$ on the global chain must be valid. $\square$

The algorithms here intentionally omit the details of matching the signature scripts, the pubkey scripts, etc., which do not change from the protocol used on the blockchain. What is different is that the outputs of an ITT are considered spent on the chain it is published in, but unspent on other chains.

[See PDF for image]

Fig. 5

Blocks $D\dots E$ have been orphaned because they do not include Block $A=stamp(\text{BSP}\#1)$

[See PDF for image]

Fig. 6

The source for the XDP#1, ITT#1 in Block A, has become orphaned, but so has block C as the longest chain rule on the global chain made the chain with G the consensus chain. And, the local chain now ends at block E

Consistency

The key result that comes from our approach is that it is never possible for the inputs to an XDP on the consensus global chain to ever become orphaned. In other words, tokens are never lost nor gained due to forks in either the global or local chains. Here we consider two cases to make this clear. In the first case, we show that the use of the BSP means that local miners never need to verify other local chains. This arises from the fact that an XDP on the global chain must follow the BSP which checkpoints the local chain that is the source of the tokens used in the XDP. If the XDP is on the global chain, then the BSP is on the global chain, which means—due to our modification to the consensus rule—that the ITT which is the source of the tokens is still guaranteed to be on the local chain that is the source of the tokens. Figure 5 shows an example where the longest chain in Locality 1 would end at Block E, but because of the BSP in Block B, the consensus chain ends at F. The BSP also makes it impossible for inputs to the XDP in block C to somehow become invalid, since the only way for the ITT in Block A to become orphaned is if the BSP in block B becomes orphaned. But in that case, as shown in Fig. 6, block C also becomes orphaned and there is no inconsistency.

[See PDF for image]

Fig. 7

Local miners must always check all blocks back to the block (labeled B here) immediately following a blockstamped block

The second example we look at, as shown in Fig. 7, is when an ITT on the global chain becomes orphaned. In this case, an XDP on the local chain will become invalid. To ensure consistency the local miners must check all blocks back to the most recent blockstamped block on their chain and the blocks on the global chain back to the block containing its BSP. In Fig. 7 block F has been orphaned and as a result, block C and its descendants are no longer valid. To detect this a local miner must check back to the block immediately following the most recent blockstamped block, block B in this case as it immediately follows block A which is blockstamped from block E on the global chain.

Clearly, both local and global miners will want to wait for some confirmation period so as to avoid having to redo work.

Verification work

Because of how we use BSPs , the extra verification work local miners have to do is bounded by the number of blocks following a blockstamp. Global miners have work proportional to the number of local chains they monitor. Most importantly, local miners never have to look at other local chains and a global miner only needs to verify a local chain back to the block most recently blockstamped from the global chain. In summary, compared to systems which can require the history of any previous transactions to verify a transaction, the local and global miners in the BlockGraph will have less verification work to perform.

Security

Here we consider how the BlockGraph affects the security of the ledger. We assume that there is sufficient hashpower on the global chain that it can be treated similarly to the current blockchain and attacking it will have a similar probability of success as discussed in [1] and further explored in [31]. Local chains are a different story as they are likely to have significantly less relative hashpower than is available to the total system.

[See PDF for image]

Fig. 8

Attacking a block that is an ancestor of a blockstamped block necessitates an attack on both the global and the local chain, as shown by the red blocks (Color figure online)

Double spends

There are two cases which need to be analyzed to understand the viability of a double-spend attack on a local chain. In the first, if the attack requires the replacement of a blockstamped block (e.g., Block A in Fig. 8), then the attacker must also fork out the BSP on the global chain. More formally,

Theorem 4

Let $G^t=(C_0^t,\{C_i^t\})$ denote a BlockGraph at time t, where $\tau$ is a BSPtransaction on the global chain. Then

$\forall u>t,block({\tau }^{\prime })\preccurlyeq stamp(\tau )$$\Rightarrow \mathbf{Pr}[{\tau }^{\prime }\notin G^u]\le \mathbf{Pr}[\tau \notin G^u]$

Proof

This result is immediate from the blockstamp properties we’ve shown previously. $\square$

In other words, once a block on a local chain is blockstamped, then attacking it or any of its ancestors is at least as hard as attacking a block on the global chain. The second case is an attack against a block that is not the ancestor-or-self of a blockstamped block. In this case, the attacker is racing against honest miners on the local chain before the next BSP stamps a block on the chain. It can be shown that since the local chain is likely to have a limited amount of hashpower available to it, an attacker can w.h.p. execute a double-spend attack against blocks that have not been blockstamped. Using the current system, where any node is allowed to join the mining pool, confirmation will have to wait until a block is blockstamped. Alternative rules for admitting miners to the local mining pool, for example, using Proof-of-Stake [32, 33–34] or requiring a maximum ping distance should be explored.

We expect that users of a local chain will prefer that BSPs occur frequently and so our throughput analysis assumes the worst case—i.e., a blockstamp to every local chain in each global block.

Irrational attacks

If an attacker is not out for gain, but rather to disrupt the system, then it is easier to attack a local chain in the BlockGraph than the blockchain in Bitcoin. For example, an attacker may perform excessive mining on some local chain and intentionally starve ordinary transactions from being included in the chain. Solving this problem, particularly for smaller localities, may require exploring alternative methods of admitting miners to the mining pool or detecting denial of service (DoS). Similar problems also exist for current blockchains in use, as they have to live with various attempts at DoS and employ mitigations [35]. On the other hand, users on a local chain can pay for more security by creating incentives for global miners to create blockstamps to the local chain. With blockstamps securing the local chain, the local chains are no more at risk than the global chain, or today’s blockchain.

[See PDF for image]

Fig. 9

The throughput speedup ratio compared to the case of one global chain, assuming $r_i=r_g$ and local transaction ratios $v_i$ are equal for different localities

[See PDF for image]

Fig. 10

The throughput speedup ratio compared to the case of one global chain, assuming $r_i=\sqrt{N}\times r_g$ and local transaction ratios $v_i$ are equal for different localities

Throughput on the BlockGraph

To measure throughput, we first define our model as follows.

We let $G=(C_0,\{C_i\}),1\le i\le N$ denote a BlockGraph as specified in Sect. 4.1. Note that there are N localities, excluding the global chain, in BlockGraph G. Further, we use an N-vector $\mathbf{v}$ to denote the local transaction ratio on each locality. Specifically, $v_i$ denotes the proportion of transactions in $C_i$ that have both inputs and outputs on the same chain, i.e., not one of the new transactions introduced by the BlockGraph. If the global chain is the bottleneck for supporting inter-locality transactions, then $C_i$ may have partially empty blocks whose proportion of local transactions is still $v_i$. Note that cross-locality payments from the same local chain can be batched together so as to decrease global chain load and increase $v_i$, if desired.

For our analysis here, we enforce a maximum transaction generation rate for each chain, measured in TPS. $r_g$ denotes this rate for global chain and $r_i$ for local chain $C_i$. For reference, with a minimum transaction size of 166 bytes [36], a 1MB maximum size per block, and a 10-minute block interval, Bitcoin’s transaction rate has an upper bound of $\frac{1\text{MB}/166\text{bytes}}{10\times 60}=10.5$ TPS.

Finally, we define throughput of the BlockGraph as the number of user-intended TPS supported by the system. That is, a transaction with inputs and outputs on the same chain counts as one user-intended transaction. If a user intends to move tokens from one locality to another, then the two ITTs and two XDPs will collectively count as one user-intended transaction.

We can derive throughput approximations for a BlockGraph of N local chains and varying amounts of non-local transactions.

Theorem 5

Given N localities, global transaction generation rate $r_g$, local rates $r_i$, and intra-locality proportions $\mathbf{v}$, then the theoretical maximum throughput5 of BlockGraph is$$\begin{array}{c}\hfill r=\left\{\begin{array}{cc}{r}_g\left(\frac{1}{2},+,\frac{{\sum }_{i=1}^N{r}_i{v}_i}{{\sum }_{i=1}^N{r}_i(1-v_i)}\right)\hfill & r_g<{\sum }_{i=1}^N{r}_i(1-v_i)\hfill \\ r_g+{\sum }_{i=1}^N{r}_i\left(\frac{3}{2},v_i,-,\frac{1}{2}\right)\hfill & r_g\ge {\sum }_{i=1}^N{r}_i(1-v_i)\hfill \end{array}\right).\end{array}$$

To clarify what the above demonstrates, we computed some examples of the upper-bound on the throughput speedup over a singular chain, as shown in Figs. 9 and  10. Intuitively, the bends in the figures signify a transition from congestion on the global chain to a throughput limit simply due to the number of local chains. When a large proportion of transactions are transfers between chains, the global chain is filled with ITTs and XDPs , making the system bottlenecked. In this case, the total throughput is then scaled with respect to the capacity of the global chain, as computed via the first case in the theorem. Otherwise, throughput may be computed by the second case. Note that we could optimize this throughput for the case when the global chain is the bottleneck by using XATs instead of the XDP–ITT pair.

Using parameters from today’s blockchain, the throughput that could be directly supported by a 2-level BlockGraph in which the global chain is the bottleneck, each chain is blockstamped on every global block, and 0.1% of the transactions are non-local is $\sim 8,600$ TPS. Using the XAT transaction (instead of an XDP and an ITT) on the global chain yields $\sim 15,000$ TPS.6 We now discuss how we derive the throughput calculations.

Proof We consider two scenarios here:

The first scenario is when transactions on global chain consist solely of XDP, ITT, and BSP, we may consider the global chain as the bottleneck for BlockGraph’s throughput. Since each inter-locality user-intended transaction has 2 out of 4 transactions on global chain and the other two on local chains, the global chain is our bottleneck if the rate of non-local transactions on fully operating localities exceeds the rate of transaction generation on global chain. That is,$$\begin{array}{c}\hfill r_g<\sum _{i=1}^N{r}_i(1-v_i).\end{array}$$Here, we have two types of user-intended transactions that we need to take into account.

1. Inter-locality user-intended transactions. For each, we have one XDP and one ITT on the global chain. Since the global chain does not contain other transactions, the total rate is at most $$\begin{array}{c}\hfill \frac{r_g}{2}\end{array}$$

2. Intra-locality user-intended transactions. We may measure these indirectly by examining how empty a locality is scaled to be. The scale factor is the same as global chain generation rate divided by the rate of non-local transactions if localities are fully operational. Note that this ratio is less than 1. In total we have $$\begin{array}{c}\hfill \frac{r_g}{{\sum }_{i=1}^N{r}_i(1-v_i)}\times \sum _{i=1}^N{r}_i{v}_i\end{array}$$

Combining gives$$\begin{array}{c}\hfill r=r_g\left(\frac{1}{2},+,\frac{{\sum }_{i=1}^N{r}_i{v}_i}{{\sum }_{i=1}^N{r}_i(1-v_i)}\right)\end{array}$$In the second scenario, the local chains are the bottleneck.$$\begin{array}{c}\hfill r_g\ge \sum _{i=1}^N{r}_i(1-v_i).\end{array}$$We have three types of user-intended transactions.

1. Inter-locality user-intended transactions. For each, we have one XDP on one locality and one ITT on another locality. Since all localities operate with full blocks, we may compute the rate as follows. $$\begin{array}{c}\hfill \frac{1}{2}\sum _{i=1}^N{r}_i(1-v_i)\end{array}$$

2. Intra-locality user-intended transactions on global chain. This is the global chain capacity apart from the piece used for inter-locality transactions: $$\begin{array}{c}\hfill r_g-\sum _{i=1}^N{r}_i(1-v_i)\end{array}$$

3. Intra-locality user-intended transactions on local chains. We may compute this directly: $$\begin{array}{c}\hfill \sum _{i=1}^N{r}_i{v}_i\end{array}$$

Again, combining gives$$\begin{array}{c}\hfill r_g+\sum _{i=1}^N{r}_i\left(\frac{3}{2},v_i,-,\frac{1}{2}\right)\end{array}$$$\square$

Implementation and experiments

The BlockGraph as presented in this paper has been implemented from a fork of the C++ implementation of Bitcoin core [37]. We modified less than 7K lines (less than 1% of the code base), to include changes to the nameserver code as well as support for local chains, the new transactions, and verification. Our code is available at github.com/seth4618/bitcoin-graph/tree/forpaper-2021.

A BlockGraph local chain miner runs a full node for the local chain and a listening node for the global chain. These two nodes communicate with each other to support validation of ITT, XDP, and BSP transactions. In our experiment, a global chain miner consists of a full node for the global chain and a listening node for every local chain.

We construct a virtual network with our modified nameserver that supports the registering of new local chains. The nameserver listens to the network to maintain a database which maps chains to the IP addresses of the known miners on that chain. For our experiment each miner is run in its own Docker container and the inter-block time for local chains is half that of the global chain. When a miner wants to create a new locality, it creates a genesis block pointing to the global chain, it then sends an ITT to the global chain to transfer tokens to the newly created chain, referred to by the hash of the genesis block. Once the ITT is published, the miner registers the genesis block with the nameservers. Users of and potential miners for this chain can then obtain the IP address(es) of miners on this chain from the namerservers.

We evaluate our implementation by setting up a network with a global chain and the appropriate number of local chains. We reduce the time to run each experiment by reducing the block size so each block can contain about 20 transactions and set the inter-block interval to 30 seconds for the global chain and 15 seconds for the local chains. We then build a graph of 3000 transactions and partition it into the appropriate number of localities. We run the transactions on a network of only a single chain, and then with a global chain and 2 to 4 local chains. A separate Docker container issues the transactions to the appropriate miners. We then compare the time it takes to complete the same set of transactions (partitioned appropriately) on k-local chains to the bitcoin case of a single chain.

Figure 11 shows the speedup for completing all the transactions on a Blockgraph with k chains to a single blockchain as the percentage of local transactions changes from about 60 to 99%. The dashed lines represent the predicted speed-up based on the analysis done in Sect. 6. The solid lines are the results obtained by our small Docker network running our implementation. The knee on each curve occurs at the transition from the local chains being the bottleneck (the second scenario from Theorem 5) to when the global chain is the bottleneck (the first scenario from Theorem 5). Our experiment used separate XDP and ITT transactions on the global chain. Using XAT on the global chain would push the knee of the curve towards the left, improving overall performance.

[See PDF for image]

Fig. 11

Comparison between experimental results (shown in solid lines) when $2r_g=r_i$ compared to the theory (shown in dashed lines)

Conclusion

The BlockGraph is a locality aware distributed public ledger that supports high throughput while reducing communication, verification, and storage costs. Local chains serving different communities can each proceed to add transactions to their ledger in parallel. Three new transactions weave these local chains into a consistent unified ledger where all transactions are transparent. The key to the security behind this system is the blockstamp transaction which allows smaller local chains to “borrow” the total hashpower of the global chain.

By creating independent local chains which can be checkpointed by a global chain, it sets the stage for reducing the cost and power consumption of transactions by supporting different, potentially less power intensive, verification methods on the local chains, and yet keeping the overall security of the global chain. We show how this simple protocol of signaling intent to transfer from one chain, blockstamping that chain, and then performing the transfer can be used to extend the blockchain. Future work to investigate how this could be applied to other layer-1 ledger designs could bring signficant rewards.

The BlockGraph increases throughput and potentially lays the groundwork for reducing the cost of transactions. It, however, does nothing to reduce confirmation time—risk-averse users will still want to wait, as they do today, for several blocks on the global chain to be created after the block containing their transcation, or the blockstamp to their local chain.

Declarations

Conflict of interest

The authors declare that they have no conflict of interest.

1

Likewise, global miners will also have less work, since they only need to verify the global chain and the local chains for which they are generating BSPs

2

An ancestor-or-self block is the block or any of the block’s ancestors. Likewise, a descendant-or-self block is the block or any of its descendants.

3

We use P2PKH as a canonical stand-in for all Bitcoin transactions, e.g., P2SH, Multisig, etc. since their semantics do not change on the BlockGraph as their inputs and outputs are all intra-chain.

4

Recall that XDP on local chains do not have special requirements on its ITT inputs on the global chain.

5

We do not count the small portion of BSPs on the global chain. And, this analysis is worse case in that we do not account for the advantage of using XATs .

6

These numbers include the space that BSPs take up on the global chain, unlike the theorem.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system. bitcoin.org. (2008). https://bitcoin.org

2. Croman, K., Decker, C., Eyal, I., Gencer, A., Juels, A., Kosba, A., Miller, A., Saxena, P., Shi, E., Sirer, E., Song, D., Wattenhofer, R.: On scaling decentralized blockchains (a position paper). In: Rohloff K, Clark J, Meiklejohn S, Wallach D, Brenner M, Ryan P (eds) Financial Cryptography and Data Security - International Workshops, FC 2016, BITCOIN, VOTING, and WAHC, Revised Selected Papers, Springer-Verlag, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp 106–125, https://doi.org/10.1007/978-3-662-53357-4_8, international Workshops on Financial Cryptography and Data Security, FC 2016 and 3rd Workshop on Bitcoin and Blockchain Research, BITCOIN 2016, 1st Workshop on Advances in Secure Electronic Voting Schemes, VOTING 2016, and 4th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2016; Conference date: 26-02-2016 Through 26-02-2016(2016)

3. Stoll, C; KlaaBen, L; Gallersdörfer, U. The carbon footprint of bitcoin. SSRN Electron. J.; 2019; [DOI: https://dx.doi.org/10.2139/ssrn.3335781]

4. Denning, PJ. The locality principle. Commun. ACM; 2005; 48, 7 pp. 19-24. [DOI: https://dx.doi.org/10.1145/1070838.1070856]

5. Patterson, D., Hennessy, J.: Computer Organization and Design, 5th edn. Morgan Kaufmann (2013)

6. Poon, J., Dryja, T.: The bitcoin lightning network: Scalable off-chain instant payments. (2016). https://lightning.network/lightning-network-paper.pdf

7. Audit INP: Number of retail prescription drugs filled at pharmacies by payer. (2020). www.kff.org/health-costs/state-indicator/total-retail-rx-drugs

8. Sompolinsky, Y; Zohar, A. Secure high-rate transaction processing in bitcoin. Financ. Cryptogr. Springer Lecture Notes Compt. Sci.; 2015; 8975, pp. 507-527.3395041 [DOI: https://dx.doi.org/10.1007/978-3-662-47854-7_32]

9. Buterin, V.: Ethereum: a next-generation smart contract and decentralized application platform. (2015). https://github.com/ethereum/wiki/wiki/White-Paper

10. Lewenberg, Y; Sompolinsky, Y; Zohar, A. Inclusive block chain protocols. Financ. Cryptogr. Springer Lecture Notes Comput. Sci.; 2015; 8975, pp. 528-547.3395042 [DOI: https://dx.doi.org/10.1007/978-3-662-47854-7_33]

11. Sompolinsky, Y; Lewenberg, Y; Zohar, A. Spectre: a fast and scalable cryptocurrency protocol. IACR Cryptol. ePrint Arch.; 2016; 2016, 1159.

12. Popov, S.: The tangle. White paper 1(3) (2018)

13. Poon, J., Buterin, V.: Plasma: scalable autonomous smart contracts. plasma.io. (2017). www.plasma.io/plasma.pdf

14. Herlihy, M.: Atomic cross-chain swaps. In: Proceedings of the 2018 ACM symposium on principles of distributed computing, pp. 245–254. (2018)

15. Herlihy, M., Liskov, B., Shrira, L.: Cross-chain deals and adversarial commerce. VLDB J. 1–19 (2021)

16. Zakhary, V., Agrawal, D., Abbadi, AE.: Atomic commitment across blockchains. (2019). arXiv preprint arXiv:1905.02847

17. Back, A., Corallo, M., Dashjr, L., Friedenbach, M., Maxwell, G., Miller, A., Poelstra, A., Timón, J., Wuille, P.: Enabling blockchain innovations with pegged sidechains. (2014). blockstream.com/sidechains.pdf

18. Nick, J., Poelstra, A., Sanders, G.: Liquid: a bitcoin sidechain (2020)

19. Kwon, J., Buchman, E.: Cosmos whitepaper. (2019). v1.cosmos.network/resources/whitepaper

20. Androulaki, E., Barger, A., Bortnikov, V., Cachin, C., Christidis, K., De Caro, A., Enyeart, D., Ferris, C., Laventman, G., Manevich, Y., et al.: Hyperledger fabric: a distributed operating system for permissioned blockchains. In: Proceedings of the thirteenth EuroSys conference, pp 1–15 (2018)

21. Karlsson, K., Jiang, W., Wicker, S., Adams, D., Ma, E., van Renesse, R., Weatherspoon, H.:Vegvisir: A partition-tolerant blockchain for the internet-of-things. In: 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), IEEE, pp. 1150–1158 (2018)

22. Amiri, MJ; Agrawal, D; Abbadi, AE. Caper: a cross-application permissioned blockchain. Proc. VLDB Endowment; 2019; 12, 11 pp. 1385-1398. [DOI: https://dx.doi.org/10.14778/3342263.3342275]

23. Amiri, M.J., Agrawal, D., El Abbadi, A.: Sharper: Sharding permissioned blockchains over network clusters. In: Proceedings of the 2021 International Conference on Management of Data, pp 76–88 (2021)

24. Stathakopoulou, C., David, T., Pavlovic, M., Vukolić, M.: Mir-bft: high-throughput robust bft for decentralized networks. (2019). arXiv:1906.05552

25. Tao, Y., Li, B., Jiang, J., Ng, HC., Wang, C., Li, B.: On sharding open blockchains with smart contracts. In: 36th IEEE International Conference on Data Engineering, ICDE 2020, pp. 1357–1368. IEEE, Dallas, TX (2020). https://doi.org/10.1109/ICDE48307.2020.00121

26. Skidanov, A.: Unsolved problems in blockchain sharding. (2018). medium.com/nearprotocol/unsolved-problems-in-blockchain-sharding-2327d6517f43. Accessed 15 April 2020

27. Luu, L., Narayanan, V., Zheng, C., Baweja, K., Gilbert, S., Saxena, P.: A secure sharding protocol for open blockchains. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 17–30. ACM, New York (2016). https://doi.org/10.1145/2976749.2978389

28. Zamani, M., Movahedi, M., Raykova, M.:Rapidchain: Scaling blockchain via full sharding. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, pp. 931–948. New York, N Y(2018). https://doi.org/10.1145/3243734.3243853

29. Buterin, V .: Ethereum 2.0 mauve paper. (2016). cdn.hackaday.io/files/10879465447136/Mauve%20Paper%20Vitalik.pdf

30. Chohan: The limits to blockchain? scaling vs. decentralization. (2019). https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3338560

31. Rosenfeld, M.: Analysis of hashrate-based double spending. CoRR abs/1402.2009. (2014). http://dblp.uni-trier.de/db/journals/corr/corr1402.html#Rosenfeld14

32. Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: A provably secure proof-of-stake blockchain protocol. In: Annual International Cryptology Conference, Springer, pp. 357–388 (2017)

33. King, S., Nadal, S.: Ppcoin: peer-to-peer crypto-currency with proof-of-stake. self-published paper. (2012)

34. Vasin, P.: Blackcoin’s proof-of-stake protocol v2. (2014). blackcoin.co/blackcoin-pos-protocol-v2-whitepaper.pdf

35. Vasek, M., Thornton, M., Moore, T.: Empirical analysis of denial-of-service attacks in the bitcoin ecosystem. In: International conference on financial cryptography and data security, Springer, pp. 57–71 (2014)

36. Tschorsch, F; Scheuermann, B. Bitcoin and beyond: a technical survey on decentralized digital currencies. IEEE Commun. Surv. Tutor.; 2016; 18, 3 pp. 2084-2123. [DOI: https://dx.doi.org/10.1109/COMST.2016.2535718]

37. bitcoincoreorg: Bitcoin core integration/staging tree. Github Repository. (2021). https://github.com/bitcoin/bitcoin