Scroll

Categories

Tags

Monthly Archives

Keyword

Back

2018.04.05

# 3. 形式模型和陈述

In this section we describe our formal framework. While we introduce new notation and terminology, the reader should keep in mind that we stick to Bitcoin’s model in almost every respect—transactions, blocks, Proof-of-work, computationally bounded attacker, P2P propagation of blocks, probabilistic security guarantees, etc. The “only” difference is that a block references (possibly) several predecessors rather than a single one. While this has far reaching consequences on how the ledger is to be interpreted, on the mining side things remain largely the same.

## A. 网络

We follow the model speciﬁed in [8]. The network of nodes (or miners) is denoted N , honest denotes the set of nodes that abide to the mining protocol (as deﬁned below), and malicious denotes the rest of the nodes. Honest nodes form a connected component in N ’s topology, and the communication delay diameter of the honest subnetwork is D: if an honest node $v ∈ N$ sends a message of size b MB at time t, it arrives at all honest nodes by time t + D the latest. The attacker is assumed to suffer no delays whatsoever on its outgoing or incoming links.

The real value of D is a priori unknown. The PHANTOM protocol assumes that D is always smaller than some constant $D_{max}$(both depend on the block size b). The parameter $D_{max}$ is not hard-coded explicitly in the protocol, rather it influences another parameter,$k = k(D_{max})$, which is hard-coded and decided once and for all at the inception of the system. Roughly speaking, $k(D_{max})$ represents an upper bound on the number bound on the number of blocks that the network creates in one unit of delay and that may not be referenced by one another. Section 4 discusses this parameter in more detail.

D的真实值是无法预知的。 PHANTOM协议假定D总是小于某个常数$D_{max}$（两者都取决于块大小b）。 参数$D_{max}$不是在协议中明确硬编码的，而是影响另一个参数，$k = k(D_{max})$，其在系统一初始时就是硬编码的并且会一直保持不变。 粗略地说，$k(D_{max})$代表网络在一个延迟单元中创建的块的数量上限，并且这些块彼此不会引用。 第4节更详细地讨论了这个参数。

## B. 挖矿架构

Proof-of-work. Nodes create blocks of transactions by solving Proof-of-work puzzles. Block creation follows a Poisson process with parameter λ. For the sake of simplicity, we assume that λ is constant.^7 The computational power of node $v∈ N$ is captured by $0 < α_v< 1$ , which represents the probability that node v will be the creator of the next block in the system (at any point in time; this is a memoryless process). The attackers’ computational power is less than 50%. Thus $∑_{v∈N}α_v=1$, and $∑_{v∈malicious}α_v := α <0.5$.

(^7) In practice, λ must occasionally be readjusted to account for shifting network conditions. PHANTOM can support a retargeting mechanism similar to Bitcoin’s, e.g., readjust every time that $Chn(G)$ grows by 2016 blocks.

(^7) 在实践中，λ必须时不时重新调整以应对网络状况的变化。 PHANTOM可以支持类似于比特币的重新定位机制，例如，每当$Chn(G)$ 增长2016个区块时进行重新调整。

Block references. Every block specifies its direct predecessors by referencing their ID in its header (a block’s ID is obtained by applying a collision resistant hash to its header); the choice of predecessors will be described in the next subsection. This results in a structure of a direct acyclic graph (DAG) of blocks (as blocks can only reference blocks created before them), denoted typically $G= (C,E)$. Here, C represents blocks and E represents the hash references. We will frequently write $B∈G$ instead of $B∈C$.

DAG topology. The topology of the blockDAG induces a natural partial ordering over blocks, as follows: if there is a path in the DAG from block C to block B we write $B∈past(C)$; in this case, C was provably created after B and therefore B should precede C in the order.^8 A node does not consider a block as valid until it receives its entire past set. The unique block genesis is the block created at the inception of the system, and every valid block must have it in its past set.

DAG 结构. 区块有向无环图（BlockDAG）的结构会导致块天然的偏序，如下所示：如果DAG中存在从块C到块B的路径，表示为$B∈past(C)$; 在这种情况下，C很大可能是在B之后创建的，因此B应该按照顺序在C之前。^8 一个节点只有在接收到块的整个过去集时才认为该块有效的。 唯一的创始区块是在系统开始时创建的，每个有效的区块都必须在其过去集中包含它。

