#  : A Peer-to-Peer Network with Verifiable Causality

In Submission

###### Abstract.

Logical clocks are a fundamental tool to establish causal ordering of events
in a distributed system. They have been used as the building block in weakly
consistent storage systems, causally ordered broadcast, distributed snapshots,
deadlock detection, and distributed system debugging. However, prior logical
clock constructs fail to work in a permissionless setting with Byzantine
participants. In this work, we introduce , a novel logical clock system that
targets an open and decentralized network. introduces a new logical clock
construct, the Decaying Onion Bloom Clock (), that scales independently to the
size of the network. To tolerate Byzantine behaviors, leverages non-uniform
incrementally verifiable computation (IVC) to efficiently prove and verify the
construction of clocks. We have applied to build two decentralized
applications, a weakly consistent key-value store and an anti-censorship
social network, demonstrating the power of scalable, verifiable causality in a
decentralized network.

##  1\. Introduction

The ordering of events is a fundamental concept in distributed systems. In
state machine replication systems (smr, ; paxos, ; vr, ; raft, ), the set of
replicas needs to agree on the order of operations in the log; shards in a
distributed database (spanner, ; megastore, ; calvin, ) are tasked to execute
distributed transactions in a consistent partial order; for mutual exclusion
of shared resources, participants in a distributed system have to agree on the
order of acquiring locks (chubby, ; lockmanager, ; netlock, ); in a
distributed storage system (gfs, ; ceph, ; bigtable, ; dynamo, ; pegasus, ),
servers apply a consistent order of mutations to storage objects.

It is well-known that perfectly synchronized clocks do not exist in realistic
distributed systems, due to clock drift and relativity. Ordering events using
physical clock timestamps is therefore not reliable and can lead to anomalies.
Logical clocks (lamport-clock, ; vector-clock, ), on the other hand, offer a
solution to order events in a distributed system without relying on physical
time. Logical clocks are consistent with _logical causality_ , , if event $a$
can causally influence event $b$, then the logical clock of $a$ is prior to
that of $b$. Unlike physical time ordering, causality in a distributed system
is only a partial order, as there exists events which do not causally
influence each other. Many forms of logical clocks have been proposed in the
literature (lamport-clock, ; vector-clock, ; bloom-clock, ; plausible-clock, ;
tree-clock, ), though not all of them can be used to deduce causality between
events. For instance, even if an event has a smaller Lamport clock (lamport-
clock, ) than another, the two events can still be logically concurrent.

Existing logical clock constructs, however, fall short in an open,
decentralized network (bitcoin, ; ethereum, ). In these networks, any
participant can join or leave the system at any time. Such dynamic environment
presents deep scalability challenges for vector-based logical clocks (vector-
clock, ; plausible-clock, ; tree-clock, ). More critically, prior systems
assume all participants in the system faithfully follow the protocol to update
and propagate their clocks. In a decentralized network, Byzantine (byzantine,
) behaviors, where a participant can deviate arbitrarily from the specified
protocol, are common. Unfortunately, existing logical clock constructs are not
Byzantine-fault tolerant. By not following the clock protocol, a single
Byzantine participant can easily compromise the clock’s causality guarantees,
, logical clocks may imply erroneous causality between events. Such
adversaries can render the entire clock construct pointless.

In this work, we address the above shortcomings by proposing a new logical
clock system, . targets a permissionless network with possible Byzantine
participants. Similar to prior logical clocks, can be used to infer causality
in the network. , however, only concerns causal dependency between object
states, , an object state is the result of a series of mutations from another
object state. In return, always infers _true causality_ , unlike the possible
causality implied by prior approaches. To handle dynamic membership,
introduces Decaying Onion Bloom Clock (), a novel construct based on Bloom
clocks (bloom-clock, ). is agnostic to the identity and the number of the
participants in the network. It achieves this property by applying Bloom
filters to only record the state transition history. To maintain low false
positive rate even for arbitrarily long causal histories, uses layers of Bloom
filters, a construct inspired by log-structured merge-tree (lsmtree, ). Recent
transitions are stored in the top layer filters; when a layer is filled up,
its filters are merged and pushed to the next layer. therefore offers accurate
causality inference for recent histories, while its accuracy gracefully
degrades for the distant past.

To tolerate Byzantine participants, builds upon recent advances in verifiable
computation (VC). Specifically, applies non-uniform incrementally verifiable
computation (IVC) (ivc, ), a proof system that uses recursive Succinct Non-
interactive Argument of Knowledge (SNARKs) (snarks, ). When mutating an object
in , the initiating node generates a succinct proof that demonstrates the
validity of both the state transition and the clock update. The proof is
attached to the object when disseminating the object in the network. A
receiver verifies the attached proof before accepting the object. Using IVC, a
node can incrementally mutate any verified object, and efficiently generate a
succinct proof for the entire causal history of the object. Moreover, both
prover time and verifier time are independent of the length of the causal
history. As each node may apply arbitrary state mutation function to an
object, uses a variant of IVC called non-uniform IVC
(Kothapalli2022SuperNovaPU, ) to address the rigidity of the original IVC
construct.

We have built two decentralized systems atop to demonstrate the power of
verifiable causality. The first system is a weakly consistent data store .
provides eventual consistency (bayou, ) even in the presence of strong
adversaries. It leverages to track versioned histories of stored data and to
effectively merge conflicting versions. It relies on provable causal history
to avoid lost updates or inconsistencies cause by Byzantine behaviors. is more
scalable, available, and provides faster query latency than existing BFT
systems. The second system, , is an anti-censorship decentralized social
network. Beyond the benefits already provided in , enables to effectively
eliminate censorship attacks, a major challenge in other social applications.
Using verifiable causality, clients in can enforce propagation and visibility
of posted content, and generate proof-of-censorship when censorship attacks
are launched.

##  2\. Background

This section covers background information on two main topics: causality of
events in a distributed system, and verifiable computation.

###  2.1. Causality of Events in Distributed Systems

The seminal work by Lamport (lamport-clock, ) introduces a _happens-before_
relationship that defines the possible causality between events in a
distributed system. Specifically, let $\prec$ be a binary relation between
pairs of events in an execution of a distributed system. $e_{1}\prec e_{2}$ if
event $e_{1}$ may influence event $e_{2}$, or equivalently, $e_{2}$ is
causally dependent on $e_{1}$. $\prec$ is a strict partial order, , it is
_irreflexive_ , _asymmetric_ , and _transitive_. Being a partial order, not
all pairs of events are causally dependent. If neither $e_{1}\prec e_{2}$ nor
$e_{2}\prec e_{1}$, $e_{1}$ and $e_{2}$ are defined to be logically concurrent
(represented as $e_{1}\parallel e_{2}$). Without perfectly synchronized
physical clocks, it is impossible to determine which of $e_{1}$ or $e_{2}$
happens first if $e_{1}\parallel e_{2}$.

Events in an execution are categorized into three general types:

  * •

Local events on a node (). They are any event happen on a node that does not
involve messages.

  * •

Message send event (). A source node sends an unicast message to a destination
node. Broadcasts or multicasts are equivalent to a set of unicast messages.

  * •

