11institutetext: University of Washington at Seattle

#  BigDipper: A hyperscale BFT system with short term censorship resistance

Bowen Xue  Soubhik Deb  Sreeram Kannan

###### Abstract

Byzantine-fault-tolerant (BFT) protocols underlie a variety of decentralized
applications including payments, auctions, data feed oracles, and
decentralized social networks[15, 29]. In most leader-based BFT protocols, an
important property that has been missing is the censorship resistance of
transaction in the short term. The protocol should provide inclusion
guarantees in the next block height even if the current and future leaders
have the intent of censoring. In this paper, we present a BFT system,
BigDipper, that achieves censorship resistance while providing fast
confirmation for clients and hyperscale throughput. The core idea is to
decentralize inclusion of transactions by allowing every BFT replica to create
their own mini-block, and then enforcing the leader on their inclusions. To
achieve this, BigDipper creates a modular system made of three components.
First, clients use a transaction broadcast protocol to send transaction to
multiple replicas. As a distribution of replicas receiving the client’s
transactions, they prepare mini-blocks to send to the data availability (DA)
component, which characterizes the censorship resistant properties of the
whole system. We design three censorship resistant DA (DA-CR) protocols whose
properties are captured by three parameters. The third component interleaves
the second DA-CR protocol into the leader based BFT protocol, it enforces the
leader to include all the data from the DA-CR into the final block. At last,
we demonstrate an integration with a two-phase Hotstuff-2.

##  1 Introduction

Short term censorship resistance provides an unusual property that
differentiates from the conventional liveness property in BFT protocols. It
guarantees transaction inclusion in the next block even if the current and
future leaders have the intent of censoring. This property is especially
useful for transactions whose value is sensitive to block heights when they
are included; for example, an auction bid trying to enter at the last
permissible block height. The benefits of th property can be generalized
further, such as periodic inclusion at precise block height and real time
interactions like high frequency trading, collateral liquidation and web3
social network. In a partially synchronous network, conventional leader based
BFT protocols [42, 9, 30, 14] cannot provide this property, because the leader
unilaterally decides which transaction appear at what place. The middleman
nature of the leader creates a principle agent problem between the BFT
protocol and the leader, where the leader can extract benefits from the
protocol through arbitrage, sandwich attack and bribery for censorship. There
are prior works[27, 28] that use a notion of fair ordering to constrain the
leader. However, those protocols require every transaction to be received by
majority of replicas, so that a fair order consensus can be reached based on
the relative ordering of receiving time for producing a first come first serve
(FCFS) ordering. Both fairness and censorship resistance are addressed in one
shot, but it comes with downsides of limited scalability and high protocol
complexity. Moreover, the rationale and implication of FCFS is still at
debate. BigDipper treats the problem differently by focusing primarily on the
property of short term censorship resistance while leaving an interface to
support any ordering mechanism. The benefits are twofold. First the property
of short-term censorship resistance itself is useful for many applications, by
removing fair ordering constraint the throughput of the protocol can scale
linearly as the number of replicas joining the system increases. Second, by
decomposing the protocol’s stack with modular interfaces, new protocols can
work directly at the fair ordering problem by stacking on top of existing
protocols. A concurrent submission called Travelers makes use of this modular
approach to develop a scalable fair ordering protocol, BigDipper can be
directly plugged in to its protocol stack as its censorship resistance BFT
consensus.

Transactions differ by their urgency for censorship resistance, like an
expiring auction bid is more important than some dinner fees transfer among
friends. But this information is known by the clients only, who are also
dynamically changing over time. So a flexible protocol is unlikely to be one
that offers a rigid inclusion guarantee for everything. The Shard protocol in
Appendix 8 fails on this part. Essentially between the protocol and clients,
there are two information asymmetries, one is about time sensitivity on the
value, the other is about which replicas are malicious. Although clients can
uses transaction value or tips to differentiate its urgency from others, but
those information alone are not enough for censorship resistance, because
determined malicious replicas can censor regardless of its tips.

In BigDipper, we offer a robust and flexible censorship resistance. It is
achieved by an architectural change to the conventional BFT protocol: all
transactions need to submit to a new component called Data Availability and
Censorship Resistant (DA-CR) layer which is maintained among the BFT replicas,
then a valid block can be created by a leader by including all the
transactions available within DA-CR. If the leader fails to include some
transactions from it, the leader will fail to reach consensus and will be
replaced for violating the liveness. But the leader enforcement alone is
insufficient to achieve censorship resistance, we need all replicas be able to
permissionlessly add transactions to DA-CR. Because the BFT replicas are
decentralized, it is used as the source for providing censorship resistance.
From the perspective of a consensus protocol, DA-CR is an intermediate layer
that restores the decentralization from the leader. In order to do that,
replicas collect and batch transactions into a new data structure called mini-
block, which is the basic unit to send to DA-CR. The final BFT block is made
of those mini-blocks. A client uses a transaction broadcast protocol to have
its transactions batched into mini-blocks by replicas.

We made two contributions for the DA-CR component. First we delineate the
properties by three parameters, $(\rho,t,\eta)$, and we produce three designs
that demonstrate different trade-offs with regard to the message complexity,
trust assumption and degree of censorship resistance. The parameterization of
each property allows us to evaluate the effectiveness of the protocol: a
protocol is more useful if it can achieve a desired property with low cost.
Specifically, $\rho$ measures the data tampering resistance to adversarial
attacks, $t$ measures the amount of censorship resistance, i.e. how many
honest mini-blocks have to be included in the final block, and $\eta$ measures
how much influence a leader can impose on the inclusion of mini-blocks. We
elaborate the exact definitions in Section 3. Each of three protocol designs
has distinct $(\rho,t,\eta)$ properties. The three DA-CR designs can be
categorized into two general design patterns depending on if they support
accountability. In an accountable protocol, every replica knows whose mini-
blocks are included in the final block. In Section 3 and 4, we delineate their
differences and implications on the derived protocols.

The second technical contribution is a transaction broadcast protocol that
enables clients to adjust the amount of resources spent on censorship
resistance. We use probability of inclusion as a quantifiable measure for the
amount of censorship resistance from which a client can choose the desired
quantity. Once a probability is selected, this quantity can translate directly
to the number of transaction copies that should be sent to distinct replicas.
The more copies of a transaction a client sends, the higher chance the
transaction would get included, up to probability $1$. Allowing clients to
express inclusion urgency through probability simplifies protocol complexity.
We discuss spamming and transaction de-duplication in Appendix 20, the central
idea is to correlate the spent resources with transaction fees.

A final technical contribution is an enforcement rule inserted into the BFT
consensus path, so that no leader can append a BFT block to the ledger unless
all the data from the DA-CR are included. We provide an integration with a
two-phase leader based BFT protocol, Hotstuff-2[30], in Section 6.2, and prove
both safety and livenesss. The integration fits all DA-CR parts inside the
two-phase BFT protocol, and requires no change to pacemaker during leader
rotation.

####  1.0.1 Why we prefer leader based protocol

It is an empirical observation that resource distribution are highly
asymmetrical. For example, the top three miningpool on Bitcoin occupy $65.9\%$
of total hash power[5]. In Ethereum post-merge, Flashbot relay propagated
$80\%$ of blocks[41]. We expect similarly for parties that runs hardware
(replicas). Because BFT protocols rely on at most $1/3$ replicas are
malicious, it is less likely that decentralized parties would collude together
when the total number of replicas are large. To achieve that, we need the
communication complexity on each node to be small. But since resourceful
parties still exists and participates the system, they can play the role to
perform heavy computation, as long as they are rewarded accordingly. Leader
based protocol fits well to this model. More discussions in Appendix 9.

###  1.1 Comparison with Other BFT protocols

Many asynchronous BFT protocols by nature provide censorship resistance,
including HoneyBadger [31] and DispersedLedger [40]. In HoneyBadger, every
replica creates its own mini-block and runs a binary agreement protocol in
parallel to commit at least $n-f$ mini-blocks. There is no centralized leader
in the system, and because of that, the asynchronous system enjoys censorship
resistance inherently. Many DAG-basd BFT protocols like Bullshark[39],
Tusk[16], Dumbo[21], VABA[1] are also leaderless and therefore censorship
resistant. But without coordination, the leaderless protocols have a all-to-
all communication pattern which hurts communication complexity.

To understand the protocol’s trade-offs, we use three metrics to
systematically compare their performance: worst case inclusion distance,
system throughput, and block interval. The worst case inclusion distance
measures the largest number of blocks malicious replicas can prevent a
transaction from entering the blockchain in the worst scenario.

Second, a performant blockchain should support many clients and satisfy
throughput requirements for a wide range of applications. Assuming each
replica has a constant bandwidth $C_{band}$, ideally we want the maximum
system throughput to increase linearly as more replicas join the network. As
more replica joins, it reinforces both the decentralization of blockchain and
the system performance. To capture the scalability of the system, we measure
it as a ratio between the total system throughput and individual bandwidth.

The third metric focuses on the latency of the block interval, because the
shorter the interval is, the faster a client can receive transactions
confirmation. The latency can be decomposed to two parts: number of round
trips and communication latency which is a ratio between the communication
bits and bandwidth.

Table 1: Comparison of BFT protocol in a system of $n$ replicas

BFT | Coor- | Per Replica Communication | System | Number | Sum | Worst | Max
---|---|---|---|---|---|---|---
protocols | dinating | DA | Consensus | / Replica | Comm | Comm. | Inclusion | Adv.
| Leader | Complexity | Download | Complexity | Throughput | Steps | Complexity | (blocks) | Ratio
Hotstuff[42] | ✓ | $O(nb)$ | ✓ | $O(1)$ | $O(1)$ | $4$ | $O(nb)$ | $f+1$ | $0.33$
HoneyBadger[31] | $\times$ | $O(nb+\lambda n^{2}\log{n})$ | ✓ | $O(n^{2}\log{n})$ | $O(1)$ | $3+\log{n}$ | $O(nb+n^{2}\log{n})$ | $1$ | $0.33$
DispersedLedger[40] | $\times$ | $O(b+n^{2})$ | $\times$ | $O(n^{2}\log{n})$ | $O(n)$ | $3+\log{n}$ | $O(b+n^{2}\log{n})$ | $1$ | $0.33$
Prime[3] | ✓ | $O(nb+n^{2})$ | ✓ | $O(n^{2})$ | $O(1)$ | $6$ | $O(nb+n^{2})$ | $1$ | $0.33$
Dumbo-2[23] | $\times$ | $O(nb+n^{2}\log{n})$ | ✓ | $O(n^{2})$ | $O(1)$ | $20$ | $O(nb+n^{2}\log{n})$ | $1$ | $0.33$
Dumbo-NG[21] | $\times$ | $O(nb)$ | ✓ | $O(n^{2}\log{n})$ | $O(1)$ | $9$ | $O(nb+n^{2}\log{n})$ | $1$ | $0.33$
VABA[1] | $\times$ | $O(nb)$ | ✓ | $O(n)$ | $O(1)$ | $13$ | $O(nb)$ | $1$ | $0.33$
Dag-Rider+AVID[26] | $\times$ | $O(nb+n^{2}\log{n})$ | ✓ | $O(n^{2}\log{n})$ | $O(1)$ | $12$ | $O(nb+n^{2}\log{n})$ | $1$ | $0.33$
Narwhal-Hotstuff[16] | ✓ | $O(nb+n^{2})$ | ✓ | $O(1)$ | $O(1)$ | $6$ | $O(nb+n^{2})$ | $1$ | $0.33$
Tusk[16] | $\times$ | $O(nb+n^{2})$ | ✓ | $O(n^{2}\log{n})$ | $O(1)$ | $9$ | $O(nb+n^{2}\log{n})$ | $1$ | $0.33$
Bullshark[39] | $\times$ | $O(nb)$ | ✓ | $O(n^{2}\log{n})$ | $O(1)$ | $4$ | $O(nb+n^{2}\log{n})$ | $1$ | $0.33$
BigDipper-$\nicefrac{{1}}{{4}}$ | ✓ | $O(b)$ | $\times$ | $O(1)$ | $O(n)$ | $4$ | $O(b)$ | $1$ | $0.25$
BigDipper-$7$ | ✓ | $O(b+n)$ | $\times$ | $O(1)$ | $O(n)$ | $4$ | $O(b+n)$ | $1$ | $0.33$
BigDipper-Lite | ✓ | $O(b+\log{n})$ | $\times$ | $O(1)$ | $O(n)$ | $4$ | $O(b+\log{n})$ | $1$ | $0.33$

Table 1 summarizes the metrics for most recent and important BFT protocols in
the past. The analysis of the table is provided in Appendix 11. At the high
level, we can decompose any consensus protocol into data availability and
consensus. Data availability (DA) ensures that everyone has access to a common
data in the unit of blocks, whereas consensus restricts the ordering among
blocks. Recent DAG based consensus protocols decouples into consensus and a
transport layer which satisfies DA. DA can be either achieved by requiring
every replica to have the full data while reaching agreement, or achieved by
applying erasure code on the data such that replicas do not have the full data
after finishing the agreement. We add a sub-column to table, Download, to
signify for each protocol. We separately display per replica complexity for DA
and consensus.

If a protocol requires every replica to have the entire BFT block while making
agreement, then maximal system throughput is upper bounded by each replica’s
bandwidth. So the system to replica throughput ratio is always $O(1)$. In
contrast, with erasure code it is possible to reach agreement on the data
without downloading it. Every replica’s bandwidth is spent on distinct set of
transactions, so the overall system throughput scales linearly as $n$
increases. We note that there are types of applications that do not require
full data for execution. For example, a sequencer[18] in the rollup
architecture does not need to execute the transaction. But more generally, as
roles are diversified in the infrastructure software, like consensus and
execution separation in Ethereum. It is possible only a handy number heavy-
duty nodes are providing the execution API. As long as, the result is provided
with vaild proof, regular replicas does not need to have all transaction data
to re-execute everything.

In Hotstuff, the worst inclusion distance is $f+1$, because there can a
sequence of $f$ malicious leader. Narwhal achieves probabilitic censorship
resistance with DAG. Prime[3] is an early leader based protocol with
censorship resistance, but its is designed for defense against performance
degradation. All leaderless BFT protocols has a distance of $1$ given
sufficient replicas have the transaction.

When computing the confirmation latency, the communication step is a fixed
number. The variable part comes from the communication bit complexity, which
is the sum of the DA and consensus complexity. Most leader based protocol has
a small complexity on consensus, because there is a central role to coordinate
communication among replicas to reach consensus. Most leaderless asynchronous
BFT protocols have high complexity on both DA and consensus, those also
include DAG based protocols like Dag-Rider[26], Bullshark[39], Dumbo[23, 21].

BigDipper-$\nicefrac{{1}}{{4}}$ achieves constant overhead while achieving
linear system capacity but it requires a stronger security assumption of
$n\geq 4f+1$. BigDipper-$7$ restores the $1/3$ assumption, but each replica
incurs a linear overhead at the download path. At last, BigDipper-Lite is a
modification based on BigDipper-$7$, that achieves all desired properties with
latency of $O(\log{n})$.

##  2 Background and Related Works

###  2.1 DA, VID and Erasure code

