Inclusive Block Chain Protocols

Abstract

Distributed cryptographic protocols such as Bitcoin and Ethereum use a data structure known as the block chain to synchronize a global log of events between nodes in their network. Blocks, which are batches of updates to the log, reference the parent they are extending, and thus form the structure of a chain. Previous research has shown that the mechanics of the block chain and block propagation are constrained: if blocks are created at a high rate compared to their propagation time in the network, many conflicting blocks are created and performance suffers greatly. As a result of the low block creation rate required to keep the system within safe parameters, transactions take long to securely confirm, and their throughput is greatly limited.

We propose an alternative structure to the chain that allows for operation at much higher rates. Our structure consists of a directed acyclic graph of blocks (the block DAG). The DAG structure is created by allowing blocks to reference multiple predecessors, and allows for more “forgiving” transaction acceptance rules that incorporate transactions even from seemingly conflicting blocks. Thus, larger blocks that take longer to propagate can be tolerated by the system, and transaction volumes can be increased.

Another deficiency of block chain protocols is that they favor more connected nodes that spread their blocks faster—fewer of their blocks conflict. We show that with our system the advantage of such highly connected miners is greatly reduced. On the negative side, attackers that attempt to maliciously reverse transactions can try to use the forgiving nature of the DAG structure to lower the costs of their attacks. We provide a security analysis of the protocol and show that such attempts can be easily countered.

A Additional Game Theoretic Analysis

1.1 A.1 Safety Level

As the players’ behavior is unknown and can take different courses, one may be interested in the player’s safety level, namely, the minimal utility he can guarantee himself. In the worst case for the player, the rest of the players choose a strategy which minimizes his utility, and the safety level is his best response to such a scenario.

Formally, player i’s safety level is the solution to the zero-sum game, where i is the max-player while the rest of the network acts as his united adversary min-player. The following theorem provides the player with a marginal probability over his memory buffer, which serves as his maxmin strategy for the single-shot game at time t.

Theorem 7

Denote player i’s memory buffer by $w_1,\ldots ,w_m$ (sorted in descending order of their fees) at a time in which it was able to create a block. Denote $\delta := 2\cdot \max _j\{d_{i,j}\}\cdot (\lambda -\lambda _i)$, and for all $q\in \left[ 0,1\right] ^{m}$ define $f(q):=\sum _{k=1}^{m}q_{k}\cdot \left( w_{k}e^{-\delta }\sum _{l=0}^{\left\lceil \frac{k}{b}\right\rceil -1}\frac{\delta ^{l}}{l!}\right)$. Let $q^*$ be the solution of the next linear program: $\max f(q) \text { s.t. } \forall k<m: \ q_{k}w_{k}\ge q_{k+1}w_{k+1} \ ; \ \forall k: \ 0\le q_{k}\le 1 \ ; \ \sum _{k=1}^{m}q_{k}=b.$ Then i’s utility from $q^*$ is at least $f(q^*)$, regardless of the strategy profile of the other players.

The idea behind the proof is to construct a game in which player i chooses transactions for his blocks, while the rest attempt to choose the very same transactions. In the worst case scenario for the player, his rivals correlate their blocks’ contents so as to maximize collisions with i’s blocks. Another worst case assumption is that the delay between the players and i is maximal. Refer to the full version of the paper for a formal construction and proof of the theorem.

1.2 A.2 An Optimal Strategy

The performance of any solution of the game, including those considered thus far, should be compared to the optimal setup. If players would play cooperatively, so as to try and maximize the system’s performance, then all blocks would contain unique transactions, with the top most fees available. Formally, if n blocks were created by the network during some long time period T, then the system’s hypothetical optimal performance, OPT(T), is defined as the sum of the top $n\cdot b$ transactions created within T (this is not necessarily feasible, as high transactions may not be available to early blocks).

Recall that transactions arrive at a rate of $\eta$. Their values are drawn according to some probability vector ${\varvec{r}}$, and we denote by R the corresponding CDF. The rate at which transactions are embedded in the DAG is denoted $\lambda _{out}:= b\cdot \lambda$ (it is the hypothetical optimal throughput).

We define a threshold below which transactions are totally ignored by the players: $v_{thresh}=R^{-1}(1-\frac{\lambda _{out}}{\eta })$. This threshold defines a cutoff,$\theta :=\{j : v_j>v_{thresh}\}$. We claim that if players choose transactions above this cutoff, uniformly, then the resulting social welfare, which is the throughput weighed according to fees, would coincide with OPT(T), as T goes to infinity. We denote the described strategy by UCO (Uniform above CutOff), and by UCO(T) the total weighed throughput achieved by applying UCO up to T.

Proposition 8

Assume nodes have an unlimited memory buffer. Let T be some time window, and denote by n(T) the number of blocks that were created by that time. Then, $\lim \limits _{T\rightarrow \infty } \frac{1}{n(T)}\cdot \mathbb {E}[OPT(T)] = \lim \limits _{T\rightarrow \infty } \frac{1}{n(T)}\cdot \mathbb {E}[UCO(T)],$ where the expectation is taken over all random events in the network and in the realization of UCO.

The intuition behind the result is that choosing a cutoff as we have prescribed implies that the incoming and outgoing rates of transactions to the buffer are equal. Thus, results from queueing theory show that the expected size of the buffer is infinite, and miners always have enough transactions above the cutoff to include in blocks. In particular, for large enough memory buffers, there are effectively no collisions between different blocks, and the transactions in blocks are unique. This surprising result is achieved at a cost: transactions have long expected waiting times for their authorization.