Sassafras Part 3: Compare and Convince

Authors: Elizabeth Crites, Handan Kılınç Alper, Alistair Stewart, and Fatemeh Shirazi

This is the third in a series of three blog posts that describe the new consensus protocol Sassafras, which is planned to be integrated into Polkadot, replacing the current BABE+Aura consensus mechanism.

Here is an overview of the three blog posts:

Part 1 - A Novel Single Secret Leader Election Protocol: The aim of this blog post is to give an introduction that is understandable to any reader with a slight knowledge of blockchains. It explains why Sassafras is useful and gives a high-level overview of how it works.

Part 2 - Deep Dive: The aim of this blog post is to dive into the details of the Sassafras protocol, focusing on technical aspects and security.

Part 3 - Compare and Convince: The aim of this blog post is to offer a comparison to similar protocols and convince the reader of Sassafras's value.

If you have not read Part 1 and Part 2

Here is a a summary:

• Sassafras is a consensus protocol for electing the leader who will produce the next block. It may be combined with a finality gadget that ensures transactions are finalized, such as Grandpa, to achieve a blockchain with blocks that are finalized in constant time intervals (e.g., every 6 seconds on Polkadot).
• It works by validators sending the tickets they have generated using online public randomness to other validators, who act as identity guards. Validators then publish these tickets on-chain where they get sorted. The first validator in the sorted list reveals their identity and produces the next block.
• Sassafras achieves a unique balance: it ensures enough security to make forking attacks infeasible, while being extremely efficient. This combination makes it an attractive option for deployment in the real world.

Let's jump into a comparison with other leader election protocols.

Non-Single Leader Election

In Part 1 of this series, we discuss how BABE finds block producers. More formally, BABE is based on probabilistic leader election (PLE), which is quite common in proof-of-stake (PoS) protocols. Due to the probabilistic nature, multiple leaders may be elected for a slot, or no leaders at all. The additional runoff procedure for selecting a leader increases the time needed to extend the blockchain. Concretely, Azouvi and Cappelleti show that the block finality time for a PoS protocol is decreased by 25% when single secret leader election (SSLE) is used versus PLE. Even more important, for an adversary who controls at most $1/3$ of the validators, SSLE provides higher security than PLE against private attacks, the most damaging kind of attack, where an adversary can create a private chain that overtakes the honest chain.

PLE-based PoS protocols provide security with more adversarial power (up to 49%), but are significantly slower (25%) to finalize the blocks. Sassafras provides security with less adversarial power ($1/3$), but finalizes the blocks significantly faster.

Single Secret Leader Election

Given the advantages of SSLE, several protocols have been proposed. We begin by providing a brief overview of various approaches.

Shuffling

The most common approach to SSLE is shuffling, where each participant registers a commitment in a list, which is repeatedly shuffled, and the winning index is selected via a randomness beacon (i.e., a public source of randomness). The main drawback of these protocols is the significant overhead associated with the proofs for correct execution of the shuffle operations. The cost to verify a proof scales linearly with the number of parties, which is impractical for on-chain use. To address this issue, Boneh et al. suggest dividing the list into sublists of size $\sqrt{N}$ and shuffling only the sublist instead of the entire list (called "stirring"). We refer to this protocol as Shuffle-1.

WHISK

WHISK is an efficient SSLE protocol proposed for Ethereum, based on the Shuffle-1 approach (i.e., "stirring"). Like Sassafras, it performs batch leader elections, in which a single leader is selected for several elections at once. The batch capability enables scalable deployment as a leader election protocol for blockchain, as the rate of leader election aligns with the rate of block production. We give a detailed comparison of WHISK and Sassafras at the end of this blog post.

PEKS

Functional encryption is a generalization of public key encryption where decryption yields a function of the encrypted message (instead of simply the encrypted message itself as in standard encryption). Public key encryption with keyword search (PEKS) is a form of functional encryption, which is used by Catalano et al. to construct an SSLE protocol as follows. Each participant who registers in an election is given a secret key $sk_i$ for $i \in \{1,...,N\}$. A subset of participants collaboratively generate a ciphertext $c$ that encrypts a random "keyword" $i^* \in \{1,...,N\}$. The participant holding $sk_{i^*}$ is able to decrypt $c$, and provides a proof that attests to this fact in order to claim leadership.