Data availability is implicit by all BFT protocols such that all replicas have
access to a common ordered data at any time. Most leader based BFT protocol
uses a simple DA by having the leader broadcast the data to everyone. There
are more sophisticated designs of DA, including AVID [13], AVID-FP [24],
AVID-M [40], SEMI-AVID-PR [33]. We compare our censorship resistant DA with
them in Appendix 13.2. Verifiable Information dispersal(VID) is a technique
that uses Reed-Solomon code to split data into $O(n)$ chunks, and each replica
only stores a constant number of chunks to ensure the data is reconstructable.
The verifiability ensures any two clients always retrieve identical data.

A Reed-Solomon(RS) erasure code is specified by a pair $(k,h)$, where $k$ is
the number of systematic chunks, created from the input data, and the second
parameter $h$ is the coding redundancy. The newly generated data are called
parity chunks. The ratio between $k$ and $h$ is called the coding ratio. The
encoding process of RS code is based on the idea of polynomial
interpolation[35], which is a linear operation. Given an input array, the
encoding can be implemented so that the output is a concatenation of input
data and parity chunks. We use $rsEncode,rsDecode$ to refer to the encoding
and decoding operations. Appendix 12.3 contains more detailed introduction.

###  2.2 Polynomial Commitment and KZG

A polynomial commitment scheme [25] treats data as a polynomial and provides
primitives including commit, createWitness, and verifyEval. The commit
primitive provides a concise and unique representation of a polynomial. It has
a Polynomial binding property such that it is computationally infeasible to
find two polynomials that commit to the same commitment. With primitives
createWitness, verifyEval, the scheme allows any party to reveal(open)
evaluations at specific indices along with witnesses(proofs) without
disclosing the entire polynomial. When presented with a correct witness, any
verifier can use verifyEval and check that the evaluations are indeed correct
against the commitment. The scheme has a Evaluation binding property such that
it is computationally infeasible to find two witnesses for two different
polynomial evaluations at the same evaluation index that passes the
verifyEval. Kate-Zaverucha-Goldberg (KZG)[25] is a polynomial commitment
scheme that is linear in commitments and witnesses.

KZG can be applied on a two dimensional matrix. Suppose we have $n$
polynomials, each of degree $d-1$, and we want to encode it with a coding
ratio of $\frac{1}{3}$. A matrix can be created where every column contains
one polynomial. The RS encoding is applied to each of $d$ row by extending the
evaluations to $2n$ more points. The commitment of every newly generated $2n$
polynomials along the columns are the polynomial extension of the first $k$
column commitments. It is due to the linearity property of KZG and RS [11]. A
good reference can is available at [33]. Figure 2 provides a visualization for
such 2D encoding. More discussion can be found in Appendix 12.3 and 12.5.

###  2.3 Combined Signature Scheme and CRHF

We use combined signature to refer to a signature generated from either a
multi-signature or threshold signature scheme. We will use the exact name when
a specific signature scheme is used. On paring friendly curves, a practical
way to aggregate multiple signatures on a common message into one signature is
to use BLS multi-signature [6]. The signature scheme provides three secure
primitive $\sigma_{i}\leftarrow$ ms-sign$(sk_{i},m)$;
$\sigma,I_{\sigma}\leftarrow$ ms-agg $(pk_{1},\sigma_{1}\cdots$
$pk_{,}\sigma_{t})$; $bool\leftarrow\textit{{ms-
verify}}(I_{\sigma},m,\sigma)$, where $I_{\sigma}$ is an indicator vector for
the signers, which has $O(n)$ size. In contrast to multi-signature, a
threshold signature show out of $n$ signers at least some ratio number of
signers have signed a common message, and it requires only constant size as
opposed to $O(n)$ size. To convert a list of data into a single message, we
assume a collision resistant hash function(CRHF) with negligible probability
for two different data to hash into the same digest. A combined signature is
valid if it contains $n-f$ signatures.

###  2.4 Security Assumptions for BigDipper

The network is assumed to be partial asynchronous. In this networks, there is
a notion of an unknown Global Stabilization Time (GST), after which all
transactions can arrive within a known $\Delta$ duration. The security
assumption is $n\geq 3f+1$. all malicious replicas can have arbitrary network
latency. The malicious replicas can be separate or coordinated by a single
adversary. Transaction censoring occurs when malicious replicas (including the
leader) exclude some transactions on purpose (it is different from the
situation when an honest replica is impatient of waiting and miss
transactions,it is not on purpose).

##  3 Censorship Resistant DA

###  3.1 Primitives

BigDipper is built on three protocol components for providing short term
censorship resistance in leader based BFT protocols. The first component
delivers clients’ transactions to BFT replicas; DA-CR ensures the censorship
resistance; the last component integrates the DA-CR with a standard BFT
protocol, like Hotstuff. The DA-CR is a critical for BigDipper BFT system as
its properties determine the degree of censorship resistance. In this section,
we outline the interfaces and their properties.

The DA-CR provides a Disperse invocation that distributes transactions data
among replicas, and a Retrieve invocation to safely retrieve the data from
honest replicas. For censorship resistance, we require the Disperse invocation
be initiated in a distributed manner from at least $n-f$ replicas, and the
final dispersal data $B$ assembled by the leader must also contain at least
$n-f$ mini-blocks. For the Retrieve invocation, either replicas or clients can
invoke the procedure to retrieve partial or full dispersed data.

Every invocation is initiated against a DA-CR instance with a unique ID, which
is used by replicas and clients to identify the correct context for intended
invocations. The Disperse invocation is associated with two events, a Start
event and a Finish event. The Finish event evaluates to the following types:
Complete or Incomplete. Since a malicious leader can stall the protocol by
inactivity, the Incomplete type serves as a trigger for the leaders
replacement. If a Disperse invocation finishes with the type Complete, it will
return a commitment $C$ and its associated combined signature from $n-f$ out
of $n$ replicas. It’s possible that a Completed Disperse invocation may not
contain mini-blocks from all $n$ replicas. This is because either some honest
replicas are late for the leader’s collection time, or some malicious replicas
refusing to participate. For the missing parts, a protocol designer can
meditate on the trade-offs and decide if to allow the leader to fill in its
own data. We elaborate on this trade-off in Appendix 18.

###  3.2 Properties of DA-CR protocols

A leader based DA-CR protocol that offers censorship resistance must provide
the following properties for all DA-CR instances. The DA-CR protocol relies on
partial synchronous assumption, which is different from asynchronous protocols
like AVID[13], AVID-M[40].

  * •

Termination: If some replicas invoke Disperse$(B)$, then those replicas
eventually Finish the dispersal. If at least $n-f$ replicas invoke
Disperse$(B)$ and the leader is honest with a network after GST, then the
dispersal Finishes with type Complete.

  * •

Availability: If an honest replica Finished a dispersal with type Complete,
then any honest retriever can invoke Retrieve and eventually reconstruct a
block $B^{\prime}$.

  * •

Correctness: If an honest replica Finished a dispersal with a type Complete,
then any honest retriever always retrieves the same block $B^{\prime}$ by
invoking Retrieve. If the leader is honest, then $B=B^{\prime}$, where $B$
contains all the mini-blocks available to the honest leader at dispersal.

  * •

Commitment Binding: If an honest replica Finished a Disperse$(B)$ invocation
with a type Complete and a valid combined signature on its commitment, no
adversary can find another different $B^{\prime}$ that verifies correctly
against the combined signature.

  * •

Inclusion-t: If an honest replica Finished a Disperse$(B)$ invocation with
type Complete, the dispersed data must include at least $t$ mini-blocks from
honest replicas.

  * •

Space-Capturing-$\eta$: If an honest replica Finished a Disperse$(B)$
invocation with type Complete, the dispersed data contains at most $\eta$
captured mini-blocks by the leader.

  * •

Data-tampering Resistance-$\rho$: In an accountable inclusion mechanism, if an
honest replica Finished a Disperse$(B)$ invocation with type Complete, the
dispersed data $B$ must ensure at least $\rho$ mini-blocks are not tampered in
the DA-CR instance. If $\rho=n$, protocol guarantees no data can be tampered.

The last three properties are new for delineating the censorship resistance.
As mentioned in Section 1, $(t,\eta,\rho)$ characterize the properties of
censorship resistance. We will use an important concept called Attestation
later. In short, it is a signature on a mini-block by a replica to declare the
replica intends to include the mini-block. We refer the readers to Appendix
13.1 for formal definitions of Space-capturing, Accountable mechanism shown in
the properties.

Next, we describe three DA-CR protocols, Table 2 summarizes their properties.
For ease of reference, we use the suffix of each protocol combining with
Card111Card stands for censorship resistance data availability with flexible
ordering. as the name for DA-CR component. Vanilla is a protocol that takes
minimal changes from a conventional leader based BFT protocol to a censorship
resistant one,it is presented in Appendix 16.1.

Table 2: Comparison of DA-CR component of BFT protocols

BigDipper | DA-CR | BFT $(n\geq)$ | $\rho$ | $t$ | $\eta$ | message | hyperscale
---|---|---|---|---|---|---|---
protocol | protocol | assumption |  |  |  | complexity | throughout
BigDipper-$7$ | Card-$7$ | $3f+1$ | $n$ | ${n-2f}$ | $0{\dagger}$ | $O(b+\lambda n)$ | ✓
BigDipper-$\nicefrac{{1}}{{4}}$ | Card-$\nicefrac{{1}}{{4}}$ | $4f+1$ | - | $n-3f$ | $n-f-1$ | $O(b+\lambda)$ | ✓
BigDipper-Lite | Card-Lite | $3f+1$ | $n$ | $n-2f-o(f/\log(f))$ | $o(f/\log{f}){\dagger}$ | $O(b+\lambda\kappa\log n)$ | ✓

$\lambda$ is a security parameter with fixed size, which uniquely represents
the data block. $\kappa$ is a small constant. ${\dagger}$ means the parameter
$\eta$ can increase up to $\eta=f$, see Appendix 18.

##  4 DA-CR Protocol Designs

We begin by presenting a DA-CR design called Card-$7$ which has properties of
$(\rho=n,t=n-2f,\eta=0)$. We present its variant Card-$\nicefrac{{1}}{{4}}$ in
Appendix 15. We provide an outline for Card-Lite that achieves $O(\log{n})$
complexity at the end.

###  4.1 Card-$7$ Protocol

At a high level, the Card-$7$ protocol relies on the Reed-Solomon code, a 2D
KZG and an aggregate multi-signature scheme to support the invocations with
mentioned properties.

It is designed to be an accountable inclusion mechanism, so that every replica
know whose mini-blocks get included. The formal protocol is given in Algorithm
2 from Appendix 14.1. In the following sections, we present an outline of both
Disperse and Retrieve invocations in sequence, and proof is given in Appendix
14.5.

Figure 1: Flow diagram for a DA-CR protocol

Figure 2: A 2D matrix data structure used by the leader for producing $3n$
commitment. Replica $1$ is excluded, as its data is $0$. $b$ denotes mini-
block(systematic chunk), orange are for parity chunks.

####  4.1.1 Disperse Invocation

The Disperse invocation for a DA-CR instance involves two round trips between
replicas and the leader, and its workflow is shown in Figure 1. For ease of
reference, we name the four communication messages as collection, dispersal,
approval and agreement in sequence. In the beginning of every BFT round, there
is special message called Signal which is received from a pacemaker inside a
BFT protocol. More details is given in Section 14.1.1.

When replicas initiate the Disperse invocations distributedly for some DA-CR
instance, each one of them generates its own mini-block, and a corresponding
attestation by signing the kzg commitment of the mini-block. A collection
message is sent by each replica to transfer (attestation, mini-block) to a
leader. Because at most $f$ malicious replicas could simply stop responding,
the leader waits for receiving at least $n-f$ mini-blocks and the
corresponding attestations. We refer the collected attestations as the
attestation set whose cardinality is $m$ equal to the number of received mini-
blocks.

When the leader is processing the collection messages shown as the yellow box
of Figure 1, data is encoded with Reed-Solomon code. Figure 2 provides a
visualization of the data structure. The received mini-blocks are laid out as
columns in a matrix, and parity chunks are generated by interpolating
additional values in each row on the matrix. The first $n$ columns of the
matrix are block space designated for mini-blocks from $n$ replicas, we refer
their corresponding commitments as the commitment list. If a replica $i$ is
excluded (when $m<n$), the corresponding $i$-th column contains identically
zero data and its commitment is $0$; otherwise the column is filled with data
from the received mini-block.

For every row, the coding ratio used by the erasure code is $\frac{1}{3}$,
which is equivalent to say two parity chunks (columns) are generated per mini-
block. Appendix 14.2 discuss the calculation to arrive at the $\frac{1}{3}$
ratio. After encoding, the leader prepares a dispersal message for each of $n$
replicas. Every message contains identical commitment list of size $n$ and an
attestation set of size $m$, but also contains two parity chunks unique for
every replica. This ensures every chunk is stored by only one replica, which
is essential for safe retrieval.

When receiving a dispersal message, a replica has several verification
procedures, shown in Algorithm 2 (line 10-12). They verify the leader has
included at least $n-2f$ honest mini-blocks, and parity chunks are generated
correctly and the leader has not tampered any data. If all verifications pass,
a replica computes a final commitment $C$ with a collision resistant hash
function (CRHF) on the commitment list. The final commitment $C$ is used as
the signing message for approving the dispersal by the multi-signature scheme
(2.3). After that, a replica sends a approval message containing the signature
to the leader. An honest replica only signs once for every unique DA-CR
instance, and it is strictly increasing as the BFT view number.

In Figure 1, after receiving approval messages, a leader waits to accumulate
$n-f$ multi-signature before proceeding. Although $f$ out of them might be
malicious, the remaining $f+1$ approval from honest replicas is sufficient to
ensure the data availability since $3(f+1)>n$. With sufficient approval, the
leader generates an aggregate signature and signer bitmap (Section2.3), and
sends the identical agreement message to all $n$ replicas. When a replica
receives a valid aggregate signature with sufficient signers, the
corresponding DA-CR instance is considered Finished with a Complete type.
Otherwise after timeout, a replica can conclude that the DA-CR instance
Finishes with a Incomplete type.

####  4.1.2 Retrieve Invocation

The retrieval algorithm is formally defined in Algorithm 4 from Appendix 14.3.
The Retrieve invocation guarantees any parts from dispersed data in any DA-CR
instance are retrievable by anyone. If the interested data is one mini-block,
a Retrieve invocation is first sent to the leader and the replica who possess
the data; upon responded with data, the retriever checks correctness by
computing polynomial commitment on the data and comparing with the commitment
list. If both deny the request, a replica queries and finds $f+1$ other honest
replicas which responds correct chunks consistent to the commitments. Because
all replicas have distinct chunks, the retriever can perform rsDecode to get
the original dispersed data, which contains all mini-blocks. For partial
retrieval from a mini-block $b_{p}$, the invocation is similar to full mini-
block. More importantly, if both deny, the retriever can query partial data
and does partial reconstruction without needs to construct the entire
dispersed data. Because each replica possesses three chunks, a retriever needs
only contact roughly $\frac{4f}{5}$ random replicas to reconstruct the data
with high probability. Appendix 14.4 presents analysis and figures.

