An overview of SPECTRE - a blockDAG consensus protocol (part 2)

In the previous post, we discussed the topological foundations of two consensus protocols: Bitcoin’s longest chain rule and the GHOST protocol (heaviest subtree rule). In this post we will analyze the DAG protocol SPECTRE.

We saw firsthand the benefits of intelligently designing a blockchain consensus protocol: the GHOST protocol enjoys more security and scalability by how it chooses to resolve forks than Bitcoin and longest chain proof of work consensus protocols. Thus, the design of new consensus variants present interesting research opportunities for blockchain research. For the interested, refer to part 1 of the overview for a plethora of papers, research directions, and preliminary topics to build a robust understanding of the technology.

Let’s start by summarizing the evolution of Proof of Work protocol design we discussed in the previous post. A proof of work is some computationally hard but tractable puzzle that helps prevent Sybil attacks. For blockchains, proofs of work are also a method for securing the underlying blockchain transactions: double-spend attacks hypothetically require reversing these proofs.

Longest chain rule (Nakamoto Consensus)

The first consensus rule utilized in Bitcoin chooses the longest chain by maximized aggregate proof of work. This is a very unidimensional perspective to consensus: if an attacker has enough computational power, they can reliably build a longer, attacker blockchain with more aggregate proof of work. Thus, this rule is not optimal to unilateral deviations by strong adversaries.

Drawbacks

• Increased throughput leads to decreased security
• Not robust to strong adversaries (50%)
• Long confirmation times

Greedy Heaviest-Observed Sub-Tree

This consensus rule relies on the size of subtrees rooted at blocks along the longest, main blockchain. Here, size is similarly defined as aggregate proof of work. At each step in the protocol, every honest participant traverses the entire block tree (think the history of every block every proposed) and chooses, at each depth level, the block with the heaviest subtree underneath. Once they hit the bottom according to this rule, participants begin mining underneath that block. Ties are chosen arbitrarily, usually based on the blocks you see first.

The benefits of this approach are as follows. To execute a double-spend, a 50% attacker’s main objective is to overwrite, previously written blocks. In order to do so, an attacker is incentivized to dedicate all its computational power to the blockchain it wants to extend. Since the consensus rule is resolved by subtrees and not chains however, the attacker can never reliably extend an attacker chain without consistently contributing to the honest blockchain. Thus, either their blocks become invalidated or the attack fails to succeed. Note, an attacker with substantial mining power say 67% could potentially build attacker subtrees at a reliable rate — by splitting up his/her mining power and building attacker subtrees. This however raises the bar for successful attacks and is overall, more secure.

Using GHOST, block throughput and size can be increased without reducing overall security. The design is inherently more scalable.

Drawbacks

• More complex implementation

Graph Theory Concepts

Let’s begin with some computer science theory. A graph G=(V,E) is defined as a set of vertices and edges between those vertices. Graphs can be directed, indicative of an ordering relation over edges, or be undirected. Friendships in a social network are examples of undirected edges and edges defined by who initiated the friendship are examples of directed edges.

A directed acyclic graph G (DAG) is a graph that has no cycles. An interesting property about direct acyclic graphs G is that they provably admit topological sorts. A topological sort o=(v_1,v_2,…) is an ordering of vertices in G such that if u and v are connected by the edge e=(u →v), u comes before v in o.

A block DAG G is simply a DAG that branches off from a genesis block b. All nodes branching off the genesis block point back to b. Instead of forming a tree structure, nodes connect to any potential nodes that don’t have children.

Rationality & Honesty

Let’s also begin thinking about the game theoretic foundations of multi-agent systems. A rational agent is one who acts to maximize his/her reward in the context of a game. In the context of a cryptocurrency mining protocol a rational agent only participates in the protocol honestly if that is what yields the highest payoff. From this, we see that attackers are truly rational agents; attackers deviate from the protocol to double-spend only if they can reliably double-spend.

From the existence of live blockchain networks such as Bitcoin and Ethereum, we know that most mining participants honestly adhere to the underlying consensus protocol. Honest participants adhere to the protocol even if there is a deviation that improves their payoff. We can go further and classify these participants as altruists in the protocol. Altruists in our model are the best types of participants. They maintain the security of the underlying blockchain according to the rules that are defined, even if they can make more otherwise. Their actions are verifiable and not uncertain, therefore their actions should take priority in the system over everything else. We use these systems to benefit humanity, right?

Can we robustly separate good and bad, expediting good actions and delaying bad actions in a consensus protocol? Attackers usually hide their actions until they can profitably execute them, i.e. building an attacker chain in secret to double-spend at a later point. The inherent delay provides a insight into how we might exploit this to build prevention mechanisms for similarly malicious behavior.

SPECTRE

