Confirmation times in SPECTRE
Summary: 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 mis-estimate 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.
Reorganizations in Bitcoin and blockDAGs
In Bitcoin, a node’s observed main chain undergoes a reorganization, or reorg, if the node discovers a new chain that excludes some blocks from its current chain and is longer than its current chain. The node switches over to this new chain, and the excluded blocks become orphans. Slight reorgs of the chain, if they occur, may be caused by network asynchronicity, whereas large reorgs 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.
Confirmation times in Bitcoin and blockDAGs
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 orphaning 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:
- α — an assumed percentage of the total hashrate an attacker might have
- ε — the risk the node is willing to absorb
A typical Bitcoin client will consider a transaction confirmed only once it’s 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%.²
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 ε and α 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.³
Size of attacker in blockDAGs
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.
Therefore, sometimes α can be set to be quite small in a blockDAG system, which significantly reduces confirmation times. For example, in the case of physical point-of-sale payments, it’s 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 α to be small — maybe even 0 — allowing them to confirm transactions much faster.
Confirmation times in SPECTRE
In SPECTRE, the assignment of D is local to the node running the protocol; there doesn’t need to be agreement. Also, D doesn’t 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, for example, 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.
Asymptotically, SPECTRE’s confirmation times are in
where λ 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 λ on confirmation times are shown in the following simulation results.
Weak liveness in SPECTRE
SPECTRE can 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 won’t be reversed with high probability, 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 amount of 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.
It’s 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 will be discussed in future texts.
_________________________________________________________________
Endnotes:
¹ This is a term borrowed from Elaine Shi and 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.
⁴ Derivation of the asymptotic bound (LaTeX’d for math formatting):
⁵ Even this only happens under peculiar attacks coordinated by malicious miners.