###  4.2 Card-Lite Protocol

Card-Lite is an improved protocol based on Card-$7$ that only requires
$O(\log{n})$ communication overhead. But it has slightly weaker censorship
resistance, as shown in Table 2. We outlines the intuition behind the protocol
and provide the complete protocol and proofs in Appendix 17.

How to differentiate two types of leaders is the key problem for any honest
replica when asked to approve a dispersal. In the context of censorship
resistance, an honest leader is required to include at least $2f+1$ mini-
blocks, whereas the censoring leader includes less than $2f+1$ mini-blocks. It
is easy to detect the malicious leader in Card-$7$, because everyone receives
the entire commitment list. But we want each replica receives only
$O(\log{n})$ commitments and attestations.

The core idea is to distinguish the two types of leader through random
sampling. If a leader does not include sufficient mini-blocks in its
commitment, there will be some random samples which the leader is unable to
answer. If the leader is unable to answer too many of them, the leader would
not be able to collect $2f+1$ signatures to make progress.

The idea assumes that the leader cannot lie about the relation between
responses and its commitment. To achieve that while keeping a low complexity,
we require the leader to use a doubly homomorphic commitment scheme[10] on the
commitment list (see Appendix 17.1 for background). So in the protocol, a
sample for chunk $i$ would contain: attestation from replica $i$, commitment
$c_{i}$, final commitment $C$, a kzg binding proof for $c_{i}$ with respect to
$C$). Because the proof is aggregatable and has a size of $O(\log{n})$, the
overall complexity per sample is just $O(\log{n})$. A random query is success
if the leader can provide the valid response, and failure otherwise.

Suppose a leader has constructed a 2D KZG matrix and receives a random query,
clearly the honest leader type has higher chance of being able to response as
opposed to the malicious type. Then if a batch of $k$ random queries are
requested, the probability of having all $k$ success query is exponentially
decreasing for both types. But if we independently retry (boost) $L$ number of
batches, eventually the probability of having at least one successful batch
would be sufficiently high. A key observation is that the honest type requires
much less boosting, the exact difference depends on the number of mini-block
$s$ which the malicious type censors. As shown in Appendix 17, if the leader
is censoring $s=\Omega(f/\log{f})$ mini-blocks, and all honest replicas sample
$L=o(n)$ each, the extremely high probability the malicious type is exposed,
but the honest type can always pass the query in all cases.

If done naively, every replica need to send $kL$ number of random queries,
which is much larger than $O(\log{n})$. But with Fiat-Shamir transform on the
final commitment, we can make the process non-interactive. The leader
deterministically generates random queries and sends back only one successful
batch to the replica to prove non-censorship. Upon receiving a batch, a
replica can independently verify the tuple and correctness of the randomness
generation. The full analysis are presented in Appendix 17.

##  5 Transaction Broadcast

In the new architecture, all replicas can add transaction to the final block,
the client now has more options to choose which replicas to send to. We
provide a transaction broadcast mechanism which clients can use to achieve a
desired amount of censorship resistance.

###  5.1 Navigator Protocol

The interface to the protocol is a submit function call, shown in Algorithm 5
from Appendix 19.2. To send a transaction, a client provides two inputs: the
transaction and number of copies $x$. The algorithm will send the transaction
to $x$ random replicas available for the view number. Replicas continuously
wait for transactions to arrive, and include them at best effort.

The difficulty with the interface is to decide how many copies to send for
achieving some desired probability for inclusion in the next block. To do
that, we create Table 3 based on the worst case assumption that all $f$
malicious replicas are censoring transactions all the time. Depending on the
type of leader and number of included honest mini-block $q$, we can compute
the probability of inclusion as a function of $x$. However, since both the
leader type and the number $q$ is unknown to the client, we have to model the
leader with a bernoulli variable with $p=2/3$ for each possible leader, and a
uniform variable for all possible $q$. Later, as the clients gets more data,
it is possible to update those prior based on Bayesian method. The lower bound
for $q$ is determined by the Inclusion-t property offered by the DA-CR. When a
leader is honest, $q$ has a range from $t$ to $n-f$. On the other extreme,
when the leader is malicious, there can be at most $t$ collected honest mini-
blocks. At runtime, the actual number of $q$ would fall anywhere between $t$
and $n-f$. In the Table, if a client sends $x\ll f$ copies, determined
malicious replicas can censor it with certainty. However, in Appendix 19.6, we
show that although a malicious leader can censor some clients who sends only a
few copies, the probability to censor $u$ different transactions altogether
decreases exponentially as $u$ increases. The rest of the section delineates
how to compute the Table.

Table 3: Probability of inclusion as a function of number of copies and number
of honest inclusion

Leader type | Malicious | Honest | Honest
---|---|---|---
number honest mini-block | $q=t$ | $q=t$ | $q=n-f$
$n-t+1\leq x\leq n$ | $\Pr(IN)=1$ | $\Pr(IN)=1$ | $\Pr(IN)=1$
$f+1\leq x<n-t+1$ | see 5.2.2 | see 5.2.1 | $\Pr(IN)=1$
$0<x<f+1$ | $Pr(IN)=0$ | see 5.2.1 | see 5.2.1

The cases with probability $1$ can be proved by the pigeonhole principle. For
instance, suppose $x=n-t$ and $q=t+1$, then there must be at least one mini-
block from an honest replica which includes the transaction, and similarly for
any pairs with $x+q\geq n+1$. On the other extreme, when a client sends less
than $x\leq f$ transactions to replicas and if a malicious leader has intent
of censoring the transaction, the adversary can selectively including those
$f+1$ honest mini-blocks without the transaction.

###  5.2 Probabilistic Transaction Inclusion

####  5.2.1 Probability of Inclusion with an Honest Leader

Given the leader is honest and the client chooses $x$ replicas randomly
without replacement, let $X$ be a random variable indicating the number of
honest replicas that have the client’s transaction. For
$0<i\leq\min{(x,n-f)}$, the probability of the transaction being included by
$X=i$ honest replicas is $\Pr(X=i;x)={n-f\choose i}{f\choose x-i}/{n\choose
x}$. Suppose $f$ malicious mini-blocks are collected by the honest leader, the
probability is

$\displaystyle\centering\Pr(\textit{IN; x,q})\@add@centering$
$\displaystyle=1-\sum_{i=1}^{x}\Pr(\textit{None }|X=i;q)\Pr{(X=i;x)}$ (1)

where $\Pr(\textit{None }|X;q)$ is the probability none of $X$ honest mini-
block containing the client’s transaction. Suppose all honest replicas have
independent and identically distributed network latency, $\Pr(\textit{None
}|X=i;q)=\prod_{j=0}^{q-1}\frac{n-f-i-j}{n-f-j}$, and the probability of
exclusion decreases exponentially as $q$ increases. We provide an empirical
evaluation in Appendix 19.4 and an table of probability in Figure 7.

####  5.2.2 Probability of Inclusion with a Malicious Leader

When a leader is malicious, but a client sends $x\geq f+1$ copies of a
transaction, the probability of inclusion equals to
$\Pr(IN)=\sum_{i=f+1}^{x}({n-f\choose i}{f\choose x-i}/{n\choose x})$, where
$f+1\leq x<n-t+1$. Further analysis is provided in Appendix 19.5.

##  6 BigDipper with BFT Integration

###  6.1 Overview

BigDipper is a system that provides censorship resistance to leader based BFT
protocols [14, 9, 42]. After transactions are included in the DA-CR, a leader
is required to take all transactions into its next block. By Commitment
binding and Correctness property of DA-CR, every replica can arrive at an
identical order. In the following, we specify the Scooping algorithm which
would be inserted into the consensus path in order to check correct inclusion
and DA. Then we demonstrate an integration with the two phase Hotstuff-2[30]
protocol which achieves all the properties in Appendix 10.1.

###  6.2 Scooping Algorithm

The Scooping algorithm is simply a procedure called verifyCard. It performs
the operation to verify if the combined signature returned by the DA-CR in
Agreement is correct. This procedure is inserted into the BFT consensus path
such that it would not proceed unless the replica can looking up its local
storage to find a valid combined signature. The algorithm is defined in
Appendix 22.1.

Algorithm 1 Hotstuff-2 adaptation

1:Modification to Enter(1)

2:As a leader, no modification. if entering the view with double certificate,
$(C_{v-1}(C_{v-1}(B_{k-1})))$, then proceed directly to Propose(2); otherwise
the leader sets a timer of $3\Delta$ then proceeds to the Propose(2)

3:As a replica, if entering a view with a double certificate, then proceed
directly to Vote-and-commit(3); otherwise the replica sends its locked
certificate and the corresponding valid combined signature of DA-CR to the
leader along with Collection message prepared from Alg.Card-$7$ line 3\- 8

4:Modification to Propose(2)

5:The leader instead of include the BFT block, it performs Alg.Card-$7$ line
22\- 26 to encode the collected mini-blocks, then broadcast the Propose and
Dispersal message together. Any certified block must come with a valid
combined signature, otherwise it must not be used for extending the next
block.

6:Modification to Vote and commit(3)

7:Before proceeding any execution, the replica performs Alg.Card-$7$ line 10\-
17 to checks the dispersal correctness and send Approval message, then
proceeds to Hotstuff-2

8:Modification to Prepare(4)

9:The leader runs Alg.Card-$7$ line 27\- 30 and send Agreement message, then
proceeds to Hotstuff-2

10:Modification to Vote2(5)

11:Replicas performs procedures from Alg.Scooping 2\- 3 before locking the BFT
block. If succeed, send along with the vote2 message a Collection message
prepared from Alg.Card-$7$ line 3\- 8.

###  6.3 BigDipper-$7$ with Hotstuff-2

DA-CR protocol can integrate with any leader based BFT that uses lock-commit
paradigm[30]. When some replicas commit a BFT block, the lock-commit paradigm
ensures safety by having at least $n-f$ replicas to lock the committed value,
such that no other value can be committed at the same block height.
HotStuff[42, 30], Tendermint [9], PBFT [14] all use the paradigm. They differ
from how liveness property is achieved when the leader is honest. If a leader
is malicious, it cannot violate the safety due to the lock, and it would be
replaced if violating liveness. We provide an integration of Card-$7$ with
Hotstuff-2, which has great properties including its simplicity, optimal
responsiveness and the two phase latency.

The integrated protocol is defined in Algorithm 1, which highlights the
additional procedures on top of the Hotstuff-2 protocol. We provide a brief
terminology of Hotstuff-2 protocol in the following; a certified block $B$ at
view $v$, whose certificate is denoted as $C_{v}(B)$, is a block with $n-f$
combined signature, certified blocks can be ranked by height; a certificate is
locked if the replicas is guarding its block; a BFT block has a double
certificate if it has been voted by $n-f$ replicas in two phases, and is safe
to commit. To help understand the protocol integration, we create a flow
diagram in Figure 10 in Appendix 23.

In the new algorithm, different from the original Hotstuff-2, a leader does
not include the entire BFT block in the Propose(2) message. Instead it uses
information dispersal and runs the encoding parts of the Card-$7$ protocol
line 22\- 26. The data availability is confirmed in exactly one round trip
later before locking any certificate. Card-$7$ does not affect Hotstuff-2
safety because the data availability is checked before locking. The abstract
signal mentioned in Section 14.1.1 can be implemented by the Hotstuff-2
pacemaker [30]. The complete proof for Safety and Liveness are presented in
Appendix 24.

##  7 Conclusion

BigDipper is a hyperscale BFT system with short term censorship resistance for
leader based protocols. It is based on the idea a DA layer can the
decentralize transaction inclusion and clients can choose amount of censorship
resistance.

## References

  * [1] Abraham, I., Malkhi, D., Spiegelman, A.: Validated asynchronous byzantine agreement with optimal resilience and asymptotically optimal time and word communication. arXiv preprint arXiv:1811.01332 (2018)
  * [2] Al-Bassam, M.: Lazyledger: A distributed data availability ledger with client-side smart contracts. arXiv preprint arXiv:1905.09274 (2019)
  * [3] Amir, Y., Coan, B., Kirsch, J., Lane, J.: Prime: Byzantine replication under attack. IEEE transactions on dependable and secure computing 8(4), 564–577 (2010)
  * [4] AWS: Aws instance type, https://aws.amazon.com/ec2/instance-types/
  * [5] blockchain.com: Bitcoin hashrate, https://www.blockchain.com/explorer/charts/pools
  * [6] Boneh, D., Drijvers, M., Neven, G.: Compact multi-signatures for smaller blockchains. In: Advances in Cryptology–ASIACRYPT 2018: 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part II. pp. 435–464. Springer (2018)
  * [7] Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: Advances in Cryptology—ASIACRYPT 2001: 7th International Conference on the Theory and Application of Cryptology and Information Security Gold Coast, Australia, December 9–13, 2001 Proceedings 7. pp. 514–532. Springer (2001)
  * [8] Bracha, G.: Asynchronous byzantine agreement protocols. Information and Computation 75(2), 130–143 (1987)
  * [9] Buchman, E., Kwon, J., Milosevic, Z.: The latest gossip on bft consensus. arXiv preprint arXiv:1807.04938 (2018)
  * [10] Bünz, B., Maller, M., Mishra, P., Tyagi, N., Vesely, P.: Proofs for inner pairing products and applications. In: Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part III 27. pp. 65–97. Springer (2021)
  * [11] Buterin, V.: 2d data availability with kate commitments, https://ethresear.ch/t/2d-data-availability-with-kate-commitments/8081
  * [12] Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and efficient asynchronous broadcast protocols. In: Advances in Cryptology—CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001 Proceedings. pp. 524–541. Springer (2001)
  * [13] Cachin, C., Tessaro, S.: Asynchronous verifiable information dispersal. In: 24th IEEE Symposium on Reliable Distributed Systems (SRDS’05). pp. 191–201. IEEE (2005)
  * [14] Castro, M., Liskov, B., et al.: Practical byzantine fault tolerance. In: OsDI. vol. 99, pp. 173–186 (1999)
  * [15] chainlink: Data oracle, https://chain.link/
  * [16] Danezis, G., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A.: Narwhal and tusk: a dag-based mempool and efficient bft consensus. In: Proceedings of the Seventeenth European Conference on Computer Systems. pp. 34–50 (2022)
  * [17] Das, S.: A brief note on estimates of binomial coefficients. URL: http://page. mi. fu-berlin. de/shagnik/notes/binomials. pdf (2016)
  * [18] Espresso: Espresso sequencer, https://hackmd.io/@EspressoSystems/EspressoSequencer
  * [19] Feist, D.: New sharding design with tight beacon and shard block integration, https://notes.ethereum.org/@dankrad/new_sharding
  * [20] Feist, D., Khovratovich, D.: Fast amortized kate proofs, https://github.com/khovratovich/Kate/blob/master/Kate_amortized.pdf
  * [21] Gao, Y., Lu, Y., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. pp. 1187–1201 (2022)
  * [22] George Kadianakis, Ansgar Dietrichs, D.F.: A universal verification equation for data availability sampling, https://ethresear.ch/t/a-universal-verification-equation-for-data-availability-sampling/13240
  * [23] Guo, B., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Dumbo: Faster asynchronous bft protocols. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. pp. 803–818 (2020)
  * [24] Hendricks, J., Ganger, G.R., Reiter, M.K.: Verifying distributed erasure-coded data. In: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. pp. 139–146 (2007)
  * [25] Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16. pp. 177–194. Springer (2010)
  * [26] Keidar, I., Kokoris-Kogias, E., Naor, O., Spiegelman, A.: All you need is dag. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. pp. 165–175 (2021)
  * [27] Kelkar, M., Deb, S., Long, S., Juels, A., Kannan, S.: Themis: Fast, strong order-fairness in byzantine consensus. Cryptology ePrint Archive (2021)
  * [28] Kelkar, M., Zhang, F., Goldfeder, S., Juels, A.: Order-fairness for byzantine consensus. Cryptology ePrint Archive, Paper 2020/269 (2020), https://eprint.iacr.org/2020/269, https://eprint.iacr.org/2020/269
  * [29] Lens: Lens social network, https://www.lens.xyz/
  * [30] Malkhi, D., Nayak, K.: Extended abstract: Hotstuff-2: Optimal two-phase responsive bft. Cryptology ePrint Archive, Paper 2023/397 (2023), https://eprint.iacr.org/2023/397, https://eprint.iacr.org/2023/397
  * [31] Miller, A., Xia, Y., Croman, K., Shi, E., Song, D.: The honey badger of bft protocols. In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. pp. 31–42 (2016)
  * [32] Mostéfaoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous byzantine consensus with t¡ n/3 and o (n2) messages. In: Proceedings of the 2014 ACM symposium on Principles of distributed computing. pp. 2–9 (2014)
  * [33] Nazirkhanova, K., Neu, J., Tse, D.: Information dispersal with provable retrievability for rollups. arXiv preprint arXiv:2111.12323 (2021)
  * [34] Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Advances in Cryptology—CRYPTO’91: Proceedings. pp. 129–140. Springer (2001)
  * [35] Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics 8(2), 300–304 (1960)
  * [36] Rothschild, M., Stiglitz, J.: Equilibrium in competitive insurance markets: An essay on the economics of imperfect information. In: Uncertainty in economics, pp. 257–280. Elsevier (1978)
  * [37] Roughgarden, T.: Transaction fee mechanism design for the ethereum blockchain: An economic analysis of eip-1559. arXiv preprint arXiv:2012.00854 (2020)
  * [38] Sheng, P., Xue, B., Kannan, S., Viswanath, P.: Aced: Scalable data availability oracle. arXiv preprint arXiv:2011.00102 (2020)
  * [39] Spiegelman, A., Giridharan, N., Sonnino, A., Kokoris-Kogias, L.: Bullshark: Dag bft protocols made practical. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. pp. 2705–2718 (2022)
  * [40] Yang, L., Park, S.J., Alizadeh, M., Kannan, S., Tse, D.: $\\{$DispersedLedger$\\}$:$\\{$High-Throughput$\\}$ byzantine consensus on variable bandwidth networks. In: 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). pp. 493–512 (2022)
  * [41] Yang, S., Zhang, F., Huang, K., Chen, X., Yang, Y., Zhu, F.: Sok: Mev countermeasures: Theory and practice (2022)
  * [42] Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: Hotstuff: Bft consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. pp. 347–356 (2019)
  * [43] ZCash: Halo2, https://zcash.github.io/halo2/design/provingsystem/permutation.html

