# Asynchronous BFT Asset Transfer: Quasi-Anonymous, Light, and Consensus-Free

Timothé Albouy, Emmanuelle Anceaume, Davide Frey, Mathieu Gestin, Arthur Rauch, Michel Raynal, François Taïani

► To cite this version:

Timothé Albouy, Emmanuelle Anceaume, Davide Frey, Mathieu Gestin, Arthur Rauch, et al. Asynchronous BFT Asset Transfer: Quasi-Anonymous, Light, and Consensus-Free. 2024. hal-04578985

HAL Id: hal-04578985

https://inria.hal.science/hal-04578985

Preprint submitted on 17 May 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
<figure><img src="image_1.png" /></figure>

HAL
open science

# Asynchronous BFT Asset Transfer: Quasi-Anonymous, Light, and Consensus-Free

Timothé Albouy, Emmanuelle Anceaume, Davide Frey, Mathieu Gestin, Arthur Rauch, Michel Raynal, François Taïani

► To cite this version:

Timothé Albouy, Emmanuelle Anceaume, Davide Frey, Mathieu Gestin, Arthur Rauch, et al. Asynchronous BFT Asset Transfer: Quasi-Anonymous, Light, and Consensus-Free. 2024. hal-04578985v2

HAL Id: hal-04578985

https://inria.hal.science/hal-04578985v2

Preprint submitted on 18 Feb 2025

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Asynchronous BFT Asset Transfer:
Quasi-Anonymous, Light, and Consensus-Free

**Timothé Albouy** ☑

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes, France

**Emmanuelle Anceaume** ☑

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes, France

**Davide Frey** ☑

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes, France

**Mathieu Gestin** ☑

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes, France

**Arthur Rauch** ☑

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes, France

**Michel Raynal** ☑

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes, France

**François Taïani** ☑

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes, France

## Abstract

This article introduces a new asynchronous Byzantine-tolerant asset transfer system (cryptocurrency) with three noteworthy properties: quasi-anonymity, lightness, and consensus-freedom. Quasi-anonymity means no information is leaked regarding the receivers and amounts of the asset transfers. Lightness means that the underlying cryptographic schemes are *succinct*, and each process only stores data polylogarithmic in the number of its own transfers. Consensus-freedom means the system does not rely on a total order of asset transfers. The proposed algorithm is the first asset transfer system that simultaneously fulfills all these properties in the presence of asynchrony and Byzantine processes. To obtain them, the paper adopts a modular approach combining a new distributed object called agreement proofs and well-known techniques such as vector commitments, universal accumulators, and zero-knowledge proofs. The paper also presents a new non-trivial universal accumulator implementation that does not need knowledge of the underlying accumulated set to generate (non-)membership proofs, which could benefit other crypto-based applications.

**2012 ACM Subject Classification** Theory of computation → Distributed algorithms

**Keywords and phrases** Agreement proof, Anonymity, Asset transfer, Asynchrony, Byzantine process, Consensus-freedom, Cryptography, Deterministic algorithm, Distributed computing, Fault-tolerance, Light algorithm, Modularity, Message-passing communication, Non-interactive, Quorum, Succintness, Vector commitment, Universal accumulator, Zero-knowledge proof.

**Funding** This work was partially supported by the French ANR projects ByBloS (ANR-20-CE25-0002-01) and PriCLeSS (ANR-10-LABX-07-81), devoted to the modular design of building blocks for large-scale Byzantine-tolerant multi-users applications. This work was also partially funded by the SOTERIA project. SOTERIA has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 101018342. This content reflects only the author's view. The European Agency is not responsible for any use that may be made of the information it contains.
Asynchronous BFT Asset Transfer:
Quasi-Anonymous, Light, and Consensus-Free

Timothé Albouy, Emmanuelle Anceaume, Davide Frey,
Mathieu Gestin, Arthur Rauch, Michel Raynal, François Taïani

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes-cedex, France

February 18, 2025

Abstract

This paper introduces a new asynchronous Byzantine-tolerant asset transfer system (cryptocurrency) with three noteworthy properties: quasi-anonymity, lightness, and consensus-freedom. Quasi-anonymity means no information is leaked regarding the receivers and amounts of the asset transfers. Lightness means that the underlying cryptographic schemes are *succinct* (i.e., they produce short-sized and quickly verifiable proofs) and each process only stores its own transfers while keeping communication cost as low as possible. Consensus-freedom means the system does not rely on a total order of asset transfers. The proposed algorithm is the first asset transfer system that simultaneously fulfills all these properties in the presence of asynchrony and Byzantine processes. To obtain them, the paper adopts a modular approach combining a new distributed object called “agreement proof” and well-known techniques such as commitments, universal accumulators, and zero-knowledge proofs.

**Keywords:** Anonymity, Asset transfer, Asynchrony, Byzantine Fault Tolerance, Consensus-freedom, Cryptography, Distributed computing, Lightness.

**Acknowledgments.** The authors would like to thank Maxence Brugères, Petr Kuznetzov, and Victor Languille for their valuable comments which helped improve this paper significantly.

This work is partially supported by the French ANR projects ByBloS (ANR-20-CE25-0002-01) and PriCLeSS (ANR-10-LABX-07-81), and the SOTERIA project. SOTERIA has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 101018342. This content reflects only the author's view. The European Agency is not responsible for any use that may be made of the information it contains.
1 Introduction

Existing decentralized *asset transfer* systems<fnref n="1" /> face a range of challenges pertaining to their privacy guarantees (*e.g.*, confidentiality), performance (*e.g.*, throughput, latency), costs (*e.g.*, in term of storage and computation), and scalability. Several solutions have been proposed to address those problems individually, but implementing a solution to one problem often negatively impacts other aspects of the system. In this paper, we propose a new asset transfer system that balances efficiency and user privacy, by guaranteeing the following desirable properties.

1. **Quasi-anonymity:** the amount and the receiver's identity of every asset transfer remain hidden from the adversary.

2. **Lightness:** all cryptographic schemes used by our solution are *succinct* (as defined in [6]), and the storage cost incurred by each process $p_i$ is polylogarithmic in $|S_i|$ for a fixed security parameter $\lambda$ (which we denote $O_\lambda(\text{polylog } |S_i|)$), where $S_i$ is the set of all transfers of $p_i$.

3. **Consensus-freedom:** our algorithm does not rely on consensus or a total order of asset transfers.

As we show next, several endeavors have been conducted to create asset transfer systems that meet the quasi-anonymity, lightness, and consensus-freedom properties.

**Anonymous and quasi-anonymous asset transfer systems.** Anonymous Asset Transfer (AAT) systems have been studied since the introduction of Bitcoin [39] and can be categorized as either *token-based* or *account-based*. Token-based AAT uses two types of Zero Knowledge Proofs (ZKP): ZKP of token existence and ZKP that a token has not been spent yet. To transfer a token, the sender proves that it possesses a token that has not yet been added to a list of spent tokens. It then “destroys” this token (by adding it to the list of spent coins) and creates a new one belonging to the transfer’s receiver. Zcash [29] is an example of this first category. Account-based AAT is mainly represented by Quisquis [19] and Zether [11]. They only store commitments to different accounts. For each transfer, the sender proves that its account has enough funds, and full anonymity is provided by randomly selecting all or a subset of the system accounts. The system introduced in this article is account-based (it does not use a list of spent coins).

All previously cited systems [29, 19, 11] provide full anonymity (*i.e.*, they ensure sender and receiver anonymity), but they also require consensus. It has been shown in [22] that fully anonymous asset transfer requires consensus to be implemented. To achieve consensus freedom despite this impossibility, it is possible to weaken the anonymity guarantees of asset transfer, as done in Zef [4] or the present paper. We call our weakened version of AAT *quasi-anonymous asset transfer (QAAT)*.

**Light asset transfer systems.** In this paper's context, *lightness* means that the storage per process is polylogarithmic in the number of its own transfers, and all underlying cryptographic schemes are *succinct*.

A cryptographic proving scheme is *succinct* if and only if its proof size and verification time are at most polylogarithmic (and thus sublinear) in the “size of the problem” [6]. This “size of the problem” depends on the scheme. For instance, it may refer to the number of signatures

<footnote n="1">¹ The terms *money* or *currency* are sometimes discouraged when talking about decentralized payment systems, as they do not always satisfy the 3 properties of money, i.e., unit of account, medium of exchange, and store of value [37].</footnote>
# 1 Introduction

Imagine a world without the ability to send money instantly across the globe, a world where financial borders seemed impassable. This was our world just a few decades ago. The advent of online money transfers, a real silent revolution, has turned our lives upside down and is reshaping the global economic landscape. Its potential for a positive impact on the world (e.g., decentralized and secured financial transactions, democratized access to financial services, micro-payments) is far from exhausted. Existing decentralized money transfer, also called *decentralized or distributed asset transfer*, faces a range of challenges pertaining to privacy (i.e., transfer confidentiality), performance (i.e., throughput and latency), and communication/computational/storage costs. Addressing these challenges amounts to designing a system that enjoys:

* **Anonymity** to hide both the identity of the parties involved in the transfer (i.e., the sender and/or the recipient)<fnref n="1" /> and the amount of transferred assets,

* **Lightness** to maintain low operational costs in terms of computation (in particular, ensuring the *succinctness* of security proofs), storage (each participant only needs to store her own transfer history), and communication (i.e., low bit complexity),

* **Consensus freedom** to operate deterministically in an asynchronous failure-prone setting. Unfortunately, existing systems invariably satisfy only a subset of these three important properties.

First, until recently, all asset-transfer systems relied on a consensus primitive. Consensus was thought necessary to avoid double spending, but as shown in [1, 26, 27], a reliable broadcast primitive whose deliveries respect process sending order is sufficient when each account is owned by a single process. This has direct practical implications because consensus imposes a non-required sequential processing of all the asset transfers (or block by block in the case of blockchains). On the other hand, not only can consensus-free asset-transfer systems process transfers concurrently, resulting in higher throughput [2, 14], but they also make it possible to leverage deterministic algorithms that achieve progress in asynchronous settings. In practical systems, this means not having to wait for synchrony assumptions to be satisfied, a condition that would otherwise lead to long delays in large-scale systems. The interested reader may find possibility and impossibility results for payment channels in asynchronous asset transfer in [37].

Second, even if recent years have shown the emergence of a variety of consensus-free solutions for asset transfer, none of them, except for the recent Zef [3] feature any level of anonymity. Anonymous asset transfer systems typically rely on consensus to enable multiple users to hide behind a set of accounts or tokens. Indeed, recent work [22] has shown that consensus is necessary to guarantee full anonymity in a system where asset transfers from correct processes never fail. Zef [3] circumvents this impossibility by weakening the anonymity requirement, similar to what we do in this paper.

Finally, most systems (including Zef [3]) exhibit high storage and/or communication cost as summarized in Table 1. With respect to storage, most systems require nodes to store the entire history of all asset transfers (e.g., the entire blockchain) or at least a number of transfers proportional to this entire history. With respect to communication, they feature a cost that is at least linear in the number of nodes, and quadratic in the case of Zef (Table 1).

**Combining quasi-anonymity, lightness, and consensus freedom.** The challenge addressed in this paper consists in designing the first asset transfer system that achieves anonymity, and consensus-freedom while incurring as-low-as-possible storage and communication costs. Specifically, the proposed solution achieves the following properties.

1. **Quasi-anonymity:** it hides the amount and the receiver's identity of each asset transfer.

2. **Lightness:** All the cryptographic schemes it uses are succinct—i.e., with at most polylogarithmic proof size and verification time—the storage cost incurred by each process $p_i$ is linear in the

<footnote n="1">¹Note that when the anonymity of only the sender or the recipient is hidden, we talk about quasi-anonymity.</footnote>
to aggregate in an aggregated signatures scheme [8], or to the arithmetic circuit size used in a Succinct Non-interactive Argument scheme (SNARG). Intuitively, succinctness captures the fact that a practicable system has to use cryptographic implementations that are themselves practicable (i.e., their computational and storage costs do not become prohibitively high with time).

Reducing the local storage cost of decentralized asset transfer systems has been a research challenge since the advent of Bitcoin [39], which introduced the notion of *light clients* (a.k.a. *Simplified Payment Verification*, or *SPV*), i.e., clients storing only a subset of the whole system data (e.g., block headers and Merkle proofs in SPV). But as efficient as they are for reducing the load of light clients, such solutions [12, 39] do not completely remove the need for * validators* (the processes verifying the transfers) to store the entire set of transfers. To overcome this limitation, alternative approaches seek to reduce the storage cost of validators to make it at most sublinear in the system’s total number of asset transfers [32, 31]. For example, the Mina system [9] leverages SNARKs (Succinct Non-interactive Arguments of Knowledge) to obtain a succinct blockchain whose storage cost for validators is proportional to the number of accounts in the system.

The system presented in this paper goes one step further: to our knowledge, it is the first light asset transfer system, i.e., it is succinct and has a storage cost for each correct process $p_i$ that is polylogarithmic in the number of asset transfers of $p_i$.<fnref n="2" />

**Consensus-free asset transfer systems.** Contrary to a common belief, asset transfer in the presence of (Byzantine) faults does not require strong agreement such as consensus or, equivalently, total order [27, 28].<fnref n="3" /> More formally, the only condition required to prevent double-spending in a payment system is for the processes to agree on the order in which transfers are issued from each individual account: if some account issues two conflicting transfers spending the same funds, the rest of the network, and especially the corresponding creditors, have to settle on which transfer (if any) is correct. This relaxed, per-account transfer ordering can be obtained by communication primitives weaker than consensus, such as *reliable broadcast* [10].<fnref n="4" />

Following the seminal result of [27], several papers have proposed payment systems based on reliable broadcast only, namely AFRT20 [1], Astro [14], and FastPay [3]. Astro has been later extended to permissionless environments with Pastro (permissionless Astro) [35], by combining weighted quorums coupled and proof-of-stake. Building on FastPay, Zef [4] provides confidential and untraceable transfers, but is not fully consensus-free as it relies on a classical blockchain, which typically requires Nakamoto-style consensus. (For simplicity, we have categorized Zef as consensus-free in Table 1.)

The benefits of leveraging communication primitives with weak ordering (such as reliable broadcast) instead of consensus (total order) when designing an asset transfer system are twofold.

First, constructing a total order is costly and forces the system's processes to treat all asset transfers in the same sequential order (or block by block in the case of blockchains). This significantly impacts the system's throughput, i.e., the number of asset transfers per

<footnote n="2">² Following the literature, we only consider the internal state and the cryptographic schemes used by our system when analyzing its storage cost. In particular, the cost induced by the network routing protocol is ignored.</footnote>

<footnote n="3">³ More specifically, consensus-freedom applies to asset transfer systems in which each account is owned by a single process.</footnote>

<footnote n="4">⁴ This is only the case for asset transfer systems where each account is owned by a single process. In systems where accounts can have multiple owners, consensus is needed.</footnote>
<table><caption>Table 1: Comparison with notable existing systems. $|T|$ denotes the total number of transfers in an execution. The storage cost is given per process, and the communication cost is given for the whole system.</caption><thead><tr><td>System</td><td>Anonymity</td><td>Comm.</td><td>Storage</td><td>Cons.-Free</td><td>Model</td></tr></thead><tbody><tr><td>Zcash [28]</td><td>Full</td><td>Ω(λn)</td><td>Ω(λ|T|)</td><td>No</td><td>Sync.</td></tr><tr><td>Mina [9, 41]</td><td>None</td><td>Ω(λn)</td><td>Ω(λ|T|/n + n log n + n)</td><td>No</td><td>Sync.</td></tr><tr><td>Pastro [33]</td><td>None</td><td>?</td><td>Ω(λ|T| + n)</td><td>Yes</td><td>Async.</td></tr><tr><td>Zef [3]</td><td>Quasi</td><td>Ω(λn<fnref n="2" />)</td><td>Ω(λ|T| + n)<fnref n="2" /></td><td>Yes</td><td>Async.</td></tr><tr><td>This paper</td><td>Quasi</td><td>O(λn)</td><td>O(λ + (|T|/n) log n + n)</td><td>Yes</td><td>Async.</td></tr></tbody></table>

number of transfers of $p_i$ for a fixed security parameter $\lambda$, and the communication cost of the algorithm remains as low as possible.

3. **Consensus freedom:** The proposed solution consists of a deterministic algorithm that can operate in an asynchronous setting prone to failures, thereby supporting responsive implementations.

**Roadmap.** This paper is made up of 7 main sections. Section 2 positions the contribution with respect to the state of the art. Section 3 defines the computing system model. Section 4 provides a concurrent specification of quasi-anonymous asset transfer (QAAT). Section 5 informally defines the cryptographic schemes used in our system. Section 6 presents a novel *Agreement Proof* abstraction, our QAAT system, and the intuition behind its correctness. Finally, Section 7 concludes the article.

Mote technical developments, such as the proofs of the QAAT algorithm, and the properties and implementations of Section 5's schemes appear in appendices.

## 2 Background and State of the Art

As we briefly mentioned above, some notable systems have addressed each of the challenges we presented individually, but to the best of our knowledge, we are the first to address all of them in a single system. Table 1 compares some of the notable existing asset transfer systems evoked below.

**Anonymous and quasi-anonymous asset transfer systems.** Anonymous Asset Transfer (AAT) systems have been studied since the introduction of the online payment system Bitcoin in 2008 [36] and can be categorized as either *token-based* or *account-based*. The two types of systems differ by the persistency of the financial medium. A token can only be used once while an account has a recorded balance. To transfer a token, the sender must prove that it possesses it and that this token has never been used before. This is generally achieved by maintaining a list of unspent tokens and a list of spent tokens. Anonymity is typically obtained by relying on cryptographic primitives (Zero-knowledge proofs—ZKPs) that allow one party to convince another party that a given statement is true without divulging any information beyond the fact that the statement is true. An example of token-based systems is Zcash [28].

Asset transfer via accounts requires the sender to prove that its account has sufficient funds. Anonymity is guaranteed by having the sender select at random a subset of its accounts. The Quisquis [19] and the Zether [11] asset-transfer systems represent account-based AATs.

All the systems we mentioned [11, 19, 28] provide full anonymity (i.e., they ensure both sender and receiver anonymity), but they also rely on consensus and therefore cannot be implemented deterministically in an asynchronous failure-prone system. Indeed, it was recently shown [22] that fully anonymous asset transfer requires consensus or equivalently total order to be implemented, if asset transfers from a

<footnote n="2">²The authors of [3] describe a public-key rotation method to further reduce Zef's storage cost, however this mechanism requires additional synchrony assumptions, as discussed in Section 6.2.5.</footnote>
<table><caption>Table 1 Comparison of the properties of notable existing systems.</caption><thead><tr><th>System</th><th>Quasi-anon.</th><th>Succinct</th><th>Polylog storage</th><th>Consensus-free</th></tr></thead><tbody><tr><td>Zcash [29]</td><td>✓ (fully anon.)</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Mina [9]</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Pastro [35]</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td></tr><tr><td>Zef [4]</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td></tr><tr><td>This paper</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

second (TPS) that can be handled. In contrast, the weak ordering provided by reliable broadcast makes it possible to process asset transfers concurrently, resulting in higher throughput [14].

Second, building a total order in the presence of asynchrony and failures is bound by a fundamental impossibility (known as the FLP theorem [21]) stating that consensus cannot be implemented deterministically in an asynchronous system prone to process faults. To circumvent this impossibility, consensus-based cryptocurrency systems typically require stronger assumptions, e.g., (partial) synchrony, randomization, or non-trivial cryptography. In comparison, reliable broadcast can be implemented in asynchronous systems even in the presence of Byzantine faults [2, 10, 30]. This makes reliable-broadcast-based asset-transfer systems more resilient because they deterministically guarantee safety and liveness in environments where their consensus-based counterparts cannot.

**Combining quasi-anonymity, lightness, and consensus-freedom.** Table 1 compares some notable existing asset transfer systems in terms of quasi-anonymity, lightness (made of succinctness and polylog storage), and consensus-freedom. To the best of our knowledge, the algorithm presented in this paper is the first to exhibit all properties while incurring polylog storage per process.

**Roadmap.** This paper is made up of 6 sections. Section 2 defines the computing model of our system. Section 3 provides the sequential specification of quasi-anonymous asset transfer (QAAT). Section 4 introduces the 4 schemes used in our system (including the novel Agreement Proof abstraction). Section 5 presents our QAAT algorithm and the intuition behind its correctness. Finally, Section 6 concludes the article. Due to space constraints, some developments, such as the proofs of our QAAT algorithm, and implementation examples of Section 4's schemes (among which a new non-trivial implementation universal accumulator implementation), appear in appendices.

## 2 System Model

**Processes.** The system comprises *n* sequential asynchronous processes denoted by $p_1, ..., p_n$. Each process $p_i$ has a unique identity, which is known to other processes. To simplify the presentation without loss of generality, we assume that *i* is the identity of $p_i$. Up to $t < n/3$ processes can be Byzantine, where a Byzantine process is a process whose behavior does not follow the code specified by its algorithm [36, 41].<fnref n="5" /> Byzantine processes may collude to fool non-Byzantine (a.k.a. correct) processes.

<footnote n="5">⁵ The assumption $t < n/3$ is only needed for the *Agreement Proof* scheme of our system (see Section 4.1).</footnote>
correct process must never fail.

We show in this paper that guaranteeing quasi-anonymity in place of anonymity is sufficient to circumvent this impossibility result, similar to what is done by Zef [3].

**Light asset transfer systems.** The idea of lightness consists in guaranteeing that all underlying cryptographic schemes are *succinct*, that processes only store transactions they are involved in, and that communication cost remains as low as possible. A cryptographic proving scheme is succinct if and only if its proof size and verification time are at most polylogarithmic in the “size of the problem” [6], where the size of the problem depends on the scheme.<fnref n="3" /> For instance, it may refer to the number of signatures in an aggregated signature scheme [8], or to the arithmetic circuit size used in a Succinct Non-interactive Argument scheme (SNARG). Intuitively, succinctness captures the fact that a practicable system has to use cryptographic implementations that are themselves practicable (i.e., their verification and storage costs do not become prohibitively high with time).

Reducing the local storage cost of decentralized asset transfer systems has been a research challenge since the advent of the Bitcoin blockchain. The notion of light clients, implemented with the simplified payment verification (SPV) protocol [36] allows clients to only store block headers and Merkle proofs in place of full blocks. Still, their local storage grows linearly with the size of the blockchain. Other solutions, such as the one presented in [12], allow a succinct and secure construction of proofs, i.e., Merkle mountain ranges, but still require the full blockchain to be maintained to update the proof with new blocks. In contrast, non-interactive proofs of proof-of-work succeed in constructing secure and succinct token-based asset transfer systems by sampling a polylogarithmic number of blocks of the blockchain [29, 30] but do not target full anonymity of the transfers. Finally, the Mina system [9] leverages SNARKs (Succinct Non-interactive Arguments of Knowledge) to obtain a succinct blockchain. However, their construction requires maintaining the full knowledge of all the accounts of the system to update the proof when a transfer occurs. In addition, Mina does not provide any level of anonymity for the transfers. Those solutions do not explicitly say that they rely on P2P for their communication. Assuming that this is the case, sending a piece of information costs $n \log(n)$ messages in average.

**Consensus-free asset transfer systems.** Fundamentally, an asset-transfer system must be double-spending-free; that is, spending a unit of value more than once must be impossible. This means that all parties agree on the order in which transfers are issued from each individual account: if some account issues two conflicting transfers spending the same funds, the rest of the network, and especially the corresponding creditors, have to agree on which transfer (if any) is correct. This relaxed, per-account ordering of transfers can be obtained by Byzantine-tolerant communication primitives weaker than consensus, e.g., *Byzantine-tolerant reliable broadcast* [10].<fnref n="4" /> Following [26], several works have proposed payment systems based on reliable broadcast only, namely AFRT20 [1], Astro [14], and FastPay [2]. Astro was later extended to permissionless environments with Pastro [33], combining weighted quorums and proof-of-stake. Building on FastPay, Zef [3] provides quasi-anonymous transfers, but it incurs quadratic communication cost and storage cost linear in the total number of transfers.

# 3 System Model

**Processes.** The system comprises $n$ sequential asynchronous processes denoted by $p_1, \dots, p_n$. Each process $p_i$ has a unique identity, which is known to other processes. To simplify the presentation without loss of generality, we assume that $i$ is the identity of $p_i$. Up to $t < n/3$ processes can be Byzantine, where a Byzantine process is a process whose behavior may not follow the algorithm [34, 38].<fnref n="5" /> Byzantine