Message receive event (). For each , there is a corresponding message receive
event on the destination node if the message is successfully delivered.

The happens-before relation $\prec$ on events in an execution obeys the
following rules:

  * •

1 $\prec$ 2 if both events happen on the same node and 1 happens before 2 in
the local sequential event order.

  * •

$\prec$ if and are the corresponding message send and receive pair.

###  2.2. Logical Clocks

Logical clocks can be used to determine the happens-before relation defined in
subsection 2.1. One instance of logical clocks is the Lamport clock (lamport-
clock, ). Using Lamport clock, each node $n_{i}$ in the system maintains a
local clock $c_{i}$, represented as a natural number. The rules to update the
clocks are:

  * •

Upon a local event i, $n_{i}$ increments its local clock.

  * •

When $n_{i}$ sends a message, $n_{i}$ increments its local clock, and attaches
the local clock value in the message.

  * •

When $n_{i}$ receives a message with a clock value $c_{m}$, it sets its local
clock to $max(c_{i},c_{m})+1$.

The logical time of an event $e$, represented as $c_{e}$, is the local clock
value after the clock update. Lamport clock guarantees the following property:
If $e_{1}\prec e_{2}$, then $c_{e_{1}}<c_{e_{2}}$. However, the inverse is not
true, , $c_{e_{1}}<c_{e_{2}}$ does not imply that $e_{1}\prec e_{2}$. To be
more precise, if $c_{e_{1}}<c_{e_{2}}$, either $e_{1}\prec e_{2}$ or
$e_{1}||e_{2}$, but not $e_{2}\prec e_{1}$. For use cases that require
accurate causality inference, Lamport clock falls short.

Vector clock addresses this shortcoming of Lamport clock. As the name
suggested, a vector clock, $v$, consists of a vector of natural numbers.
Cardinality of a vector clock equals the size of the system. Each node is
assigned a unique index in the vector clock. We use $v[i]$ to denote the $i$th
number in a vector clock $v$. The rules to update the vector clocks are:

  * •

Upon a local event i, $n_{i}$ increments $v_{i}[i]$.

  * •

When $n_{i}$ sends a message, $n_{i}$ increments $v_{i}[i]$, and attaches
$v_{i}$ in the message.

  * •

When $n_{i}$ receives a message with a clock $v_{m}$, it sets $v_{i}$ to
$v_{i}^{\prime}$, where $\forall
p\in[0..S),v_{i}^{\prime}[p]=max(v_{i}[p],v_{m}[p])$, $S$ is the size of the
system. $n_{i}$ then increments $v_{i}[i]$.

$v_{i}<v_{j}$ if and only if $\forall p\in[0..S),v_{i}[p]\leq v_{j}[p]$ and
$\exists p\in[0..S),v_{i}[p]<v_{j}[p]$. By definition, there exists $v_{i}$
and $v_{j}$ such that neither $v_{i}<v_{j}$ nor $v_{j}<v_{i}$, , $<$ is a
partial order on the set of vector clocks. Vector clock guarantees the
following stronger property: $e_{1}\prec e_{2}$ if and only if
$v_{e_{1}}<v_{e_{2}}$.

###  2.3. Verifiable Computation

In systems where identities cannot be trusted (our target deployment model),
publicly verifiable proofs are required to verify the claims made by the
participants. More concretely, if a node claims that the output of applying a
certain function $\mu$ on input $x$ is $y$, the naive way to verify such a
statement would be to re-execute the operation and compare the outputs. Such
an approach might not be viable when the verifier does not have enough
computational resources to execute the function. For instance, the current
bitcoin blockchain is approximately 450 GB in size. If a user wants to verify
the latest block, he can either:

  1. (1)

Trust the person who provided the latest block to him (this is extremely
unwise).

  2. (2)

Verify the whole chain himself from the genesis block; This takes a lot of
compute time, storage space, and network bandwidth.

An argument system is a cryptographic construct to achieve verifiable
computation without trusting the entity performing the computation. The goals
of an argument system are quite simple. For a given statement
$\mu(x)\stackrel{{\scriptstyle?}}{{\rightarrow}}y$, it produces an
accompanying proof $\pi$. This proof can be verified publicly to assert that
the statement is true with all but a negligible probability. More concretely,
a prover $P$ wishes to convince a verifier $V$ that it knows some witness
statement $w$ such that, for some public statement $x$ and arithmetic circuit
$C$, $C(x,w)\rightarrow y$.

##### Properties of an argument system.

There are two properties an argument system must satisfy:

  1. (1)

Completeness: A valid proof will always be accepted by a valid verifier.

  2. (2)

(Knowledge) Soundness: If a prover attempts to generate a proof without a
valid witness, this proof will only be accepted by the verifier with a
negligible probability.

There are many types of argument system. One of the most commonly used
argument systems is Succinct Non-interactive Arguments of Knowledge (SNARK).
As the name suggested, using a SNARK, the verifier requires no further
interaction with the prover, other than receiving the proof, when verifying;
the proof itself is also short, while the time to verify is fast (at most
logarithmic to the circuit size). If the witness $w$ cannot be derived by the
verifier with sufficient probability, then the SNARK is also considered _zero-
knowledge_ (zk-SNARK). does not require the zero-knowledge property, so we
omit the details of zk-SNARKs.

##### Recursive proof systems.

SNARKs are useful in many settings, e.g., cloud computing, as it allows a
verifier to validate computationally expensive function executions in a
fraction of the time to run it. However, in some distributed computing
scenarios, simply verifying a single execution is not sufficient. Instead, we
wish to verify a particular non-deterministic chain of executions. Naively
applying any off-the-shelf general circuit SNARK for every step will result in
proofs and verification times that grows linearly. In a highly evolving and
volatile system, these metrics are unacceptable.

There has been some recent development in verifiable computation that has the
potential to address the above challenges. One particularly promising
technique is recursive proof system. In a recursive proof system, the prover
recursively proves the correct execution of incremental computations. Such
technique can be applied to realize incrementally verifiable computation
(IVC). In IVC, in each step of the computation, the prover takes the output
and proof of the previous step, and produces an output and proof for the next
step. A verifier only needs to verify the proof of a single step to ensure
correct execution of the entire computation from genesis. Critically, both
prover and verifier time are independent of the length of the computation.
There exists quite a few constructions for recursive proofs in the wild,
ranging from constructs like Halo(Bowe2020RecursivePC, ) to PCD(pcd, ). We
envision more and more efficient constructs will be developed eventually.

##  3\.

We first define the high-level model and properties of . The system consists
of a set of nodes ($n_{1},n_{2},\dots$). Nodes can create, destroy, and mutate
_objects_. They can also send objects to other nodes in the system. Besides
send and recv, we define generic create and mutate functions:

  * •

${create()}\rightarrow o$: the create function generates an object.

  * •

${mutate(o_{1},o_{2},\dots)}\rightarrow o^{\prime}$: the mutate function takes
a list of objects $o_{1},o_{2},\dots$ and generates a new object $o^{\prime}$.

