Scroll

Categories

Tags

Monthly Archives

Keyword

Back

# PHANTOM 1:INTRODUCTION

2018.04.05

## Tags

#### 1. 介绍

##### A. 比特币协议

The Bitcoin protocol instructs miners how to create blocks of transactions. The body of a block contains new transactions published by users, a proof-of-work puzzle, and a pointer to one previous block. The latter rule implies that blocks naturally form in a tree structure. When creating his next block, the miner is instructed to reference the tip of the longest chain within the tree and ignore the rest of blocks (aka orphans). Miners share and propagate a block immediately upon receiving or creating it, and reference the latest block in the chain they observe. The security of Bitcoin relies on honest nodes being sufficiently connected so that when one miner extends the chain with a new block, it propagates in time to all honest nodes before the next one is created.

Fig. 1: An example of a block DAG G. Each block references all blocks to which its miner was aware at the time of its creation. The DAG terminology, applied to block H as an example, is as follows: $past(H) = {Genesis,C,D,E}$ – blocks which H references directly or indirectly, and which were provably created before H; $future(H) ={J,K,M}$ – blocks which reference H directly or indirectly, and which were provably created after H; $anticone(H) = {B,F,I,L}$ – the order between these blocks and H is ambiguous. Deciding the order between H and blocks in $anticone(H)$ is the main challenge of a DAG protocol. $tips(G) = {J,L,M}$ – leaf-blocks, namely, blocks with in-degree 0; these will be referenced in the header of the next block

DAG术语，以块H为例子，如下所示：
$past(H) = {Genesis,C,D,E}$ - H直接或间接引用，并且很可能在H之前创建的块;
$future(H) ={J,K,M}$ - 直接或间接引用H，并且很可能在H之后创建的块;
$anticone(H) = {B,F,I,L}$ - 这些块与H之间的顺序是不明确的。 决定H和$anticone(H)$中块之间的顺序是一个DAG协议的主要挑战。
$tips(G) = {J,L,M}$ - 叶块，即入度为0的块; 这些将在下一个块的头部中引用

In order to guarantee this property, the creation of blocks is regulated by the protocol to occur once every 10 minutes. As a result, Bitcoin suffers from a highly restrictive throughput in the order of 3-7 transactions per second (tps).

##### B. PHANTOM 协议

In this work we present PHANTOM, a protocol that enjoys a very large transaction throughput compared to Bitcoin. PHANTOM structures blocks in a Directed Acyclic Graph, a blockDAG. Rather than extending a single chain, miners in PHANTOM are instructed to reference all blocks in the graph (that were not previously referenced, i.e., leaf-blocks). An example of a blockDAG, and the basic terminology, is provided in Figure 1 above. The core challenge of a DAG protocol is how to order transactions embedded in it, so that in case of two (or more) conflicting transactions, we can accept the one that arrived first (according to the prescribed order) and reject the other(s). To that end, PHANTOM relies on the interconnectivity of honest nodes (similarly to Bitcoin’s assumption in slow rates). Since cooperating PHANTOM miners propagate their blocks as soon as possible and reference all of their counterparts’ blocks, we should expect to see in the DAG a well-connected cluster of blocks. In contrast, blocks that were mined by non-cooperating nodes will appear as outliers and will easily be discerned. Indeed, deviation from PHANTOM’s mining protocol comes in the form of (i) withholding a new block for a while, or\and (ii) creating a new block that does not reference other blocks available at the time, both cases in which the new block can be recognized and penalized. Following this intuition, together with the assumption that honest nodes hold a majority of the hashrate, we argue that the largest set of blocks with good inter-connectivity was mined by honest nodes, with high probability. Accordingly, given a blockDAG, we would want to solve the following optimization problem:

Maximum $k$-cluster SubDAG ($MCS_k$)
Input: DAG $G= (C,E)$
Output: A subset $S^* \subset C$ of maximum size, s.t. $|anticone(B)\cap S^*| \leq k$ for all $B\in S^*$.

Here, $anticone(B)$ is the set of blocks in the DAG which did not reference B(directly or indirectly via their predecessors) and were not referenced by B(directly or indirectly via B’s predecessors). The parameter k is related to an assumption that PHANTOM makes regarding the network’s propagation delay; this is explained in detail in Section 4, following the formal framework specified in Section 3.

In practice, the Maximum k-cluster SubDAG is NP hard (see problem [GT26] in [2]). PHANTOM works therefore with a variant of this problem, using a greedy algorithm approach. The algorithm will be given in Sections 2, and some interesting variants in Section 6.

Once the set of honest and dishonest blocks are properly recognized by the protocol, we order the DAG in a way that favours the former set and penalizes the latter. Interestingly, the specific way in which we order honest blocks is of no importance to the security of the protocol— any arbitrary rule which respects the topology will enjoy the robustness properties of PHANTOM, as we prove formally in Section 5.