##  8 Shard algorithm

A simple protocol, called Shard, with the new architecture can achieve the
censorship resistance property with sharding and cryptographic signatures. At
a high level, a client sends a transaction to a shard for inclusion. If a
sufficient number of replicas in a shard receive the transaction, Shard
guarantees the transaction is included in the final BFT block. Since there are
malicious replicas in any shard, a client should send multiple transactions to
a shard’s replicas to ensure that some honest replicas has received it. All
replicas then send batched transactions (mini-block) to leader for inclusion.
However, the leader might be malicious and exclude mini-blocks that include a
certain transaction. To prevent that, the leader has to include a threshold of
mini-blocks from replicas in a shard, which can be enforced by requiring a
threshold of digital signatures from members of the shard.

The shard size should be sufficiently large and rotated frequently to ensure
that each shard has a sufficient amount of honest replicas to prevent possible
collusion (in the most secure case, all replicas are in a single shard). Then
the collected mini-blocks can be aggregated in the DA running among all
replicas. In the end, the leader has to include all the data from the DA in
the final BFT block. If the leader censors a transaction from the DA, anyone
can prove to the BFT protocol of such censorship by providing a proof which
indicates the missing inclusion of the transactions in the final block. The
challenger can access the unordered transactions by querying the DA. The Shard
protocol assumes that there is a random beacon such that any client can
calculate the membership of each shard, and use it to send transactions to the
replicas.

However, such Shard protocol relies on a random beacon assumption and has to
calculate a delicate parameter, the shard size, to balance the trade-off
between communication efficiency and security against dynamical adversaries
and leader-shard collusion. A large shard size causes a client to send more
copies of the transaction; whereas a small shard lowers the probability that
there are sufficient honest replicas within a shard. In the event that
malicious replicas occupy a significant portion of the shard such that the
honest replicas cannot have sufficient signature to proceed, the protocol has
to decide whether to allow the leader to proceed when the malicious shard
refuses to participate in the protocol. If we don’t allow the leader to
proceed, the BFT protocol has a liveness attack when a shard get dynamically
corrupted; if we allow the leader to proceed, then a malicious leader can
censor any arbitrary shard to exclude all transactions. It is because we
cannot distinguish between the case when a leader is malicious or a majority
of a shard is malicious. Both of them can unilaterally censor a mini-block. As
the result, we cannot detect censorship when a leader is allowed to proceed
with all transactions missing from a shard, and there is no forensics when
censorship happens. But since the replica allocation to shards is publicly
accessible in order for clients to submit their transactions, the dynamic
adversary can acquire this information and slowly corrupt the shard. To lower
the probability the above liveness and censorship attack from happening, the
protocol has to rotate the shard very frequently to prevent the worst case
liveness attack. But shard rotation requires intricate handoff mechanism that
increases the protocol’s complexity and decreases the system’s throughput
capacity.

##  9 Proof of Stake BFT Leader Assumption

In the production leader based proof of stake blockchain, like Tendermint[9],
a replicas’ chance to become a leader is weighted proportional to replicas’
voting power. There is a natural implication from this model to our assumption
that leader is much capable such that it has high bandwidth and computing
facility. Essentially, the leader with large percentage of stake in the
partial synchronous setup already put down large capital investment in the
form of stake, but the hardware requirement is relatively cheap. For example,
a powerful instance m7g.16xlarge[4] on AWS EC2 with $64$ vCPU, $256$ GB memory
and $30$ $Gbps$ optimized bandwidth requires only $\$2.6112/hour$ in a long
term plan.

On the other hand, the censorship resistant property in BigDipper does not
give the leader much higher potential to manipulate the transactions
inclusion. Therefore from the protocol’s view, it is fine to have a few
replicas with large amount of stake, and many replicas with less stake and
regular hardware, provided that there is one powerful leader to drive
liveness.

A more uniform stake distribution is desirable, in which scenario, replicas
with insufficient hardware can choose third party services to temporarily
serve the leader’s role. Or the protocol has to downgrade the performance for
a brief time proportionally to the replicas’ stake.

To avoid the problem of downtime or third-party trust relation, the leader
selection part of BFT protocol can have an opt-in mechanism, such that only
interested parties can volunteer to becomes the leader. If some leaders are
persistently censoring, eventually replicas from community can opt-in to
improve the honest ratio in the leader set.

##  10 BigDipper Properties

###  10.1 BigDipper Properties

BigDipper is a BFT system that provides consensus on a string of bits. It
requires a transaction broadcast protocol to accept client transactions, a DA-
CR for guaranteeing transaction availability and inclusion, and finally an
integration with a BFT protocol. BigDipper relies on an execution engine like
the Ethereum Virtual Machine to handle transaction validity. BigDipper
satisfies the following additional properties besides safety and liveness of
the BFT protocols. Suppose there are $n$ total replicas, and $f$ of them are
malicious. In the property description, a replica is available if it can
include any transaction before sending its mini-block:

  * •

Strict Transaction Inclusion: If a DA-CR guarantees at least $t$ mini-block
inclusions from honest replicas, an honest client can send $n-t+1$ copies of a
transaction to distinct available replicas for guaranteed inclusion regardless
of whether the leader is malicious.

  * •

Probabilistic Transaction Inclusion Under Honest Leader: Under an honest
leader, if a DA-CR guarantees at least $t$ mini-block inclusions from honest
replicas, an honest client can send $x$ copies of a transaction to random
distinct available replicas for probabilistic inclusion, the probability
monotonically increases with $x$ and $t$. If network latency of honest
replicas are i.i.d, the probability increases exponentially with $x$ and $t$.

  * •

Probabilistic Transaction Inclusion Under Malicious Leader: Under a malicious
leader, with a DA-CR instance with $t$ guaranteed honest mini-block
inclusions, an honest client can send $x$ copies of a transaction to random
distinct available replicas for probabilistic inclusion, the probability
monotonically increases with $x$, up to $1$ when $x=n-t+1$. When $x\leq f$ the
malicious leader can censor one transaction with probability $1$, but to
censor $u$ different transactions each of $x$ copies altogether, the
probability of censoring decreases exponentially as $u$ increases.

  * •

2 $\Delta$ Probabilistic Confirmation for Clients: If a DA-CR guarantees at
least $t$ mini-block inclusions from honest replicas, an honest client can
send $x$ copies of a transaction and compute the probability of inclusion
right after 2 $\Delta$ network latency by using number of responses from $x$
replicas and belief on the leader’s type.

  * •

Hyperscale Throughput: The throughput of reaching consensus on a sequence of
bits is a constant ratio to system capacity, which scales linearly as the
number of replicas joining in the system.

##  11 BFT protocol complexity analysis

###  11.1 Prime

Prime[3] is a classic leader based protocol whose goal is to defend against
adversarial attack on performance degradation while ensuring basic safety and
liveness of a BFT protocol. The malicious replicas can perform arbitrary
operations but correctly enough for not being identified as malicious. The
paper defines a new correctness criteria that takes performance into account
for defending against performance degradation attack. For example, a malicious
leader can introduce latency in the consensus critical path to delay the rate
of confirmation. The paper relies two insights, most of procedures in the
protocol does not require malicious replicas to take action; second, if the
workload for a leader has a predictable bound, all peers can observe the
network and access the leader’s performance to decide if the leader should be
replaced. To achieve them, the protocol devises multiple sub-protocols, each
responsible for a specific tasks. When a replica receives a order
(transaction), it disseminate it to all other replicas. The pre-ordering sub-
protocol is responsible for confirming the data availability. A data structure
called PO-SUMMARY is invented to record from each replica’s view, how much
data the other replicas currently have. Essentially, PO-SUMMARY is a vector
recording cumulative sum about what other replicas have. Then each replica
broadcast PO-SUMMARY to everyone including the leader. The exchange about PO-
SUMMARY requires a $O(n^{2})$ communication, where $n$ is the number of
replicas. The leader then uses all PO-SUMMARY to create a global ordering, if
a transaction has been recorded by at least $2f+1$ replicas. BigDipper is
different from Prime although both are leader based protocols, because in
BigDipper there is never a all-to-all communication pattern, and in addition,
the inclusion of transaction does not require consensus of $2f+1$ to receive
the transaction. Although Prime uses erasure code to reconciliate data
availability, the erasure coding is done to per transaction basis. The regular
Ethereum transaction size if roughly 200Byte, then if the network has size of
equal size, the overhead per transaction is outweighting the benefits of
erasure coding. Whereas in BigDipper, the erasure code is done all
transactions batch received by a BFT replica. Applying erasure code to the
batch does not introduce too much overhead for indicating which indices its
points are evaluating on. At latency perspective, Prime extends 2-Phase PBFT
by 1.5 phase (round-trip) trips message, which are PO-REQUEST, PO-ACK, PO-
SUMMARY, whereas BigDipper perfectly fits into the 2-Phase hotstuff protocol.

###  11.2 HoneyBadger and DispersedLedger

HoneyBadger is a leaderless asynchronous BFT protocol, made of two protocols:
a reliable broadcast protocol (RBC) and an asynchronous binary agreement
protocol. To reach consensus, HoneyBadger runs $n$ reliable broadcast protocol
asynchronously. The reliable broadcast is modified based on AVID [13], where
every replica produces its own merkle tree, and broadcast the merkle leaf and
proof to all other replicas. The total communication complexity for one
replica to broadcast its data of size $b$ bytes is $O(nb+\lambda
n^{2}\log{n})$; whereas using the classic Bracha[8] reliable broadcast would
take $O(n^{2}b)$. Whenever a replica completes a reliable broadcast $j$, it
starts to contribute to the binary agreement protocol for $j$. An asynchronous
binary agreement protocol accepts inputs from all replicas. Since the binary
agreement(BA) protocols based on construction from [32] requires $O(n^{2})$
communication complexity per round, and it takes $O(k)$ rounds to complete
with probability $1-2^{-k}$. The overall complexity for BA is
$O(n^{2}\log{k})$. To ensure all $n$ instances of BA to terminate with high
probability, the expected number of round is $\log{n}$. The overall
communication complexity for all $n$ replicas to complete a round is
$O(n^{2}b+\lambda n^{3}\log{n}+n^{3}\log{n})=O(n^{2}b+\lambda n^{3}\log{n})$,
where $b$ is inputs from each replicas. The number of communication steps to
complete a honeybadger RBC (which is modified based on AVID) is $3$. The first
step sends merkle leaf to everyone, the second step sends echo among all
replicas, and the final step for sending ready messages.

DispersedLedger has a very similar structure as HoneyBadger. DispersedLedger
divides the protocols into two parts: a data availability(DA) protocol and a
binary agreement protocol. The data availability is different from reliable
broadcast protocol in HoneyBadger, because data availability can be achieved
by the Disperse invocation alone, and its retrieval part can be deferred in
the later stage. The construction of DA in DispersedLedger is called AVID-M,
which has very similar structure as the merkle construction in reliable
broadcast in HoneyBadger and AVID-H in AVID[13]. In DispersedLedger, the
communication complexity for each replica is $O(b+\lambda n^{2})$, the binary
agreement part is identical to HoneyBadger which takes $O(n^{2}\log{k})$ per
replicas, that terminates with probability $1-2^{-k}$. So together the total
communication complexity is $O(bn+\lambda n^{2}+n^{3}\log{n})$. The number of
steps for DA is $3$, the sender replica first sends the merkle leaf and proof,
the each replica sends GotChunk that contains only the merkle root, this is
the step that differs significantly from AVID-modified RBC from HoneyBadger;
the last step is to send ready message. Although both DispersedLedger and
HoneyBadger has censorship resistance property, it is implemeneted by a all-
to-all communication pattern. Whereas in BigDipper, there is an active
coordinating leader preventing the quadratic communication pattern.

###  11.3 VABA