Unlike prior work (lamport-clock, ), concerns the causality of objects, not
causality of events. We similarly define a binary relation $\prec$ on the set
of objects in an execution of a distributed system. $\prec$ denotes the causal
relationship between any two objects, , $o_{1}\prec o_{2}$ if and only if
$o_{2}$ is causally dependent on $o_{1}$. Object causality in $\sys$ is
defined as follows:

  * •

If an object $o$ is generated from create, $o$ is not causally dependent on
any other object in the system, , $\forall o^{\prime}\in O,o^{\prime}\nprec
o$, where $O$ is all objects ever generated in the execution.

  * •

If an object $o$ is generated from $mutate(o_{1},o_{2},\dots)$, $o$ is
causally dependent on $o_{1},o_{2},\dots$, , $o_{1}\prec o,o_{2}\prec o,\dots$

We note that the causality definition in is stronger than those in prior work
(lamport-clock, ). Instead of “possible influence”, $\prec$ implies definite
causal relationship between two objects111We assume mutate implies definite
causality. That is, if $mutate(o_{1},o_{2},\dots)\rightarrow o$, then $o$ is
causally dependent on $o_{1},o_{2},\dots$.. More formally, if $o_{i}\prec
o_{j}$, there exist a sequence of mutate invocations such that
$mutate(o_{i},\dots)\rightarrow o_{1}$, $mutate(o_{1},\dots)\rightarrow
o_{2}$, …, $mutate(o_{n},\dots)\rightarrow o_{j}$.

provides the following _causality inference_ guarantee:

###### Theorem 3.1.

For any two objects $o_{i}$ and $o_{j}$ which are generated in an execution of
a distributed system, can deduce the causality relationship between the two
objects, , can correctly output $o_{i}\prec o_{j}$, $o_{j}\prec o_{i}$, or
$o_{i}\parallel o_{j}$.

##  4\. Design and Implementation

This section details the concrete design of using a novel logical clock
construct coupled with verifiable computation.

###  4.1. System Setting

TODO: double check some notations, esp after re-writing the verifiable
computation part

Suppose each object is defined as a tuple $o_{i}=(s_{i},C_{i})$, where
$s_{i}\in\mathcal{S}$ is a state permutation in the set of all possible states
$\mathcal{S}$. $C_{i}$ is a logical clock construct. This indicates that for
two objects $o_{1}=(s_{1},c_{x}),o_{2}=(s_{1},c_{y})$ with homogeneous states,
they are still considered unique $o_{1}\neq o_{2}$ if the clock values are
distinct.

attributes two objects with the exact same state and clock values as
identical. This, however, is not necessarily true. This is inevitable and
might lead to certain false positives in casualty evaluations.

There exists a dynamic set of objects $O$, which initially only includes the
genesis object $o_{0}=(s_{0},C_{0},d)$, where $s_{0}$ is the genesis state.
There also exists a family of mutate functions $M=\\{\mu_{1},\cdots\\}$. For a
new object $o_{i}$ to be created, a mutate function must be operated on an
existing object:

$\displaystyle\exists o_{i-1}\in O,\exists\mu\in M:\mu(o_{i-1})\rightarrow
o_{i},o_{i}\in O$

Therefore, $d$ for an object denotes the depth, or number of mutate functions
applied onto $o_{0}$ to derive the object.

###  4.2. Logical clock Constructs

In this section, we will explore a few existing clock constructs and evaluate
its feasibility of use in .

####  4.2.1. Vector clocks

Vector clocks (vector-clock, ) have long been the standard to determine
causality in systems. However, as briefly mentioned in section 3, vector
clocks do not necessarily draw accurate object causalities. Instead, vector
clocks simply provide a temporal order and use that to infer possible
causality; This will lead to great degrees of false positives.

We illustrate this with a simple example; Suppose we have two nodes $A$ and
$B$:

  1. (1)

$A$ and $B$ start with the vector clock $[0,0]$

  2. (2)

$A$ creates a new state, tags it with the clock value $[1,0]$ and sends it to
$B$.

  3. (3)

$B$ receives this new state and updates its clock to $[1,1]$.

  4. (4)

Suppose $B$ now creates a new state by applying mutate to the genesis state
instead of $A$’s newly produced state. $B$’s new clock value will be $[1,2]$.

The issue is that although $B$’s new state does not depend on $A$’s state, its
clock implies such. This is because the vector clock only captures the
temporal order of states/objects produced by the nodes, and therefore probable
causality; Furthermore, we conjecture this probability to be impossible to be
derived.

Instead, we have to provide a way for $B$ to generate distinct clocks based on
its decision (to either mutate the genesis object or $A$’s object). This
requires the decoupling of identities and clocks. Instead, each object is now
tied to a logical clock that is used to infer its plausible relationship with
another object.

####  4.2.2. Counting bloom clocks

The Bloom clock ($BC$) (bloom-clock, ) is a logical clock construct that can
be used to probabilistically determine causality between objects. The $BC$ is
based on the counting Bloom filter (bloom-filter, ), and can be defined as a
vector of $n$ integers $[c_{1},\cdots,c_{n}]$.

In the context of , when operating on an existing object
$\mu(s_{i},C_{i},d)\rightarrow(s_{i+1},C_{i+1},d+1)$, the $BC$ protocol uses a
family of $m$ cryptographically secure hash functions $h_{1},\cdots,h_{m}$
that produces $m$ indices $h_{1}(s_{i+1}),\cdots,h_{m}(s_{i+1})$. Each index
is then mapped and incremented on $C_{i}$ to produce $C_{i+1}$.

When comparing two objects, $o_{x}=(s_{x},C_{x},d_{x})$ and
$o_{y}=(s_{y},C_{y},d_{y})$, there are 3 possible scenarios:

  1. (1)

$\forall c_{xi}\in C_{x},c_{yi}\in C_{y},\exists c_{xj}\in C_{x},c_{yj}\in
C_{y}:c_{xi}\geq c_{yi}\land c_{xj}>c_{yj}\land
d_{x}>d_{y}\Rightarrow(s_{x},C_{x})\succ(s_{y},C_{y})$.

  2. (2)

$\forall c_{yi}\in C_{y},c_{xi}\in C_{x}:c_{yi}\geq c_{xi}\land d_{y}\geq
d_{x}\Rightarrow(s_{y},C_{y})\succeq(s_{x},C_{x})$

  3. (3)

$(s_{y},C_{y},d_{y})$ and $(s_{x},C_{x},d_{x})$ are concurrent.

The $BC$ might postulate parenthood when in fact the objects are concurrent.
This is due to possible hash collisions into the limited vector of size $n$.

The fundamental benefit of $BC$’s is its inherent agnosticism towards
identities in the system; It can potentially be utilized by an unbounded
number of nodes. This makes it suitable to be utilized in highly decentralized
and permissionless settings.

However, $BC$ suffers from two main issues:

##### Issue 1: limited lifespan.

Eventually, a $BC$ will increment to a point in which comparisons between two
objects will always lead to a false positive. That is to say the $BC$ can only
hold a limited amount of objects before its utility is diminished. Therefore,
to maintain its utility, we have to limit the number of objects a $BC$ can
hold. A naive reset might work, however it is crude. Comparisons between
resets are impossible. Additionally, some synchrony might be required to
derive consensus on the state of the clock before resets.

