b-bits integers. We can now delete **q** and **r**. We finally have obtained the space-efficient construction $\langle x, \ell \rangle$ composed of $2kb_1 = 2 \log_2(b)^{s_1}$ bits. While we cannot extract elements of **a** from this representation anymore (this would require storing the quotients), we can still use it to test if an element $e_i$ was used to construct $\langle x, \ell \rangle$ by verifying if $\ell_i | \ell$ and $x \equiv e_i \mod \ell_i$. However, we remark that if an element $a_i \equiv e_i \mod \ell_i$ was stored inside **a**, then one would obtain a false positive for $e_i$. Thus, to achieve statistical soundness (collision resistance), we require the use of a secure hash function to attribute to each element its index and, thus, its prime divisor. This renders negligible the probability of attributing the same index $i$ to two elements congruent modulo $\ell_i$. In the next section, we show how to compute proofs of an element's membership and non-membership in zero knowledge.

**Accumulator (non)-membership proofs.** Let us consider a generic group of unknown order $\mathbb{G}$ with generators $g_1, g_2$. We define our accumulator as $A = \langle g_1^x, g_2^\ell \rangle \in \mathbb{G}^2$ with secret parameters $sp = \langle x, \ell \rangle$ stored by the accumulator manager (AM). Notice that the public representation of $A$ (the digest) is of constant size. Furthermore, it is not possible to retrieve $sp$ from $A$ under the DL assumption (Assumption 2). We base our (non-)membership proofs on the proof of knowledge of representation (Algorithm 4) of Boneh et al. [7], which we slightly modify to prove the knowledge of a Chinese remainder. We then render it non-interactive using the Fiat-Shamir heuristic [20]. The resulting non-interactive proof of knowledge of Chinese remainder (NIPoKCR) can then be used by the AM to prove membership of an element $e$, i.e., if $x$ was computed using $e$. Algorithm 5 details briefly the operations performed by the prover and verifier of a NIPoKCR execution. To prove non-membership, we additionally provide a proof of knowledge of “non-Chinese remainder” (Algorithm 6) that proves that for an element $e$ and prime $\ell_e, x \not\equiv e \mod \ell_e \lor \ell_e \nmid \ell$. This second proof uses a range proof to convince that the remainder of the integer division of $x$ by $\ell_e$ is in interval $[0, \ell_e - 1]$. While we do not provide an algorithm for the range proof, many compatible solutions are in the literature [13].

**Empty accumulator.** During setup, the AM samples random initial secret parameters $sp_0 = \langle x_0, \ell_0 \rangle \stackrel{\$}{\leftarrow} \mathbb{Z}^+ \times \text{Primes}(b_1 + 1, b)$. The AM then computes the value of its empty accumulator $A_0 = \langle g_1^{x_0}, g_2^{\ell_0} \rangle$ and appends it to its public parameters. Note that $\ell_0$ is sampled outside of $\text{Primes}(b_2, b_1)$ to avoid any collision with further accumulated elements. This randomness is necessary to prevent any PPT adversary from being able to compute the accumulator even if it collects the set of accumulated elements $S \setminus \{x_0\}$.

**Algorithm 4** Proof of Knowledge of Representation (PoKRep) [7].

1. **params:** $\mathbb{G} \stackrel{\$}{\leftarrow} \text{GGen}(\lambda)$; $(g_1, \dots, g_n) \in \mathbb{G}^n$;

2. **inputs:** $w \in \mathbb{G}$;

3. **witness:** $x \in \mathbb{Z}^n$;

4. **claim:** $\text{Rep}(x) = \prod_{i=1}^n g_i^{x_i} = w$;

5. Verifier sends $\ell \stackrel{\$}{\leftarrow} \text{Primes}(2, \lambda)$;

6. For each $x_i$, Prover finds $q_i, r_i$ s.t. $x_i = q_i\ell + r_i$, sets $\mathbf{q} \leftarrow \langle q_1, \dots, q_n \rangle \in \mathbb{Z}^n$ and $\mathbf{r} \leftarrow \langle r_1, \dots, r_n \rangle \in [\ell]^n$; Prover sends $Q \leftarrow \prod_{i=1}^n g_i^{q_i}$ and $\mathbf{r}$ to Verifier;

7. Verifier accepts if $\mathbf{r} \in [\ell]^n$ and $Q^\ell \text{Rep}(r) = w$.
Proof. Consider $b_i = \text{balance}_i() / v \in S_i$ a balance operation performed by a correct process $p_i$ that returns a value $v$. Define the sets $I_i$ and $R_i$ as follows:

* $I_i$ is the set of transfers invoked locally by $p_i$ before $p_i$ executed $b_i$. By construction of Algorithm 3, $p_i$ generated a sending UA at line 38 for each of these transfers.

* $R_i$ is the set of transfers received by $p_i$ whose receiving UA was generated by $p_i$ (at line 38) before invoking $b_i$.

Because $p_i$ is correct, it executes Algorithm 3, which ensures by construction (in particular due to lines 23, 35 and 45) that

$$v = \text{total}(i, I_i \cup R_i), \qquad (5)$$

taking into account that the effects of null transfers on $i$ cancel out in the definition of total.

Consider now $T_{i\triangleright}$ the subset of transfers present in $S_i$ that $p_i$ issued, and $T_{\triangleright i}$ the subset of transfers present in $S_i$ that $p_i$ received, i.e.,

$$T_{i\triangleright} \stackrel{\text{def}}{=} \{\text{transfer}_i(\star, k) \in S_i \mid i \neq k\}, \qquad (6)$$

$$T_{\triangleright i} \stackrel{\text{def}}{=} \{\text{transfer}_k(\star, i) \in S_i \mid i \neq k\}. \qquad (7)$$

By definition of total(·, ·), we have similarly

$$\text{total}(i, \{o \in S_i \mid o \to_{S_i} b_i\}) = \text{total}(i, \{o \in S_i \mid o \to_{S_i} b_i\} \cap (T_{i\triangleright} \cup T_{\triangleright i})). \qquad (8)$$

Because $p_i$'s local process order is included in $\sim_{i}$, it is also included in $\to_{S_i}$. As a result, the transfers invoked by $p_i$ before invoking $b_i$ are exactly those transfers that precedes $b_i$ in $\to_{S_i}$,

$$\{o \in S_i \mid o \to_{S_i} b_i\} \cap T_{i\triangleright} = I_i.$$

Furthermore, due to the rule *Ordering of incoming transfers* of $\sim_{i}$ and the definition of $\sim_{i}$, $b_i$ is totally ordered w.r.t. to the transfers received by $p_i$ in $\sim_{i}$ and therefore in $\to_{S_i}$. As a result, we have

$$\{o \in S_i \mid o \to_{S_i} b_i\} \cap T_{\triangleright i} = R_i.$$

These last two equalities together with Equations (5) and (8) yield the lemma.<fnref n="15" />

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

**Lemma B.22.** $\forall j \in [0..n], \forall t_{j\triangleright} = \text{transfer}_j(v, \star) \in S_i : v \le \text{total}(j, \{o \in S_i \mid o \to_{S_i} t_{j\triangleright}\})$.

*Proof.* Consider a process $p_j$ (correct or faulty) and $t_{j\triangleright} = \text{transfer}_j(v, \star) \in S_i$ a transfer invocation from $j$ that is present $S_i$ of amount $v$ to some process.

Let us define the sets $I_{t_{j\triangleright}}^{S_i}$ and $R_{t_{j\triangleright}}^{S_i}$ as follows.

* $I_{t_{j\triangleright}}^{S_i}$ is the set of transfers whose sender is $p_j$ that appear before $t_{j\triangleright}$ in sequence $S_i$ and includes $t_{j\triangleright}$,

$$I_{t_{j\triangleright}}^{S_i} = \{\text{transfer}_j^*(\star, \star) \in S_i \mid \text{transfer}_j^*(\star, \star) \to_{S_i} t_{j\triangleright} \lor \text{transfer}_j^*(\star, \star) = t_{j\triangleright}\}.$$

* $R_{t_{j\triangleright}}^{S_i}$ is the set of transfers whose receiver is $p_j$ that appear before $t_{j\triangleright}$ in sequence $S_i$.

$$R_{t_{j\triangleright}}^{S_i} = \{\text{transfer}_j^*(j, \star) \in S_i \mid \text{transfer}_j^*(j, \star) \to_{S_i} t_{j\triangleright}\}. \qquad (9)$$

**Remark B.22.1.** $\text{total}(j, I_{t_{j\triangleright}}^{S_i} \cup R_{t_{j\triangleright}}^{S_i}) = \text{total}(j, \{o \in S_i \mid o \to_{S_i} t_{j\triangleright}\}) - v$.

<footnote n="15">¹⁵Let us recall that, given 3 sets A, B, and C, we always have $(A \cap B) \cup (A \cap C) = A \cap (B \cup C)$.</footnote>
**Algorithm 5** Non-Interactive Proof of Knowledge of Chinese Remainder (NIPoKCR).

1 params: $G \stackrel{s}{\leftarrow} GGen(\lambda); \langle g_1, g_2 \rangle \in G$;

2 inputs: $e \in \mathbb{Z}$; $X \leftarrow g_1^x \in G$; $L \leftarrow g_2^\ell \in G$; $\ell_e \leftarrow H_{\text{Primes}}(H(e)) \in \text{Primes}(s_1, s_2)$;

3 witness: $x \in \mathbb{Z}$; $\ell \in G$;

4 claim: $x \equiv e \mod \ell_e \wedge \ell_e \mid \ell$.

5 Prover computes $q_e, r_e$ and $q_x, r_x$ s.t. $e = q_e \ell_e + r_e$ and $x = q_x \ell_e + r_x$; Prover computes $q_\ell$ s.t. $\ell = \ell_e q_\ell$; Prover sends $Q_1 \leftarrow g_1^{q_x} g_2^{q_e}$ and $Q_2 \leftarrow g_2^{q_\ell}$ to Verifier;

6 Verifier computes $r_e = e \mod \ell_e$ and accepts if $Q_1^{\ell_e} (g_1 g_2)^{r_e} = X g_2^e \wedge Q_2^{\ell_e} = L$.

**Algorithm 6** Non-Interactive Proof of Knowledge of Non-Chinese Remainder (NIPoKNCR).

1 params: $G \stackrel{s}{\leftarrow} GGen(\lambda); \langle g_1, g_2 \rangle \in G$;

2 inputs: $e \in \mathbb{Z}$; $X \leftarrow g_1^x \in G$; $L \leftarrow g_2^\ell \in G$; $\ell_e \leftarrow H_{\text{Primes}}(H(e)) \in \text{Primes}(s_1, s_2)$;

3 witness: $x \in \mathbb{Z}$; $\ell \in G$;

4 claim: $x \not\equiv e \mod \ell_e \vee \ell_e \nmid \ell$.

5 If $\ell_e \nmid \ell$, then Prover computes the Bezout coefficient $a, b$ s.t. $a\ell + b\ell_e = 1$ and sends $a$ and $B = g_2^b$;

6 Else Prover determines $q_e, r_e$ and $q_x, r_x$ s.t. $e = q_e \ell_e + r_e$ and $x = q_x \ell_e + r_x$, then computes $Q_x = g_1^{q_x}, R_x = g_2^{r_x}, Q_e = g_2^{q_e}$ and a range proof $\pi$ for $R_x$ proving that $r_x \in [\ell_e]$ and sends $Q_x, R_x, Q_e$ and $\pi$ to Verifier;

7 Verifier accepts if $L^a B^{\ell_e} = g_2$ or computes $r_e = e \mod \ell_e$ and accepts if $\pi$ is a valid range proof for $R_x$ and $X g_2^e = Q_x^{\ell_e} R_x Q_e^{\ell_e} + g_2^{r_e} \wedge R_x \not= g_1^{r_e}$.