Validated Asynchronous byzantine Agreement is the first protocol that achieves
multivalue byzantine agreement with $O(n^{2})$ complexity. Previous method by
[12] of MVBA requires $O(n^{3})$ communication complexity. The key
construction element is called provable broadcast, which is also a key
building block for conventional leader-based BFT protocol like [42, 9, 14],
where the leader has an active role to coordinate replicas. For VABA, each
Atomic broadcast instance is associated with an ID; within each ID, four
consecutive PB are invoked to ensure data is committed without worries of
hidden lock. All $n$ replicas performs 4-stages PB, and a leader is chosen
retrospectively after all replicas have abandoned their PB procedures. If the
selected leader prematurely terminates the 4 stage PB, a view change repeats
the 4 stage PB until an externally valid value is confirmed by all honest
replicas. BigDipper is a leader based BFT protocol, that avoids all-to-all
communication pattern, unlike VABA.

###  11.4 Dumbo, sDumbo-DL and Dumbo-NG

Dumbo is BFT protocol built upon the framework presented from HoneyBadger.
There are two versions of the protocol: Dumbo1, and Dumbo2. The Dumbo1
identified $n$ parallel asynchronous Binary Agreement protocol as the
bottleneck to the system throughput. Then it provides an optimization to
replace $n$ Asynchronous Byzatine Agreement(ABA) instance. The technique is to
replace $n$ ABA with a $\log{n}$ reliable broadcast(RBC) to ensure one honest
replica can provide a batch of transactions from $n-f$ replicas. Then all $n$
nodes runs $\log{n}$ ABA to agree on which one of the $\log{n}$ Index from RBC
are correct, and the data is received by them. In total the step which Dumbo1
takes to finish the protocol is $2+2+\log{\log{n}}$ for Value-RBC, Index-RBC
and ABA.

Dumbo2 is a further optimized version of Dumbo1. Instead of using $n$ Value-
RBC, ${\log{n}}$ Index-RBC followed by ${\log{n}}$ ABA, Dumbo2 replaced the
reliable broadcast part with a new protocol called provable RBC, that uses
threshold signature to ensure the data broadcast by Index-RBC are indeed
correct. The agreement part is replaced with only one Multivalue Byzantine
Agreement (MVBA).

###  11.5 DAG-Rider, Narwhal-Hotstuff and Tusk

DAG-Rider, Narwhal-Hotstuff and Tusk are consensus protocols that adopts a
design that separate mempool and consensus, where the mempool is implemented
as Direct acyclic graph. DAG-rider is an asynchronous protocol that arrives at
consensus every four rounds, where each round consists of a reliable data
broadcast (RBC) and is not a point-to-point communication. When a RBC is
implemented by AVID, the communication complexity is $O(nb+\lambda
n^{2}\log{n})$. Because each RBC takes $3$ communication steps (point to point
communication), the overall steps it takes to confirm a block is $12$. Because
every vertex must contain $n$ meta-data of size $\log{n}$, the broadcast would
consume $O(n^{2}\log{n})$ bits for each replica.

Narwhal is a mempool module that is dedicated to produce data protocol that
has properties of Integrity, block-availability, containment, 2/3-causality
and 1/2-chain quality. The data broadcast is achieved with provable broadcast
by using certificate from $n-f$ replicas’ signature. Narwhal-Hotstuff-2 is a
partial synchronous protocol that uses Hotstuff-2 for reaching consensus. In
the table, we use the latest Hotstuff-2 as the consensus module to reduce
latency. In the Narwhal-Tusk paper, the communication steps is $8$, because it
used the old $3$ phases Hotstuff protocol.

Tusk is an asynchronous protocol that is an implementable version of DAG-
Rider, and it includes optimization to reduce the expected communication steps
to $9$ as indicated in the paper[16].

##  12 Background Appendix

###  12.1 Validity requirement in BFT problem

Often external validity[12] is added to the BFT requirement, which requires a
polynomial-time computable predict for deciding if a transaction is valid.
BigDipper uses standard Virtual machine to handle transaction validity, the
protocol by itself serves to reach consensus on a sequence of bits.

###  12.2 DA using outsourced components

There are many ways to incorporate [38, 2] a DA into a BFT protocol, either by
borrowing external DA oracle or internalizing it with the BFT replicas. The
advantage of the second option is a single unified trust assumption. The
advantage of former options usually come with high throughput and simpler
application design logic due to modularity.

###  12.3 Reed Solomon Erasure coding

The encoding process of Reed-Solomon code is based on the idea of polynomial
interpolation[35]. Essentially, given a list of $n$ points, there is a unique
polynomial of degree $n-1$ that interpolates those points. The redundancy
generation is basically evaluating the polynomial at more points. Where those
new points locate depends on specific encoding scheme. However, one encoding
scheme that uses Fast Fourier Transform is particularly popular due to its
fast $O(n\log{n})$ computation complexity. It only requires the field which
evaluations indices belong to have root of unity, $\omega$, such that
$\omega^{z}=1$, where $z$ is power of 2. Given some data $D$, the exact
operation can be summarized as $IFFT(\textit{concate}(FFT(D),\widehat{0}))$,
where $IFFT$ is inverse FFT, and the length of $\widehat{0}$ depends on size
of redundency. Since Fast Fourier Transform is a linear operation, i.e.
$\alpha FFT(a)+\beta FFT(b)=FFT(\alpha a+\beta b)$. We will use the FFT
encoding scheme on Elliptic Curve[43] to work with KZG polynomial
commitment.Given an input array $[d_{1}\cdots d_{n}]$ with coding ratio $1/3$,
RS encoding can be implemented such that the output is $[d_{1}\cdots
d_{n},p_{n+1}\cdots p_{3n}]$, where the input data take identical locations,
and parity data $p_{*}$ are generated at new indices.

RS encoding can be used to introduce redundancy in numerous ways. Figure 4
presents a way by laying all data in one dimensional line, and apply RS
encoding. Another way is to format the data into a 2D matrix like Figure 2.
Inside the matrix, data are partitioned into columns, and redundancy is
applied by taking FFT extension on each rows, such that redundant columns are
generated. The matrix format is pioneered by [2] and used by Ethereum
Danksharding [19] in the future roadmap. Unlike those works, our construction
the matrix does not add redundancy along columns. Our RS construction is also
different from Semi-AVID-FR[33], that every replica would possess one system
chunks and two parity chunks.

###  12.4 BLS Elliptic Curve and Signature

This section serves as a very brief coverage of basic elements of BLS12-381
elliptic curve and their properties. We also briefly cover BLS signature which
can be instantiated on the BLS12-381 curve.

An elliptic curve consists of three group $G_{1},G_{2},G_{T}$ or order $p$, a
pairing is an efficiently computable function $e:G_{1}\times G_{2}\rightarrow
G_{T}$. Group $G_{1}$, $G_{2}$ have generator $g_{1},g_{2}$ respectively, and
all members in the group can be obtained by enumerating powers on the
generator. The generator of $G_{T}$ equals to $e(g_{1},g_{2})$. A pairing
function provides a following property that $e(X^{a},Y^{b})=e(X,Y)^{ab}$,
where $X,Y$ are elements from elliptic curve group $G_{1},G_{2}$, and $a,b$
are integer from their corresponding finite field. BLS12-381 is one elliptic
curve allows for pairing (bilinear) operations.

On top of BLS12-381 curve, we can instantiate BLS public key signature [7]
scheme, which allows clients to sign and verify signature. Beyond simple
signature, both threshold signature and multi-signature can be developed.

###  12.5 Polynomial Commitment and KZG

We provide a more technical definition for primitives that uses KZG scheme
that uses Discrete Logarithm(DL) and t-SDH assumptions [25]. First, KZG
requires a trusted setup of $\\{g^{z}\cdots g^{z^{t}}\\}$, where $z$ has to be
a secret to anyone and $g$ is a generator for some elliptic curve group that
has bilinear pairing property [6]. We use Setup to presents the procedures to
get those powers of generators, which requires a security parameter $\lambda$.
The security of a scheme is measured against a probabilistic polynomial time
(PPT) adversary to break the properties. A secure scheme requires all
polynomial time adversary to have negligible probability to break the scheme.
The primitive $Commit$ of a function $\phi=\sum_{j}\phi_{j}x^{j}$ can be
implemented as $C=\prod_{j=0}^{deg(\phi)}{(g^{z^{j}})}^{\phi_{j}}$, where
$g^{z^{j}}$ is provided from the public setup, and $\phi_{j}$ are the
coefficient for $j$-th monomial. The primitive $creatWitness$ for some index
$i$ with evaluation $\phi(i)$ is defined as
$\psi(x)=\frac{\phi(x)-\phi(i)}{x-i}$, and we let $w_{i}=g^{\psi(z)}$, which
is the outcomes of $Commit(\psi)$. The primitive $VerifyEval$ on some
evaluation a tuple $(i,\phi(i),w_{i})$ is defined as
$e(C,g)=e(w_{i},g^{z}/g^{i})e(g,g)^{\phi(i)}$, where $e$ represents the
bilinear pairing operation. A proof for its correctness can be found in [25].

###### Definition 1

(KZG Commitment scheme)

  1. 1.

Polynomial-binding. For all PPT adversaries $\mathcal{A}$

$\displaystyle\operatorname{Pr}\left(\begin{array}[]{c}pk\leftarrow
Setup(1^{\lambda})\\\
(C,\phi(x),\phi^{\prime}(x))\leftarrow\mathcal{A}(pk)\end{array}:\begin{array}[]{c}Commit(\phi)=C\wedge\\\
Commit(\phi^{\prime})=C\wedge\\\
\phi\neq\phi^{\prime}\end{array}\right)\leq\epsilon(\lambda).$

  2. 2.

Evaluation-binding. For all PPT adversaries $\mathcal{A}$

$\displaystyle\operatorname{Pr}\left(\begin{array}[]{c}pk\leftarrow
Setup(1^{\lambda}),\\\ (C,\langle i,\phi^{\prime}(i)),w_{i}\rangle,\\\ \langle
i,\phi^{\prime}(i)),w_{i}^{\prime}\rangle\\\ \leftarrow\mathcal{A}(pk)\\\
\end{array}:\begin{array}[]{c}VerifyEval(pk,C,i,\\\ \phi(i),w_{i})=1\wedge\\\
VerifyEval(pk,C,i,\\\ \phi^{\prime}(i),w_{i}^{\prime})=1\wedge\\\
\phi\neq\phi^{\prime}\end{array}\right)\leq\epsilon(\lambda).$

$\epsilon$ represents a negligible function such that
$\epsilon(n)\leq\frac{1}{n^{c}}$ for all n greater some function of $c$.
$\mathcal{A}$ denotes an adversary.

It can be shown that KZG provides linearity in commitments and witnesses, such
that $commit(\alpha u+\beta v)=\alpha commit(u)+\beta commit(v)$,
$\textit{createWitness}(\alpha u+\beta
v)=\alpha\textit{createWitness}(u)+\beta\textit{createWitness}(v)$. Here we
slightly abuse the notation a bit to use $+$ to present the group operation
$\cdot$, it is useful to illustrate the following property.

The linearity of KZG commitment and RS encoding provide a powerful way to
encode systematic chunks such that commitments of parity chunks interpolates
to a polynomial, which is generated purely from commitments of systematic
chunks.

There are existing works [24, 33, 19] that study and apply this property.
Generating witnesses(proofs) is a computational intensive process. Techniques
including KZG multi-reveal [20] and Universal Verification equations [22] from
Ethereum provide both fast way to compute batch and evaluate proofs.

###  12.6 Pedersen commitment

Pedersen commitment is another polynomial commitment scheme[34]. Assuming
discrete logarithm is hard, suppose we have a cryptographic group of
$(G,\cdot)$ where $\cdot$ is the group operation, that has order $q$ and
generator $g$. Suppose we choose $n$ random point,
$\textbf{g}=g_{1},\cdots,g_{n}$, from $G$, we can commit two field element
$\textbf{a}=a_{1},\cdots,a_{n}$ by defining the commit function as

$commit(\textbf{g},\textbf{a})=\prod_{i}{g_{i}}^{a_{i}}$

Since Discrete Logarithm is assumed to be hard, no adversary can find another
$a^{\prime},b^{\prime}$ that commits to the same value. where product is
carried over group operation $\cdot$.

###  12.7 Ordering Functions

BigDipper prioritizes transaction inclusion, and provide a modular interface
for any ordering modules. From the perspective of BigDipper, the other end of
the interface is treated as a ordering function, that returns a deterministic
permutation of transactions for data corresponds to some BFT view number. For
each replica, the function could be a simple deterministic implementation. For
example, a shuffling function can be implemented by computing the hash digest
of all sorted transactions; another example would be using round robin to take
transaction one-by-one from each replica. Then if all replica only access to
the same data, they all arrive to the same permutation. However, simple
ordering function suffers a limitation that a malicious leader can grind its
mini-blocks to alter transaction locations. More sophisticated oracle usually
requires inputs from other replicas or external source for providing the
ordering. For example, logical timestamp among transactions is required for
creating a FCFS fair ordering[27]; auction mechanism needs to collect bids
from possible external parties; a verifiable random function(VRF) requires
randomness inputs from other replicas. Most implementations can be optimized
with coordination from the leader. Appendix 21 displays a sketch about using
permutation argument from zero knowledge to facilitate correct ordering.

##  13 DA-CR Primitives and Definition

###  13.1 DA-CR Definitions

For a DA-CR protocol, its censorship resistance depends on the characteristics
of the Disperse invocation. Definitions (2, 3) quantify the amount of
censorship resistance with a single parameter. Given a desired parameter, the
protocol has a large design space for choosing an inclusion mechanism for
meeting the requirement. Definition (5) classifies the design space into two
categories, based on the idea of whether a leader informs every replica about
whose data are included. It is achieved with the use of attestation in
definition (4). If a design uses attestation in conforming the censorship
resistance parameter, definitions (6, 7) capture possible outcomes when a
leader interferes with the inclusion mechanism. In Section 4, we provide
protocols designed base on either of the two categories.

######  Definition 2 (Replica-Exclusion)

Suppose a Disperse invocation finishes with a Complete type with a valid
combined signature, a replica $p$ is excluded if the leader does not include
the mini-block from $p$ for the DA-CR instance. Replica-exclusion happens even
when the leader is honest.

######  Definition 3 (Censorship Resistance $t$)

A protocol is censorship resistant if it guarantees that at least $t$ honest
replicas are not excluded in any DA-CR instance. If $t=0$, the protocol is not
censorship resistant.

######  Definition 4 (Data-Attestation)

If a replica proposes some non-zero data as its mini-block for a DA-CR
instance, the replica declares it to a leader by generating a signature,
called attestation, based on data in the mini-block. An attestation from
replica $p$ is denoted $a_{p}$.

######  Definition 5 (Accountable-Inclusion-Mechanism)

To conform with the censorship resistance $t$, an accountable inclusion
mechanism requires a leader to explicitly demonstrate the required number of
inclusion by showing attestations from other replicas, whereas a non-
accountable inclusion mechanism allows the leader to demonstrate conformity
without attestations.

######  Definition 6 (Data-tampering)

