Scroll

Categories

Tags

Monthly Archives

Keyword

Back

# Confirmation Times in SPECTRE

2018.07.24

## Tags

Source : https://blog.daglabs.com/confirmation-times-in-spectre-7f68fec0d997
TranStudy : https://github.com/DAGfans/TranStudy/blob/master/Blogs/Confirmation%20Times%20in%20SPECTRE.md

# SPECTRE中的交易确认时间

Since it solves the orphan rate problem, SPECTRE can operate at very high block rates, resulting in transaction confirmation times in mere seconds (see previous blog post).
Unlike Bitcoin, SPECTRE’s core protocol is agnostic to the network propagation delay;
some upper bound on the propagation delay must be assumed, but this assumption is made locally by each node when determining transaction safety.

Nodes that misestimate the propagation delay will hurt their own performance alone.
This upper bound assumption can be adjusted locally as network conditions change, which allows SPECTRE to be responsive¹ to network conditions and achieve optimally fast confirmation times during healthy periods.
In contrast, Bitcoin’s measure of ten-minute block times is carved in stone.

## 比特币和blockDAG中的重组

In Bitcoin, a node’s observed main chain will undergo a reorganization if the node discovers a new chain that excludes some blocks from its current main chain and is longer than its current main chain.
The node will switch over to this new chain, and the excluded blocks become orphans.
Slight reorganizations of the chain, if they occur, may be caused by network asynchronicity,
whereas large reorganizations are likely to be caused by attackers with sufficient mining power to overtake the main chain, or by some catastrophic split in the network.

Since SPECTRE and PHANTOM are also proof-of-work-based, they too are susceptible to reorgs.
Each node’s canonical set of transactions (TxO set) is derived from the order of blocks that the protocol produces:
a node locally computes the order of blocks, then chronologically accepts consistent transactions.
In a DAG reorg, a successful attacker may change the initially observed order of a node’s local DAG.
If transaction tx was previously included in the node’s TxO set, an attacker could create blocks that manipulate the order such that tx is no longer part of this set.
This requires publishing a block with a transaction that conflicts with tx, and having that block precede the block containing tx.

The above figure shows two blockDAGs that a node hypothetically observes at two different times and the DAGs’ corresponding possible orderings (produced via the PHANTOM protocol).
With the addition of blocks N and O in the second DAG, PHANTOM will produce a different clustering of “honest” vs. “dishonest” blocks, and thus the ordering is changed drastically.

If there are conflicting transactions in, say, blocks I and O, then the previously accepted transaction in block I will no longer be in the node’s TxO set.
Note that PHANTOM produces a full linear ordering of blocks, which is simplest to illustrate, whereas SPECTRE produces a pairwise ordering.

## 比特币和blockDAG中的确认时间

In Bitcoin, the confirmation time of a transaction is the time it takes for the transaction to become effectively irreversible, which is equivalent to waiting until the block containing the transaction is protected against orphanization from reorgs.

Nodes set their own threshold for how few confirmations they are willing to accept before recognizing a payment as irreversible.

To that end, each node must estimate the likelihood of a chain reorg;
this is done by locally setting two parameters:

$\alpha$ — an assumption on the percentage of the total hashrate an attacker might have $\varepsilon$ — the risk the node is willing to absorb

$\alpha$ - 对攻击者可能拥有的总哈希值的百分比的假设 $\varepsilon$ - 节点愿意承担的风险

A typical Bitcoin client will consider a transaction confirmed only once it is six blocks deep
(that’s an average confirmation time of 60 minutes!).
This default number is based on an attacker size of 10% and a risk of <0.1%.²

（这个60分钟是平均确认时间！）。

Similarly, a node in a blockDAG system must locally set some parameters in order to estimate the robustness of its current ordering of the DAG.
In addition to the parameters $\varepsilon$ and $\alpha$ needed for confirming transactions in Bitcoin, the node specifies an assumption on the network delay D.
Assumptions on the network propagation delay are essential when characterizing consensus protocols.

The nature of this assumption may differ across protocols, e.g., where in the protocol it is made, whether it is part of consensus, and what harm is done when it is violated and for how long.
The Bitcoin protocol, for instance, operates under the (rather conservative) ten-minute upper bound on the network delay.³

### blockDAG中攻击者的比例

An interesting implication of having no orphans in a blockDAG system is that reorgs affect only conflicting transactions, and so transactions with no visible conflicts remain unaffected.

In particular, a double-spending attacker must engage directly with its victims, broadcasting a conflicting transaction for each transaction it aims at reversing.

In contrast, a powerful attacker in Bitcoin can harm a huge number of payments by publishing a sufficiently long chain of empty blocks.

Consequently, sometimes $\alpha$ can be set to be quite small in a blockDAG system, which significantly reduces confirmation times.

