# The Synchronization Power (Consensus Number) of Access-Control Objects: the Case of AllowList and DenyList

Davide Frey, Mathieu Gestin, Michel Raynal

► To cite this version:

Davide Frey, Mathieu Gestin, Michel Raynal. The Synchronization Power (Consensus Number) of Access-Control Objects: the Case of AllowList and DenyList. DISC 2023 - 37th International Symposium on Distributed Computing, Oct 2023, L'aquila, Italy. pp.1-32, 10.4230/LIPIcs.DISC.2023.21. hal-04399298

HAL Id: hal-04399298

https://inria.hal.science/hal-04399298v1

Submitted on 17 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Synchronization Power (Consensus Number) of Access-Control Objects: The Case of AllowList and DenyList

Davide Frey ☑

Inria, IRISA, CNRS, Université de Rennes

Mathieu Gestin ☑

Inria, IRISA, CNRS, Université de Rennes

Michel Raynal ☑

IRISA, Inria, CNRS, Université de Rennes

## Abstract

This article studies the synchronization power of AllowList and DenyList objects under the lens provided by Herlihy's consensus hierarchy. It specifies AllowList and DenyList as distributed objects and shows that, while they can both be seen as specializations of a more general object type, they inherently have different synchronization power. While the AllowList object does not require synchronization between participating processes, a DenyList object requires processes to reach consensus on a specific set of processes. These results are then applied to a more global analysis of anonymity-preserving systems that use AllowList and DenyList objects. The specification First, a blind-signature-based e-voting is presented. Second, DenyList and AllowList objects are used to determine the consensus number of a specific decentralized key management system. Third, an anonymous money transfer protocol using the association of AllowList and DenyList objects is presented. Finally, this study is used to study the properties of these application, and to highlight efficiency gains that they can achieve in message passing environment.

**2012 ACM Subject Classification** Theory of computation → Distributed computing models; Security and privacy → Access control; Security and privacy → Pseudonymity, anonymity and untraceability

**Keywords and phrases** Access control, AllowList/DenyList, Blockchain, Consensus number, Distributed objects, Modularity, Privacy, Synchronization power.

Digital Object Identifier 10.4230/LIPIcs.DISC.2023.39

## 1 Introduction

The advent of blockchain technologies increased the interest of the public and industry in distributed applications, giving birth to projects that have applied blockchains in a plethora of use cases. These include e-vote systems [1], naming services [2, 3], Identity Management Systems [4, 5], supply-chain management [6], or Vehicular Ad hoc Network [7]. However, this use of the blockchain as a swiss-army knife that can solve numerous distributed problems highlights a lack of understanding of the actual requirements of those problems. Because of these poor specifications, implementations of these applications are often sub-optimal.

This paper thoroughly studies a class of problems widely used in distributed applications and provides a guideline to implement them with reasonable but sufficient tools.

Differently from the previous approaches, it aims to understand the amount of synchronization required between processes of a system to implement *specific* distributed objects. To achieve this goal it studies such objects under the lens of Herlihy's consensus number [8]. This parameter is inherently associated to shared memory distributed objects, and has no direct correspondence in the message passing environment. However, in some specific cases, this information is enough to provide a better understanding of the objects analyzed, and thus, to gain efficiency in the message passing implementations. For example, recent papers [9, 10]

<figure><img src="image_2.png" /></figure>
have shown that cryptocurrencies can be implemented without consensus and therefore
without a blockchain. In particular, Guerraoui et al. [9] show that *k*-asset transfer has a
consensus number *k* where *k* is the number of processes that can withdraw currency from the
same account [11]. Similarly, Alpos et al. [12] have studied the synchronization properties of
ERC20 token smart contracts and shown that their consensus number varies over time as
a result of changes in the set of processes that are approved to send tokens from the same
account. These two results consider two forms of asset transfer: the classical one and the one
implemented by the ERC20 token, which allows processes to dynamically authorize other
processes. The consensus number of those objects depends on specific and well identified
processes. From this study, it is possible to conclude that the consensus algorithms only need
to be performed between those processes. Therefore, in these specific cases, the knowledge of
the consensus number of an object can be directly used to implement more efficient message
passing applications. Furthermore, even if this study uses a shared memory model, with
crash prone processes, its results can be used to implement more efficient Byzantine resilient
algorithm, in a message passing environment. This paper proposes to extend this knowledge
to a broader class of applications.

Indeed, the transfer of assets, be them cryptocurrencies or non-fungible tokens, does not constitute the only application in the Blockchain ecosystem. In particular, as previously indicated, a number of applications like e-voting [1], naming [2, 3], or Identity Management [4, 5] use Blockchain as a tool to implement some form of access control. This is often achieved by implementing two general-purpose objects: AllowLists and DenyLists. An AllowList provides an opt-in mechanism. A set of managers can maintain a list of authorized parties, namely the AllowList. To access a resource, a party (user) must prove the presence of an element associated with its identity in the AllowList. A DenyList provides instead an opt-out mechanism. In this case, the managers maintain a list of revoked elements, the DenyList. To access a resource, a party (user) must prove that no corresponding element has been added to the DenyList. In other words, AllowList and DenyList support, respectively, set-membership and set-non-membership proofs on a list of elements.

The proofs carried out by AllowList and DenyList objects often need to offer privacy guarantees. For example, the Sovrin privacy preserving Decentralized Identity-Management System (DIMS) [4] associates an AllowList<fnref n="1" /> with each verifiable credential that contains the identifiers of the devices that can use this verifiable credential. When a device uses a credential with a verifier, it needs to prove that the identifier associated with it belongs to the AllowList. This proof must be done in zero knowledge, otherwise the verifier would learn the identity of the device, which in turn could serve as a pseudo-identifier for the user. For this reason, AllowList and DenyList objects support respectively a zero-knowledge proof of set membership or a zero-knowledge proof of set non-membership.

Albeit similar, the AllowList and DenyList objects differ significantly in the way they
handle the proving mechanism. In the case of an AllowList, no security risk appears if access
to a resource is prohibited to a process, even if a manager did grant this right. As a result,
a transient period in which a user is first allowed, then denied, and then allowed again to
access a resource poses no problem. On the contrary, with a DenyList, being allowed access
to a resource after being denied poses serious security problems. Hence, the DenyList object
is defined with an additional anti-flickering property prohibiting those transient periods.
This property is the main difference between an AllowList and a DenyList object and is the
reason for their distinct consensus numbers.

<footnote n="1">¹ In reality this is a variant that mixes AllowList and DenyList which we discuss in appendix A.</footnote>
Existing systems [1, 2, 3, 4, 5] that employ AllowList and DenyList objects implement them on top of a heavy blockchain infrastructure, thereby requiring network-level consensus to modify their content. As already said, this paper studies this difference under the lens of the consensus number [11]. It shows that (i) the consensus number of an AllowList object is 1, which means that an AllowList can be implemented without consensus; and that (ii) the consensus number of a DenyList is instead equal to the number of processes that can conduct prove operations on the DenyList, and that only these processes need to synchronize. Both data structures can therefore be implemented without relying on the network-level consensus provided by a blockchain, which opens the door to more efficient implementations of applications based on these data structures.

To summarize, this paper presents the following three contributions.

1. It formally defines and studies AllowList and DenyList as distributed objects (Section 3).

2. It analyses the consensus number of these objects: it shows that the AllowList does not require synchronization between processes (Section 5), while the DenyList requires the synchronization of all the verifiers of its set-non-membership proofs (Section 6).

3. It uses these theoretical results to give intuitions on their optimal implementations. Namely the implementation of a DIMS, as well as of an e-vote system and an anonymous asset-transfer protocol (Appendix B and C).

<figure><img src="image_3.png" /></figure>

To the best of our knowledge, this paper is the first to study the AllowList and DenyList from a distributed algorithms point of view. So we believe our results can provide a powerful tool to identify the consensus number of recent distributed objects that make use of them and to provide more efficient implementations of such objects.

# 2 Preliminaries

## 2.1 Computation Model

### Model

Let $\Pi$ be a set of $N$ asynchronous sequential crash-prone processes $p_1, \cdots, p_N$. Sequential means that each process invokes one operation of its own algorithm at a time. We assume the local processing time to be instantaneous, but the system is asynchronous. This means that non-local operations can take a finite but arbitrarily long time and that the relative speeds between the clocks of the different processes are unknown. Finally, processes are crash-prone: any number of processes can prematurely and definitely halt their executions. A process that crashes is called *faulty*. Otherwise, it is called *correct*. The system is eponymous: a unique positive integer identifies each process, and this identifier is known to all other processes.
125 **Communication**

Processes communicate via shared objects of type T. Each operation on a shared object is associated with two *events*: an *invocation* and a *response*. An object type T is defined by a tuple (Q, Q₀, O, R, Δ), where Q is a set of states, Q₀ ⊆ Q is the set of initial states, O is the set of operations a process can use to access this object, R is the set of responses to these operations, and Δ ⊆ Π × Q × O × R × Q is the transition function defining how a process can access and modify an object.

132 Histories and Linearizability

A history [8] is a sequence of invocations and responses in the execution of an algorithm. An invocation with no matching response in a history, *H*, is called a *pending* invocation. A sequential history is one where the first event is an invocation, and each invocation—except possibly the last one—is immediately followed by the associated response. A sub-history is a sub-sequence of events in a history. A process sub-history $H|p_i$ of a history *H* is a sub-sequence of all the events in *H* whose associated process is $p_i$. Given an object *x*, we can similarly define the object sub-history $H|x$. Two histories *H* and $H'$ are equivalent if $H|p_i = H'|p_i, \forall i \in \{1, \dots, N\}$.

In this paper, we define the specification of a shared object, *x*, as the set of all the allowed sub-histories, $H|x$. We talk about a sequential specification if all the histories in this set are sequential. A legal history is a history *H* in which, for all objects $x_i$ of this history, $H|x_i$ belongs to the specification of $x_i$. The completion $\bar{H}$ of a history *H* is obtained by extending all the pending invocations in *H* with the associated matching responses. A history *H* induces an irreflexive partial order $<_H$ on operations, i.e. $op_0 <_H op_1$ if the response to the operation $op_0$ precedes the invocation of operation $op_1$. A history is sequential if $<_H$ is a total order. The algorithm executed by a correct process is wait-free if it always terminates after a finite number of steps. A history *H* is linearizable if a completion $\bar{H}$ of *H* is equivalent to some legal sequential history *S* and $<_H \subseteq <_S$.

151 Consensus number

The consensus number of an object of type *T* (noted *cons(*T*)*) is the largest *n* such that it
is possible to wait-free implement a consensus object from atomic read/write registers and
objects of type *T* in a system of *n* processes. If an object of type *T* makes it possible to
wait-free implement a consensus object in a system of any number of processes, we say the
consensus number of this object is *∞*. Herlihy [11] proved the following well-known theorem.

► **Theorem 1.** Let *X* and *Y* be two atomic objects type such that cons(*X*) = *m* and cons(*Y*) = *n*, and *m* < *n*. There is no wait-free implementation of an object of type *Y* from objects of type *X* and read/write registers in a system of more than *m* processes.

We will determine the consensus number of the DenyList and the AllowList objects using
Atomic Snapshot objects and consensus objects in a set of *k* processes. A Single Writer Multi
Reader (SWMR) [13] Atomic Snapshot object is an array of fixed size, which supports two
operations: Snapshot and Update. The Snapshot() operation allows a process $p_i$ to read the
whole array in one atomic operation. The Update(v, i) operation allows a process $p_i$ to write
the value *v* in the *i*-th position of the array. Afek et al. showed that a SWMR Snapshot
object can be wait-free implemented from read/write registers [13], i.e., this object type has
consensus number 1. This paper assumes that all Atomic Snapshot objects used are SWMR.
A consensus object provides processes with a single one-shot operation *propose*(). When a
process $p_i$ invokes $propose(v)$ it proposes $v$. This invocation returns a *decided* value such that the following three properties are satisfied.

171 ■ Validity: If a correct process decides value $v$, then $v$ was proposed by some process;

172 ■ Agreement: No two correct processes decide differently; and

173 ■ Termination: Every correct process eventually decides.

174 A $k$-consensus object is a consensus object accessed by at most $k$ processes.

## 2.2 Number theory preliminaries

### 176 Cryptographic Commitments

A cryptographic commitment is a cryptographic scheme that allows a Prover to commit to a value $v$ while hiding it. The commitment scheme is a two phases protocol. First, the prover computes a binding value known as commitment, $C$, using a function *Commit*. *Commit* takes as inputs the value $v$ and a random number $r$. The prover sends this hiding and binding value $C$ to a verifier. In the second phase, the prover reveals the committed value $v$ and the randomness $r$ to the verifier. The verifier can then verify that the commitment $C$ previously received refers to the transmitted values $v$ and $r$. This commitment protocol is the heart of Zero Knowledge Proof (ZKP) protocols.

### 185 Zero Knowledge Proof of set operations