In an accountable mechanism, suppose a replica $p$ participates in a Disperse
invocation with a non-zero mini-block and the leader used the attestation
$a_{p}$ for demonstrating sufficient inclusion of mini-blocks to other
replicas. Let $b_{p}$ be the mini-block in the actual dispersed data
corresponding to replica $p$, the data of replica $p$ is tampered if $a_{p}$
does not bind to $b_{p}$.

######  Definition 7 (Space-capturing)

Suppose in a Disperse invocation a replica $p$ is excluded from the DA-CR
instance, the data space designated for the replica $p$ is captured by a
leader if in the actual dispersed data $b_{p}$, it is not set to a system
default value reserved for the excluded replicas.

The default value for the excluded replicas can be arbitrary, we let the value
be identically $0$. To handle a corner case when a replica has no data to
upload, the protocol defines a special NULL transaction for differentiating
scenario. With respect to definition(5), a great difference between the two
types of inclusion mechanism is shown in Lemma 1:

###### Lemma 1

Replica-Exclusion and Space-capturing in an accountable mechanism is publicly
attributable; whereas in a non-accountable mechanism, both of them are only
known privately by the leader and the excluded replica.

The proof is a direct consequence of using attestations. In a non-accountable
mechanism, there is a lack of association between dispersed mini-blocks and
their senders, so the leader can overwrite some space with its own data as
long as it satisfies some requirement of censorship resistance $t$. In
contrast, an accountable inclusion mechanism keeps track of what mini-block is
sent by which replica. See Appendix 18 for more discussion.

When an accountable inclusion mechanism is used, it exposes an attack vector
based on definition(6), which does not exist for protocols that use non-
accountable inclusion mechanisms. The goal of the attack is to introduce
inconsistency between what is being attested and what is actually dispersed.
An honest leader never tampers data; whereas a malicious leader can tamper any
mini-blocks including those produced by other malicious replicas. With the
definitions above, we describe properties required for a DA-CR protocol.

###  13.2 DA-CR relationship with AVID protocol family

AVID is not communication efficient since every replica downloads the entire
data. AVID-FP fixes it by using homomorphic fingerprinting, but requires a
$O(n^{2}\lambda)$ number of overhead per node. AVID-M overcomes the quadratic
overhead by using merkle commitment, but it allows the room for inconsistent
coding, which either complicates the trust assumption or prolongs the
confirmation latency. Semi-AVID-PR is designed for rollup, so it does not
provide Agreement and Termination properties unlike others, but it shares many
similarity with DA-CR on data structure and properties. Compared to those
protocols, there are two great differences in DA-CR. First, DA-CR has a
network assumption of partial synchrony, which allows for a leader to
intermediate among replicas; it is the key that allows DA-CR to avoid the
second $O(n)$ broadcast step in AVID-M[40] needed to ensure the Termination
property. Second, AVID family protocols has a client-server model and the
client has the entire data; whereas DA-CR is closer to a P2P network, where
every replica has partial data and serves as both a client and a server. The
DA-CR is similar to AVID-FP, but avoids $O(n^{3})$ messages complexity,
because the leader can coordinate communication in the partial synchronous
network. At the downside of the DA-CR, a malicious leader can refuse to
proceed the protocol at any stage. A timeout and a leader replacement
mechanism are required to properly terminate a round.

###  13.3 DA-CR properties discussion

We note that the Inclusion-$t$, Data-tampering Resistance-$\rho$ and Space-
Capturing-$\eta$ are extensions to the Correctness property which is offered
by many DA-CR protocols. Those additional properties refine the relation
between the original data from an honest replica and its final dispersed mini-
block even when the leader is malicious. Data-tampering Resistance is
different from Commitment Binding, because the later guarantees there is only
one data block that matches to the final commitment and its corresponding
combined signature; whereas for Data-tampering Resistance in an accountable
mechanism, $\rho$ number of dispersed mini-blocks must indeed be consistent to
the published data attestations binding to the final commitment.

To emphasize the importance of $\rho$, suppose $\rho=0$, then the leader is
free to mutate any bits in any replicas’ mini-blocks. The malicious leader can
then attack the system by posting the original attestations, but in fact
dispersing something else. Without careful protocol design, one can come up
with scheme that violates the data tampering. The inclusion-$t$ property
directly corresponds to the censorship resistant in Definition 3, and
similarly, Space-Capturing-$\eta$ for Definition 7.

##  14 DA-CR Protocol Designs

###  14.1 BigDipper-$7$

Algorithm 2 Card-$7$

1:At the replica  $p$ :

2:$\textit{myView}\leftarrow 0$, $\textit{aggSigs}[\cdot]\leftarrow\emptyset$,
$\textit{db}\leftarrow\emptyset$

3:upon $\textit{receiving SIGNAL}(v)$ do

4: $\textit{myView}\leftarrow v$

5: $b_{p}^{v}\leftarrow mempool$

6: $c_{p}^{v}\leftarrow kzgCommit(b_{p}^{v})$

7: $a_{p}^{v}\leftarrow sign(c_{p}^{v}||v)$

8: $\text{send }\langle\textsf{Collection},a_{p}^{v},b_{p}^{v}\rangle\text{ to
leader}$

9:upon receiving Dispersal do

10: $\\{c_{i}\\}_{1\leq i\leq 3n}\leftarrow extendEval(\\{c_{i}\\}_{1\leq
i\leq n})$

11: $a\leftarrow(checkCom(c_{p},b_{p}^{v})\lor c_{p}=0)\wedge
checkInc(S,\\{c_{i}\\}_{1\leq i\leq n})$

12: $\wedge\text{ }checkCom(c_{p+n},chunk_{p+n})$ $\wedge$
$checkCom(c_{p+2n},chunk_{p+2n})$

13: if $a=\texttt{true}$ then

14: $db[c_{p},c_{p+n},c_{p+2n}]\leftarrow(b_{p}^{v},chunk_{p+n},chunk_{p+2n})$

15: $C\leftarrow CRHF(\\{c_{i}\\}_{1\leq i\leq 3n})$

16: $\sigma_{p}\leftarrow\textit{ms.sign}(sk_{p},C)$

17: $\text{send }\langle\textsf{Approval},\sigma_{p}\rangle$ to leader

18:upon receiving Agreement do

19: if $\textit{ms.verify}(m.\sigma_{agg},m.I_{\sigma_{agg}},m.C)$ then

20: $aggSigs[m.g,m.v]\leftarrow(m.\sigma_{agg},m.I_{\sigma_{agg}})$

21:At the leader:

22:upon $\textit{receiving }\textsf{Collection}\wedge\textit{ validCollect(m)
}\wedge\textit{reach-proc-time}$ do

23: $B\leftarrow\\{m.b_{p}^{v}|m.a_{p}^{r}\in S\\}$

24: $\\{c_{i},chunk_{i}\\}_{1\leq i\leq 3n}\leftarrow encode2d(B)$

25: for $i\leftarrow 1\cdots n$ do

26: $\text{send i }\langle\textsf{Dispersal},\\{c_{i}\\}_{1\leq i\leq
n},chunk_{i+n},chunk_{i+2n},S\rangle$

27:upon $\textit{receving }\textsf{Approval}\wedge validApproval(m)$ do

28:
$\sigma_{agg},I_{\sigma_{agg}}=\text{ms.agg}(\\{m.\sigma_{i_{p}},pk_{i_{p}}\\}_{1\leq
p\leq n-f})$

29: for i = 1..n do

30: $\text{send replica i
}\langle\textsf{Agreement},I_{\sigma_{agg}},\sigma_{agg},C\rangle$

Algorithm 3 utility functions

1:procedure checkCom( $commitment$, $chunk$)

2: return $kzgCommit(chunk)=commitment$

3:procedure extendEval( $\\{c_{i}\\}_{1\leq i\leq n}$)

4: return $rsEncode(\\{c_{i}\\}_{1\leq i\leq n},1/3)$ # 1d RS to 3n with
systematic encoding

5:procedure checkInc( $S$, $\\{c_{i}\\}_{1\leq i\leq n}$) S is the attestation
set

6: $O\leftarrow\emptyset$, $A\leftarrow\\{1\cdots n\\}$

7: for $a_{p}^{v}\textit{ in }S$ do

8: if $\textit{verifySig}(a_{p}^{v}||myView,c_{p})=\texttt{true}\wedge
c_{p}\neq 0$ then

9: $O\leftarrow O\cup p$

10: else

11: return false

12: for $p\leftarrow A-O$ do

13: if $c_{p}\neq 0$ then

14: return false

15: return $|O|\geq n-f$

16:procedure validCollect( $m$)

17: if
$\textit{verifySig}(msg.a_{p}^{v}||myView,\text{kzgCommit}(m.b_{p}^{v}))$ then

18: $S\leftarrow S\cup m.a_{p}^{v}$

19: if $len(S)\geq n-f$ then

20: return $\texttt{true},S$

21:procedure validApproval( $m$)

22: if $\textit{ms.verify}(\sigma_{p},pk_{p})$ then

23: $M\leftarrow M\cup(m,pk_{p})$

24: if $len(M)\geq n-f$ then

25: return $\texttt{true},M$

26:procedure encode2d( $B$)

27: $\\{chunk_{i}\\}_{1\leq i\leq 3n}\leftarrow\text{rsEncode2d}(B,1/3)$

28: for $i\leftarrow 1\cdots 3n$ do

29: $c_{i}\leftarrow\text{kzgCommit}(chunk_{i})$

30: return $\\{c_{i},chunk_{i}\\}_{1\leq i\leq 3n}$

####  14.1.1 Collection Frequency and Waiting Time

In each DA-CR instance, every replica waits for its local Signal to send mini-
blocks to the leader. The frequency of the signal must equal to the frequency
of BFT blocks. If there are more than one DA-CR instance per consensus
instance, a malicious leader can censor all but keep one DA-CR instance to
avoid stalling the BFT protocol. If the frequency is lower, the chain cannot
progress fast enough. Since an instance has the same pace as the BFT protocol,
we let the signal to carry the replica’s local view number from the BFT
protocol. In the actual implementation, the signal can come from a pacemaker
from a leader based BFT protocol[30]. Section 6.3 discuss an integration with
Hotstuff-2.

When a leader waits for collection messages in the beginning of the workflow,
the leader can add a new condition that allows it to wait extra time after
receiving $n-f$ messages. In Algorithm 2, we denote the condition as reach-
proc-time, standing for reaching processing time, which can be implemented as
a short timer that evaluates to true on timeout. The number of included mini-
blocks has a pivotal role for good censorship resistance in the transaction
broadcast protocol discussed in Section 5. In short, the more mini-blocks gets
included, the less resource a client needs to spend to achieve some certain
probability of inclusion. If reach-proc-time is always true, the leader
proceeds immediately after having $n-f$ mini-blocks. If the timer is set long
enough, all mini-blocks from all honest replicas can be collected. The timer
can be tuned to create a balance with the optimistic responsiveness property
of Hotstuff.

###  14.2 Calculating Coding Ratio for DA-CR

The coding ratio is set to be $1/3$, i.e. 2 parity chunks per one systematic
chunk. The number three comes from the assumption that only $f$ out of $3f+1$
BFT nodes are malicious. To prevent liveness attack from $f$ malicious
replicas, the leader should be allowed to proceed to complete a DA-CR instance
as long as there is a combined signatures from $2f+1$ replicas. But since $f$
out of the $2f+1$ signatures could come from the malicious replicas, we
require the remaining $f+1$ replicas to be able to reconstruct the whole data.
Although the exact ratio should have been $\frac{f+1}{3f+1}$, the erasure
coding is more efficient for integer and easy for reference. Since
$\frac{1}{3}<\frac{f+1}{3f+1}$, the data is safe.

###  14.3 Retrieve Algorithm

A retriever can invoke either retrieveChunk or retrievePoint in Algorithm 4
for receiving the data.

Algorithm 4 Retrieve Invocations

1:At the replica  $p$ :

2:upon receiving RetrieveChunk do

3: if $m.c_{p}\text{ in }db$ then

4: $\text{send back }\langle db[m.c_{p}]\rangle$

5:upon receiving RetreivePoint do

6: if $m.c_{p}\text{ in }db$ then

7: $\phi_{j},w_{j}\leftarrow\textit{createWitness}(db[m.c_{p}],j)$

8: $\text{send back }\langle\phi_{j},w_{j}\rangle$

9:

10:procedure retrieveChunk( $p$, $\\{c_{i}\\}_{1\leq i\leq n}\\}$ ) # if p=-1,
then retrieve all chunks

11: if $p\neq-1$ then

12: for $k\leftarrow\\{p,l\\}$ do

13: $chunk\leftarrow send\langle RetrieveChunk,c_{p}\rangle\text{ to replica
}k$

14: if $checkCom(c_{p},chunk)$ then

15: return $chunk$

16: $chunks=\emptyset$ # when not comply

17: $\\{c_{i}\\}_{0\leq i\leq 3n}\leftarrow extendEval(\\{c_{i}\\}_{1\leq
i\leq n})$

18: for $j\leftarrow\text{shuffle}(1\cdots n)$ do

19: $chunk\leftarrow send\langle\textsf{RetrieveChunk},c_{j}\rangle\text{ to
replica }j$

20: if $checkCom(c_{j},chunk)=\texttt{true}$ then

21: $chunks[j]\leftarrow chunk$

22: upon $len(chunks)=f+1$ do

23: $B\leftarrow rsReconstruct(chunks)$

24: if $checkCom(c_{p},B[\cdot,p])$ then # if p=-1, loop for all chunks

25: return $B[\cdot,p]$

26:procedure retrievePoint( $p$, $j$, $\\{c_{i}\\}_{1\leq i\leq n}\\}$) # for
a point at B[j,p]

27: for $k\leftarrow\\{p,l\\}$ do

28: $\phi,w\leftarrow send\langle RetrievePoint,c_{p},j\rangle\text{ to
replica }k$

29: if $\textit{kzgEvalVerify}(c_{p},j,\phi,w)$ then

30: return $\phi$

31: $\\{c_{i}\\}_{0\leq i\leq 3n}\leftarrow extendEval(\\{c_{i}\\}_{1\leq
i\leq n})$

32: for $i\leftarrow 1\cdots n$ do

33: $chunk\leftarrow send\langle RetrieveChunk,c_{j}\rangle\text{ to replica
}j$

34: $B\leftarrow\textit{retrieveChunk}(-1,\\{c_{i}\\}_{0\leq i<3n}\\})$ # when
not comply

35: return $B[j,p]$

###  14.4 Retrieval success as a function of number requested replicas

Because every replica has three data chunks, a retriever at most needs to
query $\left\lceil\frac{f+1}{3}\right\rceil+f$ replicas to reconstruct the
interested rows in the data matrix. Let
$a=\left\lceil\frac{f+1}{3}\right\rceil$. Figure 3 plots the probability of
successful reconstruction as a function of random connections with varying
number of nodes $n=3f+1$.

Since each honest replica randomly select others to connect with, the
probability of connecting to $a$ honest replicas, $\Pr(success)$, can be
calculated by the following Equation:

$\Pr(success)=\sum_{b=a}^{y}\frac{{2f+1\choose b}{f\choose y-b}}{{3f+1\choose
y}}$