### B.1.3 Security proofs

In the following, we consider an accumulator $A = \langle g_1^x, g_2^\ell \rangle$ with public parameters $pp = \langle G, g_1, g_2, H_{\text{Primes}}, A_0 \rangle$ and secret parameters $sp = \langle x, \ell \rangle$.

**Lemma 7 (UA-cfw-Indistinguishability [17]).** Let $S_1 \leftarrow S \setminus \{v_0\}$ be the set of accumulated elements in $A$ without the random initial value $v_0$. $A$ is said to be collision-freeness-weakening (cfw) indistinguishable if for any PPT adversary Adv with knowledge of $S_1$ and alternative element set $S_2$, Adv cannot decide with probability better than $\frac{1}{2} + \epsilon(\lambda)$ whether $S_1$ or $S_2$ is accumulated in $A$. Adv has access to oracles $\vartheta$, which it can query with element $x_i$ to execute addition for $x_i \notin S_1 \cup S_2$, deletion for $x_i \in S_1 \cap S_2$, obtain membership proofs for $x_i \in S_1 \cap S_2$ and non-membership proofs for $x_i \notin S_1 \cup S_2$.

**Proof.** Let $sp = \langle x, \ell \rangle$ be the secret parameters of $A = \langle g_1^x, g_2^\ell \rangle$. First, we recall that neither $x$ nor $\ell$ can directly be computed from $A$ under the DL assumption (Assumption 2). However, Adv may attempt to reconstruct $A$ from $S_1$ and $S_2$. Let $A_1$ and $A_2$ be the accumulators constructed from $S_1$ and $S_2$ by Adv using the same public parameters. Recall that $A$ was seeded with an additional random non-zero integer $v_0$ and random large prime $\ell_0$ at setup, which the adversary cannot retrieve from the public parameters. Thus, $A \neq A_1$ and the probability that Adv guesses $v_0$ and $\ell_0$ at random is negligible. Finally, Adv may try to obtain more information about $sp$ through queries to $\vartheta$. Suppose Adv queries $\vartheta$ to perform the addition of $x_i \notin S_1 \cup S_2$. Then Adv would only obtain a new version of $A$, which is still secure under the DL assumption. The same case applies to element deletion. Suppose Adv tasks $\vartheta$ with producing a membership proof for some element $x_i \in S_1 \cap S_2$. We see in the NIPoKCR protocol (Algorithm 5) that Adv obtains $Q_1 \leftarrow g_1^{q_x} g_2^{q_e}$ and $Q_2 \leftarrow g_2^{q_\ell}$, which do not leak any data on $sp$. Similarly, if Adv tasks $\vartheta$ with producing a non-membership proof for
Proof. This directly follows from the definition of total(·, ·), $I_{t_{j\triangleright}}^{S_i}$ and $R_{t_{j\triangleright}}^{S_i}$. □

Consider $SN_{t_{j\triangleright}}^{S_i}$ the set of the sequence numbers of the transfers present in $I_{t_{j\triangleright}}^{S_i}$, i.e.,

$$SN_{t_{j\triangleright}}^{S_i} = \{sn \in \mathbb{N}^* | \text{transfer}_j^{sn}(\star, \star) \in I_{t_{j\triangleright}}^{S_i}\}. \qquad (10)$$

Because $t_{j\triangleright} \in I_{t_{j\triangleright}}^{S_i}$, $SN_{t_{j\triangleright}}^{S_i}$ contains the sequence number of $t_{j\triangleright}$. However, because $\rightsquigarrow_i$ does not impose strong constraints on the order of the transfer invocations issued by a process other than $p_i$, $I_{t_{j\triangleright}}^{S_i}$ might also contain transfer invocations that have a higher sequence number than $t_{j\triangleright}$. Furthermore, note that, by construction, $SN_{t_{j\triangleright}}^{S_i}$ only contains sequence numbers of transfers whose sender is $p_j$.

Define $sn_{t_{j\triangleright}}^{\max}$ as the highest sequence number contained in $SN_{t_{j\triangleright}}^{S_i}$,

$$sn_{t_{j\triangleright}}^{\max} = \max(SN_{t_{j\triangleright}}^{S_i}), \qquad (11)$$

and $A_{t_{j\triangleright}}^{\max}$ as the UA issued by $j$ with the sequence number $sn_{t_{j\triangleright}}^{\max}$, i.e., $A_{t_{j\triangleright}}^{\max} = A_j^{sn_{t_{j\triangleright}}^{\max}}$. (By AP-Agreement, this UA is unique.)

Consider $\Sigma_{t_{j\triangleright}}^{\max}$ the set of UAs issued by $p_j$ that precede $A_{t_{j\triangleright}}^{\max}$ according to the predicates $P_A$ and $P_{ZK}$ (Lemma B.3),

$$\Sigma_{t_{j\triangleright}}^{\max} = \text{set}(\text{precedingUAs}(A_{t_{j\triangleright}}^{\max})). \qquad (12)$$

Based on $\Sigma_{t_{j\triangleright}}^{\max}$, let us define the sets $I_{t_{j\triangleright}}^{\max}$ and $R_{t_{j\triangleright}}^{\max}$ as follows.

* $I_{t_{j\triangleright}}^{\max}$ is the set of transfers whose sender is $p_j$ and whose sending UA appear in $\Sigma_{t_{j\triangleright}}^{\max}$,

$$I_{t_{j\triangleright}}^{\max} = \{\text{transfer}_j^*(\star, \star) | \text{sendingUA}(\text{transfer}_j^*(\star, \star)) \in \Sigma_{t_{j\triangleright}}^{\max}\}. \qquad (13)$$

* $R_{t_{j\triangleright}}^{\max}$ is the set of transfers whose receiver is $p_j$ and whose receiving UA appear in $\Sigma_{t_{j\triangleright}}^{\max}$, excluding the transfer invocation associated with $A_{t_{j\triangleright}}^{\max}$ in case it is a null UA (i.e., both a sending and receiving UA),

$$R_{t_{j\triangleright}}^{\max} = \left\{ \text{transfer}_{\star}^{*}(j, \star) \mid \begin{array}{l} \text{receivingUA}(\text{transfer}_{\star}^{*}(j, \star)) \in \Sigma_{t_{j\triangleright}}^{\max} \wedge \\ \text{transfer}_{\star}^{*}(j, \star) \neq \text{transfer}(A_{t_{j\triangleright}}^{\max}) \end{array} \right\}. \qquad (14)$$

Let $v_{\max}$ denote the amount of the transfer invocation $transfer(A_{t_{j\triangleright}}^{\max})$, i.e., $transfer(A_{t_{j\triangleright}}^{\max}) = transfer_{j}^{sn_{t_{j\triangleright}}^{\max}}(v_{\max}, \star)$. (The notation $transfer(A_{t_{j\triangleright}}^{\max})$ was defined at the end of Appendix B.1.1)

**Remark B.22.2.** total $(j, I_{t_{j\triangleright}}^{\max} \cup R_{t_{j\triangleright}}^{\max}) = total (j, (I_{t_{j\triangleright}}^{\max} \setminus \{transfer(A_{t_{j\triangleright}}^{\max})\}) \cup R_{t_{j\triangleright}}^{\max}) - v_{\max}.$

*Proof.* Similarly to Remark B.22.1, the remark follows from the fact that $transfer(A_{t_{j\triangleright}}^{\max}) \in I_{t_{j\triangleright}}^{\max}$ and $transfer(A_{t_{j\triangleright}}^{\max}) \notin R_{t_{j\triangleright}}^{\max}$, the definition of $v_{\max}$, and that of total(·, ·). □

**Remark B.22.3.** total $(j, (I_{t_{j\triangleright}}^{\max} \setminus \{transfer(A_{t_{j\triangleright}}^{\max})\}) \cup R_{t_{j\triangleright}}^{\max}) \geq v_{\max}.$

*Proof.* This follows from a recursion on the sequence of (valid) UAs precedingUAs($A_{t_{j\triangleright}}^{\max}$) that precede $A_{t_{j\triangleright}}^{\max}$ (Lemma B.3), as well as the checks and updates contained in the $P_{ZK}$ predicate (Algorithm 2). This includes the check at line 15 that a sending process must have enough funds, and the updates performed on the sender's balance at line 16 (for null UAs), line 17 (for non-null sending UAs), and line 19 (for non-null receiving UAs). □

**Remark B.22.4.** total $(j, I_{t_{j\triangleright}}^{\max} \cup R_{t_{j\triangleright}}^{\max}) \geq 0.$
<caption>■ Algorithm 7 Chinese-remainder-based accumulator with sublinear storage (CRASSe).</caption>

1 operation acc_setup(λ) is
2   $G = \langle G, A, B \rangle \leftarrow G\text{Gen}(\lambda)$;
3   $\langle g_1, g_2 \rangle \leftarrow O_1$;
4   Setup $H_{\text{Primes}}$ with prime domain Primes($b_2, b_1$);
5   $v_0, \ell_0 \stackrel{\$}{\leftarrow} \mathbb{Z}^+ \times \text{Primes}(b_1+1, b)$; ▷ Sample a random prime initial value
6   $sp \leftarrow \langle v_0, \ell_0 \rangle$;
7   $A_0 \leftarrow \langle g_1^{v_0}, g_2^{\ell_0} \rangle$;
8   $pp \leftarrow \langle G, g_1, g_2, H_{\text{Primes}}, A_0 \rangle$;
9   return $\langle pp, sp, A_0 \rangle$.
10 operation ua_add(pp, sp, A, v) is
11   if ua\_prove\_mem(pp, sp, A, v) ≠ abort then return A;
12   $\langle G, g_1, g_2, H_{\text{Primes}} \rangle \leftarrow pp$;
13   $\langle x, \ell \rangle \leftarrow sp$;
14   $\ell_v \leftarrow H_{\text{Primes}}(H(v))$;
15   Solve the CRT for $x' \equiv x \pmod \ell$ and $x' \equiv v \pmod \ell_v$;
16   $\ell' \leftarrow \ell \times \ell_v$;
17   $sp \leftarrow \langle x', \ell' \rangle$;
18   $A \leftarrow \langle g_1^{x'}, g_2^{\ell'} \rangle$;
19   return $\langle sp, A \rangle$.
20 operation ua_delete(pp, sp, A, v) is
21   if ua\_prove\_non\_mem(pp, sp, A, v) ≠ abort then return A;
22   $\langle G, g_1, g_2, H_{\text{Primes}} \rangle \leftarrow pp$;
23   $\langle x, \ell \rangle \leftarrow sp$;
24   $\ell_v \leftarrow H_{\text{Primes}}(H(v))$;
25   $\ell' \leftarrow \ell/\ell_v$;
26   $x' \leftarrow x \pmod \ell'$;
27   $sp \leftarrow \langle x', \ell' \rangle$;
28   $A \leftarrow \langle g_1^{x'}, g_2^{\ell'} \rangle$;
29   return $\langle sp, A \rangle$.
30 operation ua\_prove\_mem(pp, sp, A, v) is
31   return $\text{NIPoKCR}_{\text{prove}}(pp, sp, A, v)$.
32 operation ua\_prove\_non\_mem(pp, sp, A, v) is
33   return $\text{NIPoKNCR}_{\text{prove}}(pp, sp, A, v)$.
34 operation ua\_verify\_mem(pp, A, v, w) is
35   return $\text{NIPoKCR}_{\text{verify}}(pp, A, v, w)$.
36 operation ua\_verify\_non\_mem(pp, A, v, u) is
37   return $\text{NIPoKCR}_{\text{verify}}(pp, A, v, u)$.
Proof. This is a direct consequence of Remarks B.22.2 and B.22.3. □