A simple fix would be to have a $BC$ be represented by $k$ bloom filters
$(BF)$ of size $n$. These $k$ bloom filters is a sliding window on the history
of objects, where objects outside these $k$ bloom filters are forgotten.

The intuition is that after $k$ mutates, there is little to be gained from
comparing a descendant state that is so far removed from its ancestor.
Following that philosophy, more priority should be put into recent states
(relative to the current state), and less priority to distant states.
Especially in the $BC$ protocol, a similar comparison will likely return a
false positive.

##### Issue 2: multi-parent problem.

In the $BC$ protocol, all prior object clocks $C_{i}$ are compressed into a
single vector. However, this also means that similar objects (by means of
indices after hashing) represented in the clock will potentially lead to false
positives. The simple fix represented above resolves this to some extent.
Since each $BC$ is now represented by $k$ bloom filters, we can analyze the
state at each depth of mutation. This removes some false positives that
previously existed in the original $BC$.

As illustrated with Figure 1, simply utilizing the bloom clock will lead to
the false conclusion that $o_{3}$ is causally dependant on $o_{2}$;This is due
to the coincidental hash collisions. However, if a history of $BF$s are
listed, it can be referenced and compared to eliminate $o_{2}$ as a false
parent of $o_{3}$.

Figure 1. How adding some history can be used to eliminate some false
positives: Without the history, $o_{2}$ will be incorrectly determined as the
ancestor to $o_{3}$.

###  4.3. Decaying Onion Bloom Clocks

The naive resolution described in subsubsection 4.2.2 would require an
extremely inefficient $k*n$ bits.

In , we introduce a novel logical clock construct: the Decaying Onion Bloom
Clock (). an improvement over $BC$s:

  1. (1)

probabilistically determines causality between objects with a depth difference
of at most $k$.

  2. (2)

addresses the issues described in subsubsection 4.2.2, whilst utilizing less
space. achieves this by keeping a finer grain memory of recent state
transitions; This is opposed to distant state transitions, where its view is
compressed to produce a coarser grained expression. To provide indefinite
utility across any number of state transitions, eventually forgets states that
are too distant. Eventually, states that are too distant are forgotten.

  3. (3)

A sub-function that allows s of different depths to be merged. The casuality
utility is maintained with regard to any of it its ancestors.

In this section we will describe the base protocol.

Need more intuition and high-level idea before diving into details.

We generalize the Counting bloom filter construct to variable-sized Bloom
filters ($VBF_{i}$), where each of its $n$ indices are stored with exactly $i$
bits. The also consists of $|L|$ layers, each layer $l^{i}$ stores a pre-
determined amount $|l^{i}|$ of $VBF_{j^{i}}$s, where $j^{i}$ is the size an
index for each $VBF$ at layer $l^{i}$ and $j^{i+1}>j^{i}$. For the sake of
simplicity, let’s assume $j^{i}\cong i$. Each $VBF_{i}$ in a layer is ordered
from $l^{i}_{1},\cdots,l^{i}_{|l^{i}|}$.

Figure 2. An illustration of how a will look like with the setting:
$j^{i}\cong i,|L|=3,|l^{1}|=4,|l^{2}|=2,|l^{3}|=1$

Suppose for a certain execution path, it produces an ordered set of objects
$\\{o_{0},o_{1},o_{2},\cdots\\}$, where $\exists\mu\ in\
M:\mu(o_{i}=(s_{i},C_{i},d))\rightarrow(o_{i+1}=(s_{i+1},C_{i+1},d+1))$.
Initially, $VBF_{i}$s on all layers are set to 0. For illustration purposes,
let’s use the following settings:

$\displaystyle|L|=3,|l^{1}|=4,|l^{2}|=2,|l^{3}|=1$

This is illustrated with Figure 2.

When $o_{1}$ is generated, a Bloom filter $BF_{s_{1}}$ is created by hashing
$s_{1}$ with the family of $m$ distinct hash functions and setting the
corresponding indices to 1. It is important to note that $VBF_{1}\cong BF$ if
both contain the same number of indices. This is only true for $VBF_{1}$
right? Yes correct

Figure 3. (1) illustrates the for $o_{1}$, (2) illustrates the for $o_{2}$
where $BF_{s_{1}}$ is moved to $l_{2}^{1}$ to make space for $BF_{s_{2}}$.

$BF_{s_{1}}$ is inserted into $l^{1}_{1}$. When $s_{2}$ is reached,
$BF_{s_{2}}$ is created and placed into $l^{1}_{1}$, and $BF_{s_{1}}$ is moved
to the next available slot (which in this case is $l^{1}_{2}$). for $o_{1}$
and $o_{2}$ is illustrated by Figure 3.

Figure 4. (1) illustrates the for $o_{5}$, (2) for $o_{6}$, (3) for $o_{7}$,
(4) for $o_{8}$.

Eventually, as new objects (and states) are created, in the DOBC for a
specific object ($o_{4}$), $BF_{s_{1}}$ will be at
$l^{1}_{|l^{i}|}=l_{4}^{1}$. To make space for $BF_{s_{4}}$, $BF_{s_{1}}$
instead moves to $l^{2}_{1}$. In theory a $VBF_{2}$ can hold the compressed
information of $2*2-1=3$ $VBF_{1}$s. Therefore,
$BF_{s_{1}},BF_{s_{2}},BF_{s_{3}}$ are added together before it moves to
$l_{2}^{2}$. This is illustrated by Figure 4. Intuitively, a $VBF_{i+1}$ in
layer $l^{i+1}$ can store a multiple of $VBF_{i}$ from the previous layer
($l^{i}$).

Figure 5.  (1) illustrates the for $o_{16}$. (2) illustrates the for $o_{17}$,
where $BF{s_{1}},\cdots,BF_{s_{6}}$ is evicted.

When $l^{|L|}_{|l^{i}|}$ has reached the maximum capacity, and a new state is
reached, for the new object, $l^{|L|}_{|l^{i}|}$ is deleted and
$l^{|L|}_{|l^{i}-1|}$ or $l^{|L|-1}_{|l^{i}|}$ takes its place. In the context
of our example, $BF{s_{1}},\cdots,BF_{s_{6}}$ is evicted from $l^{3}_{1}$ and
$BF_{s_{7}},\cdots,BF_{s_{9}}$ takes its space. This is illustrated with
Figure 5.

In our example, the keeps track of an average of $k=13.5$ states, but it is
clear to see that its ability to compare any causality drops every 4 objects.

It is clear to see that there exists some wastage in utilization with the
example , as a $VBF_{3}$ can in theory hold $2^{3}-1=7$ $BF$’s. However,
because it can only hold a certain multiple of $VBF$’s from the previous
layer, it only holds $(2^{2}-1)*2$ $BF$s.

The maximum number of $BF$’s or unique states held by $l^{|L|}_{|l^{i}|}$ is
therefore:

$\displaystyle\gamma=\left(\prod_{i=1}^{i=|L|-1}\left\lfloor\frac{2^{j^{i+1}}-1}{2^{j^{i}}-1}\right\rfloor\right)*(2^{j^{1}}-1)$