<footnote n="3">³Following the literature, we only consider the internal state and the cryptographic schemes used by our system when analyzing its storage cost. In particular, the storage cost induced by the network routing protocol is ignored.</footnote>

<footnote n="4">⁴This is only the case for asset transfer systems where each account is owned by a single process. In systems where accounts can have multiple owners, total ordering is needed [26, 27], i.e., consensus or atomic broadcast.</footnote>

<footnote n="5">⁵The assumption $t < n/3$ is only needed for the *Agreement Proof* scheme of our system (see Section 6.1).</footnote>
**Network.** Processes communicate by exchanging messages through a fully connected asynchronous point-to-point communication network, which is assumed to be reliable (i.e., the network does not corrupt, drop, duplicate, or create messages). Let MSG be a message type and v the value contained in the message. The operation “send MSG(v) to p_j” is used for sending, and the callback “when MSG(v) is received” is used for receiving. For syntactic sugar, processes can also communicate using the macro-operation denoted broadcast MSG(v), that is a shorthand for “for all j ∈ {1, ..., n} do send MSG(v) to p_j”. When processes use this macro-operation to disseminate a message, we say that this message is broadcast and received. The macro-operation broadcast MSG(v) is unreliable. For example, if the invoking process crashes during its invocation, an arbitrary subset of processes receives the message MSG(v). Moreover, due to its very nature, a Byzantine process can send conflicting messages without using the macro-operation broadcast. Finally, the processes have access to ra_send/ra_received operations (for “receiver-anonymous send/receive”), which function like the classical send/receive operations with the additional guarantees that (i) the message cannot be read by anyone other than the receiver, and that (ii) the receiver remains anonymous from an adversary eavesdropping the network. For instance, these two operations could be implemented by broadcasting an encrypted message to the whole network that only the intended receiver can decrypt, or by using onion routing [43].

**Cryptographic schemes.** In this paper, we use cryptographic schemes such as secure hash functions, asymmetric signatures, commitments, accumulators, and arguments of knowledge. In the following, we specify these schemes regarding abstract operations and guarantees. We provide concrete implementation examples in Appendix B, detailing how each choice constrains the adversary's power.

**Security parameter λ.** λ denotes the security parameter of the cryptographic schemes used in our algorithms. There is a trade-off between the security level of our cryptographic schemes (represented by λ) and their computational, communication, and storage costs. $\epsilon(\lambda)$ is a positive number between 0 and 1 that can be made arbitrarily small by increasing λ. Additionally, $O_\lambda()$ denotes the complexity for a fixed λ: for a given expression F, $O_\lambda(F)$ is equivalent to $O(\lambda \times F)$.

**Different notions of adversaries.** We consider an adversary with a *distributed* and a *cryptographic* aspect. The *distributed* aspect means that the adversary seeks to compromise the correctness of the system by controlling process faults (Byzantine faults in our case) and the scheduling of messages (asynchrony). The *cryptographic* aspect means that the adversary also strives to compromise the anonymity properties of the system. In this respect, we consider a *probabilistic polynomial-time* (PPT) adversary, *i.e.*, one that has bounded computational power. It has only access to the information publicly transiting on the network (*i.e.*, the messages communicated using the clear-text primitives *send*, *broadcast*, and *received*), not the messages privately exchanged between pairs of processes using the *ra_send/ra_received* operations defined before. We denote our adversary as *Adv*.

**Notations.** The invocation by a process of an operation op with input parameter in and output result out is denoted $op(in)/out$. The “★” symbol means that the corresponding value is unspecified, e.g., $op_i(★)$ refers to an invocation of op by $p_i$ with an arbitrary input. A pair made up of a and b is denoted $\langle a, b \rangle$. Table 2 summarizes key notations used throughout this paper.
processes may collude to fool non-Byzantine (a.k.a. correct) processes.

**Network.** Processes communicate by exchanging messages through a fully connected asynchronous point-to-point communication network, which is assumed to be reliable (i.e., the network does not corrupt, drop, duplicate, or create messages). Let MSG be a message type and v the value contained in the message. The operation "send MSG(v) to p_j" is used for sending, and the callback "when MSG(v) is received" is used for receiving. For syntactic sugar, processes can also communicate using the macro-operation denoted broadcast MSG(v), that is a shorthand for "for all j ∈ {1, ..., n} do send MSG(v) to p_j". When processes use this macro-operation to disseminate a message, we say that this message is broadcast and received. The macro-operation broadcast MSG(v) is unreliable. For example, if the invoking process crashes during its invocation, an arbitrary subset of processes receives the message MSG(v). Moreover, due to its very nature, a Byzantine process can send conflicting messages without using the macro-operation broadcast. Finally, the processes have access to ra_send/ra_received operations (for "receiver-anonymous send/receive"), which function like the classical send/receive operations with the additional guarantees that (i) the message cannot be read by anyone other than the receiver, and that (ii) the receiver remains anonymous from an adversary eavesdropping the network. For instance, these two operations could be implemented by broadcasting an encrypted message to the whole network that only the intended receiver can decrypt, or by using onion routing [39].<fnref n="6" />

**Cryptographic schemes.** In this paper, we use cryptographic schemes such as secure hash functions, asymmetric signatures, commitments, accumulators, and arguments of knowledge. In the following, we specify these schemes regarding abstract operations and guarantees. We provide concrete implementation examples in Appendix C, detailing how each choice constrains the adversary's power.

**Security parameter $\lambda$.** We denote by $\lambda$ the security parameter of the cryptographic schemes used in our algorithms. There is a trade-off between the security level of our cryptographic schemes (represented by $\lambda$) and their computational, communication, and storage costs. We further assume that $\lambda$ dominates $\log n$, i.e., $\lambda = \Omega(\log n)$.

**Different notions of adversaries.** We consider an adversary denoted *Adv* with both *distributed* and *cryptographic* aspects. The distributed aspect seeks to compromise the correctness of the system by controlling process faults (Byzantine faults in our case) and the scheduling of messages (asynchrony). The cryptographic aspect, on the other hand, strives to compromise the anonymity properties of the system. In this respect, we consider a *probabilistic polynomial-time* (PPT) adversary, *i.e.*, one that has bounded computational power. It has only access to the information publicly transiting on the network (*i.e.*, the messages communicated using the clear-text primitives send, broadcast, and received), not the messages privately exchanged between pairs of processes using the ra_send/ra_received operations defined before.

**Notations.** The invocation by a process of an operation op with input parameter in and output result out is denoted $op(in)/out$. The "\star" symbol means that the corresponding value is left unspecified, e.g., $op_i(\star)$ refers to an invocation of op by $p_i$ with an arbitrary input. A pair made up of a and b is denoted $(a,b)$. Table 2 summarizes key notations used throughout this paper.

# 4 Quasi-Anonymous Asset Transfer (QAAT): Concurrent Specification

*Asset Transfer (AT)*, and its extension, *Quasi-Anonymous Asset Transfer (QAAT)* are derived from the *concurrent* asset transfer specification of AFRT20 [1]. We refer to this specification as concurrent because it does not consider asset transfer as a sequential object handling operation invocations in a total order. In the following, we assume that each account is owned by a single process.

**AT operations.** A distributed AT object provides processes with two operations:

<footnote n="6">⁶Note that both these solutions have a communication complexity of at most $O(\lambda n)$.</footnote>
<table><caption>Table 2 Key notations used in the paper.</caption><thead><tr><td>Notation</td><td>Meaning</td></tr></thead><tbody><tr><td>λ, ε(λ), Adv</td><td>Security parameter, Negligible real number in [0; 1], Adversary</td></tr><tr><td>AT, QAAT</td><td>Asset transfer object, Quasi-anonymous asset transfer object</td></tr><tr><td>AP, σ, P<sub>A</sub></td><td>Agreement proof scheme, Agreement proof, AP predicate</td></tr><tr><td>VC, c, o</td><td>Vector commitment scheme, Commitment, Opening</td></tr><tr><td>UA, A,<br>w, u</td><td>Universal accumulator scheme, Accumulator,<br>Membership proof, Non-membership proof</td></tr><tr><td>ZKP, π, P<sub>ZK</sub></td><td>Zero-knowledge proof scheme, Zero-knowledge proof, ZKP predicate</td></tr><tr><td>D (for “data”)</td><td>Input set (values) of the proving operations of Section 4’s schemes</td></tr><tr><td>F (for “finite”)</td><td>Output set (proofs) of the proving operations of Section 4’s schemes</td></tr><tr><td>τ:⟨snd, v, rcv, sn⟩</td><td>Asset transfer details: sender, amount, receiver, sequence number</td></tr></tbody></table>

## 3 Quasi-Anonymous Asset Transfer (QAAT): Sequential Specification

Asset Transfer (AT), and its extension, Quasi-Anonymous Asset Transfer (QAAT) are derived from the concurrent asset transfer specification of AFRT20 [1]. For simplicity, we assume that each account is owned by a single process.

**AT operations.** A distributed AT object provides processes with two operations:

- balance() / v returns the balance v of the calling process' account according to its current local vision.

- transfer(v, j) / r transfers the amount v from the account of the calling process to the account of p<sub>j</sub>, returns r = commit if the transfer succeeds, r = abort otherwise. For simplicity, if r = commit, we omit writing the result of the corresponding invocation: transfer<sub>i</sub>(v, j) / commit can be simply written transfer<sub>i</sub>(v, j).

The above balance() operation is more restricted than that of AFRT20 [1] as it only returns the balance of the local process, rather than the balances of the entire system. This is needed to ensure confidentiality (since a given process should not be able to read the accounts of other processes). Interestingly enough, this small change also allows us to obtain a sequential specification (instead of a concurrent specification [1]), as shown next.

It is assumed that the account of each process p<sub>i</sub> is initialized to a non-negative value denoted init<sub>i</sub> (in our QAAT implementation of Algorithm 3, init<sub>i</sub> is known only by p<sub>i</sub>).

**Histories and sequences.**

- A correct local history of a correct process p<sub>i</sub>, denoted L<sub>i</sub>, is a sequence of invocations made by p<sub>i</sub>. If an invocation o precedes another invocation o' in L<sub>i</sub>, we say that “o precedes o' in the process order of p<sub>i</sub>”, which is written o →<sub>i</sub> o'.

- A Byzantine local history of a Byzantine process p<sub>i</sub> is a sequence of transfer<sub>i</sub>(v, j) invocations that could have been issued by process p<sub>i</sub> from the point of view of correct processes. Let us remind that we do not know if Byzantine processes correctly implement the balance operation, so we omit the balance<sub>i</sub>() invocations in Byzantine local histories. Multiple possible Byzantine local histories for a given Byzantine process may exist as long as the content and order of this sequence are consistent with the local histories of the correct processes. Just like correct local histories, each Byzantine local history L<sub>i</sub> induces a total order relation →<sub>i</sub> between the invocation of L<sub>i</sub>.

- A global history H is an array of n local histories, one for each process: H = [L<sub>1</sub>, ..., L<sub>n</sub>], where L<sub>i</sub> is a correct local history if p<sub>i</sub> is correct, or a Byzantine local history if p<sub>i</sub> is
<table><caption>Table 2: Key notations used in the paper.</caption><thead><tr><th>Notation</th><th>Meaning</th></tr></thead><tbody><tr><td>λ, ε(λ), Adv</td><td>Security parameter, Negligible real number in [0; 1], Adversary</td></tr><tr><td>AT, QAAT</td><td>Asset transfer object, Quasi-anonymous asset transfer object</td></tr><tr><td>AP, σ, P<sub>A</sub></td><td>Agreement proof scheme, Agreement proof, AP predicate</td></tr><tr><td>c, o</td><td>Commitment digest, Opening</td></tr><tr><td>UA, A,<br>w, u</td><td>Universal accumulator scheme, Accumulator,<br>Membership proof, Non-membership proof</td></tr><tr><td>ZKP, π, P<sub>ZK</sub></td><td>Zero-knowledge proof scheme, Zero-knowledge proof, ZKP predicate</td></tr><tr><td>τ: ⟨snd, v, rcv, sn⟩</td><td>Asset transfer details: sender, amount, receiver, sequence number</td></tr></tbody></table>

* balance<sub>i</sub>()/v returns the account balance v of the calling process p<sub>i</sub> according to its current local vision.

* transfer<sub>i</sub>(v, j)/r transfers the amount v from the account of the calling process p<sub>i</sub> to the account of p<sub>j</sub>, returns r = commit if the account of p<sub>i</sub> has enough funds, r = abort otherwise. For simplicity, if r = commit, we omit the writing of the result of the corresponding invocation: transfer<sub>i</sub>(v, j)/commit can be simply written transfer<sub>i</sub>(v, j).

The above balance() operation is weaker than that of AFRT20 [1] as it can only return the balance of the local process, and not of any process of the system. This is needed to ensure confidentiality (since a given process should not be able to read the accounts of other processes).

It is assumed that the account of each process p<sub>i</sub> is initialized to a nonnegative value denoted init<sub>i</sub> (in our QAAT implementation of Algorithms 1–3, init<sub>i</sub> is known only by p<sub>i</sub>).

**Histories and sequences.**

* Let S = (o<sub>k</sub>)<sub>k∈[1..|S|]</sub> be a sequence of operation invocations. S might be finite (in which case |S| ∈ $\mathbb{N}$), or infinite (in which case |S| = +∞, and [1..|S|] = $\mathbb{N}$). We note set(S) the set of invocations in S, →<sub>S</sub> the total order defined by S, and transferSet(S) the set of transfer invocations contained in S (i.e., transferSet(S) = {k ∈ [1, |S|] | o<sub>k</sub> = transfer<sub>*</sub>(★,★)}).

* A local history of a correct process p<sub>i</sub>, denoted L<sub>i</sub>, is a sequence of operation invocations made by p<sub>i</sub>. If an invocation o precedes another invocation o' in L<sub>i</sub>, we say that “o precedes o' in the process order of p<sub>i</sub>”, which is written o →<sub>i</sub> o'.

* In a similar way, a local history of a Byzantine process p<sub>i</sub> is a sequence L<sub>i</sub> of operations invocations. However, because Byzantine processes might deviate arbitrarily from their prescribed behavior, these invocations do not necessarily correspond to how the behavior of Byzantine processes is perceived by correct processes.

* A global history H is an array of n local histories, one for each process: H = [L<sub>1</sub>, ..., L<sub>n</sub>].

* We use the notion of *mock history* to capture the perceived behavior of Byzantine processes [1]. Intuitively, a mock history $\hat{H}$ of some global history H is a history that preserves the local histories L<sub>i</sub> of correct processes p<sub>i</sub> but might change the local histories of Byzantine processes. More formally, $\hat{H} = [\hat{L}_1, ..., \hat{L}_n]$ is a mock history of H = [L<sub>1</sub>, ..., L<sub>n</sub>] iff $\hat{L}_i = L_i$ for all correct processes.

**Active processes.** Given a global history H, we say that a process is *active* in H if it is involved in a transfer<sub>i</sub>(v, j) operation invocation appearing in a local history L<sub>i</sub> of H, either as the calling process p<sub>i</sub> or as the receiver p<sub>j</sub>.

**AT-sequence.** Given a process ID i and a set of operation invocations O (performed by p<sub>i</sub> and other processes), the function total(i, O) returns the balance of the account of p<sub>i</sub> resulting from the transfers it sends and receives according to O (by adding the initial balance of p<sub>i</sub> to the funds received by p<sub>i</sub> in O, and subtracting the funds sent by p<sub>i</sub> in O):

$$total(i, O) = \text{init}_i + (\sum_{\text{transfer}_*(v,i) \in O} v) - (\sum_{\text{transfer}_i(v,*) \in O} v).$$
Byzantine.

■ A sequence $S$ of a global history $H$ is a topological sort of $H$ (i.e., a total order respecting all the process orders) that contains all the invocations of every process in $H$ and respects the process order $\rightarrow_i$ of each process $p_i$. In the following, $\rightarrow_S$ denotes the total order defined by $S$.

**AT-sequence.** Given a process ID $i$ and a set of invocations $O$, the function $total(i, O)$ returns the account balance of $p_i$ resulting from its operation invocations in $O$ (by adding the initial balance of $p_i$ to the funds received by $p_i$ in $O$, and subtracting the funds sent by $p_i$ in $O$):

$$total(i, O) = \text{init}_i + (\sum_{\text{transfer}_i(v, i) \in O} v) - (\sum_{\text{transfer}_i(v, \star) \in O} v).$$

A sequence $S$ of a global history $H$ is an asset-transfer-sequence (AT-sequence) if and only if:

1. $\forall o = \text{balance}_i() / v \in S : v = total(i, \{o' \in S | o' \rightarrow_S o\})$;

2. $\forall o = \text{transfer}_i(v, j) \in S : v \leq total(i, \{o' \in S | o' \rightarrow_S o\})$.

Informally, these conditions mean that the balance operation must return the balance of the process' account when it is invoked in the sequence, and the transfer operation must succeed (i.e., return commit) only if the balance of the debtor's account is sufficient. We say that a global history $H$ can be AT-sequenced if we can produce an AT-sequence with its invocations.

**AT properties.** A distributed algorithm $\mathcal{A}$ implements the AT specification iff it provides balance and transfer operations as defined before, such that the following properties hold.

■ **AT-Sequentiality.** Any global history $H$ from an execution of $\mathcal{A}$ can be AT-sequenced.

■ **AT-Termination.** All operations of $\mathcal{A}$ (balance and transfer) terminate for correct processes.

**Quasi-Anonymous Asset Transfer extension.** An algorithm $\mathcal{A}$ implements a Quasi-Anonymous AT object (QAAT for short) if it verifies the AT properties (stated above) and meets in addition the following privacy-preserving properties. Remind that $Adv$ denotes an adversary seeking to guess private information from the asset transfers of the system.

■ **QAAT-Receiver-Anonymity.** Given a global history $H$ produced by any execution of $\mathcal{A}$, any invocation $\text{transfer}_i(\star, j)$ contained in $H$, and $j' \in [1..n]$ a process identity chosen by $Adv$ attempting to guess $j$, then $\text{Pr}(j = j') \leq \min((1/n) + \epsilon(\lambda), 1)$.

■ **QAAT-Confidentiality.** Given a global history $H$ from an execution of $\mathcal{A}$, an arbitrary invocation $\text{transfer}_i(v, \star)$ contained in $H$, and $v' \in \mathbb{R}^+$ an amount chosen by the adversary $Adv$ attempting to guess $v$, then $\text{Pr}(v = v') \leq \epsilon(\lambda)$.

Informally, if we consider an adversary $Adv$ with absolutely no information on a transfer $\text{transfer}_i(v, j)$, the best this adversary can do is to pick $v \in \mathbb{R}^+$ and $j \in [1..n]$ uniformly at random. Doing so, $Adv$ will guess $j$ correctly with a probability of $1/n$, and $v$ with a probability of $0.6$. The above two properties capture that a Quasi-Anonymous Asset Transfer can be made arbitrarily close to this ideal situation by increasing the security parameter $\lambda$ of the cryptographic schemes.<fnref n="7" />

<footnote n="6">⁶ For simplicity, we assume that $v$ is defined on $\mathbb{R}^+$, but in practice $v$ is a bounded positive number.</footnote>

<footnote n="7">⁷ Recall that $\lim_{\lambda \to +\infty} \epsilon(\lambda) = 0$.</footnote>
A sequence $S$ of invocations is an *asset-transfer-sequence (AT-sequence)* if and only if:

1. $\forall i \in [0..n], \forall o = \text{balance}_i() / v \in S: v = \text{total}(i, \{o' \in S | o' \to_S o\})$;

2. $\forall i, j \in [0..n], \forall o = \text{transfer}_i(v, j) \in S: v \le \text{total}(i, \{o' \in S | o' \to_S o\})$.

Informally, these conditions mean that the balance operation must return the balance of the process's account when it is invoked in the sequence, and the transfer operation must succeed (i.e., return `commit`) only if the balance of the debtor's account is sufficient according to the sequence $S$.

We say that a global history $H$ can be *AT-sequenced* iff for every correct process $p_i$ there exists an *AT-sequence* $S_i$ with the following properties:

* $S_i$ contains exactly all of $p_i$'s invocations (both $\text{transfer}_i$ and $\text{balance}_i$ invocations), and all transfers by other processes, i.e., $\text{set}(S_i) = \text{set}(L_i) \cup \bigcup_{j \ne i} \text{transferSet}(L_j)$.

* $S_i$ respects $p_i$'s process order, i.e., $\to_i \subseteq \to_{S_i}$.

Intuitively, the above conditions ensure that each process $p_i$ can explain its local execution (Condition 1 of the AT-sequence definition above) from the transfers contained in the system in a way that respects $p_i$'s local order and the invariant that no account should ever be negative (Condition 2 of the AT-sequence definition).

**AT properties.** A distributed algorithm $\mathcal{A}$ implements the AT specification iff it provides balance and transfer operations as defined earlier, such that the following properties hold.

* **AT-Termination.** All operation invocations of $\mathcal{A}$ (balance and transfer) by correct processes terminate.

* **AT-Sequentiality.** For any global history $H$ capturing an execution of $\mathcal{A}$, there exists a mock history $\hat{H}$ of $H$ that can be AT-sequenced.

**Quasi-Anonymous Asset Transfer.** An algorithm $\mathcal{A}$ implements a Quasi-Anonymous AT object (QAAT for short) if it verifies the AT properties (stated above) and also meets the following privacy-preserving properties. Recall that $\text{Adv}$ denotes an adversary trying to guess private information from system asset transfers.

* **QAAT-Receiver-Anonymity.** For any global history $H$ capturing an execution of $\mathcal{A}$, for any invocation $\text{transfer}_i(\star, j)$ contained in $H$ where $p_i$ and $p_j$ are correct processes, then, with high probability, $p_j$ is indistinguishable among all the correct active processes of $H$.

* **QAAT-Confidentiality.** For any global history $H$ capturing an execution of $\mathcal{A}$, for any invocation $\text{transfer}_i(v, j)$ contained in $H$ where $p_i$ and $p_j$ are correct processes, then, with high probability, $v$ is indistinguishable among any value in $\mathbb{R}^+$.

Informally, if we consider an adversary $\text{Adv}$ and a transfer$_i(v, j)$ invocation appearing in a global history $H$, where $p_i$ and $p_j$ are correct processes, the best $\text{Adv}$ can do (w.h.p.) is to pick $v \in \mathbb{R}^+$ and $j \in [1..n]$ uniformly at random. Doing so, $\text{Adv}$ will guess $j$ correctly with a probability inversely proportional to the number of active processes in $H$, and $v$ with a probability of $0.7$ The above two properties capture that a Quasi-Anonymous Asset Transfer can be made arbitrarily close to this ideal situation by increasing the number of correct active processes and the security parameter $\lambda$ of the cryptographic schemes. Furthermore, in our QAAT implementation (Algorithms 1–3), since each correct process $p_i$ is the only one knowing its initial account balance $\text{init}_i$, QAAT-Confidentiality ensures that the account balance of $p_i$ also remains private throughout the execution with high probability.

# 5 A Modular Approach: Underlying Building Blocks

The QAAT algorithm proposed in this paper follows a modular approach. Before moving to our actual contributions in Section 6, we present in this section the cryptographic schemes upon which our QAAT system builds, namely, *Commitments*, *Universal Accumulators* (UA), and *Zero-Knowledge Proofs* (ZKP). Each scheme features a proving algorithm that aims to convince a verifying algorithm of some

<footnote n="7">⁷For simplicity, we assume that $v$ is defined on $\mathbb{R}^+$, but in practice, $v$ is a bounded positive number.</footnote>
## 4 A Modular Approach: Underlying Building Blocks

The QAAT algorithm proposed in this paper follows a modular approach. It builds upon several distributed and cryptographic schemes we present in this section before moving to the actual QAAT algorithm in Section 5. These schemes all require an implicit *setup* operation that takes as input the security parameter $\lambda$ and outputs the public parameters of the scheme, which are known to all processes, including the adversary. For instance, in a digital signature scheme, public parameters correspond to the set of all the system's public keys. All the cryptographic schemes that follow implicitly use some public parameters (although these parameters are not exposed explicitly in the specifications and algorithms). The domains of definition for the input values and output proofs of our schemes are respectively called $\mathbb{D}$ and $\mathbb{F}$. Each scheme features a proving algorithm that aims to convince a verifying algorithm of some claim through a proof. In the following, the proving algorithm is called the *prover*, while the verifying algorithm is called the *verifier*. Formally, both the prover and the verifier are poly-time probabilistic algorithms. For simplicity, we do not provide explicit termination guarantees for the purely cryptographic schemes presented in this section (VC, UA, and ZKP), as their operations consist only of mathematical computations and do not involve communication with other processes, unlike agreement proofs (AP).

