# Consensus in the Unknown-Participation Message-Adversary Model

Giuliano Losa<EMAIL_ADDRESS>0000-0003-2341-7928 Stellar Development
FoundationUSA and  Eli Gafni<EMAIL_ADDRESS>University of California, Los
AngelesUSA

###### Abstract.

We propose a new model that resembles Algorand’s mechanism that selects a
committee at each synchronous round to govern the stateless progression of its
consensus algorithm. We consider an infinite set of authenticated processors
in a synchronous round-by-round model. At each round $r$ an adversary chooses
an unknown, finite committee $C_{r}$. Unlike Algorand, no information is known
about the size of the committee. The committee can send messages to the whole
universe, while processors outside the committee at the round do not send
messages at all. Moreover, the adversary partitions the committee into a set
of good processors $G_{r}$ and a set of processors $F_{r}$ that it
impersonates during round $r$.

If we fix $F_{r}$ to be static, i.e. the same in all rounds, we obtain an
idealized version of the Sleepy Model of Pass and Shi. If both $G_{r}$ and
$F_{r}$ are static and are additionally known to the processors, we obtain the
traditional, synchronous Authenticated Byzantine Agreement Model.

Assuming that a majority of the committee is good in each round, we show that
consensus is solvable deterministically if the union of all sets $F_{r}$ is
bounded. We also show that consensus is solvable probabilistically even if
both $G_{r}$ and $F_{r}$ change without bounds.

Those are surprising and mathematically pleasing results because, contrary to
the traditional, eventually-synchronous model, there is no resiliency gap
between the static and non-static cases (in the traditional model, resiliency
degrades from half under synchrony to one third under eventual synchrony).
Moreover, these results are new even for the special case of the Sleepy Model.

##  1\. Introduction

###  1.1. The Framework: Consensus in an Abstract Model of Permissionless
Systems

Permissionless systems are open networks in which participants, including
malicious attackers, can join and leave as they please. Sybil protection
methods such as Proof-of-Work or Proof-of-Stake can in practice maintain a
favorable ratio of honest to malicious participants. Nevertheless, algorithms
for traditional, closed-system Byzantine Agreement cannot be ported as-is to
permissionless systems because we cannot assume that honest participants
remain online or do not join late.

Solving consensus under this dynamic setting, where participation and even
failures potentially fluctuate, is an active field of research. For example,
recent work of Momose and Ren (momose_constant_2022, 20) propose a consensus
algorithm with constant expected latency in the Sleepy Model, assuming
minority corruption, availability of verifiable random functions, and
eventually-stable participation.

In this paper, we tackle the problem in a new model, the IIAB model, which is
an abstract model that captures the open nature of permissionless systems by
considering an infinite universe of processors, identified by a private/public
key pairs, under both dynamically evolving participation and dynamically
evolving failures. To get a feel for the IIAB model, consider Algorand
(chen_algorand_2019, 6). In Algorand, the system logically evolves in rounds,
and in each round a potentially different subset of the participants, called a
committee, governs the evolution the round. Even though a committee member
knows it is in the committee and can prove it to others, no processor knows a
priori who else but potentially himself is in the committee.

Analogously, in the IIAB model, we have a synchronous, round-by-round system
in which an adversary chooses a finite, non-empty, unknown committee $C_{r}$
for each round $r$ and members of the committee drive the progression of the
round by broadcasting to all, while processors outside the committee remain
silent in the round. Importantly, unlike Algorand, the cardinality of the
committee is completely unknown. Committees might never overlap, so it useless
to keep state and we assume processors are stateless and their actions in a
round only depend on the messages they receive in the round. Moreover, each
committee $C_{r}$ is partitioned into two unknown sets $G_{r}$ and $F_{r}$.
Processors in $G_{r}$ are said good and the adversary does not interfere with
them, while the adversary can impersonates all the members of $F_{r}$ for the
round. We call this model the Iterated, Infinite Authenticated Byzantine
model, abbreviated IIAB. The term iterated, as in Iterated Immediate Snapshot
(borowsky_simple_1997, 5), conveys the repetition of synchronous,
communication-closed rounds.

The IIAB model subsumes other models used in previous work on permissionless
systems (or at least idealized versions thereof). For example, the Sleepy
Model of Pass and Shi (pass_sleepy_2017, 21) can be seen as the IIAB model
under the assumption that participation is dynamic but failures are static
(i.e. $F_{r}$ remains constant). As another example, with the assumption that
$G_{r^{\prime}}\cap F_{r}=\emptyset$ whenever $r^{\prime}>r$, we can capture a
model in which malicious participants may be detected and removed but where
compromised participants cannot recover and become good again because the
attacker obtains their private keys. Thus solving consensus in the IIAB model
solve it in those models too.

Solving consensus in the IIAB model under the minority corruption assumption
is non-trivial (as should be expected since the IIAB model subsumes the Sleepy
Model). As usual for consensus, the main difficulty lies in solving the
Commit-Adopt task (gafni_round-by-round_1998, 15) (originally introduced as
Graded Broadcast by Feldman and Micali (feldman_optimal_1988, 12), and also
called Ratifier by Aspnes (aspnes_modular_2010, 2)). To illustrate the
problem, consider the Asynchronous Byzantine Agreement Model and the Grade-
Cast Algorithm of Feldman and Micali (feldman_optimal_1988, 12). This
algorithm relies on two key properties of the model:

  1. (i)

For safety, the algorithm relies on the fact that no two processors may hear
of conflicting super-majorities of participants.

  2. (ii)

For liveness, the algorithm relies on the fact that, if a processor hears of a
unanimous super-majority $M$ of the processors, then all other processors are
guaranteed to eventually hear from a non-faulty super-majority of $M$.

Unfortunately, those properties fail in the IIAB model or even in the Sleepy
Model under minority corruption and even under one-third corruption. For
example:

###### Example 0.

Under minority corruption, suppose that $F_{r}=\\{p_{1}\\}$ and
$G_{r}=\\{p_{2},p_{3}\\}$ and $p_{2}$ broadcasts $v$ while $p_{3}$ broadcasts
$v^{\prime}\neq v$. If the adversary delivers $v$ to $p_{2}$ and $v^{\prime}$
to $p_{3}$, then $p_{2}$ receives $v$ from a strict majority while $p_{3}$
receives $v^{\prime}$ from a strict majority.

###### Example 0.

Under one-third corruption, consider 7 processors $p_{1}\dots p_{7}$ with
$F_{r}=\\{p_{1},p_{2}\\}$ and $G_{r}=\\{p_{3},\dots,p_{7}\\}$. Suppose $p_{6}$
hears only from $G_{r}$ and $p_{7}$ hears from all. Moreover, suppose
$p_{3},p_{4}$ broadcast $v$ while $p_{5},p_{6},p_{7}$ broadcast
$v^{\prime}\neq v$. Then $p_{6}$ receives $v^{\prime}$ from a strict majority
of the processors it hears of. Now the adversary can deliver $v$ on behalf of
$p_{1},p_{2}$ to $p_{7}$, and $p_{7}$ receives $v\neq v^{\prime}$ from a
strict majority of the procesors it hears of.

###  1.2. Summary of the Contributions

The paper makes four main contributions.

  1. (1)

We propose the IIAB model, an abstract model that streamlines the mathematics
of permissionless systems and captures the fluctuating-participation aspect of
the Sleepy Model. Then, assuming minority corruption:

  2. (2)

We show how to implement the Commit-Adopt task in the IIAB model.

  3. (3)

We present a deterministic consensus algorithm under a bounded adversary, i.e.
an adversary such that the union of all sets $F_{r}$ is finite. This adversary
subsumes various eventual-stabilization assumptions.

  4. (4)

We present a probabilistic consensus algorithm relying on a probabilistic
leader-anointment oracle. Under reasonable assumptions about the oracle
(implementable using verifiable random functions (micali_verifiable_1999,
19)), this algorithm terminates in 20 rounds in expectation.

The algorithms of Items 2, 3, and 4 show that the respective problems are
solvable, which were open questions before this work.

###  1.3. Technical Outline

####  1.3.1. Commit-Adopt and Transformation to the No-Equivocation Model

The main difficulty in solving consensus in a distributed-computing model is
captured by the Commit-Adopt task (gafni_round-by-round_1998, 15, 12). Not
surprisingly, a solution to the Commit-Adopt (CA) task in the IIAB model is at
the heart of this paper.

In the Commit-Adopt task, processors receive values as input and each must
output either $commit(v)$ or $adopt(v)$ for some input value $v$, subject to
the Validity and Safety conditions: Validity requires that, if all inputs are
the same value $v$, then all processors output $commit(v)$. Safety requires
that, if some processor outputs $commit(v)$, then all other processors output
either $commit(v)$ or $adopt(v)$ for the same $v$.

We first reduce the problem of Commit-Adopt in the IIAB model to solving
commit-adopt in a simpler model that we call the No-Equivocation model. In the
No-Equivocation model, the adversary impersonating processor $p$ cannot send
different messages to different processors and, should the adversary
selectively deliver a message from $p$ to some processors but not others, then
it must deliver a “failure notification” (not a value) for $p$ for this round,
to all those that do not get the message. This is similar to the Identical
Byzantine model of Attiya and Welch (attiya_distributed_2004, 3).

To reduce the problem of Commit-Adopt in the IIAB model to the No-Equivocation
model, we emulate the No-Equivocation model in the IIAB model. The emulation
proceed in two successive rounds of IIAB. In the first round processors send
their input to all, and in the second processors send to all what they got in
the first round. A processor $p$ delivers a message $m$ from $q$ in the No-
Equivocation model, if and only if a) a strict majority of the processors that
$p$ hears of attest that they also got the same message $m$ from $q$ and b)
$p$ did not hear of any different message from $q$. Otherwise, $p$ delivers a
failure indication for $q$.

The idea is that if two processors $p$ and $p^{\prime}$ get two different
strict majorities, of the processors each hears of, for different messages $m$
and $m^{\prime}$ from $q$ (as is possible in the IIAB model), then both $p$
and $p^{\prime}$ hear of both $m$ and $m^{\prime}$ and thus, by condition b)
above, and deliver the failure indication for $q$. This prevents processors
from emulating the delivery of different messages from $q$ and thus
neutralizes the ability of the adversary to equivocate.

####  1.3.2. Solving Commit-Adopt in the No-Equivocation Model

To ensure the Safety property of Commit-Adopt, we must ensure that when a
processor outputs $commit(v)$, then all others have some indication that this
might have happened in order to output at least $adopt(v)$ if not $commit(v)$.

The algorithm takes two rounds of the No-Equivocation model. In a first round,
processors learn the inputs of others. In the second round, a processor
proposes to commit a value $v$ if it received $v$ from a strict majority of
the processors it heard of, otherwise it proposes no-commit. Importantly, this
ensures that if there is a value $v_{0}$ proposed to be committed (recall
processors are good) this is the only value that will be proposed.

Finally, at the end of the second round, each processor $p$ outputs:

  * •

$commit(v)$ if $p$ receives proposals to commit $v$ from a strict majority of
the processors it hears of in the second round.

  * •

$adopt(v)$ if $p$ receives $v$ strictly more often than any other value. If no
such value exists then $p$ adopts its input.

We know explain the idea behind the “strictly more often” above111This idea
originated in an unpublished manuscript of Gafni and
Zikas(gafni_zikas_unpublished, 16), under fixed participation..

Consider a processor $p$ that heard proposals to commit $v$ from a strict
majority $M_{v}$ of the set of processors $H_{p}$ that $p$ heard of. Can the
adversary make another processor $p^{\prime}$ receive $w\neq v$ at least as
often as $v$? Because there is a single value that processors might propose to
commit, at best, for each processor $q\in F_{2}\cap H_{p}$ (i.e. each
impersonated processor that $p$ heard of in round 2):

  1. (a)

the adversary delivers $\lambda$ to $p^{\prime}$ for $q$ when $p$ received a
proposal to commit $v$ from $q$, or

  2. (b)

the adversary delivers a proposal to commit $w$ to $p^{\prime}$ on behalf of
$q$ when $p$ got $\lambda$ for $q$.