The total number of states a can hold thus ranges from $[k,k-\gamma+1]$
states, with an average of $k+\frac{\gamma+1}{2}$ states. Where for $|L|>1$:

$\displaystyle
k=|l^{1}|*(2^{j^{1}}-1)+\left(\sum_{i=2}^{i=|L|}\left\lfloor\frac{2^{j^{i}}-1}{2^{j^{i-1}}-1}\right\rfloor*|l^{i}|\right)$

Figure 6.  (1) illustrates the for $o_{16}$. (2) illustrates the for $o_{18}$.
To determine if $o_{18}$ is causally dependent on $o_{16}$, we simply compare
the similarly highlighted parts in both clocks. If the similarly highlighted
parts in (2) is greater than or equal to the ones in (1) for all similarly
highlighted parts, then we conclude $o_{18}\succ o_{16}$.

####  4.3.1. Comparing s

In this section, we will go through how two different s are compared to derive
causality. In the naive approach mentioned in subsubsection 4.2.2, it is quite
obvious to see how clocks can be compared. However, in , we only keep a
limited history $~{}k$ of states, therefore only histories of a certain range
can be compared. The greater the overlap, the lower the possibilities of false
positives. We will utilize the same setting from subsection 4.3 to illustrate
an example. Suppose we have the for $o_{18}$ and $o_{16}$, how we determine
causality of $o_{18}$ on $o_{16}$ is illustrated with Figure 6: Since each
state has differing depths, we compare different sections of its s to draw our
causality conclusion. For example, $l_{3}^{1}\in o_{18}$ should correspond to
$l_{1}^{1}\in o_{16}$. Similarly, the $l_{1}^{2}\in o_{18}$ corresponds to
addition of $l^{1}_{3}\cap l^{1}_{4}\in o_{16}$. Intuitively, two set of
$VBF$’s are comparable between two s if they correspond to the same depth. If
all comparable $VBF$s in $o_{18}$ are greater than or equal to the
corresponding $VBF$s in $o_{16}$, then we draw the conclusion that
$o_{18}\succ o_{16}$ with some acceptable probability.

####  4.3.2. Eliminating Wastage in

As briefly mentioned in subsection 4.3, certain parameters will lead to bit
wastage. This is not ideal if we wish to fully utilize every single bit in .
We came up with two possible approaches to mitigate wastage. These approaches
might require overhauls to the protocol:

Figure 7.  (1) illustrates the for $o_{11}$. (2) illustrates the for $o_{12}$
with incomplete decay; Although $l^{2}_{1}$ is not completely full, it is
shifted along with $1^{2}_{2}$ to completely fill $l^{3}_{1}$.

  1. (1)

Incomplete $VBF$ decay: We dictate that a $VBF_{j^{i}}$ does not necessarily
have to be “full” before it is moved to the next layer. That is to say we
change the “a $VBF_{i+1}$ in layer $l^{i+1}$ can store a multiple of $VBF_{i}$
from the previous layer ($l^{i}$)” notion of the base protocol. We should be
able to fully utilize all the space in all layers. This is illustrated by
Figure 7. An important note is that $VBF_{j^{1}}$ must be of sufficient
granularity to fill all the “gaps” of $VBF$’s of subsequent layers. Therefore,
$j^{1}=1$ should always work.

  2. (2)

Perfect $VBF$ decay: If the next layer $VBF_{j^{i}}$ can exactly hold a
multiple of $VBF_{j^{i-1}}$s from the previous layer, then naturally, space
will be fully utilized. More concretely, the number of $BF$s $VBF_{j^{i}}$ can
hold is congruent to 0 modulo of the $BF$s $VBF_{j^{i-1}}$ can hold, given
$|L|>1$.

An example would be to have the setting: $|L|=3,j^{1}=1,j^{2}=2,j^{3}=4$. No
space will be wasted since:

$\displaystyle(2^{2}-1)\%1=0$ $\displaystyle(2^{4}-1)\%(2^{2}-1)=0$

####  4.3.3. Merging s

Figure 8. Utilizing the same settings from subsection 4.3: Suppose we wish to
merge two objects $o_{x}$ and $o_{y}$ (1) The Extending Clocks solution will
append the appropriate $VBF$’s to each other. (2)The Combined Maxima Clocks
solution takes it a step further; trading false positives with space. The
$VBF$’s at each position $l^{i}_{j}$ are the maximum of the indices between
the $VBF$’s seen in the extending clocks solution.

Suppose if two objects were to be merged, the resultant state and its
descendants will have some causal relation to both parents. In , merging both
s must be done elegantly. This is to ensure that the causality of future
descendants can still be adequately inferred.

has two methods to merge clocks, each at opposite ends of the spectrum when it
comes to utility and its trade-offs.

Since only keeps track of at most $k$ objects prior to the current one. When
merging two objects
$o_{x}=(s_{x},C_{x},d_{x}),o_{y}=(s_{y},C_{y},d_{y}):|d_{x}-d_{y}|>k$ , the
resultant object technically exists as both depth $d_{y}+1$ and $d_{x}+1$.

Changed from last time

The unfortunate side effect of merging is that the new merged must keep track
of both heights.

Figure 9. Since the Extending Clocks solution merges clocks at differing
states of decay, decaying both clocks as is might lead to indefinite extra
space utilization. To make the extra space utilization transient, we use the
“more-decayed” clock as an anchor to decay the other “less-decayed” clock. As
seen in (1), since the clock highlighted red is of a greater state of decay,
therefore after (2), at (3) it also pre-emptively decays the blue clock. The
result is a single $VBF$ at $l^{2}_{1}$.

##### Extending Clocks:

The Extending clocks approach is the most naive approach. As the name
suggests, and illustrated in (1) of Figure 8: The corresponding $VBF$’s after
a merge is stored in a linked list configuration, where each
$l_{j}^{i}:i=1,j>1$ is now a pair of $VBF$’s.

Comparing s to derive causality will now be done twice; once with the red
highlighted $VBF$’s, another with the blue ones.

This merging solution will linearly grow the size of the resultant clocks per
merge. However, this increase in space is transient and will only persist for
at most $k$ mutations. This is achieved by tweaking the decay function of , by
making the new merged $BF$’s decay at different rates. This is illustrated in
Figure 9.

##### Combined Maxima Clocks:

Instead of naively appending clocks together in the previous solution, another
alternative is to take the maxima of each index of the $VBF$’s. As illustrated
in Figure 8, for $l^{2}_{1}$, the $VBF_{2}$ will have its value at each index
be the maximum of that of the corresponding two $VBF$’s from $o_{x}$ and
$o_{y}$.

Intuitively, such an approach will definitely increase the false positive
rate. However, its inherent benefit is that the resultant merged will always
remain the same size.

Furthermore, the false positive rate can be reduced by increasing $n$ (number
of indices) of the $VBF$s.

##### Hybrid Approach:

A hybrid approach will be to employ the extending clocks method for a maximum
of $p$ merges. After which, older merges will be combined in the same approach
outlined by the combined maxima clocks.

This will ensure a bound on the clock size, whilst having some good utility
and lower false positive rates in some cases.