### 4.1 A new distributed scheme: Agreement Proofs (AP)

An *Agreement proof* scheme (AP) is a new distributed scheme defined by two (explicit) operations *ap_prove* and *ap_verify* satisfying four properties. The AP scheme aims at producing transferable agreement proofs (APs) that the system has reached an agreement regarding some payload *v* originating from a given sender/prover $p_i$ with sequence number $sn_i$. Sequence numbers uniquely identify each proof the prover generates, and a new *sn* is generated by the scheme at each new proof, making the scheme *multi-shot* (i.e., a given prover can generate multiple proofs). In the asset transfer system we present in Section 5, the AP scheme precludes double-spending. In addition, an AP also shows that the system verified some arbitrary predicate $P_A$. The *ap_prove* operation is typically implemented by a distributed algorithm involving communication between a process and a system of verifiers. For instance, the AP scheme can be implemented using quorums, consensus, or reliable broadcast. An example of consensus-free AP implementation with a constant storage complexity and a communication complexity of $O(n)$ is presented in Appendix B.3.

**AP predicate.** Each object of an AP scheme is set up with a specific predicate $P_A$, called an *AP predicate*, taking in parameter some arbitrary *data*, and returning *true* or *false*. The prover $p_i$ passes to the *ap_prove* operation the payload *v* and the *data* parameter of $P_A$, and the proof $\sigma_i$ is correctly generated only if $P_A(\mathit{data}) = \mathit{true}$. Typically, the $P_A$ predicate can be passed to the implicit setup operation of the AP scheme, although the $P_A$ predicate could also change dynamically for a given AP object.

**AP operations.** We consider an AP object $O_A$ set up with an AP predicate $P_A$.

- $O_A.ap\_prove(v, data)/r$: Given the prover $p_i$, a value $v$ and some *data*, returns $r = \langle \sigma_i, sn_i, i \rangle$ if the input $P_A(\mathit{data})$ is true, where $\sigma_i$ and $sn_i$ are respectively an agreement proof and a sequence number for value $v$, or $r = \mathit{abort}$ otherwise.

- $O_A.ap\_verify(\sigma_j, v, sn_j, j)/r$: Returns the validity $r \in \{\mathit{true}, \mathit{false}\}$ of an agreement proof $\sigma_j$ for a value $v$ of a prover $p_j$ at a sequence number $sn_j$.

**Validity of an AP σ.** Given an AP object $O_A$, a value $v$, a sequence number $sn_i$ and a prover $p_i$ (correct or faulty), we say that some $\sigma$ is a "valid AP for $v$ at $sn_i$ from $p_i$" if and
claim through a proof. In the following, the proving algorithm is called the prover, while the verifying algorithm is called the verifier. Due to space constraints, the full definition of the properties of these cryptographic schemes is given in Appendix A.

**Commitments.** A *commitment* scheme allows one to create a commitment *c* to a chosen value *v* while keeping this value hidden from others, with the ability to reveal the committed value later through a proof *o* called opening.

A commitment scheme provides 2 operations: (i) $c_commit(v)/\langle c, o \rangle$ takes a value $v$ and outputs the corresponding commitment $c$ and opening $o$, and (ii) $c_verify(c, v, o)/r$ outputs $r = \text{true}$ if $o$ is a valid opening for the commitment $c$ and value $v$, and $r = \text{false}$ otherwise. Informally, a commitment scheme must be *binding* (it opens only to the committed value $v$) and *hiding* (it does not leak information on its committed value).

**Universal Accumulators (UA).** A *universal accumulator (UA) scheme* [7] produces a short commitment *A* (the accumulator) to a set of elements *E*, upon which the prover can produce both *membership proofs* *w* or *non-membership proofs* *u* of elements *e* in the set *E*, without divulging any other information. We assume each process creates an empty accumulator during the system's setup phase (see Appendix E).

Consider an accumulator *A*, its associated accumulated set *E*, and an arbitrary value *v*. A UA scheme provides 6 operations: (i) *ua_is_empty(A)*/*b* takes *A* and outputs *b* = *true* if *E* = *Ø*, and *b* = *false* otherwise; (ii) *ua_add(A, v)*/*A'* takes *A* and *v* and outputs the updated accumulator *A'* containing *v*; (iii) *ua_prove_mem(A, E, v)*/*r* takes *A*, *E*, and *v* and outputs a membership proof *r* = *w* of value *v* in accumulator *A* if *v* ∈ *E*, and *r* = *abort* otherwise; (iv) *ua_prove_non_mem(A, E, v)*/*r* takes *A*, *E*, and *v* and outputs a non-membership proof *r* = *u* of value *v* in *A* if *v* ∉ *E*, and *r* = *abort* otherwise; (v) *ua_verify_mem(A, v, w)*/*r* outputs *r* = *true* if *w* is a correct membership proof of *v* for *A*, and *r* = *false* otherwise; and (vi) *ua_verify_non_mem(A, v, u)*/*r* outputs *r* = *true* if *u* is a correct non-membership proof of *v* for *A*, and *r* = *false* otherwise.

Informally, a UA scheme must be *sound* (*proofs* are unforgeable), *complete* (the verification of (non-)membership works as intended), *undeniable* (an element cannot have both membership and non-membership proofs), and *indistinguishable* (the accumulator and proofs do not leak information on the set).

**Zero-Knowledge Proofs (ZKP).** A *zero-knowledge proof (ZKP) scheme* [42] produces proofs $\pi$ that a prover knows some *secret\_data* without divulging any other information on it to the verifier. Each object $Obj_{ZK}$ of a ZKP scheme is set up with a specific predicate $P_{ZK}$, called a *ZKP predicate*, taking as parameters *public\_data* (known both by the prover and verifier) and *secret\_data* (known only by the prover), and returning *true* or *false*. The prover $p_i$ passes to the zkp\_prove operation the *public\_data* and *secret\_data* parameters of $P_{ZK}$, and the proof $\pi_i$ is correctly generated only if $P_{ZK}(\text{public\_data}, \text{secret\_data}) = \text{true}$. The $P_{ZK}$ predicate is typically passed to the implicit setup operation of the ZKP scheme.

Consider a ZKP object $Obj_{ZK}$ set up with a ZKP predicate $P_{ZK}$. A ZKP scheme provides 2 operations: (i) $Obj_{ZK} \cdot \text{zkp\_prove}(\text{public\_data}, \text{secret\_data})/r$ outputs a result $r$, which can be either a zero-knowledge proof $r = \pi$ if the input parameters *secret\_data* and *public\_data* satisfy $P_{ZK}$ or $r = \text{abort}$ otherwise, and (ii) $Obj_{ZK} \cdot \text{zkp\_verify}(\pi, \text{public\_data})/r$ outputs the validity $r \in \{\text{true, false}\}$ of a zero-knowledge proof $\pi$ w.r.t. the *public\_data* and the ZKP predicate $P_{ZK}$. Informally, a ZKP scheme must be *knowledge-sound* (if a proof $\pi$ is valid, then the prover knows the associated *secret\_data*), *complete* (a valid proof $\pi$ can be generated from some *public\_data* and *secret\_data* that satisfy $P_{ZK}$), and *zero-knowledge* (a proof $\pi$ does not leak information on *secret\_data*).
only if any invocation of $O_A.ap_verify(\sigma, v, sn_i, i)$ by any correct process would return true.

**AP properties.** We consider an AP object $O_A$ set up with an AP predicate $P_A$.

- **AP-Validity.** If $\sigma_i$ is a valid AP for a value $v$ at sequence number $sn_i$ from a correct prover $p_i$, then $p_i$ has executed $O_A.ap_prove(v, \star)/\langle\sigma_i, sn_i\rangle$.

- **AP-Agreement.** There are no two different valid APs $\sigma_i$ and $\sigma'_i$ for two different values $v$ and $v'$ at the same sequence number $sn_i$ and from the same prover $p_i$.

- **AP-Knowledge-Soundness.** If $\sigma_i$ is a valid AP for value $v$ at sequence number $sn_i$ from a prover $p_i$ (correct or faulty), then $p_i$ knows some data such that $P_A(data)/\text{true}$.

- **AP-Termination.** Given a correct process $p_i$ that executes $O_A.ap_prove(v, data)/r$ with value $v$ and a data, if $P_A(data) = \text{true}$, then $r = \langle\sigma_i, sn_i\rangle$ and $\sigma_i$ is a valid AP for $v$ at $sn_i$ from $p_i$, and if $P_A(data) = \text{false}$, then $r = \text{abort}$.

## 4.2 Vector Commitment (VC)

A commitment scheme (as defined and used in [24, 42]) allows one to create a commitment $c$ to a chosen value $v \in \mathbb{D}$ while keeping it hidden from others, with the ability to reveal the committed value later through an opening $o$. In our system, we use a vector commitment scheme (*VC*), which guarantees that the commitments stay secure even if their associated input data is a vector of values $V \in \mathbb{D}^m$ of size $m \in \mathbb{N}^*$.

**VC operations.** We consider an arbitrary vector size $m \in \mathbb{N}^*$.

- $\text{vc\_commit}(V)/\langle c, o \rangle$: Takes a vector $V \in \mathbb{D}^m$ and outputs the corresponding commitment $c$ and opening $o$.

- $\text{vc\_verify}(c, V, o)/r$: Outputs $r = \text{true}$ if $o$ is a valid opening for the commitment $c$ and vector $V \in \mathbb{D}^m$, and $r = \text{false}$ otherwise.

**VC properties.** We consider arbitrary vector sizes $m, \ell \in \mathbb{N}^*$.

- **VC-Correctness.** $\forall V \in \mathbb{D}^m$, if $\text{vc\_commit}(V)/\langle c, o \rangle$ then $\text{vc\_verify}(c, V, o)/\text{true}$.
  Informally, a commitment created from a vector opens to this vector (using an opening).