**Remark B.22.5.** $I_{t_{j\triangleright}}^{S_i} \subseteq I_{t_{j\triangleright}}^{\max}$.

Proof. Consider $t'_{j\triangleright} = \text{transfer}_{j}^{sn'}(\star, \star) \in I_{t_{j\triangleright}}^{S_i}$, a transfer invocation whose sender is $p_j$ at sequence number $sn'$ that belongs to $I_{t_{j\triangleright}}^{S_i}$. By definition of $SN_{t_{j\triangleright}}^{S_i}$ and $sn_{t_{j\triangleright}}^{\max}$ (Equations (10) and (11)), we have

$$sn' \leq sn_{j\triangleright}^{\max}.$$

By AP-Agreement, this inequality yields $\text{sendingUA}(t'_{j\triangleright}) \in \text{set}(\text{precedingUAs}(A_{j\triangleright}^{\max}))$, and by definition of $\Sigma_{j\triangleright}^{\max}$ and $I_{t_{j\triangleright}}^{\max}$ (Equations (12) and (13)), that $t'_{j\triangleright} \in I_{t_{j\triangleright}}^{\max}$, proving the remark. □

**Remark B.22.6.** $R_{t_{j\triangleright}}^{\max} \subseteq R_{t_{j\triangleright}}^{S_i}$.

Proof. Consider $t'_{\triangleright j} = \text{transfer}_{\star}^{\star}(j, \star) \in R_{t_{j\triangleright}}^{\max}$, a transfer invocation whose receiver is $p_j$ that belongs to $R_{t_{j\triangleright}}^{\max}$. By definition of $\Sigma_{j\triangleright}^{\max}$ and $R_{t_{j\triangleright}}^{\max}$ (Equations (12) and (14)),

$$\text{receivingUA}(t'_{\triangleright j}) \in \text{set}(\text{precedingUAs}(A_{j\triangleright}^{\max})) \wedge t'_{\triangleright j} \neq \text{transfer}(A_{j\triangleright}^{\max}). \quad (15)$$

Furthermore, because $\text{transfer}(A_{j\triangleright}^{\max}) \in \mathcal{S}_i$, we have $t'_{\triangleright j} \in \mathcal{S}_i$ (either because the sender of $t_{\triangleright j}$ is correct, or by construction of $\Sigma$ if it is faulty, see Equations (3) and (4)). Remember that $A_{j\triangleright}^{\max}$ is associated with sequence number $sn_{j\triangleright}^{\max} \in SN_{t_{j\triangleright}}^{S_i}$ (Equation (11)). Because $SN_{t_{j\triangleright}}^{S_i}$ only contains the sequence numbers of transfers whose sender is $p_j$, $\text{transfer}(A_{j\triangleright}^{\max})$ must be some transfer $\text{transfer}_j^{sn_{j\triangleright}^{\max}}(\star, \star)$ sent from $p_j$. As a result, $t'_{\triangleright j} \in \mathcal{S}_i$ together with Equation (15) mean that the condition for the rule *Ordering of incoming transfers* in the definition of $\mathcal{S}_i$ is met, yielding $t'_{\triangleright j} \stackrel{1}{\rightleftharpoons} \text{transfer}(A_{j\triangleright}^{\max})$, and therefore $t'_{\triangleright j} \stackrel{1}{\rightleftharpoons} \text{transfer}(A_{j\triangleright}^{\max})$, and

$$t'_{\triangleright j} \rightarrow_{S_i} \text{transfer}(A_{j\triangleright}^{\max}). \quad (16)$$

Because $\text{transfer}(A_{j\triangleright}^{\max}) \in R_{t_{j\triangleright}}^{S_i}$, by definition of $R_{t_{j\triangleright}}^{S_i}$ (Equation (9)), $\text{transfer}(A_{j\triangleright}^{\max}) \rightarrow_{S_i} t_{j\triangleright}$, which with Equation (16) leads to $t'_{\triangleright j} \rightarrow_{S_i} t_{j\triangleright}$, and therefore $t'_{\triangleright j} \in R_{t_{j\triangleright}}^{S_i}$. □

**Remark B.22.7.** $\text{total}(j, I_{t_{j\triangleright}}^{S_i} \cup R_{t_{j\triangleright}}^{S_i}) \geq \text{total}(j, I_{t_{j\triangleright}}^{\max} \cup R_{t_{j\triangleright}}^{\max})$

Proof. This follows from Remarks B.22.5 and B.22.6 and the definition of $\text{total}(\cdot, \cdot)$. □

The lemma follows from Remarks B.22.1, B.22.4 and B.22.7. □

**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.

Proof. The lemma is proved by using $\hat{H}$ provided by Definition B.12, the sequence $S_i$ constructed in Definition B.20 for each correct process $p_i$, and considering Lemmas B.21 and B.22 that show that $S_i$ is an AT-Sequence. □

### B.1.3 AT-Termination of Algorithm 3

**Lemma 6.2 (AT-Termination).** All operation invocations 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 27). This ap_prove operation terminates by AP-Termination, so the transfer operation also terminates. □
some element $x_i \notin S_1 \cup S_2$, and follows the NIPoKNCR protocol. (Algorithm 6) shows that all data sent to Adv is secure under the DL assumption except a single Bezout coefficient, which does not reveal any data on $x$ or $\ell$ on its own. We conclude that the probability of Adv selecting the right set more accurately than at random is negligible. ◀

**Lemma 8 (UA-Undeniability).** Let $S$ be the set of elements accumulated in $A$. The probability that any PPT adversary Adv outputs $w, u$ for an element $e$ s.t. ua_verify_mem($A, e, w$)/true and ua_verify_non_mem($A, e, u$)/true is negligible.

**Proof.** Suppose that there exists an element $e$ which can be proven both membership and non-membership of for an accumulator $A = \langle x, \ell \rangle$. Then the statements $x \equiv e \mod \ell_e$ and $x \not\equiv e \mod \ell_e$ would both be true, which is impossible. ◀

**Lemma 9 (UA-Completeness).** For element $a \in S$ and $b \notin S$, $\Pr(ua_prove_mem(pp, sp, A, a) = \text{abort}) < \epsilon(\lambda)$ and $\Pr(ua_prove_non_mem(pp, sp, A, b) = \text{abort}) < \epsilon(\lambda)$.

**Proof.** The completeness property implies that NIPoKCR and NIPoKNCR are valid proofs of knowledge (PoK) for the relation of congruence. The PoK property of NIPoKCR and NIPoKNCR follow directly from the proofs of PoKRep from Boneh et al. [7], on which we base our protocols in the particular case $n=2$. The modification to prove congruence (and therefore the CRT) is straightforward. We consider accumulator $A = \langle X = g_1^x, L = g_2^\ell \rangle$ with secret parameters $\langle x, \ell \rangle$. To prove membership of an element $e$ with corresponding prime modulus $\ell_e$ using NIPoKCR, the AM first has to prove that $\ell_e \mid \ell$ by computing $q_\ell$ s.t. $\ell = \ell_e q_\ell$. Then it commits to $q_\ell$ using $Q_\ell = g_2^{q_\ell}$. The statement can then be verified against the accumulator by computing $L = Q_\ell^{\ell_e}$, where $L = g_2^\ell \in A$. Now that the existence of an element paired with $\ell_e$ is ensured, the prover computes $q_x = \lfloor x/\ell_e \rfloor$ using its secret parameters $\langle x, \ell \rangle$. It also computes $q_e = \lfloor e/\ell_e \rfloor$ to reduce the verification time of the verifier, and commits to all values using $Q = g_1^{q_x} g_2^{q_e}$. The verifier can then compute $r_e = e \mod \ell_e$ and accepts if $X g_2^e = Q^{\ell_e} (g_1 g_2)^{r_e}$. The same principle is used in NIPoKNCR to prove non-membership of an element, where the prover shows that $\ell_e \nmid \ell \lor x \not\equiv e \mod \ell_e$. The statement $\ell_e \nmid \ell$ can simply be proven by finding the Bezout coefficients $a, b$ s.t. $a\ell + b\ell_e = 1$ and obfuscating $b$ using $B = g_2^b$ to prevent the adversary from computing $\ell$, as done for non-membership of RSA accumulators [7]. Since $x \not\equiv e \mod \ell_e$, we do not disclose $r_x = x \mod \ell_e$ as it would leak information about the element accumulated with $\ell_e$. Instead, the prover sends $R_x = g_1^{r_x}$ and proves that $R_x$ commits to $r_x \in [\ell_e]$ using a range proof. Then, the verifier accepts if $Q_x^{\ell_e} R_x Q_e^{\ell_e} g_2^{r_e} = X g_2^e$ and $R_x \not= g_1^{r_e}$. ◀

**Lemma 10 (UA-Soundness).** Let $S$ be the set of elements accumulated in $A$. The probability that any PPT adversary Adv outputs $w_a, u_b$ for elements $a, b$ s.t. ua_verify_mem(pp, A, a, w_a) = true $\land$ a $\notin$ S or ua_verify_non_mem(pp, A, b, u_b) = true $\land$ a $\in$ S is negligible.

**Proof.** We saw in Lemma 9 that membership and non-membership proofs are handled by our proofs of knowledge NIPoKCR and NIPoKNCR. However, what those protocols prove is not strict equality with set elements but congruence, i.e., for any element $e \in S$ and corresponding prime $\ell_e$, $x \equiv e \mod \ell_e$. Therefore, if an element $a \notin S$ is associated with prime $\ell_e$ and $a \equiv e \mod \ell_e$, then $x \equiv a \mod \ell_e$ and membership of $a$ could be proven. To ensure that the probability of such a collision remains negligible no matter the number of accumulated elements in $S$, we use a random oracle $H$ (Assumption 1) to attribute each element $e_i$ to a random index $i = H(e_i)$, and therefore to its prime $\ell_i$. Let us write $a_i \equiv q\ell_i + r_{ai} \mod \ell_i$.
## B.2 Proof of quasi-anonymity

**Lemma 6.3 (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$.

*Proof.* To determine if the adversary $\mathit{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 = \langle A'_i, bal\_c'_i \rangle$ and data $\mathit{data} = \langle \sigma_i, \pi, sn_i + 1, \langle A_i, A'_i, bal\_c_i, bal\_c'_i \rangle \rangle$;

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

Note that sender-receiver messages (item 2) are exchanged using the ra_send operation, which ensures receiver anonymity and confidentiality (see Section 3). Therefore, only accumulator updates (item 1) need to be considered. C-Hiding guarantees that the commitments $bal\_c_i$ and $bal\_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, $\mathit{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$, $\mathit{Adv}$ cannot deduce the recipient of a transfer more accurately than random, i.e., with a probability of less than $\min((1/n) + \varepsilon(\lambda), 1)$, where $\varepsilon$ is the statistical negligible function and $\lambda$ is the security parameter of the system. $\square$

**Lemma 6.4 (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}^+$.

*Proof.* The proof follows the same reasoning as that of Lemma 6.3. $\square$

# C Implementations of the Schemes of Section 5 / Appendix A

## C.1 Preliminaries

### C.1.1 Groups of unknown order

Our choice of UA [7] implementation requires the use of groups of unknown order (as defined in [15]) in which the Strong RSA assumption, the Low Order assumption and the Adaptive Root assumption holds. Concrete examples of groups of unknown order are RSA groups, ideal class groups and hyperelliptic Jacobians. However, only class groups and hyperelliptic Jacobians are efficient in the trustless setup model. In particular, [18] provides algorithms to trustlessly setup genus-3 hyperelliptic Jacobians of unknown order with 3392-bits field elements for 128 bits of security, which is close to the 3072-bits elements of RSA groups generated using a trusted setup for the same bit-security. They also provide a new compression algorithm for class groups, reaching 128-bits of security with 5088-bits elements.
Without loss of generality, we assume that $r_{a_i} = 0$ to maximize the range of possible values of $q$. Since $\ell_i \in \text{Primes}(b_2, b_1)$, we know that $2^{b_2} < \ell_i < 2^{b_1}$. Furthermore, since all accumulated elements are $b$-bit integers, we have $0 \le a_i < 2^b$. Thus, we have:

$$ 
\begin{aligned}
0 &\le a_i < 2^b, \\
0 &\le q\ell_i < 2^b, \\
0 &\le q < \frac{2^b}{2^{b_2}}.
\end{aligned}
 $$

Because $q$ is incremented with a step of $\ell_i$, there can be at most $1 + \frac{2^b}{2^{(2b_2)}}$ distinct values of $q$. Thus, the probability that an element $a_i \notin S$ is congruent to a random pair $\langle e_i, \ell_i \rangle$ s.t. $e_i \in S$ is $\frac{1+\frac{2^b}{2^{(2b_2)}}}{\frac{1}{2^b} + \frac{1}{2^{(2b_2)}}}$, which is negligible. The probability of $Adv$ succeeding in colliding with a given index is even lower, that is $\text{Pr}(\text{BinomialDistribution}(1 + \frac{2^b}{2^{(2b_2)}}, \frac{1}{\pi(b_1)-\pi(b_2)}))$. Conversely, it is not possible to prove the non-membership of an element $e \in S$, as one cannot prove that $x \not\equiv e \mod \ell_e$ if $x \equiv e \mod \ell_e$. $\triangleleft$

## B.2 Extended Pedersen commitments for vectors

For our commitment scheme (specified in Section 4.2), we opt for the generalization of Pedersen commitments to vectors as defined in [26], which are both perfectly hiding and additively homomorphic under the discrete log assumption. The commitment scheme has public parameters $(\mathbb{G}, p, g, g_1, ..., g_n)$, where $\mathbb{G}_p$ is a finite cyclic group of prime order and $|p| = \lambda$, and $g, g_1, ..., g_n$ are group elements. A commitment to a vector $\langle m_1, ..., m_n \rangle$ with blinding factor $r$ is of the form $c = g^r \prod_{i=1}^n g_i^{m_i}$. By additively homomorphic, we mean that for any commitments $C_1, C_2$ with openings $\langle m_1, ..., m_n, r \rangle$ and $\langle m'_1, ..., m'_n, r' \rangle$, $C = C_1 + C_2$ opens to $\langle m_1 + m'_1, ..., m_n + m'_n, r + r' \rangle$. Note that all commitments are constant-size (1 group element).

**Vector commitments with partial openings.** For some applications, a given process may want to only store a partial opening to one of the values of a vector commitment. For instance, a global vector commitment may be used in a system of processes, where each process has a “personal” value in the vector. In this context, each process only stores the (constant-size) global commitment and the (constant-size) partial opening of its personal value, and can prove to other processes that its personal value “belongs” to (i.e., can be opened from) the global commitment (using the partial opening). It is also possible to update one of the values of a vector commitment if we provide (along with the new value) the partial opening of the old value. These vector commitment updates can be applied commutatively, i.e., no matter whether we apply two different updates of two values in a vector commitment in one order or the other, it always yields the same updated vector commitment as a result.

Vector commitments with partial openings can also be implemented using Pedersen commitments [26]. In our agreement proof (AP) implementation (see Appendix B.3), we use a global vector commitment with partial openings that keeps track of the sequence numbers of every process in the system: to increment its sequence number, a process has to provide the partial opening to its old sequence number. As every process only has to store this global commitment and its personal partial opening (which both have $O_\lambda()$ bits), it allows us to obtain an AP implementation with a constant storage cost of $O_\lambda()$.

To support vector commitments with partial openings, we enrich the specification of Section 4.2 with two new operations. Let us consider a vector of values $V$ and its corresponding vector commitment $c = \text{vc\_commit}(V)$.
<table><thead><tr><th rowspan="2">|S|</th><th rowspan="2">Addition<sup>1</sup></th><th colspan="2">Membership proof</th><th colspan="2">Non-membership proof</th></tr><tr><th>Generation<sup>2</sup></th><th>Verification</th><th>Generation</th><th>Verification</th></tr></thead><tbody><tr><td>100</td><td>0.337 ms</td><td>31.462 ms</td><td>0.351 ms</td><td>31.835 ms</td><td>0.687 ms</td></tr><tr><td>500</td><td>0.368 ms</td><td>155.366 ms</td><td>0.345 ms</td><td>151.720 ms</td><td>0.687 ms</td></tr><tr><td>1000</td><td>0.342 ms</td><td>299.615 ms</td><td>0.339 ms</td><td>298.825 ms</td><td>0.675 ms</td></tr><tr><td>1500</td><td>0.337 ms</td><td>447.879 ms</td><td>0.338 ms</td><td>444.978 ms</td><td>0.663 ms</td></tr><tr><td>2000</td><td>0.360 ms</td><td>607.562 ms</td><td>0.345 ms</td><td>605.435 ms</td><td>0.668 ms</td></tr></tbody></table>

<caption>Table 4: Performance of accumulator proof generation and verification for various set sizes $|S|$.</caption>

## C.2 Accumulator

For our accumulator (specified in Appendix A.2), we opt for the trustless extension of universal RSA accumulators in groups of unknown order from [7]. While RSA accumulators typically require the accumulated elements to be prime numbers, one can use a hash function with prime domain to accumulate arbitrary elements. The scheme features constant size public parameters, accumulator digest and proofs of (non-)membership. Moreover, (non-)membership proofs can be verified in constant time. The scheme can thus be described as succinct. Note that when adding a new element $e$ to an accumulator $A$, the membership proof of $e$ is the value of $A$ before $e$ was added. Therefore, as a process only needs the membership proof of a transfer when updating the accumulator and creating the ZKP of its account update, membership proof generation is done in constant time in Algorithm 3.

### C.2.1 Hashing to primes

An RSA accumulator can only contain prime numbers. To overcome this limitation, one must use a hash-to-prime function $H_{\text{Primes}}: \{0, 1\}^* \to \text{Primes}(\lambda)$, where $\text{Primes}(\lambda)$ is the set of primes smaller than $2^\lambda$. $H_{\text{Primes}}$ must be deterministic and collision-resistant to prevent an element from being mapped to multiple primes or multiple elements from being hashed into the same prime. A common method of hashing to prime numbers is to combine a pseudo-random function (e.g., hash function) with a probabilistic primality test. The resulting function consists of successively hashing the concatenation of the data to hash with an incremented counter until finding the smallest nonce that yields a prime number.

### C.2.2 Experimentations

All our tests are executed sequentially on a core i9-11950H processor. Our implementation is coded in C++ using the GNU MP Bignum library. We instantiated $H_{\text{Primes}}$ using SHA3 and a probabilistic Miller-Rabin primality test with 80 rounds, resulting in an error probability of $4^{-80}$. The output of SHA3 is truncated to 264 bits, which is sufficient to obtain 128 bits of security as the prime counting function estimates that there are at least $2^{256}$ primes in $[0, 2^{264}]$. We measure an average time of 9 ms to hash a single element to a 264 bits prime. We also implement a 2048-bit RSA accumulator. Table 4 shows the performance of proof generation and verification. We observe that while (non-)membership proof generation from "scratch" scales linearly with the size of the accumulated set, membership proof generation during element addition is computed in constant time as element accumulation consists of a single exponentiation of the RSA digest by the newly added element. Similarly, we observe that (non-)membership proof verification is constant time, as it also consists of a single group exponentiation.

<footnote n="1">¹ This also outputs the membership proof of the new element.</footnote>

<footnote n="2">² Unused, as we rely on the proof generated during addition.</footnote>
- $\text{vc\_val\_update}(c, i, o, v')/r$: Takes a vector commitment $c$, an index $i$, an opening of the old value at index $i$, and a new value $v'$, and returns a pair $r = \langle c', o' \rangle$ where $c'$ is an updated vector commitment (committing the same vector as $c$, except that the $i^{\text{th}}$ value is now $v'$) and $o'$ is the opening of $v'$ at index $i$ in $c$ if $o$ is a valid opening for the $i^{\text{th}}$ value of $c$, or $r = \text{abort}$ otherwise.

- $\text{vc\_val\_verify}(c, i, v, o)/r$: Returns $r = \text{true}$ if $o$ is a valid opening for the commitment $c$ and value $v$ at index $i$, or $r = \text{false}$ otherwise.

The enriched specification of vector commitments with these new operations stays correct, binding and hiding: informally, if we consider some vector commitment $c_{\text{init}}$ for a vector $V$ and some value $v_{\text{init}} \in V$ at index $i$ with partial opening $o_{\text{init}}$, the VC-Correctness, VC-Binding and VC-Hiding properties of Section 4.2 still hold even if we replace the $\text{vc\_commit}(V)/\langle c, o \rangle$ and $\text{vc\_verify}(c, V, o)/\text{true}$ mentions by $\text{vc\_val\_update}(c_{\text{init}}, i, o_{\text{init}}, v)/\langle c, o \rangle$ and $\text{vc\_val\_verify}(c, i, v, o)/\text{true}$, respectively.

## B.3 A consensus-free quorum-based Agreement Proof implementation

In this section, we provide an implementation of the agreement proof scheme of Section 4.1 that does not rely on consensus, is succinct, and has a constant storage requirement of $O_{\lambda}(1)$. Our AP implementation leverages 2 schemes:

1. threshold digital signatures (see Appendix B.3.1), for creating constant-size agreement proofs $\sigma$ (i.e., quorums of signatures) and verifying them without the set of all public keys;

2. vector commitments with partial openings (see Appendix B.2) for committing the vector of all $\langle \text{sequence number, process identity} \rangle$ pairs of the system.

### B.3.1 Threshold signatures

Threshold signatures are a family of aggregated digital signatures that are produced in a system of $n$ processes, by having at least $k$ out of $n$ processes (the threshold) produce individual signatures for the same message, which we call *intermediary signatures*. Once these intermediary signatures have been produced, they are aggregated (typically by a coordinating process) into a fixed-size aggregated signature, called the threshold signature $\sigma$. We call a threshold signature with a threshold of $k$ signers out of $n$ processes a *k-threshold signature*. Unlike multi-signature schemes, which keep track of the identities of their signers, threshold signatures use a single system-wide public key, which is the same for all threshold signatures produced by the scheme. The global public key is typically generated during the setup phase of the system. Naturally, a *k*-threshold signature for a message $m$ is valid iff it aggregates $k$ valid distinct intermediary signatures for $m$.

Various asymmetric signature schemes can be transformed into threshold signature schemes [46, 48, 52, 60]. Furthermore, the verification algorithm of most threshold versions of a classical signature scheme remains unchanged and can thus be efficiently verified independently of the number of co-signers. In particular, Roast [44] implements an asynchronous threshold Schnorr signature scheme that supports arbitrary choices of $t$, guarantees unforgeability against a dishonest majority ($n > 2t$), and guarantees that as long as $t+1$ honest signers participate, a valid signature is outputted the remaining $n-t-1$ signers are malicious and try to prevent the creation of the signature. It is also optimal-round efficient, with one preprocessing round before knowing the messages to be signed and one signing round per message.
### C.3 Commitment scheme

In our system, each process creates a hiding commitment of a single value (the balance of its account). This commitment can be based on any constant-size commitment scheme with trustless setup. For example, one could use Pedersen commitments in groups of unknown order (or elliptic curves [21]), which are unconditionally hiding and computationally binding. Conversely, other schemes such as ElGamal commitments [24] could be used to obtain commitments that are unconditionally binding but computationally hiding. Note that it is impossible for a commitment scheme to be both unconditionally binding and unconditionally hiding.

### C.4 Transparent zk-SNARK with time-optimal prover

For our zk-SNARK scheme, we choose Spartan [42], which is both transparent (trustless setup) and prover time-optimal.

## D A consensus-free quorum-based Agreement Proof implementation

In this section, we provide an implementation of the agreement proof scheme of Section 6.1 that does not rely on consensus, uses succinct cryptography, and has a storage of $O(\lambda + n)$ bits per process and an overall communication of $O(\lambda n)$ bits. Our AP implementation leverages threshold digital signatures (see Appendix D.1) to create constant-size (i.e., $O(\lambda)$-bit) agreement proofs $\sigma$ (i.e., quorums of signatures) and to verify them without the set of all public keys.

### D.1 Threshold signatures

Threshold signatures are a family of aggregated digital signatures that are produced in a system of $n$ processes, by having at least $k$ out of $n$ processes (the threshold) produce individual signatures for the same message, which we call *intermediary signatures*. Once these intermediary signatures have been produced, they are aggregated (typically by a coordinating process) into a fixed-size aggregated signature, called the threshold signature $\sigma$. We call a threshold signature with a threshold of $k$ signers out of $n$ processes a *k-threshold signature*. Unlike multi-signature schemes, which keep track of the identities of their signers, classical threshold signature schemes use a protocol called distributed key generation (DKG) to distribute the secret key of a signature scheme across processes. Processes then interact to reconstruct a single signature that can be verified against a single system-wide public key. The computation of the individual shares of the secret key and the derivation of the system-wide public key are typically performed during the setup phase of the system. Naturally, a $k$-threshold signature for a message $m$ is valid if and only if it aggregates $k$ valid distinct intermediary signatures for $m$.

Various threshold signature schemes have been built on top of asymmetric schemes such as RSA, Schnorr, BLS or ECDSA [8, 16, 31, 40, 43, 44]. Furthermore, the verification algorithm of most threshold versions of a classical signature scheme remains unchanged and can thus be efficiently verified independently of the number of co-signers using the system-wide public key. For example, the asynchronous DKG protocol of [16] can be used with DLOG-based threshold cryptosystems such as BLS [8] or Schnorr [5, 40] to provide $k$-threshold signatures with high-threshold values ($k \in [t, n - t - 1]$).

#### D.1.1 Succinctness of threshold signatures

Efficient high-threshold signature implementations (e.g., [5, 8, 40]) guarantee that, for a fixed $\lambda$ and any number of signers $k$, the size and verification time of a threshold signature is equivalent to that of a single intermediary signature. Unlike classical signature schemes and multi-signature schemes, which require knowing the public keys of all the signers of a quorum of signatures, threshold signature schemes only
require knowing one global public key for the system for verifying a quorum of signatures. In other
words, given the maximum number of signers $n$ in the system, instead of having quorum signatures of
size $O(\lambda n)$ bits with classical signature schemes or of size $O(\lambda + n)$ bits with multi-signature schemes
(as the set of signers of a quorum can be encoded in a bit vector), threshold signatures can produce
quorum signatures of size $O(\lambda)$ bits (once a quorum has been generated, the individual identities of the
signers are not needed for its verification). Therefore, these implementations are of constant size and
constant verification time, and thus succinct.

### D.1.2 Verifying intermediary signatures without storing all individual public keys

As mentioned previously, only a single global public key is needed to verify a threshold signature, in-
stead of all the signers’ public keys. However, the coordinator must verify all intermediary signatures’
validity before generating the threshold signature. To do that without having to store all the system’s
public keys, it is possible to use a *vector commitment (VC)* [13], a generalization of the classical com-
mitment scheme presented in Appendix A.1. Like its name suggests, a VC scheme commits a vector of
values, upon which it is then possible to have a “partial” opening of a single value of the vector, without
having to open the vector in its entirety. One of the most widely known examples of vector commitment
is Merkle trees [35].

In our context, this scheme would allow us to “compress” the entire vector of public keys of the
system into a VC of size $O(\lambda)$. This VC would be created during the system setup. In addition to the
global VC, each correct process $p_i$ also stores its individual public key, and the partial opening for the
$^i$th value of the VC, corresponding to $p_i$’s public key. This way, $p_i$ can prove to another process $p_j$ that
it indeed belongs to the system, by sending to $p_j$ its individual public key and partial opening. With this
data, $p_j$ can then verify that the $^i$th value of the global VC indeed opens to $p_i$’s public key.

Since each correct process $p_i$ stores the global VC ($O(\lambda)$ bits), its individual public key ($O(\lambda)$ bits), and the partial opening of the $^i$th value of the global VC ($O(\lambda)$ bits), this technique does not impact the overall storage cost of our AP algorithm (Algorithm 4) of $O(\lambda + n)$ bits stored per correct process.

More generally, this technique effectively allows us to have a public key infrastructure (PKI) under a
fixed storage cost of $O(\lambda)$ bits per correct process (provided that the set of public keys does not change
over time). For simplicity, all this machinery is hidden in the validation of intermediary signatures of
Algorithm 4, lines 15 and 22.

### D.1.3 Efficiently aggregating intermediary signatures

For constructing a $k$-threshold signature, a coordinator process has to receive and aggregate $k$ interme-
diary signatures by $k$ distinct processes. In particular, it has to make sure that it does not aggregate
multiple intermediary signatures from the same process.

For the sake of simplicity, we address these issues by a naive approach in Algorithm 4: we require
the coordinator $p_i$ to save all the intermediary signatures it receives (and implicitly their signer’s identity)
in the $sigs_i$ set (line 25). Once the threshold signature has been produced, $sigs_i$ is emptied, and all the
temporary data (intermediary signatures and sender identities) are deleted. The $sigs_i$ set contains at
most $n$ intermediary signatures ($O(\lambda)$ bits) and signer identities ($O(\log n)$ bits), which incurs a total
of $O(n(\lambda + \log n))$ bits. However, as this data is stored only temporarily during the execution of the
`ap_prove()` operation, we consider that it pertains to the *space complexity* of `ap_prove()`, and not the
overall *storage cost* of our system.

Remark that this suboptimal space complexity can be easily reduced to $O(\lambda + n)$ bits using the fol-
lowing method. Instead of aggregating the intermediary signatures all at once at the end of the execution
of `ap_prove()` (line 11), they can be gradually aggregated as they are received (line 21) on an aggregated
signature of $O(\lambda)$ bits, which becomes a threshold signature once it aggregates at least $k$ intermediary
predicate (line 16). Then, $p_i$ waits for the provided $sn_j$ to be the next one (in FIFO order) to be processed (line 17). After that, $p_i$ produces its intermediary signature (line 18) and sends it to $p_j$ in a QUORUMSIG message (line 19). Finally, $p_i$ updates the pair of $p_j$ in $sn\_c_i$ with its new $sn_j$ (line 20) and saves the new partial opening of this update in $o_i$ if $i = j$ (line 21).

When $p_i$ receives a QUORUMSIG message, it saves the provided intermediary signature if it is valid and if $p_i$ has not already produced an AP for the payload (line 23).

**Algorithm 8** Light and consensus-free quorum-based Agreement Proof algorithm for an AP predicate $P_A$, and assuming $n > 3t$ (code for $p_i$).

1 **init:** $sigs_i \leftarrow \emptyset$; $v_i \leftarrow \perp$; $sn_i \leftarrow 0$; $sn\_c_i \leftarrow$ global VC for the vector containing a $\langle 0, j \rangle$ pair for every $j \in [1..n]$; $o_i \leftarrow$ partial opening of the $\langle 0, i \rangle$ pair at index $i$ in $sn\_c_i$.

2 **operation ap_verify($\sigma_j, v, sn_j, j$) is**

3 **return** $\begin{cases} \text{true} & \text{if } \sigma_j \text{ is a valid } (\lfloor \frac{n+t}{2} \rfloor+1)\text{-threshold signature for } \langle v, sn_j, j \rangle, \\ \text{false} & \text{otherwise.} \end{cases}$

4 **operation ap_prove($v, data$) is**

5 **if** $P_A(data) = \text{false then return abort;}$
6 $v_i \leftarrow v$; ▷save $v$ for condition at line 23

7 $sn_i \leftarrow sn_i + 1$; ▷increment $sn_i$

8 $sig_i \leftarrow$ initialization signature of $\langle v, data, sn_i, i \rangle$ by $p_i$;

9 **broadcast** QUORUMINIT($v, data, sn_i, i, sig_i, o_i$);

10 **wait** ($sig_i$ has strictly more than $\frac{n+t}{2}$ intermediary signatures for $\langle v, sn_i, i \rangle$);

11 $\sigma_i \leftarrow$ aggregation of $sig_i$ into a $(\lfloor \frac{n+t}{2} \rfloor+1)$-threshold signature for $\langle v, sn_i, i \rangle$;

12 $sig_i \leftarrow \emptyset$; $v_i \leftarrow \perp$; ▷flush temporary data

13 **return** $\langle \sigma_i, sn_i \rangle$.

14 **when** QUORUMINIT($v, data, sn_j, j, sig_j, o_j$) is received do

15 **if** $sig_j$ is not a valid initialization signature for $\langle v, data, sn_j, j \rangle$ by $p_j$ **then** return;

16 **if** $P_A(data) = \text{false then return}$;

17 **wait** ($\text{vc\_val\_verify}(sn\_c_i, j, \langle sn_j - 1, j \rangle, o_j)$);

18 $sig_i \leftarrow$ intermediary signature for $\langle v, sn_j, j \rangle$ by $p_i$;

19 **send** QUORUMSIG($i, sig_i$) to $p_j$;

20 $\langle sn\_c_i, o_j \rangle \leftarrow \text{vc\_val\_update}(sn\_c_i, j, o_j, \langle sn_j, j \rangle)$; ▷update global VC $sn\_c_i$

21 **if** $i = j$ **then** $o_i \leftarrow o_j$. ▷save new partial opening if $p_i$ is the prover

22 **when** QUORUMSIG($j, sig_j$) is received do

23 **if** $sig_j$ is a valid intermediary signature for $\langle v_i, sn_i, i \rangle$ by $p_j$ **and** AP $\sigma_i$ for $v_i$ not already produced by $p_i$ **then** $sig_i \leftarrow sig_i \cup \{sig_j\}$.

Let us remark that, like in our asset transfer algorithm of Algorithm 3, we impose the fact that the size of the $sn_i$ variable must be in $O_\lambda(1)$. Let us also note that this implementation of the Agreement Proof scheme has a message complexity of only $O(n)$.

### B.3.3 Proof of Algorithm 8

In the following correctness proofs of the AP scheme, we consider an AP object $O_A$ set up with an AP predicate $P_A$.
signatures. This way, each intermediary signature can be forgotten right after it is received and aggregated. Furthermore, the coordinator can use a bit vector of *n* bits to efficiently keep track of the processes that already participated in the aggregated signature (the *i*-th bit indicates if the intermediary signature of *p*<sub>*i*</sub> was already received or not).

## D.2 Algorithm

In this section, we present our AP implementation, which eschews consensus by using threshold signatures for quorums. It achieves lightness by using succinct cryptographic primitives and ensuring a storage cost of $O(\lambda + n)$ bits per correct process, and a communication of $O(\lambda n)$ bits sent overall.<fnref n="16" />

Algorithm 4 describes the code of this implementation for a correct process $p_i$ and an AP predicate $P_A$. It uses 3 local variables: $sigs_i$ (a set of intermediary signatures used for generating threshold signatures), $v_i$ (the value of the current ap_prove execution), and $seq_nums_i$ (the array containing the sequence number (initialized with 0) of each process $p_j$, $j \in [n]$).

The ap_verify operation simply verifies that the provided AP $\sigma_j$ is a valid ($\lfloor \frac{n+t}{2} \rfloor + 1$)-threshold signature for the provided value $v$, sequence number $sn_j$ and process $p_j$ (line 1).

The ap_prove operation first computes its next sequence number $sn_i$ of $p_i$ (line 5). Then, it verifies that the provided $v$, *data*, and $sn_i$ satisfy the AP predicate (line 6). If it does, $p_i$ then saves the provided value $v$ in the local variable $v_i$ (line 7). Next, $p_i$ generates the first signature of its payload, called the initialization signature (line 8), and broadcasts it in a QUORUMINIT message which requests other processes of the system to sign its payload (line 9). Process $p_i$ then waits for a quorum of intermediary signatures from other processes (line 10), and when it is received, $p_i$ aggregates all intermediary signatures into a ($\lfloor \frac{n+t}{2} \rfloor + 1$)-threshold signature (line 11), flushes the temporary data (line 12) and returns the AP and next sequence number (line 13).

When $p_i$ receives a QUORUMINIT message from a process $p_j$, it first checks that the provided initialization signature is valid (line 15) and that the provided $v$, *data*, and $sn_j$ satisfy the AP predicate (line 16). Then, $p_i$ waits for the provided $sn_j$ to be the next one (in FIFO order) to be processed (line 17). After that, $p_i$ produces its intermediary signature (line 18) and sends it to $p_j$ in a QUORUMSIG message (line 19). Finally, $p_i$ updates the sequence number of $p_j$ in $seq_nums_i$ with its new $sn_j$ (line 20).

When $p_i$ receives a QUORUMSIG message, it checks if the intermediary signature is valid (line 22), if it has not already received a previous intermediary signature from the same signer (line 23), and if it has not already produced an AP for the payload (line 24). If these conditions pass, $p_i$ saves the provided intermediary signature (line 25).

## D.3 Proof of Algorithm 4

In the following correctness proofs of the AP scheme, we consider an AP object $Obj_A$ set up with an AP predicate $P_A$.

**Lemma D.1 (AP-Validity).** If $\sigma_i$ is a valid AP for a value $v$ at sequence number $sn_i$ from a correct process $p_i$, then $p_i$ has executed $Obj_A.ap_prove(v, \star)/\sigma_i$ as its $sn_i$<sup>th</sup> invocation of $Obj_A.ap_prove(..)$.

*Proof.* Let us assume that $\sigma_i$ is a valid AP for value $v$ at sequence number $sn_i$ from a correct process $p_i$. By definition of the ap_verify operation at line 3, $\sigma_i$ is a valid ($\lfloor \frac{n+t}{2} \rfloor + 1$)-threshold signature for $v$ at $sn_i$ from $p_i$. This threshold signature must have been aggregated from at least $\lfloor \frac{n+t}{2} \rfloor + 1$ intermediary signatures. Given the system assumption $n > 3t$, we have $\lfloor \frac{n+t}{2} \rfloor + 1 > \lfloor \frac{4t}{2} \rfloor + 1 = 2t + 1 \geq t + 1$. Therefore, at least one correct process must have produced an intermediary signature for $\langle v, sn_i, i \rangle$ at line 18. However, to execute this line, this correct process must have verified the initialization signature of $p_i$ at

<footnote n="16">¹⁶For these analyses, like in our asset transfer algorithm of Algorithm 3, we impose that sequence numbers are constant-size.</footnote>
**Lemma 11 (AP-Validity).** If $\sigma_i$ is a valid AP for a value $v$ at sequence number $sn_i$ from a correct process $p_i$, then $p_i$ has executed $O_A.ap\_prove(v, \star)/\langle\sigma_i, sn_i\rangle$.

**Proof.** Let us assume that $\sigma_i$ is a valid AP for value $v$ at sequence number $sn_i$ from a correct process $p_i$. By definition of the ap_verify operation at line 3, $\sigma_i$ is a valid ($\lfloor \frac{n+t}{2} \rfloor + 1$)-threshold signature for $v$ at $sn_i$ from $p_i$. This threshold signature must have been aggregated from at least $\lfloor \frac{n+t}{2} \rfloor + 1$ intermediary signatures. Given the system assumption $n > 3t$, we have $\lfloor \frac{n+t}{2} \rfloor + 1 > \lfloor \frac{4t}{2} \rfloor + 1 = 2t + 1 \ge t + 1$. Therefore, at least one correct process must have produced an intermediary signature for $\langle v, sn_i, i \rangle$ at line 18. However, to execute this line, this correct process must have verified the initialization signature of $p_i$ at line 15. By the unforgeability of signatures, the only way to produce this initialization signature is for $p_i$ to execute line 8, during an $O_A.ap\_prove(v, \star)/\langle\sigma_i, sn_i\rangle$ execution. ◀

**Lemma 12 (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 process $p_i$.

**Proof.** Let us assume, on the contrary, that there exists 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 process $p_i$ (correct or faulty). By definition of the ap_verify operation at line 3, $\sigma_i$ and $\sigma'_i$ are valid ($\lfloor \frac{n+t}{2} \rfloor + 1$)-threshold signatures for $v$ and $v'$ (resp.) at $sn_i$ from $p_i$. These threshold signatures must have been aggregated from the intermediary signatures of two sets of processes, $A$ and $B$, which have respectively signed $\langle v, sn_i, i \rangle$ and $\langle v', sn_i, i \rangle$. We have $|A| \ge \lfloor \frac{n+t}{2} \rfloor + 1 \le |B|$, or equivalently, $|A| > \frac{n+t}{2} < |B|$.14 We thus have $|A \cap B| = |A| + |B| - |A \cup B| > 2\frac{n+t}{2} - |A \cup B| \ge 2\frac{n+t}{2} - n = t$. Therefore, at least one correct process $p_j$ must belong both to $A$ and $B$, and must have signed both $\langle v, sn_i, i \rangle$ and $\langle v', sn_i, i \rangle$ for $v \ne v'$. But by the fact that correct processes produce intermediary signatures for some $sn_i$ at line 18 and right after update the $\langle sn_i, i \rangle$ pair in their sn_c commitment at line 20, it follows that correct processes produce at most one intermediary signature for a given $sn_i$ and sender identity $i$, which contradicts the fact that $p_i$ must belong both to $A$ and $B$. ◀

**Lemma 13 (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}$.

**Proof.** Let us assume that $\sigma_i$ is a valid AP for value $v$ at sequence number $sn_i$ from a process $p_i$ (correct or faulty). By definition of the ap_verify operation at line 3, $\sigma_i$ is a valid ($\lfloor \frac{n+t}{2} \rfloor + 1$)-threshold signature for $v$ at $sn_i$ from $p_i$. This threshold signature must have been aggregated from at least $\lfloor \frac{n+t}{2} \rfloor + 1$ intermediary signatures. Given the system assumption $n > 3t$, we have $\lfloor \frac{n+t}{2} \rfloor + 1 > \lfloor \frac{4t}{2} \rfloor + 1 = 2t + 1 \ge t + 1$. Therefore, at least one correct process must have produced an intermediary signature for $\langle v, sn_i, i \rangle$ at line 18. However, to execute this line, this correct process must have verified the satisfaction of $P_A$ by the received data at line 16, which entails that the prover $p_i$ must have known the data such that $P_A(data)/\text{true}$. ◀

**Lemma 14 (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}$.

**Proof.** Let us assume that a correct process $p_i$ executes $O_A.ap\_prove(v, data)/r$ with value $v$ and a data. If $P_A(data) = \text{false}$, then $p_i$ passes the condition at line 5 and return abort.

<footnote n="14">14 Recall that $\forall i \in \mathbb{Z}, r \in \mathbb{R}: (i \ge \lfloor r \rfloor + 1) \iff (i > r)$.</footnote>
1 **init**: $sigs_i \leftarrow \emptyset; v_i \leftarrow \perp; seq\_nums_i[1..n] \leftarrow [0..0]$.

2 **operation ap_verify($\sigma_j, v, sn_j, j$)** is

3
return { true if $\sigma_j$ is a valid ($\lfloor \frac{n+t}{2} \rfloor+1$)-threshold signature for $\langle v, sn_j, j \rangle$, 
false otherwise.

4 **operation ap_prove(v, data)** is

5 $sn_i \leftarrow seq\_nums_i[i] + 1$; ▷increment own sequence number

6 **if** $P_A(v, data, sn_i) = \text{false then return abort;}$

7 $v_i \leftarrow v$; ▷save $v$ for condition at line 21

8 $sig_i \leftarrow$ initialization signature of $\langle v, data, sn_i, i \rangle$ by $p_i$;

9 broadcast QUORUMINIT($v, data, sn_i, i, sig_i$);

10 wait ($sigs_i$ has strictly more than $\frac{n+t}{2}$ intermediary signatures for $\langle v, sn_i, i \rangle$);

11 $\sigma_i \leftarrow$ aggregation of $sigs_i$ into a ($\lfloor \frac{n+t}{2} \rfloor+1$)-threshold signature for $\langle v, sn_i, i \rangle$;

12 $sigs_i \leftarrow \emptyset; v_i \leftarrow \perp$; ▷flush temporary data

13 return $\langle \sigma_i, sn_i \rangle$.

14 **when** QUORUMINIT($v, data, sn_j, j, sig_j$) **is** received **do**

15 **if** $sig_j$ is not a valid initialization signature for $\langle v, data, sn_j, j \rangle$ by $p_j$ **then** return;

16 **if** $P_A(v, data, sn_j) = \text{false then return;}$

17 wait $seq\_nums_i[j] = sn_j - 1$;

18 $sig_i \leftarrow$ intermediary signature for $\langle v, sn_j, j \rangle$ by $p_i$;

19 send QUORUMSIG($i, sig_i$) to $p_j$;

20 $seq\_nums_i[j] \leftarrow sn_j$. ▷update $p_j$'s sequence number

21 **when** QUORUMSIG($j, sig_j$) **is** received **do**

22 **if** $sig_j$ is not a valid intermediary signature for $\langle v_i, sn_i, i \rangle$ by $p_j$ **then** return;

23 **if** some intermediary signature by $p_j$ already in $sigs_i$ **then** return;

24 **if** some AP $\sigma_i$ for $v_i$ already produced by $p_i$ **then** return;

25 $sigs_i \leftarrow sigs_i \cup \{sig_j\}$.

**Algorithm 4:** Light and consensus-free quorum-based Agreement Proof algorithm for an AP predicate $P_A$, and assuming $n > 3t$ (code for $p_i$).

line 15. By the unforgeability of signatures, the only way to produce this initialization signature is for $p_i$ to execute line 8, during an $Obj_A.ap_prove(v, \star)/\sigma_i$ execution. □

**Lemma D.2 (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'$.

**Proof.** Let us assume, on the contrary, that there exists 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 process $p_i$ (correct or faulty). By definition of the ap_verify operation at line 3, $\sigma_i$ and $\sigma'_i$ are valid ($\lfloor \frac{n+t}{2} \rfloor+1$)-threshold signatures for $v$ and $v'$ (resp.) at $sn_i$ from $p_i$. These threshold signatures must have been aggregated from the intermediary signatures of two sets of processes, A and B, which have respectively signed $\langle v, sn_i, i \rangle$ and $\langle v', sn_i, i \rangle$. We have $|A| \ge \lfloor \frac{n+t}{2} \rfloor + 1 \le |B|$, or equivalently, $|A| > \frac{n+t}{2} < |B|$.<fnref n="17" /> We thus have $|A \cap B| = |A| + |B| - |A \cup B| > 2\frac{n+t}{2} - |A \cup B| \ge 2\frac{n+t}{2} - n = t$. Therefore, at least one correct process $p_j$ must belong both to A and B, and must have signed both $\langle v, sn_i, i \rangle$ and $\langle v', sn_i, i \rangle$ for $v \ne v'$. But by the fact that correct processes produce

<footnote n="17">¹⁷Recall that $\forall i \in \mathbb{Z}, r \in \mathbb{R}: (i \ge |r| + 1) \iff (i > r)$.</footnote>
If $P_A(\mathit{data}) = \mathit{true}$, $p_i$ continues the execution, produces an initialization signature at line 8, broadcasts a QUORUMINIT message at line 9 and wait for a quorum of signatures from the system at line 10.

Upon receiving this QUORUMINIT message, each correct process $p_j$ passes the conditions at line 15 (as $p_i$ has correctly generated its initialization signature $\mathit{sig}_i$) and at line 16 (as $p_i$ has verified the satisfaction of $P_A$ by data at line 5), and then wait that the received $sn_i$ is the next in FIFO order to be processed at line 17. As $p_i$ uses its sequence numbers in FIFO order, then $p_i$ has necessarily sent a QUORUMINIT message for each $sn'_i \in [1..sn_i]$, and $p_j$ will eventually receive all these QUORUMINIT messages. By induction, $p_j$ will pass the wait statement at line 17 for each $sn'_i \in [1..sn_i]$, because if $sn'_i = 1$, the condition line 17 is satisfied as the $sn\_c_j$ vector commitment is initialized at line 1 with a $\langle 0, i \rangle$ pair at index $i$, and if $sn'_i > 1$, then $p_j$ will eventually replace the $sn'_i - 2$ by $sn'_i - 1$ at line 20. Therefore, all correct processes, which are at least $n-t$, will eventually pass the wait statement at line 17. Given the system assumption $n > 3t$, we have $n - t = \frac{2n-2t}{2} > \frac{n+3t-2t}{2} = \frac{n+t}{2}$. Therefore, strictly more than $\frac{n+t}{2}$ (or, equivalently, at least $\lfloor \frac{n+t}{2} \rfloor + 1$)<fnref n="15" /> correct processes will produce an intermediary signature at line 18 and send it back to $p_i$ at line 19.

Finally, $p_i$ will receive this quorum of intermediary signatures at line 23, which will unlock the wait instruction at line 10, and $p_i$ will aggregate all intermediary signatures into a valid AP $\sigma_i$, and will return $\langle \sigma_i, sn_i \rangle$ at line 13. ◀

### B.3.4 Consensus-freedom and lightness of Algorithm 8

The consensus-freedom of Algorithm 8 follows trivially from the fact that the only communication primitives that it uses are classic send/receive operations and a best-effort broadcast operation, and because it always terminates in the presence of failures and asynchrony. The lightness of Algorithm 8 comes from its succinctness and constant storage.

- The succinctness of Algorithm 8 comes from the succinctness of threshold signatures: as shown in Appendix B.3.1, the best implementations of threshold signatures guarantee that the size and verification time of threshold signatures (and therefore also the agreement proofs $\sigma_i$ produced by Algorithm 8) are equivalent to that of a single intermediary signature. Therefore, Algorithm 8 is succinct.

- The constant storage of Algorithm 8 comes from its local variables: the $\mathit{signs}_i$ set and $v_i$ values are emptied at the end of each ap\_prove execution (line 12), and by definition, $sn_i$ and $sn\_c_i$ and $o_i$ have $O_\lambda(1)$ bits. Therefore, Algorithm 8 has a constant storage.

## B.4 Transparent zk-SNARK with time-optimal prover

For our zk-SNARK scheme, we choose Spartan [45], which is both transparent (trustless setup) and prover time-optimal.

### C Trustless system setup

Like most distributed or cryptographic systems, our system requires a setup phase to compute the initial public and private parameters enabling processes to participate in the system. We assume the initial knowledge of a genesis data structure to specify the process identifiers and the initial amounts of their respective accounts. Our system is set up in a trustless manner,

<footnote n="15">¹⁵ See footnote 14.</footnote>
intermediary signatures for some $sn_i$ at line 18 and right after updating the i-th sequence number in their `seq_num`s array at line 20, it follows that correct processes produce at most one intermediary signature for a given $sn_i$ and sender identity $i$, which contradicts the fact that $p_i$ must belong both to A and B. □

**Lemma D.3 (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(\star, data, sn_i)/true$.

*Proof.* Let us assume that $\sigma_i$ is a valid AP for value $v$ at sequence number $sn_i$ from a process $p_i$ (correct or faulty). By definition of the ap_verify operation at line 3, $\sigma_i$ is a valid ($\lfloor \frac{n+t}{2} \rfloor + 1$)-threshold signature for $v$ at $sn_i$ from $p_i$. This threshold signature must have been aggregated from at least $\lfloor \frac{n+t}{2} \rfloor + 1$ intermediary signatures. Given the system assumption $n > 3t$, we have $\lfloor \frac{n+t}{2} \rfloor + 1 > \lfloor \frac{4t}{2} \rfloor + 1 = 2t + 1 \geq t + 1$. Therefore, at least one correct process must have produced an intermediary signature for $\langle v, sn_i, i \rangle$ at line 18. However, to execute this line, this correct process must have verified the satisfaction of $P_A$ by the received data at line 16, which entails that the prover $p_i$ must have known the data such that $P_A(\star, data, sn_i)/true$. □

**Lemma D.4 (AP-Termination).** Given a correct process $p_i$ that executes $Obj_A.ap_prove(v, data)/r$ with value $v$ as its $sn_i^{th}$ invocation of $Obj_A.ap_prove(..)$, and a data, if $P_A(\star, data, sn_i) = true$ then $r = \sigma_i$, where $\sigma_i$ is a valid AP for $v$ at $sn_i$ from $p_i$. If $P_A(\star, data, sn_i) = false$, then $r = abort$.

*Proof.* Let us assume that a correct process $p_i$ executes $Obj_A.ap_prove(v, data)/r$ with value $v$ and a data as its $sn_i^{th}$ invocation of $Obj_A.ap_prove(..)$. If $P_A(\star, data, sn_i) = false$, then $p_i$ passes the condition at line 6 and return abort. If $P_A(\star, data, sn_i) = true$, $p_i$ continues the execution, produces an initialization signature at line 8, broadcasts a QUORUMINIT message at line 9 and wait for a quorum of signatures from the system at line 10.

Upon receiving this QUORUMINIT message, each correct process $p_j$ passes the conditions at line 15 (as $p_i$ has correctly generated its initialization signature $sig_i$) and at line 16 (as $p_i$ has verified the satisfaction of $P_A$ by data at line 6), and then wait that the received $sn_i$ is the next in FIFO order to be processed at line 17. As $p_i$ uses its sequence numbers in FIFO order, then $p_i$ has necessarily sent a QUORUMINIT message for each $sn'_i \in [1..sn_i]$, and $p_j$ will eventually receive all these QUORUMINIT messages. By induction, $p_j$ will pass the wait statement at line 17 for each $sn'_i \in [1..sn_i]$, because if $sn'_i = 1$, the condition line 17 is satisfied as $seq_num_j[i]$ is initialized at line 1 to 0, and if $sn'_i > 1$, then $p_j$ will eventually replace the $sn'_i - 2$ by $sn'_i - 1$ at line 20. Therefore, all correct processes, which are at least $n-t$, will eventually pass the wait statement at line 17. Given the system assumption $n > 3t$, we have $n-t = \frac{2n-2t}{2} > \frac{n+3t-2t}{2} = \frac{n+t}{2}$. Therefore, strictly more than $\frac{n+t}{2}$ (or, equivalently, at least $\lfloor \frac{n+t}{2} \rfloor + 1$) correct processes will produce an intermediary signature at line 18 and send it back to $p_i$ at line 19.

Finally, $p_i$ will receive this quorum of intermediary signatures at line 21, which will unlock the wait instruction at line 10, and $p_i$ will aggregate all intermediary signatures into a valid AP $\sigma_i$, and will return $\langle \sigma_i, sn_i \rangle$ at line 13. □

## D.4 Consensus-freedom of Algorithm 4

The consensus-freedom of Algorithm 4 follows trivially from the fact that the only communication primitives that it uses are classic send/receive operations and a best-effort broadcast operation, and because it always terminates in the presence of failures and asynchrony.

## D.5 Succinctness of Algorithm 4

The succinctness of Algorithm 4 comes from the succinctness of threshold signatures: as shown in Appendix D.1, the best implementations of threshold signatures guarantee that the size and verification time of threshold signatures (and therefore also the agreement proofs $\sigma_i$ produced by Algorithm 4) are equivalent to that of a single intermediary signature. Therefore, Algorithm 4 is succinct.
i.e., no trusted party is involved in the distributed computation of the system parameters nor holds a trapdoor or secret that could otherwise be used to compromise the system's safety. We refer to the distributed setup operation of the system as `system_setup()`. Note that the generation of the genesis data is not part of the `system_setup()`. This trustless setup is possible because the cryptographic schemes implementing our schemes also provide a trustless setup (see Appendix B).

We provide the following implementation draft to demonstrate the feasibility of `system_setup()`.

1. Assume public knowledge of `genesis_data` $\leftarrow \bigcup_{i=1}^{n} \langle pk_i, A_i, bal\_c_i \rangle$, where $A_i$ is the empty accumulator of process $p_i$ and `bal\_c_i` is a commitment to the initial balance of $p_i$ (`init_i`).

2. Assume private knowledge of the opening of `bal\_c_i`, secret parameters of $A_i$ and secret key of signature key pair $\langle sk_i, pk_i \rangle$ for each process $p_i$.

3. Execute the setup operation of each cryptographic scheme.

4. Setup the global vector commitment of $\langle \text{sequence number}, \text{process identity} \rangle$ pairs ($sn\_c_i$ in Algorithm 8) with public nonce $H(\text{genesis\_data})$ (with $H()$ a secure hash function), and initial vector $\bigcup_{i=1}^{n} \{0||i\}$ (we concatenate the initial $sn=0$ with the identity of each process $p_i$). The $sn\_c_i$ commitment is global, and hence is the same for all processes at the setup.

5. Generate a threshold signature $\sigma_i$ (compatible with Algorithm 8) that will serve as the initial agreement proof of $p_i$ for each $v_i = \langle A_i, bal\_c_i \rangle$.

6. Each process $p_i$ can now safely delete `genesis_data` and output its initial parameters $\langle sn\_c_i, A_i, bal\_c_i, \sigma_i, bal\_o_i \rangle$.

## D Transfer batching

In this section, we briefly propose a method to commit to batches of transfers (instead of single transfers) and to verify those batches succinctly, i.e., faster than if the batched transfers were verified individually. Such a method is advantageous both in terms of anonymity and efficiency, which is explained in more detail in Section 5.5.

**Incrementally Verifiable Computation (IVC).** Informally, an IVC can be represented as a function $F$ that takes as input a previous execution of $F$ and some additional input. For example, $F$ could be the function implementing the operation `process_transfer()` of Algorithm 3. Then each execution of $F$ would take as input an accumulator, an agreement proof, a balance commitment and a transfer commitment of a process $p_i$ and update the accumulator and balance commitment of $p_i$ accordingly. Note that by “chaining” several iterations of $F$, we obtain the processing of a batch of transfers.

**Folding scheme for IVC proofs.** Folding schemes such as Nova [34] or Sangria [23] allow creating efficient SNARKS that a given number of iterations of an IVC were correctly executed by generating a proof for each step, then combining them successively on-the-fly in constant time (factor of 2 for Nova). Once the prover wishes to demonstrate the correct processing of its IVC iterations, the IVC proof is compressed into a single, small and succinct SNARK proof.
## D.6 Storage cost of Algorithm 4

The storage of Algorithm 4 is of $O(\lambda + n)$ bits stored by each correct process. It comes from its local variables: the $signs_i$ set and $v_i$ values are emptied at the end of each ap_prove execution (line 12)<fnref n="18" />, and $seq_num$s$_i$ is an array of size $n$ containing constant-size sequence numbers (by definition). Lastly, the threshold signature scheme requires the storage of $O(\lambda)$ bits (see Appendix D.1.2). Therefore, each correct process only stores $O(\lambda + n)$ bits in Algorithm 4.

## D.7 Communication cost of Algorithm 4

The communication cost of Algorithm 4 is $O(n\lambda)$ bits sent by correct processes overall during an execution of ap_prove. It follows from the message exchanges entailed by an ap_prove($v, data$) invocation by a correct prover $p_i$. Recall that, for simplicity, we assume that the size of the $v$ and $data$ parameters of ap_prove(..) are of constant size.

In a first step, $p_i$ broadcasts a QUORUMINIT($v, data, sn_i, i, sig_i$) message at line 9, where $v, data$, and $sn_i$ are constant-size, $i$ has $O(\log n)$ bits, and $sig_i$ has $O(\lambda)$ bits. As this message is broadcast to all $n$ processes, the overall communication cost of this first step is $O(n(\lambda + \log n))$ bits.

In a second step, every correct process of the system $p_j$ receives the QUORUMINIT message, passes the conditions at lines 15 and 16, and sends a QUORUMSIG($j, sig_j$) message to $p_i$ at line 19, where $j$ has $O(\log n)$ bits, and $sig_j$ has $O(\lambda)$ bits. This amounts to $O(n(\lambda + \log n))$ bits sent overall by correct processes during this second step.

Therefore, the total number of bits sent by correct processes during the execution of Algorithm 4 is $O(n(\lambda + \log n))$. However, as we assume that $\lambda = \Omega(\log n)$ (see Section 3, ¶ Security parameter $\lambda$), the previous asymptote simplifies to $O(n\lambda)$ bits sent overall.

## E Trustless system setup

Like most distributed or cryptographic systems, our system requires a setup phase to compute the initial public and private parameters enabling processes to participate in the system. We assume the initial knowledge of a genesis data structure to specify the process identifiers and the initial amounts of their respective accounts. Our system is set up in a trustless manner, i.e., no trusted party is involved in the distributed computation of the system parameters nor holds a trapdoor or secret that could otherwise be used to compromise the system's safety. We refer to the distributed setup operation of the system as system_setup(). Note that the generation of the genesis data is not part of the system_setup(). This trustless setup is possible because the cryptographic schemes implementing our schemes also provide a trustless setup (see Appendix C).

We provide the following implementation draft to demonstrate the feasibility of system_setup().

1. Assume public knowledge of genesis_data $\leftarrow \bigcup_{i=1}^{n} \langle pk_i, A_i, bal_c_i \rangle$, where $A_i$ is the empty accumulator of process $p_i$ and $bal_c_i$ is a commitment to the initial balance of $p_i$ (init$_i$).

2. Assume private knowledge of the opening of $bal_c_i$, secret parameters of $A_i$ and secret key of signature key pair $\langle sk_i, pk_i \rangle$ for each process $p_i$.

3. Execute the setup operation of each cryptographic scheme.

4. Generate a threshold signature $\sigma_i$ (compatible with Algorithm 4) that will serve as the initial agreement proof of $p_i$ for each $v_i = \langle A_i, bal_c_i \rangle$.

<footnote n="18">¹⁸See Appendix D.1.3 for a discussion on why we consider the storage of these temporary variables to be part of the space complexity of the ap_prove() operation (and not the system's storage cost), and how this space complexity could be easily reduced to $O(\lambda + n)$ bits.</footnote>
5. Each process $p_i$ can now safely delete genesis_data and output its initial parameters $\langle A_i, bal_{c_i}, \sigma_i, bal_{o_i} \rangle$.

## F Transfer batching

In this section, we briefly propose a method to commit to batches of transfers (instead of single transfers) and to verify those batches succinctly, i.e., faster than if the batched transfers were verified individually. Such a method is advantageous both in terms of anonymity and efficiency, which is explained in more detail in Section 6.2.5.

**Incrementally Verifiable Computation (IVC).** Informally, an IVC can be represented as a function $F$ that takes as input a previous execution of $F$ and some additional input. For example, $F$ could be the function implementing the operation `process_transfer()` of Algorithm 3. Then each execution of $F$ would take as input an accumulator, an agreement proof and a balance commitment of a process $p_i$ and update the accumulator and balance commitment of $p_i$ accordingly. Note that by “chaining” several iterations of $F$, we obtain the processing of a batch of transfers.

**Folding scheme for IVC proofs.** Folding schemes such as Nova [32] or Sangria [23] allow the creation of efficient SNARKS that a given number of iterations of an IVC were correctly executed by generating a proof for each step, then combining them successively on-the-fly in constant time (factor of 2 for Nova). Once the prover wishes to demonstrate the correct processing of its IVC iterations, the IVC proof is compressed into a single, small and succinct SNARK proof.

## References

[1] A. Auvolat, D. Frey, M. Raynal, and F. Taïani. Money transfer made simple: a specification, a generic algorithm, and its proof. *Bulletin of EATCS*, 132:22–43, 2020.

[2] M. Baudet, G. Danezis, and A. 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.

[3] M. Baudet, A. Sonnino, M. Kelkar, and G. 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.

[4] J. C. Benaloh and M. 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 LNCS, pages 274–285, 1993.

[5] F. Benhamouda, S. Halevi, H. Krawczyk, Y. Ma, and T. Rabin. SPRINT: high-throughput robust distributed schnorr signatures. In *EUROCRYPT (5)*, volume 14655 of Lecture Notes in Computer Science, pages 62–91. Springer, 2024.

[6] N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, and O. Paneth. Succinct non-interactive arguments via linear interactive proofs. *J. Cryptol.*, 35(3):15, 2022.

[7] D. Boneh, B. Bünz, and B. Fisch. Batching techniques for accumulators with applications to IOPs and stateless blockchains. In *Proc. 39th Int’l Cryptology Conference*, LNCS, pages 561–586, 2019.

[8] D. Boneh, B. Lynn, and H. Shacham. Short signatures from the weil pairing. *J. Cryptol.*, 17(4):297–319, 2004.

[9] J. Bonneau, I. Meckler, R. Vanishree, and E. Shapiro. Mina: decentralized cryptocurrency at scale (White paper), 2020.
[10] G. Bracha. Asynchronous Byzantine agreement protocols. Inf. Comput., 75(2):130-143, 1987.

[11] B. Bünz, S. Agrawal, M. Zamani, and D. 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 LNCS, pages 423-443, 2020.

[12] B. Bünz, L. Kiffer, L. Luu, and M. Zamani. Flyclient: super-light clients for cryptocurrencies. In Proc. IEEE Symposium on Security and Privacy, pages 928-946, 2020.

[13] D. Catalano and D. Fiore. Vector commitments and their applications. Cryptology ePrint Archive, Paper 2011/495, 2011.

[14] D. Collins, R. Guerraoui, J. Komatovic, P. Kuznetsov, M. Monti, M. Pavlovic, Y. Pignolet, D. Seredinschi, A. Tonkikh, and A. Xygkis. Online payments by merely broadcasting messages. In Proc. 50th IEEE/IFIP Int'l Conf. on Dependable Systems and Networks (DSN'20), pages 26-38. IEEE, 2020.

[15] I. Damgård and M. Koprowski. Generic lower bounds for root extraction and signature schemes in general groups. In Proc. Int'l Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'02), volume 2332 of LNCS, pages 256-271. Springer, 2002.

[16] S. Das, Z. Xiang, L. Kokoris-Kogias, and L. 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] D. Derler, C. Hanser, and D. Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. In Proc. RSA Conference, volume 9048 of LNCS, pages 127-144. Springer, 2015.

[18] S. Dobson, S. D. Galbraith, and B. Smith. Trustless unknown-order groups. CoRR, abs/2211.16128, 2022. eprint: 2211.16128.

[19] P. Fauzi, S. Meiklejohn, R. Mercer, and C. 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] L. Fortnow. The complexity of perfect zero-knowledge. Adv. Comput. Res., 5:327-343, 1989.

[21] C. Franck and J. Großschädl. Efficient implementation of Pedersen commitments using twisted Edwards curves. In Proc. 3rd Int'l Conference on Mobile, Secure, and Programmable Networking (MSPN'17), volume 10566 of Lecture Notes in Computer Science, pages 1-17. Springer, 2017.

[22] D. Frey, M. Gestin, and M. 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, 21:1-21:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.

[23] A. Gabizon, Z. J. Williamson, and O. Ciobotaru. PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. IACR Cryptol. ePrint Arch.:953, 2019.

[24] T. E. Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory, 31(4):469-472, 1985.

[25] O. Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001, pages 1-372. ISBN: 0-521-79172-3.

[26] R. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovic, and D. Seredinschi. The consensus number of a cryptocurrency. Distributed Comput., 35(1):1-15, 2022.

[27] S. Gupta. A non-consensus based decentralized financial transaction processing model with support for efficient auditing (Master thesis). Arizona State University, 2016.
[28] D. E. Hopwood, S. Bowe, and T. H. N. Wilcox. Zcash protocol specification, 2016.

[29] A. Jain, E. Anceaume, and S. 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.

[30] A. Kiayias, N. Leonardos, and D. Zindros. Mining in logarithmic space. In Proc. ACM SIGSAC Conference on Computer and Communications Security (CCS'21), pages 3487-3501. ACM, 2021.

[31] C. Komlo and I. Goldberg. FROST: flexible round-optimized schnorr threshold signatures. In Proc. 27th Int'l Conf. on Selected Areas in Cryptography (SAC'20), volume 12804 of LNCS, pages 34-65. Springer, 2020.

[32] A. Kothapalli, S. T. V. Setty, and I. 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.

[33] P. Kuznetsov, Y. Pignolet, P. Ponomarev, and A. Tonkikh. Permissionless and asynchronous asset transfer. Distributed Computing, 36(3):349-371, 2023.

[34] L. Lamport, R. E. Shostak, and M. C. Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982.

[35] R. C. Merkle. A digital signature based on a conventional encryption function. In Proc. 7th Int'l Cryptology Conference (CRYPTO'87), volume 293 of LNCS, pages 369-378. Springer, 1987.

[36] S. Nakamoto. Bitcoin: a peer-to-peer electronic cash system, 2008.

[37] O. Naor and I. Keidar. On payment channels in asynchronous money transfer systems. In Proc. 36th Symposium on Distributed Computing (DISC'2022), volume 246 of LIPIcs, 29:1-29:20, 2022.

[38] M. C. Pease, R. E. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980.

[39] M. G. Reed, P. F. Syverson, and D. M. Goldschlag. Anonymous connections and onion routing. IEEE J. Sel. Areas Commun., 16(4):482-494, 1998.

[40] T. Ruffing, V. Ronge, E. Jin, J. Schneider-Bensch, and D. 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.

[41] P. Schindler, A. Judmayer, N. Stifter, and E. R. Weippl. HydRand: efficient continuous distributed randomness. In Proc. IEEE Symposium on Security and Privacy (SP'20), pages 73-89. IEEE, 2020.

[42] S. T. V. Setty. Spartan: efficient and general-purpose zksnarks without trusted setup. In Proc. 40th Annual International Cryptology Conference (CRYPTO'20), volume 12172 of LNCS, pages 704-737. Springer, 2020.

[43] D. R. Stinson and R. Strobl. Provably secure distributed schnorr signatures and a (t, n) threshold scheme for implicit certificates. In Proc. 6th Australasian Conf. Information Security and Privacy (ACISP'01), volume 2119 of LNCS, pages 417-434. Springer, 2001.

[44] H. W. H. Wong, J. P. K. Ma, H. H. F. Yin, and S. 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.