###  4.4. Verifiable Logical Clock Construction

To apply a proof system for we first need to articulate the requirements we
need, more precisely:

  1. (1)

The proof system must support a known family of functions
($M=\\{\mu_{1},\cdots,\mu_{i},\cdots,\mu_{\omega}\\},|M|=\omega$).

  2. (2)

For a particular proof corresponding to a linear execution of $n$ functions.
The proof must assert to the validity that a non-deterministic multiset of
functions of size $n$ have been applied onto the genesis state. That is to say
$\exists m=\\{m_{1},\cdots,m_{n}\\}:\forall m_{i}\in m,m_{i}\in M$ where there
$\exists\pi$ that validates $s_{n}\leftarrow
m_{n}(m_{n-1}\cdots(m_{1}(s_{0})))$, where $s_{0}$ is the genesis state.

  3. (3)

Transparent setup: every one can join as is.

  4. (4)

Proof size and verification time must remain constant.

At the time of writing, we will utilize the constructs introduced in
Nova(Kothapalli2021NovaRZ, ) and subsequently
SuperNova(Kothapalli2022SuperNovaPU, ).

####  4.4.1. R1CS (Rank 1 Constraint System)

To understand Nova and by extension, SuperNova, we must first briefly explain
R1CS. R1CS is a method to quickly verify that a particular binary or
arithmetic execution has been carried out properly without actually running
through the execution again. More precisely, R1CS allows the prover to
generate a solution to some polynomial problem (represented by the arithmetic
circuit), in which the verifier can verify in constant time.

The arithmetic circuit222We will omit details in regard to binary circuits as
any binary circuit can be converted into an arithmetic circuit. can be viewed
logically as a collection of gates, where each gate has a left and right input
as well as a single output. How the gates are wired to produce the final
outputs are defined by a set of 3 matrices $A,B,C\in\mathbb{F}^{q\times q}$.
The prover also generates a solution vector $Z={W,x,1},Z\in\mathbb{F}^{q}$,
where $W$(or witness) are the intermediary outputs, $x$(or instance) are the
inputs and outputs of the circuit, and $1$ is a constant.

The verifier can simply verify the execution of the whole circuit as:

$(A\cdot Z)\circ(B\cdot Z)=(C\cdot Z)$

Where $\cdot$ denotes matrix multiplication and $\circ$ denotes the Hadamard
product.

####  4.4.2. What is Nova?

Nova, is an Incrementally Verifiable Computation (IVC) algorithm that requires
no trusted setup, generates constant sized proofs for any step, and guarantees
constant verification time. Nova introduced a novel method to combine two R1CS
instances into a single instance. Naively adding two R1CS instances would lead
to an incorrect instance. Therefore, Nova introduces a variant of R1CS:
_Relaxed R1CS_ which introduces an error vector $E\in\mathbb{F}^{q}$, where an
instance $(E,u,x)$ is satisfied if:

$(A\cdot Z)\circ(B\cdot Z)=u\cdot(C\cdot Z)+E$

Where $Z=(W,x,u)$. In particular, suppose there are two separate instances
$Z_{1}=(W_{1},x_{1},u_{1})$ and $Z_{2}=(W_{2},x_{2},u_{2})$. $u\leftarrow
u_{1}+r\cdot u_{2}$ and $E$ is a function of $(Z_{1},Z_{2},r)$. The resulting
instance or _folded_ instance can be simply verified by the verifier. The
intuition is that if any of the relaxed R1CS instances that were folded is
invalid, then the final folded relaxed R1CS instance will be invalid as well.
Therefore, verifying the final folded relaxed R1CS instance asserts that
arithmetic circuit has been executed correctly a particular number of times.

Verifier work is further reduced by the introduction of the _committed relaxed
R1CS_ scheme. This scheme allows the prover to utilize additively-homomorphic
commitment schemes (like Pedersen commitments) to save the verifier from
generating $E$ themselves. Instead, the prover will send commitments for
${E_{1},E_{2},W_{1},W_{2}}$ as well as another matrix $T$ which is a result of
a function of $Z_{1},Z_{2}$.

The verifier can additively combine the commitments to generate the committed
folded instance. The prover will then reveal the actual folded instance. If it
matches, the verifier can simply take the folded instance as is to use for
verification.

The resultant proof structure for the $i^{th}$ step is a folded committed
relaxed R1CS instance and witness pair asserting to the validity of executions
up till step $i-1$, and a single relaxed R1CS asserting to the validity of
step $i$.

The scheme is then made _non-interactive_ by utilizing a public coin333This
can be instantiated by using a cryptographic-secure hash function hinging on
the Fiat-Shamir heuristic.

####  4.4.3. Nova for a family of functions

Traditional IVCs like Nova typically are designed for a single function. To
allow Nova to satisfy requirement (2) above, we can utilize a universal
circuit. Intuitively, a universal circuit can be visualized as a circuit made
by combining $n$ sub-circuits, each representing the execution to a particular
function. The inputs of this universal circuit will then “select” a particular
sub-circuit to execute.

The major downside to utilizing general circuits is that for any step of the
execution, the whole circuit is actually still processing some input and
generating some output. This means the prover will be doing some unnecessary
work. Additionally prove sizes might be larger.

SuperNova(Kothapalli2022SuperNovaPU, ) was developed to circumvent this issue,
we will elaborate this in the following text.

####  4.4.4. SuperNova: Universal machines without universal circuits

SuperNova generalizes Nova’s IVC to _non-uniform_ IVC, i.e., there exists a
family of functions $F=\\{f_{1},\cdots,f_{n}\\}$, and a control function
$\varphi$ which determines the function to run at a particular step $j$. That
is to say at the $j^{th}$ step, the prover proves that
$f_{j},j=\varphi(W_{i},x_{i})$ has been correctly applied with witness
instance pair $(W_{i},x_{i})$ to produce $x_{i+1}$.

##### Recursive Proofs in SuperNova:

It is not possible to naively apply the folding scheme developed in Nova,
because each function (and the corresponding circuit) is structurally
heterogeneous.

A SuperNova proof therefore maintains a list of running instances
$\mathtt{U}_{i}$, where $\mathtt{U}_{i}[j]$ is the folded instance of all
previous invocations of $f_{j}$ before the $i^{th}$ step. It also contains a
corresponding list of Witnesses $\mathtt{W}_{i}$, as well as an instance
witness pair $(\mathtt{u}_{i},\mathtt{w}_{i})$ that asserts to valid execution
of step $i$.

Furthermore, instead of simply applying the functions within the function
family as is, SuperNova instead runs the _augmented_ version of the function
$f^{\prime}_{\varphi(W_{i},x_{i})}$.

In essence, the augmented function does not just simply run
$f_{\varphi(W_{i},x_{i})}(W_{i},x_{i})$ to output $x_{i+1}$. It also checks
that $\mathtt{U}_{i},\varphi(W_{i-1},x_{i-1})$ are indeed produced by the
prior step if it is contained in $\mathtt{u}_{i}$. This asserts that checking
$\mathtt{U}_{i+1}$ is the same as checking $(\mathtt{U}_{i},\mathtt{u}_{i})$.
The augmented function then folds $\mathtt{u}_{i}$ into
$\mathtt{U}_{i}[\varphi(W_{i-1},x_{i-1})]$, and produces
$\varphi(W_{i},x_{i})$.