For instance, in the case of physical point-of-sale payments, it is unlikely that a large mining entity will bother to visit the point of sale and reverse the payment.

Point-of-sale nodes may therefore justifiably set their $\alpha$ to be small — maybe even 0 — allowing them to confirm transactions much faster.

## 确认时间，SPECTRE案例

In SPECTRE, the assignment of D is local to the node running the protocol; there does not need to be agreement.

This also does not need to be a correct estimate, as knowledge of network propagation delays is tricky and dynamic.

Instead, each node sets an upper bound on D based on recent history. This is analogous to the upper-bound network delay estimate upon which Bitcoin’s ten-minute block time is based.

Unlike in Bitcoin, each node in SPECTRE solely bears the consequences of its choice of D.

A paranoid node that significantly overestimates D will hurt itself by waiting too long to recognize that a transaction is irreversible, and a negligent node that significantly underestimates D will hurt itself by prematurely accepting transactions.

However, nodes may change their choice of D as they wish, e.g., if their former choice is overly inaccurate or if network conditions change — and they can do so without coordinating with the rest of the network.

Thus, the core protocol of SPECTRE (i.e., the pairwise ordering procedure) is agnostic to the network propagation delay.
Confirmation times in SPECTRE do largely depend on the propagation delay, but this is estimated locally by each node.

SPECTRE中的确认时间很大程度上取决于传播延迟，但这是由每个节点在本地估计的。

Asymptotically, SPECTRE’s confirmation times are in

where $\lambda$ is the block creation rate.⁴
Under a range of normal network conditions, this yields confirmation times on the order of seconds.
When the network is healthy, nodes will tighten their upper bound on D and minimize this time.
The effects of D and $\lambda$ on confirmation times are shown in the simulation results below.

D和$\lambda$对确认时间的影响在下面的模拟结果中显示。

(left) Effect of delay D on confirmation times with $\lambda = 10$ blocks per second and $\alpha = 0.25$.

(Note: as stated earlier, in some cases nodes may safely set $\alpha$ as low as 0, speeding up confirmation times even further.)

(右图)出块率$\lambda$对等待时间的影响，D = 5秒且$\alpha = 0.25$。图片来自SPECTRE论文附录B。
(注意：如前所述，在某些情况下，节点可以安全地将$\alpha$设置为低至0，从而进一步加快确认时间。)

## SPECTRE中的弱活性

SPECTRE is able to achieve fast confirmations by relaxing the Liveness property which, together with Safety, is traditionally required from consensus protocols.
In this context, Safety means that a decision is not reversed w.h.p., and Liveness means that a decision is guaranteed to be made (preferably sooner rather than later).

In SPECTRE, if two conflicting transactions are published at the same time or one soon after another, then neither transaction is guaranteed to be effectively irreversible and thus decided upon within a finite time.
On the other hand, a published transaction with no near-published conflicts is guaranteed to become irreversible.
The authors of SPECTRE call this property Weak Liveness.

SPECTRE的作者将此属性称为弱活性。

It is crucial to observe that this weakening does not harm the usability of the system for honest users.
Honest users would never attempt to double spend a transaction right after they have published it, and so for such users the weakening of Liveness is non-consequential.
Dishonest users, in contrast, might publish conflicting transactions;
for these users Weak Liveness implies that both transactions might remain pending for an indefinite period of time.⁵
Importantly, recipients of these published conflicting transactions will immediately notice the double spend attempt and refrain from accepting either transaction as valid.

Note that this argument applies only to a payments use case, for which SPECTRE is designed, in which the owner of the funds is the sole entity that can produce and sign such conflicting transactions.
In contrast, in a smart contracts application, any user could potentially feed the contract with conflicting inputs; SPECTRE is less suited for this.

In PHANTOM, some of these issues are dealt with in a new way, as we will discuss in future blog posts.

## Endnotes:

¹ This is a term borrowed from Elaine Shi and Rafael Pass.

¹ 这是从Elaine Shi和Rafael Pass处引用的术语。

² Source: https://bitcoil.co.il/Doublespend.pdf

³ Technically, the estimate of ten minutes is more subtle: it is an assumption that the probability of a Poisson process with mean interval of ten minutes producing two events within an interval shorter than D is negligible.

³ 从技术上讲，十分钟的估计更为微妙：假设平均间隔为十分钟的泊松分布过程在短于D的区间内产生两个事件的概率可以忽略不计。

⁴ Derivation of the asymptotic bound (LaTeX’d for math formatting):

⁴ 渐近边界的推导（用于数学格式的LaTeX格式）：

⁵ Even this only happens under peculiar attacks coordinated by malicious miners.

⁵ 即使这只发生在恶意的矿工合谋的特殊攻击下。

Top