However, the ordering rule does affect confirmation times. An arbitrary topological ordering might take a long while before converging, especially if an active visible attack is taking place. Thus, vanilla PHANTOM does not guarantee fast convergence time in all cases. In Section 7 we elaborate on this, and discuss techniques and modifications that allow fast confirmation times.

Fig. 2: An example of the largest 3-cluster of blocks within a given DAG:A,B,C,D,F,G,I,J(coloured blue). It is easy to verify that each of these blue blocks has at most 3 blue blocks in its anticone, and (a bit less easy) that this is the largest set with this property. Setting PHANTOM’s inter-connectivity parameter with $k= 3$ means that at most 4 blocks are assumed to be created within each unit of delay, so that typical anticone sizes should not exceed 3. Blocks outside the largest 3-cluster,E,H,K(coloured red), belong to the attacker (w.h.p.). For instance, block E has 6 blue blocks in its anticone (B,C,D,F,G,I); these blocks didn’t reference E, presumably because E was withheld from their miners. Similarly, block K admits 6 blue blocks in its anticone (B,C,G,F,I,J); presumably, its malicious miner received already some blocks from(B,C,D,G), but violated the mining protocol by not referencing them.

##### C. 相关工作

Many suggestions to improve Bitcoin’s scalability have been proposed in recent years. These proposals fall into two categories, on-chain scaling and off-chain scaling. Roughly speaking, the former includes protocols where all valid transactions are those that appear – as in Bitcoin – inside blocks that are organized in some data structure (aka “the ledger”).

On-chain scaling. The protocols in this category may differ e.g. in how fast blocks are created, how blocks are organized in the ledger (a chain, a tree, a DAG, etc.), which transactions in the ledger are considered valid, and more. PHANTOM belongs to this line of works. Previous works in this family of protocols includes GHOST [9], where a main chain of blocks is chosen according to a greedy algorithm and not through the longest chain rule; Inclusive [5], where any chain-selection rule is extended to an ordered DAG and transactions off the main chain are added in a consistent manner; Bitcoin NG [1], where the ledger consists of slow key blocks (containing no transactions) and fast micro blocks that contain transactions. The sole purpose of key blocks in Bitcoin NG is to define the miner that is eligible to create micro blocks in that epoch and confirm thus transactions at a high rate.

GHOST is still susceptible to some attacks, one of which was described in [3]. The DAG in Inclusive adds throughput but not security to the main chain, hence suffers from the same limitations as the underlying main chain selection rule. Key blocks in Bitcoin NG are still generated slowly, thus confirmation times remain high.

GHOST仍然容易受到一些攻击，其中之一在[3]中有所描述。 Inclusive中的DAG增加了主链的吞吐量但没有增加安全性，因此会受到与底层主链选择规则相同的限制。 Bitcoin NG中关键的块仍然会缓慢产生，因此确认时间仍然很长。

Our work is most similar to the SPECTRE protocol [8]. SPECTRE enjoys both high throughput and fast confirmation times. It uses the structure of the DAG as representing an abstract vote regarding the order between each pair of blocks. One caveat of SPECTRE is that the output of this pairwise ordering may not be extendable to a full linear ordering, due to possible Condorcet cycles. PHANTOM solves this issue and provides a linear ordering over the blocks of the DAG. As such, PHANTOM can support consensus regarding any general computation, also known as Smart Contracts, which SPECTRE cannot. Indeed, in order for a computation or contract to be processed correctly and consistently, the full order of events in the ledger is usually required, and particularly the order of inputs to the contract.^1 PHANTOM’s linear ordering does not come without cost—confirmation times are mush slower than those in SPECTRE. In Section 7 we describe how the same system can simultaneously enjoy the best of both protocols.

Off-chain scaling. Another totally different approach keeps block creations infrequent and their sizes small (so that propagation delay remains negligible), yet this slow chain is not used for recording the entire economic activity. Instead, most of the transactions occur outside the chain, with better scalability, and the chain itself is used for the purpose of resolving conflicts or settling transactions. One example is Hybrid Consensus [6], improving over [4], which uses the chain to select a rotating committee of nodes which in turn run a classic consensus protocol to confirm transactions in the corresponding epoch. Another well known proposed solution in the same category is the Lightning Network [7] (LN), where transactions are processed off-chain over over a network of micro payment channels, and the blockchain is used only for settlement of these channels.

Our work is orthogonal and complementary to these solutions, and can enhance their operation by orders-of-magnitude. For instance, when the DAG is used to serve channel-settlement transactions of LN, it allows for a much cheaper access (due to larger supply of blocks and capacity) and much faster processing than if the LN were operating over a chain.

(^1) Contracts that do not require such a strict ordering can indeed be served under SPECTRE as well.
(^1) 不需要这种严格排序的合约也可以在SPECTRE下提供。

Top