$((i+1,x_{0},x_{i+1}),\mathtt{U}_{i+1},\varphi(W_{i},x_{i}))\leftarrow
f^{\prime}_{\varphi(W_{i},x_{i})}(\mathtt{U}_{i},\mathtt{u}_{i},\varphi(W_{i-1},x_{i-1}),(i,x_{0},x_{i},W_{i}))$

Resulting in the witness pair $(\mathtt{u}_{i+1},\mathtt{w}_{i+1})$.

Intuitively, verifying $\mathtt{U}_{i+1}$ is equivalent to verifying the prior
$i$ steps. $\mathtt{u}_{i+1}$ asserts the $i+1$ step. Therefore, the proof for
step $i$ can be expressed as:

$\Pi_{i}=((\mathtt{U}_{i},\mathtt{W}_{i}),(\mathtt{u}_{i},\mathtt{w}_{i}))$

Additional details on SuperNova proofs using committed relaxed R1CS instances
can be found in the original paper.

We aim to utilize the Non-Uniform Incrementally Verifiable Computation scheme
described above for . As such, each function in $F$ corresponds injectively to
a specific mutate function in $M$. The depth value $d$ simply corresponds to
$i$ in each instance $\mathtt{u}_{i}$. The object state and clock value
corresponds to $x_{i}$.

##  5\. Use Cases

So far, we have discussed the high-level properties of , and a concrete design
of using and verifiable computation. In this section, we describe a few use
cases of .

###  5.1. Weakly Consistent Data Store

Prior systems (dynamo, ) have built data stores with eventual consistency
using logical clocks. Similarly, we leverage to build a weakly consistent
decentralized data storage, . implements a key-value storage interface. Each
unique _key_ is mapped to an arbitrarily-sized value. is fully decentralized
and permissionless. Any node can join and leave the system at any time.
Compared to its strongly consistent counterparts (bitcoin, ; ethereum, ),
offers higher efficiency, scalability, and availability.

provides _eventual consistency_ : if no further writes are applied to a key,
eventually all nodes observe the same value mapped to the key. Each node
maintains a subset of the keys in the key-space. We use a distributed hash
table (DHT) (chash, ; chord, ; kademlia, ) with virtual nodes for key-space
partitioning and request routing. For fault tolerance, each key is stored on
$R$ virtual nodes closest to the key hash on the hash ring, where $R$ is a
configurable parameter. This set of virtual nodes is called the _replica
group_ for the key. Higher $R$ offers stronger fault tolerance, but results in
longer update latency and higher storage overhead.

’s storage API exposes three external operations, Get, Insert, and Update. Get
takes a key and returns the value mapped to the key. Update maps a new value
to an existing key. Insert creates a new key into with an initial mapped
value. Insert also takes an optional user-defined Merge function. The Merge
function takes a set of values as input and outputs a single value. For
instance, a Merge function for numerical value types could be maximum, and
union for set value types.

When a client invokes Insert, the request is routed to one of the $R$
responsible virtual nodes on the DHT. The client can choose any reachable
nodes, $L$, in the replica group. Upon receiving the Insert request, $L$
invokes create to generate an object, with the genesis state set to the value
in the request. The object state also includes the Merge function in the
request. $L$ then forwards the generated object to the remaining nodes in the
replica group. Each node in the group verifies the validity of the object
using the attached proof (subsection 4.4) and stores it locally.

When a client invokes Update on a key, the request is similarly routed to one
of the $R$ responsible virtual nodes, $L$. Note that $L$ does not need to be
the same node that creates the object. $L$ then invokes mutate with the
locally stored object $o_{l}$ as input, , ${mutate(o_{l})}\rightarrow
o_{l}^{\prime}$. The output object state is set to the value in the Update
request. $L$ then forwards $o_{l}^{\prime}$ to the other nodes in the replica
group. When a replica node receives $o_{l}^{\prime}$, it uses to determine the
causality relation between $o_{l}^{\prime}$ and its locally stored object $o$.
If $o_{l}^{\prime}\prec o$, the node ignores the object. If $o\prec
o_{l}^{\prime}$, the node replaces the local object with $o_{l}^{\prime}$.
Otherwise, $o\parallel o_{l}^{\prime}$ and the node invokes
${mutate(o_{l}^{\prime},o)}\rightarrow o^{\prime}$, and stores the new object
$o^{\prime}$. When invoking mutate, the node applies the Merge function stored
in the object.

When a client invokes Get, it simply routes the request to any of the $R$
nodes in the replica group. The node returns the object if it is stored
locally. The client iterates through the replica group until the object is
found.

###  5.2. Anti-Censorship Decentralized Social Network

The second use case is a decentralized social network, , which we built atop .
In , users (represented by a private/public key pair) publish posts (, short
text, blogs, and photos) to the network, and subscribe to other users to
receive their posted content. Users can also react and comment on posted
content, both of which are fetched alongside the content.

stores the status and all published content of a user in a object with the
type . 444For simplicity, we store both the metadata and the content in the
object. An optimized implementation can store content separately, and only
saves content hashes, which can be used as pointers, in the object. All posts
are signed by the publishing user. defines a Update and a Merge function.
Update takes a and produces a new with the newly published posts added to it.
Merge takes multiple s for the same user and merge their content to produce a
new . Probably need to define the semantics of Merge, , ignores old state in
causal dependency chain. To read the posts of a user, a subscribed client
simply fetches the corresponding . We omit the exact format of and detailed
implementation of Update and Merge.

uses a DHT (chash, ; chord, ; kademlia, ) for content routing. Each user is
mapped to $R$ nodes closest to its public key hash on the hash ring, with $R$
a configurable parameter. Similar to the data store, these $R$ nodes are
called the replica group of the . To publish a post, the user first fetches
its own from any of nodes in the replica group. It can optionally cache the to
avoid subsequent fetches. If the is not available, the user creates a new by
calling create(). The user then applies mutate() on the with the Update
function to add the post, and sends the resulting to all nodes in the replica
group. When a node receives a , it verifies the validity of the object (,
contains the correct signatures from the user) and the clock, and applies
$\code{mutate(\uobj,\uobj{}^{\prime})}$ with the Merge() function, where ’ is
the currently stored user object.

To subscribe to another user, the client sends a Subscribe message to all $R$
nodes in the replica group of the target user. The replicas records this
subscription. Once a replica node receives a generated by the target user, it
sends a notification to the subscribed client, who then fetches from the
replica. The client verifies the validity of the object before accepting it.
Due to asynchrony and network partitions, it may receive stale or diverged s.
To address this issue, the client stores a for each subscribed user. When it
received a ’ from a replica, it applies
$\code{mutate(\uobj,\uobj{}^{\prime})}$ with the Merge function to update the
object.

##  6\. Conclusion