A Zero Knowledge Proof (ZKP) system is a cryptographic protocol that allows a prover to prove some Boolean statement about a value $x$ to a verifier without leaking any information about $x$. A ZKP system is initialized for a specific language $\mathcal{L}$ of the complexity class $\mathcal{NP}$. The proving mechanism takes as input $\mathcal{L}$ and outputs a proof $\pi$. Knowing $\mathcal{L}$ and $\pi$, any verifier can verify that the prover knows a value $x \in \mathcal{L}^2$. However, the verifier cannot learn the value $x$ used to produce the proof. In the following, it is assumed there exists efficient non interactive ZKP systems of set-membership and set-non-membership (e.g., constructions from [14] can be used).

## 3 The AllowList and DenyList objects: Definition

Distributed AllowList and DenyList object types are the type of objects that allow a set of managers to control access to a resource. The term "resource" is used here to describe the goal a user wants to achieve and which is protected by an access control policy. A user is granted access to the resource if it succeeds in proving that it is authorized to access it. First, we describe the AllowList object type. Then we consider the DenyList object type.

The AllowList object type is one of the two most common access control mechanisms. To access a resource, a process $p \in \Pi_V$ needs to prove it knows some element $v$ previously authorized by a process $p_M \in \Pi_M$, where $\Pi_M \subseteq \Pi$ is the set of managers, and $\Pi_V \subseteq \Pi$ is the set of processes authorized to conduct proofs. We call verifiers the processes in $\Pi_V$. The sets $\Pi_V$ and $\Pi_M$ are predefined and static. They are parameters of the object. Depending on the usage of the object, these subset can either be small, or they can contain all the processes in $\Pi$.

<footnote n="2">² The notation $x \in \mathcal{L}$ denotes the fact that $x$ is a solution to the instance of the problem expressed by the language $\mathcal{L}$</footnote>
39:6 The Synchronization Power of Access Control Objects

A process $p \in \Pi_V$ proves that $v$ was previously authorized by invoking a $PROVE(v)$ operation. This operation is said to be valid if some manager in $\Pi_M$ previously invoked an APPEND($v$) operation. Intuitively, we can see the invocation of the APPEND($v$) operation as the action of authorizing some process to access the resource. On the other hand, the $PROVE(v)$ operation, performed by a prover process, $p \in \Pi_V$, proves to the other processes in $\Pi_V$ that they are authorized. However, this proof is not enough in itself. The verifiers of a proof must be able to verify that a valid $PROVE$ operation has been invoked. To this end, the AllowList object type is also equipped with a $READ$() operation. This operation can be invoked by any process in $\Pi$ and returns all the valid $PROVE$ operations invoked, along with the identity of the processes that invoked them. The list returned by the READ operation can be any arbitrary permutation of the list of $PROVE$ operations. All processes in $\Pi$ can invoke the READ operation.<fnref n="3" />

An optional anonymity property can be added to the AllowList object to enable privacy-preserving implementations. This property ensures that other processes cannot learn the value $v$ proven by a $PROVE(v)$ operation.

The AllowList object type is formally defined as a sequential object, where each invocation is immediately followed by a response. Hence, the sequence of operations defines a total order, and each operation can be identified by its place in the sequence.

**► Definition 2.** The AllowList object type supports three operations: APPEND, PROVE, and READ. These operations appear as if executed in a sequence $Seq$ such that:

- Termination. A PROVE, an APPEND, or a READ operation invoked by a correct process always returns.

- APPEND Validity. The invocation of $APPEND(x)$ by a process $p$ is valid **if**:

- $p \in \Pi_M \subseteq \Pi$; and

- $x \in S$, where $S$ is a predefined set.

- Otherwise, the operation is invalid.

- PROVE Validity. **If** the invocation of $op=PROVE(x)$ by a process $p$ is valid, **then**:

- $p \in \Pi_V \subseteq \Pi$; and

- A valid $APPEND(x)$ operation appears before $op$ in $Seq$.

- Otherwise, the invocation is invalid.

- Progress. **If** a valid $APPEND(x)$ operation is invoked, **then** there exists a point in $Seq$ such that any $PROVE(x)$ operation invoked after this point by any process $p \in \Pi_V$ will be valid.

- READ Validity. The invocation of $op=READ$() by a process $p \in \Pi_V$ returns the list of valid invocations of $PROVE$ that appears before $op$ in $Seq$ along with the names of the processes that invoked each operation.

- Optional - Anonymity. Let us assume the process $p$ invokes a $PROVE(v)$ operation. If the process $p'$ invokes a $READ$() operation, then $p'$ cannot learn the value $v$ unless $p$ leaks additional information.<fnref n="4" />

<footnote n="3">³ Usually, AllowList objects are implemented in a message-passing setting. In these cases, the READ operation is implicit. Each process knows a local state of the distributed object, and can inspect it any time. In the shared-memory setting, we need to make this READ operation explicit.</footnote>

<footnote n="4">⁴ The Anonymity property only protects the value $v$. The system considered is eponymous. Hence, the identity of the processes is already known. However, the anonymity of $v$ makes it possible to hide other information. For example, the identity of a client that issues a request to a process of the system. These example are discussed in Section 7. Thereby, the anonymity property does not contravene the READ validity property, which only discloses the process identity.</footnote>
The AllowList object is defined in an append-only manner. This definition makes it
possible to use it to build all use cases explored in this paper. However, some use cases
could need an DenyList with an additional REMOVE operation. This variation is studied in
Appendix A.

The DenyList object type can be informally presented as an access policy where, contrary to the AllowList object type, all users are authorized to access the resource in the first place. The managers are here to revoke this authorization. A manager revokes a user by invoking the APPEND(*v*) operation. A user uses the PROVE(*v*) operation to prove that it was not revoked. A PROVE(*v*) invocation is invalid only if a manager previously revoked the value *v*.

All the processes in $\Pi$ can verify the validity of a PROVE operation by invoking a `READ()` operation. This operation is similar to the `AllowList`'s `READ` operation. It returns the list of valid PROVE invocations along with the name of the processes that invoked it.

There is one significant difference between the DenyList and the AllowList object types. With an AllowList, if a user cannot access a resource immediately after its authorization, no malicious behavior can harm the system—the system’s state is equivalent to its previous state. However, with a DenyList, a revocation not taken into account can let a malicious user access the resource and harm the system. In other words, access to the resource in the DenyList case must take into account the "most up to date" available revocation list.

To this end, the DenyList object type is defined with an additional property. The anti-flickering property ensures that if an APPEND operation is taken into account by one PROVE operation, it will be taken into account by every subsequent PROVE operation. Along with the progress property, the anti-flickering property ensures that the revocation mechanism is as immediate as possible. The DenyList object is formally defined as a sequential object, where each invocation is immediately followed by a response. Hence, the sequence of operations define a total order, and each operation can be identified by its place in the sequence.

**► Definition 3.** The DenyList object type supports three operations: APPEND, PROVE, and READ. These operations appear as if executed in a sequence *Seq* such that:

■ Termination. A PROVE, an APPEND, or a READ operation invoked by a correct process always returns.

■ APPEND Validity. The invocation of APPEND(*x*) by a process *p* is valid **if**:

■ *p* ∈ Π<sub>*M*</sub> ⊆ Π; and

■ *x* ∈ *S*, where *S* is a predefined set.

Otherwise, the operation is invalid.

■ PROVE Validity. **If** the invocation of a *op* =PROVE(*x*) by a correct process *p* is not valid, **then**:

■ *p* ∉ Π<sub>*V*</sub> ⊆ Π; or

■ A valid APPEND(*x*) appears before *op*<sub>*P*</sub> in *Seq*.

Otherwise, the operation is valid.

■ PROVE Anti-Flickering. **If** the invocation of a operation *op* =PROVE(*x*) by a correct process *p* ∈ Π<sub>*V*</sub> is invalid, **then** any PROVE(*x*) operation that appears after *op* in *Seq* is invalid.<fnref n="5" />

<footnote n="5">⁵ The only difference between the AllowList and the DenyList object types is this anti-flickering property. As it is shown in Section 5 and in Section 6, the AllowList object has consensus number 1, and the DenyList object has consensus number $k = |\Pi_V|$. Hence, this difference in term of consensus number is due solely to the anti-flickering property. It is an open question whether a variation of this property could transform any consensus number 1 object into a consensus number k object.</footnote>
39:8 The Synchronization Power of Access Control Objects