Each time it does either (a) or (b), the adversary decreases by one the gap
between $v$’s count in the eyes of $p$ and $w$’s count in the eyes of
$p^{\prime}$. However, each time the adversary must spend a member of
$F_{2}\cap H_{p}$. But $F_{2}\cap H_{p}$ must consists of a minority among
$H_{p}$ by definition of the model, while $p$ received proposals for $v$ from
a strict majority of $H_{p}$. Thus $|F_{2}\cap H_{p}|<|M_{v}|$ and the
adversary can never close the gap.

####  1.3.3. Solving Consensus by Alternating a Conciliator and a Commit-Adopt

To solve consensus, we use the classic method (berman_towards_1989, 4) of
alternating between what Aspnes (aspnes_modular_2010, 2) calls a conciliator
phase and a Commit-Adopt phase. The goal of the conciliator phase is to
produce agreement eventually or with some probability, while the goal of the
Commit-Adopt phase is to detect agreement and produce a consensus decision. So
processors start with a conciliator, then take their conciliator output to the
next Commit-Adopt, then take their Commit-Adopt output to the next
conciliator, etc. At any point, if a processor outputs $commit(v)$ from a
Commit-Adopt, the processor outputs $v$ as consensus decision.

For safety, a decision produced by a processor in a commit-adopt phase must
never be contradicted later. Thus a conciliator must additionally ensure that,
should all commit or adopt the same value $v$ in the preceding Commit-Adopt
phase, all must output $v$. This is the Validity Property of conciliators.

####  1.3.4. Deterministic Consensus Under a Bounded Adversary

In Section 4.4 we solve consensus deterministically in the No-Equivocation
model by using a conciliator that is an adaptation of the synchronous
algorithm of Dolev and Strong (dolev_authenticated_1983, 11) to our setting.

The main difficulty is that, contrary to the model of the Dolev-Strong
algorithm, processors in the No-Equivocation model are stateless. We get
around this problem by having processors forward every message they receive in
every round, so as to pass on information from previous rounds up to the last
round. In the last round $N$, each processor looks at all messages it received
and extracts processor-value pairs. Similarly to the Dolev-Strong algorithm, a
processor extracts $\langle q,v\rangle$ if it can infer that $v$ was received
in a round $r<N$ by at least one processor $p$ that was good in round $r$ and
that $p$ received $v$ recursively signed by a chain of $r$ unique processors
starting from $q$. This ensures that, after a sufficient number of rounds, all
processors extract the same pairs and can pick a deterministic output.

Importantly, to satisfy the Validity property of conciliators, a processor
must output any value that is associated with a strict majority of the round-1
participants it has extracted a value for. To ensure an eventual decision, we
increase the number of rounds each time we run the conciliator. The details
are in Section 4.4.

One interesting bit is that the algorithm requires one more round than the
Dolev-Strong algorithm: if the adversary impersonates $f$ different processors
then we need $f+2$ rounds to ensure agreement.

####  1.3.5. Consensus with a Probabilistic Leader-Anointment Oracle

In Section 4.5, we assume that an oracle gives each processor the identity of
a leader. At times, processors may not all receive the same leader, and a
leader may be a processor impersonated by the adversary. However, with
probability $\alpha=1/2$, all processors obtain the same good leader.

This assumption abstracts the use of Verifiable Random Function
(micali_verifiable_1999, 19) (VRF) for leader-election: because processors
cannot lie about their VRF output and $|G_{r}|>|F_{r}|$, with probability half
a good processor has the highest output among the committee for the round and
all can see that.

To solve consensus, the idea is to rely on a good, unanimously agreed-upon
leader to bring all processors into agreement during a conciliator phase.
However, blindly trusting the leader would put the Validity Property at risk.
We must therefore check that the leader’s proposal does not contradict any
previous decision. This creates a tension between safety and liveness:
processors must ignore the leader’s proposal when they suspect that a
contradicting decision was previously made, but ignoring the leader too
liberally puts liveness at risk.

We propose a solution in three rounds. In the first two rounds, participants
do Commit-Adopt on the value associated with their inputs (i.e. a processor
that got either $commit(v)$ or $adopt(v)$ in the previous Commit-Adopt uses
value $v$). In the third round, participants broadcast the output they got in
round 2 from Commit-Adopt. At the end of the third round, a processor $p$ that
receives $commit(v)$ from a strict majority of the processors it hears of
ignores its leader and outputs $v$. Otherwise, $p$ outputs the value it
received from its leader.

This solves the problem: when all have the same good leader, all output the
same value. To see this, note that if a processor receives $commit(v)$ from a
strict majority of the processors it hears of in round three, then a good
processor output $commit(v)$ in round 2 and thus the leader must have
broadcast either $commit(v)$ or $adopt(v)$. It is also easy to see that the
Validity property of conciliators hold: if all start with the same value, all
output $commit(v)$ from the Commit-Adopt at the end of round 2, and all output
$v$ at the end of round 3.

##  2\. The IIAB Model

In the IIAB model, an infinite set $P$ of processors run a distributed
algorithm in a synchronous, message-passing system in which every processor
can send a message to every other processor.

The system executes as follows. First, each processor receives an input. Then,
execution proceeds in a sequence of communication-closed rounds numbered
1,2,3…. Each processor $p$ has a unique private/public key pair per round $r$,
noted $K_{p}^{r}$, whose public part is known to all, and signs all the
messages it sends in round $r$ using $K_{p}^{r}$. We write $K_{p}^{r}(v)$ for
the value $v$ signed with the key $K_{p}^{r}$ and we work in the standard
Dolev-Yao (dolev_security_1983, 10) model of public-key cryptography.

Each round is governed by a committee, whose members we call the participants
for the round, and consists of a broadcast phase and a receiving phase. In the
broadcast phase, committee members broadcast messages to all other processors
in $P$. Obviously a message can encapsulate a set of messages. Processor do
not maintain state; instead, the set of messages that each participant $p$
broadcasts is determined by the round number, by $p$’s initial input, and by
set of messages that $p$ received in the previous round. In the receiving
phase, each processor may receive some messages, as we describe below, and
then produce an output if it never did so before. A processor that produces an
output nevertheless continues execution.

Processors never fail but there is an adversary that controls who participates
in the committee for the round and that can impersonate some of the
participants. Each round, the adversary chooses a finite committee
$C_{r}\neq\emptyset$ and a partition $G_{r}\cup F_{r}$ of the committee into a
set of good processors $G_{r}\neq\emptyset$ and a set of impersonated
processors $F_{r}$. Only the members of $C_{r}$ participate in the broadcast
phase of round $r$. All processors participate in the receiving phase, but the
messages they receive are controlled by the adversary as follows.

The messages of processors that are good in round $r$ are received by every
processor by the end of round $r$. However, when the adversary impersonates a
processor $q$ in round $r$, the adversary obtains the private key $K_{q}^{r}$
(and only $K_{q}^{r}$), and, for each processor $p$, the adversary drops $q$’s
message to $p$ and may deliver a forged message to $p$ on behalf of $q$. Note
that we say that $p$ receives a message from $q$ when $p$ receives a message
of the form $m=K_{q}^{r}(v)$, even if $m$ was forged.

The adversary can forge arbitrary messages except that it cannot forge
signatures when it does not have the corresponding private key. The adversary
also eavesdrops on all communication. Thus, if a forged message delivered in
round $r$ contains signed data, either a) the signed data was sent in round
$r$ or before by some processor or b) the signature is produced using a
private key obtained by the adversary in round $r$ or before.

Note that, for simplicity, processors are restricted to broadcasting messages,
and thus all processors receive the same messages from $p$ in round $r$ if $p$
is good. However, when the adversary impersonates $p$, it can deliver
different messages on behalf of $p$ to different processors, including
messages that $p$ never broadcast.

#### Hearing from Processors; Receiving from Strict Majorities

Next, we proceed with some terminology and observations useful for the rest of
the paper.

###### Definition 0 (Hears Participating).

We say that $p$ hears of $q$ in round $r$ when $p$ receives some message of
the form $K_{q}^{r}(v)$ in round $r$.

###### Definition 0 (Receiving a Value from a Strict Majority).

We say that a processor $p$ receives $v$ from a strict majority in round $r$
when there is a strict majority $Q$ of the processors that $p$ hears
participating in round $r$ such that $p$ receives $K_{q}^{r}(v)$ in round $r$
from each member $q$ of $Q$.

It is importantly to note that a strict majority of the processors that $p$
hears of in round $r$ is not necessarily a strict majority of the committee.

###### Example 0.

Take 4 processors $p_{1}$ to $p_{4}$ with $G_{r}=\\{p_{1},p_{2},p_{3}\\}$ and
$F_{r}=\\{p_{4}\\}$, and $p_{1}$ hears of $\\{p_{1},p_{2},p_{3}\\}$ only in
round $r$. Then $\\{p_{1},p_{2}\\}$ is a strict majority of the processors
that $p_{1}$ hears from, but it is not a strict majority of the committee
$\\{p_{1},p_{2},p_{3},p_{4}\\}$.

Moreover, as shown in Examples 1 and 2, two processors may receive
contradictory strict majorities: $p$ may receive a strict majority for $v$ in
round $r$ while $q$ receives strict majority for $v^{\prime}\neq v$ in round
$r$ even if each participant broadcasts a single value. The only guarantee is
that if $p$ receives a strict majority for $v$ in round $r$, then a processor
that is good in round $r$ sent $v$.

###  2.1. Discussion

####  2.1.1. Solvability of Consensus

Dolev and Strong (dolev_authenticated_1983, 11) shows that consensus is
solvable in the stationary Authenticated Byzantine model with minority
corruption, while Fitzi (fitzi_generalized_2002, 14) shows minority is also
necessary. Thus, our algorithms here are of optimal corruption level.

####  2.1.2. Relationship to Practical Scenarios

The IIAB model subsumes the following interesting, practically-motivated
models:

  1. (1)

If we assume that $G_{r}$ and $F_{r}$ remain constant (i.e. $F_{r}=F_{1}$,
$G_{r}=G_{1}$, and thus $C_{r}=C_{1}$ for every $r$), and that both $G_{r}$
and $F_{r}$ are known to the processors, then we obtain the traditional
synchronous, authenticated Byzantine agreement model.

  2. (2)

If we assume that $F_{r}$ remains constant, then we obtain a round-by-round
version of the Sleepy model of Pass and Shi (pass_sleepy_2017, 21), also used
by Momose and Ren in more recent work (momose_constant_2022, 20).

  3. (3)

If we assume that $F_{r}\cap G_{r^{\prime}}=\emptyset$ when $r^{\prime}>r$, we
now encompass the case in which any processor can become faulty, faulty
processors can leave (e.g. because they are identified and removed from the
system in some way), and yet faulty processors can never become good again
(e.g. because an attacker now has their keys).

Note that in all the cases of the IIAB model above, we could let the round
keys of each processor $p$ be all the same (i.e. $K_{p}^{r}=K_{p}^{1}$ for
every $r$) because, once the adversary impersonates a processor $p$ in round
$r$, either the adversary never ceases to impersonate $p$ or $p$ stops
participating forever.

####  2.1.3. Unusual Model Features

Some features of this model are worth highlighting:

  1. (1)

Since processors are stateless, a processor can “join” a round even if it did
not receive messages in any prior rounds.

  2. (2)

Even if the adversary impersonates processor $p$ during round $r$, it cannot
send messages with the key $K_{p}^{r^{\prime}}$ for $r^{\prime}<r$ unless it
also impersonated $p$ during round $r^{\prime}$. From this perspective,
informally, the round keys provide a kind of cryptographic ratcheting (as in
e.g. the key refreshment of Di Raimondo et al. (di_raimondo_secure_2005, 9)).

  3. (3)

Round keys also provide, informally, a kind of post-compromise security (cohn-
gordon_post-compromise_2016, 7): even if the adversary impersonates processor
$p$ during round $r$, it may cease to do so in later rounds (in some sense,
$p$ recovers and is able to use a new key that the adversary does not have).

  4. (4)

Processors never fail; instead, the adversary sometimes impersonates them.

Items (2), (3), and (4) might seem unrealistic. Even if so, those properties
streamline the mathematics of the IIAB model (e.g. no need to make a
difference between who outputs after a round and who does not). Moreover,
those properties do not prevent the IIAB model from capturing interesting
practically-motivated models like the Sleepy Model (see Section 2.1.2).
Finally, advances in cryptography might enable practical realizations of (2),
(3), and (4).