Serialization of Proof-of-work Events: Confirming Transactions via
Recursive Elections (SPECTRE) is a protocol proposed by Sompolinsky, Lewenberg, and Zohar that extends our notion of scalability and dimension. It focuses on building a directed acyclic graph (DAG) structure to allow concurrent and parallel block creation on the block DAG. The parallelization is exhibited by the separation between the mining and consensus portions of the protocol. In addition, the authors relax traditional consensus notions to provide greater scalability, leading to the notion of weak liveness. What we will see is that this relaxation comes only at cost to dishonest participants.

Mining

The mining protocol utilized by SPECTRE follows a similar Proof of Work system as Bitcoin, where the computational puzzles are finding hashes under a target difficulty. At each step in an individual node’s mining process, it examines its view of the blockDAG network and does the following:

• Finds the set of all blocks with 0 in-degree, denoted B.
• Computes hashes until it finds a hash h<D.
• Creates a block b with hash h, includes B in the header (directed edges to those blocks), and broadcasts b.

The mining protocol makes no assumption on the transactions included in newly created blocks. It is seen as a separate atomic component of the overall protocol that enables greater scalability by allowing nodes to create blocks at arbitrarily high rates (upper bounded in reality by networking constraints and more generally the speed of light).

Consensus

Rather than focus on consensus at the block level, SPECTRE prioritizes consensus at the transactional level in a separate mechanism to the mining mechanism. It utilizes a recursive voting procedure based on the precedence of blocks in any topological sort of the underlying DAG. In this voting procedure, every block submits a vote for every pair of blocks. We will tally up these votes in order to decide the set of accepted transactions at any moment in the execution of the consensus mechanism.

At a given time in the consensus protocol and for a given participant’s blockDAG, each block will submit votes over every pair of blocks. A block z’s vote, (-1,0,1), over a given pair of blocks (x,y) is a preference ordering over these two blocks, i.e. a preference over the transactions in these blocks. If z thinks x<y it votes -1, x>y it votes 1, and otherwise votes 0. These votes place an additional ordering on top of a topological sort ordering, which will help us identify the verifiably, confirmed transactions in the blockDAG. In order to define the voting procedure precisely, we need to introduce some more terminology.

• past(x) and future(x) are the sets of blocks the precede and succeed block x respectively
• virtual(G) is a function takes as input a DAG G and returns the hypothetical next block to be created such that past(virtual(G))=G.
• vote(z,G), which takes as input a block z and and DAG G and returns a voting profile of z, i.e. a matrix* containing at each index (x,y) z’s vote over blocks x and y.

Note, the voting function is anti-symmetric, i.e reversing the order is multiplication by -1 i.e. the matrix’s transpose is the negative matrix.

Since connected subsets of G are also DAGs, we can apply this function recursively to the set past(x). Given this, lets introduce precisely how a block z votes over (x,y), breaking ties arbitrarily:

If z is in future(x) and not future(y), then z votes -1, if the reverse is true then z votes 1.

If z is in future(x) and future(y), then z votes according to virtual(past(z)).

If z is not in future(x) and not in future(y), then z votes according to the majority of all other blocks in G.

If z is the next block the current participant has created or seeks to create, then z votes according to the majority of all other blocks in G.

If z is either x or y, then z votes for itself in the ordering, defined above.

In effect, each block will vote based on what either it, it’s past, or the majority believe about a pair of blocks over G. Since blocks vote with the majority, past blocks tend towards voting with their future blocks.

The example below is a single voting procedure for a single pair of blocks. In its entirety, the SPECTRE protocol runs this procedure recursively for each block z and past(z) and ultimately outputs a list/matrix of pairwise preference orderings.

An example of the voting procedure, taken from SPECTRE research paper

By design, SPECTRE emphasizes the time-based nature of transactions in its voting scheme. If block a precedes block b and they conflict, then the protocol will ensure that a gets voted on the most, the fastest. By ensuring that every new block references all leaf blocks it sees, honest participants swarm to build on honest blocks. Attackers, revealing hidden blocks at some later date, do not benefit from receiving connections from honest blocks; this reduces the rate and amount that these blocks get voted on, i.e. SPECTRE prioritizes quickness over powerfulness in terms of sheer mining power.

As the authors mention in their paper, there are a few intuitive characteristics about the protocol that make it robust:

Vote in favour of visible blocks. Honest miners build on honest blocks.

Majority amplification. Honest blocks will side with earlier (honest) blocks in conflicts.

Referencing recent blocks is beneficial. Building on recent, honest blocks gives more votes to honest blocks versus attackers mining hidden blocks who lose out on votes.

Votes from the past counter pre-mining attacks. Concurrent block creation usually means honest blocks will outnumber attacker blocks and thus vote accordingly if an attacker withholds block propagation.