Other Approaches to SSLE

There are other approaches to SSLE, including indistinguishability obfuscation (IO) and threshold fully homomorphic encryption (TFHE); however, they are impractical due to the heavy cryptographic operations required.

Comprehensive Comparison

We now give a comprehensive comparison in terms of the security guarantees and communication and computational overhead of the above protocols and Sassafras.

Security Comparison

We assess the security of SSLE protocols based on three criteria, summarized in Table 1.

1. Public Slots: A public slot is one in which the leader for that slot is known (either publicly or to the adversary).

In Sassafras, a slot is public if the repeater of the ticket assigned to a slot is malicious, as described in Part 2. The leader of a public slot may be attacked.

2. Unpredictability Level: The unpredictability level of a leader is the reciprocal of the anonymity set.

Shuffle-2 and Shuffle-3, by Catalano et al., as well as the PEKS-based protocol exhibit the highest level of unpredictability. For all non-public slots, Sassafras achieves a similar level of unpredictability.

3. Security Model: Protocols are proven secure via a security game, or in the universal composability (UC) model, which guarantees security when composed with other protocols in a larger system. Security is proven either against a static adversary, who is assumed to control a set of parties from the onset only, or against a stronger adaptive adversary, who may dynamically corrupt parties as the protocol progresses.

Sassafras and Shuffle-3 achieve the highest level of security, against adaptive adversaries in the UC model. Shuffle-1 and WHISK are insecure in our threat model. We discuss this in detail at end of this blog post.