As we increase the number of replica, the ratio of achieving successful
reconstruction is high even at the ratio of 0.6(f+a). Each node only need to
connect to approximately $4f/5$ replicas to reconstruct the data if it uses
query replicas randomly.

The data reconstruction can be run asynchronously, and takes one round trip
time to complete.

Figure 3: The probability to connect to $a$ replicas as we change the total
number of replicas $n=3f+1$. The x axis is presented as the ratio of
$\frac{y}{f+a}$. The max value of x-axis is $f+a$. Figure 4: The data
structure for 1 Dimensional KZG RS encoding

###  14.5 Card-$7$ Properties Proofs

Data-tampering Resistance-$n$: We prove by contradiction. Suppose a mini-block
of some replica $p$ has been tampered by the leader in some dispersal with a
valid aggregate signature. By definition, the leader must have accepted $p$’s
attestation, and included it as a part of the attestation set. By intersection
argument, $f+1$ honest replicas must have signed a common commitment list as
its message for the aggregate signature. By (Alg.Card-7 line 11), we know the
attestation signature of the tampered mini-block must verify correctly to
$p$-th commitment in the commitment list, otherwise no honest replica would
send the Approval. Because each of $f+1$ honest has three chunks and has
verified their consistency with the received commitment list (Alg.Card-7.line
11-12), they in total possess $3f+3>n$ consistent chunks. The $3f+3$ chunks
are sufficient to interpolate every row to get the evaluations for the $p$-th
column in the dispersed data, denote it as $b_{p}^{\prime}$. By linearity of
Reed-Solomon code and KZG commitments, $b_{p}^{\prime}$ must have committed
correctly to $p$-th location in the commitment list. But by definition of
data-tampering, $b_{p}^{\prime}$ does not bind to $a_{p}$, then the adversary
must have broken the polynomial binding property of a polynomial commitment
scheme.

Inclusion-(f+1): By (Alg.Card-7 line 11), the leader has to claim to at least
include $2f+1$ valid attestations in the leader’s mini-block. Out of which, at
least $m\geq f+1$ mini-blocks come from honest replicas. By the Data-tampering
Resistance property, all $f+1$ mini-block must be original from honest
replicas without tampering.

Space-Capturing-$0$: Since all mini-blocks corresponding to the excluded
replicas has to be $0$ according to (Alg.Card-7 line 12), and because a
malicious leader cannot forge signature, no adversary can insert its own data
into mini-block designated for other honest replicas.

Termination: Suppose some replicas invoke Disperse$(B)$. Because all honest
replicas can timeout, they eventually finish with type Incomplete even if the
protocol has stalled due to malicious leader or network asynchrony. When the
leader is honest and the network is after GST, there would be at least $2f+1$
Collection messages with correct commitment signatures. All verification in
the Dispersal messages would pass, and the leader is able to gather at least
$2f+1$ aggregate signatures. As the result, all honest replicas can finish
with type Complete.

Availability: An honest replica has finished with a DA-CR instance with a type
Complete, it must have received an aggregate signature with at least $2f+1$
signer on a common message. $f+1$ of them must come from honest replicas.
Because the coding ratio is $\frac{1}{3}<\frac{f+1}{3f+1}$, there are
sufficient honest replicas to complete reconstruction. As the result any
honest retriever can retrieve and reconstruct some data $B^{\prime}$.

Commitment Binding: We prove by contradiction. Suppose a dispersal of $B$
completed with an aggregate signature, and adversary finds another
$B^{\prime}$ that also verify correctly with the signature. Since the
aggregate signature requires at least $n-f$ signatures, at least $f+1$ honest
replicas have signed a common message. By intersection argument, there is at
most one valid aggregate signature per instance. Because the hash function is
collision resistant and there is only one aggregate signature, the underlying
commitment list for producing both $B$ and $B^{\prime}$ must also be also be
identical. Suppose $B$ and $B^{\prime}$ are different at the $p$-th mini-
block. By polynomial binding, an adversary cannot find two $b_{p}$ and
$b_{p}^{\prime}$ that commits to identical commitment. Hence all $f+1$ honest
replicas must have cheated.

Correctness: An honest replica has Finished a dispersal with a type Complete,
then by Availability, the retriever must be able to retrieve some data
$B^{\prime}$. Because the dispersed data $B^{\prime}$ is Commitment Binding,
any retriever can only retrieve identical mini-blocks that binds to the
commitment list. For those do not bind to the commitment list, the kzg
commitment cannot match. Let $B$ denote the mini-blocks that a leader collects
right before starting the RS encoding. If the leader is honest, then
$B=B^{\prime}$.

##  15 Card-$\nicefrac{{1}}{{4}}$ Protocol

In every dispersal instance of Card-$7$, a replica needs to download both the
commitment list and the attestation set whose size is linear to the number of
replicas. In this section, we develop a non-accountbale protocol called
Card-$\nicefrac{{1}}{{4}}$ that has constant message complexity as shown in
Table 2. It also provides us a chance to analyze how accountability affects
DA-CR properties by comparing two protocols. For the rest of the section, a
threshold signature scheme is used for achieving a constant signature
overhead.

At a high level, Card-$\nicefrac{{1}}{{4}}$ is very similar to Card-$7$, both
of them use identical message flow depicted in Figure 1. However, there are
three changes that differentiate the two protocols. First, when a replica
sends its mini-block to the leader, no attestation is ever generated. Second,
after a leader collected at least $q\geq n-f$ mini-blocks, the leader
concatenates all mini-blocks and use the single polynomial to performs the RS
encoding. The result is a single commitment which can be used in the approval
message. Figure 4 in Appendix 16 displays the data structure. The third
difference happens at the dispersal step, the leader only sends coded data to
those $q$ replicas whose mini-blocks are collected. As the result, there is no
linear overhead in the number of replicas. However removing the accountability
component, i.e. attestation set, the protocol also suffers some drawback. We
state it in the Lemma 2:

###### Lemma 2

If a protocol uses an accountable inclusion mechanism, the leader can send
dispersal to all replicas, and all honest replicas (including excluded ones)
can sign the approving signature without violating censorship-resistance. For
honest replicas in a non-accountable inclusion mechanism, only those whose
mini-blocks are included by the leader can approve the dispersal.

In Card-$7$, a leader sends an identical tuple (attestation set, commitment
list) to all replicas. Once the tuple is received, any replica including the
excluded one can participate the approval step, because anyone can verify
Alg.Card-$7$.line 11-12 to determine if the leader has included at least $n-f$
mini-blocks. However in the non-accountable mechanism like
Card-$\nicefrac{{1}}{{4}}$, because attestation is not available, no replica
can associate a mini-block to its original sender except a mini-block is
created by itself. An excluded honest replica cannot distinguish between the
case when an honest leader including $n-f$ replicas and the case when a
malicious leader includes $n-f$ arbitrary mini-blocks. Consequently, only
replicas whose mini-blocks are included can send approval. In non-accountable
mechanisms, a leader has to be allowed to proceed with even $n-2f$ approving
signature because there is a case when $f$ honest replicas are excluded, and
at the same time $f$ malicious replicas refuse to send approval message. The
security assumption for Card-$\nicefrac{{1}}{{4}}$ becomes $n\geq 4f+1$. It is
required for efficient information dispersal. Because $f$ replicas out of
$n-2f$ approving replicas can be malicious, we require $n-3f$ replicas to be
able to reconstruct the whole data. With $4f+1$, we can perform the RS coding
with a chunk size $O(1/f)$ of the final BFT block size. Other properties and
proofs are provided in Appendix 16.3.

###  15.1 Necessary condition for $\rho=n$

When an accountable inclusion mechanism is used by a DA-CR protocol, we want
every dispersal to be tamperment proof, as it removes the requirement to
detect the inconsistency. We provide Lemma 3 that states the necessary
condition for $\rho=n$ and shows 1D KZG alone in Card-$\nicefrac{{1}}{{4}}$ is
insufficient:

###### Lemma 3

If a dispersal scheme provides Data-tampering resistance-$n$, all honest
signing replicas that approve the dispersal must have together ensured the
consistency of every data in the dispersed block against the attestations.

The proof to Lemma 3 can be derived from the statement. Suppose there is one
data point not checked by any honest signing replicas, then the malicious
leader can mutate that data point to introduce inconsistency. If Card-$7$ uses
1D KZG for encoding, a leader can mutate mini-blocks from some $z\leq f$
honest replicas. But the rest $n-z$ replicas would still verify correctly that
their received chunks are consistent to a global commitment, and the adversary
can progress the protocol with tampered data. The 2D KZG construction from
Card-$7$ satisfies the Lemma condition on every data point, because the
interpolating polynomial of the commitment list can implicitly perform cross-
columns checking. The proof of Data-tampering resistance-$n$ in Section 14.5
demonstrates this key idea.

##  16 Non-accountable inclusion mechanisms

###  16.1 Vanilla Protocol

Vanilla uses unaccountable inclusion mechanism. The biggest advantage is the
constant message complexity as shown in Table 2. The construction and message
flow are very similar to Card-$7$ depicted in Figure 1 and Algorithm 2. Here
we overload the term Vanilla for both entire protocol and DA-CR.

Vanilla is a protocol with minimal changes from regular BFT protocols [42, 30,
9, 14]. The BFT block is still assembled from mini-blocks, but it the
dispersal step, the whole BFT block (containing all mini-blocks) is broadcast
to everyone, instead of using verifiable information dispersal. Although
inefficient, Vanilla has censorship resistance of $t=n-3f$. A leader first
waits for $n-f$ mini-blocks to assemble the BFT block; for each replica who
received the BFT block, it verifies if the block contains its own mini-block,
and only its own data is included it would send the approving partial
signature. For the same reason stated in Lemma 2, the excluded replicas cannot
participate the approving procedure because it cannot verify if the leader has
indeed include other’s mini-blocks. Consequently, the leader is required to
collect $n-2f$ aggregate signature before proceeding, because there could be
$f$ malicious replicas within the $n-f$ replicas whose mini-blocks are
collected. At least, since an honest leader only needs to wait for $n-2f$
approving message, there could be $f$ malicious replicas. So the Inclusion-t
of DA-CR property for Vanilla is only $n-3f$. So when $n=3f+1$, the minimal
mini-blocks coming from honest replicas in the final BFT block is only one.

###  16.2 Proofs for Vanilla

In this section, we provide DA-CR property proofs for Vanilla. First briefly
recapping the algorithm. It belongs to non-accountable inclusion mechanism.
The sequence of message exchange follows the same workflow shown in Figure 1
as to Card-$7$ protocol discussed in the main text.

The biggest difference in Vanilla compared to Card-$7$ is that dispersal
message contains the entire BFT block, as opposed to a chunk. In both scheme,
the approving message is signed by a threshold signature scheme. We now
presents proofs for Vanilla protocol. Because every replica in Vanilla
receives the entire data, Availability, Correctness, Commitment Binding are
inherited by default. Because the protocol uses the same message sequence and
timeout, Termination proof is identical to Card-$7$. Because it uses non-
accountable mechanism, Data-tampering Resistance-$\rho$ is not applicable.
Inclusion-(n-3f) is discussed in the last section. Essentially, because the
leader can wait for at least $n-f$ mini-blocks. After dispersing the BFT
block, in the worst case only $n-2f$ can send approval message, and we must
allow the leader to proceed with that amount of approval. In the remaining
replicas, $f$ can be malicious, and therefore the included honest replicas is
$n-3f$. The proof for Space-Capturing-$2f$ is due to non-accountability. A
malicious leader can falsely submit mini-block for any $2f$ mini-block space,
as long as there is one honest replica who sends the approval message, the
malicious leader can move to the next round, because there are $f$ malicious
replicas to approve the message. So in the end, the leader captures $n-f-1$
mini-blocks.

###  16.3 Proofs for Card-$\nicefrac{{1}}{{4}}$

Now we show proofs for Card-$\nicefrac{{1}}{{4}}$. One Big difference from
Card-$7$ is the usage of 1D KZG scheme shown in Figure 4 and threshold
signature. All mini-blocks are first concatenated into one dimensional line,
and then the leader performs RS encoding to extends $n$ chunks to $3n$ chunks.
Then the leader produces only one polynomial commitment, which is used as
approval message. Another big difference comes from an increase of required
security assumption of $4f+1$ in order to enable information dispersal.

Availability, Correctness follows the same proof as Card-$7$, since there are
at least $f+1$ honest replicas each holding three correct chunks. Commitment
Binding is provided by KZG polynomial commitment scheme. Because we do not
change the message sequence and timeout, Termination is identical. Because it
is not an accountable mechanism, Data-tampering Resistance-$\rho$ is not
applicable. Inclusion-n-3f is stated in the Section 15, and the argument is
identical to proofs of Vanilla. At last, Space-Capturing-$2f$ are identical
proofs for Vanilla.

##  17 Card-Lite Protocol and Analysis

###  17.1 Doubly Homomorphic Commitment Scheme

In this section, we provide a summary on how to use Doubly Homomorphic
Commitment Scheme[10] in Card-Lite to achieve $O(\log{n})$ overhead complexity
while still ensuring correct RS encoding. For explicit construction of
polynomial commitment scheme that allows opening with witnesses, [10] contains
more details on the construction.

Since Card-Lite is a 2D KZG RS construction, the leader has a commitment list
of size $n$. The censorship resistance protocol described in Section 4.2
requires each replica to have $2$ parity chunks and $2$ commitments as usual,
but it additionally requires samples other columns. The two parity chunks are
used for ensuring data availability. To ensure all sampled commitments
corresponds to a single commitment polynomial of degree $n-1$, every
commitment must come with a logarithmic sized proof binding to the commitment
$C$. Because otherwise, the leader can attack the system by incorrect coding,
such that no retrieve can reliably retrieve data binding to the commitment
list.

Regular merkle tree vector commitment provides the first requirement
(logarithmic proof size), but fails the second requirement, because there is
no way to verify all $3n$ commitments are interpolating a polynomial of degree
$n-1$. The doubly homomorphic commitment scheme allow us to perform commitment
of commitments, which treats the commitment list of 2D KZG as $n$ evaluation
points, which is points from $G_{1}$ group in some elliptic curve. Then with a
polynomial with $n$ evaluations, we can find out their corresponding
coefficients, and get the final commitment with Pedersen Commitment scheme
(see Appendix 12.6) by taking the inner product between the $n$ coefficients
from group $G_{1}$ and $n$ basis from group $G_{2}$. We require the underlying
elliptic curves has pairing capability such that we can derive a final
commitment in $G_{T}$, see Appendix 12.4.

