How Primary Committee Size Impacts Blockchain Security in Discrepancy Detection Protocols

Table of Links

Abstract and 1. Introduction

2. Key Concepts

   2.1 Append-Only Log and 2.2 Virtual Machine State

   2.3 Transactions As Curried Functions

   2.4 Natural Names of State

   2.5 Ground Truth

   2.6 Efficient Representations of State

   2.7 Checkpoints

   2.8 Execution Parameters: callData

   2.9 Execution Ordering

   2.10 Deciding on the Correct State

3. Ideal Layer 2 Design

   3.1 VM Job Queue and Transaction Order Finality

   3.2 Data Availability and Garbage Collection

   3.3 State Finality

   3.4 Checkpoint Finality

4. Conclusion and References

A. Discrepancy Detection Security Parameters

A Discrepancy Detection Security Parameters

The key security parameter for the discrepancy fastpath approach is the size of the primary committee used for the DD protocol. The size of the slow path DR backup committee depends on the DR protocol chosen, but it can be chosen generously, since the DR protocol should be used extremely infrequently. Any existing state verification protocol can be used, e.g., consensus based on majority voting, 2/3 supermajority, etc.

For the DD primary committee, the security assumptions are that faults are independent, e.g., due to installation-specific configuration errors, personnel security, bribery, etc; and that at most some fraction of the available participants are faulty. We will use a random selection to choose a subset of the available participants to serve in the primary committee. Because we are looking for any discrepancy in the reported output state, this is not a stake-weighted voting scheme.

Let T denote the total number of available participants, and B denote the number of faulty or Byzantine participants.[6] We need to pick C, the size of the primary committee.

Our goal is to make the probability that the entire primary committee are faulty is negligibly small. An acceptable level would be small enough such that the expected number of committee formations needed before an all-faulty committee is chosen is enormous, so that even with a high worst-case rate of committee selections, many lifetimes must pass before such an event would take place.

Since DR schemes cannot work unless there is at least an honest majority, we will use B ≈ T /2 as worst-case parameters, e.g., T = 100 and B = 49. With a committee size of C = 25, this is an expected W = 3.837 · 109 committee selections. Assuming a committee selection rate of 1, 000 per hour, this works out to about 437 years before an all-faulty committee is encountered. This ramps up quickly: at C = 26, it works out to be about 1, 368 years; at C = 30, it is about 177, 740 years. Obviously if we were to assume B ≈ T /3, the primary committee can be even smaller for the same level of security.

An interesting observation is that DD could work with a pool of participants that are less trustworthy than would be feasible with other protocols, i.e., where honest nodes are not a majority, as long as the DR participant pool is acceptable (e.g. a majority are honest for when DR uses honest majority). Estimating whether participants are corruptible is difficult, obviously, and it is not clear why we might have to work with a faulty-majority participant pool, though the possibility is intriguing. A possibility is to require periodic external security audits to participate in the DR pool, and have less stringent requirements to participate in the DD pool.

[6] If we wish to use the BAR model, instead of B we would use B + R as the worst case to assume that all rational participants could be bribed etc, by the virtue of arbitrary token creation/transfers.