Similarly, the future set of a block, $future(B)$, represents blocks that were provably created after it: $B ∈ past (C) \Leftrightarrow C ∈ future (B)$. In contrast to the past set, the future set of a block keeps growing in time, as more blocks are created and are referencing it. To avoid ambiguity, we write $future(B)∩G$ or $future(B,G)$, and write $future(B)$ only when the context is clear or unimportant.

The set $anticone (B)$ represents all blocks not in B ’s future or past (excluding B as well). These are blocks whose ordering with respect to B is not deﬁned via the partial ordering that the topology of the DAG induces. Formally, for two distinct blocks $B, C ∈ G: C ∈ anticone (B, G) \Leftrightarrow (B \notin past (C) ∧ C \notin past (B)) \Leftrightarrow B ∈ anticone (C, g)$. Here too we usually specify the context, $anticone (B, G)$, because the anticone set can grow with time.

In Figure 1 above we illustrates this terminology.

(^8) Note that an edge in the DAG points back in time, from the new block to previously created blocks which it references.

(^8) 请注意，DAG中一条边会及时从新块指向到它引用的之前创建的块上。

DAG mining protocol. $G_t^v$ denotes the block DAG that node $v ∈ N$ observes at time t. This DAG represents the history of all (valid) block-messages received by the node. $G_t^{oracle} := ∪_{v∈N} G_t^v$ denotes the block DAG of a hypothetical oracle node, and $G_t^{pub} := ∪_{v∈honest} G_t^v$ denotes the block DAG containing all blocks that are visible to some honest node(s).

DAG 挖矿协议. $G_t^v$表示节点$v ∈ N$在时间t观察到的区块有向无环图（BlockDAG）。 这个有向无环图（DAG）表示节点接收到的所有（有效）块消息的历史。 $G_t^{oracle} := ∪_{v∈N} G_t^v$表示某个假定的预言节点的区块有向无环图（BlockDAG），而$G_t^{pub} := ∪_{v∈honest} G_t^v$表示包含了对某个(些)诚实节点可见的所有区块的有向无环图(BlockDAG)。 译注： 这个oracle在Spectre论文应用比较多，是一个假定拥有所有信息的节点，方便论述

A tip of the DAG is a leaf-block, namely, a block with in-degree 0. The instructions to a miner in the DAG paradigm are simple:

DAG的末梢是一个叶块，即一个入度为0的块。 在有向无环图（DAG）范例中对矿工的规则很简单：

1. When creating or receiving a block, transmit it to all of one’s peers in N . Formally, this implies that $∀v, u ∈ honest : G_t^v ⊆ G_{t+D}^u$ .
2. When creating a block, embed in its header a list containing the hash of all tips in the locally-observed DAG. Formally, this implies that if block B was created at time t, by honest node v , then $past (B) = G_t^v$ . ^9

Since these are the only two mining rules in our system, a byzantine behaviour of the attacker (which controls up to α of the mining power) amounts to an arbitrary deviation from one or both of these instructions.

1. 当某个节点创建或接收一个块时，将该块发送给网络N中的该节点的所有对等节点。形式上，这意味着：$∀v, u ∈ honest : G_t^v ⊆ G_{t+D}^u$ 。
2. 在创建块时，在其头部中嵌入一个包含本地观察到的DAG中所有末梢的散列列表。 在形式上，这意味着如果块B在时间t处由诚实节点v创建，则B的过去集$past (B) = G_t^v$。^9

(^9) Technically it is more accurate to write $past(B) =G_v^t \setminus {B}$, as a block does not belongs to its own past set. (^9) 从技术上讲，写成$past(B) =G_v^t \setminus {B}$会更准确，因为一个区块不属于它自己的过去集。

## C. DAG 客户端协议

The DAG as described so far possibly embeds conﬂicting transactions. These are resolved on the client level. A client can be deﬁned formally as a node in N which has no mining power. Intuitively, it is any user of the system who is interested in reading and interpreting the current state of the ledger.

In this work, a transaction tx is an arbitrary message that is embedded in a block. An underlying Consistency rule takes as input a set T of transactions and returns valid or invalid. Our work is agnostic to the deﬁnition and operation of this rule, or to the characterization of the transaction space. Instead, we focus on the following task: devising a protocol through which all nodes agree on the order of all transactions in the system. Once such an order is agreed, one can iterate over all transactions, in the prescribed order, and approve each transaction that is consistent – according to the underlying rule – with those approved so far. Such an ordering rule constitutes the client protocol, and is run by each client locally without any need to communicate additional messages with other clients.