###  2.2. Composing Algorithms

In later sections we construct algorithms by sequentially composing sub-
algorithms. In such cases, the sub-algorithms all use a fixed, finite number
of rounds, and thus composition only amounts to executing the algorithms in a
sequence, feeding the outputs of an algorithm as inputs to the next.

###  2.3. The No-Equivocation Model

In this section we present the No-Equivocation model, which in Section 3 we
show how to emulate in the IIAB mode. We then present algorithms in the No-
Equivocation model, which greatly simplifies the task thanks to Theorems 5 and
6.

When forging messages in the IIAB model, the adversary is restricted only by
Dolev-Yao-style assumptions about cryptographic signatures. In the No-
Equivocation model, the adversary is additionally assumed to deliver at most
one value per processor and per round and, should $p$ receive a value from $q$
while $p^{\prime}$ does not, then the adversary must deliver a failure
notification $\lambda$ for $q$ to $p^{\prime}$ (notice $q$ can receive
$\lambda$ and $p$ receives no message). Receiving $\lambda$ for $q$ counts as
hearing $q$ participating in the round.

###### Definition 0 (No-Equivocation model).

The No-Equivocation model consists of IIAB model with the following,
additionally assumptions:

  1. (1)

Processors never broadcast the special value $\lambda$ and, for every $v$, $q$
and $r$, $K_{q}^{r}(v)\neq\lambda$.

  2. (2)

In every round $r$, if a processor receives $m(\neq\lambda)$ for $q$, then
every processor receives either $m$ or $\lambda$ for $q$.

###### Definition 0 (Hears Participating (in the No-Equivocation model)).

We say that $p$ hears of $q$ in round $r$ when $p$ receives some message of
the form $K_{q}^{r}(v)$ or $\lambda$ in round $r$.

Thus, for each round and each processor $q$, all the following combinations
are possible:

  1. (1)

no processor hears of $q$ ($q$ is not in the committee, or $q\in F_{r}$ and
the adversary delivers nothing on behalf of $q$), or

  2. (2)

all receive the value $m$ that $q$ actually sent ($q\in C_{r}$, or $q\in
F_{r}$ but the adversary doesn’t tamper with its outgoing messages), or

  3. (3)

there is a value $m$ (possibly different from the value that $q$ broadcast)
such that some processors receive $m$ for $q$ and others receive $\lambda$
($q\in F_{r}$ and the adversary tampered with its outgoing broadcast), or

  4. (4)

some processors receive $\lambda$ for $q$ and some do not hear at all of $q$
(either $q$ is not in the committee and no processor hears of $q$, or $q\in
F_{r}$, which allows any combination of not-heard-of and $\lambda$).

###  2.4. Liveness Assumptions

To solve consensus, we augment the models with one of the following two
liveness assumptions.

###### Definition 0 (Bounded Adversary).

Under the Bounded-Adversary assumption, we assume that the union of all
impersonated sets is a finite set. Formally,
$F_{B}=\bigcup_{r\in\mathbf{N},r>0}F_{r}$ is a finite set.

Note that, under the Bounded-Adversary assumption, for every round $r$, we
have $F_{r}\subseteq F_{B}$. Nevertheless, both $G_{r}$ and $F_{r}$ can keep
changing forever. Also note that the Bounded Adversary subsumes adversaries
that are eventually static or eventually bounded.

###### Definition 0 (Probabilistic Leader-Anointment).

Under the Probabilistic Leader-Anointment assumption, we assume an oracle that
anoints leaders. At the beginning of each round $r$, the oracle provides each
processor $p$ with the identity of a leader $l_{p}^{r}$ among the committee
for the round. The Oracle is probabilistic in that, in each round $r$ and with
probability $\alpha=1/2$, all processors in round $r$ obtain not only the same
leader $l_{p}^{r}$, but also $l_{p}^{r}\in G_{r}$.

This leader-Anointment Oracle is just an abstraction of using verifiable
random functions (micali_verifiable_1999, 19) to elect a leader. In this case,
because in each round we have a strict majority of good participants, we
obtain $\alpha=1/2$.

##  3\. Emulating the No-Equivocation Model

In this Section, we show how to implement the No-Equivocation model defined in
Section 2.3 in the IIAB model. Then, in later sections, we give algorithms in
the No-Equivocation model, knowing we can compile them to algorithms for the
IIAB model.

Below we present the algorithm precisely along with a proof, and we refer the
reader to Section 1.3.1 for an intuitive description.

###### Algorithm 1 (Emulation of No-Equivocation Model).

We emulate a round $r$ of the No-Equivocation model using two consecutive
rounds, numbered $2r-1$ and $2r$, of the IIAB model, and we define the round
keys $KSM_{q}^{r}$ of the emulated No-Equivocation model as
$KSM_{q}^{r}=K_{q}^{2r-1}$. Each participant $p$ does the following for each
round $r$ to emulate:

  1. (1)

In round $2r-1$, for each message $m$ that $p$ must emulate the broadcasting
of in round $r$ of the No-Equivocation model, $p$ broadcasts $m$.

  2. (2)

In round $2r$, $p$ forwards all the messages it received in the first round,
and, at the end of round $2r$, for each processor $q$ such that $p$ receives
$K_{p^{\prime}}^{2r}(K_{q}^{2r-1}(v))$, for some $v$ and $p^{\prime}$, $p$
emulates the delivery of the following messages:

    1. (a)

If $p$ receives $K_{q}^{2r-1}(v)$ from a strict majority in round 2 and $p$
does not receive $K_{q}^{2r-1}(v^{\prime})$, with $v^{\prime}\neq v$, then $p$
delivers $K_{q}^{2r-1}(v)$.

    2. (b)

Else $p$ delivers $\lambda$ for $q$.

###### Theorem 1.

The No-Equivocation Emulation Algorithm is correct.

###### Proof.

By the definition of the No-Equivocation model, it suffices to show that:

  1. (i)

If $p_{1}$ delivers $m\neq\lambda$ for $q$ then each processor $p_{2}$ deliver
either $m$ or $\lambda$ for $q$.

  2. (ii)

If $q$ is a good processor in round 1, then every processor delivers $q$’s
input for $q$.

We start with Item (i). Suppose that $p_{1}$ outputs $v\neq\lambda$ for
processor $q$ and consider a processor $p_{2}$. Since $p_{1}$ outputs $v$, a
strict majority of the processors that $p_{1}$ receives a message from in
round 2 forwarded $K_{q}^{2r-1}(v)$ to $p_{1}$. Because $G_{2r}$ also is a
strict majority of the processors that $p_{1}$ receives a message from in
round 2, there is a processor $p_{1}^{\prime}$ that is good in round 2 and
that forwards $K_{q}^{2r-1}(v)$ to $p_{1}$. Thus, because messages from good
processors are received intact by all, $p_{2}$ also receives $K_{q}^{2r-1}(v)$
from $p_{1}$ in round 2.

Suppose $p_{2}$ outputs according to Item 2a and assume by contradiction that
$p_{2}$ outputs $v^{\prime}\neq v$. Then $p_{2}$ heard
$K_{q}^{2r-1}(v^{\prime})$ from each member of a strict majority in round 2.
Thus $p_{2}$ heard of $K_{q}^{2r-1}v$ and $K_{q}^{2r-1}(v^{\prime})$ from $q$,
with $v^{\prime}\neq v$, which contradicts the condition of Item 2a. Now
assume that $p_{2}$ outputs according to Item 2b. Then $p_{2}$ outputs
$\lambda$ for $q$. Thus $p_{2}$ outputs either $v$ or $\lambda$ for $q$ and we
are done with Item (i).

Next, we show Item (ii). Consider a processor $q$ that is good in round 1 with
input $v$. By definition of the model, every processor receives
$K_{q}^{2r-1}(v)$ by the end of round 1. Thus, in round 2, each good processor
forwards $K_{q}^{2r-1}(v)$ to every processor. Hence, by the end of round 2,
each processor receives $K_{q}^{2r-1}(v)$ from a strict majority in round 1.
Moreover, because the adversary cannot forge signatures with $K_{q}^{2r-1}$
(since $q$ is non-faulty in round 1), no processor receives a message
$K_{q}^{2r-1}(v^{\prime})$ where $v^{\prime}\neq v$. Therefore, every
processor outputs $v$ for $q$ according to Item 2a. ∎

##  4\. Solving Consensus in the No-Equivocation model

In this Section, we propose two algorithms for solving consensus in the No-
Equivocation model: a deterministic algorithm which assumes that the adversary
is bounded, and an algorithm that assumes a probabilistic leader-anointment
oracle but tolerates an adversary that is not bounded.

We start with Definition 1 below, which defines the Consensus Problem.

###### Definition 0.

In the Consensus Problem, every processor receives an input and must produce
an output such that:

  * Safety

No two processors produce different outputs.

  * Validity

If all processors have the same input $v$, then every processor must output
$v$.

  * Liveness

The Liveness property depends on the liveness assumptions we make:

    * Eventual

When we assume a bounded adversary, we must guarantee that, eventually, all
processors output a value.

    * Probabilistic

When we assume probabilistic leader-anointment, the conciliator phase must
guarantee that, with probability 1, all processors output.

###  4.1. Solving Consensus by Alternating Conciliation and Commit-Adopt

To solve consensus, we use the classic approach (berman_towards_1989, 4)
consisting in alternating between a conciliator phase and a Commit-Adopt
(gafni_round-by-round_1998, 15) phase (Commit-Adopt was introduced as Graded
Broadcast by Feldman and Micali (feldman_optimal_1988, 12)), starting with a
conciliator. The initial inputs of the processors are given to the first
conciliator phase, and then the outputs of every conciliator phase are given
as input to the next commit-adopt phase, and the outputs of every commit-adopt
phase are given as input to the conciliator phase (with a small caveat
described below). This result in what we call the conciliator-then-commit-
adopt sequence.

The role of the conciliator phase is to produce agreement eventually or with
some probability, depending on the liveness assumptions we make, while the
role of the commit-adopt phase is to detect a pre-existing agreement and
produce a consensus decision. Given how well-known this construction is, we
describe it informally.

A conciliator phase obeys the following specification.

###### Definition 0.

In the conciliator phase, each processor starts with an input value and must
produce an output subject to the following conditions:

  * Validity

If there is a value $v$ such that all processors have input $v$, then all
processors output $v$.

  * Liveness

The Liveness guarantee that depends on the liveness assumptions we make:

    * Bounded

When we assume a bounded adversary, the conciliator is parameterized by a
natural number $N>0$ and we must guarantee that there is a natural number $M$
determined $B$ such that, if $N\geq M$, then, in a conciliator with parameter
$N$, all processors output the same value.

    * Probabilistic

When we assume probabilistic leader-anointment, the conciliator phase must
guarantee that, for every combination of inputs and with some non-zero
probability, all processors output the same value.

Outputs of a conciliator phase are taken as input to the next commit-adopt
phase in the conciliator-then-commit-adopt sequence. A commit-adopt phase
obeys the following specification.

###### Definition 0.

In the commit-adopt task, each processor starts with an input value and must
produce an output of the form $commit(v)$ or $adopt(v)$ for some value $v$,
subject to two conditions:

  * Safety

If a processor outputs $commit(v)$ then every processor must output
$commit(v)$ or $adopt(v)$.

  * Validity

If all processors have the same input $v$, then every processor outputs
$commit(v)$.

The Validity Property ensures that a pre-exiting agreement on inputs indeed
leads to a consensus decision. The Safety Property ensures that if some
processor decides $v$, then all are in agreement on $v$ (all output
$commit(v)$ or $adopt(v)$) even if they have not detected it.

Moreover, in the conciliator-then-commit-adopt sequence, a processor that
outputs $commit(v)$ in a commit-adopt phase outputs $v$ as consensus decision.
Moreover, and this is where the caveat mentioned above appears, a processor
that outputs $commit(v)$ or $adopt(v)$ uses $v$ as input to the next
conciliator phase (i.e. it does not matter whether the processor committed or
adopted; only the value matters to the conciliator phase).

####  4.1.1. Correctness