- **VC-Binding.** $\forall V \in \mathbb{D}^m$, $\text{vc\_commit}(V)/\langle c, o \rangle$: $\text{Pr}(\text{vc\_verify}(c, V, o')/\text{true} \wedge o' \neq o) < \epsilon(\lambda)$.
  Informally, a commitment opens to only one vector (w.h.p.).

- **VC-Hiding.**
  $\forall c_1, c_2 \in \mathbb{F}, \forall V \in \mathbb{D}^m, \text{vc\_commit}(V)/\langle c, \star \rangle: |\text{Pr}(c = c_1) - \text{Pr}(c = c_2)| < \epsilon(\lambda)$.
  Informally, a commitment does not leak any information on its committed vector (w.h.p).

## 4.3 Universal Accumulators (UA)

An accumulator scheme (notion introduced in [5]) produces a short commitment to a set of elements $S$. A universal accumulator (UA) is a special kind of accumulator that can prove both the inclusion or non-inclusion of an element in the set by using *membership* or *non-membership proofs*, respectively. One of the most widely known examples of accumulators is Merkle trees [38]; however, Merkle trees do not exhibit some desirable accumulator properties provided by more efficient implementations, such as RSA accumulators [7].

In the following, we consider a new dynamic and universal accumulator scheme that does not need the knowledge of the entire accumulated set $S$ to add or delete elements or produce membership and non-membership proofs. Furthermore, processes are not required to update the (non-)membership of their (non-)accumulated elements when additions or deletions are performed on the accumulator. To the best of our knowledge, no previously proposed
# 6 A Light Consensus-Free Quasi-Anonymous Asset Transfer Algorithm

Our novel asset-transfer system leverages the building blocks presented in Section 5 and comprises two main contributions. The first, Agreement Proofs, presented in Section 6.1 lies in a novel construct that produces transferable proofs that the processes have reached an agreement on some payload. The second, presented in Section 6.2 consists of our novel asset-transfer algorithm, which leverages the building blocks presented in section 5, and our novel Agreement Proofs to guarantee quasi-anonymity, lightness, and consensus freedom.

## 6.1 A new distributed scheme: Agreement Proofs (AP)

An Agreement proof scheme (AP) is a novel distributed scheme defined by two (explicit) operations ap_prove and ap_verify. It aims at producing transferable agreement proofs (APs) that the system has reached an agreement regarding some payload value $v$ originating from a given sender/prover $p_i$ with sequence number $sn_i$. Sequence numbers uniquely identify each proof the prover generates using ap_prove, making the scheme multi-shot (i.e., a given prover can generate multiple proofs). Our asset-transfer algorithm, presented in Section 6.2, leverages APs to prevent double-spending. Hence, the AP scheme, specified in the following, provides easily interpretable properties that formalize the notion of cryptographic certificates, which are often used in distributed systems [3]. In Appendix D, we provide a consensus-free AP implementation with a storage complexity of $O(\lambda + n)$ and a communication complexity of $O(n\lambda)$.

**AP predicate.** Each object of an AP scheme is set up with a specific predicate $P_A$, called an AP predicate, taking in the AP's sequence number $sn$ and some arbitrary data as parameters, and returning true or false. The prover $p_i$ passes the payload $v$ and the data parameter of $P_A$ to the ap_prove operation, which generates a correct proof $\sigma_i$ only if $P_A(v, data, sn_i) = true$, where $sn_i$ is the sequence number of the current ap_prove invocation by $p_i$, i.e., the number of times the prover $p_i$ has invoked ap_prove up to the current invocation. We further assume that during system initialization, a valid genesis AP can be generated by the set-up procedure for a pair $(v, data)$ at sequence number $sn_i = 0$. (We return to the set-up procedure in Section 6.2.1 and discuss implementation details in Appendix E.)

**AP operations.** We consider an AP object $Obj_A$ set up with an AP predicate $P_A$.

* $Obj_A.ap_prove(v, data)/r$: Given the prover $p_i$, a payload value $v$ and some data, the operation returns $r = \sigma_i$ if the predicate $P_A(v, data, sn_i)$ is true, where $sn_i$ is the sequence number of the current ap_prove invocation by $p_i$, and $\sigma_i$ is an agreement proof for value $v$ at sequence number $sn_i$, or $r = \text{abort}$ otherwise.

* $Obj_A.ap_verify(\sigma_j, v, sn_j, j)/r$: The operation returns the validity $r \in \{\text{true, false}\}$ of an agreement proof $\sigma_j$ for a value $v$ of a prover $p_j$ at a sequence number $sn_j$.

**Validity of an AP $\sigma$.** Given an AP object $Obj_A$, a payload value $v$, a sequence number $sn_i$ and a prover $p_i$ (correct or faulty), we say that some $\sigma$ is a "valid AP for $v$ at $sn_i$ from $p_i$" if and only if any invocation of $Obj_A.ap_verify(\sigma, v, sn_i, i)$ by any correct process would return true.

**AP properties.** An AP object $Obj_A$ set up with an AP predicate $P_A$ satisfies four properties.

* **AP-Validity.** If $\sigma_i$ is a valid AP for a value $v$ at sequence number $sn_i > 0$ from a correct prover $p_i$, then $p_i$ has executed $Obj_A.ap_prove(v, \star)/\sigma_i$ as its $sn_i^{th}$ invocation of $Obj_A.ap_prove(\star, \star)$.

* **AP-Agreement.** There are no two different valid APs $\sigma_i$ and $\sigma'_i$ for two different values $v$ and $v'$ at the same sequence number $sn_i$ and from the same prover $p_i$. More formally, $Obj_A.ap_verify(\sigma_i, v, sn_i, i) = Obj_A.ap_verify(\sigma'_i, v', sn_i, i) = true$ implies $v = v'$.

* **AP-Knowledge-Soundness.** If $\sigma_i$ is a valid AP for value $v$ at sequence number $sn_i > 0$ from a prover $p_i$ (correct or faulty), then $p_i$ knows some data such that $P_A(v, data, sn_i)/true$.

* **AP-Termination.** Given a correct process $p_i$ that executes $Obj_A.ap_prove(v, data)/r$ with value $v$ and a data, if $P_A(v, data, sn_i) = true$ where $sn_i$ is the sequence number of the current ap_prove
accumulator possesses all these properties. Based on the Chinese remainder theorem [24], an implementation of this new accumulator is presented in Appendix B.1.

**Accumulator manager.** Each accumulator $A$ has a manager, which is the only process allowed to call the ua_add(), ua_delete(), ua_prove_mem() and ua_prove_non_mem() operations (described below) for $A$. This restriction is allowed because the manager is the only process who knows some secret needed to execute these operations. For classical accumulators [38, 7], this secret is typically the plain accumulated set$^8$, however, this secret is polylog-sized (i.e., $O_\lambda(\text{polylog }|S|)$) in our Chinese-remainder-based accumulator (Appendix B.1). Multi-manager accumulators are allowed by simply sharing the secret among multiple processes, but this inevitably compromises the indistinguishability of the accumulator for all co-managers. We assume that the empty accumulator of each manager is created during the system's setup phase (see Appendix C).

**UA operations.** We consider an accumulator $A$ and its associated accumulated set $S$.

- ua_is_empty($A$)/$b$: Takes $A$ and outputs $b = \text{true}$ if $S = \emptyset$, and $b = \text{false}$ otherwise.

- ua_add($A, v$)/$A'$: Takes $A$ and a value $v$ and outputs the updated accumulator $A'$ containing $v$.

- ua_delete($A, v$)/$r$: Takes $A$ and a value $v$ and outputs the updated accumulator $r = A'$ without $v$ if $v \in S$, and $r = \text{abort}$ otherwise.

- ua_prove_mem($A, v$)/$r$: Takes $A$ and a value $v$ and outputs a membership proof $r = w$ of value $v$ in accumulator $A$ if $v \in S$, and $r = \text{abort}$ otherwise.

- ua_prove_non_mem($A, v$)/$r$: Takes $A$ and a value $v$ and outputs a non-membership proof $r = u$ of value $v$ in $A$ if $v \notin S$, and $r = \text{abort}$ otherwise.

- ua_verify_mem($A, v, w$)/$r$: Outputs $r = \text{true}$ if $w$ is a correct membership proof of value $v$ for $A$, and $r = \text{false}$ otherwise.

- ua_verify_non_mem($A, v, u$)/$r$: Outputs $r = \text{true}$ if $u$ is a correct non-membership proof of value $v$ for $A$, and $r = \text{false}$ otherwise.

**UA properties.** We consider an accumulator $A$ and its associated set $S$.

- **UA-Soundness.** $\forall v \notin S, ua_prove_mem(A, S, v)/r : \Pr(r \neq \text{abort}) < \epsilon(\lambda)$ and $\forall v \in S, ua_prove_mem(A, S, v)/r : \Pr(r \neq \text{abort}) < \epsilon(\lambda)$.

Informally, the probability of computing a membership proof for a non-accumulated element or a non-membership proof for an accumulated element is negligible.

- **UA-Completeness.** $\forall v \in S, ua_verify_mem(A, v, ua_prove_mem(A, S, v))/r : \Pr(r = \text{true}) > 1-\epsilon(\lambda)$ and $\forall v \notin S, ua_verify_non_mem(A, v, ua_prove_non_mem(A, S, v))/r : \Pr(r = \text{true}) > 1-\epsilon(\lambda)$.

Informally, all honestly accumulated values are verified as true with their corresponding membership proof with a negligible probability of error.

- **UA-Undeniability.** $\forall v \in \mathbb{D}, \forall w, u \in \mathbb{F}: \Pr(ua_verify_mem(A, v, w) \wedge ua_verify_non_mem(A, v, u)) < \epsilon(\lambda)$.

Informally, the probability of computing both a membership and non-membership proof for the same element is negligible.

- **UA-Indistinguishability.** No information on some accumulated set $S$ is leaked from its associated accumulator $A$, membership proofs $w$ or non-membership proofs $u$.$^9$

<footnote>$^8$ With the only exception that RSA accumulators do not need the accumulated set to add new elements.</footnote>

<footnote>$^9$ For a more formal definition of Indistinguishability, we refer the interested reader to [17].</footnote>
1 **init**: $bal_i \leftarrow init_i; sn_i \leftarrow 0; \langle bal_{c_i}, bal_{o_i} \rangle \leftarrow c_commit(init_i); T_i \leftarrow \emptyset$;
$A_i \leftarrow$ empty universal accumulator of $p_i$;
$\sigma_i \leftarrow$ initial valid agreement proof for $\langle A_i, bal_{c_i} \rangle$ at $sn_i = 0$ from $p_i$.

**Algorithm 1:** Initialization of the variables of Algorithm 3 (code for $p_i$).

invocation by $p_i$, then $r = \sigma_i$ where $\sigma_i$ is a valid AP for $v$ at $sn_i$ from $p_i$. If $P_A(v, data, sn_i) = \text{false}$ then $r = \text{abort}$.

## 6.2 QAAT Algorithm

Our quasi-anonymous asset-transfer (QAAT) algorithm leverages agreement proofs to guarantee that there can be at most one transfer per sequence number from any process $p_i$ ensuring that a process cannot spend the same funds twice. In addition, it leverages non-membership proofs to guarantee that a given transfer is not already in the receiver's accumulator, ensuring that a process cannot redeem the same transfer twice.

### 6.2.1 Setup and initialization of process variables

We present in Algorithm 1 the initialization of each of the variables maintained by each process $p_i$ in our system: $bal_i$ (the balance of process $p_i$, only known to $p_i$ and initialized to $init_i$), $sn_i$ (the current sequence number of $p_i$, i.e., the one for $p_i$'s latest transfer, initialized to 0), $bal_{c_i}$ and $bal_{o_i}$ (respectively the commitment and opening of $bal_i = init_i$), $T_i$ (the set of transfers details of $p_i$, including debits and credits, initially empty), $A_i$ (a universal accumulator of $T_i$, recording all $p_i$'s debits and credits and initialized to the empty accumulator), and $\sigma_i$ (the previous agreement proof of $p_i$, initialized to a valid AP for the initial accumulator and balance commitment of $p_i$). We assume that the $bal_i$ and $sn_i$ variables are of constant size (e.g., 64 bits).

To initialize all these variables, and in particular $\sigma_i$, which involves communication among the processes, we employ the trustless setup procedure presented in Appendix E.

### 6.2.2 AP and ZKP predicates

Our system relies on an AP object *AccountUpdate*, and a ZKP object *TransferValidity*, both shown in Algorithm 2. They are respectively set up with the AP predicate $P_A$ and the ZKP predicate $P_{ZK}$ on line 2. A process creates new AP and ZKP objects each time it sends or receives an asset transfer. Hence, in these predicates, the prover can either be the sender or receiver of the asset transfer at hand. We also assume that these predicates have access to the identity of the prover, denoted *pvr*. In the following, *snd* and *rcv* refer to the sender and receiver (resp.). The statement **assert B**, where *B* evaluates to a Boolean, is a shortcut for “if $\neg B$ then return false”. Predicates return **true** by default.

**Predicate $P_A$**. The $P_A$ predicate takes 3 parameters: the payload $v$ (used both for the AP generation and verification), the *data* (used only for the AP generation), and the current sequence number of the prover $sn_{pvr}$. The $v$ parameter contains the new accumulator of the prover, $A'_{pvr}$, as well as the commitment to its new balance, $bal'_{c_{pvr}}$. The *data* parameter contains the previous AP of the prover, $\sigma_{pvr}$, the current ZKP of the prover, $\pi_{pvr}$, and some data $old\_state\_data_{pvr}$ about the state of the prover before the transfer. This $old\_state\_data_{pvr}$ contains the prover's preceding accumulator $A_{pvr}$ and a commitment to its previous balance $bal'_{c_{pvr}}$.

$P_A$ starts with some unpacking (line 4), and tuple concatenation (operation $\oplus$) to obtain the public data $public\_data_{pvr}$ describing the current transfer (line 5). $public\_data_{pvr}$ encompasses the prover's accumulator before applying the transfer $A_{pvr}$, a commitment $bal'_{c_{pvr}}$ to the prover's old balance, the
For simplicity and compliance with the traditional definitions given in the cryptography literature [7], we do not give properties for the ua_add and ua_delete operations. We implicitly assume that they behave correctly, that is, we can only prove the membership of an element that has been added but never deleted, we can only prove the non-membership for an element that has never been added or that has been deleted, and the ua_delete operation returns abort if the element was never added.

## 4.4 Zero-Knowledge Succinct Non-Interactive Arguments (zk-SNARGs)

By abuse of notation, we refer to the last scheme used in this article as zero-knowledge proofs (ZKP), which correspond to proofs that some prover knows some secret data without divulging any other information on it to the verifier. Specifically, we use Zero-Knowledge Succinct Non-Interactive Arguments (zk-SNARGs), which include zk-SNARKs and zk-STARKs [40].

**ZKP predicate.** Each object of a ZKP scheme is set up with a specific predicate $P_{ZK}$, called a ZKP predicate, taking in parameters a public data `public_data` (known both by the prover and verifier) and a secret data `secret_data` (known only by the prover), and returning true or false. The prover $p_i$ passes to the `zkp_prove` operation the `public_data` and `secret_data` parameters of $P_{ZK}$, and the proof $\sigma_i$ is correctly generated only if $P_{ZK}(\text{public\_data}, \text{secret\_data}) = \text{true}$. Much like the $P_A$ predicate, the $P_{ZK}$ predicate is typically passed to the implicit setup operation of the ZKP scheme.

**ZKP operations.** We consider a ZKP object $O_{ZK}$ set up with a ZKP predicate $P_{ZK}$.

- $O_{ZK}.zkp_prove(\text{public\_data}, \text{secret\_data})/r$: Returns a result $r$, which can be either a zero-knowledge proof $r = \pi$ if the input parameters `secret_data` and `public_data` satisfy $P_{ZK}$, or $r = \text{abort}$ otherwise.

- $O_{ZK}.zkp_verify(\pi, \text{public\_data})/r$: Returns the validity $r \in \{\text{true, false}\}$ of a zero-knowledge proof $\pi$ with respect to the public data `public_data` and the ZKP predicate.

**ZKP properties.** We consider a ZKP object $O_{ZK}$ set up with a ZKP predicate $P_{ZK}$.

- **ZKP-Knowledge-Soundness.** If $O_{ZK}.zkp_verify(\pi, \text{public\_data})$ is true, then the prover knows some `secret_data` such that $O_{ZK}.zkp_prove(\text{public\_data}, \text{secret\_data})/\pi$ and $P_{ZK}(\text{public\_data}, \text{secret\_data})$ is true.

- **ZKP-Completeness.** For any pair $(\text{public\_data}, \text{secret\_data})$ such that $P_{ZK}(\text{public\_data}, \text{secret\_data})$ is true, we must have $O_{ZK}.zkp_verify(O_{ZK}.zkp_prove(\text{public\_data}, \text{secret\_data}))$ is true.

- **ZKP-Zero-Knowledge.** No information on some secret data `secret_data` is leaked by its associated public data `public_data` and zero-knowledge proof $\pi$.<fnref n="10" />

# 5 A Light Consensus-Free Quasi-anonymous AT Algorithm

The asset transfer system presented in this section leverages the building blocks presented in Section 4. Intuitively, each process $p_i$ has an accumulator $A_i$ containing all its transfers (debits and credits), and a sequence number $sn_i$ for its last transfer. Agreement proofs guarantee that there can be at most one transfer per sequence number from $p_i$, in other words, they ensure that a process cannot spend twice the same funds. Non-membership proofs make sure that a given transfer is not already in the receiver's accumulator, in other words, they ensure that a process cannot redeem twice the same transfer.

<footnote n="10">¹⁰ For a more formal definition of Zero-Knowledge, we refer the interested reader to [25].</footnote>
2 **init**: AccountUpdate ← AP object setup with $P_A$;
TransferValidity ← ZKP object setup with $P_{ZK}$.

3 **predicate** $P_A(\langle A'_{pvr}, bal\_c'_{pvr} \rangle, \langle \sigma_{pvr}, \pi_{pvr}, old\_state\_data_{pvr} \rangle, sn_{pvr})$ **is**

▷ Unpacking data about the prover's preceding state

4 $\langle A_{pvr}, bal\_c_{pvr} \rangle \leftarrow old\_state\_data_{pvr}$;

5 $public\_data_{pvr} \leftarrow \langle A_{pvr}, bal\_c_{pvr} \rangle \oplus \langle A'_{pvr}, bal\_c'_{pvr}, sn_{pvr} \rangle$;

▷ $\pi_{pvr}$ proves the knowledge of a valid transfer fulfilling the ZKP predicate $P_{ZK}$ (line 9)
from $\langle A_{pvr}, bal\_c_{pvr} \rangle$ to $\langle A'_{pvr}, bal\_c'_{pvr} \rangle$

6 **assert** TransferValidity.zkp_verify($\pi_{pvr}, public\_data_{pvr}$);

▷ If this is the prover's first transfer, its preceding accumulator $A_{pvr}$ is empty

7 **if** $sn_{pvr} = 1$ **then** **assert** ua_is_empty($A_{pvr}$);

▷ The prover's preceding AP $\sigma_{pvr}$ is valid at sequence number $sn_{pvr} - 1$

8 **assert** AccountUpdate.ap_verify($\sigma_{pvr}, \langle A_{pvr}, bal\_c_{pvr} \rangle, sn_{pvr} - 1, pvr$).

9 **predicate** $P_{ZK}(public\_data, secret\_data)$ **is**

▷ Unpacking public and private data

10 $\langle A_{pvr}, bal\_c_{pvr}, A'_{pvr}, bal\_c'_{pvr}, sn_{pvr} \rangle \leftarrow public\_data$;

11 $\langle A'_{snd}, bal\_c_{snd}, \sigma_{snd}, w_{snd}, \tau, bal_{pvr}, bal\_o_{pvr}, bal\_o'_{pvr}, u_{pvr} \rangle \leftarrow secret\_data$;

▷ The public commitment for balance should match the private data

12 **assert** $c_verify(bal\_c_{pvr}, bal_{pvr}, bal\_o_{pvr})$;

▷ The prover's accumulator has received the transfer $\tau$, $A'_{pvr} = A_{pvr} \cup \{\tau\}$

13 **assert** ua_verify_non_mem($A_{pvr}, \tau, u_{pvr}$) ∧ ua_add($A_{pvr}, \tau) = A'_{pvr}$;

▷ The prover's balance has been properly updated

14 $\langle snd, v, rcv, sn_{snd} \rangle \leftarrow \tau$; **assert** $v \ge 0$;

▷ Trfs of sending APs are tagged with the AP's s.n. / a sending process has sufficient funds

15 **if** $pvr = snd$ **then** **assert** $sn_{snd} = sn_{pvr} \wedge bal_{pvr} \ge v$;

16 **if** $pvr = rcv$ **then** **assert** $c_verify(bal\_c'_{pvr}, bal_{pvr}, bal\_o'_{pvr})$;

17 **else if** $pvr = rcv$ **then** **assert** $c_verify(bal\_c'_{pvr}, bal_{pvr} - v, bal\_o'_{pvr})$;

18 **else if** $pvr = rcv$ **then**

19 **assert** $c_verify(bal\_c'_{pvr}, bal_{pvr} + v, bal\_o'_{pvr})$;

▷ A receiving prover implies a valid corresp. sending AP $\sigma_{snd}$ from the sender

20 **assert** ua_verify_mem($A'_{snd}, \tau, w_{snd}$);

21 **assert** AccountUpdate.ap_verify($\sigma_{snd}, \langle A'_{snd}, bal\_c_{snd} \rangle, sn_{snd}, snd$);

22 **else** return false.

<caption>**Algorithm 2:** AP and ZKP predicates of Algorithm 3.</caption>

prover's accumulator after the transfer $A'_{pvr}$, and a commitment $bal\_c'_{pvr}$ to the prover's new balance. $P_A$ then checks that the ZKP $\pi_{pvr}$ is valid (line 6) using the public data describing the transfer. Then, if this is the first transfer of the prover (debit or credit), $P_A$ checks that the prover's preceding accumulator is empty (line 7). Finally, $P_A$ verifies the prover's preceding AP (line 8).

**Predicate** $P_{ZK}$. The $P_{ZK}$ predicate takes two parameters as input: public_data and secret_data. The former, public_data, consists of the tuple constructed at line 5. The latter, secret_data, consists of the sender's accumulator $A_{snd}$ (recall that the sender is not always the prover), a commitment $bal\_c_{snd}$ of the sender's balance, the sender's AP $\sigma_{snd}$, the sender's membership proof $w_{snd}$ that the transfer is in $A_{snd}$ (notice that all the previous parameters are equal to $\perp$ if the prover is not the receiver as in this
**Algorithm 1** Initialization of the variables of Algorithm 3 (code for $p_i$).

1 **init:** $bal_i \leftarrow init_i$; $sn_i \leftarrow 0$; $\langle bal\_c_i, bal\_o_i \rangle \leftarrow vc\_commit(init_i)$;
   $A_i \leftarrow$ empty universal accumulator of $p_i$;
   $\sigma_i \leftarrow$ initial valid agreement proof for $\langle A_i, bal\_c_i \rangle$ at $sn_i = 0$ from $p_i$.

## 5.1 Setup and initialization of process variables

We present in Algorithm 1 the initialization of the variables of each process $p_i$ in our system: $bal_i$ (the balance of process $p_i$, only known by itself and initialized to $init_i$), $sn_i$ (the current sequence number of $p_i$, initialized to 0), $bal\_c_i$ and $bal\_o_i$ (respectively the commitment and opening of $bal_i = init_i$), $A_i$ (the universal accumulator for the transfers (debits and credits) of $p_i$, initialized to the empty accumulator where $p_i$ is the only manager), and $\sigma_i$ (the previous agreement proof of $p_i$, initialized to a valid AP for the initial accumulator and balance commitment of $p_i$). To keep our system light, we impose that the $bal_i$ and $sn_i$ variables are of constant size (e.g., 64 bits).

At the start of the system, we must use a setup procedure to obtain all these variables, and in particular $\sigma_i$, which involves communication among the processes. To this end, we present in Appendix C a trustless setup procedure for bootstrapping our system.

## 5.2 AP and ZKP predicates

Our system relies on an AP object *AccountUpdate*, and a ZKP object *Transfer Validity*, which are respectively set up with the AP predicate $P_A$ and the ZKP predicate $P_{ZK}$ given in Algorithm 2 (line 2). In our system, a process creates a new AP and ZKP each time it sends or receives an asset transfer. Hence, in these predicates, the prover can either be the sender or receiver of the asset transfer at hand. We also assume that these predicates have access to the identity of the prover, denoted *pvr*. In the following, *snd* and *rcv* refer to the sender and receiver (resp.).

**Predicate $P_A$.** The $P_A$ predicate takes as input in its *data* parameter the previous AP of the prover $\sigma_{pvr}$, the current ZKP of the prover $\pi_{pvr}$, the prover's last sequence number $sn_{pvr}$, and the public data $public\_data_{pvr}$ of $\pi_{pvr}$ (line 4).

$P_A$ first checks that the $\pi_{pvr}$ ZKP is valid (line 5). Then, if this is the first transfer of the prover (debit or credit), $P_A$ checks that the prover's accumulator is empty (line 7). Finally, $P_A$ verifies the prover's previous AP (line 8).

**Predicate $P_{ZK}$**. The $P_{ZK}$ predicate takes as input in its *public\_data* parameter the prover's accumulators before and after adding the new transfer $A_{pvr}$ and $A'_{pvr}$ (resp.), the commitments of the prover's balance before and after applying the new transfer $bal\_c_{pvr}$ and $bal\_c'_{pvr}$ (resp.), and the prover's commitment of the transfer $trf\_c_{pvr}$ (line 10).

The $P_{ZK}$ predicate takes as input in its *secret\_data* parameter the sender's accumulator $A_{snd}$ (recall that the sender is not always the prover), the commitment of the sender's balance $bal\_c_{snd}$, the sender's AP $\sigma_{snd}$, the sender's membership proof $w_{snd}$ that the transfer is in $A_{snd}$ (notice that all the previous parameters are equal to $\perp$ if the prover is not the receiver), the transfer $\tau$, the prover's opening of the transfer $bal\_o_{pvr}$, the prover's balance $bal_{pvr}$, the commitments of the prover's balance before and after applying the transfer $bal_{pvr}$ and $bal'_{pvr}$ (resp.), and the prover's non-membership proof $u_{pvr}$ that the transfer was not already in $A_{pvr}$ (line 11).

Recall that all checks of $P_{ZK}$ are done in zero-knowledge, without divulging any data to
case there are not used in the body of $P_{ZK}$), the transfer details $\tau$, the prover's opening of the transfer $bal_{o_{pvr}}$, the prover's balance $bal_{pvr}$, commitments of the prover's balance before and after applying the transfer $bal_{pvr}$ and $bal'_{pvr}$ (resp.), and the prover's non-membership proof $u_{pvr}$ that the transfer was not already in $A_{pvr}$ (line 11).

All the checks of $P_{ZK}$ are done in zero-knowledge, without divulging any data to the verifier(s). $P_{ZK}$ first checks that the commitments to the prover's balance and to the prover's transfer indeed open respectively to its balance (line 12). $P_{ZK}$ then checks that the prover's accumulator has been correctly updated, i.e., that the transfer did not already belong to the prover's old accumulator, and that the prover's new accumulator can be obtained by adding the transfer to its old accumulator (line 13). Finally, the $P_{ZK}$ predicate verifies two properties of the transfer: (i) that the prover's balance has been updated according to the transfer's information in $\tau$ (lines 14–19), and (ii), in case the prover is the receiver, that the passed AP $\sigma_{snd}$ is valid and matches $\tau$ on the sender's side (lines 20–21). In more detail, $P_{ZK}$ first verifies that if the prover is a sender, the transfer $\tau$ is stamped with the same sequence number $sn_{pvr}$ as that of the prover's current AP (line 15, $sn_{pvr}$ is passed as a parameter to $P_{ZK}$ from $P_A$ at line 6). Then, if the prover, sender and receiver are the same, $P_{ZK}$ checks that the prover's balance remains unchanged (line 16)<fnref n="8" />. Otherwise, if the prover is only the sender, $P_{ZK}$ ensures the transfer amount has been subtracted from the prover's balance, and that the prover had enough funds to perform the transfer (line 17). Finally, if the prover is only the receiver, then $P_{ZK}$ verifies that the new prover's balance was obtained by adding the transfer's amount to its old balance (line 19), that the sender's accumulator contains the transfer (line 20), and that the sender's AP is valid (line 21). If the prover is neither the sender nor the receiver of $\tau$, $P_{ZK}$ returns `false` (line 22).

### 6.2.3 Algorithm

Algorithm 3 presents the code of our QAAT implementation for a process $p_i$. The balance operation simply returns the value of $bal_i$ (line 23). In the transfer operation, $p_i$ first checks it has enough funds (line 25). Then $p_i$ creates the transfer details $\tau$ with its next sequence number (line 26), processes its own transfer using the process_transfer internal operation (line 27), creates a membership proof $w_i$ of the transfer in its accumulator (line 28), sends all the necessary information to the receiver in a TRANSFER message (line 29) and returns commit (line 30). When $p_i$ receives a TRANSFER message, it processes the transfer using the process_transfer internal operation if it is the transfer receiver, and if the sender's AP and membership proof are valid (line 33).

In the process_transfer internal operation, $p_i$ first computes its new balance $bal'_i$ depending on whether it is the sender or receiver (line 35), and commits its new value (line 36). Next, $p_i$ proves the non-membership of the transfer $\tau$ in its old accumulator $A_i$ (line 37) and creates its new accumulator by adding the transfer (line 38). Process $p_i$ then constructs the ZK proof $\pi$ that the transfer $\tau$ is valid (lines 39–42). It then creates the public data (line 40) and secret data (line 41) of the ZKP, and generates the ZKP (line 42). Next, $p_i$ creates the data of the Agreement Proof (AP) predicate (line 43). Finally, $p_i$ generates the AP $\sigma_i$ (line 44) before updating its local state (line 45).

### 6.2.4 Intuition of Algorithm 3's proofs

In this section, we sketch the high-level intuition behind the correctness of our solution. The full correctness developments are given in Appendix B.

**Correctness proof.** The correctness of our system comes from the fact that it satisfies AT-Sequentiality and AT-Termination.

**Lemma 6.1 (AT-Sequentiality).** For any global history $H$ capturing an execution of Algorithm 3, there exists a mock history $\hat{H}$ of $H$ that can be AT-sequenced.

<footnote n="8">⁸This condition is needed to support empty transfers, which are used to enhance the sender anonymity of the system.</footnote>
<caption>**Algorithm 2** AP and ZKP predicates of Algorithm 3.</caption>

2 **init:** AccountUpdate ← AP object setup with $P_A$;
Transfer Validity ← ZKP object setup with $P_{ZK}$.
3 **predicate** $P_A(\mathit{data})$ **is**
4 &nbsp;&nbsp;&nbsp;&nbsp;$(\sigma_{pvr}, \pi_{pvr}, \mathit{sn}_{pvr}, \mathit{public\_data}_{pvr}) \leftarrow \mathit{data}$;
5 &nbsp;&nbsp;&nbsp;&nbsp;if $\neg \mathit{Transfer Validity.zkp\_verify}(\pi_{pvr}, \mathit{public\_data}_{pvr})$ **then** return false;
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(A_{pvr}, \star, \mathit{bal\_c}_{pvr}, \star, \star) \leftarrow \mathit{public\_data}_{pvr}$;
7 &nbsp;&nbsp;&nbsp;&nbsp;if $\mathit{sn}_{pvr} = 1 \land \neg \mathit{ua\_is\_empty}(A_{pvr})$ **then** return false;
8 &nbsp;&nbsp;&nbsp;&nbsp;return AccountUpdate.ap_verify($\sigma_{pvr}, (A_{pvr}, \mathit{bal\_c}_{pvr}), \mathit{sn}_{pvr}, pvr$).
9 **predicate** $P_{ZK}(\mathit{public\_data}, \mathit{secret\_data})$ **is**
10 &nbsp;&nbsp;&nbsp;&nbsp;$(A_{pvr}, A'_{pvr}, \mathit{bal\_c}_{pvr}, \mathit{bal\_c'}_{pvr}, \mathit{trf\_c}_{pvr}) \leftarrow \mathit{public\_data}$;
11 &nbsp;&nbsp;&nbsp;&nbsp;$(A_{snd}, \mathit{bal\_c}_{snd}, \sigma_{snd}, w_{snd}, \tau, \mathit{trf\_o}_{pvr}, \mathit{bal}_{pvr}, \mathit{bal\_o}_{pvr}, \mathit{bal\_o'}_{pvr}, u_{pvr}) \leftarrow \mathit{secret\_data}$;
12 &nbsp;&nbsp;&nbsp;&nbsp;if $\neg \mathit{vc\_verify}(\mathit{bal\_c}_{pvr}, \mathit{bal}, \mathit{bal\_o}_{pvr})$ **then** return false;
13 &nbsp;&nbsp;&nbsp;&nbsp;if $\neg \mathit{ua\_verify\_non\_mem}(A_{pvr}, \tau, u_{pvr})$ **then** return false;
14 &nbsp;&nbsp;&nbsp;&nbsp;if $\mathit{ua\_add}(A_{pvr}, \tau) \neq A'_{pvr}$ **then** return false;
15 &nbsp;&nbsp;&nbsp;&nbsp;if $\mathit{vc\_verify}(\mathit{trf\_c}_{pvr}, (\tau, u_{pvr}, A_{snd}, \mathit{bal\_c}_{snd}, \sigma_{sand}, w_{sand}), \mathit{trf\_o}_{pvr})$ **then**
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return false;
17 &nbsp;&nbsp;&nbsp;&nbsp;$(\mathit{snd}, v, \mathit{rcv}, \mathit{sn}_{sand}) \leftarrow \tau$;
18 &nbsp;&nbsp;&nbsp;&nbsp;if $pvr = \mathit{sand} = \mathit{rcv}$ **then** return $\mathit{vc\_verify}(\mathit{bal\_c'}_{pvr}, \mathit{bal}_{pvr}, \mathit{bal\_o'}_{pvr})$;
19 &nbsp;&nbsp;&nbsp;&nbsp;if $pvr = \mathit{sand}$ **then** return $\mathit{vc\_verify}(\mathit{bal\_c'}_{pvr}, \mathit{bal}_{pvr} - v, \mathit{bal\_o'}_{pvr}) \land \mathit{bal}_{pvr} \ge v$;
20 &nbsp;&nbsp;&nbsp;&nbsp;if $pvr = \mathit{rcv}$ **then** return $\mathit{vc\_verify}(\mathit{bal\_c'}_{pvr}, \mathit{bal}_{pvr} + v, \mathit{bal\_o'}_{pvr})$
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\land \mathit{ua\_verify\_mem}(A_{sand}, \tau, w_{sand})$
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\land \mathit{AccountUpdate.ap\_verify}(\sigma_{sand}, (A_{sand}, \mathit{bal\_c}_{sand}), \mathit{sn}_{sand}, \mathit{sand})$;
21 &nbsp;&nbsp;&nbsp;&nbsp;return false.

the verifier(s). $P_{ZK}$ first checks that the commitment to the prover's balance indeed opens to its balance (line 12) and that the transfer does not already belong to the prover's old accumulator (line 13). $P_{ZK}$ then checks if the prover's new accumulator can be obtained by adding the transfer to its old accumulator (line 14). Next, if the prover, sender and receiver are the same, $P_{ZK}$ checks that the prover's balance is the same before and after the transfer (line 18)<fnref n="11" />. Otherwise, if the prover is only the sender, then $P_{ZK}$ checks that the new prover's balance is obtained by subtracting the transfer amount from the old balance, and that the old balance was sufficient to do the transfer (line 19). Finally, if the prover is only the receiver, then $P_{ZK}$ checks that the new prover's balance is obtained by adding the transfer amount to the old balance, that the sender's accumulator contains the transfer, and that the sender's AP is valid (line 20). If neither of the 3 last conditions passed, $P_{ZK}$ returns false (line 21).

<footnote n="11">¹¹This condition is needed to support empty transfers, which are used to enhance the sender anonymity of the system.</footnote>
23 **operation balance() is** return $bal_i$.

24 **operation transfer(v, j) is**

25 if $v < 0 \lor v > bal_i$ then return abort;

26 $\tau \leftarrow \langle i, v, j, sn_i + 1 \rangle$;

27 process_transfer($\tau$, $\perp$, $\perp$, $\perp$, $\perp$); ▷Producing ZKP and Agreement Proof for $\tau$

28 $w_i \leftarrow ua_prove_mem(A_i, T_i, \tau)$; ▷Membership proof that $\tau$ is now in $A_i$

29 ra_send TRANSFER($\tau$, $\sigma_i$, $A_i$, $w_i$, $bal_c_i$) to $p_j$; ▷ra_send is receiver-anonymous

30 return commit.

31 **when** TRANSFER($\tau$, $\sigma_j$, $A_j$, $w_j$, $bal_c_j$) **is** ra_received **from** $p_j$ **do**

32 if $\{\tau.rcv = i \land ua_verify_mem(A_j, \tau, w_j) \land AccountUpdate.ap_verify(\sigma_j, \langle A_j, bal_c_j \rangle, \tau.sn, j)\}$ then

33 process_transfer($\tau$, $A_j$, $bal_c_j$, $\sigma_j$, $w_j$).

34 **internal operation** process_transfer($\tau$, $A_j$, $bal_c_j$, $\sigma_j$, $w_j$) **is**

35 ▷Computing new balance with corresponding commitment and opening

35 $bal'_i \leftarrow bal_i$; **if** $i = \tau.snd$ **then** $bal'_i \leftarrow bal'_i - \tau.v$; **if** $i = \tau.rcv$ **then** $bal'_i \leftarrow bal'_i + \tau.v$

36 $\langle bal_c'_i, bal_o'_i \rangle \leftarrow c_commit(bal'_i)$; ▷New commitment and opening for $bal'_i$

37 $u_i \leftarrow ua_prove_non_mem(A_i, T_i, \tau)$; ▷Non-membership proof, $\tau$ not in $A_i$

38 $A'_i \leftarrow ua_add(A_i, \tau)$; ▷Adding new transfer to accumulator

39 ▷Constructing ZK proof that transfer is valid

39 $old_state_data \leftarrow \langle A_i, bal_c_i \rangle$;

40 public_data $\leftarrow$ old_state_data $\oplus$ $\langle A'_i, bal_c'_i, sn_i + 1 \rangle$;

41 secret_data $\leftarrow$ $\langle A_j, bal_c_j, \sigma_j, w_j, \tau, bal_i, bal_o_i, bal_o'_i, u_i \rangle$;

42 $\pi \leftarrow$ TransferValidity.zkp_prove(public_data, secret_data);

43 ▷Obtaining Agreement Proof (AP) on transfer's validity

43 data $\leftarrow \langle \sigma_i, \pi, old_state_data \rangle$;

44 $\sigma_i \leftarrow AccountUpdate.ap_prove(\langle A'_i, bal_c'_i \rangle, data)$;

45 ▷Updating local state

45 $sn_i \leftarrow sn_i + 1$; $A_i \leftarrow A'_i$; $bal_i \leftarrow bal'_i$; $bal_c_i \leftarrow bal_c'_i$; $bal_o_i \leftarrow bal_o'_i$.

<caption>**Algorithm 3:** QAAT algorithm (code for $p_i$).</caption>

*Proof sketch.* The proof first constructs the mock history $\hat{H}$ by starting from the UAs linked to the APs generated by correct processes, and then recursively traversing these UAs and APs using the predicates $P_A$ and $P_{ZK}$ to uncover UAs issued by Byzantine processes that are causally linked to the operations of correct processes. Each UA yields information on a transfer invocation at a given sequence number, which we then use to construct the mock local execution $\hat{L}_j$ of each Byzantine process $p_j$.

Given a correct process $p_i$, we then construct a partial $\rightsquigarrow_i$ order on $S_i = \text{set}(\hat{L}_i) \cup \bigcup_{j \neq i} \text{transferSet}(\hat{L}_j)$. This construction is somewhat technical for two reasons: (1) Transfers might not be received in the order they were issued (in particular by $p_i$), which implies $\rightsquigarrow_i$ should not enforce any local process order $\rightarrow_j$ other than that of $p_i$. (2) Simultaneously, $\rightsquigarrow_i$ should be constraining enough to guarantee that balance invocations by $p_i$ exactly reflect previous transfers (Property n.1 of an AT-sequence in Section 4) and that each transfer is backed by sufficient funds (Property n.2). We construct $\rightsquigarrow_i$ incrementally using two binary relations: $\rightsquigarrow_i^1$ that captures $p_i$'s local order and ensures that all transfers are sufficiently funded, and $\rightsquigarrow_i^2$ to guarantee balance invocations by $p_i$ can be properly explained. Part of the proof focuses on the acyclicity of $\rightsquigarrow_i^1 \cup \rightsquigarrow_i^2$, so that $\rightsquigarrow_i$ can be defined as the transitive closure
<caption>■ Algorithm 3 Light and consensus-free QAAT algorithm (code for $p_i$).</caption>

22 operation balance() is return $bal_i$.
23 operation transfer($v, j$) is
24 if $v > bal_i$ then return abort;
25 $\tau \leftarrow \langle i, v, j, sn_i + 1 \rangle$;
26 process_transfer($\tau, \perp, \perp, \perp, \perp$);
27 $w_i \leftarrow ua\_prove\_mem(A_i, \tau)$;
28 ra\_send TRANSFER($\tau, \sigma_i, A_i, w_i, bal\_c_i$) to $p_j$; $\triangleright$ ra\_send is receiver-anonymous
29 return commit.
30 when TRANSFER($\tau, \sigma_j, A_j, w_j, bal\_c_j$) is ra\_received from $p_j$ do
31 if $\tau.\rcv = i \land ap\_verify(\sigma_j, \langle A_j, bal\_c_j \rangle, \tau.sn, j) \land ua\_verify\_mem(A_j, \tau, w_j)$ then
32 process\_transfer($\tau, A_j, bal\_c_j, \sigma_j, w_j$).
33 internal operation process\_transfer($\tau, A_j, bal\_c_j, \sigma_j, w_j$) is
34 $u_i \leftarrow ua\_prove\_non\_mem(A_i, \tau)$;
35 $A'_i \leftarrow ua\_add(A_i, \tau)$;
36 if $i = \tau.snd = \tau.rcv$ then $bal'_i \leftarrow bal_i$;
37 else if $i = \tau.snd$ then $bal'_i \leftarrow bal_i - \tau.v$ else $bal'_i \leftarrow bal_i + \tau.v$;
38 $\langle bal\_c'_i, bal\_o'_i \rangle \leftarrow vc\_commit(bal'_i)$;
39 $\langle trf\_c'_i, trf\_o'_i \rangle \leftarrow vc\_commit(\langle \tau, u_i, A_j, bal\_c_j, \sigma_j, w_j \rangle)$;
40 public\_data $\leftarrow \langle A_i, A'_i, bal\_c_i, bal\_c'_i, trf\_c_i \rangle$;
41 secret\_data $\leftarrow \langle A_j, bal\_c_j, \sigma_j, w_j, \tau, trf\_o_i, bal_i, bal\_o_i, bal\_o'_i, u_i \rangle$;
42 $\pi \leftarrow Transfer Validity.zkp\_prove(public\_data, secret\_data)$;
43 data $\leftarrow \langle \sigma_i, \pi, sn_i + 1, public\_data \rangle$;
44 $\langle \sigma_i, \star \rangle \leftarrow AccountUpdate.ap\_prove(\langle A'_i, bal\_c'_i \rangle, data)$;
45 $sn_i \leftarrow sn_i + 1$; $A_i \leftarrow A'_i$; $bal_i \leftarrow bal'_i$; $bal\_c_i \leftarrow bal\_c'_i$; $bal\_o_i \leftarrow bal\_o'_i$.

## 5.3 Algorithm

Algorithm 3 presents the code of our QAAT implementation for a process $p_i$. The balance operation simply returns the value of $bal_i$ (line 22). In the transfer operation, $p_i$ first checks it has enough funds (line 24). Then $p_i$ creates the transfer details with its next sequence number (line 25), processes its own transfer using the process\_transfer internal operation (line 26), creates a membership proof of the transfer in its accumulator (line 27), sends all the necessary information to the receiver in a TRANSFER message (line 28) and returns commit (line 29). When $p_i$ receives a TRANSFER message, it processes the transfer using the process\_transfer internal operation if it is the transfer receiver, and if the sender's AP and membership proof are valid (line 32).

In the process\_transfer internal operation, $p_i$ first proves the non-membership of the transfer in its old accumulator (line 34) and creates its new accumulator by adding the transfer (line 35). If $p_i$ is both the sender and receiver, its balance does not change (line 36), otherwise $p_i$ computes its new balance depending on whether it is the sender or receiver (line 37). Next, $p_i$ commits its new balance (line 38) and the transfer information (line 39). Process $p_i$ then creates the public data (line 40) and secret data (line 41) of the ZKP, and generates the ZKP (line 42). Next, $p_i$ creates the data of the AP predicate (line 43). Finally, $p_i$ generates the AP (line 44) and updates its local variables (line 45).
$(\stackrel{1}{\rightsquigarrow}_i \cup \stackrel{2}{\rightsquigarrow}_i)^+$. Finally, we chose $S_i$ as a topological sort of $(S_i, \rightsquigarrow_i)$ and prove it fulfills the two properties of AT-Sequences. (Full derivations in Appendix B.1.) $\square$

**Lemma 6.2 (AT-Termination).** *All operation invocations of Algorithm 3 (balance and transfer) terminate for correct processes.* (Proof in Appendix B.1.)

**Quasi-anonymity proof.** Intuitively, our system is quasi-anonymous because it uses cryptographic schemes that do not leak sensitive data (i.e., commitments, universal accumulators, and zero-knowledge proofs). We prove the following lemmas in Appendix B.2.

**Lemma 6.3 (QAAT-Receiver-Anonymity).** *For any global history H capturing an execution of $\mathcal{A}$, for any invocation transfer$_i(\star, j)$ contained in H where $p_i$ and $p_j$ are correct processes, then, with high probability, $p_j$ is indistinguishable among all the correct active processes of H.* (Proof in Appendix B.2.)

**Lemma 6.4 (QAAT-Confidentiality).** *For any global history H capturing an execution of $\mathcal{A}$, for any invocation transfer$_i(v, j)$ contained in H where $p_i$ and $p_j$ are correct processes, then, with high probability, $v$ is indistinguishable among any value in $\mathbb{R}^+$. (Proof in Appendix B.2.)

**Succinctness.** The overall succinctness of our system stems from the succinctness of our Agreement Proof implementation (Appendix D.5), the constant size of the digests and proofs of RSA accumulators (Appendix C.2) and of commitments (Appendix C.3), and of the succinctness of Spartan zk-SNARKs (Appendix C.4). By definition, the proofs of computation produced by the prover of a succinct ZKP scheme are succinctly verified. Therefore, primitives whose verification is encapsulated inside the ZKP predicate only need to be constant size for our scheme to be succinct (although accumulator (non-membership proof verification and commitment openings can, in fact, be succinct).

**Storage of $O(\lambda + (|T|/n) \log n + n)$ bits per correct process.** In our system, each correct process $p_i$ only stores its local transfer details, the sequence number of each of the $n$ processes, and a few cryptographic structures, yielding a storage of $O(\lambda + (|T|/n) \log n + n)$, where $T$ is the set of all transfers in the system. Let us consider the size of $p_i$'s local variables. By definition, $bal_i$ and $sn_i$ are constant-size (see Section 6.2.3). Moreover, $bal_{c_i}$ and $bal_{o_i}$ have $O(\lambda)$ bits with a constant size commitment scheme (Appendix C.3), $A_i$ has $O(\lambda)$ bits with the constant size RSA accumulator implementation (Appendix C.2), and $\sigma_i$ has $O(\lambda)$ bits with our implementation of agreement proofs (Appendix D). Moreover, our AP algorithm stores $O(\lambda + n)$ bits per correct process (Appendix D). Finally, the $T_i$ set is of size $O(|T|/n)$ (where $T$ is the set of all transfers of the system) and contains transfer details of size $O(\log n)$ bits (because of process IDs). This amounts to a total storage cost of $O(\lambda + (|T|/n) \log n + n)$.

**Communication of $O(n\lambda)$ bits overall.** In our system, a transfer$_i(\star, j)$ invocation by a correct process $p_i$ entails the following communications: (i) the ap_prove invocation by the sender $p_i$ at line 44, (ii) the ra_send of the transfer details from the sender to the receiver at line 29, and (iii) the ap_prove invocation by the receiver $p_j$ at line 44 (which is only guaranteed to happen if $p_j$ is correct). As our Agreement Proof implementation (Appendix D) communicates only $O(\lambda n)$ bits overall (Appendix D.7), (i) and (iii) incur an overall communication of $O(\lambda n)$. For (ii), the receiver-anonymous ra_send operation can be implemented with an overall communication cost of $O(\lambda n)$, as discussed in Section 3. As a result, our system's overall communication cost is $O(\lambda n)$.

**Consensus-freedom.** This directly comes from our distributed Agreement Proof implementation (Appendix D), which does not rely on strong agreement such as consensus (Appendix D.4).

### 6.2.5 Further enhancements

**Transfer batching.** One could argue that requiring users to commit an accumulator update to the system each time they send or receive a single transfer is inefficient. To address this problem, we
## 5.4 Intuition of Algorithm 3's proofs

Due to space constraints, the full developments on our system's correctness, quasi-anonymity, lightness and consensus-freedom are given in Appendix A. Nonetheless, we describe in this section the high-level intuition behind these proofs.

**Correctness proof.** The correctness of our system comes from the fact that it satisfies AT-Sequentiality and AT-Termination.

**► Lemma 1 (AT-Sequentiality).** *Any global history H from an execution of Algorithm 3 can be AT-sequenced.*

**Proof sketch.** AT-Sequentiality is the property that poses the most important technical difficulty: we have to show that for any execution of our algorithm, there exists a way to create a sequence of invocations respecting all process orders (the AT-sequence) that contains all the transfer/balance invocations of all correct processes, and “fake” transfer invocations of Byzantine processes, such that the legality of the operations is respected. To do that, let us remark that it is sufficient to prove that we can create a strict (i.e., irreflexive) partial order defining the precedence of all transfer/balance correct invocations and transfer Byzantine invocations (thus forming a directed acyclic graph of all these invocations), such that the legality of the operations is respected. Indeed, once we have this legal partial order of invocations, we can trivially extend it to a legal total order (i.e., a topological sort), which would constitute the AT-sequence.

Hence, a method for constructing an AT-sequence must both describe (i) how the “fake” transfer$_i(\star, \star)$ Byzantine invocations are added to the Byzantine local histories $L_i$ of every Byzantine process $p_i$, and (ii) how the partial order of all invocations of the execution is constructed. We give in Appendix A.1 such a method, that we call $M$, for constructing an invocation sequence $S$. Using $M$, we “kill two birds with one stone” by using the set of valid agreement proofs that are produced by correct or faulty processes in the system, giving us both all Byzantine transfer invocations, and the partial order between all the transfer/balance invocations of the system. Finally, we show that any sequence $S$ produced using $M$ is an AT-sequence. (Full derivations in Appendix A.1.) ◀

**► Lemma 2 (AT-Termination).** *All operations of Algorithm 3 (balance and transfer) terminate for correct processes.* (Proof in Appendix A.1.)

**Quasi-anonymity proof.** Intuitively, our system is quasi-anonymous because it uses cryptographic schemes that do not leak sensitive data (i.e., vector commitments, universal accumulators, and zero-knowledge proofs). We prove the following lemmas in Appendix A.2.

**► Lemma 3 (QAAT-Receiver-Anonymity).** *Given the global history H produced by any execution of Algorithm 3, any transfer$_i(\star, j)$ invocation of H, and $j' \in [1..n]$ a process identity chosen by Adv trying to guess j, we must have: $\Pr(j = j') \le \min((1/n) + \epsilon(\lambda), 1)$. (Proof in Appendix A.2.)*

**► Lemma 4 (QAAT-Confidentiality).** *Given a global history H from an execution of Algorithm 3, an arbitrary transfer$_i(v, \star)$ invocation of H, and $v' \in \mathbb{R}^+$ an amount chosen by the adversary Adv trying to guess v, we must have: $\Pr(v = v') \le \epsilon(\lambda)$. (Proof in Appendix A.2.)*

**Informal arguments for lightness and consensus-freedom.** If we instantiate it with the implementations of Appendix B, our system is light (as it uses succinct cryptography and
propose aggregating an arbitrary number of transfers into a single accumulator update. As a result, a user could choose only to declare an accumulator update when making a payment, while cashing all receipts simultaneously when doing so. To implement transfer batching, we use an optimization method for ZK proofs known as folding [32] in Appendix F.

**Reducing local storage (public key rotation).** The QAAT system presented in this article is light, i.e., the storage cost per process $p_i$ is in $O(\lambda + (|T|/n) \log n + n)$, where $|T|$ is the set of all transfers (debits and credits) of the system. This storage cost is justified by $p_i$'s need to store some data whose size is proportional to its entire transfer history, to prove that it is not trying to redeem the same transfer several times. However, a public key rotation mechanism could be added to remove the need to store past transfers. When a process $p_i$ rotates its public key, it changes its old public key for a new one, while transferring all its funds to the account associated to the new public key. Once this is done, $p_i$ can flush its old local data (and, in particular, its accumulator data). Thus, the process only has to record information concerning this rotating transfer which can be seen as the genesis state of a newly created account, and obtains a storage cost of $O(\lambda + n)$. However, this mechanism would involve one major technical challenge: a sender has to retrieve the receiver's public key before it can send funds to her. To achieve this retrieval, the sender can initiate a handshake with the receiver, but due to asynchrony and the fact that the receiver may be faulty, the handshake may never complete, hampering the termination of the transfer. This method is briefly mentioned by Zef [3] as a solution to safely delete the data of unused accounts. To circumvent the incompatibility of its asynchronous model and the handshake, Zef assumes that each transfer is initiated in a synchronous environment outside the system where the receiver transmits its public key to the sender.

**Towards full anonymity.** Our system is not fully anonymous, as it guarantees Receiver Anonymity and Confidentiality, but not that the transfer issuer remains anonymous (i.e., Sender Anonymity). However, remark that our system allows “empty” transfers with amount 0 (or transfers to oneself), which do not change any balance. These empty transfers could be used to obfuscate the traffic of funds from the adversary’s point of view, and if they are issued at the right moment, we conjecture that they could preclude (w.h.p.) timing attacks, i.e., attacks where an adversary deanonymizes the sender (or receiver) of an asset transfer by observing the timing of messages transiting on the network. If so, our system would reach full anonymity asymptotically (by adding more empty transfers at some well-chosen moments). The design of the heuristics to choose the moments to issue empty transfers is left to future work.

# 7 Conclusion

This article considered the problem of asynchronous Byzantine-fault-tolerant asset transfer, with the additional constraint of satisfying the properties of quasi-anonymity (i.e., no leak of information on the transfers' amounts and receivers), lightness (i.e., succinct cryptography and light storage cost), and consensus-freedom (i.e., no total order of transfers). These properties are important for achieving good performance, confidentiality, and user privacy in an asset transfer system. In this context, this article introduced Quasi-Anonymous Asset Transfer (QAAT), and presented a consensus-free and light QAAT implementation, along with its formal proofs. To our knowledge, our asset transfer system is not only the first to fulfill the 3 properties, but also the first one to have a $O(\lambda|T|/n)$ storage cost, where $T$ is the set of all transfers of the system. In addition, the article presented a new distributed abstraction called Agreement Proofs, which captures the notion of distributed agreement in a transferable short-sized proof.

Presently, our asset transfer solution still lacks some capabilities compared to more mature blockchain systems (e.g., Sybil resistance or smart contracts) or mainstream payment networks (e.g., overdrawn accounts or fraud detection), but we believe that it demonstrates that systems with low verification, storage, and network costs can still guarantee strong privacy features. Furthermore, we conjecture that our system's scalability can be further enhanced, and in particular, that it can be made permissionless without sacrificing consensus-freedom, by leveraging techniques such as the ones introduced in [33].
our accumulator implementation requires storing polylog bits in the size of the accumulated set) and consensus-free (as we implement agreement proofs without consensus). More details are given in Appendix A.3.

## 5.5 Further enhancements

**Transfer batching.** One could argue that requiring users to commit an accumulator update to the system each time they send or receive a single transfer is inefficient. To address this problem, we propose aggregating an arbitrary number of transfers into a single accumulator update. As a result, a user could choose only to declare an accumulator update when making a payment, while cashing all receipts simultaneously when doing so. To implement transfer batching, we use a method known as folding in Appendix D.

**Constant local storage (public key rotation).** The QAAT system presented in this article is light, i.e., the storage cost of a given process $p_i$ is in $O_\lambda(\text{polylog } |S_i|)$, where $S_i$ is the set of transfers (debits and credits) of $p_i$. This storage cost is justified by $p_i$'s need to store some data whose size is proportional to its entire transfer history, to prove that it is not trying to redeem the same transfer several times. However, a public key rotation mechanism could be added to obtain a system with a constant storage cost. When a process $p_i$ rotates its public key, it changes its old public key for a new one, while transferring all its funds to the account associated to the new public key. Once this is done, $p_i$ can flush its old local data (and, in particular, its accumulator data) so that its storage cost stays bounded by a constant. Thus, the process only has to record information concerning this rotating transfer which can be seen as the genesis state of a newly created account. However, this mechanism would involve one major technical challenge: a sender has to retrieve the receiver's public key before it can send funds to it. To achieve this retrieval, the sender can initiate a handshake with the receiver, but due to asynchrony and the fact that the receiver may be faulty, the handshake may never complete, hampering the termination of the transfer.

**Towards full anonymity.** Our system is not fully anonymous, as we deterministically guarantee Receiver Anonymity and Confidentiality, but not Sender Anonymity. However, remark that our system allows “empty” transfers with amount 0 (or transfers to oneself), which do not change any balance. These empty transfers could be used to obfuscate the traffic of funds from the adversary’s point of view, and if they are issued at the right moment, we conjecture that they could preclude (w.h.p.) timing attacks, i.e., attacks where an adversary deanonymizes the sender (or receiver) of an asset transfer by observing the timing of messages transiting on the network. If so, our system would reach full anonymity asymptotically (by adding more empty transfers at “clutch moments”). The design of the heuristics determining the “clutch moments” for issuing empty transfers is left to future work.

# 6 Conclusion

This article considered the problem of asynchronous Byzantine-fault-tolerant asset transfer, with the additional constraint of satisfying the properties of quasi-anonymity (i.e., no leak of information on the transfers' amounts and receivers), lightness (i.e., succinct cryptography and polylogarithmic storage cost), and consensus-freedom (i.e., no total order of transfers). These properties are important for achieving good performance, confidentiality, and user privacy in an asset transfer system. In this context, this article introduced Quasi-Anonymous Asset Transfer (QAAT), and presented a consensus-free and light QAAT implementation,
# A Underlying Building Blocks: Full Definitions

This appendix section presents the full definitions of the cryptographic schemes used in our QAAT system, namely Commitments, Universal Accumulators (UA), and Zero-Knowledge Proofs (ZKP). More precisely, this section provides the operations and properties of these schemes.

These schemes all require an implicit *setup* operation that takes as input the security parameter $\lambda$ and outputs the public parameters of the scheme, which are known to all processes, including the adversary. For instance, in a digital signature scheme, public parameters correspond to the set of all the system's public keys. All the cryptographic schemes that follow implicitly use some public parameters (although these parameters are not exposed explicitly in the specifications and algorithms). The domains of definition for the input values and output proofs of our schemes are respectively called $\mathbb{D}$ and $\mathbb{F}$ (see Table 3). Each scheme features a proving algorithm that aims to convince a verifying algorithm of some claim through a proof. In the following, the proving algorithm is called the prover, while the verifying algorithm is called the verifier. Formally, both the prover and the verifier are poly-time probabilistic algorithms. For simplicity, the schemes presented in this section do not have explicit termination properties, as their operations only consist of local mathematical computations.

We further denote by $\varepsilon(\lambda)$ a positive number between 0 and 1 that can be made arbitrarily small by increasing $\lambda$.

<table><caption>Table 3: Input and output sets of the cryptographic schemes of Appendix A.</caption><thead><tr><td>Set</td><td>Meaning</td></tr></thead><tbody><tr><td>$\mathbb{D}$ (for “data”)</td><td>Input set (values) of the proving operations of the cryptographic schemes</td></tr><tr><td>$\mathbb{F}$ (for “finite”)</td><td>Output set (proofs) of the proving operations of the cryptographic schemes</td></tr></tbody></table>

## A.1 Commitment schemes

A commitment scheme is a cryptographic primitive that enables a prover to succinctly commit to a value $v$ in the form a small digest $c$ (the commitment) and compute a proof $o$ (the opening) that the commitment “opens” to $v$. Commitment schemes must be binding, i.e., the prover cannot find another value that matches the digest. Most schemes also have a hiding property, meaning that the digest does not reveal any information about the committed value. Some schemes allow digests to be combined to perform operations (e.g., addition or multiplication) on committed values, such as homomorphic schemes. There are many variants of commitments to handle different types of data, such as polynomials, vectors, or even functions. In our system, we use a simple *commitment* scheme (C) to a bounded integer.

### Commitment operations.

* $c_commit(v)/\langle c, o \rangle$ takes a value $v \in \mathbb{D}$ and outputs the corresponding commitment $c$ and opening $o$.

* $c_verify(c, v, o)/r$ outputs $r = true$ if $o$ is a valid opening for the commitment $c$ and value $v \in \mathbb{D}$, and $r = false$ otherwise.

### Commitment properties.

* **C-Correctness.** $\forall v \in \mathbb{D}$, if $c_commit(v)/\langle c, o \rangle$ then $c_verify(c, v, o)/true$. Informally, a commitment created from a value opens to this value (using an opening).

* **C-Binding.** $\forall c, o, o' \in \mathbb{F}, \forall v, v' \in \mathbb{D}: \Pr(c_verify(c, v, o)/true \land c_verify(c, v', o')/true \land v' \neq v) < \varepsilon(\lambda)$. Informally, a commitment opens to only one value (w.h.p.).
along with its formal proofs. To our knowledge, our asset transfer system is not only the first to fulfill the 3 properties, but also the first one to have a polylogarithmic storage cost.

In addition, the article presented a new distributed abstraction called Agreement Proofs, which captures the notion of distributed agreement in a transferable short-sized proof. It also presented a new implementation of universal accumulators based on the Chinese remainder theorem, the first one which does not need knowledge of the underlying accumulated set to add/delete elements or generate (non-)membership proofs.

Presently, our asset transfer solution still lacks some capabilities compared to more mature blockchain systems (e.g., Sybil resistance or smart contracts) or mainstream payment networks (e.g., overdrawn accounts or fraud detection), but we believe that it demonstrates how strong privacy features can still be guaranteed by systems with low computational, storage and network requirements. Furthermore, we conjecture that our system's scalability can be further enhanced, and in particular, that it can be made permissionless without sacrificing consensus-freedom, by leveraging techniques such as the ones introduced in [35].
• **C-Hiding.** $\forall c_1, c_2 \in \mathbb{F}, \forall v \in \mathbb{D}, c\_commit(v)/\langle c, \star \rangle : |\Pr(c = c_1) - \Pr(c = c_2)| < \varepsilon(\lambda)$.
Informally, a commitment does not leak any information on its committed value (w.h.p).

## A.2 Universal Accumulators (UA)

An *accumulator* scheme (notion introduced in [4]) produces a short commitment to a set of elements $E$. A *universal accumulator (UA)* is a special kind of accumulator that can prove both the inclusion or non-inclusion of an element in the set by using *membership* or *non-membership proofs*, respectively. RSA accumulators [7] are a notable implementation of this scheme. We assume that the empty accumulator of each process is created during the system's setup phase (see Appendix E).

**UA operations.** We consider an accumulator $A$ and its associated accumulated set $E$.

• $ua\_is\_empty(A)/b$: Takes $A$ and outputs $b = true$ if $E = \emptyset$, and $b = false$ otherwise.

• $ua\_add(A, v)/A'$: Takes $A$ and a value $v$ and outputs the updated accumulator $A'$ containing $v$.

• $ua\_prove\_mem(A, E, v)/r$: Takes $A, E$, and a value $v$ and outputs a membership proof $r = w$ of value $v$ in accumulator $A$ if $v \in E$, and $r = \text{abort}$ otherwise.

• $ua\_prove\_non\_mem(A, E, v)/r$: Takes $A, E$, and a value $v$ and outputs a non-membership proof $r = u$ of value $v$ in $A$ if $v \notin E$, and $r = \text{abort}$ otherwise.

• $ua\_verify\_mem(A, v, w)/r$: Outputs $r = true$ if $w$ is a correct membership proof of value $v$ for $A$, and $r = false$ otherwise.

• $ua\_verify\_non\_mem(A, v, u)/r$: Outputs $r = true$ if $u$ is a correct non-membership proof of value $v$ for $A$, and $r = false$ otherwise.

**UA properties.** We consider an accumulator $A$ and its associated set $E$.

• **UA-Soundness.** $\forall v \notin E, ua\_prove\_mem(A, E, v)/r : \Pr(r \neq \text{abort}) < \varepsilon(\lambda)$ and $\forall v \in E, ua\_prove\_non\_mem(A, E, v)/r : \Pr(r \neq \text{abort}) < \varepsilon(\lambda)$.

Informally, the probability of computing a membership proof for a non-accumulated element or a non-membership proof for an accumulated element is negligible.

• **UA-Completeness.** $\forall v \in E, ua\_verify\_mem(A, v, ua\_prove\_mem(A, E, v))/r : \Pr(r = true) > 1 - \varepsilon(\lambda)$ and $\forall v \notin E, ua\_verify\_non\_mem(A, v, ua\_prove\_non\_mem(A, E, v))/r : \Pr(r = true) > 1 - \varepsilon(\lambda)$.

Informally, all honestly accumulated values are verified as true with their corresponding membership proof with a negligible probability of error.

• **UA-Undeniability.** $\forall v \in \mathbb{D}, \forall w, u \in \mathbb{F}: \Pr(ua\_verify\_mem(A, v, w) \land ua\_verify\_non\_mem(A, v, u)) < \varepsilon(\lambda)$.

Informally, the probability of computing both a membership and non-membership proof for the same element is negligible.

• **UA-Indistinguishability.** No information on some accumulated set $E$ is leaked from its associated accumulator $A$, membership proofs $w$ or non-membership proofs $u$.<fnref n="9" />

For simplicity and compliance with the traditional definitions given in the cryptography literature [7], we do not give properties for the $ua\_add$ operations. We implicitly assume that they behave correctly, that is, we can only prove the membership of an element that has been added and we can only prove the non-membership for an element that has never been added.

<footnote n="9">⁹For a more formal definition of Indistinguishability, we refer the interested reader to [17].</footnote>
References

1 Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. Money transfer made simple: a specification, a generic algorithm, and its proof. *Bulletin of EATCS*, 132:22–43, 2020.

2 Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. Byzantine-tolerant causal broadcast. *Theor. Comput. Sci.*, 885:55–68, 2021.

3 Mathieu Baudet, George Danezis, and Alberto Sonnino. FastPay: High-performance Byzantine fault tolerant settlement. In *Proc. 2nd ACM Conference on Advances in Financial Technologies (AFT'20)*, pages 163–177. ACM, 2020.

4 Mathieu Baudet, Alberto Sonnino, Mahimna Kelkar, and George Danezis. Zef: Low-latency, scalable, private payments. In *Proc. 22nd Workshop on Privacy in the Electronic Society (WPES@CCS'23)*, pages 1–16. ACM, 2023.

5 Josh Cohen Benaloh and Michael de Mare. One-way accumulators: A decentralized alternative to digital signatures (Extended abstract). In *Proc. 12th Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'93)*, volume 765 of Springer LNCS, pages 274–285, 1993.

6 Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct non-interactive arguments via linear interactive proofs. *J. Cryptol.*, 35(3):15, 2022.

7 Dan Boneh, Benedikt Bünz, and Ben Fisch. Batching techniques for accumulators with applications to IOPs and stateless blockchains. In *Proc. 39th Int'l Cryptology Conference*, Springer LNCS 11692, pages 561–586, 2019.

8 Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. *J. Cryptol.*, 17(4):297–319, 2004.

9 Joseph Bonneau, Izaak Meckler, Rao Vanishree, and Evan Shapiro. Mina: Decentralized cryptocurrency at scale (White paper), 2020.

10 Gabriel Bracha. Asynchronous Byzantine agreement protocols. *Inf. Comput.*, 75(2):130–143, 1987.

11 Benedikt Bünz, Shashank Agrawal, Mahdi Zamani, and Dan Boneh. Zether: Towards privacy in a smart contract world. In *Proc. 24th Int'l Conference on Financial Cryptography and Data Security (FC'20)*, volume 12059 of *Lecture Notes in Computer Science*, pages 423–443, 2020.

12 Benedikt Bünz, Lucianna Kiffer, Loi Luu, and Mahdi Zamani. Flyclient: Super-light clients for cryptocurrencies. In *Proc. IEEE Symposium on Security and Privacy*, pages 928–946, 2020.

13 Miranda Christ, Foteini Baldimtsi, Konstantinos Kryptos Chalkias, Deepak Maram, Arnab Roy, and Joy Wang. Sok: Zero-knowledge range proofs. *IACR Cryptol. ePrint Arch.*, page 430, 2024.

14 Daniel Collins, Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei Tonkikh, and Athanasios Xygkis. Online payments by merely broadcasting messages. In *Proc. 50th IEEE/IFIP Int'l Conference on Dependable Systems and Networks (DSN'20)*, pages 26–38. IEEE, 2020.

15 Ivan Damgård and Maciej Koprowski. Generic lower bounds for root extraction and signature schemes in general groups. In Lars R. Knudsen, editor, *Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings*, volume 2332 of *Lecture Notes in Computer Science*, pages 256–271. Springer, 2002.

16 Sourav Das, Zhuolun Xiang, Lefteris Kokoris-Kogias, and Ling Ren. Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling. In *Proc. 32nd USENIX Security Symposium*, pages 5359–5376. USENIX Association, 2023.

17 David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In Kaisa Nyberg, editor, *Topics in Cryptology - CT-RSA 2015, The Cryptographer's Track at the RSA Conference 2015, San Francisco, CA, USA, April 20-24, 2015. Proceedings*, volume 9048 of *Lecture Notes in Computer Science*, pages 127–144. Springer, 2015.
### A.3 Zero-Knowledge Proofs (ZKP)

We refer to the last scheme used in this article as zero-knowledge proofs (ZKP), which correspond to proofs that a prover knows some secret data without divulging any other information on it to the verifier. Specifically, we use zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) [42]. The difference between proof and argument systems comes from the strength of the soundness property. A proof system must be perfectly sound (i.e., withstand a computationally unbounded adversary) whereas an argument system guarantees computational soundness (i.e., against a PPT adversary with a very high probability). The use of arguments is necessary as it was proven by Fortnow [20] that no perfect soundness zero-knowledge proof systems exist for NP-complete problems, while there exist perfect zero-knowledge arguments systems for NP-complete problems (e.g., zk-SNARKs).

**ZKP predicate.** Each object of a ZKP scheme is set up with a specific predicate $P_{ZK}$, called a ZKP predicate, taking as parameters a public_data (known both by the prover and verifier) and a secret_data (known only by the prover), and returning true or false. The prover $p_i$ passes to the zkp_prove operation the public_data and secret_data parameters of $P_{ZK}$, and the proof $\pi_i$ is correctly generated only if $P_{ZK}(\text{public\_data}, \text{secret\_data}) = \text{true}$. Much like the $P_A$ predicate (Section 6.1), the $P_{ZK}$ predicate is typically passed to the implicit setup operation of the ZKP scheme.

**ZKP operations.** We consider a ZKP object $Obj_{ZK}$ set up with a ZKP predicate $P_{ZK}$.

* $Obj_{ZK}$.zkp_prove(\text{public\_data}, \text{secret\_data})/r$: Returns a result $r$, which can be either a zero-knowledge proof $r = \pi$ if the input parameters secret_data and public_data satisfy $P_{ZK}$, or $r = \text{abort}$ otherwise.

* $Obj_{ZK}$.zkp_verify(\pi, \text{public\_data})/r$: Returns the validity $r \in \{\text{true, false}\}$ of a zero-knowledge proof $\pi$ with respect to the public data public_data and the ZKP predicate.

**ZKP properties.** We consider a ZKP object $Obj_{ZK}$ set up with a ZKP predicate $P_{ZK}$.

* **ZKP-Knowledge-Soundness.** If $Obj_{ZK}$.zkp_verify($\pi$, public_data) is true, then the prover knows some secret_data such that $Obj_{ZK}$.zkp_prove(public_data, secret_data)/$\pi$ and $P_{ZK}(public\_data, secret\_data)$ is true w.h.p.

* **ZKP-Completeness.** For any pair $(\text{public\_data}, \text{secret\_data})$ such that $P_{ZK}(\text{public\_data}, \text{secret\_data})$ is true, we must have $Obj_{ZK}$.zkp_verify(Obj_{ZK}.zkp_prove(public\_data, secret\_data), public\_data) is true w.h.p.

* **ZKP-Zero-Knowledge.** No information on some secret_data is leaked by its associated public_data and zero-knowledge proof $\pi$.<fnref n="10" />

## B Proofs of our QAAT System (Algorithms 1 to 3)

In this appendix section, we provide full derivations on the proof of correctness (Appendix B.1) and quasi-anonymity (Appendix B.2) of our QAAT system (Algorithms 1–3). Throughout the section, we rely on the full property definitions of the commitment, UA, and ZKP schemes given in Appendix A.

<footnote n="10">¹⁰For a more formal definition of Zero-Knowledge, we refer the interested reader to [25].</footnote>
18 Samuel Dobson, Steven D. Galbraith, and Benjamin Smith. Trustless unknown-order groups. *CoRR*, abs/2211.16128, 2022.

19 Prastudy Fauzi, Sarah Meiklejohn, Rebekah Mercer, and Claudio Orlandi. Quisquis: A new design for anonymous cryptocurrencies. In *Proc. 25th Int'l Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'19)*, volume 11921 of LNCS, pages 649-678. Springer, 2019.

20 Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In *Proc. Advances in Cryptology (CRYPTO'86)*, volume 263 of LNCS, pages 186-194. Springer, 1986.

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

22 Davide Frey, Mathieu Gestin, and Michel Raynal. The synchronization power (consensus number) of access-control objects: the case of allowlist and denylist. In *Proc. 37th Int'l Symposium on Distributed Computing (DISC'2023)*, volume 281 of LIPIcs, pages 21:1-21:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.

23 Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. *IACR Cryptol. ePrint Arch.*, page 953, 2019.

24 Carl Friedrich Gauss. *Disquisitiones arithmeticae*. K. Gesellschaft der Wissenschaften zu Göttingen, 1801.

25 Oded Goldreich. *The Foundations of Cryptography - Volume 1: Basic Techniques*. Cambridge University Press, 2001.

26 Jens Groth. Short pairing-based non-interactive zero-knowledge arguments. In *Proc. 16th International Conference on the Theory and Application of Cryptology and Information Security*, volume 6477 of Springer LNCS, pages 321-340, 2010.

27 Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. *Distributed Comput.*, 35(1):1-15, 2022.

28 Saurabh Gupta. A non-consensus based decentralized financial transaction processing model with support for efficient auditing (Master thesis). Arizona State University, 2016.

29 Daira Emma Hopwood, Sean Bowe, and Taylor Hornby Nathan Wilcox. Zcash protocol specification, 2016.

30 Damien Imbs and Michel Raynal. Trading off t-resilience for efficiency in asynchronous Byzantine reliable broadcast. *Parallel Process. Lett.*, 26(4):1650017:1-1650017:8, 2016.

31 Anurag Jain, Emmanuelle Anceaume, and Sujit Gujar. Extending the boundaries and exploring the limits of blockchain compression. In *Proc. 42nd Int'l Symposium on Reliable Distributed Systems (SRDS'23)*, pages 187-197. IEEE, 2023.

32 Aggelos Kiayias, Nikos Leonardos, and Dionysis Zindros. Mining in logarithmic space. In *Proc. ACM SIGSAC Conference on Computer and Communications Security (CCS'21)*, pages 3487-3501. ACM, 2021.

33 Chelsea Komlo and Ian Goldberg. FROST: flexible round-optimized schnorr threshold signatures. In *Proc. 27th Int'l Conference on Selected Areas in Cryptography (SAC'20)*, volume 12804 of Lecture Notes in Computer Science, pages 34-65. Springer, 2020.

34 Abhiram Kothapalli, Srinath T. V. Setty, and Ioanna Tzialla. Nova: Recursive zero-knowledge arguments from folding schemes. In *42nd Annual International Cryptology Conference (CRYPTO'22)*, volume 13510 of LNCS, pages 359-388. Springer, 2022.

35 Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, and Andrei Tonkikh. Permissionless and asynchronous asset transfer. *Distributed Computing*, 36(3):349-371, 2023.

36 Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The Byzantine generals problem. *ACM Trans. Program. Lang. Syst.*, 4(3):382-401, 1982.

37 Karl Marx. *Das Kapital. Kritik der politischen Ökonomie. Buch I: Der Produktionsprocess des Kapitals*. Otto Meissner, 1867.
# B.1 Proof of correctness

## B.1.1 Preliminaries

We first introduced a number of preliminary results and definitions that we will use to prove the AT-Sequentiality of Algorithm 3 in Appendix B.1.2. In the following, $\sigma_i^{sn}$ denotes an AP (Agreement Proof) that is valid at a sequence number $sn$ for a process $p_i$ (correct or faulty).

**Definition B.1** (Valid UA at a sequence number $sn$ for a process $p_i$). We say that a Universal Accumulator (UA) A is valid at a sequence number $sn$ for a process $p_i$ (correct of faulty) if there exists a valid Agreement Proof (AP) $\sigma_i^{sn}$ that is valid at $sn$ for $p_i$ and verifies AccountUpdate.ap_verify($\sigma_i^{sn}$, $\langle A, \star \rangle$, $sn, i$). As a shortcut, we might interchangeably say that A was issued by $p_i$ at sequence number $sn$. When this holds, we note A's sequence number and AP issuer as superscript and subscript, respectively, i.e., $A = A_i^{sn}$.

**Lemma B.2** (Unicity of valid UAs at a sequence number $sn$ for a process $p_i$). There is at most one UA that is valid at a sequence number $sn \ge 0$ for a process $p_i$ (correct of faulty), i.e., if A and $A'$ are both valid UAs at $sn$ for $p_i$ according to Definition B.1, then $A = A'$.

*Proof.* This trivially follows from Definition B.1 and the AP-Agreement property of Agreement Proofs. $\square$

**Lemma B.3** (Sequence of preceding UAs of a valid UA). Consider a valid UA $A_i^{sn}$ at sequence number $sn \ge 0$ issued by a process $p_i$ (correct or faulty). The following holds.

* $A_i^{sn}$ can be associated with a unique sequence of preceding UAs, denoted precedingUAs($A_i^{sn}$) = ($A_i^0, A_i^1, \dots, A_i^{sn}$), so that each $A_i^k$ is a valid UA issued by $p_i$ at sequence number $k$, with $0 \le k \le sn$.

* The sequences of UAs produced for UAs issued by the same process $p_i$ are prefix-ordered, i.e., if $A_i^{sn_1}$ and $A_i^{sn_2}$ are two valid UAs issued by $p_i$ at sequence numbers $sn_1$ and $sn_2$ respectively such that $sn_1 \le sn_2$, then precedingUAs($A_i^{sn_1}$) is a prefix of precedingUAs($A_i^{sn_2}$).

*Proof.* Let us consider a valid UA $A_i^{sn}$ at sequence number $sn \ge 0$ issued by a process $p_i$ (correct or faulty).

* If $sn = 0$, we pick precedingUAs($A_i^0$) = ($A_i^0$).

* If $sn > 0$, by Definition B.1, $A_i^{sn}$ is associated with some AP $\sigma_i^{sn}$ issued by $p_i$ that is valid at sequence number $sn$. By AP-Knowledge-Soundness, $p_i$ knows some data = $\langle \sigma'_i, \star, \star \rangle$ s.t. $P_A(\star, \langle \sigma'_i, \star, \star \rangle, sn)$ is true. Line 8 of the code of Predicate $P_A$ (Algorithm 2) implies that $\sigma'_i$ is a valid AP at sequence number $sn - 1$ from $p_i$ for some payload $\langle A_{pvr}, \star \rangle$. $A_{pvr}$ fulfills Definition B.1, and is therefore a valid UA at sequence number $sn - 1$ from $p_i$. By induction, we obtain that, for each $sn'$ s.t. $0 \le sn' \le sn$ there is a valid UA $A_i^{sn'}$ at $sn'$ from $p_i$. We denote this sequence as precedingUAs($A_i^{sn'}$) = ($A_i^0, A_i^1, \dots, A_i^{sn'}$).

By Lemma B.2, precedingUAs($A_i^{sn}$) is unique. We say that the sequence of valid UAs ($A_i^{sn'}$)$_{0 \le sn' \le sn}$ is the sequence of preceding UAs of $A_i^{sn}$. Prefix ordering similarly follows from Lemma B.2. $\square$

**Definition B.4** (Valid transfer $\tau$ at a sequence number $sn$ for a process $p_i$). We say that a transfer $\tau = \langle \text{snd}, v, \text{rcv}, \text{sn}_{\text{snd}} \rangle$ is valid at a sequence number $sn > 0$ for a process $p_i$ (correct of faulty) if there exist a non-membership proof $u$ and two valid UAs $A_i^{sn}$ and $A_i^{sn-1}$ issued by $p_i$ at sequence numbers $sn$ and $sn - 1$ respectively, such that:

$$ua_verify_non_mem(A_i^{sn-1}, \tau, u) \land ua_add(A_i^{sn-1}, \tau) = A_i^{sn}. \quad (1)$$
38 Ralph C. Merkle. A digital signature based on a conventional encryption function. In Proc. 7th Int'l Cryptology Conference (CRYPTO'87), volume 293 of Lecture Notes in Computer Science, pages 369-378. Springer, 1987.

39 Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.

40 Anca Nitulescu. zk-snarks: a gentle introduction, 2020.

41 Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980.

42 Torben P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Proc. 11th Annual Int'l Cryptology Conference (CRYPTO'91), volume 576 of Lecture Notes in Computer Science, pages 129-140. Springer, 1991.

43 Michael G. Reed, Paul F. Syverson, and David M. Goldschlag. Anonymous connections and onion routing. IEEE J. Sel. Areas Commun., 16(4):482-494, 1998.

44 Tim Ruffing, Viktoria Ronge, Elliott Jin, Jonas Schneider-Bensch, and Dominique Schröder. ROAST: robust asynchronous Schnorr threshold signatures. In Proc. ACM SIGSAC Conference on Computer and Communications Security (CCS'22), pages 2551-2564. ACM, 2022.

45 Srinath T. V. Setty. Spartan: Efficient and general-purpose zksnarks without trusted setup. In Proc. 40th Annual International Cryptology Conference (CRYPTO'20), volume 12172 of Lecture Notes in Computer Science, pages 704-737. Springer, 2020.

46 Douglas R. Stinson and Reto Strobl. Provably secure distributed schnorr signatures and a (t, n) threshold scheme for implicit certificates. In Vijay Varadharajan and Yi Mu, editors, Proc. 6th Australasian Conference on Information Security and Privacy (ACISP'01), volume 2119 of Lecture Notes in Computer Science, pages 417-434. Springer, 2001.

47 Harry W. H. Wong, Jack P. K. Ma, Hoover H. F. Yin, and Sherman S. M. Chow. How (not) to build threshold EdDSA. In Proc. 26th Int'l Symposium on Research in Attacks, Intrusions and Defenses (RAID'23), pages 123-134. ACM, 2023.

**A Proofs of Algorithm 3**

In this appendix section, we provide full derivations on the proof of correctness (Appendix A.1) and quasi-anonymity (Appendix A.2) of Algorithm 3. We also provide informal arguments for the lightness and consensus-freedom of Algorithm 3 (Appendix A.3).

A.1 Proof of correctness

We start by defining notations used in the AT-Sequentiality proof, and then define a method $M$ for constructing a sequence of invocations $S$ from an execution of Algorithm 3.

**AP notation.** If some $\sigma$ is a valid AP at a sequence number $sn$ from a process $p_i$, we denote it by $\sigma_i^{sn}$.

**Sequence of previous APs of an AP.** Let us consider a valid AP $\sigma_i^{sn}$ at sequence number $sn > 0$ from a process $p_i$ (correct or faulty). By AP-Knowledge-Soundness, $p_i$ knows some $data = \langle \sigma'_i, \star, \star, sn-1, \star \rangle$ s.t. $P_A(data)$ is true, where $\sigma'_i$ is an AP at sequence number $sn-1$ from $p_i$. From line 8 of $P_A$, $\sigma'_i$ is also a valid AP at sequence number $sn-1$ from $p_i$. By induction and using AP-Agreement, we obtain that, for each $sn'$ s.t. $0 \le sn' \le sn$ there is a single valid AP $\sigma_i^{sn'}$ at $sn'$ from $p_i$. We say that the sequence of all $\sigma_i^{sn'}$ valid APs where $0 \le sn' \le sn$ is the sequence of previous APs of $\sigma_i^{sn}$, denoted previous\_APs$^{sn}$.

**Transfer invocation corresponding to an AP.** By AP-Knowledge-Soundness, for every valid AP $\sigma_i^{sn}$ at a sequence number $sn$ from a process $p_i$ (correct or faulty) where $sn > 0$ (the sequence number $sn = 0$ is excluded as the initial AP $\sigma_i^0$ does not have a corresponding transfer invocation), the prover $p_i$ must know some $data = \langle \star, \pi_i, \star, sn-1, public\_data \rangle$ satisfying $P_A(data)$. Moreover, given that TransferValidity.zkp_verify($\pi_i, public\_data$) must be true
When this holds, we note $\tau$'s sequence number and UA issuer<sup>11</sup> as superscript and subscript, respectively, i.e., $\tau = \tau_i^{sn}$.

When the context is clear, for simplicity, we might abbreviate Equation (1) using a set notation into
$$A_i^{sn} = A_i^{sn-1} \cup \{\tau\}, \text{ where } \cup \text{ denotes the disjoint set union.}$$

**Lemma B.5 (Transfer associated with a valid UA).** *Consider a valid UA $A_i^{sn}$ at sequence number $sn > 0$ issued by a process $p_i$ (correct or faulty)<fnref n="12" />. The existence of $A_i^{sn}$ implies that there exists a valid transfer $\tau_i^{sn}$ issued by $p_i$ at sequence number $sn$ (Definition B.4). Furthermore this transfer is unique for a given $p_i$ and $sn$. We say that $A_i^{sn}$ is associated with $\tau_i^{sn}$.*

*Proof.* Consider a valid UA $A_i^{sn}$ at sequence number $sn > 0$ issued by a process $p_i$ (correct or faulty). By Definition B.1, there exists a valid AP $\sigma_i^{sn}$ at sequence number $sn$ for $p_i$ so that `AccountUpdate.ap_verify(\sigma_i^{sn}, \langle A_i^{sn}, \star \rangle, sn, i)`. By AP-Knowledge-Soundness, and by definition of the $P_A$ predicate for `AccountUpdate` objects (Algorithm 2), the prover $p_i$ must know some data = $\langle \star, \pi_i, \text{old\_state\_data} \rangle$ satisfying $P_A(\langle A_i^{sn}, \star \rangle, \text{data}, sn)$. Due to line 6 of the code of Predicate $P_A$ (Algorithm 2), this implies that `TransferValidity.zkp_verify(\pi_i, \text{old\_state\_data} \oplus \langle A_i^{sn}, \star, sn \rangle)$ is true, where $\text{old\_state\_data} = \langle A_i^{sn-1}, \star \rangle$. As a result, by ZKP-Knowledge-Soundness and by construction of the $P_{ZK}$ predicate of the ZKP object `TransferValidity` (Algorithm 2), the prover $p_i$ must know some secret_data containing a transfer $\tau = \langle \text{snd}, v, \text{rcv}, sn' \rangle$ variable (fifth parameter at line 11 of Algorithm 2) such that $P_{ZK}(\langle A_i^{sn-1}, \star \rangle \oplus \langle A_i^{sn}, \star, sn \rangle, \text{secret\_data})$ is true (if $i = \text{snd}$, then $sn = sn'$ due to the check at line 17 of Algorithm 2, otherwise if $i = \text{rcv}$, $sn$ and $sn'$ can be different). Furthermore, due to line 8, and by Lemma B.2, $A_i^{sn-1}$ is the valid UA at sequence number $sn-1$ for process $p_i$. This observation, together with line 13 of Algorithm 2 implies that $\tau$ is a valid transfer issued by $p_i$ at sequence number $sn$. Because $A_i^{sn}$ and $A_i^{sn-1}$ are unique for $p_i$ at their respective sequence number, line 13 further yields that $\tau$ is the sole transfer that is valid for $p_i$ and $sn$. $\square$

**Corollary B.6 (Sequence of preceding transfers of a valid UA).** *Consider a valid UA $A_i^{sn}$ at sequence number $sn \ge 0$ issued by a process $p_i$ (correct or faulty). $A_i^{sn}$ can be associated with a unique sequence of preceding transfers, denoted $\text{precedingTrans}(A_i^{sn}) = (\tau_i^1, \dots, \tau_i^{sn})$, so that each $\tau_i^k$ is a valid transfer issued by $p_i$ at sequence number $k$, with $1 \le k \le sn$.*

*Proof.* The corollary follows from Lemmas B.3 and B.5. $\square$

**Lemma B.7 (Prefix-ordering of of preceding transfers).** *The sequences of transfers produced for UAs issued by the same process $p_i$ are prefix-ordered, i.e., if $A_i^{sn_1}$ and $A_i^{sn_2}$ are two valid UAs issued by $p_i$ at sequence numbers $sn_1$ and $sn_2$ respectively such that $sn_1 \le sn_2$, then $\text{precedingTrans}(A_i^{sn_1})$ is a prefix of $\text{precedingTrans}(A_i^{sn_2})$.*

*Proof.* This follows from the unicity of a valid transfer for a given process and sequence number, as stated in Lemma B.5. $\square$

For simplicity, in the following, we equate valid transfers with their corresponding transfer invocation. More precisely, if $\tau_i^{sn}$ is a valid transfer at sequence number $sn$ for a process $p_i$, we denote the transfer invocation corresponding to a $\tau_i^{sn}$ by $\text{transfer}_{\text{snd}}^{sn'}(v, \text{rcv})$, where $\text{snd}$ and $\text{sn'}$ are respectively the id of the sender and the sequence number of the transfer contained in $\tau$. In this case, we say that $\text{transfer}_{\text{snd}}^{sn'}(v, \text{rcv})$ is the transfer invocation for prover $p_i$ at sequence number $sn$.

**Definition B.8 (Sending UAs, receiving UAs, and null UAs).** *We distinguish two sorts of valid UAs that are produced in our system: sending UAs, and receiving UAs.*

<footnote n="11">¹¹We note that the UA issuer of transfer $\tau$ is not always the sender of $\tau$.</footnote>

<footnote n="12">¹²The sequence number $sn = 0$ is excluded as the genesis AP $\sigma_i^0$ does not have a corresponding transfer.</footnote>
(line 5), then by ZKP-Knowledge-Soundness, the prover $p_i$ must know some secret_data containing a $\tau = \langle \mathit{snd}, v, \mathit{rcv}, \mathit{sn}' \rangle$ variable such that $P_{\mathit{ZK}}(\mathit{public\_data}, \mathit{secret\_data})$ is true (if $i = \mathit{snd}$, then $\mathit{sn} = \mathit{sn}'$, otherwise $i = \mathit{rcv}$ and $\mathit{sn}$ and $\mathit{sn}'$ can be different). We denote the transfer invocation corresponding to $\tau$ by $\mathit{transfer}_{\mathit{snd}}^{\mathit{sn}'}(v, \mathit{rcv})$. In this case, we say that $\mathit{transfer}_{\mathit{snd}}^{\mathit{sn}'}(v, \mathit{rcv})$ is the transfer invocation corresponding to the AP $\sigma_i^{\mathit{sn}}$.

**Sending APs, receiving APs, and null APs.** We distinguish two sorts of valid APs that are produced in our system: *sending APs*, and *receiving APs*.

- Some valid $\sigma_i^{\mathit{sn}}$ is a sending AP if it corresponds to a $\mathit{transfer}_i^{\mathit{sn}}(\star, j)$ invocation (where $i$ and $j$ can be different). If the prover $p_i$ is correct, the sending AP is produced during the $\mathit{process\_transfer()}$ call at line 26.

- Some valid $\sigma_i^{\mathit{sn}}$ is a sending AP if it corresponds to a $\mathit{transfer}_j^{\mathit{sn}'}(\star, i)$ invocation (where $i$ and $j$ can be different, and $\mathit{sn}$ and $\mathit{sn}'$ can be different). If the prover $p_i$ is correct, the receiving AP is produced during the $\mathit{process\_transfer()}$ call at line 32.

Remind that a transfer invocation $\mathit{transfer}_i^{\mathit{sn}}(v, i)$ from a process $p_i$ to itself is allowed in our algorithm, which entails that the corresponding AP $\sigma_i^{\mathit{sn}}$ is both a sending AP and a receiving AP. In this case, $\sigma_i^{\mathit{sn}}$ is said to be a *null AP*, and $\mathit{transfer}_i^{\mathit{sn}}(v, i)$ is said to be a *null transfer invocation*.

**Matching non-null sending AP of a non-null receiving AP.** Notice that, due to the verification of the sending AP in the $P_{\mathit{ZK}}$ predicate at line 20 when the prover is the receiver, any non-null receiving AP $\sigma_i^{\mathit{sn}}$ must have a *matching sending AP* $\sigma_j^{\mathit{sn}'}$.<fnref n="12" />

**Transfer or balance invocation notations.** If a correct process $p_i$ performs a *balance*<sub>*i*</sub>() invocation while its $\mathit{sn}_i$ variable has value $\mathit{sn}$, we denote it by $\mathit{balance}_i^{\mathit{sn}}()$.<fnref n="13" /> For simplicity, we denote by $\mathit{op}_i^{\mathit{sn}}()$ any invocation $\mathit{balance}_i^{\mathit{sn}}()$ or $\mathit{transfer}_i^{\mathit{sn}}(\star, \star)$.

**Method *M* for constructing an invocation sequence *S*.** We describe in the following a method, that we call *M*, for constructing a sequence *S* of all the operation invocations produced by an execution of Algorithm 3, captured as a global history $H = (L_1, ..., L_n)$. First, we incrementally construct a partially-ordered set (poset) $P = (I, \to_P)$, where $I$ is the set of all operation invocations of the execution and $\to_P$ is a partial order on $I$ defining the precedence of invocations. Initially, for every correct process $p_i$, $I$ includes all the $\mathit{transfer}_i(v, j)$ and $\mathit{balance}_i()$ operation invocations in $L_i$, and the $\to_P$ order extends the $\to_i$ process order. We also define a set called $\mathit{receiving\_APs\_to\_process}$, which contains non-null receiving APs that must be processed to construct *P*. Non-null receiving APs are particularly important, as they allow us to infer $\to_P$ relations between the $\mathit{transfer()}$ invocations of different processes. The $\mathit{receiving\_APs\_to\_process}$ set is initialized with all non-null receiving APs produced during the execution by correct processes at line 44, in a $\mathit{process\_transfer()}$ call at line 32. We now describe the steps to construct *P* iteratively.

1. We initialize a new variable $\mathit{new\_receiving\_APs}$ to the empty set $\emptyset$. This set will contain the new non-null receiving APs discovered during the current iteration, and it will replace the current $\mathit{receiving\_APs\_to\_process}$ at the end of the iteration. (Some non-null receiving APs can be “rediscovered” several times during the procedure, which does not pose a problem for the construction.)

<footnote n="12">¹²The reverse is not always true: if the receiver of a transfer is faulty, it may never produce a receiving AP for the corresponding sending AP.</footnote>

<footnote n="13">¹³Recall that we do not consider $\mathit{balance()}$ invocations from Byzantine processes.</footnote>
* A valid $A_i^{sn}$ is a sending UA if the issuer $p_i$ of $A_i^{sn}$ is also the sender of the corresponding transfer $transfer_i^{sn}(*, j)$ (where i and j can be different). If the issuer $p_i$ is correct, the sending UA has been produced at line 38 of Algorithm 3, during the process_transfer() call at line 27.

* A valid $A_i^{sn}$ is a receiving UA if the issuer $p_i$ of $A_i^{sn}$ is also the receiver of the corresponding transfer $transfer_j^{sn'}(*, i)$ (where i and j can be different, and $sn$ and $sn'$ can be different). If the issuer $p_i$ is correct, the receiving UA is produced at line 38 of Algorithm 3, during the process_transfer() call at line 33.

Recall that a transfer invocation $transfer_i^{sn}(v, i)$ from a process $p_i$ to itself is allowed in our algorithm, which entails that the corresponding UA $A_i^{sn}$ is both a sending UA and a receiving UA. In this case, $A_i^{sn}$ is said to be a null UA, and $transfer_i^{sn}(v, i)$ is said to be a null transfer invocation.

**Lemma B.9 (Matching receiving UA to a sending UA).** Any valid receiving UA $A_i^{sn}$ for some transfer $\tau_i = \langle j, *, i, sn_{\tau_i} \rangle$ from a receiver $p_i$ (correct or faulty) can be matched to a valid sending UA $A_j^{sn_{\tau_i}}$ for the same transfer $\tau_i$ from the sender $p_j \neq p_i$ (correct or faulty).

*Proof.* Consider a valid receiving UA $A_i^{sn}$ (Definition B.8) at sequence number $sn$ for process $p_i$ corresponding to some receiving transfer $\tau_i = \langle j, *, i, sn_{\tau_i} \rangle$ whose sender is $p_j$ and receiver is $p_i$. Two cases arise depending on whether $A_i^{sn}$ is a null or non-null UA (cf. Definition B.8).

* If $A_i^{sn}$ is a null UA, it is both a sending UA and a receiving UA, and corresponds to a transfer $\tau_i = \langle i, *, i, sn \rangle$ from $p_i$ to itself, thus fulfilling the lemma.

* If $A_i^{sn}$ is a non-null receiving UA, this $A_i^{sn}$ is associated to a valid AP $\sigma_i^{sn}$ (Definition B.1). Lines 20 and 21 of $P_{ZK}$ (Algorithm 2) imply the existence of a valid UA $A_j^{sn_{\tau_i}}$ for $p_j$ at sequence number $sn_{\tau_i}$, with $j \neq i$ (since $A_i^{sn}$ is non-null), and $\tau_i \in A_j^{sn_{\tau_i}}$.

Consider the sequence preceding UAs $(A_j^{sn_{\tau_i}}) = (A_j^k)_{0 \le k \le sn_{\tau_i}}$ of UAs preceding $A_j^{sn_{\tau_i}}$ (Lemma B.3), and the sequence preceding Trans $(A_j^{sn_{\tau_i}}) = (\tau_j^k)_{0 < k \le sn_{\tau_i}}$ of transfers preceding $A_j^{sn_{\tau_i}}$ (Corollary B.6). By construction of the two sequences, each transfer $\tau_j^k$ is valid for $p_j$ at sequence number $k$, which implies

$$ \forall k \in [1..sn_{\tau_i}] : A_j^k = A_j^{k-1} \cup \{\tau_j^k\}. \qquad (2) $$

Line 7 of $P_A$ (Algorithm 2) implies that $A_j^0$ is empty. This observation and the above equation yield that $A_j^{sn_{\tau_i}}$ contains exactly the transfers present in the sequence preceding Trans $(A_j^{sn_{\tau_i}})$.

Since $\tau_i \in A_j^{sn_{\tau_i}}$, there exists some $k_0 \in [1..sn_{\tau_i}]$ such that $\tau_i = \tau_j^{k_0}$. As the sender of $\tau_i$ is $p_j$, line 17 of $P_{ZK}$ (Algorithm 2) implies that $k_0 = sn_{\tau_i}$, and that $\tau_i = \tau_j^{sn_{\tau_i}}$ by the unicity of a valid transfer for a given process and sequence number, as stated in Lemma B.5. $\square$

**Notations.** For the remaining proofs, we introduce the following notations to manipulate the different notions we have discussed. All notations are defined with respect to a particular global history $H$.

* $transfer(A_i^{sn}) \stackrel{def}{=} transfer_{snd}^{sn'}(v, rcv)$ is the transfer invocation corresponding to a valid UA $A_i^{sn}$ when $sn > 0$ (see Lemma B.5). $A_i^{sn}$ might be a sending UA (in which case $i = snd$ and $sn = sn'$) or a receiving UA (in which case $i = rcv$).

* $sendingUA(transfer_i^{sn}(v, j)) \stackrel{def}{=} A_i^{sn}$ is the sending UA issued by $p_i$ corresponding to a valid transfer invocation $transfer_i^{sn}(v, j)$ performed by $p_i$ towards $p_j$. By definition of a valid transfer and Lemma B.9, this sending UA always exists, and by AP-Agreement, it is unique. As a shortcut, we further say that $sn$ (the sequence number of the UA $A_i^{sn}$) is the sequence number of the transfer invocation $transfer_i^{sn}(v, j)$.
2. For every non-null receiving AP $\sigma_{rcv}^{sn_{rcv}} \in \text{receiving\_APs\_to\_process}$, we get the matching non-null sending AP $\sigma_{snd}^{sn_{snd}}$ and its associated sequence of previous APs $\text{previous\_APs}_{snd}^{sn_{snd}}$, and execute the following sub-steps.

a. For every sending AP $\sigma_{snd}^{sn_{snd}} \in \text{previous\_APs}_{snd}^{sn_{snd}}$, we add its corresponding $\text{transfer}_{snd}^{sn_{snd}}(\star, \star)$ invocation in $I$ if it was not already contained (typically because $p_{snd}$ is correct).

b. For every pair of invocations $o'_{snd} = \text{transfer}_{snd}^{sn'_{snd}}(\star, \star)$, $o''_{snd} = \text{transfer}_{snd}^{sn''_{snd}}(\star, \star) \in I$ s.t. $sn'_{snd} < sn''_{snd}$, we have $o'_{snd} \to_P o''_{snd}$ (process order of $p_{snd}$).

c. For every pair of invocations $o'_{rcv} = \text{op}_{snd}^{sn'_{snd}}()$, $o'_{snd} = \text{op}_{rcv}^{sn'_{rcv}}() \in I$ s.t. $sn'_{snd} \le sn_{snd}$ and $sn_{rcv} \le sn'_{rcv}$, we have $o'_{snd} \to_P o'_{rcv}$ (the sending precedes the reception).

d. We add all receiving APs of $\text{previous\_APs}_{snd}^{sn}$ to $\text{new\_receiving\_APs}$.

3. We assign $\text{new\_receiving\_APs}$ to $\text{receiving\_APs\_to\_process}$.

4. Repeat from step 1 until $\text{receiving\_APs\_to\_process}$ is empty.

Once we have finished performing the above steps, we perform the transitive closure on the $\to_P$ relation to make sure that we end up with a well-formed partial order. Finally, we obtain a sequence $S$ containing all the invocations of $I$ by collapsing the $\to_P$ partial order into any possible total order $\to_S$.

**Lemma 1 (AT-Sequentiality).** Any global history $H$ from an execution of Algorithm 3 can be AT-sequenced.

**Proof.** Let us consider any execution of Algorithm 3, captured as a global history $H = (L_1, ..., L_n)$. We subsequently show that any sequence of invocation $S$ created from $H$ using method $M$ is an AT-sequence. Let us consider one of such sequences that we call $S$, with $\to_S$ its associated total order. We have the following for every operation invocation $o = \text{op}_i^{sn}() \in S$ by process $p_i$ at sequence number $sn$.

- Case where $o$ is a $\text{balance}_i^{sn}/v$ invocation. In this case, $p_i$ is necessarily correct, and we have to prove that $v = \text{total}(i, \{o' \in S \mid o' \to_S o\})$.

By construction of $S$ using method $M$, the following holds. For all the $\text{transfer}_i^{sn'}(v', j)$ sent by $p_i$ before $o$ in $S$ where $i \neq j$, $p_i$ has subtracted $v'$ to its balance $\text{bal}_i$ at line 37 during the $\text{process\_transfer}()$ call at line 26. Likewise, for all the $\text{transfer}_j^{sn'}(v', i)$ received by $p_i$ before $o$ in $S$ where $i \neq j$, $p_i$ has added $v'$ to its balance $\text{bal}_j$ at line 37 during the $\text{process\_transfer}()$ call at line 32. Therefore, the value $v$ returned by $\text{balance}_i^{sn}/v$ is computed exactly like $\text{total}(i, \{o' \in S \mid o' \to_S o\})$.

- Case where $o$ is a $\text{transfer}_i^{sn}(v, j)$ invocation (remind that, implicitly, we only consider $\text{transfer}/r$ invocations that return $r = \text{commit}$). In this case, we have to prove that $v \le \text{total}(i, \{o' \in S \mid o' \to_S o\})$.

If the sender $p_i$ is correct, then the proof follows the same reasoning as the previous case, and from the fact that $p_i$ checks that it has enough funds for the transfer at line 24.

If the sender $p_i$ is Byzantine, the proof relies on the $P_{ZK}$ predicate. For each of the valid APs $\sigma_i^{sn'}$ at $sn'$ from $p_i$ (where $0 < sn' \le sn$) that are used to construct $S$ using method $M$, $p_i$ must provide in the $\text{secret\_data}$ of the associated ZKP $\pi_i^{sn'}$ its old and new balances, respectively denoted $\text{bal}_{pvr}$ and $\text{bal}'_{pvr}$ at line 11. Be $\sigma_i^{sn'}$ a null AP, a non-null sending AP, or a non-null receiving AP, the transition from the old to the new balance of $p_i$ is verified in zero-knowledge at line 18, 19, or 20, respectively.

By construction of $S$ using method $M$, we have the following for each of the valid APs $\sigma_i^{sn'}$ at $sn'$ from $p_i$ where $0 < sn' < sn$. If $\sigma_i^{sn'}$ is a sending AP corresponding to a $\text{transfer}_i^{sn'}(v', j)$ invocation, then $\text{transfer}_i^{sn'}(v', j)$ must appear before $o$ in the $\to_P$ order.
• sendingUA($A_i^{sn}$) $\stackrel{\text{def}}{=} A_j^{sn'}$ is by extension the sending UA issued by $p_j$ corresponding to a valid receiving UA $A_i^{sn}$ issued by $p_i$. sendingUA($A_i^{sn}$) is a shortcut for sendingUA(transfer($A_i^{sn}$)). In case $A_i^{sn}$ is a null UA (Definition B.8), we have sendingUA($A_i^{sn}$) = $A_i^{sn}$.

• receivingUA(transfer_i^sn(v, j)) $\stackrel{\text{def}}{=} A_j^{sn'}$ is, when it exists, the receiving UA issued by $p_j$ corresponding to a valid transfer invocation transfer_i^sn(v, j) performed by $p_i$ towards $p_j$. When both the sender $p_i$ and the receiver $p_j$ are correct, this receiving UA always exists because of the network's reliability, and because the internal operation process_transfer(..) of Algorithm 3 (lines 34–45) does not contain any blocking operation.

When transfer_i^sn(v, j) has no corresponding receiving UA (this can happen when either the sender $p_i$ or the receiver $p_j$ are Byzantine), by convention we define receivingUA(transfer_i^sn(v, j)) $\stackrel{\text{def}}{=} \perp$.

• If a correct process $p_i$ performs a balance_i() invocation while its $sn_i$ variable has value $sn$, we denote it by balance_i^sn().13

For simplicity, we denote by $op_i^{sn}()$ any invocation balance_i^sn() or transfer_i^sn(★,★).

## B.1.2 AT-Sequentiality of Algorithm 3

Let us consider any execution of Algorithm 3, captured as a global history $H = (L_1, ..., L_n)$. To prove AT-Sequentiality (Lemma 6.1), we must construct a mock history $\hat{H}$ of $H$ that preserves the local histories of correct processes and replaces the local histories $L_j$ of Byzantine processes $p_j$ by mock local histories $\hat{L}_j$ so that $\hat{H}$ can be AT-sequenced. We construct $\hat{H}$ and the corresponding AT-sequence $S_i$ incrementally by introducing several intermediary definitions and lemmas.

In the following, $C$ is the set of correct processes, and $B$ the set of Byzantine processes. $C \cup B = \{p_1, ..., p_n\}$. We construct the mock local histories $\{\hat{L}_j\}_{p_j \in B}$ of Byzantine processes as follows.

**Definition B.10.** We define the set $\Sigma$ of UAs defined recursively by the following rules.

• $\Sigma$ contains all the UAs issued by correct processes at line 38 of Algorithm 3. This includes both sending and receiving UAs.

• If some receiving UA $A$ belongs to $\Sigma$, then sendingUA($A$) also belongs to $\Sigma$,

$$ \{ \text{sendingUA}(A) \mid A \text{ is a valid receiving UA} \wedge A \in \Sigma \} \subseteq \Sigma. $$

• If some UA $A$ belongs to $\Sigma$, then all UAs by the same issuer that precedes $A$ also belong to $A$,

$$ \bigcup_{A \in \Sigma} \text{set}(\text{precedingUAs}(A)) \subseteq \Sigma. \qquad (3) $$

$\Sigma$ can be seen as the causal transitive closure of the UAs issued by correct processes: it contains all the UAs that can be traced back to some UA issued by a correct process, either through a sending/receiving relationship as captured by Lemma B.9, or through local precedence as captured by Lemma B.3.

**Lemma B.11 (Validity of UAs in $\Sigma$).** All UAs contained in $\Sigma$ are valid.

*Proof.* The remark holds because all UAs issued by correct processes are valid by construction, and results from the application of Lemma B.9 and Lemma B.3 when defining sendingUA(·) and precedingUAs(·) respectively. □

<footnote>13Recall that we do not consider balance() invocations from Byzantine processes.</footnote>
Likewise, if $\sigma_i^{sn'}$ is a receiving AP corresponding to a transfer$_j^{sn''}$($v', i$) invocation, then transfer$_j^{sn''}$($v', i$) must appear before $o$ in the $\to_S$ total order. Therefore, by induction, the balance of a Byzantine process is also computed exactly like total($i, \{o' \in S \mid o' \to_S o\}$). Finally, due to the $bal_{pvr} \ge v$ check at line 19, the old balance of $p_i$ right before $o$ is guaranteed to be greater than transfer value, which concludes the proof. ◀

**Lemma 2 (AT-Termination).** *All operations of Algorithm 3 (balance and transfer) terminate for correct processes.*

**Proof.** The balance operation of Algorithm 3 terminates trivially. Furthermore, the only blocking instruction of the transfer operation of Algorithm 3 is the ap_prove operation at line 44, in the process_transfer internal operation (called at line 26). This ap_prove operation terminates by AP-Termination, so the transfer operation also terminates. ◀

## A.2 Proof of quasi-anonymity

**Lemma 3 (QAAT-Receiver-Anonymity).** *Given the global history $H$ produced by any execution of Algorithm 3, any transfer$_i(\star, j)$ invocation of $H$, and $j' \in [1..n]$ a process identity chosen by Adv trying to guess $j$, we must have: $\Pr(j = j') \le \min((1/n) + \epsilon(\lambda), 1)$.*

**Proof.** To determine if Adv can obtain any information on the receiver $p_j$ of any transfer$_i(\star, j)$ invocation given a global history $H$, we analyze the content of all message types produced by Algorithm 3. Our algorithm features 2 message types with the following content:

1. Accumulator update sent by a (sender or receiver) process $p_i$ publicly to the network in the ap_prove operation at line 44: value $v = (A'_i, bal\_c'_i)$ and data $data = (\sigma_i, \pi, sn_i + 1, (A_i, A'_i, bal\_c_i, bal\_c'_i, trf\_c_i))$;

2. Message from a sender $p_{snd}$ to a receiver $p_{rcv}$: $\langle \tau, \sigma_{snd}, A_{snd}, w_{snd}, bal\_c_{snd} \rangle$.

Note that sender-receiver messages (item 2) are exchanged outside using the ra_send operation, which ensures sender anonymity and confidentiality. Therefore, only accumulator updates (item 1) need to be considered. VC-Hiding guarantees that the vector commitments $bal\_c_i$, $bal\_c'_i$, and $trf\_c_i$ do not leak any data on the corresponding committed values. Similarly, UA-Indistinguishability guarantees that the accumulators $A_i$ and $A'_i$ do not leak any data on their accumulated sets, and ZKP-Zero-Knowledge ensures that $\pi$ does not leak any data on its secret input secret_data. Finally, the sequence number $sn_i + 1$ does not reveal whether $p_i$ is a sender or receiver, only the number of transfers (debits or credits) in $A_i$. Thus, Adv does not learn any information from accumulator updates.

We conclude that without any information on the content of transfers already included or newly added to some history $H$, Adv cannot deduce the recipient of a transfer more accurately than random, i.e., with a probability of less than $\min((1/n) + \epsilon(\lambda), 1)$, where $\epsilon$ is the statistical negligible function and $\lambda$ is the security parameter of the system. ◀

**Lemma 4 (QAAT-Confidentiality).** *Given a global history $H$ from an execution of Algorithm 3, an arbitrary transfer$_i(v, \star)$ invocation of $H$, and $v' \in \mathbb{R}^+$ an amount chosen by the adversary Adv trying to guess $v$, we must have: $\Pr(v = v') \le \epsilon(\lambda)$.*

**Proof.** The proof follows the same reasoning as that of Lemma 3. ◀
**Definition B.12** (Mock history $\hat{H}$). For a Byzantine process $p_j \in B$, we construct the set $\Theta_j$ of transfer invocations whose sender is $p_j$, and for which both a sending and a receiving UA can be found in $\Sigma$. More formally, we have

$$ \Theta_j \stackrel{\text{def}}{=} \left\{ \text{transfer}_j^{\text{sn}}(\star, \star) \mid \begin{array}{l} \exists A_1, A_2 \in \Sigma : A_1 \text{ is a sending UA} \wedge A_2 \text{ is a receiving UA} \wedge \\ \text{transfer}(A_1) = \text{transfer}(A_2) = \text{transfer}_j^{\text{sn}}(\star, \star) \end{array} \right\}. $$

Let us note $SN_j$ the set of the sequence numbers of the transfer invocations present in $\Theta_j$. $SN_j$ is a set of strictly positive integers (since $p_j$'s genesis UA $A_j^0$ created at line 1 of Algorithm 1 does not have a corresponding transfer invocation), $SN_j \subseteq \mathbb{N}^*$. Note that, by AP-Agreement, each sequence number in $SN_j$ corresponds to a single transfer invocation in $\Theta_j$. As a result, we can define the mock local history $\hat{L}_j$ of $p_j$ as the sequence of transfer invocations present in $\Theta_j$ ordered by their sequence numbers,

$$ \hat{L}_j \stackrel{\text{def}}{=} (\text{transfer}_j^{\text{sn}}(\star, \star) \in \Theta_j)_{\text{sn} \in SN_j}. $$

Combining the mock local histories $(\hat{L}_j)_{j \in B}$ of Byzantine processes with the local histories $(L_i)_{i \in C}$ of correct processes yields a mock history $\hat{H}$.

**Definition B.13** (Set $\mathcal{S}_i$ of operation perceived by a correct process $p_i$). Consider a correct process $p_i$, and the set $\mathcal{S}_i$ containing all invocations made by $p_i$ (to the operations transfer and balance), and all transfer invocations by other processes (correct of faulty) present in $\hat{H}$.

$$ \mathcal{S}_i = \text{set}(L_i) \cup \bigcup_{j \in C \setminus \{i\}} \text{transferSet}(L_j) \cup \bigcup_{j \in B} \text{transferSet}(\hat{L}_j), \quad (4) $$

where $C$ and $B$ are the sets of correct and Byzantine processes as defined above, respectively, and transferSet(·) is the notation introduced in Section 4 to denote the set of transfer invocations contained in a sequence.

To produce a sequence $S_i$ from the elements of $\mathcal{S}_i$, we construct a partial order $\rightsquigarrow_i$ on $\mathcal{S}_i$. We do so incrementally, by introducing two binary relations, $\overset{1}{\rightsquigarrow}_i$ and $\overset{2}{\rightsquigarrow}_i$.

* $\overset{1}{\rightsquigarrow}_i$ totally orders the invocation of $p_i$ and ensures that incoming transfers received by a process $p_j$ are ordered before the subsequent balance invocations (if $j = i$) and outgoing transfers issued by $p_j$.

* $\overset{2}{\rightsquigarrow}_i$ focuses specifically on $p_i$ to guarantee that incoming transfers received by $p_i$ are totally ordered with respect to $p_i$'s local invocation to balance(·).

Distinguishing between $\overset{1}{\rightsquigarrow}_i$ and $\overset{2}{\rightsquigarrow}_i$ as intermediary steps towards $\rightsquigarrow_i$ will in turn make it easier to prove that the $\rightsquigarrow_i$ is acyclic (a necessary condition to show that it is a partial order).

**Definition B.14** (Binary relations $\overset{1}{\rightsquigarrow}_i$, $\overset{2}{\rightsquigarrow}_i$, and $\rightsquigarrow_i$ on $\mathcal{S}_i$). We define $\overset{1}{\rightsquigarrow}_i$ on $\mathcal{S}_i$ as follows.

* **Inclusion of $p_i$'s local order.** $\overset{1}{\rightsquigarrow}_i$ respects the local process order $\rightarrow_i$ of operations invoked by $p_i$, i.e., $\rightarrow_i \subseteq \overset{1}{\rightsquigarrow}_i$.

* **Ordering of incoming transfers.**

- For any process $p_j$, $t_{\triangleright j} = \text{transfer}^*_*(\star, j) \in \mathcal{S}_i$ a transfer invocation whose receiver is $p_j$, and $t_{j\triangleright} = \text{transfer}^*_j(\star, \star) \in \mathcal{S}_i$ a transfer invocation by $p_j$ such that $t_{\triangleright j} \neq t_{j\triangleright}$, if receivingUA($t_{\triangleright j}$) $\in$ precedingUAs(sendingUA($t_{j\triangleright}$)), then $t_{\triangleright j} \overset{1}{\rightsquigarrow}_i t_{j\triangleright}$.
## A.3 Informal arguments for lightness and consensus-freedom

In this section, we informally show that our asset transfer system (Algorithm 3) is consensus-free and light if it is instantiated with the AP, VC, UA and ZKP implementations of Appendix B. Our system's consensus-freedom follows the consensus-freedom of our AP implementation (Appendix B.3). The lightness of our system comes from its succinctness and polylogarithmic storage.

- The succinctness of our system comes from the succinctness of our Agreement Proof implementation (Appendix B.3) and CRASSe implementation of universal accumulators (Appendix B.1), as well as the succinctness of Pedersen vector commitments (Appendix B.2) and Spartan zk-SNARKs (Appendix B.4).

- Let us consider a correct process $p_i$. The polylogarithmic storage of our system comes from the fact that all its local variables, apart from the accumulator $A_i$, are in $O_\lambda(1)$ bits: by definition, $bal_i$ and $sn_i$ have $O_\lambda(1)$ bits (see Section 5.3), $bal_{c_i}$ and $bal_{o_i}$ have $O_\lambda(1)$ bits with Pedersen vector commitments, and $\sigma_i$ has $O_\lambda(1)$ bits with our AP implementation (see Appendix B.3). Moreover, $A_i$ has $O_\lambda(\text{polylog } |S_i|)$ bits with our CRASSe implementation (see Appendix B.1), where $S_i$ is the accumulated set corresponding to $A_i$ containing all the transfers (debits or credits) of $p_i$. Finally, the local variables of our AP implementation are also in $O_\lambda(1)$ bits (see Appendix B.3).

# B Implementations of the Schemes of Section 4

## B.1 A new accumulator implementation: Chinese-remainder-based accumulator with sublinear storage (CRASSe)

In this section we introduce a new non-trivial implementation of a cryptographic accumulator based on the Chinese Remainder Theorem (CRT) [24]. We call this new accumulator implementation CRASSe, for “Chinese-remainder-based accumulator with sublinear storage”. To our knowledge, this accumulator is the first one that does not require the manager to know the plain accumulated set $S$ to add/delete elements or prove their (non-)membership. It is also the first accumulator that incurs a storage cost for the manager that is only polylogarithmic in the size of the accumulated set $S$, which we denote $O_\lambda(\text{polylog } |S|)$. Algorithm 7 implements all operations presented in the universal accumulator specification of Section 4.3.

### B.1.1 Preliminaries

**Notations.** We use the following notations in our accumulator implementation.

- $a \parallel b$ is the concatenation of two bit-strings $a$ and $b$.

- $\mathbf{a}$ (note the bold font) is a vector of an arbitrary size $n$ with elements $\{a_1, \dots, a_n\}$.

- $[n]$ denotes the set of integers $\{1, \dots, n-1\}$.

- $x \stackrel{s}{\leftarrow} S$ denotes sampling a random element $x \in S$ uniformly.

- $\text{Primes}(a, b)$ is the set of primes greater than $2^a$ and smaller than $2^b$.

- $H_{\text{Primes}}$ is a mapping of each index $i \in [\pi(2^b) - \pi(2^a)]$ to a distinct prime in $\text{Primes}(a, b)$, where $\pi$ is the prime counting function.

- $\text{GGen}(\lambda)$ is a randomized algorithm that generates a group of unknown order in a range $[A, B]$ such that $A, B$ and $A-B$ are all integers exponential in $\lambda$.

- $a \mid b$ means “a divides b” and $a \nmid b$ means “a does not divide b”.
- For transfer invocation $t_{\succ i} = \text{transfer}^*_{\star}(\star, i) \in \mathcal{S}_i$ whose receiver is $p_i$, and any invocation $b_i = \text{balance}_{i}(\cdot)/v$ performed by $p_i$, if the execution of line 38 that generated receiving UA ($t_{\succ i}$) occurred before that of line 23 corresponding to $b_i$, then $t_{\succ i} \stackrel{1}{\rightsquigarrow} b_i$.

We define $\stackrel{2}{\rightsquigarrow}_i$ on $\mathcal{S}_i$ as follows.

* **Ordering of $p_i$'s balance.** For any invocation $b_i = \text{balance}_{i}(\cdot)/v$ performed by $p_i$, and any transfer invocation $t_{\succ i} = \text{transfer}^*_{\star}(\star, i) \in \mathcal{S}_i$ whose receiver is $p_i$, if the execution of line 23 corresponding to $b_i$ occurred before that of line 38 that generated receiving UA ($t_{\succ i}$), then $b_i \stackrel{2}{\rightsquigarrow} t_{\succ i}$.

$\stackrel{1}{\rightsquigarrow}_i$ is defined as the transitive closure of the union of $\stackrel{1}{\rightsquigarrow}_i$ and $\stackrel{2}{\rightsquigarrow}_i$, i.e., $\stackrel{1}{\rightsquigarrow}_i = (\stackrel{1}{\rightsquigarrow}_i \cup \stackrel{2}{\rightsquigarrow}_i)^+$.

**Lemma B.15.** $\stackrel{1}{\rightsquigarrow}_i$ is acyclic.

*Proof.* The distributed system is implicitly embedded in some physical time, which we assume is Newtonian and linear.<fnref n="14" /> We associate each element $x$ of $\mathcal{S}_i$ with a timestamp $\tau(x)$ from this physical time as follows:

* if $x = \text{balance}_{i}(\cdot)/v$ is a balance invocation by $p_i$, $\tau(x)$ is the time point at which line 23 of Algorithm 3 is executed;

* if $x = \text{transfer}^*_{\star}(\star, \star)$ is a transfer invocation, $\tau(x)$ is the time point at which sendingUA($x$) was created.

Consider $x, y \in \mathcal{S}_i$ such that $x \stackrel{1}{\rightsquigarrow}_i y$. At least one of the following cases holds.

* Case 1 (Inclusion of $p_i$'s local order): $x$ and $y$ are both invoked by $p_i$ with $x \to_i y$. Because $p_i$ is sequential, by definition of $\to_i$ we have $\tau(x) < \tau(y)$.

* Case 2 (Ordering of incoming transfers):

- $x = \text{transfer}^*_{\star}(\star, j) \in \mathcal{S}_i$ is a transfer invocation whose receiver is some process $p_j$, and $y = \text{transfer}^*_{j}(\star, \star) \in \mathcal{S}_i$ a transfer invocation by $p_j$, such that receivingUA($x$) $\in$ precedingUAs(sendingUA($y$)). This last inclusion means that sendingUA($y$) can be linked recursively to receivingUA($x$) using proofs issues by $p_j$, the predicates $P_A$ and $P_{ZK}$, and AP-Knowledge-Soundness and ZKP-Knowledge-Soundness. AP-Knowledge-Soundness and ZKP-Knowledge-Soundness both imply that $p_j$ must know the secret data required to issue a proof *before* the proof is generated. As a result receivingUA($x$) $\in$ precedingUAs(sendingUA($y$)) implies that $\tau(x) < \tau(y)$.

- $x = \text{transfer}^*_{\star}(\star, i) \in \mathcal{S}_i$ is a transfer invocation whose receiver is $p_i$, $y = \text{balance}_{i}(\cdot)/v$ is a balance invocation performed by $p_i$, such that the execution of line 38 that generated receivingUA($x$) occurred before that of line 23 corresponding to $y$. The same reasoning as above yields that $\tau(x) < \tau(y)$.

We conclude that $\stackrel{1}{\rightsquigarrow}_i$ respects the timestamps assigned by $\tau(\cdot)$. Assuming physical time is acyclic, this implies that $\stackrel{1}{\rightsquigarrow}_i$ is also acyclic. $\square$

<footnote n="14">¹⁴Note that the proof also holds in the context of special relativity, even though there may not be an absolute global clock ordering the events of the system. This is because any observer in the system still sees the events in a linear (total) order that may, however, differ from one observer to the next. For this proof, it suffices to take any observer (e.g., $p_i$) as a frame of reference to construct the timestamps. But because of the causality principle, two causally-linked events are necessarily seen in the same order, no matter the chosen frame of reference.</footnote>
Most of the above notations are standard cryptographic notations. We reuse the notations introduced by [7].

**Generic groups of Unknown Order.** We adopt the generic group model for groups of unknown order as defined in [15] and used in [7].

**► Definition 5 (Groups of Unknown Order).** A group of unknown order $\mathbb{G}$ has order $|\mathbb{G}| \stackrel{\$}{\leftarrow} [A, B]$ where $A$ and $B$ are two public integer parameters. The elements of the group $\mathbb{G}$ are defined by a random injective function $\sigma : \mathbb{Z}_{|\mathbb{G}|} \to \{0, 1\}^\ell$ for some $\ell$ such that $2^\ell \gg |\mathbb{G}|$. The group elements are denoted $\sigma(0), \dots, \sigma(\mathbb{G} - 1)$. Let $\mathcal{A}$ be a probabilistic generic group algorithm initialized with a list $\mathcal{L}$ of encodings. $\mathcal{A}$ can query oracles $O_1$ and $O_2$.

- $O_1$ selects $r \in \mathbb{Z}_{|\mathbb{G}|}$, appends $\sigma(r)$ to $\mathcal{L}$ and returns $\sigma(r)$.

- When $\mathcal{L}$ has size $q$, $O_2(i, j, \pm)$ selects two indices $i, j \in \{1, \dots, q\}$, ouputs $\sigma(i \pm j)$ and appends it to $\mathcal{L}$.

Concrete examples of such groups are RSA groups, ideal class groups of imaginary quadratic fields and hyperelliptic Jacobians. Note that RSA groups require a trusted setup to compute the RSA modulus, and are thus not viable for our trustless implementation. Dobson et al. [18] provide an algorithm (Algorithm 4 of [18]) to compute efficient genus-3 hyperelliptic Jacobians of unknown order trustlessly.

**Assumptions.** We define in the following cryptographic assumptions used in our construction.

**► Assumption 1 (Random Oracle Model (ROM)).** Informally, the ROM assumes a public oracle that implements a completely random function. Such a function cannot exist in the real world, as it would take infinite space to represent. However, cryptographic hash functions are designed to behave similarly and are assumed to be ROs in practice.

**► Assumption 2 (Discrete Logarithm Assumption (DL)).** Let $\mathcal{G} \leftarrow \text{GGen}(\lambda)$ be a generic group of unknown order and let $\langle g_1, \dots, g_n \rangle$ and let Adv be a generic polynomial time algorithm. The DL assumption holds for $\mathcal{G}$ iff Adv succeeds with at most a negligible probability in outputting $a_1, \dots, a_n$ and $b_1, \dots, b_n$ s.t. $\prod_{i=1}^n g_i^{a_i} = \prod_{i=1}^n g_i^{b_i}$.

**► Theorem 6 (Chinese Remainder Theorem (CRT)).** Let $\ell_1, \dots, \ell_k$ be pairwise coprime integers greater than 1 and $a_1, \dots, a_k$ integers s.t. $0 \le a_i < \ell_i$. Then $\exists! x \in \mathbb{Z}$ s.t. $0 \le x < \prod_{i=1}^k n_i$ and $\forall i \in \{1, \dots, k\}, x \equiv a_i \bmod n_i$.

## B.1.2 Construction

**Sublinear representation of a set of bounded integers.** Our aim is to store a compressed version of a set of positive $b$-bits integers $\mathbf{a} = \{a_1, \dots, a_k\}$. To achieve this goal, we make use of the CRT. Let $b_1$ and $b_2$ be polylogarithmic bit sizes in $b$, with $b_i = \log_2(b)^{s_i}$ and $s_1 > s_2$. Note that the choice of $b_1$ and $b_2$ determines the maximum size of the set (number of indexes). Let $\ell = \{\ell_1, \dots, \ell_k\}$ be a set of $k$ distinct $b_1$-bit prime numbers in Primes($b_2, b_1$). We assume that the index/prime mapping of $\ell$ is provided in the form of the public function $H_{\text{Primes}}$, such that $\ell_i = H_{\text{Primes}}(i)$. Thus, we do not consider the storage of $\ell$. We can write $a_i = q_i\ell_i + r_i$, where $q_i = \lfloor a_i/\ell_i \rfloor$ and $r_i = a_i \bmod \ell_i$ are the quotient and the remainder of the integer division of $a_i$ by $\ell_i$. Recall that as the integers in $\ell$ are primes and the set $\mathbf{r} = \{r_1, \dots, r_k\}$ contains integers $r_i < \ell_i$, there exists a unique integer $x < \prod_{i=1}^k \ell_i$ that satisfies the equation of the CRT (Theorem 6). Since $x$ is bounded by $\prod_{i=1}^k \ell_i$, $x$ can be stored as a $(kb_1)$-bit integer, which is polylogarithmically more efficient than storing $k$.
**Lemma B.16.** $\stackrel{2}{\rightsquigarrow}_i$ is acyclic.

*Proof.* $\stackrel{2}{\rightsquigarrow}_i$ is a simple bipartite binary relation between balance invocations on one side, and transfer invocations on the other, hence it cannot contain cycles, and is therefore acyclic. □

**Lemma B.17.** $\stackrel{1}{\rightsquigarrow}_i \cup \stackrel{2}{\rightsquigarrow}_i$ is acyclic.

*Proof.* The proof is by contradiction. Assume $\stackrel{1}{\rightsquigarrow}_i \cup \stackrel{2}{\rightsquigarrow}_i$ contains at least one cycle. Consider the shortest such cycle $\mathcal{C}_{\min}$. Because $\stackrel{1}{\rightsquigarrow}_i$ and $\stackrel{2}{\rightsquigarrow}_i$ are both acyclic (Lemmas B.15 and B.16), $\mathcal{C}_{\min}$ must involve both $\stackrel{1}{\rightsquigarrow}_i$ and $\stackrel{2}{\rightsquigarrow}_i$.

Consider one of the $\stackrel{2}{\rightsquigarrow}_i$ ordering in $\mathcal{C}_{\min}$. By definition of $\stackrel{2}{\rightsquigarrow}_i$, this ordering is of the form $b_i \stackrel{2}{\rightsquigarrow}_i t_{\triangleright i}$, where $b_i$ is a balance invocation by $p_i$ and any $t_{\triangleright i}$ is a transfer invocation whose receiver is $p_i$. Consider the successor $y$ of $t_{\triangleright i}$ in $\mathcal{C}_{\min}$. By construction of $\stackrel{2}{\rightsquigarrow}_i$, $t_{\triangleright i} \stackrel{2}{\rightsquigarrow}_i y$, which implies $t_{\triangleright i} \stackrel{1}{\rightsquigarrow}_i y$.

By definition of $\stackrel{1}{\rightsquigarrow}_i$, $t_{\triangleright i} \stackrel{1}{\rightsquigarrow}_i y$ leads to two cases.

* Case 1: $t_{\triangleright i} \to_i y$. In this case, $y \in L_i$ by definition of $\to_i$, $p_i$'s local process order.

* Case 2: $t_{\triangleright i} \not\to_i y$. In this case, $t_{\triangleright i} \stackrel{1}{\rightsquigarrow}_i y$ resulted from the rule *Ordering of incoming transfers*. $y$ is therefore either a balance or transfer operation invoked by $p_i$, i.e., we also have $y \in L_i$.

We therefore have $b_i \stackrel{2}{\rightsquigarrow}_i t_{\triangleright i} \stackrel{1}{\rightsquigarrow}_i y$, with $b_i, y \in L_i$. The definitions of $\stackrel{2}{\rightsquigarrow}_i$ and $\stackrel{1}{\rightsquigarrow}_i$ imply that the invocation of $b_i$ by $p_i$ precedes in time the generation of receivingUA($t_{\triangleright i}$) also by $p_i$, which itself precedes the invocation of $y$ still by $p_i$ (either directly in the case of $\stackrel{2}{\rightsquigarrow}_i$, and if $y$ is a balance invocation, or using the same argument on cryptographic proofs as in Lemma B.15 if $y$ is a transfer). By definition of the process order $\to_i$, this leads to $b_i \to_i y$, and hence $b_i \stackrel{1}{\rightsquigarrow}_i y$. We can, therefore, remove $t_{\triangleright i}$ from $\mathcal{C}_{\min}$, and replace $b_i \stackrel{2}{\rightsquigarrow}_i t_{\triangleright i} \stackrel{1}{\rightsquigarrow}_i y$ by $b_i \stackrel{1}{\rightsquigarrow}_i y$, thus creating a cycle $\mathcal{C}'_{\min}$ in $\stackrel{1}{\rightsquigarrow}_i \cup \stackrel{2}{\rightsquigarrow}_i$ with one less element than $\mathcal{C}_{\min}$. This is a contradiction as $\mathcal{C}_{\min}$ was assumed to be the shortest. □

**Corollary B.18.** $\stackrel{2}{\rightsquigarrow}_i$ is a partial order on $\mathcal{I}_i$.

*Proof.* $\stackrel{2}{\rightsquigarrow}_i$ is transitive by construction. By Lemma B.17, it is the transitive closure of an acyclic relation and is, therefore, also acyclic. □

**Lemma B.19.** Each element of the poset $(\mathcal{I}_i, \stackrel{2}{\rightsquigarrow}_i)$ only has a finite number of predecessors.

*Proof.* This follows from the sequential nature of processes (and in particular that all processes have a starting point in their execution), the link between $\stackrel{1}{\rightsquigarrow}_i$ and $\stackrel{2}{\rightsquigarrow}_i$ and physical time (Lemmas B.15 and B.16), and the (implicit) assumption that processes only take a finite number of local steps per unit of time. □

**Definition B.20 (Sequence $S_i$).** By Lemma B.19 the poset $(\mathcal{I}_i, \stackrel{2}{\rightsquigarrow}_i)$ can be sorted topologically into a sequence. We define $S_i$ as one of the topological sorts of $(\mathcal{I}_i, \stackrel{2}{\rightsquigarrow}_i)$. We note $\to_{S_i}$ the total order induced by $S_i$ on its elements.

In the following, we will use the function $total(\cdot, \cdot)$ introduced in Section 4 to compute the account balance of a process resulting from the transfer it sends and receives. Given a process $p_j$ and a set of operations invocations $O$, $total(j, O)$ is defined as

$$total(j, O) = \text{init}_j + (\Sigma_{\text{transfer}_*(v,j) \in O} v) - (\Sigma_{\text{transfer}_j(v,\star) \in O} v).$$

**Lemma B.21.** $\forall b_i = \text{balance}_i() / v \in S_i : v = total(i, \{o \in S_i | o \to_{S_i} b_i\})$.