Formally, an ordering rule $ord$ takes as input a blockDAG G and outputs a linear order over G’s blocks, $ord(G) = (B_0 , B_1 , . . . , B_{|G|} )$. Transactions in the same block are ordered according to their appearance in it, and this convention allows us to talk henceforth on the order of blocks only. With respect to a given rule $ord$, we write $B \prec_{ord(G)}C$ if the index of B precedes that of C in $ord(G)$; we abbreviate and write $B\prec_GC$ or even $B\prec C$ when the context is understood. For convenience, we use the same notation $B\prec_GC$ when $B ∈ G$ but $C\notin G$.

## D. 顺序的收敛

The following definition captures the desired security of the protocol, in terms of the probability that some order between two blocks will be reversed.

Deﬁnition 3. Fix a rule $ord$. Let $B ∈ G = G_t^{pub}$ . The function Risk is deﬁned by the probability that a block that did not precede B in time $t_1 ≥ t_0$ will later come to precede it: $Risk(B, t_1):= Pr \left ( ∃s>t_1,∃C∈G_s^{pub}: B\prec_{G_t^{pub}}C∧C\prec_{G_s^{pub}}B \right )$ .

In the deﬁnition above, the probability is taken over all random events in the network, including block creation and propagation, as well as the attacker’s arbitrary (byzantine) behaviour. The convergence property below guarantees that the order between a block and those succeeding it, or those not published yet, will not be reversed, w.h.p. This captures the security of the protocol, as it provides honest nodes with (probabilistic) security guarantees regarding possible reorgs.

Property 1. An ordering rule $ord$ is converging if $∀t_0 > 0$ and $B ∈ G_t^{pub} :\lim_{t_1 \to ∞} Risk (B, t_1 ) = 1$, even when a fraction α of the mining power is byzantine.

Remark. Property 1 essentially couples the Safety and Liveness properties required from consensus protocols. Indeed, once $Risk( B , t_1)< \epsilon$ , a decision to accept transactions in B can be made (Liveness), and is guaranteed to be irreversible (Safety) up to an error probability of $\epsilon$ (as in Bitcoin and other protocols). Nevertheless, we avoid phrasing our results in these terms, for the sake of clarity of presentation. The complication arises from the need to analyze the system from the perspective of every node $G_t^v$ , and not merely from the public ledger’s hypothetical perspective $G_t^{pub}$ ; this technicality is not unique to PHANTOM, and should be regarded in any work that formalizes blockchain based consensus (unless propagation delays are assumed to be negligible). We leave the task of bridging this gap to a later version.

The security threshold is the minimal hashing power that the attacker must acquire in order to disrupt the protocol’s operation:

Deﬁnition 4. The security threshold of an ordering rule $ord$ is deﬁned as the maximal α (attacker’s relative computational power) for which Property 1 holds true.

A protocol is scalable if it is safe to increase the block creation rate λ without compromising the security, that is, if the security threshold does not deteriorate as λ increases (this can be phrased also in terms of increasing the block size b rather than λ).

## E. 主要结果

Our goal in this paper is to describe formally the ordering procedure of PHANTOM and to prove that it is scalable in the above sense.

Theorem 5 (PHANTOM scales). Given a block creation rate $λ > 0, δ > 0$, and $D_{max} > 0$, if $D_{max}$ is equal to or greater than the network’s propagation delay diameter D, then the security threshold of PHANTOM, parameterized with $k(D_{max} , δ)$, is at least $1/2 \cdot (1-\delta )$.

The parameterization of PHANTOM via $k(D_{max} , δ)$ is deﬁned in the subsequent section (see (1)). Theorem 5 encapsulates the main achievement of our work. We prove the theorem formally in Section 5. Contrast this result to a theorem regarding the Bitcoin protocol, which appears in several forms in previous work (e.g., [6], [9]):

PHANTOM通过$k(D_{max} , δ)$的参数化在后面的章节中定义(参见(1))。 定理5包括了我们工作的主要成果。 我们在第5节中正式证明了该定理。 该结果与比特币协议的定理相比较，在过去的工作中已经以几种形式出现(例如，[6]，[9])：

Theorem 6 (Bitcoin does not scale). As λ increases, the security threshold of the Bitcoin protocol goes to 0.

Finally, we note that even if $D_{max} \ngeqslant D$, the system’s security does not immediately break apart. Rather, the minimal power needed to attack the system goes from 50% to 0, deteriorating at a rate that depends on the error gap $D-D_{max}$ .

Top