Observer that, taken together, the Safety and Validity properties of commit-
adopt and the Validity property of the conciliator phase guarantees that, once
a processor decides (at the end of a commit-adopt phase), the decision can
never be contradicted. Moreover, the liveness property of the conciliator
phase (Eventual liveness or Probabilistic liveness, depending on the liveness
assumptions) together with the Validity property of commit-adopt guarantee the
corresponding liveness property of consensus: when the conciliator phase
creates agreement, all processors decide in the next commit-adopt phase.

###  4.2. Key Properties of the No-Equivocation model

In this Section we present Theorems 5 and 6, which capture key properties of
the No-Equivocation model that later algorithms rely on. First, in Theorem 5,
we show that no two processors can receive two different messages from the
same processor in the same round. Thus, despite unknown participation, we can
rely on a property similar to the classic quorum-intersection principle that
many classic algorithms rely on (e.g. Grade-Cast (feldman_optimal_1988, 12)).

Second, in Theorem 6, we show that if a processor receives $m$ from a strict
majority in round $r$ and if no processor broadcasts $m^{\prime}$ in round
$r$, then every processor receives $m$ strictly more often than $m^{\prime}$
in round $r$. We use this property to ensure that, should a processor act
after hearing from a unanimous strict majority, other processors have an
indication that this might have happened. This is similar to the classic
property, also used in Grade-Cast, that if a processor hears from a unanimous
super-majority, i.e. $2f+1$ out of $3f+1$, then all processors eventually hear
from $f+1$ correct processors out of those $2f+1$.

We start with Lemma 4, which is a technical lemma that we use to prove
Theorems 5 and 6.

###### Lemma 0.

Consider a round $r$. Suppose that a processor $p$ receives $v$ from each
member $q$ of a set $P_{v}$ of processors. Let $H$ be the set of processors
that $p$ hears of and let $H^{\prime}$ be the set of processors that a
processor $p^{\prime}$ hears of. Then we have:

  1. (1)

$P_{v}\subseteq H\cap H^{\prime}$, and

  2. (2)

if $P_{v}$ is a strict majority of $H$, then $P_{v}$ is a strict majority of
$H\cap H^{\prime}$.

###### Proof.

We start with Item 1. First note that $P_{v}\subseteq H$ by definition. By
definition of the No-Equivocation model, for every $q\in P_{v}$, if
$p^{\prime}$ does not receive $v$ then $p^{\prime}$ receives $\lambda$ for
$q$. Hence, $p^{\prime}$ hears of every processor $q$ such that $p$ receives
$v$ from $q$, i.e. $P_{v}\subseteq H^{\prime}$. Thus, we have $P_{v}\subseteq
H\cap H^{\prime}$.

For Item 2, note that we have just established that $P_{v}\subseteq H\cap
H^{\prime}$. Therefore, if $P_{v}$ is a strict majority of $H$, by simple
properties of sets, we get that $P_{v}$ is a strict majority among $H\cap
H^{\prime}$. ∎

###### Theorem 5.

Consider a round $r$. For every two different value $v_{1}$ and $v_{2}$, if a
processor $p$ receives $v_{1}$ from a strict majority and no processor
broadcasts both $v_{1}$ and $v_{2}$, then no processor $p^{\prime}$ receives
$v_{2}$ from a strict majority.

###### Proof.

Suppose by contradiction that $p$ receives $v_{1}$ from a strict majority
$Q_{1}$ of the processors it hears of and that $p^{\prime}$ receives $v_{2}$
from a strict majority $Q_{2}$ of the processors it hears of. Because the
adversary cannot equivocate in the No-Equivocation model, we have that $Q_{1}$
and $Q_{2}$ are disjoint.

However, by Lemma 4.2, $Q_{1}$ consists of a strict majority of $H\cap
H^{\prime}$. Similarly, $Q_{2}$ consists of a strict majority of $H\cap
H^{\prime}$. This contradicts the fact that $Q_{1}$ and $Q_{2}$ are disjoint.
∎

###### Theorem 6.

Consider a round $r$. Suppose that a processor $p$ receives $m_{1}$ from a
strict majority. Moreover, suppose that $m_{2}\neq\lambda$ and that no
processor broadcasts $m_{2}$ in round $r$. Then, for every processor
$p^{\prime}$, $p^{\prime}$ receives $m_{2}$ from strictly less processors than
it receives $m_{1}$ from.

###### Proof.

Suppose that $p$ receives $m_{1}$ from a majority $M_{1}$ of the set $H$ of
processors that $p$ hears from. Consider a processor $p^{\prime}$ and the set
$H^{\prime}$ of processors that $p^{\prime}$ hears from.

Let $M_{2}^{\prime}$ be the set of processors from which $p^{\prime}$ receives
$m_{2}$ and let $M_{1}^{\prime}$ be the set of processors from which
$p^{\prime}$ receives $m_{1}$. So we have to show that
$|M_{1}^{\prime}|-|M_{2}^{\prime}|>0$.

Let $A$ be the set of processors $q$ among $M_{1}$ such that $p^{\prime}$ does
not receive $m_{1}$ from $q$. By definition of $A$, we have $M_{1}\setminus
A\subseteq M_{1}^{\prime}$. Therefore, we have
$|M_{1}^{\prime}|\geq|M_{1}|-|A|$, thus
$|M_{1}^{\prime}|-|M_{2}^{\prime}|\geq|M_{1}|-(|A|+|M_{2}^{\prime}|)$. Hence
it suffices to show that $|M_{1}|-(|A|+|M_{2}^{\prime}|)>0$.

Because the adversary cannot equivocate, $p^{\prime}$ receives $\lambda$ from
all members of $A$. Thus, $A$ and $M_{2}^{\prime}$ are disjoint. Therefore, it
suffices to show that $|M_{1}|>|A\cup M_{2}^{\prime}|$.

Moreover, by definition of $A$, we have $A\subseteq M_{1}$ and, by property of
the No-Equivocation model, $A\subseteq F_{r}$. Thus, $A\subseteq F_{r}\cap
H\cap H^{\prime}$. Moreover, by assumption of the Lemma, no processor
broadcasts $m_{2}$. Thus $M_{2}^{\prime}\subseteq F_{r}$. Also, since
$m_{2}\neq\lambda$, by Lemma 4.1 we have that $M_{2}^{\prime}\subseteq H\cap
H^{\prime}$. Therefore we have $A\cup M_{2}^{\prime}\subseteq F_{r}\cap H\cap
H^{\prime}$.

To conclude, note that $F_{r}\cap H\cap H^{\prime}$ is not a strict majority
of $H\cap H^{\prime}$. This is because members of $G_{r}$ are heard of by all,
thus $G_{r}\subseteq H\cap H^{\prime}$, and since $G_{r}\cap F_{r}=\emptyset$
and $G_{r}$ is a strict majority of $C_{r}$, $F_{r}$ is not a strict majority
of $H\cap H^{\prime}$. Thus $A\cup M_{2}^{\prime}$ is not a strict majority of
$H\cap H^{\prime}$. But, by Lemma 4.2, $M_{1}$ is a strict majority of $H\cap
H^{\prime}$. Thus, $|M_{1}|>|A\cup M_{2}^{\prime}|$ and we are done. ∎

###  4.3. Commit-Adopt in the No-Equivocation model

In this Section, we present Algorithm 2, which implements Commit-Adopt (see
Definition 3) in the No-Equivocation model. This algorithm is the key
contribution of the paper. Its correctness leans heavily on Theorem 6 above.

###### Algorithm 2.

The algorithm takes 2 rounds. In the first round, each processor broadcasts
its input. In the second round, each participant $p$ broadcasts propose-
commit$(v)$ if it heard $v$ from a strict majority; otherwise, $p$ broadcasts
no-commit. At the end of the second round, each participant $p$ determines its
output as follows:

  1. (a)

If $p$ received propose-commit$(v)$ from a strict majority, then it outputs
$commit(v)$.

  2. (b)

Else, if $p$ received $v$ from strictly more processors than any other value,
then $p$ outputs $adopt(v)$.

  3. (c)

Else, $p$ adopts its input.

###### Theorem 7.

Algorithm 2 implements Commit-Adopt.

###### Proof.

First, we show the Safety Property of Commit-Adopt. Assume by contradiction
that a processor $p$ outputs $commit(v)$ and a processor $p^{\prime}$ outputs
$commit(v^{\prime})$ or $adopt(v^{\prime})$ and $v\neq v^{\prime}$.

Suppose that $p^{\prime}$ outputs according to Item (a) above. Then
$p^{\prime}$ receives $\textit{propose-commit}(v^{\prime})$ from a majority.
Moreover, since $p$ outputs $commit(v)$, $p$ receives propose-commit$(v)$ from
a strict majority. With $v\neq v^{\prime}$, this contradicts Theorem 5.

Now suppose that $p^{\prime}$ does not output according to Item (b) above.
Note that, if a processor broadcasts $\textit{propose-commit}(v)$, then, by
Theorem 5, no processor broadcasts $\textit{propose-commit}(w)$ for $w\neq v$.
Moreover, since $p$ outputs $commit(v)$, $p$ receives $\textit{propose-
commit}(v)$ from a strict majority in round 2. Therefore, we satisfy the
premises of Theorem 6 with $m_{1}=\textit{propose-commit}(v)$,
$m_{2}=\textit{propose-commit}(v^{\prime})$. Thus, by Theorem 6, $p^{\prime}$
receives $\textit{propose-commit}(v^{\prime})$ strictly less often than
$\textit{propose-commit}(v)$. Thus $p^{\prime}$ outputs $adopt(v)$ according
to Item (b) above. With $v\neq v^{\prime}$, this contradicts the assumption
that $p^{\prime}$ outputs $commit(v^{\prime})$ or $adopt(v^{\prime})$.

Next, we show the Validity Property of Commit-Adopt. Suppose that all
processors have input $v$. Then, since good processors are a strict majority
of the participants in the first round, every processor receives $v$ from a
strict majority in the first round. Thus, every participant broadcasts
$\textit{propose-commit}(v)$ in round 2. Similarly, every processor receives
$\textit{propose-commit}(v)$ from a strict majority in the second round. Thus,
every processor outputs $commit(v)$ and we are done. ∎

###  4.4. A Conciliator for the Bounded Adversary

In this Section we present a conciliator algorithm that is always safe but
that is live only assuming that the adversary is bounded, meaning that there
there is a bound $B$, unknown to the processors, on the cardinality of the
union of all impersonated sets (Definition 6). Equivalently, there is a finite
set $F_{B}$ with $|F_{B}|=B$ such that, for every round $r$, $F_{r}\subseteq
F_{B}$.

We implement a conciliator as defined in Definition 2 with the Eventual
Liveness property. To do so, we adapt the synchronous, authenticated Byzantine
Agreement algorithm of Dolev and Strong (dolev_authenticated_1983, 11) to our
setting.

We achieve the Eventual Liveness property by running the Dolev-Strong
algorithm after the stabilization round and for a sufficient number of rounds.
We make sure this eventually happens by strictly increasing the number of
rounds of the Dolev-Strong algorithm each time it appears in the conciliator-
then-commit-adopt sequence. Moreover, we specify the output rule of the Dolev-
Strong algorithm in order to satisfy the Safety property of the conciliator
specification: processor output the majority value if there is one. Finally,
we adapt the algorithm to our stateless setting by having processors sign and
forward all the messages they receive and only extract and compute their
output value in the last round. Interestingly, without state, we need
$|F_{B}|+2$ rounds while the original Dolev-Strong algorithm needs $f+1$
rounds where $f$ is the number of failures.

To define the algorithm, we first need new notions related to sequences of
signatures.

###### Definition 0.

We say that $s$ is a distinct sequence of signatures on a value $v$ (initiated
by $q_{1}$) if $s$ is of the form
$s=K_{q_{n}}^{n}(K_{q_{n-1}}^{n-1}(...K_{q_{1}}^{1}(v)))$ where, for every
$i,j\in 1..n$, $q_{i}\neq q_{j}$ if $i\neq j$.

###### Definition 0.

We say that a processor $p$ hears of
$s^{\prime}=K_{q_{k}}^{k}(K_{q_{k-1}}^{k-1}(...K_{q_{1}}^{1}(v)))$ in a round
$n$ if $s^{\prime}$ is a distinct sequence of signatures and $p$ receives
$s=K_{q_{n}}^{n}(K_{q_{n-1}}^{n-1}(...s^{\prime}))$ in round $n$ (note $s$
itself does not have to be distinct).

