Fast, Private and Regulated Payments in Asynchronous Networks

Bitcoin [33] revolutionized the world of finance by proposing a fully decentralized asset-transfer system that allows an open set of users to consistently exchange assets without any mutual trust. Instead of relying on a central authority, users repeatedly engage in a form of consensus [22, 18] to maintain a replicated ledger – an ever-growing record of all transactions. It was later observed [27, 26] that, strictly speaking, global consensus, a notoriously hard task [16, 17] that requires partial synchrony [22, 12], is not necessary in payments. In most common cases, when every account is maintained by a dedicated user, asset transfer can be implemented in an asynchronous, responsive way on top of the reliable-broadcast primitive [10] (instead of consensus).

Reliable broadcast is weaker than consensus as it allows the correct users to eventually and consistently agree on the set of issued transactions but not on their order. However, it turned out to be strong enough to prevent double spending, a major issue in asset-transfer systems. This observation gave rise to a series of purely asynchronous, consensus-free asset-transfer systems [14, 5, 31].

However, a decentralized asset-transfer system, as any replicated service, still faces a vital challenge of preserving privacy of its users. Indeed, in all the mentioned payment protocols, all transactions are inherently public and every user’s activities are traceable. Hiding the amount of a payment offers confidentiality and hiding the identities of the sender and receiver offers anonymity. Fully private payment systems ought to offer both confidentiality and anonymity. Furthermore, many important payment applications, such as Central Bank Digital Currency (CBDC) [4], require mechanisms for regulatory enforcement, such as limiting transaction amounts.

Existing distributed asset-transfer systems ([6, 7, 37, 38, 41, 44, 45], to name a few) arbitrate a trade-off between the four following aspects: (a) Privacy guarantees, (b) Model assumptions, (c) Regulation enforcement, and (d) Performance. Reconciling these four aspects is a onerous challenge, as strengthening one aspect often weakens another. Table 1 provides a detailed comparison of several payment systems across these dimensions. This table and its content are detailed and discussed in Section 8.

In this paper, we address this challenge. We introduce the abstraction of Fully Private Asset Transfer (FPAT) that maintains conventional safety and liveness properties of a payment system (informally, no asset is spent twice and every transaction takes effect), while at the same time making sure that no transaction’s detail is leaked to a non-involved party. We then describe the PaxPay protocol, a FPAT implementation over an asynchronous network. PaxPay has been implemented in Golang using Gnark library [8].

As in UTXO transactions [33], to execute a transfer, the sender spends a set of old coins it has received earlier and generates a set of new coins of the same total value. Every coin is uniquely identified by its serial number. Every coin should be signed by a sufficiently large set (a $2/3$ quorum) of validators, i.e., dedicated parties that maintain lists of spent coins and make sure that no user spends a same coin twice.

The protocol operates in an asynchronous network, where any number of users and less than one third of validators can be Byzantine (deviating arbitrarily from its algorithm). The rest of the validators are considered semi-honest (following their algorithm but possibly sharing their states with the adversary). To ensure that the transfer is legal, several assertions have to be checked: the total value of the spent coins equals the total value of the new coins, the user that calls the transfer is the owner of the spent coins, all the coins are properly signed, etc.

To provide full privacy (confidentiality and anonymity), PaxPay leverages several cryptographic primitives. The legality of transactions is verified within a non-interactive zero-knowledge proofs (NIZK). A blind signature scheme is used at the validators’ side and these signatures are verified within the NIZK, allowing not to reveal the coins or their signatures when spending them. To verify these signatures efficiently, we implemented the NIZK using the Groth16 [25] scheme and employed a pairing-based signature scheme [35]. We then selected a pair of elliptic curves that form a chain to instantiate these cryptographic primitives, allowing efficient verification of the signature within the NIZK (we refer to Section 7 for more details).

We also describe and implement a regulation enforcement mechanism that can be built on top of our system. Similar to PEReDi and PARScoin [37, 38], our approach allows setting limits on individual transfer amounts or the cumulative amount transferred by a user since they joined the system. However, regulations for CBDCs mandate stringent measures for Anti-Money Laundering (AML) and Countering the Financing of Terrorism (CFT). These measures go beyond simply limiting transaction amounts.

PEReDi and PARScoin [37, 38] address these requirements and enable validators to reveal the details of transfers if needed. This could put at risk the privacy of the users. Their approach relies on additional trust assumptions, requiring non-Byzantine validators to be honest (i.e., not to share any information with the adversary) to maintain privacy. We avoid such extra assumptions by equipping the users with a mechanism to generate cryptographic proofs for arbitrary statements about the histories of their transactions. It enables extracting a requested information without disclosing the full content of the transaction histories.