Protocol	Public	Anonymity Set	Security
Shuffle-1	none ✓	$(1-\alpha)\sqrt{N}$	game-based, static (insecure in our threat model)
Shuffle-2	none ✓	$(1-\alpha) N$✓	UC, static
Shuffle-3	none ✓	$(1-\alpha) N$✓	UC, adaptive ✓
PEKS-based	none ✓	$(1-\alpha) N$ ✓	UC, static
WHISK	$-1.25\frac{\ln((1-\alpha)}{\sqrt{N}} N$	$(1-\alpha) \sqrt{N}$	no formal security analysis (insecure in our threat model)
Sassafras	$(1-\alpha)\alpha N$	$(1-\alpha) N/2$ ✓	UC, adaptive ✓

Table 1: Single secret leader election (SSLE) protocols. $N$ is the total number of participants, $\alpha$ is the fraction of corrupt parties, and $(1-\alpha)$ is the fraction of honest parties. For batch election protocols WHISK and Sassafras, values are given per election. Public is the fraction of leaders in an election that are leaked. The unpredictability level of a leader is the reciprocal of the anonymity set, e.g., $\frac{1}{(1-\alpha) \sqrt{n}}$. UC is the universal composability model.

We now give a detailed efficiency comparison of SSLE protocols.

Communication Overhead

We consider $N = 2^{14} = 16384$ validators running an SSLE protocol to elect single leaders for $2^{13} = 8192$ slots. These are the parameters proposed for WHISK as well as the PEKS-based scheme.

Our analysis demonstrates that Sassafras outperforms other protocols in terms of computational and communication costs on the blockchain.

In particular, we conducted a comprehensive comparison of various protocols based on message size during the setup phase and off-chain and on-chain election communication. The setup overhead includes messages added on the chain or exchanged off-chain related to the keys or commitments used by validators before the elections. Similarly, the election overhead includes messages added on the blockchain and exchanged off-chain during the election protocol to elect $2^{13}$ leaders.

While the setup phase is expected to be rare in PoS blockchain protocols, shuffle-based solutions (with the exception of WHISK) impose impractical levels of message overhead. For election messages on the blockchain, Shuffle-2 and Shuffle-3 are highly inefficient. In stark contrast, Sassafras introduces a mere 7.64 MB overhead on the blockchain.

Protocol		Setup	Election
Shuffle-1	Off-Chain On-Chain	- $8790.15$ MB	- $123.7$ MB
Shuffle-2	Off-Chain On-Chain	- $13527.97$ MB	- $4831.84$ MB
Shuffle-3	Off-Chain On-Chain	- $17823.72$ MB	- $17718.31$ MB
PEKS-based	Off-Chain On-Chain	$252$ MB $1.08$ MB	$23592.96$ MB $301.47$ MB
WHISK	Off-Chain On-Chain	- $4.72$ MB	- $90.44$ MB
Sassafras	Off-Chain On-Chain	- $1.57$ MB ✓	$42.47$ MB $7.64$ MB ✓

Table 2: Communication overhead of SSLE protocols on a blockchain.

Computational Overhead

We similarly conducted a comparison of various protocols based on on-chain computation required to verify election messages and the leader. Efficient on-chain computation is crucial in blockchain protocols, as they need to be performed quickly to facilitate timely block propagation.

In terms of both communication and computational overhead, Sassafras outperforms other SSLE protocols by an order of magnitude or more. Further details of our benchmark analysis can be found in the paper.

Protocol	On-Chain Comp. during the Election	Benchmark
Shuffle-1	$O(\sqrt{N})$	$40.9$ ms
Shuffle-2	$O(N)$	$5241.9$ ms
Shuffle-3	$O(N)$	$11793.6$ ms
PEKS-based	$O(\log^2 N)$	$16.9$ ms
WHISK	$O(\sqrt{N})$	$20$ ms
Sassafras	$O(1)$	$7.81$ ms ✓

Table 3: Computational overhead of SSLE protocols on a blockchain. $N$ is the total number of participants.

Key Takeaways

This concludes the three-part blog post series on Sassafras. Here are some key takeaways:

• Single leader election: Sassafras elects a single block producer for each slot, ensuring faster consensus compared to protocols that rely on probabilistic leader election, which may not guarantee a unique leader or a leader at all times.
• Maintaining the secrecy of a block producer: Sassafras ensures the secrecy of block producers to mitigate against denial-of-service (DoS) attacks.
• Lightweight: Sassafras features exceptionally low communication and computational complexity and scales better than existing solutions.

---

Further Reading: Security Comparison with WHISK

For the interested reader, we now give a detailed comparison of the unpredictability levels achieved by WHISK and Sassafras under the assumption that the adversary can corrupt up to $1/3$ of parties. These can be a combination of corrupted and weakly corrupted parties, captured by $\alpha + \alpha_w \leq 1/3$, where $\alpha_w$ is the maximum fraction of weak corruptions (e.g., DoS-type attacks; see Part 2 for more details.) WHISK, like Sassafras, permits a fraction of leaders to be leaked, as seen in Table 1 under the "Public" column.

Let us consider the following toy example to demonstrate the implications of this in both protocols. Out of one million validators on Ethereum, the proposed number of validators to run the WHISK protocol is $N = 2^{14} = 16384$. Now consider when $\alpha = \alpha_w = 1/6$, so that $\alpha N = (1/6)(16384) = 2730$ parties can be corrupted, and $2730$ parties can be weakly corrupted. Sassafras results in $(1-\alpha)\alpha N = (1-1/6)(1/6)(16384)= 2276$ leaked leaders, but the anonymity set is of size $(1-\alpha)N/2 = 6826$, so the leaders remaining achieve good privacy, and, as discussed in Part 2 , the leaked leaders still allow consensus to succeed. In contrast, WHISK only leaks $\frac{-1.25 \ln(1-\alpha)}{\sqrt{N}} N = 29$ leaders, but the anonymity set is only of size $(1-\alpha) \sqrt{n} = 107$ for the remaining honest leaders. That is, all honest leaders in the set of $16384$ parties can be easily targeted for weak corruption. Indeed, it is in the adversary's interest to simply weakly corrupt all $1/3 n = 5460$ parties in its "corruption budget." Thus, WHISK is insecure under our threat model, as is the single election protocol Shuffle-1. The main purpose of deploying SSLE protocols in blockchains is to mitigate against DoS attacks, which our model accounts for strongly, and Sassafras achieves by design.

WHISK targets efficiency over other SSLE protocols by performing $\ell < N$ batch elections with $O(\sqrt{N})$ communication and computational complexity (see Table 3). Sassafras's efficiency surpasses that of WHISK by performing an arbitrary number (not restricted to $\ell < n$) of batch elections with $O(1)$ communication and computational complexity.