###### Definition 0.

We say that a processor $p$ in round $n$ hears of $q$ participating in a round
$k$, with $1\leq k\leq n$, when $p$ receives
$s=K_{q_{n}}^{n}(K_{q_{n-1}}^{n-1}(...K_{q_{1}}^{1}(v)))$ (not necessarily
unique) in round $n$ and $q=q_{k}$.

###### Algorithm 3.

The algorithm is parameterize by a natural number $N>0$ and runs for $N$
rounds. Each participant $p$ does the following:

  1. (1)

In the first round, $p$ signs and broadcasts its input value.

  2. (2)

In each round $r$, $1\leq r\leq N$, $p$ signs and forwards every message it
receives in the previous round.

  3. (3)

At the end of the last round, $p$ outputs as follows. Consider the set $S$ of
distinct sequences of signatures that $p$ hears of in round $N$. If there is
$k\in 1..N$ and a strict majority $Q$ of the processors that $p$ hears of
participating in round $k$ such that $p$ hears
$K_{q_{k}}^{k}(K_{q_{k-1}}^{k-1}(...K_{q_{1}}^{1}(v)))\in S$ for each member
$q_{k}$ of $Q$, then we say that $p$ extracts $\langle q_{1},v\rangle$.

    1. (a)

If $p$ extracted $\langle q,v\rangle$ from a strict majority of the processors
$q$ it has extracted a value for, then $q$ outputs $v$.

    2. (b)

Else, $p$ outputs the smallest valid value that it receives.

###### Theorem 11.

Algorithm 3 implements a conciliator with the Eventual Liveness guarantee.

###### Proof.

Recall the specification of a conciliator with the Eventual Liveness guarantee
in Definition 2. We must show the Validity Property and the Eventual Liveness
Property.

Let us start with the Validity Property. Assume that all processors have the
same input $v$. The, at the end of round $N$, every processor extracts
$\langle q,v\rangle$ for every processor $q\in G_{1}$. Moreover, for every
$q\in G_{1}$, $q$ never broadcasts $K_{q}^{1}(v^{\prime})$ with
$v^{\prime}\neq v$. Thus, $v$ is unique such that every processor $p$ extracts
$\langle q,v\rangle$ for a strict majority of the processors $q$ that $p$
hears participating in round 1. Therefore, every processor outputs $\langle
q,v\rangle$ according to Item 3a and we are done.

For the Eventual Liveness Property, it suffices to show that, if $N>B+1$, then
every processor extracts the same processor-value pairs. Since processor pick
their output as a function of the set of extracted pairs, we have agreement.
So, suppose that $N>B+1$. By definition of the algorithm, it suffices to show
that, for every two processors $p_{1}$ and $p_{2}$, if $p_{1}$ extracts
$\langle q,v\rangle$ then $p_{2}$ extracts $\langle q,v\rangle$.

Suppose that $p_{1}$ extracts $\langle q,v\rangle$. Then, by definition, there
is $k\in 1..N$ and a strict majority $Q$ of the processors that $p$ hears of
participating in round $k$ such that $p_{1}$ hears
$s_{q_{k}}=K_{q_{k}}^{k}(K_{q_{k-1}}^{k-1}(...K_{q_{1}}^{1}(v)))\in S$ for
each member $q_{k}$ of $Q$. Note that, since $Q$ is a strict majority of the
processors that $p$ hears participating in round $k$, a) a good processor
$q_{k}$ broadcast $K_{q_{k}}^{k}(K_{q_{k-1}}^{k-1}(...K_{q_{1}}^{1}(v)))$ with
$q_{1}=q$. Consider the following two exhaustive cases.

First, suppose $k<N$. By a) above, every processor receives
$K_{q_{k}}^{k}(K_{q_{k-1}}^{k-1}(...K_{q_{1}}^{1}(v)))$ by the end of round
$k$. Thus, by the end of round $k+1\leq N$, every processors receives
$K_{q_{k+1}}(K_{q_{k}}^{k}(K_{q_{k-1}}^{k-1}(...K_{q_{1}}^{1}(v))))$. This
means that, at the end of round $N$, every processor, including $p_{2}$,
extracts $\langle q,v\rangle$.

Second, suppose that $k=N>B+1$. Then, because $s$ is distinct and the
adversary is restricted to impersonating processors in a $F_{B}$ with
$F_{B}=|B|$, there is a processor $q_{j}$ that is good in round $j$, $1\leq
j<k$, such that $q_{j}$ broadcasts
$K_{q_{j}}^{j}(K_{q_{j-1}}^{j-1}(...K_{q_{1}}^{1}(v)))$. Thus, every
processors receive $K_{q_{j}}^{j}(K_{q_{j-1}}^{j-1}(...K_{q_{1}}^{1}(v)))$ by
the end of round $j<k$. So, every processor $p$ receives
$K_{q_{j+1}^{j+1}}(K_{q_{j}}^{j}(K_{q_{j-1}}^{j-1}(...K_{q_{1}}^{1}(v))))$
from each member $q_{j+1}$ of a set $Q$ consisting of a strict majority of the
processors that $p$ hears of participating in round $j+1\leq k=N$. Thus, every
processor, including $p_{2}$, extracts $\langle q,v\rangle$, and we are done.
∎

Finally, note that this algorithm sends exponentially many messages in the
number of rounds. We can improve this if we restrict the value domain to a
binary value domain. In this case, processors can limit their forwarding to
only two chains per initiator, which means that the algorithm now sends a
linear number of messages in the number of rounds and quadratic in the number
of participants.

###  4.5. A Conciliator Relying on Probabilistic Leader-Anointment

In this Section, we present a conciliator algorithm in the No-Equivocation
model that satisfies the Probabilistic progress guarantee of Definition 2
under the Probabilistic Leader-Anointment assumption (see Definition 7). Thus,
we assume that, at the beginning of each round $r$, an oracle provides each
processor $p$ with the identity of a leader $l_{p}^{r}$ and that, with non-
zero probability $\alpha$, all processors in round $r$ obtain the same good
leader.

The idea is to rely on a good, unanimously agreed-upon leader to bring all
processors into agreement. However, blindly trusting the leader would put the
Validity Property at risk. Therefore, we first use Commit-Adopt to make sure
that, if all get the same input $v$, all commit $v$. Commit-Adopt takes two
rounds. Finally, in a third round, each participant broadcasts its Commit-
Adopt output, and it ignores its leader if and only if it received $commit(v)$
from a strict majority in round 3.

###### Algorithm 4 (Conciliator under Probabilistic Leader-Anointment).

The algorithm takes 3 rounds of the No-Equivocation model. In the first two
rounds, participants do Commit-Adopt according to Algorithm 2. Then, in the
third round, each participant $p$ broadcasts its Commit-Adopt output and then
outputs as follows:

  1. (1)

If $p$ received $commit(v)$ from a strict majority, then $p$ outputs $v$.

  2. (2)

Else, if $p$ received $commit(v)$ or $adopt(v)$ from its leader $l_{p}^{3}$,
then $p$ outputs $v$.

  3. (3)

Else $p$ outputs its input.

###### Theorem 12.

Assuming the probabilistic leader-anointment oracle of Definition 7, Algorithm
4 implements the conciliator specification with the Probabilistic progress
guarantee.

###### Proof.

We must show the Validity and Probabilistic Liveness of Definition 2.

For Validity, if all start with $v$ then, by property of Commit-Adopt, all
output $commit(v)$ from the Commit-Adopt at the end of round 2 and thus
broadcast $commit(v)$, then all receive a strict majority of $commit(v)$ by
the end of round 3, and thus all output $v$ according to Item 1.

For the Liveness property, it suffices to show that if all processors obtain
the same good leader $l\in G_{2}$ in round 2, then all output the same value.
So, suppose that all processors obtain the same good leader $l$ in round 2.
First note that, since $l$ is a good processor, every processor receives $l$’s
suggestion and no processor outputs according to Item 3. Thus, it suffices to
consider the following two cases:  (a) $p_{1}$and $p_{2}$ output according to
Item 1.  (b) $p_{1}$outputs according to Item 1 and $p_{2}$ outputs according
to Item 2.

First, assume that both $p_{1}$ and $p_{2}$ output according to Item 1 and
assume by contradiction that $p_{1}$ outputs $v_{1}$ and $p_{2}$ outputs
$v_{2}\neq v_{1}$. Then, $p_{1}$ received $commit(v_{1})$ from a strict
majority in round 3 and $p_{2}$ received $commit(v_{2})$ from a strict
majority in round 3. Since no processor broadcasts both $commit(v_{1})$ and
$commit(v2)$, with Theorem 5, we get a contradiction.

Second, assume that $p_{1}$ outputs according to Item 1 and $p_{2}$ outputs
according to Item 2. Then $p_{1}$ receives $commit(v_{1})$ from a strict
majority in round 3. Thus, at least one good participant $p\in G_{3}$
broadcast $commit(v_{1})$ in round 3, and thus all processors output either
$commit(v_{1})$ or $adopt(v_{1})$ from the Commit-Adopt at the end of round 2.
Thus $p_{2}$ receives either $commit(v_{1})$ or $adopt(v_{1})$ from its leader
and outputs $v_{1}$. ∎

###### Lemma 0.

If the parameter $\alpha$ of the probabilistic leader-anointment oracle is
equal to $1/2$, then every processor in the conciliator-then-commit-adopt
sequence produces a consensus output after 20 rounds of the IIAB model, in
expectation.

###### Proof.

By property of the Algorithm 4, all processors terminate if the leader gives
the same good leader to all processors. By assumption, this happens with
probability $\alpha=1/2$. Thus, in expectation, we need to draw 2 leaders
before all processors output. Committing after the second conciliator takes 2
conciliators and 2 Commit-Adopts. That amounts to 10 rounds in the No-
Equivocation model, i.e. 20 IIAB rounds. ∎

##  5\. Related Work

In order to simplify reasoning about distributed-computing problems, a number
of earlier works use the notion of a message adversary that controls
communication while processors themselves never fail. Afek and Gafni
(afek_simple_2015, 1) consider a synchronous system with omissions, where the
omissions of outgoing messages are preformed by a Message Adversary. In this
model a processor is never faulty and obeys the algorithm following the
messages it receives. Thus, when solving a task in the model, all processors
are obliged to output, as opposed to only correct ones in failure-based
models. Using the Message Adversary model, Afek and Gafni greatly simplify the
proof of the characterization of wait-free computation.

We adopt a similar setting in the current paper: a processor never fails, but
a malicious adversary might temporarily impersonate it and send messages on
its behalf. Santoro and Widmayer (santoro_agreement_2007, 22) also study
consensus under benign, transient communication failures which resemble the
Message Adversary of Afek and Gafni.

In an unpublished manuscript written in 2019, Gafni and Zikas
(gafni_zikas_unpublished, 16) introduce the Mobile Message Adversary in the
authenticated Byzantine, synchronous setting with fixed, known participation.
They show how to solve Commit-Adopt in the resulting model, and the Commit-
Adopt algorithm we present (Algorithm 2) borrows the main algorithmic idea.
The introduction of unknown participation in the IIAB model however
significantly complicates the matter. Gafni and Zikas also present a flawed
consensus algorithm for their model (the flaw is that their conciliator does
not satisfy the Validity property of Definition 2).

Algorand (chen_algorand_2019, 6) proceeds from round to round choosing an
authenticated committee for the round. A committee member does not a-priori
know the other committee members, but nevertheless when getting a message from
a committee member it can verify its eligibility to be on the committee.
Proof-of-Stake ensures, probabilistically, that the committee consists of a
1/3 fraction of honest members. The main difference with out setting is that
processors know in Algorand know, even if only in expectation, the cardinality
of the committee. This has profound algorithmic implications: in Algorand a
processor can check with high probability whether some fraction $f$ of the
committee supports some value, whereas in the IIAB model processors can only
check whether a fraction $f$ _of the processors they hear of_ support some
value.