Additionally, we incorporate a novel mechanism, empowering the regulator to impose sanctions, precluding specific addresses from interactions with other users. This ensures compliance with traditional financial sanctions emitted by the central banks or intergovernmental organizations (e.g., the UN¹¹1https://main.un.org/securitycouncil/en/sanctions/information) and explicitly required by the European Central Bank for the digital Euro [4].

The regulatory mechanism is implemented by introducing an additional type of coin, referred to as the compliance coin. At a time, each user may possess several regular coins, but only one unique compliance coin. In each transfer, the compliance coin of the sender must be spent together with the regular coins. Then a new compliance coin containing the information of the transfer is generated (i.e., signed by a quorum of validators). The compliance coin thus allows us to keep track records of all the interactions of a user with the system, which can be seen as a commitment to the transaction history and some aggregated values. To generate an initially valid compliance coin, before joining the system, the user must be registered with a regulatory authority.

Our regulation framework incurs very low impact on the transaction throughput. It mainly affects the transaction proving time (by doubling it compared to the non-regulated case), which we do not consider a primary performance factor. In contrast, such a mechanism could be difficult and performance-intensive to implement in other protocols that rely on Sigma protocols [15], such as UTT [41], Zef [6], Peredi [37], and Parscoin [38], which use these protocols to construct their NIZKs.

Finally, we evaluated the performance of PaxPay, in comparison with state-of-the-art payment systems that provide privacy-preserving and/or regulatory-enforcement features (cf Table 1). In our benchmark (detailed in Section 7.2), we witness that PaxPay can process at least $8$ times more transactions per second than any of these systems. The benchmark on AWS EC2 instances demonstrates a throughput of $925$ transactions per second. The performance gains can be explained by the use of Groth16 as a succinct NIZK with low verification cost. In return, this comes at the cost of heavy computations required to generate a proof. The time required to create a transfer request with limited computational resources in PaxPay on a one-core CPU is up to $7s$ for example. However, given the throughput gains, this appears to be a good trade-off. Moreover, PaxPay’s design allows for pushing the throughput even further by parallelizing the validator’s load on several machines.

The full version of this paper [11] incorporates more details including the algorithms that implement PaxPay, the security proofs, the link toward PaxPay implementation and additional details on the benchmarks.

To sum up our contributions:

• $\mathrm{■}$

  We formalize the problem by introducing the Fully Private Asset Transfer abstraction (FPAT).

• $\mathrm{■}$

  We propose PaxPay, a protocol that implements a FPAT object, and prove its correctness.

• $\mathrm{■}$

  We implement PaxPay in Golang, mainly leveraging on the Gnark [8] library.

• $\mathrm{■}$

  PaxPay achieves a true reconciliation of (a) Privacy, (b) Model Assumptions (network synchrony and trust assumptions for validators), (c) Regulation Enforcement, and (d) Performance. Unlike earlier works that propose trade-offs, PaxPay excels in each of these aspects simultaneously, bringing together the best of all these dimensions:

  • –

    Regarding Privacy, transactions in PaxPay are confidential, fully anonymous, and unlinkable, ensuring the most robust privacy guarantees.

  • –

    Regarding Model Assumptions, the system tolerates up to one-third Byzantine validators, with the remaining validators only required to be semi-honest, and does not rely on the network synchrony.

  • –

    Regarding Regulation, PaxPay provides a comprehensive regulation framework by enabling users to generate cryptographic proofs about their transaction history, setting spending limits, and incorporating a sanction mechanism preventing sanctioned addresses to receive or spend funds.

  • –

    Finally, our implementation outperforms state-of-the-art protocols. Also, we show that the transaction throughput of PaxPay scales with the computational power of validators. The system can further increase its supported throughput by distributing validators across additional machines.

• $\mathrm{■}$

  PaxPay can find a variety of use cases such as a standalone payment system, a layer 2 solution on top of a blockchain (brings scalability, compliance, or privacy) or a CBDC.

Gupta [27] and Guerraoui et al. [26] proposed a payment system that replaces the conventional consensus-based synchronization with the secure broadcast primitive [10, 32]. Systems like Astro [14], FastPay [5], Zef [6], PARScoin [38] and UTT [41] extend this approach, operating without consensus in asynchronous networks.

Zerocash [7], Zexe [9], Monero [34], Quisqus [21] and Lelantus [29] are payment systems built on top of blockchains and consensus. They provide privacy via NIZKs or ring signatures. Zerocash and Zexe [7, 9] use commitments stored in Merkle trees and nullifiers to prevent double spending. Each transaction is accompanied by an NIZK to provide privacy but these systems offer inherently low transaction throughput. Monero [34] and Quisquis [21] relies on ring signatures to provide anonymity but only limits the sender and receiver’s identity to a small subset of the users, known as the anonymity set. Compared to Monero, Quisquis offers stronger privacy guarantees in certain scenarios preventing possible de-anonymization.

Lelantus [29, 30] offers privacy via NIZK requires less advanced cryptographic assumptions than Zerocash or Zexe, for instance it does not require any trusted setup. It also proposes batch verification for validators.

All payment systems mentioned so far are built on a blockchain and, thus, require consensus. Baudet et al. [6] describe Zef, a private payment system, that assumes an asynchronous network but only provides partial anonymity and confidentiality. To improve performance, the transaction data in Zef is distributed over a set of authorities. Each authority can be sharded – i.e., distributed over several machines, as in Astro [14] and in this work.

PRCash [44], Platypus [45], PEReDi [37], PARScoin [38] and UTT [41] incorporate certain regulatory features into private payment systems. A common element in their designs is the reliance on NIZK.

Garman et al. [23] were among the first to address regulation by enforcing policies such as fixing a spending limit on a system with a similar construction as Zerocash. Their system has not been implemented and, as it is built on top of Zerocash, it shares the same major drawbacks.

PRCash [44], as Zerocash, is blockchain-based and operates with commitments but offers only partial privacy. Regulation features proposed by PRCash are limited: users cannot spend more than a predefined amount set by the regulator within a certain time window.

UTT [41], a concurrent work to our paper, proposes an asynchronous private payment system with privacy guarantees, a low transaction latency and a high transaction throughput. Both UTT and PaxPay protocols follow a similar approach, using coin commitments and consistent broadcast to create and spend coins in a fully private manner. However, the regulation features offered by UTT are restricted to the anonymity budget that limits the amount of anonymous coins that a user can transfer. Compared to UTT, PaxPay offers a more comprehensive set of regulation features and exhibit better performance, due to improved NIZK construction.

Platypus [45] offers regulation features of holding limits, receiving limits, and spending limits. It uses NIZK with low verification costs to increase transaction throughput. However, unlike other payment systems described in this section, Platypus is a centralized payment system rather than a distributed one.

PEReDi [37] is an account-based system. The regulation framework enforces spending and receiving limits for each transaction and imposes restrictions on the maximum amount a user can hold. Additionally, the system allows validators to trace funds and reveal details of certain payments. Users encrypt their transaction details with a threshold encryption scheme so that a quorum of validators can decrypt them. PEReDi needs a synchronous network and correct (i.e., non-Byzantine) validators must be honest (i.e., strictly follow the protocol and avoid seeking additional information). In contrast, most systems discussed here (as well as ours) are designed to tolerate semi-honest correct validators.

Concurrently with this work, the same authors have recently proposed PARScoin [38]. PARScoin enhances PEReDi by allowing asynchronous transactions yet still requires honest validators and faces limited throughput. PARScoin’s protocol is similar to the one employed by UTT and our work, relying on Byzantine consistent broadcast. Our work differs from PARScoin in the NIZK construction which offers better performance, fewer assumptions on the validators and additional regulations features. Also, neither PRCash, PARScoin nor PEReDi have conducted latency tests to evaluate the maximum transaction throughput of their systems, they only provide benchmarks of their primitives (such as the time to prove or verify a transaction).

Other decentralised privacy-preserving payment systems adopt this auditability approach such as [3, 36, 13].

In this paper, we introduce a new specification (inspired by the formalism recently proposed by Albouy et al. [1]), as existing ones do not address our particular problem. They describe either private payment systems that cannot be implemented in asynchronous networks [19], asynchronous payment systems that lack anonymity [26, 14, 31], or non-sequential specifications that do not align with how specifications are typically defined in the distributed systems literature [37, 38, 41].

At the abstract level, the state of the FPAT object is represented as an array of $U$ positive integer values ${[v_k]}_{k=1}^U$, one for each user, interpreted as the current balances of the users’ accounts. Let ${[v_k^{init}]}_{k=1}^U$ be the initial state of the object. The object exports two operations: transfer and balance. Assuming that a user $u$ invokes an operation, they are defined as follows:

• $\mathrm{■}$

  ${\text{transfer}}_u(v,w)/r$ takes as inputs a value $v$ and a user identifier $w$. It transfers the amount $v$ from $u$ to $w$: updates a state ${[v_k]}_{k=1}^U$ to the state ${[v_k^{\prime }]}_{k=1}^U$ where $v_k^{\prime }=v_k+v$ if $k=w\wedge u\ne w$, $v_k^{\prime }=v_k-v$ if $k=u\wedge u\ne w$ and $v_k^{\prime }=v_k$ otherwise. It returns a binary response $r=\mathrm{𝖼𝗈𝗇𝖿𝗂𝗋𝗆}$ if it succeeds and $r=\mathrm{𝖿𝖺𝗂𝗅}$ otherwise.

• $\mathrm{■}$

  ${\text{balance}}_u()/v_u$ takes no inputs and returns the value $v_u$ stored at location $u$ of the state ${[v_k]}_{k=1}^U$.

Let $𝒪$ be a set of FPAT operations – invocations of transfer and balances provided with matching responses, each associated with a distinct user. Let ${\text{transfer}}_u(\ast ,\ast )/C$ (resp., ${\text{transfer}}_u(\ast ,\ast )/F$) denotes a transfer operation invoked by a user $u$ that returns confirm (resp. fail). For each user $u$, we define a function ${\text{total}}_i(𝒪)$ as follows:

${\text{total}}_u(𝒪)$ is thus defined as the current balance of $u$ after all successful transfers in $𝒪$ complete: the initial amount owned by $u$, minus all the funds sent by $u$ plus all the funds received by $u$ in the set of operation $𝒪$.

A sequential history $S$ (of FPAT) is a totally ordered set of FPAT operations, let ${\prec }_S$ be this order. Let ${S|}_u$ denotes the sub-sequence of $S$ consisting of the events of user $u$. We say that $S$ is legal if:

1. 1.

   $\forall o=transfe{r}_u(v,w)/C\in Sv\le tota{l}_u(\{o^{\prime }\in S:o^{\prime }{\prec }_{S}o\})$

2. 2.

   $\forall o=balanc{e}_u()/v\in Sv\le tota{l}_u(\{o^{\prime }\in S:o^{\prime }{\prec }_{S}o\})$

3. 3.

   If an operation ${\text{balance}}_u()$ returning $v_1$ directly precedes a ${\text{transfer}}_u(v_2,w)$ operation in ${S|}_u$, and $v_2\le v_1$, then the transfer operation cannot return $\mathrm{𝖿𝖺𝗂𝗅}$.

Consider an execution of a FPAT algorithm: a sequence of events produced by the algorithm, such as invocations and responses of FPAT operations, sending and receiving messages, etc. A local history $L_i$ of a user $i$ is the sequence of operations invoked by $i$ in that execution. We assume that correct users are well-formed – they never invoke a new operation before the previous one returns, and thus if $u$ is correct, then $L_u$ is sequential. In case the last operation of $L_u$ is incomplete (not followed by a response), we can add any matching response and get a completion of $L_u$. Now a history $H$ is a vector $(L_1,L_2,\mathrm{\dots },L_{|𝒰|})$ of local histories, one for each user. Notice that if the history is produced by an execution of a FPAT algorithm, only the local histories of correct users are of interest for us: a Byzantine user is not obliged to follow the protocol.

A sequential (FPAT) history $S$ is a serialization of a history $H=(L_1,L_2,\mathrm{\dots },L_{|𝒰|})$ if for each correct user $u$, there exists ${\widehat{L}}_u$, a completion of $L_u$, such that ${S|}_u={\widehat{L}}_u$ (${\prec }_S$ respects the local order ${\prec }_{{\widehat{L}}_u}$). $S$ can be seen as a global interpretation of the local histories of correct users. Notice that we allow any operations to be executed by Byzantine users in $S$, as long as it “makes sense” to the correct ones.

An implementation of a FPAT-object is FPAT-Safe if and only if, for any finite history of execution $H$ it produces, there exists a serialization $S$ of $H$ which is legal.

Liveness ensures that (1) every operation invoked by a correct user eventually completes and (2) considering two correct users $u$ and $w$, if $w$ transfers money to $u$, then $u$ eventually receives this money. Let us consider the existence of a global time during the execution of an implemented FPAT object. An implementation of a FPAT-object is FPAT-Live if:

1. 1.

   All transfer and balance operations terminate for correct users.

2. 2.

   Consider a correct user $u$. For each operation ${\text{transfer}}_{\ast }(\ast ,u)$ completed during the execution at time $t$, there exists a time $t^{\prime }\ge t$ such that any operation balance inserted at time $t^{\prime \prime }\ge t^{\prime }$ will return a value $v$ such that:

   $$v\ge \sum _{\begin{array}{c}{\text{transfer}}_{\ast }(v_{+},u)\\ \text{invoked by correct users}\\ \text{completed before time }t\end{array}}{v}_{+}-\sum _{\begin{array}{c}{\text{transfer}}_u(v_{-},\ast )\\ \text{completed before time }{t}^{\prime \prime }\end{array}}{v}_{-}$$

We capture the privacy guarantees of FPAT through a distinguishing game ${𝒢}^{priv}$ described in details the full version of the paper. FPAT-privacy has important implications that can be expressed as a collection of properties we use here. Let $ϵ$ be a negligible function and $\lambda$ the security parameter. Consider a protocol execution, let $H$ be its history and ${𝒰}_{Byz}$ the set of users controlled by the adversary, among the $U$ users of the system. Let $o={\text{transfer}}_u(v,w)\in H$ be any transfer operation such that $u$ is honest. Then for each guess $(u^{\prime },v^{\prime },w^{\prime })$ made by an adversary with no prior knowledge, where $u^{\prime }$ is the payment sender, $v^{\prime }$ is the value, and $w^{\prime }$ is the payment recipient, the following properties hold:

1. 1.

   Sender-anonymity: $\mathrm{\mathbb{P}}(u^{\prime }=u)\le \frac{1}{U-|{𝒰}_{Byz}|}+ϵ(\lambda )$, i.e., the adversary only knows that the sender is not itself.

2. 2.

   Receiver-anonymity: If $w$ is honest, then $\mathrm{\mathbb{P}}(w^{\prime }=w)\le \frac{1}{U-|{𝒰}_{Byz}|}+ϵ(\lambda )$, i.e., the adversary only knows that the receiver is not itself.

3. 3.

   Confidentiality: If $w$ is honest, then $\mathrm{\mathbb{P}}(v^{\prime }=v)\le ϵ(\lambda )$, i.e.,the adversary cannot guess the amount of the transaction.

These three properties together constitute full privacy. Additionally, FPAT-privacy, as captured by the distinguishing game ${𝒢}^{priv}$, implies unlinkability: given two transfers, no adversary can determine whether the sender, receiver, or amount is the same in both transfers.

Every user is identified by her public address $apk$ that is derived from a secret address $ask$ as follows: $apk=PR{F}_{ask}(0)$ ⁴⁴4The address generation is detailed in [11] and shows the address generation process by sampling a random $ask$ and deriving the $apk$.

The protocol uses a ($2f+1$, $N$)-threshold blind signature scheme, as defined in Section 3.3. The secret signing keys ${[s{k}_i]}_{i=1}^N$ are held by each of the validators. The aggregated public key is denoted by $p{k}_{agg}$ The protocol will also make use of NIZK, as defined in Section 3.3. The setup algorithms for these primitives are again described in [11].

A coin is a tuple $\text{c}=(v,apk,\rho )$ with:

• $\mathrm{■}$

  $v$ the (integer) value of the coin.

• $\mathrm{■}$

  $apk$ the public address of the owner of the coin.

• $\mathrm{■}$

  $\rho$ the seed of the coin, from which the serial number is derived.

Coins are similar to unspent transactions (UTXO) in Bitcoin: to make a payment, a user “spends” old coins and creates new coins whose owners are the payment recipients.

Using a quorum of validators signatures (inspired by Byzantine Consistent Broadcast), we decide whether a coin is valid or not. In concrete terms, a coin is valid if it has been signed by $2f+1$ validators. During a transfer, several old coins ${[{\text{c}}_i^{old}]}_{i\in [1,n]}$ are spent to create new coins ${[{\text{c}}_j^{new}]}_{j\in [1,m]}$. To make sure that a coin it not spent twice, a unique serial number is derived from the coin’s seed $\rho$ as $sn={\text{PRF}}_{ask}(\rho )$. Each validator maintains a list snList of the old coins’ serial numbers. The coins ${[{\text{c}}_i^{old}]}_{i\in [1,n]}$ are considered spent when a quorum of $2f+1$ validators have appended the corresponding serial numbers ${[s{n}_i^{old}]}_{i\in [1,n]}$ to their snList.

Intuitively, as the computation of $s{n}_i^{old}$ is using the PRF and the secret address of the payer, no party can link $s{n}_i^{old}$ to ${\rho }_i^{old}$ or $ap{k}_i^{old}$, and thus the sender-anonymity property is preserved. The full version of the paper details an algorithm that initializes the balances for the initial set of users, by creating coins for each of them.⁵⁵5As discussed in Section 8, depending on the use cases of the system, this algorithm might not be executed. Instead, users might freely join the system and call a Mint algorithm that provides them with new coins.

User storage consists of:

• $\mathrm{■}$

  $apk/ask$: its public/secret address pair

• $\mathrm{■}$

  $\mathrm{𝖼𝗈𝗂𝗇𝖫𝗂𝗌𝗍}={[({\text{c}}_i,{\sigma }_i)]}_i$: the set of coins owned by the user associated with the aggregated signature of each coin.

• $\mathrm{■}$

  $\mathrm{𝗋𝗁𝗈𝖫𝗂𝗌𝗍}$: the list of all seed $\rho$ corresponding to coins received by the user

Validator storage consists of:

• $\mathrm{■}$

  $sk$: its secret signing key

• $\mathrm{■}$

  $\mathrm{𝗌𝗇𝖫𝗂𝗌𝗍}$: the list of serial numbers identifying spent coins.

• $\mathrm{■}$

  $\mathrm{𝗌𝗂𝗀𝗇𝖾𝖽𝖢𝗈𝗂𝗇𝖫𝗂𝗌𝗍}$: the list of all blinded coins signed by the replica.

Assuming a user has enough funds, she can issue payments to several recipients ${[ap{k}_j^{new}]}_{j=1}^m$ in one transfer by sending $v_j^{new}$ to $ap{k}_j^{new}$. The full algorithm is described in [11]. The user first chooses $n$ (old) coins denoted ${[{𝐜}_i^{old}]}_{i=1}^n$ and their signatures ${[{\sigma }_i^{old}]}_{i=1}^n$ from her $\mathrm{𝖼𝗈𝗂𝗇𝖫𝗂𝗌𝗍}$, where ${𝐜}_i^{old}=(v_i^{old},ap{k}_i^{old},{\rho }_i^{old})$, such that the total value of the old coins does not fall below the total value payed in the transfer: ${\sum }_{i=1}^n{v}_i^{old}\ge {\sum }_{j=1}^m{v}_j^{new}$. (Otherwise, the transfer operation returns fail.) The user then computes the serial number ${[s{n}_i^{old}]}_{i=1}^n$ of every old coin as follows: $s{n}_i^{old}={\mathrm{𝖯𝖱𝖥}}_{as{k}_i^{old}}({\rho }_i^{old})$.

The $j$ new coins are then produced by the user according to the values and addresses to pay: $\forall j\in [1,m]$, ${𝐜}_j^{new}=(v_j^{new},ap{k}_j^{new},{\rho }_j^{new})$. ${\rho }_j^{new}$ is derived as ${\rho }_j^{new}={\mathrm{𝖯𝖱𝖥}}_{{\rho }_{seed}}(s{n}_1^{old}||\mathrm{\dots }||s{n}_n^{old}||j)$ , where ${\rho }_{seed}$ is sampled randomly. This binds each new coin to the old coins spent for its creation. This way, we make sure that the validators signing ${𝐜}^{new}$ mark the same old coins as spent. Since the value of the chosen old coins might exceed the value of the new coins, the user also produces a redeem coin ${𝐜}_{m+1}^{new}=(v_{m+1}^{new},ap{k}_{m+1}^{new},{\rho }_{m+1}^{new})$, with $ap{k}_{m+1}^{new}=apk$ and $v_{m+1}^{new}$ the exceeding value. The coins ${[{𝐜}_j^{new}]}_{j=1}^{m+1}$ are then blinded. The blinding of ${𝐜}_j^{new}$ is denoted ${\widetilde{𝐜}}_j^{new}=\mathrm{𝖡𝖫𝖨𝖭𝖣}({𝐜}_j^{new},b_j)$, where $b_j$ is a randomly sampled blinding factor.
The sender of the payment then computes an NIZK with:

• $\mathrm{■}$

  public_input : $({[s{n}_i^{old}]}_{i=1}^n,{[{\widetilde{𝐜}}_j^{new}]}_{j=1}^{m+1})$

• $\mathrm{■}$

  private_input : $({[{\text{c}}_i^{old}]}_{i=1}^n,{[{\sigma }_i^{old}]}_{i=1}^n,{[as{k}_i^{old}]}_{i=1}^n,{[{\text{c}}_j^{new}]}_{j=1}^{m+1},$ ${[b_j]}_{j=1}^{m+1},$ ${\rho }_{seed})$

This NIZK ${\pi }_{transfer}$ proves the following relations:

1. 1.

   Serial numbers ${[s{n}_i^{old}]}_{i=1}^n$ are correctly derived from the old coins ${[{\text{c}}_i^{old}]}_{i=1}^n$.

2. 2.

   New coins ${[{\text{c}}_j^{new}]}_{j=1}^{m+1}$ are correctly derived from the old coins ${[{\text{c}}_i^{old}]}_{i=1}^n$.

3. 3.

   Blinded coins ${[{\widetilde{𝐜}}_j^{new}]}_{j=1}^{m+1}$ are correctly derived from ${[{\text{c}}_j^{new}]}_{j=1}^{m+1}$ and ${[b_j]}_{j=1}^{m+1}$.

4. 4.

   Signatures ${[{\sigma }_i^{old}]}_{i=1}^n$ of the coin ${[{𝐜}_i^{old}]}_{i=1}^n$ are correct.

5. 5.

   Private addresses ${[as{k}_i^{old}]}_{i=1}^n$ match the public address ${[ap{k}_i^{old}]}_{i=1}^n$.

6. 6.

   The sum of the values of the old coins ${[{\text{c}}_i^{old}]}_{i=1}^n$ equals the sum of the values of the new coins ${[{\text{c}}_j^{new}]}_{j=1}^{m+1}$.

The user can now send the NIZK ${\pi }_{transfer}$ along with the public inputs to all the validators. The detailed algorithm run by the validators is detailed in [11]. Once a validator receives the proof:

1. 1.

   It checks that none of the ${[s{n}_i^{old}]}_{i=1}^n$ appears in its snList;

2. 2.

   It checks that the proof $\pi$ is correct;

3. 3.

   If the last two conditions are fulfilled, it adds all ${[s{n}_i^{old}]}_{i=1}^n$ to snList, add all ${[{\widetilde{𝐜}}_j^{new}]}_{j=1}^{m+1}$ to signedCoinList, it signs all the coins ${[{\widetilde{𝐜}}_j^{new}]}_{j=1}^{m+1}$ and returns the blinded partial signatures.

4. 4.

   If any of the previous conditions is not fulfilled, the validator checks if the blinded coins ${[{\widetilde{𝐜}}_j^{new}]}_{j=1}^{m+1}$ appear in signedCoinList. If they all do, then the validator still sends back the signatures. This is done because a Byzantine validator $p$ might receive a transfer request from a user $u$ and send it to other validators using a private channel. As a result, other validators might answer $p$ before answering $u$, preventing $u$ from receiving the signatures while the old coins are actually spent (their serial numbers would have been added to snList already).

Once the user receives $2f+1$ valid partial signatures for the coins ${[{\widetilde{𝐜}}_j^{new}]}_{j=1}^{m+1}$ from $2f+1$ validators, she can unblind and aggregate them to form $m+1$ signatures ${[{\sigma }_j]}_{j=1}^{m+1}$ that are valid signatures for ${[{𝐜}_j^{new}]}_{j=1}^{m+1}$. She can now send each couple $({𝐜}_j^{new},{\sigma }_j^{new})$ to $ap{k}_j^{new}$. The user $ap{k}_j^{new}$ only accepts the payment if ${\rho }_j^{new}\notin {\mathrm{𝗋𝗁𝗈𝖫𝗂𝗌𝗍}}_{ap{k}_j^{new}}$ and ${\mathrm{𝖵𝖤𝖱𝖨𝖥𝖸}}_{\mathrm{𝖲𝗂𝗀}}({𝐜}_j^{new},{\sigma }_j^{new},p{k}_{agg})==1$.⁶⁶6For convenience, we allow the Transfer algorithm to send money to several recipients in a single call, in contrast with the specification, which allows only one recipient at a time. As explained in the security proof in [11], this more generic transfer can be seen as a batch of successive transfer calls, each destined to a single user.

Consider a coin ${𝐜}^{\text{old}}$ that has been spent. Hence, a set ${𝒱}_1$ of $2f+1$ validators have claimed to have added $s{n}^{\text{old}}$ to their snList, and at least $f+1$ out of them are correct. If a Byzantine user tries to spend ${𝐜}^{\mathrm{𝐨𝐥𝐝}}$ again, it should collect confirmations from a set ${𝒱}_2$ of $2f+1$ validators that will have to add $s{n}^{\text{old}}$ in their snList again. Since there are $3f+1$ validators in total, ${𝒱}_1$ and ${𝒱}_2$ have at least one correct validator in common. It must refuse to sign the second transaction because $s{n}^{\text{old}}$ is already in its snList, so double spending is prevented and FPAT-Safety is guaranteed. The full proof is presented in [11].

Figure 1 depicts a transfer:

1. 1.

   Alice wants to pay $3$ recipients with $2$ coins. She generates 3 blinded coins and a matching NIZK, and sends them to the validators.

2. 2.

   Each validator checks the validity of the NIZK and that the old coins are not in its snList, and, if so, sign the blinded coins and add the serial numbers to their snList.

3. 3.

   Alice receives the signatures.

4. 4.

   For each coin: once $2f+1$ blinded partial signatures are received, Alice unblinds and then aggregates them into one aggregated signature.

5. 5.

   Alice sends the coin tuples and their signatures to their recipients.

The compliance coin of a user $u$ is defined as a tuple $c{c}_u=(apk,\rho ,v,com)$ where:

• $\mathrm{■}$

  $apk$ is $u$’s sole public address

• $\mathrm{■}$

  $\rho$ the coin seed, as for a normal coin

• $\mathrm{■}$

  $v$ is the total amount of money sent so far by $u$

• $\mathrm{■}$

  $com$ is the commitment to the list of all the transfer done by $u$ so far. For each coin created, it commits the tuple $(apk,v)$ with $apk$ the public key of the receiver and $v$ the value sent. It uses the incremental commitment introduced in Section 3.3

$com$ allows to trace $u$’s activities and allows $u$ to prove additional statements on her transaction history in case of an update of the regulation.

Adding a user registration process is essential for regulatory enforcement, to comply with the know-your-customer (KYC) and customer-due-diligence (CDD) checks. Additionally, it ensures the uniqueness of the compliance coin for each physical user.

To this end, the validator storage is provided with a new list $\mathrm{𝗋𝖾𝗀𝗂𝗌𝗍𝖾𝗋𝖾𝖽𝖫𝗂𝗌𝗍}$, the list of the enrolled users associated with their public key. $\mathrm{𝗋𝖾𝗀𝗂𝗌𝗍𝖾𝗋𝖾𝖽𝖫𝗂𝗌𝗍}$ is used to make sure that a physical user can only register once on the system. The registration process is as follows for the user $u$:

1. 1.

   Generate a random $\rho$ and computes $c{c}_u=(ap{k}_u,\rho ,0,0)$ and its blinding ${\widetilde{cc}}_u$ (with blinding factor $b$).

2. 2.

   Computes an NIZK ${\pi }_{register}$ that takes (${\widetilde{cc}}_u$, $ap{k}_u$) as public input and ($as{k}_u,c{c}_u,b$) as private input. It proves that:

   1. (a)

      ${\widetilde{cc}}_u=\mathrm{𝖡𝖫𝖨𝖭𝖣}((ap{k}_u,\rho ,0,0),b)$.

   2. (b)

      $as{k}_u$ and $ap{k}_u$ form a correct secret/public address pair.

3. 3.

   Send to each validator ${\pi }_{register}$ and $({\widetilde{cc}}_u,ap{k}_u)$.

4. 4.

   Upon correct KYC and CDD proving $u$’s identity, each validator check if ${\pi }_{register}$ is correct and that: $(u,\ast )\notin \mathrm{𝗋𝖾𝗀𝗂𝗌𝗍𝖾𝗋𝖾𝖽𝖫𝗂𝗌𝗍}$ ($u$ has registered no public address yet). If so, they sign ${\widetilde{cc}}_u$, send it back to $u$, and add $(u,ap{k}_u)$ to $\mathrm{𝗋𝖾𝗀𝗂𝗌𝗍𝖾𝗋𝖾𝖽𝖫𝗂𝗌𝗍}$.

5. 5.

   Once $u$ has received $2f+1$ partial signature, she can unblind and aggregates the partial signatures to form a valid signature for $c{c}_u$.

The detailed algorithm is described in [11].

Section 5 described how a transfer is handled by a user $u$, by spending $n$ old coins ${[{𝐜}_i^{old}]}_{i=1}^n$ and creating $m+1$ new coins ${[{\widetilde{𝐜}}_j^{new}]}_{j=1}^{m+1}$ to pay $m$ recipients ($m$ coins are created to pay the recipient and a redeem coin is also created with index $m+1$ to get the excess of money back to $u$). Now the user also has to update a compliance coin at each payment and prove that their transfer is compliant. The following additional steps are thus required. She generates $m$ random values: ${[r_j]}_{j=1}^m$. The user provides an additional proof ${\pi }_{comply}$. This proof takes the following public inputs:

• $\mathrm{■}$

  ${\widetilde{cc}}_u^{new}$ the blinding of the new compliance coin

• $\mathrm{■}$

  $s{n}_{cc}^{old}$ the serial number of the old compliance

• $\mathrm{■}$

  $V_{sent}^{max}$ the maximum amount that can be transferred in one transfer

• $\mathrm{■}$

  $V_{total}^{max}$ the total amount of money that $u$ can transfer in her use of the system

• $\mathrm{■}$

  $SancList$ the list of addresses under sanctions

${\pi }_{comply}$ takes the following as private input:

• $\mathrm{■}$

  $c{c}^{old}=(ap{k}_{cc}^{old},{\rho }_{cc}^{old},v_{cc}^{old},co{m}^{old})$ the old compliance coin

• $\mathrm{■}$

  $c{c}^{new}=(ap{k}_{cc}^{new},{\rho }_{cc}^{new},v_{cc}^{new},co{m}^{new})$ the new compliance coin

• $\mathrm{■}$

  $as{k}_{cc}^{old}$ the secret address corresponding to $ap{k}_{cc}^{old}$

${\pi }_{comply}$ should verify the following clauses:

1. 1.

   $\forall i\in [1,n],ap{k}_i^{old}=ap{k}_{cc}^{old}$

2. 2.

   $ap{k}_{cc}^{old}={\mathrm{𝖯𝖱𝖥}}_{as{k}_{cc}^{old}}(0)$

3. 3.

   $ap{k}_{m+1}^{new}=ap{k}_{cc}^{old}$

4. 4.

   $ap{k}_{cc}^{new}=ap{k}_{cc}^{old}$

5. 5.

   ${\rho }_{cc}^{new}={\mathrm{𝖯𝖱𝖥}}_{{\rho }_{seed}}(s{n}_1^{old}||\mathrm{\dots }||s{n}_n^{old}||m+2)$

6. 6.

   $v_{cc}^{new}=v_{cc}^{old}+{\sum }_{1\le j\le m}{v}_j^{new}$

7. 7.

   $co{m}_0=co{m}^{old}$ $\wedge \forall j\in [1,m],co{m}_j=\mathrm{𝖨𝖭𝖢𝖱}(co{m}_{j-1},ap{k}_j^{new},v_j^{new},r_j)$ $\wedge co{m}^{new}=co{m}_m$

8. 8.

   ${\sum }_{1\le j\le m}{v}_j^{new}\le V_{sent}^{max}$

9. 9.

   $v_{cc}^{new}\le V_{total}^{max}$

10. 10.

    $ap{k}_{cc}^{old}\notin SancList$

11. 11.

    $\forall j\in [1,m],ap{k}_j^{new}\notin SancList$

Conditions (1) ensures that all the input coins belong to the owner of the input compliance coin. Condition (2) ensures that $u$, the user that invokes transfer, is the owner of the compliance coin. Condition (3) ensures that the redeem coin will belong to $u$. Conditions (4), (5), (6) and (7) ensure that the new compliance coin is well-formed. Condition (8), (9) and (10) ensure that the transfer is compliant. (8) verifies that the amount of the transfer does not exceed that maximum allowed for a single transfer. (9) verifies that the total amount of money sent by $u$ does not exceed that maximum amount. (10) verifies that the sender is not a user under sanctions. (11) verifies that none of the receivers of the transfer is under sanction.

The user storage is also augmented with a list $\mathrm{𝖼𝗈𝗆𝖫𝗂𝗌𝗍}$, in which she stores the tuples $(apk,v,r)$ that she has used at each transfer. At the end of the transfer described above, she thus append to $\mathrm{𝖼𝗈𝗆𝖫𝗂𝗌𝗍}$ the following: $\forall j,j\in [1,m],(ap{k}_j^{new},v_j^{new},r_j)$. She can later use $\mathrm{𝖼𝗈𝗆𝖫𝗂𝗌𝗍}$ and her compliance coin to prove any statement about her transaction.

Upon receiving correct proofs (${\pi }_{comply},{\pi }_{transfer}$) and their public parameters, the validators execute the same algorithm as for a non regulated transfer, except that they verify both ${\pi }_{comply}$ and ${\pi }_{transfer}$. They can then sign the news coins and then send the signature back. The detailed algorithm is described in [11].