<table><caption>Table 1 Transition function $\Delta$ for the PROOF-LIST object.</caption><thead><tr><th>Process</th><th>Operation</th><th>Initial state</th><th>Response</th><th>Final state</th><th>Conditions</th></tr></thead><tbody><tr><td>p<sub>i</sub> &isin; &Pi;<sub>M</sub></td><td>APPEND(y)</td><td>(listed-values = {x &isin; S},<br>proofs = ({(p<sub>j</sub> &isin; &Pi;, S &sub; S, P &isin; P<sub>L<sub>S</sub></sub>)}))</td><td>True</td><td>(listed-values &cup; {y},<br>proofs)</td><td>y &isin; S</td></tr><tr><td>p<sub>i</sub></td><td>APPEND(y)</td><td>(listed-values = {x &isin; S},<br>proofs = ({(p<sub>j</sub> &isin; &Pi;, S &sub; S, P &isin; P<sub>L<sub>S</sub></sub>)}))</td><td>False</td><td>(listed-values, proofs)</td><td>p<sub>i</sub> &notin; &Pi;<sub>M</sub> &or; y &notin; S</td></tr><tr><td>p<sub>i</sub> &isin; &Pi;<sub>V</sub></td><td>PROVE(y)</td><td>(listed-values = {x &isin; S},<br>proofs = ({(p<sub>j</sub> &isin; &Pi;, S &sub; S, P &isin; P<sub>L<sub>S</sub></sub>)}))</td><td>(A, P)</td><td>(listed-values,<br>proofs &cup; {(p<sub>i</sub>, A, P)})</td><td>&forall;y &isin; L<sub>A</sub> &and; A &sub; listed-values<br>&and;&forall;P &isin; P<sub>L<sub>A</sub></sub> &and; C(y, S&#773;) = 1</td></tr><tr><td>p<sub>i</sub></td><td>PROVE(y)</td><td>(listed-values = {x &isin; S},<br>proofs = ({(p<sub>j</sub> &isin; &Pi;, S&#773; &sub; S, P &isin; P<sub>L<sub>S&#773;</sub></sub>)}))</td><td>False</td><td>(listed-values, proofs)</td><td>&forall;y &notin; L<sub>A</sub> &or; A &sub; listed-values<br>&or; &forall;P &notin; P<sub>L<sub>A</sub></sub> &or; &forall;p<sub>i</sub> &notin; &Pi;<sub>V</sub><br>&or; C(y, S&#773;) = 0</td></tr><tr><td>p<sub>i</sub> &isin; &Pi;</td><td>READ()</td><td>(listed-values = {x &isin; S},<br>proofs = ({(p<sub>j</sub> &isin; &Pi;, S&#773; &sub; S, P &isin; P<sub>L<sub>S&#773;</sub></sub>)}))</td><td>proofs</td><td>(listed-values, proofs)</td><td></td></tr></tbody></table>

287 ■ READ Validity. The invocation of op =READ() by a process $p \in \Pi_V$ returns the list of valid invocations of PROVE that appears before op in Seq along with the names of the processes that invoked each operation.

288
289 ■ Optional - Anonymity. Let us assume the process $p$ invokes a PROVE($v$) operation. If the process $p'$ invokes a READ() operation, then $p'$ cannot learn the value $v$ unless $p$ leaks additional information.

293 ■ **4 PROOF-LIST object specification**

294 Section 5 and Section 6 propose an analysis of the synchronization power of the AllowList and the DenyList object types using the notion of consensus number. Both objects share many similarities. Indeed, the only difference is the type of proof performed by the user and the non-flickering properties. Therefore, this section defines the formal specification of the PROOF-LIST object type, a new generic object that can be instantiated to describe the AllowList or the DenyList object type.

295
296
297
298
299 The PROOF-LIST object type is a distributed object type whose state is a pair of arrays (listed-values, proofs). The first array, listed-values, represents the list of authorized/revoked elements. It is an array of objects in a set S, where S is the universe of potential elements. The second array, proofs, is a list of assertions about the listed-values array. Given a set of managers $\Pi_M \subseteq \Pi$ and a set of verifiers $\Pi_V \subseteq \Pi$, the PROOF-LIST object supports three operations. First, the APPEND($v$) operation appends a value $v \in S$ to the listed-values array. Any process in the manager's set can invoke this operation. Second, the PROVE($v$) operation appends a valid proof about the element $v \in S$ relative to the listed-values array to the proofs array. This operation can be invoked by any process $p \in \Pi_V$. Third, the READ() operation returns the proofs array.

300
301
302
303
304
305
306
307
308
309 The sets $\Pi_V$ and $\Pi_M$ are static, predefined subsets of $\Pi$. There is no restriction on their compositions. The choice of these sets only depends on the usage of the AllowList or the DenyList. Depending on the usage, they can either contain a small subset of processes in $\Pi$ or they can contain the whole set of processes of the system.

310
311
312
313
314
315
316
317
318
319 To express the proofs produced by a process $p$, we use an abstract language $\mathcal{L}_A$ of the complexity class $\mathcal{NP}$, which depends on a set $A$. This language will be specified for the AllowList and the DenyList objects in Section 5 and Section 6. The idea is that $p$ produces a proof $\pi$ about a value $v \in S$. A PROVE invocation by a process $p$ is valid only if the proof $\pi$ added to the proofs array is valid. The proof $\pi$ is valid if $v \in \mathcal{L}_A$—i.e., $v$ is a solution to the instance of the problem expressed by $\mathcal{L}_A$, where $\mathcal{L}_A$ is a language of the complexity class
$\mathcal{NP}^6$ which depends on a subset $\mathcal{A}$ of the *listed-values* array ($\mathcal{A} \subseteq \mathcal{S}$). We note $\mathcal{P}_{\mathcal{L}_{\mathcal{A}}}$ the set of valid proofs relative to the language $\mathcal{L}_{\mathcal{A}}$. $\mathcal{P}_{\mathcal{L}_{\mathcal{A}}}$ can either represent Zero Knowledge Proofs or explicit proofs.

320

321

322

If a proof $\pi$ is valid, then the PROVE operation returns $(\mathcal{A}, \text{Acc.Prove}(v, \mathcal{A}))$, where $\text{Acc.Prove}(v, \mathcal{A})$ is the proof generated by the operation, and where $\mathcal{A}$ is a subset of values in *listed-values* on which the proof was applied. Otherwise, the PROVE operation returns "False". Furthermore, the *proofs* array also stores the name of the processes that invoked PROVE operations.

323

324

325

326

327

Formally, the PROOF-LIST object type is defined by the tuple $(Q, Q_0, O, R, \Delta)$, where:

328

- The set of valid state is $Q = (\text{listed-values} = \{x \in \mathcal{S}\}, \text{proofs} = \{(p \in \Pi, \hat{S} \subseteq \mathcal{S}, P \in \mathcal{P}_{\mathcal{L}_{\hat{S}}}\})$, where *listed-values* is a subset of $\mathcal{S}$ and *proofs* is a set of tuples. Each tuple in *proofs* consists of a proof associated with the set it applies to and to the identifier of the process that issued the proof;

329

330

331

332

- The set of valid initial states is $Q_0 = (\emptyset, \emptyset)$, the state where the *listed-values* and the *proofs* arrays are empty;

333

334

- The set of possible operation is $O = \{\text{APPEND}(x), \text{PROVE}(y), \text{READ}(\cdot)\}$, with $x, y \in \mathcal{S}$;

335

- The set of possible responses is $R = \{ \text{True}, \text{False}, (\hat{S} \subseteq \mathcal{S}, P \in \mathcal{P}_{\mathcal{L}_{\hat{S}}}), \{(p \in \Pi, \hat{S}' \subseteq \mathcal{S}, P' \in \mathcal{P}_{\mathcal{L}_{\hat{S}'}})\} \}$, where True is the response to a successful APPEND operation, $(\hat{S}, P)$ is the response to a successful PROVE operation, $\{(p, \hat{S}', P')\}$ is the response to a READ operation, and False is the response to a failed operation; and

336

337

338

339

- The transition function is $\Delta$. The PROOF-LIST object type supports 5 possible transitions. We define the 5 possible transitions of $\Delta$ in Table 1.

340

341

The first transition of the $\Delta$ function models a valid APPEND invocation, a value $y \in \mathcal{S}$ is added to the *listed-values* array by a process in the managers' set $\Pi_M$. The second transition of the $\Delta$ function represents a failed APPEND invocation. Either the process $p_i$ that invokes this function is not authorized to modify the *listed-values* array, i.e., $p_i \notin \Pi_M$, or the value it tries to append is invalid, i.e., $y \notin \mathcal{S}$. The third transition of the $\Delta$ function captures a valid PROVE operation, where a valid proof is added to the *proofs* array. The function C will be used to express the anti-flickering property of the DenyList implementation. It is a boolean function that outputs either 0 or 1. The fourth transition of the $\Delta$ function represents an invalid PROVE invocation. Either the proof is invalid, or the set on which the proof is issued is not a subset of the *listed-values* array. Finally, the fifth transition represents a READ operation. It returns the *proofs* array and does not modify the object's state.

342

343

344

345

346

347

348

349

350

351

352

The language $\mathcal{L}_{\mathcal{A}}$ does not directly depend on the *listed-values* array. Hence, the validity of a PROVE operation will depend on the choice of the set $\mathcal{A}$.

353

354

# 5 The consensus number of the AllowList object

355

This section provides an AllowList object specification based on the PROOF-LIST object. The specification is then used to analyze the consensus number of the object type.

356

357

<footnote n="6">6 In this article, $\mathcal{L}_A$ can be one of the following languages: a value $v$ belongs to $\mathcal{A}$ (AllowList), or a value $v$ does not belongs to $\mathcal{A}$ (DenyList).</footnote>
39:10 The Synchronization Power of Access Control Objects

We provide a specification of the AllowList object defined as a PROOF-LIST object, where $C(y, \hat{S}) = 1$ and

$$ \forall y \in S, y \in \mathcal{L}_A \Leftrightarrow (A \subseteq S \land y \in A). \qquad (1) $$

In other words, $y$ belongs to a set $A$. Using the third transition of the $\Delta$ function, we can see that $A$ should also be a subset of the *listed-values* array. Hence, this specification supports proofs of set-membership in *listed-values*. A PROOF-LIST object defined for such language follows the specification of the AllowList. To support this statement, we provide an implementation of the object.

To implement the AllowList object, Algorithm 1 uses two Atomic Snapshot objects. The first one represents the *listed-values* array, and the second represents the *proofs* array. These objects are arrays of $N$ entries. Furthermore, we use a function "Proof" that on input of a set $S$ and an element $y$ outputs a proof that $y \in \text{listed-values}$. This function is used as a black box, and can either output an explicit proof—an explicit proof can be the tuple $(y, A)$, where $A \subseteq \text{listed-values}$—or a Zero Knowledge Proof.

**Shared variables**

AS-LV $\leftarrow N$-dimensions Atomic-Snapshot object, initially $\{\emptyset\}^N$;

AS-PROOF $\leftarrow N$-dimensions Atomic-Snapshot object, initially $\{\emptyset\}^N$;

**Operation APPEND($v$) is**

1. If $(v \in S) \land (p \in \Pi_M)$ then

2. local-values $\leftarrow$ AS-LV.Snapshot()[p];

3. AS-LV.update(local-values $\cup$ v, p);

4. Return true;

5. Else return false;

**Operation READ() is**

6. Return AS-PROOF.Snapshot();

**Operation PROVE($v$) is**

7. If $p \notin \Pi_V$ then

8. Return false;

9. A $\leftarrow$ AS-LV.Snapshot();

10. If $v \in A$ then

11. $\pi_{set-memb} \leftarrow$ Proof($v \in A$);

12. proofs $\leftarrow$ AS-PROOF.Snapshot()[p];

13. AS-PROOF.update(proofs $\cup$ (p, A, $\pi_{set-memb}$), p);

14. Return (A, $\pi_{set-memb}$);

15. Else return false.

■ Algorithm 1 Implementation of an AllowList object using Atomic-Snapshot objects

372 ▶ Theorem 4. *Algorithm 1 wait-free implements an AllowList object.*

**Proof.** Let us fix an execution $E$ of the algorithm presented in algorithm 1. Each invocation is a sequence of a finite number of local operations and Atomic-Snapshot accesses. Because the Atomic Snapshot primitive can be wait-free implemented in the read-write shared memory model, each correct process terminates each invocation in a finite number of its own steps.

Let $H$ be the history of the execution $E$. We define $\bar{H}$, the completed history of $H$. Any invocation in $H$ can be completed in $\bar{H}$. We give the completed history $\bar{H}$ of $H$:

■ Any invocation of the APPEND operation that did not reach line 3 can be completed with the line "Return false";

■ Any invocation of the PROVE operation that did not reach line 13 can be completed with the line "Return false";

■ Any invocation of the APPEND operation that reached line 3 can be completed with line 4; and

■ Any invocation of the PROVE operation that reached line 13 can be completed with line 14.

The linearization points of the APPEND, PROVE and READ operations are respectively line 3, line 13 and line 6. For convenience, We call any operation in $\bar{H}$ that returns "false" an invalid operation. We verify that each operation in $\bar{H}$ respects the specification:

■ Any operation in $\bar{H}$ run by a process $p$ that is invalid is an operation that only modifies the internal state of $p$ and that was invoked by a faulty process or that was invoked by a
process without the write to invoke the operation. Therefore, these invalid operations do
not impact the validity and the progress properties of the AllowList object.

If an APPEND operation invoked by a process *p* in $\bar{H}$ returns "true", it implies that *p* reached line 3. Therefore *p* appended a value *v* to the array *listed-values* at the index *p*. Process *p* is the only process able to write at this index. Because the Update operation is atomic, and because *p* is the only process able to write in AS-LV[*p*], the *listed-values* array append-only property is preserved. Furthermore, the element added to *listed-value* belongs to the set *S*, and the process that appends the value belongs to the set of managers $\Pi_M$. Therefore, any invocation of the APPEND operation in $\bar{H}$ that returns "true" fulfills the APPEND validity property. Hence, any APPEND invocation in $\bar{H}$ follows the AllowList specification.

If an invocation of the PROVE operation by a process *p* in $\bar{H}$ returns ($\mathcal{A}$, $\pi$), then $p \in \Pi_V$ reached line 13. Therefore, *p* appended a proof $\pi$ to the *proofs* array at the index *p*, and the proof is a valid proof that $v \in \mathcal{A}$. Process *p* is the only process allowed to modify the *proofs* array at this index. There is no concurrency on the write operation. Furthermore, the set $\mathcal{A}$, is a subset of the AS-LV array (line 9). Because the only way to add an element to the AS-LV array is via an APPEND operation, because we consider the linearization point of the PROVE operation to be at line 13, the PROVE validity property is ensured. The progress property is ensured thanks to the atomicity of the Atomic Snapshot object. If some process executes line 3 of the APPEND operation at time $t_1$, then any correct process that reaches line 8 of the PROVE(*x*) operation at time $t_2 > t_1$ will be valid. Hence, any PROVE invocation in $\bar{H}$ follows the AllowList specification.

A READ operation always returns the values of the AS-PROOF array that were linearized
before the execution of line 6, thanks to the atomicity of the Atomic Snapshot object.
Furthermore, the returned value is always a set of successful PROVE operations (AS-
PROOF). This set is compounded of proofs associated to the name of the process that
invoked the operation. Therefore, the READ validity property is ensured. Hence, any
READ invocation in $\bar{H}$ follows the AllowList specification.

All operations in $\bar{H}$ follow the AllowList specification. Thus, $\bar{H}$ is a legal history of the
AllowList object type, and $H$ is linearizable. To conclude, the algorithm presented in
algorithm 1 is a wait-free implementation of the AllowList object type.

**Corollary 5.** *The consensus number of the AllowList object type is 1.*

# 6 The consensus number of the DenyList object

In the following, we propose two wait-free implementations establishing the consensus number of the DenyList object type. In this section and in the following, we refer to a DenyList with $|\Pi_V| = k$ as a *k*-DenyList object. This analysis of this parameter *k* is the core of the study conducted here. Because it is a statically defined parameter, the knowledge of this parameter can improve efficiency of DenyList implementation by reducing the number of processes that need to synchronize in order to conduct a proof.

## 6.1 Lower bound

Algorithm 2 presents an implementation of a *k*-consensus object using a *k*-DenyList object with $\Pi_M = \Pi_V = \Pi$, and $|\Pi| = k$. It uses an Atomic Snapshot object, AS-LIST, to allow processes to propose values. AS-LIST serves as a helping mechanism [15]. In addition, the algorithm uses the progress and the anti-flickering properties of the PROVE operation of
436

437

438

439

440

441

442

443

444

445

446

447

the $k$-DenyList to enforce the $k$-consensus agreement property. The PROPOSE operation operates as follows. First, a process $p$ tries to prove that the element 0 is not revoked by invoking PROVE(0). Then, if the previous operation succeeds, $p$ revokes the element 0 by invoking APPEND(0). Then, $p$ waits for the APPEND to be effective. This verification is done by invoking multiple PROVE operations until one is invalid. This behavior is ensured by the progress property of the $k$-DenyList object. Once the progress has occurred, $p$ is sure that no other process will be able to invoke a valid PROVE(0) operation. Hence, $p$ is sure that the set returned by the READ operation can no longer grow. Indeed, the READ operation returns the set of valid PROVE operation that occurred prior to its invocation. If no valid PROVE(0) operation can be invoked, the set returned by the READ operation is fixed (with regard to the element 0). Furthermore, all the processes in $\Pi$ share the same view of this set.

448

449

450

451

452

453

Finally, $p$ invokes READ() to obtain the set of processes that invoked a valid PROVE(0) operation. The response to the READ operation will include all the processes that invoked a valid PROVE operation, and this set will be the same for all the processes in $\Pi$ that invoke the PROPOSE operation. Therefore, up to line 7, the algorithm solved the set-consensus problem. To solve consensus, we use an additional deterministic function $f_i : \Pi^i \to \Pi$, which takes as input any set of size $i$ and outputs a single value from this set.

454

455

To simplify the representation of the algorithm, we also use the `separator()` function, which, on input of a set of proofs ($\{(p \in \Pi, \{\hat{S} \subseteq S, P \in \mathcal{P}_{\mathcal{L}_S}\})\}$), outputs `processes`, the set of processes which conducted the proofs, i.e. the first component of each tuple.

**Shared variables**

$k$-dlist $\leftarrow k$-DenyList object;

AS-LIST $\leftarrow$ Atomic Snapshot object, initially $\emptyset$}^k$

**Operation PROPOSE(v) is**

1: AS-LIST.update(v, p);

2: $k$-dlist.PROVE(0);

3: $k$-dlist APPEND(0);

4: Do

5: ret $\leftarrow$ $k$-dlist.PROVE(0);

6: Until (ret $\neq$ false);

7: processes $\leftarrow$ separator($k$-dlist.READ());

8: Return AS-LIST.Snapshot()[f|processes|(processes)].

■ **Algorithm 2** Implementation of a $k$-consensus object using one $k$-DenyList object and one Atomic Snapshot

456

457

► **Theorem 6.** *Algorithm 2 wait-free implements a $k$-consensus object.*

458

459

460

461

462

463

464

465

466

467

468

**Proof.** Let us fix an execution $E$ of the algorithm presented in Algorithm 2. The progress property of the $k$-DenyList object ensures that the while loop in line 4 consists of a finite number of iterations—an APPEND(0) is invoked prior to the loop, hence, the PROVE(0) operation will eventually be invalid. Each invocation of the PROPOSE operation is a sequence of a finite number of local operations, Atomic Snapshot object accesses and $k$-DenyList object accesses which are assumed atomic. Therefore, each process terminates the PROPOSE operation in a finite number of its own steps. Let $H$ be the history of $E$. We define $\bar{H}$ the completed history of $H$, where an invocation of PROPOSE which did not reach line 8 is completed with a line "return false". Line 8 is the linearization point of the algorithm. For convenience, any PROPOSE invocation that returns false is called an failed invocation. Otherwise, it is called a successful invocation.

469

We now prove that all operations in $\bar{H}$ follow the $k$-consensus specification:

470

471

472

■ The process $p$ that invoked a failed PROPOSE operation in $\bar{H}$ is faulty—by definition, the process prematurely stopped before line 8. Therefore, the fact that $p$ cannot decide does not impact the termination nor the agreement properties of the $k$-consensus object.
A successful PROPOSE operation returns AS-LIST.Snapshot()[f processes | processes]. Furthermore, a process proposed this value in line 1. All the processes that invoke PROPOSE conduct an APPEND(0) operation, and wait for this operation to be effective using the while loop at line 4 to 6. Thanks to the anti-flickering property of the k-DenyList object, when the APPEND operation is effective for one process—i.e. the Progress happens, in other words,a PROVE(0) operation is invalid—, then it is effective for any other process that would invoke the PROVE(0) operation. Hence, thanks to the anti-flickering property, when a process obtains an invalid response from the PROPOSE(0) operation at line 5, it knows that no other process can invoke a valid PROVE(0) operation. This implies that the READ operation conducted at line 7 will return a fix set of processes, and all the processes that reach this line will see the same set. Furthermore, because each process invokes a PROPOSE(0) before the APPEND(0) at line 3, at least one valid PROPOSE(0) operation was invoked. Therefore, the processes set is not empty. Because each process ends up with the same set processes, and thanks to the determinism of the function $f_i$, all correct processes output the same value $v$ (Agreement property and non-trivial value). The value $v$ comes from the Atomic Snapshot object, composed of values proposed by authorized processes (Validity property). Hence a successful PROPOSE operation follows the k-consensus object specification.

All operations in $\hat{H}$ follow the k-consensus specification. To conclude, the algorithm presented in algorithm 2 is a wait-free implementation of the k-consensus object type. ◀

► Corollary 7. The consensus number of the k-DenyList object type is at least k.

## 6.2 Upper bound

This section provides a DenyList object specification based on the PROOF-LIST object. The specification is then used to analyze the upper bound on the consensus number of the object type.

We provide an instantiation of the DenyList object defined as a PROOF-LIST object, where:

$$ \forall y \in \mathcal{S}, y \in \mathcal{L}_A \Leftrightarrow (A \subseteq \mathcal{S} \land y \notin A). $$

And where :

$$ C(y, \hat{S}) = \begin{cases} 1, & \text{if } \forall A' \in \hat{S}, y \notin A' \\ 0, & \text{otherwise.} \end{cases} $$

In other words, the first equation ensures that $y$ does not belong to a set $A$, while the second equation ensures that the object fulfills the anti-flickering property. Hence, this instantiation supports proofs of set-non-membership in listed-values. A PROOF-LIST object defined for such language follows the specification of the DenyList. To support this statement, we provide an implementation of the object.

To build a k-DenyList object which can fulfill the anonymity property, it is required to build an efficient helping mechanism that preserves anonymity. It is impossible to disclose directly the value proven without disclosing the user's identity. Therefore, we assume that a process $p$ that invokes the PROVE($v$) operation can deterministically build a cryptographic commitment to the value $v$. Let $C_v$ be the commitment to the value $v$. Then, any process $p' \neq p$ that invokes PROVE($v$) can infer that $C_v$ was built using the value $v$. However, a process that does not invoke PROVE($v$) cannot discover to which value $C_v$ is linked. If the
targeted application does not require the user's anonymity, it is possible to use the plaintext $v$ as the helping value.

Algorithm 3 presents an implementation of a $k$-DenyList object using $k$-consensus objects and Atomic Snapshots. The APPEND and the READ operations are analogous to those of Algorithm 1.

On the other hand, the PROVE operation must implement the anti-flickering property. To this end, a set of $k$-consensus objects and a helping mechanism based on commitments are used.

When a process invokes the PROVE($v$) operation, it publishes $C_v$, the cryptographic commitment to $v$, using an atomic snapshot object. This commitment is published along with a timestamp [16] defined as follows. A local timestamp $(p, c)$ is constituted of a process identifier $p$ and a local counter value $c$. The counter $c$ is always incremented before being reused. Therefore, each timestamp is unique. Furthermore, we build the strict total order relation $\mathcal{R}$ such that $(p, c)\mathcal{R}(p', c') \Leftrightarrow (c < c') \lor ((c = c') \land (p < p'))$. The timestamp is used in coordination with the helping value $C_v$ to ensure termination. A process $p$ that invokes the PROVE($v$) operation must parse all the values proposed by the other processes. If a PROVE($v$') operation was invoked by a process $p'$ earlier than the one invoked by $p$—under the relation $\mathcal{R}$—, then $p$ must affect a set "val" for the PROVE operation of $p'$ via the consensus object. The set "val" is obtained by reading the AS-LV object. The AS-LV object is append-only—no operation removes elements from the object. Furthermore, the sets "val" are attributed via the consensus object. Therefore, this mechanism ensures that the sets on which the PROVE operations are applied always grow.

Furthermore, processes sequentially parse the CONS-ARR using the counter$_p$ variable. This behavior, in collaboration with the properties of the consensus, ensures that all the processes see the same tuples (winner, val) in the same order.

Finally, if a process $p$ observes that a PROVE operation conducted by a process $p' \neq p$ is associated to a commitment $C_v$ equivalent to the one proposed by $p$, then $p$ produces the proof of set-non-membership relative to $v$ and the set "val" affected to $p'$ in its name. We consider that a valid PROVE operation is linearized when this proof of set-non-membership is added to AS-PROOF in line 19. Hence, when $p$ produces its own proof—or if another process produces the proof in its name—it is sure that all the PROVE operations that are relative to $v$ and that have a lower index in CONS-ARR compared to its own are already published in the AS-PROOF Atomic Snapshot object. Therefore, the anti-flickering property is ensured. Indeed, because the affected sets "val" are always growing and because of the total order induced by the CONS-ARR array, if $p$ reaches line 25, it previously added a proof to AS-PROOF in the name of each process $p' \neq p$ that invoked a PROVE($v$) operation and that was attributed a set at a lower index than $p$ in CONS-ARR. Hence, the operation of $p'$ was linearized prior to the operation of $p$.

A PROVE operation can always be identified by its published timestamp. Furthermore, when a proof is added to the AS-PROOF object, it is always added to the index counter$_{p,w}$. Therefore, if multiple processes execute line 19 for the PROVE operation labeled counter$_{p,w}$, the AS-PROOF object will only register a unique value.

Furthermore, we use a function "Proof" that on input of a set $S$ and an element $x$ outputs a proof that $x \notin S$. This function is used as a black box, and can either output an explicit proof—an explicit proof can be the tuple $(x, S)$—, or a Zero Knowledge Proof.

**Theorem 8.** *Algorithm 3 wait-free implements a $k$-DenyList object.*

*Proof.* Let us fix an execution $E$ of the algorithm presented in Algorithm 3. The strict order relation $\mathcal{R}$ used to prioritize accesses to the CONS-ARR array implies that each process that
**Shared variables**

AS-LV ← *N*-dimensions Atomic-Snapshot object, initially {$\emptyset$}$^N$;

AS-Queue ← *N*-dimensions Atomic-Snapshot object, initially {$\emptyset$}$^N$;

CONS-ARR$_p$ ← an array of *k*-consensus objects of size *l* > 0;

AS-PROOF ← *l*-dimensions Atomic-Snapshot object, initially {$\emptyset$}$^l$;

**Local variables**

For each $p \in \Pi_V$:

evaluated$_p$ ← an array of size *l* > 0, initially {$\emptyset$}$^l$;

counter$_p$ ← a positive integer, initially 0;

**Operation APPEND(v) is**

1. If ($v \in S$) ∧ ($p \in \Pi_M$) then

2. local-values ← AS-LV.Snapshot()[p];

3. AS-LV.UPDATE(local-values ∪ v, p);

4. Return true;

5. Else return false;

**Operation PROVE(v) is**

6. If $p \notin \Pi_V$ then

7. Return false;

8. $C_v$ ← Commitment(v);

9. cnt ← counter$_p$;

10. AS-Queue.UPDATE(((cnt, p), C_v), p);

11. queue ← AS-Queue.Snapshot() \ evaluated$_p$;

12. While (cnt, p) ∈ queue do

13. oldest ← the smallest clock value in queue under $\mathcal{R}$;

14. prop ← (oldest, AS-LV.snapshot());

15. (winner, val) ← CONS-ARR[counter$_p$].propose(prop);

16. ((counter$_{p_w}$, p_w), C*) ← winner;

17. If $C^* = C_v \land v \notin val$ then

18. $\pi_{SNM} \leftarrow \text{Proof}(v \notin val)$;

19. AS-PROOF.update((p_w, val, $\pi_{SNM}$, winner), counter$_{p_w}$);

20. evaluated$_p$ ← evaluated$_p$ ∪ winner;

21. queue ← queue \ winner;

22. counter$_p$ ← counter$_p$ + 1;

23. If $v \notin val$ then

24. Return (val, $\pi_{SNM}$);

25. Else return false;

**Operation READ() is**

26. Return AS-PROOF.Snapshot();

**Algorithm 3** *k*-DenyList object type implementation using *k*-consensus objects and Atomic Snapshot objects.

enters the while loop in line 12 will only iterate a finite number of times. Furthermore, we assume that *k*-consensus objects and atomic-snapshot objects are atomic. Therefore, each process returns from a PROVE, an APPEND, or a READ operation in a finite number of its own steps.

Let $H$ be the history of $E$. We define $\bar{H}$, the completed history of $H$. We associate a specific response with all pending invocations in $H$. The associated responses are:

Any invocation of the APPEND operation that did not reach line 3 can be completed with the line "**Return** false".

Any invocation of the PROVE operation that did not reach line 10 can be completed with the line "**Return** false".

Any pending invocation of the PROVE operation by the process *p* that reached line 10 is completed with the line "**Return** (val, $\pi_{SNM}$);" if (*p*, value, $\pi_{SNM}$, winner) is in the AS-PROOF array, and the value added by process *p* in line 10 is "winner". Otherwise, the operation is completed with the line "**Return** false".

Any pending invocation of the APPEND operation that reached line 3 can be completed with line 4.

The linearization point of the APPEND and READ operations are respectively at line 3 and 26. Let us consider a valid PROVE operation invoked by a process *p* that is attributed a tuple (winner, val) at the index counter$_{p_w}$ of the CONS-ARR array. We say this operation is linearized when the first AS-PROOF.update labeled with counter$_{p_w}$ in line 19 is executed by any process.

For convenience, we call operations that return false invalid operations. The consensus objects in CONS-ARR are accessed at most once by each process. There are only $k = |\Pi_V|$ processes allowed to access these objects. Therefore, the *k*-consensus objects in the array always return a value different from $\emptyset$. We now prove that all operations in $\bar{H}$ follow the DenyList specification:

An invalid APPEND operation in $\bar{H}$ only modifies the internal state of the process. This operation does not modify the state of the shared object. It is either invoked by an unauthorized process which fails in line 1, or by a faulty process. This operation follows the specification;

An invalid PROVE operation in $\bar{H}$ is an operation that returns false in line 7 or 25. In
the first case, the process was not authorized to propose a proof. In the second case, the value *v* used by the process is already inside the set "val" the process was attributed by the consensus in line 15. This set is produced from the values added to the AS-LV object. This object begins as an empty set, and values inside this set can only be added using the APPEND operation. Therefore, the PROVE validity property is ensured.

If an invocation of the APPEND operation in $\bar{H}$ returns true, it implies that process *p* appended a value *v* to the *listed-values* array, at the index *p* at line 3. Because the WRITE operation is atomic, and because *p* is the only process able to write in AS-ACC[*p*], the *listed-values* array append-only property is preserved. Hence a successful APPEND operation follows the specification.

If an invocation of the PROVE operation in $\bar{H}$ returns True, it implies that: 1) process *p* was attributed a *k*-consensual set "val" on line 15, 2) from line 17, *v* $\notin$ val, and 3) a proof that *v* $\notin$ "val" was added to the AS-PROOF object, either by *p* or by another process performing the helping mechanism. First, to prove the progress property, we assume a history where first, a process *p*′ obtains a positive response from an APPEND(*v*) operation. Afterward, a process *p* invokes a PROVE(*v*) operation. Therefore, the value *v* will already be included in the AS-LV object at this time because *p*′ received a positive response from its invocation. Any process that executes the line 14 of the PROVE operation after the invocation of *p* will propose a set where *v* is included. Therefore, the set "val" that will be affected to *p* by the consensus on line 15 will include *v*. The PROVE(*v*) operation invoked by *p* will be invalid. The progress property is ensured.

Second, the anti-flickering property is ensured by the helping mechanism and the *k*-consensus objects used from line 10 to 22. The processes in $\Pi_V$ that invoke the PROVE(*v*) operation will sequentially attribute a set "val" to each proving process, using the set of *k*-consensus objects. Furthermore, this sequential attribution takes into account the evolution of the AS-LV object. Therefore, the set associated with the object CONS-ARR[*i* − 1] is always included in the set associated with the object CONS-ARR[*i*].

Furthermore, the CONS-ARR array is browsed sequentially by each process invoking the PROVE operation. Therefore, if a process *p* that invokes a PROVE(*v*) operation with a timestamp *t*, and this invocation is not valid in the end, *p* will nonetheless linearize all the PROVE(*v*) operations that have a lower timestamp than *t* before returning from the operation. Hence, all the valid PROVE(*v*) operations will be linearized before the response of *p*'s invocation, and any invocation of a PROVE(*v*) operation that occurs after the response of *p*'s invocation will fail.

Third, the PROVE validity property directly follows from point (2) and the anti-flickering property. Hence a successful PROVE operation follows the specification.

A READ operation always returns, and thanks to the atomicity of the Atomic Snapshot object, it always returns the most up-to-date version of the AS-PROOF array.

All operations in $\bar{H}$ follow the *k*-DenyList specification. Therefore the algorithm presented in Algorithm 3 is a wait-free implementation of the *k*-DenyList object type. ◀

The following corollary follows from Theorem 6 and Theorem 8.

► **Corollary 9.** The *k*-DenyList object type has consensus number *k*.

7 Discussion

This section presents several applications where the AllowList and the *k*-DenyList can be used to determine consensus number of more elaborate objects. More importantly, the analysis of
the consensus of these use cases makes it possible to determine if actual implementations achieve optimal efficiency in terms of synchronization. If not, we use the knowledge of the consensus number of the AllowList and DenyList objects to give intuitions on how to build more practical implementations. More precisely, the fact that consensus numbers of AllowList and DenyList objects are (in most cases) smaller than *n* implies that most implementations can reduce the number of processes that need to synchronize in order to implement such distributed objects. The liveness of many consensus protocols is only ensured when the network reaches a synchronous period. Therefore, reducing the number of processes that need to synchronize can increase the system's probability of reaching such synchronous periods. Thus, it can increase the effectiveness of such protocols.

## 7.1 Revocation of a verifiable credential

We begin by analyzing Sovrin's Verifiable-Credential revocation method using the DenyList object [4]. Sovrin is a privacy-preserving Distributed Identity Management System (DIMS). In this system, users own credentials issued by entities called issuers. A user can employ one such credential to prove to a verifier they have certain characteristics. An issuer may want to revoke a user's credential prematurely. To do so, the issuer maintains an append-only list of revoked credentials. When a user wants to prove that their credential is valid, they must provide to the verifier a valid ZKP of set-non-membership proving that their credential is not revoked, i.e. not in the DenyList. In this application, the set of managers $\Pi_M$ consists solely of the credential's issuer. Hence, the proof concerns solely the verifier and the user. The way Sovrin implements this verification interaction is by creating an ad-hoc peer-to-peer consensus instance between the user and the verifier for each interaction. Even if the resulting DenyList has consensus number 2, Sovrin implements the APPEND operation using an SWMR stored on a blockchain-backed ledger (which requires synchronizing the *N* processes of the system). Our results suggest instead that Sovrin's revocation mechanism could be implemented without a blockchain. The APPEND operation could be implemented using FIFO reliable broadcast, and the PROVE operation could be implemented using pairwise consensus between users and verifiers.

## 7.2 The Anonymous Asset Transfer object

The anonymous asset transfer object is another application of the DenyList and the AllowList objects. As described in Appendix B, it is possible to use these objects to implement the asset transfer object described in [9]. Our work generalizes the result by Guerroui et al. [9]. Guerraoui et al. show that a joint account has consensus number *k* where *k* is the number of agents that can withdraw from the account. We can easily prove this result by observing that withdrawing from a joint account requires a denylist to record the already spent coins. Nevertheless, our ZKP capable construction makes it possible to show that an asset transfer object where the user is anonymous, and its transactions are unlinkable also has consensus number *k*, where *k* is the number of processes among which the user is anonymous. The two main implementations of Anonymous Asset Transfer, ZeroCash and Monero [17, 18], use a blockchain as their main double spending prevention mechanism. While the former provides anonymity on the whole network, the second only provides anonymity among a subset of the processes involved in the system. Hence, this second implementation could reduce its synchronization requirements accordingly.

Furthermore, our implementation uses AllowList as *ex-nihilo*-coin-creation prevention mechanism. Hence, both security properties of an anonymous asset transfer object can be
enforced separately. Using the fact that AllowLists have consensus number 1, this result
implies that this part of the protocol could be handled more efficiently. For example, the
most space and resource-intensive part of the ZeroCash protocol is the ex-nihilo-coin-creation
prevention mechanism. This part of the protocol is implemented in a synchronous way,
i.e., all processes synchronize to conduct it, which is, as we demonstrated, sub-optimal.
Therefore, this analysis may lead to a more efficient ZeroCash-like asset transfer protocol
implementation.

7.3 Distributed e-vote systems

Finally, another direct application of the DenyList object is the blind-signature-based e-vote
system with consensus number *k*, *k* being the number of voting servers, which we present in
Appendix C. Most distributed implementations of such systems also use blockchains, whereas
only a subset of the processes involved actually require synchronization.

8 Related Works

Bitcoin and blockchain

Even though distributed consensus algorithms were already largely studied [19, 20, 21, 22, 23], the rise of Ethereum—and the possibilities offered by its versatile smart contracts—led to new ideas to decentralized already known applications. Among those, e-vote and DIMS [4] are two examples.

Blockchains increased the interest in distributed versions of already existing algorithms. However, these systems are usually developed with little concern for the underlying theoretical basis they rely on. A great example is trustless money transfer protocols or crypto money. The underlying distributed asset-transfer object was never studied until recently. A theoretical study proved that a secure asset-transfer protocol does not need synchronicity between network nodes [9]. Prior to this work, all proposed schemes used a consensus protocol, which cannot be deterministically implemented in an asynchronous network [24]. The result is that many existing protocols could be replaced by more efficient, Reliable Broadcast [23] based algorithms. This work leads to more efficient implementation proposal for money transfer protocol [10]. Alpos et al. then extended this study to the Ethereum ERC20 smart contracts [12]. This last paper focuses on the asset-transfer capability of smart contracts. Furthermore, the object described has a dynamic consensus number, which depends on the processes authorized to transfer money from a given account. Furthermore, this work and the one from Guerraoui et al. [9] both analyze a specific object that is not meant to be used to find the consensus number of other applications. In contrast, our work aims to be used as a generic tool to find the consensus number of numerous systems.

E-vote

An excellent example of the usage of DenyList is to implement blind signatures-based e-vote
systems [25]. A blind signature is a digital signature where the issuer can sign a message
without knowing its content. Some issuer signs a cryptographic commitment—a cryptographic
scheme where Alice hides a value while being bound to it [26]—to a message produced by
a user. Hence, the issuer does not know the actual message signed. The user can then
un-commit the message and present the signature on the plain-text message to a verifier.
The verifier then adds this message to a DenyList. A signature present in the DenyList is no
longer valid. Such signatures are used in some e-vote systems [27, 28]. In this case, the blind
signature enables anonymity during the voting operation. This is the e-vote mechanism that we study in this article. They can be implemented using a DenyList to restrain a user from voting multiple times. This method is explored in Appendix C

There exists two other way to provide anonymity to the user of an e-vote system. The first one is to use a MixNet [29, 30, 31]. MixNet is used here to break the correlation between a voter and his vote. Finally, anonymity can be granted by using homomorphic encryption techniques [32, 33].

Each technique has its own advantages and disadvantages, depending on the properties of the specific the e-vote system. We choose to analyze the blind signature-based e-vote system because it is a direct application of the distributed DenyList object we formalize in this paper.

## Anonymous Money Transfer

Blockchains were first implemented to enable trustless money transfer protocols. One of the significant drawbacks of this type of protocol is that it only provides pseudonymity to the user. As a result, transfer and account balances can be inspected by anyone, thus revealing sensitive information about the user. Later developments proposed hiding the user's identity while preventing fraud. The principal guarantees are double-spending prevention—i.e., a coin cannot be transferred twice by the same user—and *ex nihilo* creation prevention—i.e., a user cannot create money. Zcash [18] and Monero [17] are the best representative of anonymous money transfer protocols. The first one uses an AllowList to avoid asset creation and a DenyList to forbid double spending, while the second one uses ring signatures. We show in Appendix B that the DenyList and AllowList objects can implement an Anonymous Money Transfer object, and thus, define the synchronization requirements of the processes of the system.

# 9 Conclusion

This paper presented the first formal definition of distributed AllowList and DenyList object types. These definitions made it possible to analyze their consensus number. This analysis concludes that no consensus is required to implement an AllowList object. On the other hand, with a DenyList object, all the processes that can propose a set-non-membership proof must synchronize, which makes the implementation of a DenyList more resource intensive.

The definition of AllowList and DenyList as distributed objects made it possible to thoroughly study other distributed objects that can use AllowList and DenyList as building blocks. For example, we discussed authorization lists and revocation lists in the context of the Sovrin DIMS. We also provided several additional examples in the Appendix. In particular, we show in Appendix B that an association of DenyList and AllowList objects can implement an anonymous asset transfer protocol and that this implementation is optimal in terms of synchronization power. This result can also be generalized to any asset transfer protocol, where the processes act as proxies for the wallet owners. In this case, synchronization is only required between the processes that can potentially transfer money on behalf of a given wallet owner.

## Acknowledgments

We wish to thank the anonymous reviewers for their insightful comments and remarks that led to significant improvements to our paper. This work was funded by the SOTERIA
39:20 The Synchronization Power of Access Control Objects

<footnote n="770">770 project. SOTERIA has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No101018342. This content reflects only 771 the author's view. The European Agency is not responsible for any use that may be made of 772 the information it contains.
773</footnote>
References

1 Gaby G. Dagher, Praneeth Babu Marella, Matea Milojkovic, and Jordan Mohler. Broncovote: Secure voting system using ethereum's blockchain. In *ICISSP*, 2018.

2 Ethereum name service documentation. online - https://docs.ens.domains/ - accessed 23/11/2022.

3 Harry A. Kalodner, Miles Carlsten, Paul Ellenbogen, Joseph Bonneau, and Arvind Narayanan. An empirical study of namecoin and lessons for decentralized namespace design. In *Workshop on the Economics of Information Security*, 2015.

4 Sovrin: A protocol and token for self-sovereign identity and decentralized trust. Technical report, Sovrin Foundation, 2018.

5 Lundkvist, Heck, Torstensson, Mitton, and Sena. Uport: A plateform for self-sovereign identity. Technical report, Uport.

6 Ming K. Lim, Yan Li, Chao Wang, and Ming-Lang Tseng. A literature review of blockchain technology applications in supply chains: A comprehensive analysis of themes, methodologies and industries. *Computers and Industrial Engineering*, 154:107133, 2021.

7 Jyoti Grover. Security of vehicular ad hoc networks using blockchain: A comprehensive review. *Vehicular Communications*, 34:100458, 2022.

8 Maurice P Herlihy and Jeannette M Wing. Linearizability: A correctness condition for concurrent objects. *ACM Transactions on Programming Languages and Systems*, 12(3):463–492, 1990.

9 Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič, and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. PODC ’19, page 307–316, 2019.

10 Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. Money Transfer Made Simple: a Specification, a Generic Algorithm, and its Proof. *Bulletin European Association for Theoretical Computer Science*, 132, October 2020.

11 Maurice Herlihy. Wait-free synchronization. *ACM Trans. Program. Lang. Syst.*, 13(1):124–149, jan 1991.

12 Orestis Alpos, Christian Cachin, Giorgia Azzurra Marson, and Luca Zanolini. On the synchronization power of token smart contracts. In *41st IEEE ICDCS*, pages 640–651, 2021.

13 Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. *JACM*, 40(4):873–890, sep 1993.

14 Daniel Benarroch, Matteo Campanelli, Dario Fiore, Kobi Gurkan, and Dimitris Kolonelos. Zero-knowledge proofs for set membership: Efficient, succinct, modular. In *Financial Cryptography and Data Security*. Springer Berlin Heidelberg, 2021.

15 Keren Censor-Hillel, Erez Petrank, and Shahar Timnat. Help! PODC ’15, page 241–250, 2015.

16 Leslie Lamport. Time, clocks and the ordering of events in a distributed system. *Communications of the ACM 21*, (7), 558-565, July 1978.

17 Nicolas van Saberhagen. Cryptonote v 2.0, october 2013.

18 Eli Ben Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized anonymous payments from bitcoin. In *2014 IEEE Symposium on Security and Privacy*, pages 459–474, May 2014.

19 Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. OSDI ’99, page 173–186, 1999.

20 Leslie Lamport. *The Part-Time Parliament*, volume 16. 1998.

21 Miguel Castro and Barbara Liskov. Proactive recovery in a Byzantine-Fault-Tolerant system. In *OSDI 2000*, October 2000.

22 Pierre-Louis Aublin, Sonia Ben Mokhtar, and Vivien Quéma. Rbft: Redundant byzantine fault tolerance. In *IEEE 33rd International Conference on Distributed Computing Systems*, pages 297–306, 2013.

23 Gabriel Bracha. Asynchronous byzantine agreement protocols. *Information and Computation*, 75(2):130–143, 1987.
39:22 The Synchronization Power of Access Control Objects

825

24 Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. *J. ACM*, 32(2):374–382, apr 1985.

826

827

25 David Chaum. Blind signatures for untraceable payments. In *Advances in Cryptology*, pages 199–203, 1983.

828

829

26 Torben Pryds Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In *Advances in Cryptology — CRYPTO '91*, pages 129–140, 1992.

830

831

27 Atsushi Fujioka, Tatsuaki Okamoto, and Kazuo Ohta. A practical secret voting scheme for large scale elections. In *AUSCRYPT '92*, pages 244–251, 1993.

832

833

28 Miyako Ohkubo, Fumiaki Miura, Masayuki Abe, Atsushi Fujioka, and Tatsuaki Okamoto. An improvement on a practical secret voting scheme. In *Information Security*, pages 225–234, 1999.

834

835

836

29 Ari Juels, Dario Catalano, and Markus Jakobsson. Coercion-resistant electronic elections. *WPES '05*, page 61–70, 2005.

837

838

30 Markus Jakobsson, Ari Juels, and Ronald L. Rivest. Making mix nets robust for electronic voting by randomized partial checking. In *11th USENIX Security Symposium*, August 2002.

839

840

31 Michael R. Clarkson, Stephen Chong, and Andrew C. Myers. Civitas: Toward a secure voting system. *IEEE SSP*, pages 354–368, 2008.

841

842

32 Olivier Baudron, Pierre-Alain Fouque, David Pointcheval, Jacques Stern, and Guillaume Poupard. Practical multi-candidate election system. *PODC '01*, page 274–283, 2001.

843

844

33 Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A secure and optimally efficient multi-authority election scheme. In *EUROCRYPT '97*, pages 103–118, 1997.

845

846

34 Gang Wang, Zhijie Jerry Shi, Mark Nixon, and Song Han. Sok: Sharding on blockchain. In *Proceedings of the 1st ACM Conference on Advances in Financial Technologies*, page 41–61, 2019.

847

848

849

35 Satoshi Nakamoto. Bitcoin: A peer-topeer electronic cash system. Technical report, march 2009.

850

851

36 Andreas Pfitzmann and Marit Hansen. Anonymity, unlinkability, undetectability, unobservability, pseudonymity, and identity management–a consolidated proposal for terminology. *Version v0*, 31, 01 2007.

852

853

A Variations on the listed-values array

854

855

856

857

In the previous sections, we assumed the *listed-values* array was append-only. Some use cases might need to use a different configuration for this array. In this section, we want to explore the case where the *listed-values* array is no longer append-only.

858

One-process only

859

860

861

862

863

864

865

866

867

868

869

870

We will first explore a limited scenario where the processes can only remove the values they wrote themselves. In this case, there are no conflicts on the append and remove operations. The *listed-values* array can be seen as an array of |Π<sub>V</sub>| values. A process *p*<sub>i</sub> can write the *i*-th index of the *listed-values* array. It is the only process that modifies this array. Therefore, there are no conflicts upon writing. We would need to add a REMOVE operation to the AllowList and DenyList object. Because of this REMOVE operation, the AllowList could act as a DenyList. Indeed, let us assume the managers adds all elements of the universe of the possible identifiers to the AllowList in the first place. Then, this AllowList can implement a DenyList object, where the REMOVE operation of the AllowList is equivalent to the APPEND operation of the DenyList. Hence, the AllowList object would need an anti-flickering property to prevent concurrent PROVE operations from yielding conflicting results. This implies that an AllowList object implemented with a REMOVE operation
is equivalent to a DenyList object and has consensus number $k$, where $k$ is the number of processes in $\Pi_V$.

### Multi-process

The generalization of the previous single-write-remove *listed-values* array is a *listed-values* array where $k_{AR}$ (AR for APPEND/REMOVE) processes can remove a value appended by process $p_i$. We assume each process $p$ is authorized to conduct APPEND and REMOVE operations on its "own" register. Furthermore, each process $p_i$ has a predefined authorization set $A_i \subseteq \Pi_M$, defining which processes can APPEND or REMOVE on $p_i$'s register. We always have $p_i \in A_i$. If $p_j \in A_i$, then $p_j$ is allowed to "overwrite" (remove) anything $p_i$ wrote. In this case, all authorized processes need to synchronize in order to write a value on the *listed-values* array. More precisely, we can highlight two cases.

The first case is the "totally shared array" case, where all processes share the same $A_i = \Pi_M$. Any modifications on the *listed-values* array by one process $p_i$ can be in competition with any other process $p_j \in \Pi_M$. Therefore, there must be a total synchronization among all the processes of the managers' set to modify the *listed-values* array. When such behaviour is needed, both AllowList and DenyList require solving consensus among at least $|\Pi_M|$ processes to implement the APPEND and REMOVE operations.

The second case is the "cluster" case: a subset of processes share a sub-array, which they can write. In this case, each process in a given cluster must synchronize before writing (or removing) a value. The synchronization required is only between this cluster's $k_{AR}$ authorized process. This corresponds to some extent to a sharded network [34].

## B Anonymous Asset-Transfer object type

Decentralized money transfer protocols were popularized by Bitcoin [35]. Guerraoui et al. proposed a theoretical analysis [9] that proved that the underlying object, the asset transfer object, has consensus number 1 if each account is owned by a single process. This result implies that the expensive Proof Of Work (POW) leveraged by the Bitcoin implementation is an over-engineered solution in a message-passing setting. A less expensive solution based on the Reliable-Broadcast primitive works as well [10]. The paper by Guerraoui et al. also studies the case where multiple processes share accounts. In this case, the consensus number of the resulting object is $k$, the maximum number of processes sharing a given account.

These works give a good insight into the problem of asset transfer, but they only study pseudonymous systems, where all transactions can be linked to a single pseudonym. With the growing interest in privacy-enhancing technologies, cryptocurrency communities try to develop anonymous and unlinkable money transfer protocols [18, 17]. The subsequent question is to know the consensus number associated with the underlying distributed object. The formalization of the AllowList and the DenyList objects presented in this article makes it possible to answer this question. This section is dedicated to this proof.

### B.1 Problem formalization

#### Asset-Transfer object type definition

The Asset-Transfer object type allows a set of processes to exchange assets via a distributed network. We reformulate the definition proposed by Guerraoui et al. [9] to describe this object:
► **Definition 10.** The (pseudonymous) Asset-Transfer object type proposes two operations, TRANSFER and BALANCE. The object type is defined for a set Π of processes and a set W of accounts. An account is defined by the amount of assets it contains at time t. Each account is initially attributed an amount of assets equal to $v_0 \in \mathbb{Z}^{+*}$. We define a map $\mu: \mathcal{W} \to \{0, 1\}^{\Pi^|}$ which associates each account to the processes that can invoke TRANSFER operations for these wallets. The Asset Transfer object type supports two operations, TRANSFER and BALANCE. When considering a TRANSFER $(i, j, v)$ operation, $i \in \mathcal{W}$ is called the initiator, $j \in \mathcal{W}$ is called the recipient, and $v \in \mathbb{N}$ is called the amount transferred. Let $T(i, j)_t$ be the sum of all valid TRANSFER operations initiated by process $i$ and received by process $j$ before time $t$. These operations respect three properties:

■ (Termination) TRANSFER and BALANCE operations always return if they are invoked by a correct process.

■ (TRANSFER Validity) The validity of an operation TRANSFER$(x, y, v)$ invoked at time $t$ by a process $p$ is defined in a recursive way. If no TRANSFER$(x, i, v)$, $\forall i \in \mathcal{W}$ was invoked before time $t$, then the operation is valid if $v \le v_0$ and if $p \in \mu(x)$. Otherwise, the operation is valid if $v \le v_0 + \sum_{i \in \mathcal{W}} T(i, x)_t - \sum_{j \in \mathcal{W}} T(x, j)_t$ and if $p \in \mu(x)$.

■ (BALANCE Validity) A BALANCE operation invoked at time $t$ is valid if it returns $v_0 + \sum_{i \in \mathcal{W}} T(i, x)_t - \sum_{j \in \mathcal{W}} T(x, j)_t$ for each account $x$.

The Asset transfer object is believed to necessitate a double-spending-prevention property. This property is captured by the TRANSFER Validity property of Theorem 10. Indeed, the double-spending-prevention property is defined to avoid ex-nihilo money creation. In a wait-free implementation, a valid transfer operation is atomic. Therefore, double spending is already prevented. A TRANSFER operation takes into account all previous transfers from the same account.

The paper by Guerraoui et al. [9] informs us that the consensus number of such an object depends on the map $\mu$. If $\sum_{i \in \{0, \dots, |\Pi|\}} \mu(w)[i] \le 1$, $\forall w \in \mathcal{W}$, then the consensus number of the object type is 1. Otherwise, the consensus number is $\max_{w \in \mathcal{W}}(\sum_{i \in \{0, \dots, |\Pi|\}} \mu(w)[i])$. In other words, the consensus number of such object type is the maximum number of different processes that can invoke a TRANSFER operation on behalf of a given wallet.

From continuous balances to token-based Asset-Transfer

The definition proposed by Guerraoui et al. uses a continuous representation of the balance of each account. Implementing anonymous money transfer with such a representation would require a mechanism to hide the transaction amounts [18]. As such a mechanism would not affect the synchronization properties of the anonymous-money-transfer object, we simplify the problem by considering a token-based representation. This means that the algorithm can transfer only tokens of a predefined weight. To move from one representation to the other, we operate a bijection between the finite history of a continuous account-based money representation and a token-based representation.

Let $\mathcal{W}$ be a set of accounts. Let $\mu: \mathcal{W} \to \{0, 1\}^{\Pi}$ be the owner map, and let $D_{(I,V)}$ be a discretization function such that $D_{(I,V)}: S \subseteq \mathbb{R}^+ \to \mathbb{N}^I$, for some $I \in \mathbb{N}^*$. $D_{(I,V)}$ is defined as follows:

$$ 
\begin{array}{l}
\forall i \in \{0, \dots, I\}, \quad \forall x \in S: \displaystyle\sum_{i=1}^{I} D_{(I,V)}(x)[i] = x \\
\text{where } D_{(I,V)}(x) = ((D_{(I,V)}(x)[i] = V) \lor (D_{(I,V)}(x)[i] = 0)).
\end{array}
$$
We need to define $\mathcal{S}$ in order to make $D_{(I,V)}$ bijective. Let the array $\{\text{InitBal}_1, \dots, \text{InitBal}_{|W|}\}$ be the initial balances of the $|W|$ accounts, with $\text{InitBal}_i \in \mathbb{R}^+, \forall i \in \{1, \dots, p\}$. Let us fix an execution $E$ of an Asset Transfer object. Let $H$ be the history of $E$, and let $\bar{H}$ be the linearization of this history. Let us assume the amounts transferred are in $\mathbb{N}^{*+}$. Let $T$ be the array of transferred amounts. Let $V$ be the greatest common divisor of all the elements in $T$ and the initial balance array. Let $\text{TotalTrans}_i$ be the total number of transactions the account receives $i$ in $\bar{H}$. Let $\text{balance}(i, j)$ be the balance of the account $i$ after its $j$'th asset reception. Let $I$ be the greatest amount of money possessed by an account in $\bar{H}$ divided by $V$, i.e., $I = \frac{\max_{i \in \{1, \dots, |W|\}}(\max_{j \in \{1, \dots, \text{TotalTrans}_i\}}(\text{balance}(i, j)))}{V}$. Hence, we can apply $D_{(I,V)}$ to each element of the initial balance array. We can define $\mathcal{S}$ as the infinite set $\{0, V, 2V, 3V, \dots\}$. Using such an $\mathcal{S}$, the map $D_{(I,V)}$ is bijective when applied to $\bar{H}$.

Thanks to this bijection, all transactions can be seen as a given amount of "coins" transferred. A coin corresponds to a given amount of asset $V$. The amount of coins of each account is represented by an array of size $I$, with values $V$ or 0. Hence, we have a discretized version of the asset transfer object, and there exists a bijection between the continuous setup and the discretized setup.

We use the discrete version of the Asset Transfer object in the following to reason about Anonymous Asset transfers. Specifically, a transfer in the tokenized version for a value of $kV$ consists of $k$ TRANSFER operations, each transferring a token of value $V$.

## Anonymity set

Let $\mathcal{S}$ be a set of actors. We define "anonymity" as the fact that, from the point of view of an observer, $o \notin \mathcal{S}$, the action, $v$, of an actor, $a \in \mathcal{S}$, cannot be distinguished from the action of any other actor, $a' \in \mathcal{S}$. We call $\mathcal{S}$ the anonymity set of $a$ for the action $v$ [36].

Implementing Anonymous Asset Transfer requires hiding the association between a token and the account or process that owns it. If a "token owner" transfers tokens from the same account twice, these two transactions can be linked together and are no longer anonymous. Therefore, we assume that the "token owner" possesses offline proofs of ownership of tokens. These proofs are associated with shared online elements, allowing other processes to verify the validity of transactions. We call *wallet* the set of offline proofs owned by a specific user. We call the individual who owns this wallet the *wallet owner*. It is important to notice that a wallet owner can own multiple wallets, whereas we assume a wallet is owned by only one owner. Furthermore, we assume each process can invoke TRANSFER operations on behalf of multiple wallet owners. Otherwise, a single process, which is in most cases identified by its ip-address or its public key, would be associated with a single wallet. Thus, the wallet would be associated with a unique identifier, and the transactions it would operate could not be anonymous. With the same reasoning, we can assume that a wallet owner can request many processes to invoke a TRANSFER operation on his or her behalf. Otherwise, the setup would not provide "network anonymity", but only "federated anonymity", where the wallet is anonymous among all other wallets connected to this same process. In our model, processes act as proxies.

## The Anonymous Asset-Transfer object type

We give a new definition of the Asset-Transfer object type that takes anonymity into account. The first difference between a Pseudonymous Asset Transfer object type and an anonymous one is the absence of a BALANCE operation. The wallet owner can compute the balance of its own wallet using a LOCALBALANCE function that is not part of the distributed
object. The TRANSFER operation is also slightly modified. Let us consider a sender that wants to transfer a token $T_O$ to a recipient. The recipient creates a new token $T_R$ with the associated cryptographic offline proofs (in practice, $T_R$ can be created by the sender using the public key of the recipient). Specifically, it associates it with a private key. This private key is known only to the recipient: its knowledge represents, in fact, the possession of the token. Prior to the transfer operation, the recipient sends token $T_R$ to the sender. The sender destroys token $T_O$ and activates token $T_R$. The destruction prevents double spending, and the creation makes it possible to transfer the token to a new owner while hiding the recipient's identity. Furthermore, this process of destruction and creation makes it possible to unlink the usages of what is ultimately a unique token.

Each agent maintains a local wallet that contains the tokens (with the associated offline proofs) owned by the agent. The owner of a wallet $w$ can invoke TRANSFER operations using any of the processes in $\mu(w)$. A transfer carried out from a process $p$ for wallet $w$ is associated with an anonymity set $\mathcal{A}S_p^w$ of size equal to the number of wallets associated with process $p$: $|\mathcal{A}S_p^w| = \sum_{i \in W} \mu(i)[p]$. The setup with the maximal anonymity set for each transaction is an Anonymous Asset Transfer object where each wallet can perform a TRANSFER operation from any process: i.e., $\mu(i) = \{1\}^{|\Pi|}, \forall i \in W$. The token-based Anonymous Asset Transfer object type is defined as follows:

► **Definition 11.** *The Anonymous Asset Transfer object type supports only one operation: the TRANSFER operation. It is defined for a set $\Pi$ of processes and a set $W$ of wallets. An account is defined by the amount of tokens it controls at time $t$. Each account is initially attributed an amount $v_0$ of tokens. We define a map $\mu: W \to \{0, 1\}^{|\Pi|}$ which associates each wallet to the processes that can invoke TRANSFER on behalf of these wallets. When considering a TRANSFER($T_O, T_R$) operation, $T_O$ is the cryptographic material of the initiator that proves the existence of a token $T$, and $T_R$ is the cryptographic material produced by the recipient used to create a new token. The TRANSFER operation respects three properties:*

1929 (Termination) The TRANSFER operation always returns if it is invoked by a correct process.

1931 (TRANSFER Validity) A TRANSFER($T_O, T_R$) operation invoked at time $t$ is valid if:

1932 (Existence) The token $T_O$ already existed before the transaction, i.e., either it is one of the tokens initially created, or it has been created during a valid TRANSFER($T'_O, T_O$) operation invoked at time $t' < t$.

1935 (Double spending prevention) No TRANSFER($T_O, T'_R$) has been invoked at time $t'' < t$.

1937 (Anonymity) A TRANSFER($T_O, T_R$) invoked by process $p$ does not reveal information about the owner $w$ and $w'$ of $T_O$ and $T_R$, except from the fact that $w$ belongs to the anonymity set $\mathcal{A}S_p^w$.

1940 Let us extract knowledge from this definition. The TRANSFER validity property implies that the wallet owner can provide existence and non-double-spending proofs to the network. It implies that any other owner in the same anonymity set and with the same cryptographic material (randomness and associated element) can require the transfer of the same token.

1944 We know the material required to produce a TRANSFER proof is stored in the wallet. Furthermore, we can assume that all the randomness used by a given wallet owner is produced by a randomness Oracle that derives a seed to obtain random numbers. Each seed is unique to each wallet. We assume the numbers output by an oracle seems random to an external observer, but two processes that share the same seed will obtain the same set of random numbers in the same order.
Finally, a transaction must be advertised to other processes and wallet owners via the TRANSFER operation. Therefore, proofs of transfer are public. We know these proofs are deterministically computed thanks to our deterministic random oracle model. Furthermore, only one sender and recipient are associated with each transfer operation. Therefore, the public proof cryptographically binds (without revealing them) the sender to the transaction. Hence, the public proof is a cryptographic commitment, which can be opened by the sender or any other actor who knows the same information as the sender.

In order to study the consensus number of this object, we consider that wallet owners can share their cryptographic material with the entire network, thereby giving up their anonymity. This would not make any sense in an anonymous system, but it represents a valuable tool to reason about the consensus number of the object. This sharing process can be implemented by an atomic register (and therefore has no impact on the consensus number, as we discuss later).

Processes can derive the sender's identity from the shared information using a local "uncommit" function. The "uncommit" function takes as input an oracle, a random seed, token elements, and an "on-ledger" proof of transfer of a token and outputs a wallet owner ID if the elements are valid. Otherwise, it outputs $\emptyset$.

## B.2 Consensus number of the Anonymous Asset-Transfer object type

### Lower bound

Algorithm 4 presents an algorithm that implements a $k$-consensus object, using only $k$-Anonymous Asset Transfer objects and SWMR registers. The $k$ in $k$-Anonymous Asset Transfer object refers here to the size of the largest $\mu(w)$, $\forall w \in W$. The signature of the TRANSFER operation is slightly modified from the one presented in the previous section. The sent token is a randomized token produced using the original token TokenMat and a random number. Thus, the $T_O$ used is the result of the function randomize(TokenMat, O, seed) where O is a randomness oracle that uses the seed to provide random numbers. The oracle and the seed are shared by all the processes in the system. In Algorithm 4, the receiving token $T_R^p$ is a dummy token that is never used.

**Shared variables:**

AT $\leftarrow k$-Anonymous-AT object, initialized with $k$ wallets, each one of the $k$ wallets possesses the elements necessary to transfer one shared token.

RM-LEDGER $\leftarrow$ Atomic Snapshot object, initially $\{\emptyset\}^k$;

V-LED $\leftarrow$ Atomic Snapshot object, initially $\{\emptyset\}^k$;

O $\leftarrow$ A random oracle;

TokenMat $\leftarrow$ secret associated with a unique token;

**Local variables:**

seed $\leftarrow$ random number;

$T_R^p \leftarrow$ receiving token;

**Operation PROPOSE(v) is:**

1: RM-LEDGER[p].update(seed, p);

2: V-LED[p].update(v, p);

3: $T_O \leftarrow$ randomize(TokenMat, O, seed);

4: res $\leftarrow$ AT.transf er($T_O$, $T_R^p$);

5: RML $\leftarrow$ RM-LEDGER.s n snapshot();

6: VL $\leftarrow$ V-LED. s n snapshot();

7: For $i$ in $\{1, \dots, k\}$ do:

8: If uncommit(O, RML[i], TokenMat, res) $\neq$ $\emptyset$ then:

9: Return VL[i];

10: Return False;

■ Algorithm 4 Implementation of a $k$-consensus object using $k$-Anonymous-AT objects

► **Theorem 12.** *Algorithm 4 wait-free implements $k$-consensus.*

**Proof.** Let us fix an execution $E$ of the algorithm. Each PROPOSE operation only requires a finite number of AT-transfer operations and a finite number of accesses to Atomic Snapshot objects. Both objects are assumed to be atomic. The number of wallet owners is finite. Therefore, each process finishes the invocation of PROPOSE in a finite number of its own steps. Let $H$ be the history of $E$. We define $\bar{H}$ the completion of $H$, where:
1084

1085

■ Any invocation of PROPOSE in $H$ which does not reach line 4 is completed with the line "return False";

1086

1087

1088

1089

■ Any invocation of PROPOSE in $H$ that reaches line 4 is completed with the lines 5 to 9. We call operations that return false failed operations. The other operations are called successful operations. We verify that the completed history $\tilde{H}$ follow the specification of a $k$-consensus object:

1090

1091

1092

■ Any process that invokes a failed PROPOSE in $\tilde{H}$ is a faulty process. The fact that this process cannot decide on a value does not impact the validity, the agreement, or the termination properties.

1093

1094

1095

1096

1097

1098

1099

■ Any invocation of a successful PROPOSE operation in $\tilde{H}$ returns the value proposed by the unique process that successfully transferred the token associated with TokenMat. If a process reaches line 5 at time $t$, then a unique TRANSFER succeeded at time $t' < t$. Hence, the uncommit operation returns 1 at least and at most once, ensuring the Validity property. The agreement is ensured because no two processes can spend the same coin. Furthermore, the coin associated with TokenMat is transferred to a dummy account which cannot invoke TRANSFER operations. Therefore, the agreement property is verified.

1100

1101

1102

All invocations of the PROPOSE operation in $\tilde{H}$ follow the specification, and the algorithm presented in Algorithm 4 is wait-free. In conclusion, the proposed implementation of a $k$-consensus object is linearizable. ◀

<figure><img src="image_4.png" /></figure>

1103

► **Corollary 13.** *The consensus number of the Anon-AT object is at least k.*

1104

Upper Bound

1105

1106

1107

1108

1109

1110

1111

1112

1113

1114

We give an implementation of the Anon-AT object using only Atomic Snapshot objects, DenyList objects, and AllowList objects. Each wallet owner can request a TRANSFER operation to $k$ different processes. The proposed implementation uses disposable tokens that are either created at the initialization of the system or during the transfer of a token. When a token is destroyed, a new token can be created, and the new owner of the token is the only one to know the cryptographic material associated with this new token. In the following, we use the zero-knowledge version of the DenyList and AllowList object types, where all set-(non-)membership proofs use a zero-knowledge setup. In addition, we use an AllowList object to ensure that a token exists (no ex-nihilo creation), and we use a DenyList object to ensure that the token is not already spent (double-spending protection).

1115

1116

1117

1118

1119

1120

1121

1122

The underlying cryptographic objects used are out of the scope of this paper. However, we assume our implementation uses the ZeroCash [18] cryptographic implementation, which is a sound anonymous asset transfer protocol. More precisely, we will use a high-level definition of their off-chain functions. It is important to point out that using the ZeroCash implementation, it is possible to transfer value from a pseudonymous asset transfer object to an anonymous one using a special transaction called “Mint”. To simplify our construction, we assume that each wallet is created with an initial amount of tokens $v_0$ and that our object does not allow cross-chain transfers. We, therefore, have no “Mint” operation.

1123

1124

1125

1126

1127

1128

ZeroCash uses a TRANSFER operation called *pour* that performs a transfer operation destroying and creating the associated cryptographic material. Here, we use a modified version of *pour* which does not perform the transfer or any non-local operation. It is a black-box local function that creates the cryptographic material required to prove the destruction of the source token ($T_O$) and the creation of the destination one ($T_R$). Our modified *pour* function takes as input the source token, the private key of the sender ($sk_s$), and the public
1129 key of the recipient ($pk_r$): $pour(T_O, pk_r, sk_s) \rightarrow tx$, $tx$ being the cryptographic material that makes it possible to destroy $T_O$ and create $T_R$.

1131 There might be multiple processes transferring tokens concurrently. Therefore, we define a deterministic local function ChooseLeader($\mathcal{A}, tx$), which takes as input any set $\mathcal{A}$ and a transaction $tx$, and outputs a single participant $p$ which invoked BL.PROVE($tx$).$^7$

**Shared variables:**

DL $\leftarrow k$-DenyList object, initially $(\emptyset, \emptyset)$;

AL $\leftarrow$ AllowList object, initially $((token_{(i,j)})_{i=1}^k)_{j=1, \emptyset}$;

**Operation TRANSFER($T_O, pk_r, sk_s$) is:**

1: $tx \leftarrow Pour(T_O, pk_r, sk_s)$

2: **If** verify($tx$) and $tx \in AL$ and $tx \notin DL$ **then**:

3: AL.PROVE($tx$);

4: DL.PROVE($tx$);

5: DLAPPEND($tx$);

6: **Do:**

7: ret $\leftarrow$ DL.PROVE($tx$);

8: **While** ret $\neq$ false;

9: **If** ChooseLeader(DL.READ(), $tx.T_R$)=$p$ **then**:

10: AL.append($tx.T_R$);

11: **Return** $tx.T_R$;

12: **Return** False;

■ **Algorithm 5** Anon-AT object implementation using SWMR registers, AllowList objects, and DenyList objects.

1134 ▶ **Theorem 14.** *Algorithm 5 wait-free implements an Anon-AT object.*

1135 **Proof.** Let us fix an execution *E* of the algorithm. *E* only uses DenyList objects and SWMR registers (AllowList objects have consensus number 1 and can be implemented using SWMR registers). Each TRANSFER operation only requires a finite number of DenyList.PROVE and DenyListAPPEND operations, which are assumed atomic. Each process finishes the invocation of TRANSFER in a finite number of its own steps. Let *H* be the history of *E*. We define $\bar{H}$ the completion of *H*, where:

1141 ■ Any pending invocation of TRANSFER in *H* that did not reached line 11 is completed with the line "return False";

1143 ■ Any pending invocation of PROPOSE in *H* that reached line 11 is completed with line 12.

1145 We call operations that return false failed operations. The other operations are called successful operations. In the following, we analyze if the completed history $\bar{H}$ follows the Anonymous Asset-Transfer object specification:

1148 ■ Any process that fails in an invocation of a TRANSFER operation in $\bar{H}$ is a faulty process. It cannot transfer money or create or double-spend a token. Therefore, it does not contradict the properties of the Anonymous Asset Transfer object. This faulty process can lose tokens (by destroying it and not transferring it), but because we assume a crash is definitive, all its tokens are lost anyway.

1153 ■ A TRANSFER($T_O, T_R$) operation invoked by a process $p$ in $\bar{H}$ that succeeds proves to the network that the token $T_O$ exists and was not spent. After creating the cryptographic material for the new token and for destroying the old one, the operation verifies the correctness of the material and the validity of the old and new tokens (line 2). The prove operation in line 3 necessarily succeeds as $tx \in AL$. The prove in line 4 may instead fail if another process is performing a concurrent transfer operation for the same $T_O$. This

<footnote>$^7$ In reality, the signature of chooseLeader would be more complicated as the function needs $T_O, pk_r, sk_s$ in addition to $tx$. These additional elements make it possible to uncommit $tx$, thereby matching the values of the PROVE operation with $tx.T_R$. Note that this does not pose an anonymity threat as this is a local function invoked by the owner of $sk_s$. We omit these details in the following to simplify the presentation.</footnote>
1159

1160

1161

1162

1163

1164

1165

1166

1167

1168

1169

potential conflict is resolved by the ChooseLeader function, which takes as input the list of successful prove operations on the DenyList. The determinism of the ChooseLeader function and the agreement provided by the READ operation ensure that all processes add the same $tx.T_R$ at line 10 even if multiple processes issue concurrent conflicting TRANSFER operations for the same $T_O$. The previous statement enforces double-spending prevention. The non-creation property is ensured by the PROVE operation conducted on the AllowList on line 3. Finally, anonymity is enforced using the ZKP version of the AllowList and the DenyList objects.

All invocations of the TRANSFER operation in $\tilde{H}$ follow the specification of the Anonymous Asset Transfer object. In conclusion, the proposed algorithm is a wait-free implementation of the Anonymous Asset Transfer object. ►

1170

1171

1172

**Corollary 15.** *The consensus number upper bound of a k-anon-AT object is k. Using this corollary and the previous one, we further deduct that k-anon-AT object has consensus number k.*

1173

## B.3 From the size of the anonymity set to the consensus number

1174

1175

A relation exists between the size of the anonymity set of an AAT object and the consensus number of this object. The goal of this section is to explore this relationship.

1176

1177

1178

1179

1180

1181

1182

1183

1184

Let the relation between wallets and processes be represented by a graph. In the graph, vertices are either wallets or processes. Edges only link wallets to processes, and represent the fact that a process can order a TRANSFER operation on behalf on the associated wallet. Then, on the one hand, the consensus number *k* of a *k*-anon-AT is the maximum multiplicity of any wallet in the graph—i.e. $k = \max_{w \in W} |\mu(w)|$. On the other hand, the size of the anonymity set for a wallet *w* and a given TRANSFER operation invoked by a process *p* is the multiplicity of this process in the graph. Furthermore, the size of the anonymity set for a wallet *w* and any TRANSFER operation is the minimum multiplicity of a process associated to *w*.

1185

# C E-vote system implementation using a DenyList object

1186

1187

1188

1189

1190

1191

1192

1193

In this section, we show that DenyList objects can provide upper bounds on the consensus number of a complex objects. As an example, we study an e-vote system. An e-vote system must comply with the same properties as an "in-person" voting. An "in-person" voting system must ensure four security properties, two for the organizers and two for the voters. First, the organizers of the vote must ensure that each person who votes has the right to do so. Second, each voter must vote only once. Third, a voter must verify that their vote is considered in the final count. Fourth, an optional property is voter anonymity. Depending on the type of vote, the voter may want to hide their identity.

1194

1195

1196

1197

1198

1199

1200

1201

We want to design a distributed e-vote system, where a voter can submit their vote to multiple different voting servers—while ensuring the unicity of their vote. We assume each server is a process of the distributed infrastructure. The voters act as clients, submitting vote requests to the servers. We assume the "right to vote" property is ensured using tokens. The Token is a one-time-used pseudonym that links a vote to a voter. Users obtain their Tokens from an issuer. All the voting servers trust this issuer. Neither the voters nor the issuer has access to the e-vote object—except if one of the actors assumes multiple roles. Using these specifications, we define the e-vote object type as follows:
**► Definition 16.** The e-vote object type supports two operations: VOTE(Token, v) and VOTE-COUNT(). Token is the voter's identifier, and v is the ballot. Moreover, these operations support three mandatory properties and one optional property:

1. (Vote Validity) A VOTE(Token, v) invoked at time t is valid if:
   - Token is a valid token issued by an issuer trusted by the voting servers; and
   - No valid VOTE(Token, v') operation was invoked at time t' < t, where v' ≠ v.

2. (VOTE-COUNT validity) A VOTE-COUNT() operation returns the set of valid VOTE operations invoked.

3. (optional - Anonymity) A Token does not link a vote to its voter identity, even if the voting servers and the issuers can collude.

In the following, we analyze an e-vote system based on signatures. The issuer issues a signature to the voter. The message of the signature is a nonce. The tuple (signature, nonce) is used as a token. When a voter issues a vote request, the server verifies the signature's validity and proceeds to vote if the signature is valid.

Adding anonymity to a signature-based e-vote system can be easily achieved using blind signatures [25]. A blind signature algorithm is a digital signature scheme where the issuer does not learn the value it signs. Because the signed value is usually a nonce, the issuer does not need to verify the value—a value chosen maliciously will not grant the voter more privileges than expected.

Formally, a Blind signature algorithm is defined by the tuple (Setup, Commit, Sign, Uncommit, Verify), where Setup creates the common values of the scheme (generators, shared randomness, etc...) and secret/public key pairs for all issuers. The public keys are shared with all the participants in the system. Commit is a commitment scheme that is hiding and binding; it outputs a commitment to a value—the nonce—randomly chosen by the user. The Sign algorithm takes as input a commitment to a nonce and the secret key of an issuer. It outputs a signature on the commitment. The Uncommit algorithm takes a signature on a commitment and the issuer's public key as input and outputs the same signature on the uncommitted message (the original message). Finally, the Verify algorithm outputs 1 if the uncommitted signature is a valid signature by an issuer on the message m.

Algorithm 6 provides a wait-free implementation of an e-vote system using any signature scheme, one k-DenyList object, and one SWMR atomic snapshot object. Here, the value of k corresponds to the number of voting servers, and $k=|\Pi_V| = |\Pi_M|$. The idea of the algorithm is to use the APPEND operation to state that a token has already been used to cast a vote. In order to obtain a wait-free implementation, we use a helper value [15] stored in the Atomic Snapshot object AS-prevote. The vote operation is conducted as follows: the voting server V communicates the vote it will cast in the AS-prevote object. Then, V conducts a PROVE(Token) operation to prove that the Token has not yet been used. Then, V invokes an APPEND(Token) operation and waits until the APPEND is effective—the do-while loop in line 8 to 10. Finally, V uses the READ operation to verify that it is the only process that proposed a vote for this specific Token. If it is the case, the vote is added to the vote array—the AS-vote array. Otherwise, the vote is added to the vote array only if the other servers that voted using the same Token proposed the same ballot in line 4.

Other implementations can be proposed in the case of two concurrent transactions requested by the same voter—to different servers—with different values. For example, it is possible to modify the algorithm presented in Algorithm 6 using a deterministic function to choose one value among all the potential votes. This modification does not impact the properties of this implementation.
39:32 The Synchronization Power of Access Control Objects

We now provide an informal proof of the linearizability of this implementation. The
anti-flickering property of the k-DenyList object ensures the termination of the while loop.
Therefore, the implementation is wait-free. The same property ensures that the vote-values
variables are the same for all voters with the same Token, thus ensuring the unicity of the
vote. The proof of authorization of the vote is ensured by the signature verification in line
1. The anonymity property is also fulfilled if a blind signature scheme is used. Therefore,
the use of anonymous DenyList objects is not required. Hence, we can conclude that the
consensus number of the k-DenyList object type is an upper bound on the consensus number
of an e-vote system.

**Shared variables:**

k-dlist ← k-DenyList object;
AS-prevote ← Atomic Snapshot object, initially {0}^k
AS-vote ← Atomic Snapshot object, initially {0}^k

**Operation** VOTE((signature, pk, token, v) is:

1: If Verify(signature, token, pk) ≠ 1 then:

2:   **Return** false;

3: AS-prevote.update((token, v), p);

4: ret ← k-dlist.PROVE(token)

5: If ret = false then:

6:   **Return** false;

7: k-dlistAPPEND(token);

8: Do:

9: ret ← k-dlist.PROVE(token);

10: While ret ≠ false;

11: votes ← k-dlist.READ();

12: client-votes ← all values in votes where token is token;

13: voters ← all processes in client-votes;

14: vote-values ← all values in AS-prevote

' where token is token and processes that added the value are in voters;

15: If vote-values = {v}^l, ∀ l ≥ 1 then:

16: previous-votes ← AS-vote.SNAPSHOT()[p];

17: AS-vote.UPDATE(previous-votes ∪ (token, v, voters), p);

18: **Return** true;

19: Else **return** false;

**Operation** VOTE-COUNT() is:

20: votes ← all values in AS-vote.Snapshot().

' Only one occurrence of each tuple (token, v, voters) is kept;

21: **Return** votes;

**Algorithm 6 Implementation of an e-vote object using one k-DenyList object and Atomic Snapshots**

It is also possible to build a wait-free implementation of a k-consensus object using one e-vote object. This implementation is presented in Algorithm 7. The idea of this algorithm is that each process will try to vote with the same Token. Because only one vote can be accepted, the e-vote object will only consider the first voter. Ultimately, every process will see the same value in the vote object. This value is the result of the consensus.

Each invocation is a sequence of a finite number of local operations and e-vote object
accesses, which are assumed atomic. Therefore, each process terminates the PROPOSE
operation in a finite number of its own steps. A vote can only be taken into account if it was
proposed by some process, which enforces the validity property. The agreement property
comes from the unicity of the vote. Finally, the non-trivial property of the consensus object
is ensured because the decided value is any value v chosen by the winning process.

**Shared variables:**

vote-obj ← e-vote object where the only authorized token is 0;
σ ← signature on 0 by a trusted issuer;

**Operation** PROPOSE(v) is:
1: vote-obj.VOTE((σ, 0), v);
2: {(winner-token, value)} ← vote-obj.VOTE-COUNT();
3: **Return** value;

**Algorithm 7 Implementation of a k-consensus object using one e-vote object**

The consensus number of a blind-signature-based e-vote system is bounded on one side by the consensus number of a *k*-consensus object and the other side by the consensus number of a *k*-DenyList object. Hence, the blind-signature-based e-vote object type has consensus number *k*.