Pass and Shi (pass_sleepy_2017, 21) propose the Sleepy Model, where processor
wake up to participate, and may go back to sleep. Thus like Algorand
participation is not known a-priori, but unlike Algorand how many participate
is unknown (even in expectation). They consider minority corruption and employ
a longest-chain mechanism achieving probabilistic safety. The Snow-White paper
(daian_snow_2019, 8) extends the work of Pass and Shi to the Proof-of-Stake
setting and proposes practical algorithms.

Monmose and Ren (momose_constant_2022, 20) achieve deterministic safety in the
Sleepy Model, but liveness is probabilistic and requires eventually stable
participation. Malkhi, Momose, and Ren (malkhi_byzantine_2022, 17) remove the
above stability requirement, at the expense of reducing corruption to at most
1/3. In a more recent follow-up in an online blog, Malki, Momose, and Ren
(research_minority_2022, 18) claim to increase corruption to at most 1/2.

###  5.1. Conclusion

Like all good basic research, the unpublished 2020 write-up of Gafni and
Zikas(gafni_zikas_unpublished, 16) (privately made available to us), which was
considered by all who knew about it elegant but esoteric, is found 3 years
later to contain an algorithmic idea for Commit-Adopt that is relevant to
permissionless systems.

In this paper, we build on the Gafni and Zikas work to solve consensus in a
general model of permissionless systems called the IIAB model. We solve
consensus deterministically under a bounded adversary (which subsumes
eventually stable participation), and probabilistically, even under an
unbounded adversary, but relying on a leader-anointment oracle that can be
implemented using verifiable random functions.

We present structured modular algorithms without trying to reduce message or
round complexity. This leads to remarkably simple algorithms ready to be
taught in class tomorrow. In the time-honored tradition of separation of
concerns: First investigate feasibility at the utmost level of clarity; only
then optimize for efficiency. The latter is left to future work.

Last but not least: The remarkable FLP result (fischer_impossibility_1985, 13)
showed that consensus can be prevented if $n$ processors are required to
proceed each missing only some single processor in a round. Santoro and
Widmayer (santoro_agreement_2007, 22) generalized FLP to a synchronous system
with a single processor omission at a round, but the omission changes from
round to round.

These two settings give rise to two separate notions of eventual synchrony
(the latter better called eventual stationarity). First, eventual in the sense
of FLP, i.e. asynchronous then eventually synchronous. Second, in the sense of
Santoro and Widmayer, i.e. synchronous but mobile faults then eventually the
faults become stationary (limited support set).

The former notion of eventual exhibits mathematical ugliness – Authenticated
Byzantine can synchronously solve consensus with minority faulty, but the
eventual version requires a bound of one third. There is no such gap from half
to one third in the eventually stationary notion: As we have shown, the IIAB
model solves consensus under eventually stationary for minority corruption.

We conclude by asserting that Distributed Computing is mathematically clean,
if we dispense with the construct of “wait for a number of processors” but
rather use “wait some amount of time”. The latter can capture the former, in
the eventual sense, if waiting for longer and longer periods.

## References

  * (1) Yehuda Afek and Eli Gafni  “A simple characterization of asynchronous computations”  In _Theoretical Computer Science_ 561, Part B, Special Issue on Distributed Computing and Networking, 2015, pp. 88–95  DOI: 10.1016/j.tcs.2014.07.022
  * (2) James Aspnes  “A modular approach to shared-memory consensus, with applications to the probabilistic-write model”  In _Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing_ , PODC ’10  New York, NY, USA: Association for Computing Machinery, 2010, pp. 460–467  DOI: 10.1145/1835698.1835802
  * (3) Hagit Attiya and Jennifer Welch  “Distributed computing: fundamentals, simulations, and advanced topics”  John Wiley & Sons, 2004
  * (4) Piotr Berman, Juan A. Garay and Kenneth J. Perry  “Towards optimal distributed consensus”  In _FOCS_ 89, 1989, pp. 410–415
  * (5) Elizabeth Borowsky and Eli Gafni  “A Simple Algorithmically Reasoned Characterization of Wait-free Computation (Extended Abstract)”  In _Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing_ , PODC ’97  ACM, 1997, pp. 189–198  DOI: 10.1145/259380.259439
  * (6) Jing Chen and Silvio Micali  “Algorand: A secure and efficient distributed ledger”  In _Theoretical Computer Science_ 777, In memory of Maurice Nivat, a founding father of Theoretical Computer Science - Part I, 2019, pp. 155–183  DOI: 10.1016/j.tcs.2019.02.001
  * (7) Katriel Cohn-Gordon, Cas Cremers and Luke Garratt  “On post-compromise security”  In _2016 IEEE 29th Computer Security Foundations Symposium (CSF)_ IEEE, 2016, pp. 164–178
  * (8) Phil Daian, Rafael Pass and Elaine Shi  “Snow White: Robustly Reconfigurable Consensus and Applications to Provably Secure Proof of Stake”  In _Financial Cryptography and Data Security_ , Lecture Notes in Computer Science  Cham: Springer International Publishing, 2019, pp. 23–41  DOI: 10.1007/978-3-030-32101-7˙2
  * (9) Mario Di Raimondo, Rosario Gennaro and Hugo Krawczyk  “Secure off-the-record messaging”  In _Proceedings of the 2005 ACM Workshop on Privacy in the Electronic Society_ , 2005, pp. 81–89
  * (10) D. Dolev and A. Yao  “On the security of public key protocols” Conference Name: IEEE Transactions on Information Theory  In _IEEE Transactions on Information Theory_ 29.2, 1983, pp. 198–208  DOI: 10.1109/TIT.1983.1056650
  * (11) Danny Dolev and H. Strong  “Authenticated algorithms for Byzantine agreement”  In _SIAM Journal on Computing_ 12.4, 1983, pp. 656–666
  * (12) Paul Feldman and Silvio Micali  “Optimal algorithms for Byzantine agreement”  In _Proceedings of the twentieth annual ACM symposium on Theory of computing_ , STOC ’88  New York, NY, USA: Association for Computing Machinery, 1988, pp. 148–161  DOI: 10.1145/62212.62225
  * (13) Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson  “Impossibility of Distributed Consensus with One Faulty Process” tex.ids= fischer_impossibility_1985-1  In _Journal of the ACM_ 32.2, 1985, pp. 374–382  DOI: 10.1145/3149.214121
  * (14) Matthias Fitzi  “Generalized communication and security models in Byzantine agreement”, 2002
  * (15) Eli Gafni  “Round-by-round Fault Detectors (Extended Abstract): Unifying Synchrony and Asynchrony”  In _Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing_ , PODC ’98  New York, NY, USA: ACM, 1998, pp. 143–152  DOI: 10.1145/277697.277724
  * (16) Eli Gafni and Vassilis Zikas  “Synchrony/Asynchrony vs. Stationary/Mobile? The Latter is Superior…in Theory”, 2020  URL: https://www.dropbox.com/s/9lvbvar738yr9ni/Gafni%20-%20SynchronyAsynchrony%20vs%20Stationary.pdf?dl=0
  * (17) Dahlia Malkhi, Atsuki Momose and Ling Ren  “Byzantine Consensus under Fully Fluctuating Participation” Report Number: 1448, 2022  URL: https://eprint.iacr.org/2022/1448
  * (18) Dahlia Malkhi, Atsuki Momose and Ling Ren  “Minority Corruption Resilience in Byzantine Generals with Unknown and Fluctuating Participation”, 2022  URL: https://blog.chain.link/minority-corruption-resilience-in-byzantine-generals-with-unknown-and-fluctuating-participation/
  * (19) S. Micali, M. Rabin and S. Vadhan  “Verifiable random functions” ISSN: 0272-5428  In _40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)_ , 1999, pp. 120–130  DOI: 10.1109/SFFCS.1999.814584
  * (20) Atsuki Momose and Ling Ren  “Constant Latency in Sleepy Consensus”  In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’22  New York, NY, USA: Association for Computing Machinery, 2022, pp. 2295–2308  DOI: 10.1145/3548606.3559347
  * (21) Rafael Pass and Elaine Shi  “The Sleepy Model of Consensus”  In _Advances in Cryptology – ASIACRYPT 2017_ , Lecture Notes in Computer Science  Cham: Springer International Publishing, 2017, pp. 380–409  DOI: 10.1007/978-3-319-70697-9˙14
  * (22) Nicola Santoro and Peter Widmayer  “Agreement in synchronous networks with ubiquitous faults”  In _Theoretical Computer Science_ 384.2, Structural Information and Communication Complexity (SIROCCO 2005), 2007, pp. 232–249  DOI: 10.1016/j.tcs.2007.04.036


# Optical interferometry in the presence of large phase diffusion

Marco G. Genoni  QOLS, Blackett Laboratory, Imperial College London, London
SW7 2BW, UK  Stefano Olivares  Dipartimento di Fisica, Università degli Studi
di Milano, I-20133 Milano, Italy  CNISM, UdR Milano Statale, I-20133 Milano,
Italy.  Dipartimento di Fisica, Università degli Studi di Trieste, I-34151
Trieste, Italy  Davide Brivio  Dipartimento di Fisica, Università degli Studi
di Milano, I-20133 Milano, Italy  Simone Cialdi  Dipartimento di Fisica,
Università degli Studi di Milano, I-20133 Milano, Italy  INFN, Sezione di
Milano, I-20133 Milano, Italia  Daniele Cipriani  Dipartimento di Fisica,
Università degli Studi di Milano, I-20133 Milano, Italy  Alberto Santamato
Dipartimento di Fisica, Università degli Studi di Milano, I-20133 Milano,
Italy  Stefano Vezzoli  Dipartimento di Fisica, Università degli Studi di
Milano, I-20133 Milano, Italy  Matteo G. A. Paris
<EMAIL_ADDRESS>Dipartimento di Fisica, Università degli Studi di
Milano, I-20133 Milano, Italy  CNISM, UdR Milano Statale, I-20133 Milano,
Italy.

###### Abstract

Phase diffusion represents a crucial obstacle towards the implementation of
high precision interferometric measurements and phase shift based
communication channels. Here we present a nearly optimal interferometric
scheme based on homodyne detection and coherent signals for the detection of a
phase shift in the presence of large phase diffusion. In our scheme the
ultimate bound to interferometric sensitivity is achieved already for a small
number of measurements, of the order of hundreds, without using nonclassical
light.

###### pacs:

07.60.Ly, 42.87.Bg

##  I Introduction

Optical interferometry represents a high accurate measurement scheme with wide
applications in many fields of science and technology Cav81 ; r1 ; r2 ; r3 ;
r4 . Besides, the precise estimation of an optical phase shift is relevant for
optical communication schemes where information is encoded in the phase of
travelling pulses. Several experimental protocols have been proposed and
demonstrated to estimate the value of the optical phase Armen02 ; Mitch04 ;
Nag07 ; Res07 ; Hig07 ; Hig09  and showing the possibility to attain the so-
called Heisenberg limit Z92 ; Sam92 ; Lane93 ; San95 ; Eck06 ; Giov046 ; Guo08
; Sme08 ; Gro11 ; Hay11 ; Bra11 . Recent developments also revealed the
potential advantages of nonlinear interactions Boi08 . However, in realistic
conditions, one has to retrieve phase information that has been unavoidably
degraded by different sources of noise, which have to be taken into account in
order to evaluate the interferometric precision Gio11 . The effects of
imperfect photodetection in the measurement stage, or the presence of
amplitude noise in the interferometric arms have been extensively studied
Par95 ; Cam03 ; Huv08 ; Coo10 ; BanPhNat ; BanPhPRL ; Cab10 ; Joo11 ; DurkinPh
; Bah11 ; Dat11 . Only recently, the role of phase-diffusive noise in
interferometry have been theoretically investigated for optical polarization
qubit Bri10 ; Ber10 ; tes:11 , condensate systems BEC1 ; BEC2 , Bose-Josephson
junctions Fer10 , and Gaussian states of light Gen11 . As a matter of fact,
phase-diffusive noise is the most detrimental for interferometry and any
signal that is unaffected by phase-diffusion, is also invariant under a phase
shift, and thus totally useless for phase estimation.