In this work, we design a new logical clock system, . addresses key
limitations of prior logical clock constructs. It scales perfectly in a
decentralized network with dynamic membership, and tolerates Byzantine
behaviors regardless of the proportion of adversaries. achieves the above
strong properties by introducing a novel logical clock structure, the Decaying
Onion Bloom Clock (). It additionally applies non-uniform IVC to ensure
independently verifiable construction of even in the presence of Byzantine
behaviors. To showcase the capability of verifiable causality enabled by , we
have built a weakly consistent key-value store and an anti-censorship social
network using .

## References

  * (1) J. Baker, C. Bond, J. C. Corbett, J. J. Furman, A. Khorlin, J. Larson, J.-M. Leon, Y. Li, A. Lloyd, and V. Yushprakh.  Megastore: Providing Scalable, Highly Available Storage for Interactive Services.  In Proceedings of the Conference on Innovative Data system Research, CIDR ’11, pages 223–234, Asilomar, California, 2011.
  * (2) N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer.  From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 326–349, New York, NY, USA, 2012. Association for Computing Machinery.
  * (3) B. H. Bloom.  Space/time trade-offs in hash coding with allowable errors.  Commun. ACM, 13(7):422–426, jul 1970.
  * (4) S. Bowe, J. Grigg, and D. Hopwood.  Recursive proof composition without a trusted setup.  2020\.
  * (5) M. Burrows.  The Chubby Lock Service for Loosely-Coupled Distributed Systems.  In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, OSDI ’06, pages 335–350, Seattle, Washington, 2006. USENIX Association.
  * (6) V. Buterin.  A Next-Generation Smart Contract and Decentralized Application Platform.  2014\.
  * (7) F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber.  Bigtable: A Distributed Storage System for Structured Data.  In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, OSDI ’06, pages 205–218, Seattle, Washington, 2006. USENIX Association.
  * (8) A. Chiesa and E. Tromer.  Proof-carrying data and hearsay arguments from signature cards.  In A. C. Yao, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 310–331. Tsinghua University Press, 2010.
  * (9) J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford.  Spanner: Google’s Globally-Distributed Database.  In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI ’12, pages 251–264, Hollywood, CA, USA, 2012. USENIX Association.
  * (10) G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels.  Dynamo: Amazon’s Highly Available Key-Value Store.  In Proceedings of Twenty-First ACM SIGOPS Symposium on Operating Systems Principles, SOSP ’07, pages 205–220, Stevenson, Washington, USA, 2007. Association for Computing Machinery.
  * (11) S. Ghemawat, H. Gobioff, and S.-T. Leung.  The Google File System.  In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, SOSP ’03, pages 29–43, Bolton Landing, NY, USA, 2003. Association for Computing Machinery.
  * (12) A. Hastings.  Distributed lock management in a transaction processing environment.  In Proceedings Ninth Symposium on Reliable Distributed Systems, pages 22–31, 1990.
  * (13) D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin.  Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.  In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 654–663, El Paso, Texas, USA, 1997. Association for Computing Machinery.
  * (14) A. Kothapalli and S. T. V. Setty.  Supernova: Proving universal machine executions without universal circuits.  IACR Cryptol. ePrint Arch., 2022:1758, 2022.
  * (15) A. Kothapalli, S. T. V. Setty, and I. Tzialla.  Nova: Recursive zero-knowledge arguments from folding schemes.  In IACR Cryptology ePrint Archive, 2021.
  * (16) L. Lamport.  Time, Clocks, and the Ordering of Events in a Distributed System.  Commun. ACM, 21(7), July 1978.
  * (17) L. Lamport.  Paxos Made Simple.  ACM SIGACT News, 32(4):51–58, Dec. 2001.
  * (18) L. Lamport, R. Shostak, and M. Pease.  The Byzantine Generals Problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982.
  * (19) J. Li, J. Nelson, E. Michael, X. Jin, and D. R. K. Ports.  Pegasus: Tolerating Skewed Workloads in Distributed Storage with In-Network Coherence Directories.  In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI ’20, pages 387–406. USENIX Association, Nov. 2020\.
  * (20) U. Mathur, A. Pavlogiannis, H. C. Tunç, and M. Viswanathan.  A tree clock data structure for causal orderings in concurrent executions.  In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’22, page 710–725, New York, NY, USA, 2022. Association for Computing Machinery.
  * (21) P. Maymounkov and D. Mazières.  Kademlia: A Peer-to-Peer Information System Based on the XOR Metric.  In P. Druschel, F. Kaashoek, and A. Rowstron, editors, Peer-to-Peer Systems, IPTPS ’02, pages 53–65, Berlin, Heidelberg, 2002\. Springer Berlin Heidelberg.
  * (22) S. Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  2009\.
  * (23) B. M. Oki and B. H. Liskov.  Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems.  In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC ’88, pages 8–17, Toronto, Ontario, Canada, 1988. Association for Computing Machinery.
  * (24) D. Ongaro and J. Ousterhout.  In Search of an Understandable Consensus Algorithm.  In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC ’14, pages 305–320, Philadelphia, PA, 2014. USENIX Association.
  * (25) P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil.  The log-structured merge-tree (lsm-tree).  Acta Inf., 33(4):351–385, jun 1996.
  * (26) L. Ramabaja.  The bloom clock.  arXiv 1905.13064, 2019.
  * (27) F. B. Schneider.  Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial.  ACM Comput. Surv., 22(4):299–319, Dec. 1990.
  * (28) R. Schwarz and F. Mattern.  Detecting causal relationships in distributed computations: In search of the holy grail.  Distributed Computing, 7(3):149–174, Mar. 1994.
  * (29) I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan.  Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications.  In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM ’01, pages 149–160, San Diego, California, USA, 2001\. Association for Computing Machinery.
  * (30) D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser.  Managing update conflicts in bayou, a weakly connected replicated storage system.  In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, SOSP ’95, page 172–182, New York, NY, USA, 1995. Association for Computing Machinery.
  * (31) A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi.  Calvin: Fast Distributed Transactions for Partitioned Database Systems.  In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, SIGMOD ’12, pages 1–12, Scottsdale, Arizona, USA, 2012. Association for Computing Machinery.
  * (32) F. J. Torres-Rojas and M. Ahamad.  Plausible Clocks: Constant Size Logical Clocks for Distributed Systems.  Distrib. Comput., 12(4):179–195, Sept. 1999.  Place: Berlin, Heidelberg Publisher: Springer-Verlag.
  * (33) P. Valiant.  Incrementally verifiable computation or proofs of knowledge imply time/space efficiency.  In Proceedings of the 5th Conference on Theory of Cryptography, TCC’08, page 1–18, Berlin, Heidelberg, 2008. Springer-Verlag.
  * (34) S. A. Weil, S. A. Brandt, E. L. Miller, D. D. E. Long, and C. Maltzahn.  Ceph: A Scalable, High-Performance Distributed File System.  In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, OSDI ’06, pages 307–320, Seattle, Washington, 2006. USENIX Association.
  * (35) Z. Yu, Y. Zhang, V. Braverman, M. Chowdhury, and X. Jin.  Netlock: Fast, centralized lock management using programmable switches.  In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM ’20, page 126–138, New York, NY, USA, 2020. Association for Computing Machinery.