Transaction Finality

So far, we have only mentioned how the voting procedure works and not how transactions are confirmed and finalized. Similar to how the voting procedure outputs a list of pairwise orderings, SPECTRE utilizes a separate algorithm(s) for outputting a hyper-set of valid transactions TxO and RobustTxO.

In order to guarantee transaction finality with high probability, it helps to define what that scenario looks like. We will get rid of all honest executions to clarify the situations we require additional investigating.

• Transactions that have no conflicts are clearly valid the deeper they are embedded into the blockDAG.
• If T is a set of transactions ordered by time and closed under future(-), i.e. each transaction is included in the future of the block of the 1st transaction, then the earliest transactions are accepted and later conflicts rejected.
• Transactions that are in a past validated TxO or RobustTxO always remain in such collections. Conflicts to these transactions will never enter these collections.

The cases that require more thought are those that conflict and are not within the future of either (depending on time). These are conflicting transactions which have distinct pasts, since if one was in the other’s past, then one would be in the other’s future → a contradiction.

In order to decide whether transaction x comes before y, the authors define an online and offline risk score which upper bounds the probability that an attacker can reverse a pairwise ordering with a number of tunable parameters. Using this risk score, we can build a collection RobustTxO, allowing online and offline users full control over the transactions they accept. From the perspective of a user of the underlying cryptocurrency powered by SPECTRE, he/she can reliably and quickly decide when transactions included in their blocks are valid using a RobustTxO collection with arbitrary (though high) “confidence” probabilities.

From the honest executions of the protocol, we see that honest transactions get included into the transaction collections with relative ease and speed. When there are no conflicts, blocks are created and propagated concurrently to quickly and robustly provide transaction confirmation. Since attackers with low mining power have decreasing incentives to broadcast conflicting transactions, the blockDAG can progress quickly and users can spend and receive cryptocurrency transactions with high speed and reliability.

Recall our notions of safety and liveness from the previous article; we now provide the analogue of weak liveness and safety that the SPECTRE protocol ensures:

• Weak-Liveness. Every non-faulty node’s transactions get accepted, assuming their are no conflicts and its inputs are accepted
• Safety. Every non-faulty node decides on the same set of accepted transactions

The authors show that we can satisfy safety and weak liveness for honest users only. This is great in some cases because honest users are the only users we actually care about when building decentralized systems. If we can reliably delay the actions of attackers and serve only altruists in the system, then the collective social welfare is maximized. By prioritizing actions of honest users — transactions and blocks that don’t have conflicts — we can speed up the system for settings that are visibly honest.

Scalability

Compared to the GHOST protocol and surely the Bitcoin protocol, SPECTRE enjoys even greater scalability through its novel separation between mining and consensus. Blocks can be created at very high rates in parallel, and users can construct confirmed transactions .

Topological sorting & Linear ordering

One thing I’ve found interesting as I read through consensus protocol papers, especially relating to blockDAGs, is the importance of a linear ordering with respect to blocks and/or transactions. The authors of SPECTRE make it clear that the pairwise ordering relation is not transitive, i.e. not always a linear ordering. The idea is that some DAG states may exhibit cases of Condorcet’s Paradox, a paradox in social choice theory around cycles of pairwise preferences. These cycles occur not in how the DAG is constructed over time but rather how the individual blocks vote on pairwise orderings. Without proper orderings between all pairs of blocks — complete liveness vs weak liveness — SPECTRE is only suited to support cryptocurrency networks where a strict ordering among transactions is not a necessity.

Additionally, the voting procedure presents interesting ideas for future research directions. While these are not flushed out, here are some of mine:

• Given we seek to maximize votes for honestly generated blocks with and without conflicts, there seems to be a subtle transition into the optimization space. Can we manipulate the consensus goal into a distributed optimization/learning problem for nodes to solve? How can we potentially incorporate this idea into the mining process given miners have a lot of computational power to spare?
• Regardless of the fact that a linear ordering in SPECTRE does not provide added benefit (since its linearizability is only halted by conflicting transactions), what do the pairwise ordering and topological ordering have in common? What tools can we use from algebraic topology, poset topologies, etc to understand algebraic notions of consensus within the DAG framework?

Related work on Scalability

Below are some papers relevant to research on scalability and may be redundant from my last post:

1. Bitcoin-Ng — Proof of Work for Leader selection & Byzantine Consensus for transaction processing
2. Algorand — Proof of Stake for scalability
3. SoK-Consensus in the Age of Blockchains — A review of the entire blockchain/DAG consensus ecosystem up to 2017.

If you enjoyed this piece and want to stay in touch for more researchy content, follow me on Medium and Twitter @dungulator.