In this paper, we present an experimental interferometric scheme where phase
diffusion may be inserted in a controlled way, and demonstrate that homodyne
detection and coherent signals are nearly optimal for the detection of a phase
shift in the presence of large phase diffusion. Indeed, while in ideal
conditions squeezed vacuum is the most sensitive Gaussian probe state for a
given average photon number Mon06 , for large phase-diffusive noise, coherent
states become the optimal choice, outperforming squeezed states Gen11 . In our
scheme the ultimate bound to interferometric sensitivity, as dictated by the
Cramér-Rao (CR) theorem, is achieved already for a small number of repeated
measurements, of the order of hundreds, using Bayesian inference on homodyne
data and without the need of nonclassical light.

The paper is structured as follows: In Section II we describe the evolution of
a light beam in a phase diffusing environment as well as the bound to
interferometric precision in the presence of phase noise. In Section III we
describe our experimental apparatus, whereas the experimental results are
reported and discussed in Section IV. Section V closes the paper with some
concluding remarks.

##  II Interferometry in the presence of phase diffusion

The evolution of a light beam in a phase diffusing environment is described by
the master equation

$\dot{\varrho}=\Gamma\mathcal{L}[a^{{\dagger}}a]\varrho\,,$

where $\mathcal{L}[O]\varrho=2O\varrho O^{\dagger}-O^{\dagger}O\varrho-\varrho
O^{\dagger}O$ and $\Gamma$ is the phase damping rate. An initial state
$\varrho_{0}$ evolves as

$\varrho_{t}=\mathcal{N}_{\Delta}(\varrho_{0})=\sum_{n,m}e^{-\Delta^{2}(n-m)^{2}}\varrho_{n,m}|n\rangle\langle
m|\,,$

where $\Delta\equiv\Gamma t$, and $\varrho_{n,m}=\langle
n|\varrho_{0}|m\rangle$. The diagonal elements are left unchanged, in fact
energy is conserved, whereas the off-diagonal ones are progressively
destroyed, together with the phase information carried by the state. Phase
diffusion corresponds to the application of a random, zero-mean Gaussian-
distributed phase shift, i.e.,

$\displaystyle\varrho_{t}=\int_{\mathbbm{R}}\\!d\beta\,g(\beta|\Delta)U_{\beta}\varrho_{0}U_{\beta}^{{\dagger}}\qquad
g(\beta|\Delta)=\frac{e^{-\beta^{2}/(4\Delta^{2})}}{\sqrt{4\pi\Delta^{2}}}$
(1)

where $U_{\beta}=\exp\\{-i\beta(a^{\dagger}a)\\}$ is the phase shift operator.

We assume that the phase noise occurs between the application of the phase
shift and the detection of the signal, and consider the estimation of a phase
shift applied to a single-mode coherent state. Homodyne detection is then
performed on the output state

$\varrho_{\Delta,\alpha}(\phi)=\mathcal{N}_{\Delta}(U_{\phi}|\alpha\rangle\langle\alpha|U_{\phi}^{\dagger})\,,$

and the value of the unknown phase shift $\phi$ is inferred using Bayesian
estimation applied to homodyne data. Notice, however, that since the phase
noise map and the phase shift operation commute, our results are valid also
when the phase shift is applied to an already phase-diffused coherent state.
The precision of the above procedure is then compared with the benchmarks
given by i) the quantum CR bound for coherent states and any quantum limited
kind of measurement, ii) the ultimate precision achievable with optimized
Gaussian states, i.e., the quantum CR bound for general Gaussian signals,
where, e.g., we allow for squeezing.

###  II.1 Interferometric precision in the presence of phase noise

The quantum CR bound Mal9X ; BC9X ; Bro9X ; LQE ; Dav11  is obtained starting
from the Born rule $p(x|\phi)=\hbox{Tr}[\Pi_{x}\varrho_{\phi}]$ where
$\\{\Pi_{x}\\}$ is the operator-valued measure describing the measurement and
$\varrho_{\phi}$ the density operator of the family of phase-shifted states
under investigation. Upon introducing the (symmetric) logarithmic derivative
$L_{\phi}$ as the operator satisfying

$2\partial_{\phi}\varrho_{\phi}=L_{\phi}\varrho_{\phi}+\varrho_{\phi}L_{\phi}\,,$

one proves that the ultimate limit to precision (independently on the
measurement used) is given by the quantum CR bound

$\textrm{Var}(\phi)\geq[MH(\phi)]^{-1}\,,$

where $H(\phi)=\hbox{Tr}[\varrho_{\phi}\,L_{\phi}^{2}]$ is the quantum Fisher
information (QFI). The ultimate sensitivity of an interferometer thus depends
on the family of signals used to probe the phase shift and thus, as said
above, we are going to compare the precision of our interferometer with the
maximum achievable with coherent states, and with the ultimate precision
achievable with optimized Gaussian states (for more details about the
derivation of the corresponding quantum CR bounds see Gen11 ).

Homodyne detection measures the field quadrature

$x_{\theta}=\frac{1}{2}(ae^{-i\theta}+a^{\dagger}e^{i\theta})\,,$

where $\theta=\arg\alpha+\pi/2$ is set to the optimal value to detect the
imposed phase shift. The likelihood of a set of homodyne data

$X=\\{x_{1},x_{2},\ldots,x_{M}\\}\,,$

is the overall probability of the sample given the unknown phase $\phi$, i.e.,

$L(X|\phi)=\prod_{k=1}^{M}p(x_{k}|\phi)\,,$

where

$\displaystyle
p(x|\phi)=\frac{e^{-2x^{2}}}{\pi\Delta}\int_{\mathbbm{R}}\\!\\!d\beta\>e^{-\frac{\beta^{2}}{2\Delta^{2}}+4\alpha
x\cos(\beta+\phi)-2\alpha^{2}\cos^{2}(\beta+\phi)}\,.$

Assuming that no a priori information is available on the value of the phase
shift (i.e., uniform prior), and using the Bayes theorem, one can write the a
posteriori probability

$\displaystyle P(\phi|X)=\frac{1}{\cal N}\,L(X|\phi)\qquad{\cal
N}=\int_{\Phi}d\phi\,L(\phi|X)\,,$ (2)

$\Phi=[0,\pi]$ being the parameter space. The probability $P(\phi|X)$ is the
expected distribution of $\phi$ given the data sample $X$. The Bayesian
estimator $\phi_{\rm B}$ is the mean of the a posteriori distribution, whereas
the sensitivity of the overall procedure corresponds to its variance

${\rm Var}[\phi_{\rm B}]=\int_{\Phi}d\phi\,(\phi-\phi_{\rm
B})^{2}\,P(\phi|X)\,.$

Bayesian estimators are known to be asymptotically unbiased and optimal,
namely, they allow one to achieve the CR bound as the size of the data sample
increases H9X ; O09 . On the other hand, the number of data needed to achieve
the asymptotic region may depend on the specific implementation Bar00 . In the
following we will experimentally show that our setup achieves optimal
estimation already after collecting few hundreds of measurements.

##  III Experimental apparatus

A schematic diagram of the interferometer is reported in Fig. 1. The principal
radiation source is provided by a He:Ne laser (12 mW, 633 nm) shot-noise
limited above 2 MHz. The laser emits a linearly polarized beam in a TEM00
mode. The beam is splitted into two parts of variable relative intensity by a
combination of a halfwave plate (HWP) and a polarizing beam splitter (PBS).
The strongest part is sent directly to the homodyne detector where it acts as
the local oscillator, whereas the ramaining part is used to encode the signal
and will undergo the homodyne detection. The optical paths travelled by the
local oscillator and the signal beams are carefully adjusted to obtain a
visibility typically above 90% measured at one of the homodyne output ports.
The signal is amplitude modulated at 4 MHz with a defined modulation depth to
control the average number of photons in the generate state.

The amplitude modulation system consist of a KDP non-linear crystal with the
$xy$ axes at 45∘, and a PBS. The modulation is applied at the KDP crystal by
means a waveform generator Rohde & Schwarz and a power amplifier Mini-Circuits
ZHL-32A. The modulation depth is imposed at the proper level by a computer
that sends a costant voltage to a mixer (M1) located between the waveform
generator and the power amplifier. One of the mirrors in the signal path is
piezo mounted to obtain a variable phase difference between the two beams. The
piezo is preloaded and its resonance frequency is 13.5 kHz.

The phase difference is controlled by the computer after a calibration stage.
The computer sends a voltage signal between 0 and 10 V that corresponds at the
phase diffusion with a frequency of 5 kHz to a power amplifier based on LM675
integrated circuit that is able to drive the piezo at this frequency. With
this system it is possibile to generate any kind of phase modulation.

Figure 1: (color online). Schematic diagram of the experimental setup. A He:Ne
laser is divided into two beams, one acts as the local oscillator and the
other represents the signal beam. The signal is modulated at $4$MHz with a
defined modulation depth to control the average number of photons in the
generate state. One of the mirrors in the signal path is piezo mounted to
obtain a variable phase difference between the two beams. The data are
recorded by a homodyne detector whose difference photocorrent is demodulated
and then acquired by a computer after a low pass filter. We also show the
typical homodyne samples obtained for coherent signals of different amplitudes
by varying the phase of the local oscillator (these are used to check the
calibration of the piezo, which is performed using signals with a larger
number of photons).

The detector is composed by a 50:50 beams splitter (BS) and a balanced
amplifier detector with a bandwidth of 50 MHz. The difference photocurrent is
filtered with high pass filters, amplified and demodulated at 4 MHz by means
of an electrical mixer (M2). In this way the detection occurs outside any
technical noise and, more importantly, in a spectral region where the laser
does not carry excess noise. The signal is filterd by a low pass filter with a
bandwidth of 300 kHz and sent to the computer through the National Instrument
multichannel data acquisition 6251 with 16 bit of resolution and 1.25 MS/s
sampling rate. The same device is used to send diffusion parameters to the
phase modulator and signal parameters to the amplitude modulator.

##  IV Experimental results

In this Section, we present our experimental results, obtained with signals of
different energies and different levels of noise. At first we show homodyne
samples with the corresponding a posteriori distributions and then compare the
precision obtained in our scheme with the ultimate bound imposed by the
(quantum) Cramér-Rao theorem. Finally, we analyze the dependence of precision
on the signal energy and the noise in order to illustrate how in the limit of
large phase diffusion coherent states becomes the optimal Gaussian probe
states. In fact, they outperform squeezed vacuum states, whose non-classical
features are degraded by phase diffusion process, to an extent that make them
useless for quantum metrology.

In Fig. 2 we report typical examples of homodyne samples, referred to a
coherent signal with $N=|\alpha|^{2}$ mean photon number measured at fixed
optimal $\theta$, together with the corresponding Bayesian a posteriori
distribution for the phase shift. The yellow area denotes the portion of data
used to infer the phase shift. We choose this range in order to emphasize that
the optimality region in achieved already in that region. In fact, upon
considering larger samples, precision would be improved, due to the
statistical scaling of the variance ${\rm Var}[\phi]=C/M$, $C$ being a
proportionality constant. On the other hand, optimality, i.e., the fact that

$C\simeq 1/H_{\alpha}\,,$

where $H_{\alpha}$ is the QFI for phase-diffused coherent signals, is achieved
for $M\sim 100$ measurements. In the noiseless case the QFI is given by
$H_{\alpha}=4N$, whereas it decreases monotonically by increasing the value of
the noise parameter $\Delta$. Notice that using optimized Gaussian signals,
i.e. the squeezed vacuum state, one has a QFI given by $H_{g}=8N^{2}+8N$ in
the noiseless case. However, in the presence of large phase diffusion, i.e.
for large values of $\Delta$, $H_{\alpha}$ is larger than the QFI obtained for
phase-diffused squeezed vacuum states. In other words, coherent states turns
out to be the optimal Gaussian probe states Gen11 .

Figure 2: (color online) Typical examples of homodyne samples measured at
fixed optimal $\theta$, together with the corresponding Bayesian a posteriori
distribution for the phase shift. The phase diffusion is $\Delta=\pi/6$ rad
and the yellow area denotes the portion of data used to infer the phase shift.

In Fig. 3 we plot the quantity

$K_{M}=M\,{\rm Var}[\phi_{\rm B}]H_{\alpha}\,,$