With construction of generalized inner product argument (GIPA)[10], we can use
the polynomial commitment scheme with ability to open indices with witness
size $O(\log{n})$. To save verification cost, one can use a structured setup
on $G_{2}$ similar structure in the setup of KZG 12.5 ($g^{z^{i}}$. However
computation is not our concerns. But we can use SRS to limit the size of
polynomial to degree $n-1$, which eliminates the needs of low degree testing
to ensure the degree polynomial is indeed low degree of $n-1$.

Otherwise, we can use a low degree testing, by repeatedly reducing the degree
of polynomial by splitting even and odd monomial, then committing the combined
polynomial of half of the degree for $O(\log{n})$ times, until there is a
constant polynomial.

Figure 5: The sampling matrix for one replica.

###  17.2 Configuring Parameter for boosting

As described in Section 4.2, we recap the full Card-Lite protocol and present
analysis to derive proper parameters to achieve properties stated in Table 2.
Since the leader cannot send commitment list of length $n$ to replica, it has
to use a doubly homomorphic commitment scheme to reveal commitments with
$O(\log n)$ size proof. All replicas sign the final commitment $C$ (which is
commitment of the commitments) as its approving message. After collecting
mini-blocks and creating an attestation set, the leader creates $n$ sampling
matrix, and each matrix has the format shown in Figure 5. The matrix entry at
coordinate $(i,j)$ consists of a tuple of $(a_{p},c_{p},\textit{proof of
}c_{p})$ corresponding to the some random query that requests an attestation
from replica $p$, where $1\leq p<n$. There are in total $kL$ random query. In
Figure 5, we use subscript to denote each sample, and omits their proofs.
Clearly, if some replica $q$ wants to create such a matrix, it cannot send
$kL$ random queries to create the matrix. We require the leader to use Fiat-
Shamir Transform to generate randomness for replica $q$ based on the
commitment $C$ by using hash function $h$ to generate ${r_{i,j}}=h(C,i,j,q)$,
where we use ($r_{i,j}$ mod $n$) to decide which replicas the random query
wants to receive the tuple for. The leader has to present $n$ matrix for each
replica. Let’s now focus on one such matrix.

If a leader excludes attestations from some replicas, some entries in the
matrix must be empty, because no leader can provide proof for something that
is not on the polynomial or attestations is not available. It is orthogonal to
Data tampering attack, which is handled by the 2D KZG construction.

Suppose there are two types of leaders, both types collect attestation set
from replicas, and use 2D KZG scheme shown in Figure 2 for encoding, and
generate a commitment list. For simplicity of presentation, we don’t allow any
space capturing, hence all excluded mini-blocks must be $0$.

We want to understand the worst case scenario on how much a malicious leader
can censor. The honest leader type does not censor mini-blocks, whereas a
malicious leader censors at least $s\geq 1$ mini-blocks on top of $f$
allowable exclusion. Now in the random query game, the probability that a
random number mod $n$ picks on the included mini-block is
$\Pr_{m}(\text{valid})\leq p_{d}=(2f+1-s)/(3f+1)$ for a malicious leader
(inequality in case the malicious leader censors more); whereas for an honest
leader is $\Pr_{h}(\text{valid})=p_{h}=({2f+1})/({3f+1})$ (inequality in case
malicious replicas complies with the protocol).

Then if $k$ of such random queries are requested, the probability of providing
all $k$ valid responses together is at $g_{d}\leq p_{d}^{k}$ for malicious and
$g_{h}\geq p_{h}^{k}$ for honest leader respectively. Clearly, $g_{d}<g_{h}$.
As in the main text, we call the $k$ query together as a batch.

Now we can compute a value $\rho<1$ such that ${p_{d}}^{\rho}={p_{h}}$, and
equivalently
$\rho=\frac{\log(1/p_{h})}{\log(1/p_{d})}=\frac{\log(1/g_{h})}{\log(1/g_{d})}$.
Similarly compute a value $k$, such that ${p_{d}}^{k}=\frac{1}{f^{\tau}}$,
where $\tau$ is a small positive value $\tau>1$, hence equivalently
$k=\frac{\tau\log{f}}{\log{1/p_{d}}}$. We can bound $g_{d}$ and $g_{h}$ by

$\displaystyle g_{h}\geq{p_{h}}^{k}$
$\displaystyle={p_{h}}^{\frac{\tau\log{f}}{\log{(1/p_{d})}}}$
$\displaystyle=f^{-\frac{\log{(1/p_{h})}}{\log{(1/p_{d})}}}$
$\displaystyle=f^{-\rho}$ $\displaystyle g_{d}\leq p_{d}^{k}$
$\displaystyle=f^{-1}$

The second equality comes from logarithmic rule $a^{\log{b}}=b^{\log{a}}$. Now
suppose the node sends $L$ batches to the leader. Now define two probability
$P_{1},P_{2}$, which equal to the probability that none of $L$ batch is
successful for honest and malicious leaders respectively.

Suppose we choose $L=\tau f^{\rho}\log{f}$, where $\tau$ is some constant.

$\displaystyle P_{1}\geq 1-(1-g_{h})^{L}$ $\displaystyle=1-(1-f^{-\rho})^{\tau
f^{\rho}}$ $\displaystyle=1-e^{-\tau\log{f}}$ $\displaystyle=1-f^{-\tau}$
$\displaystyle P_{2}\leq 1-(1-g_{d})^{L}$ $\displaystyle=1-(1-f^{-1})^{-\tau
f^{\rho}\log{f}}$ $\displaystyle=1-e^{-\tau f^{\rho-1}\log{f}}$

Clearly, $P_{1}$ approaches to $1$ for any $\tau>1$. Whereas for $P_{2}$, we
need additional procedure to derive bounds. Since exponential is continuous
function, we can bring the limit to the exponent,

$\lim_{f\rightarrow\infty}e^{-\tau
f^{\rho-1}\log{f}}=e^{\lim_{f\rightarrow\infty}-\tau f^{\rho-1}\log{f}}$

we then need to calculate $\rho$ to derive bounds on $s$, such that for the
malicious type the limit on the exponent goes to $0$, and consequently
$P_{2}\rightarrow 0$.

Since $\lim_{f\rightarrow\infty}(f^{-1/\log{f}})^{\tau}=e^{-\tau}$. We want to
get a $\rho$ such that $\rho-1$ equal to $\frac{-\tau}{\log{f}}$. By
definition, $\rho=\frac{\log(1/p_{h})}{\log(1/p_{d})}$.

We can approximate $\rho$ with Taylor series with some additive second order
error $\frac{6}{(3f+1)^{3}}$, which is close to $0$ as $f$ increases.

$\displaystyle p_{h}$ $\displaystyle=\frac{2f+1}{3f+1}=1-\frac{f}{3f+1}\approx
e^{-\frac{f}{3f+1}}$ $\displaystyle p_{d}$
$\displaystyle=\frac{2f+1-s}{3f+1}=1-\frac{f-1+s}{3f+1}\approx
e^{-\frac{f-1+s}{3f+1}}$

hence $\rho=\frac{f}{f-1+s}$. With the equality
$\rho-1=\frac{-\tau}{\log{f}}$. Now compute $s$

$\displaystyle\log{f}$
$\displaystyle=\frac{\tau}{1-\rho}=\frac{f-1+s}{s-1}\tau$ $\displaystyle s$
$\displaystyle=\frac{f\tau}{\log{f}}=\Theta(\frac{f}{\log{f}})$

As the result,

$\displaystyle P_{2}$ $\displaystyle\leq 1-e^{-\tau
f^{\rho-1}\log{f}}=1-e^{-\tau e^{-\tau}\log{f}}=1-f^{-\tau e^{\tau}}$

Clearly, $e^{-\tau}$ decreases much faster than $\tau$ for $\tau>1$, $P_{2}$
approaches $0$ exponentially fast as we increase $\tau$. Therefore

$\displaystyle P_{1}$ $\displaystyle\geq 1-f^{-\tau}$ $\displaystyle P_{2}$
$\displaystyle\leq 1-f^{-\tau e^{-\tau}}$

Even with a small $\tau$, the honest replicas can differentiate two types with
extremely high probability.

The leader prepare one $k\times L$ matrix for every one replica. Each matrix
corresponds to a sampling replica $p$. If the leader finds a valid batch
(row), it can demonstrate that sufficient many mini-blocks are included, by
sending the particular valid row(batch) in the matrix to the replica. For an
honest leader, it needs to find the working batch for at least $2f+1$
replicas, hence the probability of is

$\displaystyle\Pr(\text{success | honest})$ $\displaystyle={P_{1}}^{2f+1}=(1-f^{-\tau})^{2f+1}$ $\displaystyle\approx e^{-\frac{2f+1}{f^{\tau}}}$ $\displaystyle\approx e^{-2f^{1-\tau}}\textit{ where }\tau>1$ $\displaystyle\approx 1$

However, if the leader is malicious, it needs to convince at least $f+1$
honest replica.

$\displaystyle\Pr(\text{success | malicious})$ $\displaystyle={P_{2}}^{f+1}=(1-f^{-\tau e^{-\tau}})^{f+1}$ $\displaystyle\approx e^{-\frac{f+1}{f^{\tau e^{-\tau}}}}$ $\displaystyle\approx e^{-f^{(1-\tau e^{-\tau})}}$ $\displaystyle\approx e^{-f}$ $\displaystyle\approx 0$

Hence for any number of censoring with $s\geq\Theta(\frac{f}{\log{f}})$, there
is extremely low chance that all $f+1$ would find valid batches. So a
malicious leader can at most censor $s=o(\frac{f}{\log{f}})$. In summary, the
leader needs to create $n$ sample matrix for each replicas, each of which has
$(\tau f^{\frac{f}{f-1+s}}\log{f})$ number of rows and
($\frac{\tau}{\log{1/p_{d}}}\log{f}$) number of column. Since
$p_{d}=\frac{2f+1-s}{3f+1}$ and $1\leq s\leq o(\frac{f}{\log{f}})$, we can
derive a more concise inequality for the number of columns, i.e batch size as

$\displaystyle\centering k\@add@centering$
$\displaystyle=-\tau(\log{f})\log{p_{d}}$
$\displaystyle\leq-\tau(\log{f})\log(\frac{2f-\frac{f}{\log{f}}}{3f})$
$\displaystyle\leq\tau(\log{f})\log{2/3}$ $\displaystyle\leq\kappa\log{f}$

where $\kappa$ is a small positive constant.

For every dispersal, a leader has in total $O(f^{2}\log^{2}{n})$ rows for all
replicas. A malicious leader cannot grind the final commitment $C$ to increase
the probability of convincing $f+1$ replicas if it censors
$s=\Theta(\frac{f}{\log{f}})$, because it needs to grind at least $Z$ times,
such that $Z*e^{-f}$ equals to some constant, where $n$ can take asymptotic
value.

The overall overhead message size is therefore just the $\kappa\log{f}$ tuples
consisting of $(a_{p},c_{p},proof)$. The proof part takes $O(\log{n})$ size
because the polynomial commitment scheme uses IPA. However, since Pedersen
commitments are aggregatable, the $\log{f}$ proofs can collapse together in a
single proof. Hence the overall overhead complexity is still $O(\log{f})$.

###  17.3 Card-Lite Proof

We now prove the DA-CR properties for Card-Lite property.

Termination: Since we don’t touch the protocol mechanism, and there is still
timeout to detect livelessness, Termination proof is identical to the
Card-$7$.

Availability: If an honest replicas received an threshold signature, there
must be at least $2f+1$ signer, and $f+1$ are honest replicas. Since there are
at least $f+1$ honest replicas that signed the message, eventually an honest
retrieve can find a honest replicas to get the correct commitment list that
commits to the final commitment $C$. After getting the commitment list, since
coding ratio is $1/3$, any honest retriever can reconstruct the whole BFT
block without concerning about the degree of the polynomial and incorrect
coding. This is because we use IPA for commitment to the polynomial and can
use a fixed size SRS to ensure the commitment is consistent to a polynomial of
degree $n-1$. (we can optionally use a low degree testing for the same
purpose).

Commitment Binding: The idea is similar in proof for Card-$7$ except we
replace the collision resistant hash function(CRHF) with a polynomial
commitment scheme (generalized inner product argument), which is also
collision resistant.

Correctness: The proof is identical to Card-$7$.

Data-tampering Resistance-$n$: Since IPA is commitment binding, no adversary
can find another commitment list that maps to the same final commitment. As
the result, the proof is identical to Card-$7$, since all signing replicas is
using a common commitment list.

Inclusion-$(f-o(f/\log{n}))$: The proof is a direct consequence from Section
17.2.

Space-Capturing-($o(f/\log{f})$): Since the Data-tampering Resistance is
$n-2f-z$ where $z=o(f/\log{f})$, the malicious leader can capture $z$ mini-
blocks without honest replicas noticing. The malicious leader cannot capture
more than $z$ because the correct batch of size $k$ which the leader has to
provide to all honest replicas must come with $k$ original attestations.

One thing worth noticing is that the protocol designer also has a coarser
control on how much to allow the leader to do space capturing, instead of a
batch containing all $k$ original attestation, it could allow $k-1$
attestations but allow the leader to have $2$ attestations.

##  18 Stealing or LSC?

So far, we have yet discussed Leader Space Capturing (LSC) in depth. This
section serves for developing difference and clarifying some internal
tradeoff. In developing censorship resistance property, we use
decentralization as the underlying force to achieve it. It is therefore
natural to adhere to a principle that block building is a collective work that
everyone should be given a fair share of space resource. However, a space
capturing is a phenomenal when a leader has taken data space from other
replicas which can potentially have positive effects on the system
utilization. On the other hand, if without constraint a malicious leader can
capture too much space leaving only one guaranteed inclusion of honest
replica; in the protocol Vanilla, as $n$ becomes larger, the protocol is as
close to as a regular leader based BFT protocol.

LSC is intractable with non-accountable inclusion mechanism because there is
no mapping about whose mini-blocks get included. On the other hand,
accountable inclusion mechanism allows protocol designers to tune the amount
of LSC. In both accountable mechanisms we discussed, the parameter $\eta$ is
configured as $0$, however with little modification, all accountable protocols
can increase the number, by allowing a leader to replace some $0$ in the
commitment list with leader’s own attestations and mini-block.

Given possible choices of LSC, we now elaborate in what ways LSC can be
beneficial and harmful, which would be helpful for protocol designers to
decides if to allow LSC and at what amount.

As mentioned, space capturing is unobservable in non-accountable mechanisms.
However, if it is allowed in accountable mechanism, $\eta$ is the only
mechanism which can control the amount of LSC. Recall in in section 14.1.1, we
discuss a local parameter read-proc-time which determines how much longer an
honest leader waits after receiving $n-f$ mini-blocks. But since the read-
proc-time is an unobservable parameter to the outside parties, all leaders can
set it to maximize LSC, and the protocol has no means of enforcement. On the
positive side, when the network is bad and many replicas cannot submit mini-
blocks fast enough before the dispersal period ends, LSC allows the leader to
make use of available space for higher system throughput. On the negative
side, if we attempt a rational model for a moment, and assume replica’s
revenue increases with the number of included mini-block, then LSC encourages
any leader to take data space from other replicas. However, at the same time
if everyone gets the chance to be a leader, all can do LSC while at the same
time increasing system utilization.

If LSC is allowed, there is subtle difference of LSC depending on the
accountability of the inclusion mechanism. If non-accountable mechanism is
used, a malicious leader can apply censorship on the basis of replicas, and
the replica which repeatedly do not get mini-blocks included cannot even prove
itself being censored. And vice versa for a malicious replicas falsely accuses
a leader when its data is included. In accountable mechanism, although we
cannot attribute which party is at fault, we can at least know without false