i.e., the variance of the Bayesian estimator from homodyne data multiplied by
the number of data (measurements) and by the coherent states quantum Fisher
information, as a function of $M$. $K_{M}$ is by definition larger than one
and expresses the ratio between the actual precision of the interferometric
setup and the CR bound. As it is apparent from the plot $K_{M}$ rapidly
decreases with the number of measurements, almost independently on the value
of the number of photons $N$ and of the noise parameter $\Delta$. The
optimality region, i.e., $K_{M}\simeq 1$ is achieved already for $M\simeq 100$
measurements, and the asymptotic value of $K_{M}$ is closer to 1 for
increasing $N$ and $\Delta$. Furthermore, the number of measurements needed to
achieve the optimal region may be (slightly) reduced by using the Jeffreys
prior Jpp

$p(\phi)\propto\sqrt{F(\phi)}\,$

instead of the uniform one, where

$F(\phi)=\int\\!dx\,p(x|\phi)[\partial_{\phi}\log p(x|\phi)]^{2}$

is the Fisher information of the homodyne distribution.

Figure 3: (color online) The noise ratio $K_{M}=({\rm Var}[\phi_{\rm
B}]MH_{\alpha})$ as a function of the number of data $M$ and for different
values of the number of photons $N$ and the noise parameter $\Delta$. Blue
circles: $N=0.90$, $\Delta=\pi/18$ rad; red squares: $N=0.90$, $\Delta=\pi/9$
rad; yellow diamonds: $N=4.12$, $\Delta=\pi/18$ rad; green triangles:
$N=4.12$, $\Delta=\pi/9$ rad.

In Fig. 4 we show the variance of the Bayesian estimator from homodyne data

$V_{M}=M{\rm Var}[\phi_{\rm B}]$

obtained after $M$ measurements, together with the CR bound $1/H_{\alpha}$ for
coherent states, and for the (phase-diffused) optimized Gaussian states, i.e.,
$1/H_{g}$. In particular, the top panel shows the behaviour as a function of
$\Delta$ for different values of the number of photons $N$, while in the
bottom panel we plot the same quantities as a function of the number of
photons $N$ and for different values of the noise $\Delta$. As it is apparent
from the plots, nearly optimal inferferometric precision is achieved for
increasing energy or phase diffusion, i.e., for larger values of $N$ or
$\Delta$.

##  V Conclusions

In conclusion, we have demonstrated a nearly optimal interferometric scheme
based on homodyne detection and coherent signals for the detection of a phase
shift in the presence of large phase diffusion. Our scheme does not require
nonclassical light and achieve the ultimate bound to interferometric
sensitivity using Bayesian analysis on small samples of homodyne data, where
the number of measurements is of the order of few hundreds.

It is worth noting that for large phase diffusion coherent states are the
optimal Gaussian probe states. Indeed they outperform squeezed vacuum states,
whose non-classical features are degraded by phase diffusion process, such
that they become completely useless for quantum metrology.

Optical interferometry represents a high accurate measurement scheme with wide
applications in many fields of science and technology, including high
precision measurements and communication channels. On the other hand, phase
diffusion represents a crucial obstacle towards the implementation of high
precision interferometric measurements and phase shift based communication
channels. Our results allow to design feasible, high-performance,
communication channels also in the presence of phase noise, which cannot be
effectively controlled in realistic conditions. Therefore, besides fundamental
interest, our results also represent a benchmark for realistic phase based
communication or measurement protocols.

Figure 4: (color online) Variance $V_{M}=M{\rm Var}[\phi_{\rm B}]$ of the
Bayesian estimator from homodyne data after $M=100$ measurements (points),
together with the CR bound for coherent states (solid lines) and for optimized
Gaussian states (dashed lines). The top panel of shows the behaviour of
$V_{100}$ as a function of $\Delta$ for different values of the number of
photons (top red lines/squares: $N=0.90$; bottom blue lines/circles:
$N=14.11$). The bottom panel shows $V_{100}$ as a function of the number of
photons $N$ and for different values of the noise (top blue lines/squares:
$\Delta=\pi/9$ rad; bottom green lines/circles: $\Delta=\pi/18$ rad).

## Acknowledgements

This work has been supported by MIUR (FIRB “LiCHIS” - RBFR10YQ3H), the UK
EPSRC (EP/I026436/1), MAE (INQUEST), UniMi (PUR2009 SIN.PHO.NANO), UIF/UFI
(Vinci Program), and the University of Trieste (FRA2009).

## References

  * (1) C. M. Caves, Phys. Rev. D 23, 1693 (1981).
  * (2) R. Bluhm, V. A. Kostelecky, C. D. Lane, N. Russel, Phys. Rev. Lett. 88, 090801 (2002).
  * (3) C. Jentsch, T. Muller, E. Rasel, W. Ertmer, Gen. Rel. Gravit. 36, 2197 (2004).
  * (4) S. Fray, C. A. Diez, T. W. Hänsch, M. Weitz, Phys. Rev. Lett. 93, 240404 (2004).
  * (5) M. J. Snadden, J. M. NcGuirk, P. Bouyer, K. G. Haritos, M. A. Kasevich, Phys. Rev. Lett. 81, 971 (1998).
  * (6) M. A. Armen, J. K. Au, J. K. Stockton, A. C. Doherty, and H. Mabuchi, Phys. Rev. Lett. 89, 133602 (2002).
  * (7) M. W. Mitchell, J. S. Lundeen, and A. M. Steinberg, Nature 429, 161 (2004).
  * (8) T. Nagata, R. Okamoto, J. L. O’Brien, K. Sasaki, and S. Takeuchi, Science 316, 726 (2007).
  * (9) K. J. Resch, K. L. Pregnell, R. Prevedel, A. Gilchrist, G. J. Pryde, J. L. O’Brien, and A. G. White, Phys. Rev. Lett. 98, 223601 (2007).
  * (10) B. L. Higgins, D. W. Berry, S. D. Bartlett, H. M. Wiseman, and G. J. Pryde, Nature 450, 393 (2007).
  * (11) B. L. Higgins, D. W. Berry, S. D. Bartlett, M. W. Mitchell, H. M. Wiseman, and G. J. Pryde, New J. Phys. 11, 073023 (2009).
  * (12) Z. Hradil Quantum Opt. 4, 93 (1992).
  * (13) S. L. Braunstein, Phys. Rev. Lett. 69, 3598 (1992).
  * (14) A. S. Lane, S. Braunstein, C. M. Caves, Phys. Rev. A 47, 1667 (1993).
  * (15) B. C. Sanders, G. J. Milburn, Phys. Rev. Lett. 75, 2944 (1995).
  * (16) K. Eckert, P. Hyllus, D. Bruss, U. V. Poulsen, M. Lewenstein, C. Jentsch, T. Muller, E. M. Rasel, W. Ertmer, Phys. Rev. A 73, 013814 (2006).
  * (17) V. Giovannetti, S. Lloyd, and L. Maccone, Science 306, 1330 (2004); Phys. Rev. Lett. 96, 010401 (2006).
  * (18) F. W. Sun, B. H. Liu, Y. X. Gong, Y. F. Huang, Z. Y. Ou, G. C. Guo, EPL 82, 24001 (2008).
  * (19) L. Pezzé, A. Smerzi, G. Khoury, J.F. Hodelin, and D. Bouwmeester, Phys. Rev. Lett. 99, 223602 (2007); L. Pezzé, A. Smerzi, Phys. Rev. Lett. 100, 073601 (2008).
  * (20) J. Grond, U. Hohenester, I. Mazets, and J. Schmiedmyer, New J. Phys. 12, 065036 (2010); J. Grond, U. Hohenester, J. Schmiedmayer, A. Smerzi, Phys. Rev. A 84, 023619 (2011).
  * (21) M. Hayashi Progr. Inf. 8, 81 (2011).
  * (22) D. Braun, J. Martin, Nat. Comm. 2, 223 (2011); D. Braun, Eur. Phys. J. D 59. 521 (2010).
  * (23) S. Boixo, A. Datta, M. J. Davis, S. T. Flammia, A. Shaji, C. M. Caves, Phys. Rev. Lett. 101, 040403.
  * (24) V. Giovannetti, S. Lloyd, and L. Maccone, Nat. Phot. 5, 222 (2011).
  * (25) M. G. A. Paris, Phys. Lett A 201, 132 (1995); S. Olivares, M. G. A. Paris, Optics Spectr. 103, 231 (2007).
  * (26) R. A. Campos, C. C. Gerry, and A. Benmoussa, Phys. Rev. A 68, 023810 (2003).
  * (27) S. D. Huver, C. F. Wildfeuer, and J. P. Dowling, Phys. Rev. A 78, 063828 (2008).
  * (28) J. J. Cooper, D. W. Hallwood, and J. A. Dunningham, Phys. Rev. A 81, 043624 (2010).
  * (29) M. Kacprowicz, R. Demkowicz-Dobrzanski, W. Wasilewski, K. Banaszek, I. A. Walmsley, Nat. Phot. 4, 357 (2010).
  * (30) U. Dorner, R. Demkowicz-Dobrzanski, B. J. Smith, J. S. Lundeen, W. Wasilewski, K. Banaszek and I. A. Walmsley, Phys. Rev. Lett. 102, 040403 (2009); Phys. Rev. A. 80, 013825 (2009).
  * (31) H. Cable, G. A. Durkin, Phys. Rev. Lett. 105, 013603 (2010).
  * (32) J. Joo, W. J. Munro, T. P. Spiller, Phys. Rev. Lett. 107, 083601 (2011).
  * (33) S. Knysh, V. N. Smelyanskiy and G. A. Durkin, Phys. Rev. A 83, 021804(R) (2011).
  * (34) T. B. Bahder, Phys. Rev. A 83, 053601 (2011).
  * (35) A. Datta, L. Zhang, N. Thomas-Peter, U. Dorner, B. J. Smith, I. A. Walmsley, Phys. Rev. A 83, 063836 (2011).
  * (36) D. Brivio, S. Cialdi, S. Vezzoli, B. Teklu, M. G. Genoni, S. Olivares, M. G. A. Paris, Phys. Rev. A 81, 012305 (2010).
  * (37) B. Teklu, M. G. Genoni, S. Olivares, M. G. A. Paris, Phys. Scr. T140, 014062 (2010).
  * (38) E. Tesio, S. Olivares and M. G. A. Paris, Int. J. Quant. Inf. 9, 379 (2011).
  * (39) I. Tikhonenkov, M. G. Moore and A. Vardi, Phys. Rev. A 82, 043624 (2010).
  * (40) Y. C. Liu, G. R. Jin, L. You, Phys. Rev. A 82, 045601 (2010).
  * (41) G. Ferrini, D. Spehner, A. Minguzzi, F. W. J. Hekking, Phys. Rev. A 82, 033621 (2010).
  * (42) M. G. Genoni, S. Olivares, M. G. A. Paris, Phys. Rev. Lett. 106, 153603 (2011).
  * (43) A. Monras, Phys. Rev. A 73, 033821 (2006).
  * (44) J. D. Malley, J. Hornstein, Stat. Sci. 8, 433 (1993).
  * (45) S. L. Braunstein and C. M. Caves, Phys. Rev. Lett. 72, 3439 (1994); S. L. Braunstein, C. M. Caves and G. J. Milburn, Ann. Phys. 247, 135 (1996).
  * (46) D. C. Brody, L. P. Hughston, Proc. Roy. Soc. Lond. A 454, 2445 (1998); A 455, 1683 (1999).
  * (47) M. G. A. Paris, Int. J. Quant. Inf. 7, 125 (2009).
  * (48) B. M. Escher, R. L. de Matos Filho, L. Davidovich, Nat. Phys. 7, 406 (2011); Braz. J. Phys. 41, 229 (2011).
  * (49) Z. Hradil, Phys. Rev. A 51, 1875 (1995); Z. Hradil, R. Myška, and J. Peřina, M. Zawisky, Y. Hasegawa, H. Rauch, Phys. Rev. Lett. 76, 4295 (1996).
  * (50) S. Olivares, M. G. A. Paris, J. Phys. B 42, 055506 (2009); B. Teklu, S. Olivares, M. G. A. Paris, J. Phys. B 42, 035502 (2009).
  * (51) O. E. Barndorff-Nielsen and R. D. Gill, J. Phys. A 33, 4481 (2000).
  * (52) H. Jeffreys, Proc. Roy. Soc. A 186, 453 (1946).