Curve Trees:

Practical and Transparent Zero-Knowledge Accumulators

Matteo Campanelli¹

Mathias Hall-Andersen²

(preliminary version)

June 13, 2022

Abstract. In this work we propose a new accumulator construction and efficient ways to prove knowledge of some element in a set without leaking anything about the element. This problem arises in several applications including privacy-preserving distributed ledgers (e.g., Zcash) and anonymous credentials. Our approaches do not require a trusted setup and significantly improve on the efficiency state of the of the art. We introduce new techniques inspired by commit-and-prove techniques and combine shallow Merkle trees, 2- cycles of elliptic curves to obtain constructions that are highly practical. Our basic construction—which we dub Curve Trees—is completely transparent (does not require a trusted setup) and is based on simple standard assumptions (DLOG and Random Oracle Model). It has small proofs and commitments and very efficient proving and verification time. Curve trees can be instantiated to be efficient in practice: the commitment to a 32 set (accumulator) is 256 bits for any set size; for a set of size 2 a proof is approximately 2KB, a verifier runs in ≈ 160ms (easily parallelizable to ≈ 80ms) and a prover in ≈ 3*.*6s on an ordinary laptop. Using our construction as a building block we can construct a simple and concretely efficient anonymous cryptocurrency with full anonymity set. We estimate the verification time to be ≈ 320ms (and trivially parallelizable to run in ≈ 160ms) or < 10ms when batch-verifying multiple (> 100) transactions simultaneously. Transaction sizes are < 3KB. Our timings are competitive with those of the approach in Zcash Sapling and trade slightly larger proofs (proofs in Zcash are 0.2KB) for a completely transparent setup.

$$ 2^{32} $$

1 Introduction

Zero-knowledge proofs are a cryptographic primitive that allows one to prove knowledge of a secret without revealing it. In many applications the focus is on proofs that are short and with efficient running time.

One of the rising applications of zero-knowledge is in set-membership: given a short digest to a set S, we want to later show knowledge of a member in the set without revealing the latter. This primitive is useful in domains such as privacy-preserving distributed ledgers, anonymous broadcast, financial identities and asset governance (see, e.g., + discussion in [BCF 21]).

Limitations of prior work. Our focus in this work is on solutions that are highly practical. That is, solutions with short proving/verification time and short proofs. While efficient solutions to zero-knowledge set-membership already exist, we argue that they have limitations. In particular, either they still have a high computational/communication cost (we elaborate in Section 1.2 where we compare to transparent polynomial commitments and ring signa- + tures [LRR 19]) or they rely on proof systems that are non-transparent. The latter means that, in order for the system to be bootstrapped, it is necessary to invoke a trusted authority. This is true for example in ZCash + (Sapling) [HBHW21] and in [CFH 21]. While we can partly overcome this issue by emulating the trusted authority through a large-scale MPC, this is still highly expensive, both computationally and logistically¹. Other solutions, such + as [BCF 21, CHA21], mitigate this problem by requiring a trusted setup for parameters that are reusable in other cryptographic settings (an RSA modulus). This, however, still requires invoking a trusted authority or arranging a + parameter-generation ceremony [CHI 20], which may not always be viable. We then turn to solutions that are fully transparent and still very efficient.

¹ https://z.cash/technology/paramgen/

Our contributions. Our main contribution is a concretely efficient construction for proving private set-membership with a fully transparent setup. Specifically we design a new data structure, Curve Trees, that supports concretely small commitment to a set and where we can show set membership in zero-knowledge and with a small proof.

The design of a curve tree is simple and relies on discrete logarithm and the random oracle model (ROM) for its security. A curve tree can be described as a shallow Merkle tree where the leaves are points over an elliptic curve (and so are internal nodes). To hash, at each level we use an appropriately instantiated Pedersen hash alternating curves at each layer (we require a 2-cycle of curves). To prove membership in zero-knowledge we use commit-and-prove² capabilities of Bulletproofs and leverage the algebraic nature of our data structure. Our curves can be instantiated with existing ones in literature (see “Supported Curves” in Section 3.1). A curve tree has structure-preserving fea- + tures[ACD 16] in that we never need to use any combinatorial hash (e.g., SHA) to convert representation of elements at each level or use their bit decomposition. While we focus on accumulators and set membership, our approach can straightforwardly be applied to opening of vectors rather than sets obtaining an “index-hiding” vector commitment.

$$ \mathrm{A C D^{+}16} $$

Using our construction as a building block we can construct a simple and concretely efficient anonymous payment system with full anonymity set³ and transparent setup. We dub this payment system VCash⁴. In VCash, the constraint system used for the zero-knowledge proof of a “spend” transaction is 20x smaller than that in ZCash Sapling (the currently deployed version of ZCash).

$$ \mathrm{s e t}^{3} $$

$$ \mathbb{V}\mathrm{C a s h}^{4} $$

32 Concretely for two inputs/two outputs and anonymity sets of 2 (like in Zcash) our confidential transactions (Vcash) require participants to compute/verify two Bulletproofs proofs of ≈ 5000 constraints each. Verifying each of the proofs in parallel (2 cores) in batches of at least 100 transactions (e.g. when verifying the validity of all transactions in a block) yields a very practical per-transaction verification time of < 10 ms⁵. Transaction sizes are < 3 KB. Our timings are competitive with those of the approach in ZCash Sapling and trade slightly larger proofs (proofs in ZCash are 0.2KB) for a completely transparent setup and simpler curve requirements.

$$ 2^{32} $$

$$ <10~\mathrm{m s}^{5} $$

1.1 Technical Overview

Preliminaries: elliptic-curves and SNARK-native relations In the following we assume that the reader is familiar with elliptic curves (see also Section 3.1 and notation in Section 2.1).

We informally say that a relation is “SNARK-native” to prove for a specific (SNARK) proof scheme if it is can be “naturally represented in the constraint system” (a constraint systems is a representation of a relation we aim to prove). For example, we usually consider Pedersen hashing (and commitments) to be native to Bulletproofs (instantiated in the right curve). In fact we can prove we know the scalar representation ⃗u of a group element P U =_i[u_i] G_ithrough roughly |⃗u| constraints⁶. Notice that for this operation to be actually native, each of the scalars [u_i] should be elements in the scalar field of the curve to which U and the G_i-s belong to.

$$ U=\sum_{i}\left[u_{i}\right]G_{i} $$

$$ \left[u_{i}\right] $$

$$ G_{i}-{\mathrm{S}} $$

Starting point: shallow Merkle trees As a warm up we will ignore zero-knowledge for most of this overview and then show how to account for it. Our starting point are shallow Merkle trees, i.e. Merkle trees with a general d branching factor ℓ ≥ 2. Let us consider a balanced tree of depth d. This has N = ℓ leaves (and it is encoding a set of ′ an equal number of elements). We can represent this tree as labeled. Each internal node v is labeled with the hash H(v₁,...,v_ℓ) of the concatenation of its children; each leaf is labeled by its own value v. The root of this Merkle tree (i) is public and represents the commitment to the set of elements. An internal node rt at level i can be seen as a root to a subtree branching from it. We denote by 0 the “lowest” level, to which the leaves belong, and by d the level to (d) which the root belongs to (so we denote it by rt⁾.

$$ \ell\geq2 $$

$$ N=\ell^{d} $$

$$ v^{\prime} $$

$$ H(v_{1},\ldots,v_{\ell}) $$

$$ r mathrm t{{^(\ i)}} $$

$$ \mathsf{r t}^{(d)}, $$

One of the main advantages of trees with a high branching factor is that we may afford in practice a linear √ 324 dependence on the depth. For a concrete vector size such as N = 2, we can choose ℓ = N = 256 and obtain a depth d = 4.

$$ N=2^{32} $$

$$ \ell=\sqrt[4]{N}=256 $$

$$ d=4 $$

(0) The straightforward approach to opening a leaf v in a Merkle tree opening provides the specific leaf together (i) (0) (i) with the rt-s, the ⁱnternal nodes along the path from v the root, and the sets Siblings⁽rt) of sⁱblings of each

$$ v^{(0)} $$

$$ \mathsf{S i b l i n g s(\mathsf{r t}^{(i)})} $$

$$ \mathsf{r t}^{(i)}{}_{-\mathsf{S}} $$

$$ v^{(0)} $$

² In the sense of the commit-and-prove building blocks in LegoSNARK [CFQ19] and in the work by Lipmaa [Lip16].

³ An anonymity set can be seen as the subset of existing transactions a spent transaction can be narrowed down to. We say that a protocol supports a full anonymity set then it this set consists of the whole history of transactions so far.

⁴ As a reference to both ZCash and Veksel [CHA21] from which it borrows part of its design.

⁵ + We use page 32 in [BBB 17] for our estimates. Our calculations are available at https://gist.github.com/matteocam/ 377832d7b1f86cd0eac81149e9e65bdb.

$$ \mathrm{[B B B^{+}17]} $$

⁶ While this is an informally defined notion, we contrast the Bulletproof example with the approach applying JubJub in Zcash Sapling. The latter is not native for Groth16 instantiated with BLS12-381 as it requires additional constraints for bit decompositions rather than directly describing the multiexponentiation.

⁽ⁱ⁾ rt. This way, anybody can verify membership of the leaf by hashing the siblings at each level. The size of the opening certificate is roughly ℓ · d.

$$ rmathsf{t}^{(i)} $$

We would like to compress the communication complexity even further using SNARKs. However we are looking for better tradeoffs than what we can obtain by “plugging the whole tree opening inside the SNARK” (we discuss this more in the related work).

Our basic blueprint Our high-level solution stems from this insight. Instead of providing all siblings at opening (1) (d) (1) (d)7 time, we can just provide the internal nodes rt*,...,* rt together with short SNARKs π,...,π. Each proof (i) (i) (i) (i+1) (i) ⁽ⁱ⁾ π should show “knowledge of the appropriate siblings”, namely of v₁,...,v such that rt = H⁽v₁,...,v⁾ _ℓ ℓ ⁽ⁱ⁾ (i) (0) (0₎ and rt _is among the v-s ₍denot_ing v by rt).

$$ \mathsf{r t}^{(1)},\ldots,\mathsf{r t}^{(d)} $$

$$ \bar{\mathrm{S N A R K s}};\pi^{(1)},\ldots,\pi^{(d)}\bar{?} $$

$$ \pi^{(i)} $$

$$ \mathsf{r}\mathsf{t}^{(0)}, $$

$$ v{^{(i)}}_{-\mathrm{S}} $$

$$ rmathsf{t}^{(i)} $$

$$ \mathsf{r t}^{(i+1)}=\mathcal{H}(v_{1}^{(i)},\dots,v_{\ell}^{(i)}) $$

$$ v^{(0)} $$

$$ v_{1}^{(i)},\ldots,v_{\ell}^{(i)} $$

Our main challenge is to keep at bay the complexity of proving (and verifying) a hash of size ℓ at each level. In order to go from this general construction to our final concrete one, there are three additional steps:

1.Going from generic hash-functions to towers of elliptic curves

2.Adding zero-knowledge (from hashes to commitments with “select-and-rerandomize”)

3.Going from d to 2 proofs by moving from towers to 2-cycles of elliptic curves.

We now elaborate on each. We stress that, for sake of clarity, we somewhat simplify our explanation and leave out several optimizations we carry out in our final construction. See Section 3 and Section 4 for the actual construction.

Efficient proofs through “tower hashing” In order to obtain an efficient proof of hashing, we would like to apply a hash that is SNARK-native in the sense defined above. Our target will be applying a simple Pedersen vector hashing that is native for Bulletproofs, which is a transparent proof system. We, however, quickly run into an issue: this does not work for more than one level because it is not structure-preserving. An intuition about what we mean by that is: hashing at a single level would be no problem but when, when applied at multiple levels, we would need to hash the output of an earlier hash function. This would not be “native” anymore for the proof system. The problem arises because a Pedersen hash maps field elements to group elements and because we have multiple levels: a parent x of a node—an hash image—will have to be hashed again to produce its own parent—thus being part of a preimage. Node x would need to be a point in the field and in the group at the same time.

In a general version of our solution, we solve this problem by using a different hash function at each level so that we can prove it natively inside Bulletproofs at each level. In order to do this we exploit a tower of curves, with a curve at each different level. We provide more details in Section 3.1. Through this solution we can simply produce a root (i+1) (i) ⁽ⁱ) rt of ℓ chⁱldren v₁,...,v by representing each child as a pair of coordinates (①*,②) ∈ F^pin the base field and ℓ producing a Pedersen hash with 2ℓ* generators in E_q(F_p). We can thus produce a group element H lying in E_q(F_p) and represent it (and its siblings) as pairs in F_q× F_q. At the next level we can do the same using 2ℓ generators in E_r(F_q) for another elliptic curve of order r. And so in the same way till we get to the root. In our concrete solution we will reduce this tower to a 2-cycle and use only two elliptic curves.

$$ \mathfrak{r t}^{(i+1)} $$

$$ v_{1}^{(i)},\ldots,v_{\ell}^{(i)} $$

$$ \big(\mathbb{X},\mathbb{Y}\big)\in\mathbb{F}_{p} $$

$$ \mathbb{E}{q}(\mathbb{F}{p}) $$

$$ \mathbb{E}{q}(\mathbb{F}{p}) $$

$$ \mathbb{F}{q}\times\mathbb{F}{q}. $$

$$ \mathbb{E}{r}(\mathbb{F}{q}) $$

Adding Zero-Knowledge So far we have been concerned with solutions that do not hide which element in the vector we are opening. We actually provided the internal nodes we encounter along the opening path; therefore, in order to make our solution private, we need to modify it so to provide a masking of each of the internal nodes along (i) the opening path. That is, instead of sending the actual internal node rt ⁽the hash of its children), we let the prover ′ (i) (i) ′ sample some fresh randomness [ρ] and send rerandomization (a commitment⁾ cm = rt + [ρ] · H (where h is a group generator). What the verifier should be shown in zero-knowledge at each level is a slight variation on the (i+1) (i) relation we considered before. For level i, Given cm and cm ⁽respectⁱvely, the rerandomized nodes along the (i) (i) ′ path at the next and current level) the verifier should be guaranteed that the prover knows some v₁,...,v, [ρ], [ρ] ℓ i+1 (i) (i) ′ and index j ∈ {1,...,ℓ} such that (a) cm = H₍v₁,...,v, [ρ]) ₍the hash is again a Pedersen hash but now ℓ ′ (i) (i) randomized through [ρ]) and (b) cm = v_j+ [ρ] H. What is important for efficiency is that relation (a)—a multiscalar exponentatiation—can again be proved natively as before. Relation (b)—a single multiplication—needs to be expressed as an arithmetic circuit. This is still relatively inexpensive for us since because it’s performed once per level in a shallow tree.

$$ rmathsf{t}^{(i)} $$

$$ [\rho^{\prime}] $$

$$ {mathsf{c m}}^{(i)}={\mathsf{r t}}^{(i)}+\left|\rho^{\prime}\right|\cdot H $$

$$ \mathsf{c m}^{(i)} $$

$$ j,\in,1,\ldots,\ell} $$

$$ v_{1}^{(i)},\ldots,v_{\ell}^{(i)},\left[\rho\right],\left[\rho^{\prime}\right] $$

$$ \ \ \ a,\mathfrak{c m}^{i+1}=\mathcal{H}(v_{1}^{(i)},\ldots,v_{\ell}^{(i)},[\rho^{\prime}]) $$

$$ [\rho^{\prime}] $$

$$ (b),\mathsf{c m}^{(i)},=,v_{i}^{(i)}+\left[\rho\right]\boldsymbol H{} $$

$$ (a)-\mathrm{a} $$

Optimizing with a 2-cycle and further technical points We optimize our proof size further by applying an observation. We can move from a tower of d curves to only 2-cycle (two curves only). We can use this to reduce our communication complexity since instead of having d proofs—one per level each with a different curve—we can

⁷ We anticipate that our final solution will have reduce to two proofs instead of d.

produce together two proofs—each referring to *d/*2 of the levels. See also Section 4.3 for other optimizations and technical points.

$$ d/2 $$

Vcash: transparent practical anonymous transactions. We use Curve Trees as a main building block in Vcash. We defer the reader to [CHA21] for some high level ideas on the architecture (see in particular Section 1.3). The basic idea is to have the unspent coins in the systems stored as a set S of commitments in an accumulator. At the moment of transferring a coin, a user would prove in zero-knowledge that they own the coin (that is, they know the opening of some element in the set S) and provide a rerandomization of that coin (which also needs to be appropriately proved in zero-knowledge). We describe our construction at the high-level in Section 5.

1.2 Related Work

When comparing to existing approaches to zero-knowledge for set membership we focus on succinctness and prover efficiency.

Some works with transparent setup do not achieve succinctness (that is, practically short proofs and a o(|S|) verification time). For example, Monero [AJ18]—or, generally, approaches based on ring signatures—have proofs linear in the set and where the verifier’s running time is linear in the size of the set |S|.

$$ o(|S|) $$

$$ \mathrm{[A J18]\ o r} $$

Other approaches to accumulator with zero-knowledge properties do not involve general-purpose SNARKs. This + includes for example the multilinear pairing-based polynomial commitment in [BCF 21], the seminal KZG [KZG10] + and the polynomial commitments in [BMM 21]. They, however, all require knowledge-based assumptions and a + trusted setup. Similar observations hold for the recent work in Caulk[ZBK 22].

$$ [\mathrm{B C B}^{+}21] $$

Other works apply asymptotically efficient polynomial commitments with a transparent setup, but their commit- + ment and proof size are concretely large. This is the case of Hyrax [WTs 18], where for large set sizes commitments can be ≫ 10KB, and Dory [Lee21] where commitments are 190 bytes (6-7 times larger than ours). Proofs of single opening are also large (18 KB) in Dory, although the scheme can amortize this cost with batching (expect for very large opening batches this amortized proof size is still significantly higher than ours). The Spartan proof system has overall opening sizes, proving and verification time that are competitive with respect to ours (for sets up to 20 approximately 2 where Spartan starts to perform worse), but it has very high commitment sizes, e.g. ≥ 20KB 20 8 for sets of size 2 (625*×* worse than ours). Other transparent polynomial commitments include those based on Reed-Solomon IOPs [BBHR18] or on Diophantine ARguments of Knowledge (DARK) [BFS20]. As argued in [Lee21] (Section 1.1) they achieve worse concrete performances than the works above in practice.

$$ |\mathrm{W s}^{+}18| $$

$$ \gg10K B $$

$$ 2^{20} $$

$$ \mathrm{e.g.},\geq,20K B $$

$$ 2^{20} $$

Works that apply specialized proving techniques on accumulators in unknown-order groups: Veksel, [CHA21,

• • CHA22, BCF 21, CFH 21]. These works obtain concretely small proofs/verifier with an efficient proving time, but
• require an RSA modulus (non-transparent) for their efficient instantiations⁹. While the work in [CFH 21] obtains concretely efficient proving time with a slightly larger proof size in ZCash but it require trusted setup to instantiate its proof system in addition to RSA modulus.

$$ \mathrm{C F H^{+}21]} $$

$$ [\mathrm{C F H^{+}21}] $$

Using “friendlier” hash functions for Merkle trees mitigates the complexity of proving an opening. One such + example is Poseidon [GKR 21]. The limitation of these solutions is that they rely on hash functions which are quite new and have not received the proper cryptanalytic scrutiny yet.

$$ [\mathrm{G K R^{+}2]} $$

Comparing our accumulator to transparent Algebraic Merkle Trees. The most interesting comparison to our (zero-knowledge) accumulator construction is a “transparent” version of that used in ZCash. Here, for to show membership in a set we apply a specific type of Merkle tree. In it, the collision-resistant hash function we use at each level has an extra property and in particular we require it to be “algebraic” (that is it can be expressed as a polynomial in a ring). A natural choice for this—and the one applied in ZCash—is Pedersen hash. In order to prove membership we apply a zkSNARK to the opening of the Merkle tree. For this approach to be efficient we need that 10 the group in which we compute the hash is tied to the group in which the zkSNARK “functions”. ZCash uses Groth16 on curve BLS12-381 [Gro16] as a zkSNARK and a specific curve for hashing, JubJub. Nonetheless, this approach could be made transparent by applying Bulletproofs on the Ristretto curve and choosing an appropriate elliptic curve for hashing (this includes for example Jabberwock in [CHA21]). In the remainder of this comparison we refer to this way of transparently instantiating Merkle trees with Pedersen hash as AlgMT_BP.

$$ \mathsf{A l g M}mathsf\overline{{T}}_{\mathrm{B P}} $$

⁸ See [Lee21] for numbers referred in this section.

⁹ In all these works we can replace the RSA group with a transparent class-group [BH01], substantially increasing their complexity. See, e.g., discussion in [DGS20]

¹⁰ More specifically, this means that elliptic curve of the zkSNARK should be of order related to that of the definition field of the elliptic curve we use for Pedersen hashing.

We now compare the approach in our work to that in AlgMT_BP. Let us denote by N the set size. First we observe that asymptotically AlgMT^BPrequires performing log₂(N) hash computations with 2 elements each (one per level of 32 tree, hence log₂(N)) inside the SNARK. Concretely, for a representative choice of N = 2 to ≈ 45000 constraints. Our construction, on the other hand, requires ≈ 5000 constraints (almost an order of magnitude less).

$$ A\vert{\sf g M M}_{\mathrm{B P}} $$

$$ \ \mathsf{A g M!_{B P}} $$

$$ \log_{2}(N) $$

$$ \log_{2}(N)) $$

$$ N=2^{32}\ \mathrm{t o}\approx45000 $$

Comparing to Verkle Trees. At the very high-level, our approach resembles the currently explored “Verkle Tree” (VT) approach in Ethereum¹¹. In both approaches an internal node represents a vector commitment to its children. The two approaches have a few substantial differences. First, that approach is currently not structure-preserving in the sense ours is. Each node is a commitment to a hash (e.g., SHA or Blake) of the children. This is required to solve a similar problem to that we approach with towers of curves. Currently Verkle Trees do no account for zero-knowledge (our focus in this work). If they did, we would also need to show in zero-knowledge that hashing the children has been performed correctly. For example, in the case of Blake this would require 20K additional constraints per level¹² (our solution, on the other hand, is in the ballpark of 5K constraint in total). Another difference is that the current implementation uses KZG polynomial commitments [KZG10] which requires a trusted setup.

13 Curve trees and Halo2. Halo2 is a concrete transparent (zero-knowledge) proof system that uses recursion. It is concretely efficient and it obtains recursion by going back and forth in a cycle of two curves. Halo2 and curve trees have orthogonal goals: one is a full-fledged proof system, the other can be seen as a specialized data structure (and related constraint system) for zero-knowledge for set membership. We see, however, great potential in combining the techniques in these two systems and we are currently working in this direction.

2 Preliminaries

2.1 Notation

We denote by E[F] the elliptic curve E defined over the field F, whenever clear from context we might omit the field of definition and simply write E. Whenever possible we explicitly mark scalar elements through square brackets and group elements with upper case letters (we will occasionally break this convention if not important). We denote by M(R) an upper bound (by construction) on the multiplicative complexity of verifying the relation R. In practice, when estimating performance, the latter is the primary metric when proving satisfiability of arithmetic circuits.

When expressing an NP relation R(x,w) we make the private witness w explicit as such but we keep the public statement x implicit. For example, in the relation R below z

$$ R(x,w) $$

$$ \mathcal {R} := \left{z: y = \mathrm {S H A} \left(g ^ {z}\right) \right} $$

the only private witness is z, while g and y are considered publicly known inputs.

2.2 Commitments

We use the following syntax for commitments:

Definition 1(Commitments). A commitment scheme C is a pair of algorithms (Setup*,*Comm) with syntax:

λ – Setup(1) → ck : generates a commitment key ck*;*

$$ -{\mathrm{\sf ettup}}(1^{\lambda})\to{\sf {ck}} $$

– Comm(ck*,m*; r) → c_m: produces commitment com_mto message m with randomness r.

$$ c o m_{m} $$

$$ -\mathsf{C o m m}(\mathsf{c k},m;r)\to c_{m} $$

As it is standard, we call message space the set of of m-s for which Comm is defined and commitment space its range, Rng(Comm). We require commitments to be perfectly hiding—the distribution of Comm(ck*,m*; r) is identical to the uniform distribution over the commitment space—and computationally binding—no efficient adversary can produce ′ ′ ′ ′ ′ two pairs (m,r), (m,r) such that m ̸= m and Comm(ck*,m*; r) = Comm(ck*,m*; r).

$$ \mathsf{C o m m}(\mathsf{c k},m;r) $$

$$ (m,r),(m^{\prime},r^{\prime}) $$

$$ m\neq m^{\prime} $$

$$ \sf{C o m m}(c,m;r)=C o m(c,k;m^{\prime};r^{\prime}) $$

Remark 1(Rerandomizable Commitments). We will use rerandomizable commitments, i.e., endowed with an algo- ′ ′ ′ ′ rithm Rerand(ck*,Comm(ck,m*; r)) → (c,r) such that c = Comm(ck*,m*; r + r). Notice that homomorphic commitments (and thus Pedersen commitments) satisfy this property.

$$ (\mathsf c k,\mathsf{C o m m}(\mathsf c k k,r))\to\big(c^{\prime},r^{\prime}\big) $$

$$ c^{\prime}=\mathsf{C o m m}(c\mathsf{k},m;r+r^{\prime}) $$

¹¹ https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html

¹² https://github.com/zcash/zcash/issues/2258

¹³ https://electriccoin.co/blog/explaining-halo-2/

2.3 Accumulators

Definition 2(Accumulator scheme). An accumulator scheme Acc over universe U_λ(Acc) (where λ is a security parameter) consists of PPT algorithms Acc = (Setup*,Accum,PrvMem,*VfyMem) with the following syntax:

$$ \mathcal{U}_{\lambda}(\mathsf{A c c}) $$

^λ Setup(1) → (pp) generates public parameters pp*.*

$$ {\mathsf{S e t u p}}(1^{\lambda})\to({\mathsf{p p}}) $$

Accum(pp*,S*) → A deterministically computes accumulator A for set S ⊆U_λ(Acc).

$$ {\mathsf{A c c u m}}({\mathsf{p p}},S)\to A $$

$$ S\subseteq\mathcal{U}_{\lambda}(\mathsf{A c c}) $$

PrvMem(pp*,S,x*) → W computes witness W that proves x is in accumulated set S.

$$ (\mathsf{p p},S,x)\to W $$

VfyMem(pp*,A,x,W*) → b ∈{0,1} verifies through witness whether x is in the set accumulated in A. We do not require parameter x to be in U_λ(Acc) from the syntax.

$$ (\mathrm {p p}, A, x, W) \rightarrow b \in {0, 1 } $$

$$ \mathcal{U}_{\lambda}(\mathsf{A c c}) $$

An accumulator scheme should satisfy correctness—the accumulator works as expected—and soundness—no effi- cient adversary can choose a set S and then find a witness that checks on Acc*.Accum(pp,S*) and x ̸∈ S¹⁴.

$$ e\mathcal{N}.cdot $$

$$ x\not\in S^{14} $$

2.4 NIZKs

Non-Interactive Zero-Knowledge schemes (or NIZKs) require a reference string which can be either uniformly sampled (a urs), or structured (a srs). In the latter case it needs to be sampled by a trusted party. In this work we use and assume transparent NIZKs, i.e. whose algorithms use a reference string urs sampled uniformly.

$$ \Re={\mathfrak{R}{\lambda}}{\lambda\in\mathbb{N}} $$

Definition 3. A NIZK for a relation family R = {R_λ}_λ∈Nis a tuple of algorithms ZK = (Prove*,*VerProof) with the following syntax:

$$ \mathsf{Z K}=(\mathsf{P r o v e},\mathsf{V e r P r o f f}) $$

– ZK*.Prove(urs,R,x,w*) → π takes as input a string urs*, a relation description R, a statement x and a witness w* such that R(x,w); it returns a proof π.

$$ R,x,w)\to\pi $$

$$ R, $$

$$ R(x,w) $$

$$ \pi $$

– ZK*.VerProof(urs,R,x,π*) → b ∈{0,1} takes as input a string urs*, a relation description R, a statement x and a* proof π; it accepts or rejects the proof.

$$ (\operatorname {u r s}, R, x, \pi) \rightarrow b \in {0, 1 } $$

We require a NIZK to be complete, that is, for any λ ∈ N*,R ∈* R and (x,w) ∈ R it holds with overwhelming poly(λ) probability that VerProof(urs*,R,x,π*) where urs ←$ {0,1} and proof π ← Prove(urs*,R,x,w*).

$$ \lambda\in\mathbb{N},R\in\mathfrak{R} $$

$$ (x,w),\in,R $$

$$ \pi\gets\mathsf{P r o v e}(\mathsf{u r s},R,x,w) $$

$$ \leftarrow\ \ {mathfrak s1}^{\mathsf{p o l y}(\lambda)}} $$

We also require knowledge-soundness and zero-knowledge to hold. Informally, the former states we can efficiently “extract” a valid witness from a proof that passes verification; the latter states that the proof leaks nothing about the witness (this is modeled through a simulator that can output a valid proof for an input in the language without knowing the witness). We use variants of these notions with certain composability properties, e.g. requiring auxiliary inputs and relation generators. For a full formal treatment of these, we refer the reader to Sections 2.2 and 2.5 in [BCFK19].

$$ 2.5 $$

Whenever the relation family is obviously defined, we talk about a “NIZK for a relation R”.

$$ R^{\ } $$

Remark 2(Relations and Public Inputs). In the algorithms above we have both a relation R and a public input x as inputs. The reason is that in a soundness experiment, R may be constrained to be from a certain distribution on R whereas x can be be chosen arbitrarily by the adversary. See for example Section 2.2 in [BCFK19]. In our constructions we often assume prover and verifier to implicitly take as input the relation description¹⁵.

In the proof of security of our construction we require an additional property for one of our NIZKs, simulation- extractability. Namely, extractability should hold even with respect to an adversary that has access to simulated proofs. We refer the reader to [Gro06] for formal definitions.

Modular NIZKs through Commit-and-Prove. We use the framework for black-box modular composition of commit-and-prove NIZKs (or CP-NIZKs) in [CFQ19] and [BCFK19]. Informally a CP-NIZK is a NIZK that can efficiently prove properties of committed inputs through some commitment scheme C. Let x be a public input and c a commitment. Such a scheme can for example prove knowledge of (u,ω,r) such that c = Comm(u; r) and that relation R_inner(x;u,ω) holds. We can think of ω as a non-committed part of the witness. Besides the proof, the verifier’s inputs are x and c.

$$ (u,\omega,r) $$

$$ R_{\mathrm{i n n e r}}(x;u,\omega) $$

$$ c=\mathsf{C o m m}(u;r) $$

In our construction we will make use of the following folklore composition to obtain efficient NIZKs from CP- ′ NIZKs. Fixed a commitment scheme and given two CP-NIZKs CP*,CP respectively for two “inner” relations R and ′ ∗ ′ ′ ′ ′ ^′ R, we can prove their conjunction (for a shared witness u) R (x,x,u,ω,ω) = R(x,u,ω)∧ R* (x,u,ω) like this: the ′ prover commits to u as c ← Comm(u,r); generates proofs π and π from the respective schemes; it outputs combined ∗ ′ ′ ′ proof π := (c,π,π). The verifier checks each proof over respective inputs (x,c) and (x,c).

$$ R^{\prime},. $$

$$ \mathsf{C P},\mathsf{C P}^{\prime} $$

$$ R^{*}(x,x^{\prime},u,\omega,\omega^{\prime})=R(x,u,\omega)\wedge R^{\prime}(x^{\prime},u,\omega^{\prime}) $$

$$ \pi^{*}:=(c,\pi,\pi^{\prime}) $$

$$ c\leftarrow\mathsf{C o m m}(u,r) $$

$$ \pi^{\prime} $$

$$ (x,c) $$

$$ (x^{\prime},c^{\prime}) $$

The following theorem (informally stated) is a direct consequence of Theorem 3.1 in [CFQ19].

¹⁴ These definitions are standard and we refer the reader to [BBF19] for a formal treatment. ¹⁵ This parameter is usually short.

Theorem 1(Black-Box Composition of CP-NIZKs). The construction above is a secure NIZK for the con- ∗ junction relation R.

$$ R^{*} $$

• We can see Bulletproof [BBB 18] as a CP-NIZK since it works efficiently over an implicit commitment representation (see discussion in [CFQ19]). We use this fact in our instantiations.

3 Curve Trees as Accumulators

3.1 Towers of Elliptic Curves

We call a sequence of elliptic curves E₁(F_p1),...,E_n(F_pn) a tower, iff. for i ∈ [1,n − 1] : p_i= |E_i+1(F_pi+1)|; in other words the field of E_i(F_p1) is the scalar field of E_i+1(F_p+1). We will generally let the field of definition be implicit to simplify notation. Towers of curves have previously been used to optimize the proving of cryptographic operations in + zkSNARKs [KZM 15] [HBHW21], which will also be the application in this paper. Additionally the same techniques has been applied for recursive proofs systems [BCTV14] [BGH19]. We will not require that any of the curves are pairing friendly.

$$ \mathbb{E}{1}(\mathbb{F}{p_{1}}),\ldots,\mathbb{E}{n}(\mathbb{F}{p_{n}}) $$

$$ i\in[1,n-1]:p_{i}=|\mathbb{E}{i+1}\ \ \ {left\ {\mathbb{F}}{p_{i+1}}\ \ \ }; $$

$$ \mathbb{E}{i}(\mathbb{F}{p_{1}}) $$

$$ \mathbb{E}{i+1}(\mathbb{F}{p+1}) $$

Cycles of Elliptic Curves. Of particular interest are m-cycles of elliptic curves: infinitely long towers where E_i(F_pi) = E_i+m(F_pi+m) for all i. Most commonly m = 2, which will be the primary case of interest in this paper as well.

$$ \mathbb{E}{i}(\mathbb{F}{p_{i}})=\mathbb{E}{i+m}(\mathbb{F}{p_{i+m}}) $$

$$ m=2 $$

3.2 The Accumulator: (ℓ, E₁, . . . ,Ed)-Curve Tree

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d})\mathrm{-C u r v e~T r e e} $$

Our accumulation scheme is a “Curve Tree”: a Curve Tree can be seen as an ‘algebraically compatible’ Merkle tree which uses a Pedersen commitments over E₁*,...,*E_das the compression function for each level respectively. Notice that below we use a “randomness” scalar [r]. This will be useful for several concrete aspects of our construction described in the next section.

$$ \mathrm{T r e e{}} $$

$$ \mathbb{E}{1},\ldots,\mathbb{E}{d} $$

Definition 4(Curve Trees). A Curve Tree, parameterized by a branching factor ℓ and a tower of Elliptic curves E₁*,...,*E_dhas the following recursive structure:

$$ \mathbb{E}{1},\ldots,\mathbb{E}{d} $$

Leaf: (ℓ, E₁)−CurveTree: A (ℓ, E₁)-Curve Tree (leaf node) is a 3-tuple (C,0,C) where C ∈ E₁*: a tree containing C* with root C.

$$ (\ell,\mathbb{E}_{1}) $$

$$ (C,0,C) $$

$$ C\in\mathbb{E}_{1}. $$

Parent: (ℓ, E₁*,...,E_d)−CurveTree: A (ℓ, E₁,...,E_d)-Curve Tree is a 3-tuple* (C, r, (T₁, ..., T_ℓ)), where T₁,...,T_ℓ are (ℓ, E₁*,...,E_d−1)-Curve Trees, i.e.* ˆ₁ ˆ₁ ˆ ˆ

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d}) $$

$$ 4\ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d}) $$

$$ (C,,r,,(T_{1},,\ldots,,T_{\ell})) $$

$$ T_{1},\ldots,T_{\ell} $$

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d-1}, $$

$$ T _ {1} = \left(\hat {C} _ {1} = \left(\mathrm {x} _ {1}, \mathrm {y} _ {1}\right), \hat {r} _ {1}, \hat {T} _ {1}\right), \dots , T _ {\ell} = \left(\hat {C} _ {\ell} = \left(\mathrm {x} _ {\ell}, \mathrm {y} _ {\ell}\right), \hat {r} _ {\ell}, \hat {T} _ {\ell}\right) $$

The root C of the (ℓ, E₁*,...,E_d)-Curve Tree is a Pedersen commitment to the coordinates of the children:*

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d}) $$

$$ C=\langle\vec{\varkappa},\vec{G}^{(d,X)}\rangle+\langle\vec{\varkappa},\vec{G}^{(d,Y)}\rangle+[r]\cdot H^{(d)} $$

⃗(d,X)⃗(d,Y) ℓd (d) For constants G, G ∈ E and H ∈ E^d.

$$ \vec{G}^{(d,X)},\vec{G}^{(d,Y)}\in\mathbb{E}_{d}^{\ell} $$

$$ H^{(d)}\in\mathbb{E}_{d} $$

3.3 Supported Curves.

Since we only require the hardness of discrete log, the techniques described in this paper are broadly applicable to any tower of curves and in particular existing cycles of elliptic curves, e.g. the “Pasta Cycle” (Pallas / Vesta curves) [Hop20], the “Tweedle Cycle” (Tweedledum / Tweedledee curves) [Hop19] or the Secp256k1 / Secq256k1 curves cycle [Poe18]. Even though our techniques do not use bilinear pairing, security of our zero-knowledge accumulator holds even in the presence of an efficiently computable bilinear map (type I, type II or type III) on one/both of the curves – enabling interoperability of our techniques with proof systems over such cycles.

$$ \mathrm{y c c l e}^{\mathrm{??}} $$

4 Zero-Knowledge Set Membership in Curve Trees

In this section we describe how to prove set membership in zero knowledge for our curve trees accumulators. We use

• • a slightly more specific version of the relation for zero knowledge for set membership in, e.g., [BCF 21, CFH 21]. Our variant (dubbed “Select-and-Rerandomize”) obtains stronger unlinkability properties and is described below. We
• • stress that our construction can be straightforwardly adapted to fit the setting in [BCF 21, CFH 21] where the commitment to the element is already given and there is no need for rerandomization. √

$$ \mathrm{[B C F^{+}21} $$

$$ \mathrm{C F H^{+}21]} $$

$$ [ \mathrm {B C F} ^ {+} 2 1 $$

d Our final scheme achieves O(logn) communication an_d O( n) computation where d is the depth of the tree and n is the size of the accumulated set.

$$ O(\sqrt[d]{n}) $$

$$ O(\log n n) $$

Fig. 1. Illustration of a (4*,E₁,E₂,*E₃)-Curve Tree. Hatch pattern circles indicates that the point is represented as a field element, rounded rectangles represents Pedersen commitments to the field elements (circles) inside. Darker shades indicates lower levels in the tree.

$$ (4,\mathbb{E}{1},\mathbb{E}{2},\mathbb{E}_{3}) $$

4.1 “Select-and-Rerandomize” Accumulators

Here we define an auxiliary interface for a primitive we call a “select-and-rerandomize accumulator”. Given an accumulator of committed values, I can provide you with a handle (a commitment) to a value in the accumulated set proving to you it is in the set but without revealing which one it is. We achieve this through rerandomization of commitments and zero-knowledge proofs over the set membership relation and commitment rerandomization. This primitive is natural in several settings, such as in anonymous payment systems, including the one in this work and in [CHA21]. Similar attempts at having hiding for accumulator witnesses (with different techniques) also appeared + in [CFH 21].

Below we assume an accumulator scheme and an accumulated set S whose elements are (rerandomizable) commitments. We also denote by pp the concatenation of the accumulator parameters and the commitment key.

$$ {\mathcal{P}}({\mathfrak{p p}},S,c)\to\left(c^{\prime},\pi,r^{\prime}\right) $$

′ ′ SelRerand*.P*(pp*,S,c*) → (c,π,r) returns a rerandomized commitment (of c ∈ S), a proof of membership and the (auxiliary) randomness used for rerandomization.

$$ c\in S) $$

′ ′ SelRerand*.V*(pp*,A,c,π*) → 0*/*1 verifies that c is a rerandomization of an element in the set.

$$ {\mathcal{V}}({\mathsf{p p}},A,c^{\prime},\pi)\to0/1 $$

$$ c^{\prime} $$

Correctness: For any set S, c ∈ S (with c an honestly generated commitment), honestly generated parameters pp = (pp_acc*,*ck) the following holds

$$ \beta,,c\in\beta $$

$$ {\mathsf{p p}}=({\mathsf{p p}}_{\mathrm{a c c}},{\mathsf{c k}}) $$

$$ \operatorname {S e l R e a n d}. \mathcal {V} (\mathrm {p p}, \operatorname {A c c u m} \left(\mathrm {p p} _ {\mathrm {a c c}}, S\right), c ^ {\prime}, \pi) = 1 \wedge c ^ {\prime} = \operatorname {R e r a n d} \left(\mathrm {c k}, c; r ^ {\prime}\right) $$

′ ′ where SelRerand*.P*(pp*,S,c*) → (c,π,r).

$$ {\mathcal{P}}{{\big(}{\mathfrak{p p}},S,c{{\big)}}\to{\big(}c^{\prime},\pi,{{\big)}}{.}} $$

Security (informal): we require the proof π to be an extractable NIZK (i.e., we require knowledge soundness and zero-knowledge) for the relation below: ()

$$ \pi $$

$$ \mathcal{R}^{(\mathsf{S e l e c t R e r a n d})}:=\left{(W,c,r):\begin{matrix}{c^{\prime}=\mathsf{R e r a n d}(\mathsf{c k},c;r^{\prime})}\ {\wedge\ \mathsf{A c c.N I y M M m}(\mathsf{p p}_{\operatorname{a c c}},A,c,W)}\ \end{matrix}\right} $$

whenever the parameters and the accumulator have been generated honestly.

4.2 Constructing Select-and-Rerandomize in Curve Trees

The main intuition is as follows. Observe that the leafs of a (ℓ, E₁*,...,*E_d)-Curve Tree are curve points on E₁. These leafs are going to be Pedersen commitments to secret vectors. We exploit the recursive algebraic structure of our tree to enable efficient zero-knowledge proofs of knowledge of these vectors. A crucial feature of Curve Trees is that the roots (and that of every sub-tree) are rerandomizable commitments to Curve Trees: by rerandomizing the root

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d}) $$

$$ \mathbb{E}_{1} $$

′ (d) C as C ← C + [δ] · H we obtain a perfectly hiding commitment to the same set of children as the original tree, we exploit this observation to traverse the tree level-by-level using a simple zero-knowledge proof described in the next section. Another property of curve trees is that the height can dynamically increase as the number of elements in the tree grows: by using a cycle of curves the tree can grow “upward” while the leaves remain E₁ points.

$$ C^{\prime}\leftarrow C+[\delta]\cdot H^{(d)} $$

$$ \ {mathbb E_{1}} $$

Rerandomized Curve Tree

Fig. 2. Illustration of the “select and rerandomize relation”. In the example illustrated above i = 4 and j = 3. Note that Cˆ is one layer deeper in the tree.

$$ i=4 $$

$$ j=3 $$

$$ \hat{C} $$

4.2.1 Single-Level Select-and-Rerandomize The central component in our construction is a simple construction for a select-and-rerandomize-like relation for a single level in a curve tree (we later recursively invoke this to obtain a full select-and-rerandomize in Section 4.2.2). Its underlying relation takes as input a rerandomized commitment Cˆ, an alleged parent C and hidden indexes (the root of a (ℓ, E₁*,...,E)-Curve Tree), secret index i whose d semantics is “Cˆ is the i-th child of C”. Practically, this is accomplished by opening the commitment C to ⃗①,⃗② using ˆ = (①(d−1) a Pedersen commit-and-prove over E_d,* then rerandomizes the i’th point Ci, ②_i) + [δ] · H ∈ E_d−1. Slightly more formally we require a zero-knowledge argument of knowledge for the following relation: ()

$$ \hat{C} $$

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d})\mathrm{\ \ C u r v e\ T r e e}) $$

$$ \mathrm {i s} “ \hat {C} $$

$$ C^{\ } $$

$$ \vec{\mathbb{X}},\vec{\mathbb{Y}} $$

$$ \mathbb{E}_{d}. $$

$$ \hat{\mathcal{C}}=\left(\mathbb{X}{i},\mathbb{Y}{i}\right)+\left[\emptyset\right]\cdot H^{(d-1)}\in\mathbb{E}_{d-1} $$

$$ \mathcal{R}^{(\mathsf{I-L u v C C r T})}:=\left{(i,r,\delta,\vec{\mathtt{x}},\vec{\mathtt{y}}):\begin{aligned}{}&{{}C=\langle\vec{\mathtt{x}},\vec{X^{(t)}}\rangle+\langle\vec{\mathtt{y}},\vec{Y^{(t)}}\rangle+[r]\cdot H^{(d)}}\ {}&{{}\wedge\ \hat{C}=(\mathtt{x}{i},\mathtt{y}{i})+[\delta]\cdot H^{(d-1)}}\ \end{aligned}\right} $$

(d) (d) (d) As noted the C = ⟨⃗①*, X⃗ ⟩* +⟨⃗②*, Y⃗ ⟩+ [r]· H* constraint can be very efficiently enforced using a commit-andprove for Pedersen commitments (e.g. Bulletproofs or Compressed Σ-Protocol) over E. While Cˆ = (①*,* ②) + [δ] · d i i ^(d−1) H requires a single fixed-based exponentiation “inside the circuit”. We describe an optimized arithmetic circuit for the relation above in Appendix B.

$$ \mathcal{C}=\langle\vec{\mathbb{X}},\vec{X^{(d)}}\rangle+\langle\vec{\mathbb{Y}},\vec{Y^{(d)}}\rangle+\left[[\{{}boldsymbol{r}}\right]!\cdot!!{\boldsymbol{H}}^{(d)} $$

$$ \bar{\mathbf H{}}^{left({d-1})} $$

$$ \mathbb{E}d_{} $$

$$ \hat {C} = \left(\mathrm {x} _ {i}, \mathrm {y} _ {i}\right) + [ \delta ] $$

In the appendix we describe a generalization of this relation to the “forest” case where we do not have only one root but several roots (this can be used for a flatter construction described in Remark 3).

√ d (1-Lvl-CrvT) 4.2.2 Recursive n Membership Proof. We can observe that R already yiel_ds a “one-level” selectand-rerandomize. We can apply it one level at the time and obtain a full construction. Note that in the single-level case, at a given level we can provide a (hiding) Pedersen commitment of one of the children. The latter in turn represents the root of a (sub-)Curve Tree. We can thus extend the technique presented to obtain membership proofs √ √ d d with O( n) prover/verifier complexity: by letting ℓ = n and using d − 1 individual proofs and η = 1 (except √ d possibly for the first proof which sets η = n). The proofs then descends down the Curve Tree one level at a time.

$$ \sqrt{n} $$

$$ \mathcal{R}^{\ {mathsf((1L v-C v v T)}} $$

$$ O(\sqrt[d]{n}) $$

$$ \ell={\sqrt[d]{n}} $$

$$ d-1 $$

$$ \eta=1 $$

$$ \eta=\sqrt[d]{n}) $$

Theorem 2(informal). The construction in Section 4.2.2 is select-and-rerandomize over curve trees as accumula- √ d tors with O( n) prover/verifier complexity. This construction is transparent if we instantiate the underlying NIZK with Bulletproofs.

$$ O(\sqrt[d]{n})} $$

$$ i f $$

$$ \mathcal{V}(\mathsf{p p},\mathsf{r t},c^{},\pi^{}) $$

$$ \mathcal {P} \left(\mathrm {p p}, S, c ^ {*}\right) $$

$$ \pi^{*} $$

$$ \left(\hat{c}^{(1)},\ldots,\hat{c}^{(d)},\pi^{(1)},\ldots,\pi^{(d)}\right) $$

$$ c^{*} $$

$$ {\operatorname{L e t}}\ c^{(0)},\ldots,c^{(d)} $$

$$ \hat{c}^{(0)}:=\mathsf{r t} $$

$$ j=1,\ldots,d $$

$$ \mathrm{(w i t h};c^{(0)} $$

$$ j=1,\ldots,d $$

$$ b _ {j} \leftarrow \mathrm {Z K}. \operatorname {V e r P r o o f} (\mathrm {p p}, \mathcal {R} ^ {(1 - \mathrm {L v l} - \mathrm {C r v T})}, \hat {c} ^ {(j - 1)}, \hat {c} ^ {(j)}) $$

$$ (\hat{c}^{(j)},r^{(j)})\leftarrow\mathsf{R e r a n d}(\mathsf{c k},c^{(j)}) $$

$$ \hat{c}^{(0)}:=\mathsf{r}\mathrm{a n d}r^{(0)}:=0 $$

$$ \pi_{j}\xleftarrow{}\mathsf{Z K.P r o v e(p p,}\mathcal{R}^{(\ -\mathsf{L w v-C r v T})},\hat{c}^{(j-1)},\hat{c}^{(j)},\mathit{r}^{(j)},\mathit{r}^{(j)},\mathit{r}^{(j-1)}) $$

$$ \begin{array}{r l}{\bigwedge}&{{}b_{j}=1}\end{array} $$

$$ \scriptstyle{j=1,...,}\ell $$

$$ \pi^{*}:=\left(\hat{c}^{(1)},\ldots,\hat{c}^{(d)},\pi^{(1)},\ldots,\pi^{(d)}\right) $$

Fig. 3. Select-and-rerandomize for a (ℓ, E₁*,...,Ed*)*−*CurveTree

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d}) $$

The theorem above can be proved straightforwardly by invoking Theorem 1 at each level in the tree. Zeroknowledge follows straightforwardly by the rerandomization of the commitments and the zero-knowledge of the underlying NIZK.

4.3 Optimizations

In this section, we briefly cover some straightforward optimizations.

Merging Proofs. The approach above which necessitates a total of d − 1 individual proofs π₁,...,π_d−1. However, when using a (2) cycle of curves, all the even/odd proofs are over the same curve/field and can therefore be combined in to a single larger statement; only requiring 2 proofs in total for any d.

$$ \pi_{1},\ldots,\pi_{d-1} $$

Point Compression / Permissible Points. In the setting where the accumulator is guaranteed to have been computed honestly (e.g. in our confidential transactions application), we can reduce the number of exponentiations during committing and the size of the witness by only committing to the ①-coordinate of the children: this remains binding by ensuring that only one of (①*,②) and (①, −*②) is “allowed”. One common choice is to take the numerically smallest between ② and *−*②, or discriminate based upon the parity (even/odd) over Z, however neither of these constraints can be efficiently expressed as an arithmetic circuit; instead we use a universal hash function. Let S(v) = 1 iff. v ∈ F is a quadratic residue (i.e. there exists w ∈ F st. w² = v) and S(v) = 0 otherwise. Now consider the following family of 2-universal hash functions from any field to {0,1}:

$$ (\mathrm {x}, \mathrm {y}) $$

$$ \left(\mathbb{X},-\mathbb{y}\right) $$

$$ S(v)=1 $$

$$ v\in\mathbb{F} $$

$$ w\in\mathbb{F},\mathrm{s t}.,w^{2}=v) $$

$$ S(v)=0 $$

$$ {0,1} $$

$$ \mathcal{U}_{\alpha,\beta}(v):\mathbb{F}\rightarrow{0,1} $$

$$ \mathcal{U}_{\alpha,\beta}(v)\mapsto S(\alpha\cdot v+\beta) $$

Observe that the constraint U_α,β(v) = 1 can be enforced using a circuit with multiplicative complexity 1, showing {(w) : w² = (α · v + β)}. We exploit this to efficiently define a set of “permissible points” on E:

$$ \mathcal{U}_{\alpha,\beta}(v)=1 $$

$$ {(w):w^{2}=\big(\alpha\cdot v+\beta\big)_{\cdot} $$

$$ \mathcal {P} _ {\mathbb {E}} = \left{\left(\mathrm {x}, \mathrm {y}\right) \mid (\mathrm {x}, \mathrm {y}) \in \mathbb {E} \left(\mathbb {F} _ {p}\right) \wedge \mathcal {U} _ {\alpha , \beta} (\mathrm {y}) = 1 \wedge \mathcal {U} _ {\alpha , \beta} (- \mathrm {y}) = 0 \right} $$

Note that¹/4 of the points on E are permissible and any (①,②) ∈P is uniquely defined by its ①-coordinate – this E is the case for any finite field of characteristic ∈{ / 2,3}. Any Pedersen commitment C can be “made permissible” by simply adding H (“incrementing the randomness”) until the point is permissible:

$$ (\mathtt{X},\mathtt{Y})\in\mathcal{P}_{\mathbb{E}} $$

$$ ^1/4 $$

$$ \mathbb{E} $$

$$ \notin{2,3} $$

$$ \begin{aligned}{}&{{}\frac{\mathsf{M a k e P e r m i s s i b l e}(C):\mathbb{E}\to\mathcal{P}{\mathbb{E}}}{1:\quad\mathsf{w h i l e}\ C\notin\mathcal{P}{\mathbb{E}}:C\leftarrow C+H}}\ {}&{{}\quad2:\quad\mathbf{r e t u r n}\ C}\ \end{aligned} $$

In expectation, this requires 4 curve additions and 8 square roots. By enforcing that only permissible points are (SelectRerand) added to the accumulator¹⁶ so that the “decompression” is unique, we can reduce the complexity of R slightly, instead showing:  

$$ \mathcal{R} $$

$$ \mathcal{R}^{(\mathsf{1-L u V-C n T T})}:={\begin{matrix}{C=\langle\vec{\mathtt{x}},\vec{X^{(t)}}\rangle+[r]\cdot H^{(d)}}\ {}\end{matrix} $$

(t) Note the (①_i*,②) ∈P_E(t) constra_int only requires a check that (①i,*②⁾ ∈ E in addi^tion to Uα,β(②) = 1. We include the full circuit description in Appendix B.

$$ \big(\mathtt{x}{i},\mathtt{y}\big)\in\mathcal{P}{\mathbb{E}^{(t)}} $$

$$ \big(\mathtt{x}_{i},\mathtt{y}\big)\in\mathbb{E}^{(t)} $$

$$ \mathcal{U}_{\alpha,\beta}(\mathtt{y})=1 $$

5 VCash: Transparent and Efficient Anonymous Payment System

In this section we informally describe our anonymous payment system, which we dub VCash. The techniques and model here follow mostly prior work; we defer extended and formal details to the final version of this paper.

Like ZCash our construction supports the largest possible anonymity set at every transaction. On the other hand, our scheme has an additional leakage: a party S sending a transaction tx to a party R can learn when R will spend the coins received in tx (but not to whom). Only sender S can infer this.

5.1 Model

The flow of our protocol roughly follows known blueprints. We defer the reader to Section 3 and 6 and Appendix D in [CHA21, CHA22] for a formal description of a closely related model. One important difference with the formal description in Veksel, however, is that we do not assume parties to hold accounts. Instead, in VCash (as in Zcash) a transaction pours pairs of input coins into pairs of output coins of equivalent value.

Intuition about the model: at any given moment in time, each party holds a certain number of coins¹⁷ Each user is also holding a state roughly containing all the transfers occurred so far. Through the state, any user can verify the validity of each transfer and used to verify the validity of each.

Components of the model:

Setup The setup algorithm produces the initial parameters of the system. We emphasize that it does not require to be run by a trusted setup.

Pouring A sender S can “pour” the value of two input coins into two new output coins nullifying the input ones. The recipients of the two new coins can be distinct. It is possible for S itself to be one or both of the recipients. We require that the total value of input and output coins is the same.

Verifying and Processing We provide a verifying algorithm by which parties can check a transfer is valid (roughly that the sender could afford it) and processing algorithm by which parties can update their state after a transfer. Although we describe them separately for clarity they are run together in our formal construction in ??.

5.2 Construction

Again we defer the reader to the technical overview and Section 3 in [CHA21, CHA22] for further background. Here we provide high-level details.

A transaction consist of the creation of output coins from input coins. A coin roughly consists of a commitment to its amount and other information that ensures it will be used only once and by its intended recipient.

For a transaction to be valid it must be the case that:

1.Output coins are in an appropriate non-negative range (we want to give money and not take it in a transaction); 2.the total value of input and output coins is the same;

¹⁶ In case of our anonymous cryptocurrency application, this is enforced by the network of block validators: as a condition for a transaction being valid.

¹⁷ “Holding” a coin requires knowing a certain secret key associated with the user. In this section we ignore the aspect of registering with a new key to the system, but we stress it is straightforward to add.

3.input coins “exist” and are valid themselves.

We use zero-knowledge proofs to ensure the above. The first two properties can be ensured by range proofs and homomorphic properties of Pedersen commitments respectively. The last property is where we can use our selectand-rerandomize constructions from the previous sections. All coins are stored in an accumulator. When I want to spend an input coin I can select-and-rerandomize it obtaining a rerandomized version of that coin. Now I can include that in my transaction to prove this is the rerandomization of something existing in the accumulator.

Other aspects of the system (e.g., nullifiers) can be implemented straightforwardly (e.g. through public key rerandomization) and have small impact on the concrete efficiency of our construction; we do include these costs in our evaluation.

5.3 Concrete Efficiency

In VCash, the constraint system used for the zero-knowledge proof of a “spend” transaction is 20x smaller than that in ZCash Sapling (the currently deployed version of ZCash).

32 Concretely for two inputs/two outputs and anonymity sets of 2 (like in Zcash) our confidential transactions (Vcash) require participants to compute/verify two Bulletproofs proofs of ≈ 5000 constraints each. Verifying each of the proofs in parallel (2 cores) in batches of at least 100 transactions (e.g. when verifying the validity of all transactions in a block) yields a very practical per-transaction verification time of < 10 ms. Transaction sizes are < 3 KB. Our timings are competitive with those of the approach in ZCash Sapling and trade slightly larger proofs (proofs in ZCash are 0.2KB) for a completely transparent setup and simpler curve requirements.

References

⁺ ACD 16.Masayuki Abe, Melissa Chase, Bernardo David, Markulf Kohlweiss, Ryo Nishimaki, and Miyako Ohkubo. Constantsize structure-preserving signatures: Generic constructions and simple assumptions. Journal of Cryptology, 29(4):833–878, October 2016. AJ18.Kurt M. Alonso and Jordi Herrera Joancomartí. Monero - privacy in the blockchain. Cryptology ePrint Archive, Report 2018/535, 2018. https://eprint.iacr.org/2018/535. ⁺ BBB 17.Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. Cryptology ePrint Archive, Report 2017/1066, 2017. https: //eprint.iacr.org/2017/1066. ⁺ BBB 18.Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy, pages 315–334. IEEE Computer Society Press, May 2018. BBF19.Dan Boneh, Benedikt Bünz, and Ben Fisch. Batching techniques for accumulators with applications to IOPs and stateless blockchains. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 561–586. Springer, Heidelberg, August 2019. BBHR18.Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast reed-solomon interactive oracle proofs of proximity. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 14:1–14:17. Schloss Dagstuhl, July 2018. ⁺ BCF 21.Daniel Benarroch, Matteo Campanelli, Dario Fiore, Kobi Gurkan, and Dimitris Kolonelos. Zero-knowledge proofs for set membership: Efficient, succinct, modular. In Nikita Borisov and Claudia Diaz, editors, Financial Cryptog- raphy and Data Security, pages 393–414, Berlin, Heidelberg, 2021. Springer Berlin Heidelberg. BCFK19.Daniel Benarroch, Matteo Campanelli, Dario Fiore, and Dimitris Kolonelos. Zero-knowledge proofs for set membership: Efficient, succinct, modular. Cryptology ePrint Archive, Report 2019/1255, 2019. https://eprint.iacr. org/2019/1255. BCTV14.Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Scalable zero knowledge via cycles of elliptic curves. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II, volume 8617 of LNCS, pages 276–294. Springer, Heidelberg, August 2014. BFS20.Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK compilers. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 677–706. Springer, Heidelberg, May 2020. BGH19.Sean Bowe, Jack Grigg, and Daira Hopwood. Halo: Recursive proof composition without a trusted setup. Cryptology ePrint Archive, Report 2019/1021, 2019. https://eprint.iacr.org/2019/1021. BH01.Johannes Buchmann and Safuat Hamdy. A survey on iq cryptography. In Public-Key Cryptography and Compu- tational Number Theory, pages 1–15, 2001. ⁺ BMM 21.Benedikt Bünz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, and Psi Vesely. Proofs for inner pairing products and applications. In International Conference on the Theory and Application of Cryptology and Information Security, pages 65–97. Springer, 2021. ⁺ CFH 21.Matteo Campanelli, Dario Fiore, Semin Han, Jihye Kim, Dimitris Kolonelos, and Hyunok Oh. Succinct zeroknowledge batch proofs for set accumulators. Cryptology ePrint Archive, Report 2021/1672, 2021. https://ia. cr/2021/1672. CFQ19.Matteo Campanelli, Dario Fiore, and Anaïs Querol. LegoSNARK: Modular design and composition of succinct zero-knowledge proofs. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 2075–2092. ACM Press, November 2019. CHA21.Matteo Campanelli and Mathias Hall-Andersen. Veksel: Simple, efficient, anonymous payments with large anonymity sets from well-studied assumptions. Cryptology ePrint Archive, Report 2021/327, 2021. https: //ia.cr/2021/327. CHA22.Matteo Campanelli and Mathias Hall-Andersen. Veksel: Simple, efficient, anonymous payments with large anonymity sets from well-studied assumptions. In Proceedings of the 2022 ACM on Asia Conference on Com- puter and Communications Security, pages 652–666, 2022. ⁺ CHI 20.Megan Chen, Carmit Hazay, Yuval Ishai, Yuriy Kashnikov, Daniele Micciancio, Tarik Riviere, abhi shelat, Muthu Venkitasubramaniam, and Ruihan Wang. Diogenes: Lightweight scalable RSA modulus generation with a dishonest majority. Cryptology ePrint Archive, Report 2020/374, 2020. https://eprint.iacr.org/2020/374. DGS20.Samuel Dobson, Steven D. Galbraith, and Benjamin Smith. Trustless groups of unknown order with hyperelliptic curves. Cryptology ePrint Archive, Report 2020/196, 2020. https://eprint.iacr.org/2020/196. ⁺ GKR 21.Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. Poseidon: A new hash function for zero-knowledge proof systems. pages 519–535. USENIX Association, 2021. Gro06.Jens Groth. Simulation-sound nizk proofs for a practical language and constant size group signatures. In Interna- tional Conference on the Theory and Application of Cryptology and Information Security, pages 444–459. Springer, 2006. Gro16.Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305–326. Springer, Heidelberg, May 2016.

Archive, Report 2015/1093, 2015. https://ia.cr/2015/1093. https://ia.cr/2015/1093

GW20.Ariel Gabizon and Zachary J. Williamson. plookup: A simplified polynomial protocol for lookup tables. Cryptology ePrint Archive, Report 2020/315, 2020. https://eprint.iacr.org/2020/315. GWC19.Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953, 2019. https: //eprint.iacr.org/2019/953. HBHW21.Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. Zcash protocol specification, version 2021.2.16 [nu5 proposal], 2021. Hop19.Daira Hopwood, 2019. https://github.com/daira/tweedle. Hop20.Daira Hopwood, 2020. https://github.com/zcash/pasta. KZG10.Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, pages 177–194. Springer, Heidelberg, December 2010. ⁺ KZM 15.Ahmed Kosba, Zhichao Zhao, Andrew Miller, Yi Qian, Hubert Chan, Charalampos Papamanthou, Rafael Pass, abhi shelat, and Elaine Shi. C*∅c∅*: A framework for building composable zero-knowledge proofs. Cryptology ePrint Archive, Report 2015/1093, 2015. https://ia.cr/2015/1093. Lee21.Jonathan Lee. Dory: Efficient, transparent arguments for generalised inner products and polynomial commitments. In Theory of Cryptography Conference, pages 1–34. Springer, 2021. Lip16.Helger Lipmaa. Prover-efficient commit-and-prove zero-knowledge SNARKs. In David Pointcheval, Abderrahmane Nitaj, and Tajjeeddine Rachidi, editors, AFRICACRYPT 16, volume 9646 of LNCS, pages 185–206. Springer, Heidelberg, April 2016. ⁺ LRR 19.Russell W. F. Lai, Viktoria Ronge, Tim Ruffing, Dominique Schröder, Sri Aravinda Krishnan Thyagarajan, and Jiafan Wang. Omniring: Scaling private payments without trusted setup. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 31–48. ACM Press, November 2019. Poe18.Andrew Poelstra, 2018. https://moderncrypto.org/mail-archive/curves/2018/000992.html. ₊ WTs 18.Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish. Doubly-efficient zkSNARKs without trusted setup. In 2018 IEEE Symposium on Security and Privacy, pages 926–943. IEEE Computer Society Press, May 2018. ⁺ ZBK 22.Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, and Mark Simkin. Caulk: Lookup arguments in sublinear time. Cryptology ePrint Archive, Paper 2022/621, 2022. https://eprint.iacr. org/2022/621.

A Forest Single-Level Select-and-Rerandomize

Here we describe a slight generalization of the relation in Section 4.2.1. Its underlying relation takes as input hidden indexes j ∈ [η], i ∈ [ℓ] and η public roots of a forest of (ℓ, E₁*,...,E^d)-Curve Trees C₁,..., C^η∈* E^d. In this context we also assume a root Cˆ of a (ℓ, E₁*, ...,* E)-Curve Tree which is a (known¹⁸) rerandomization of one of the children d−1 of C₁,..., C^η∈ E^d. Practically, this is accomplished by opening the j’th commitment C_jto ⃗①*,⃗② using a Pedersen ˆ = (①(d−1) commit-and-prove over E_d,* then rerandomizes the i’th point Ci, ②_i)+[δ]· H ∈ E_d−1. Slightly more formally we require a zero-knowledge argument of knowledge for the following relation: ()

$$ j\in[\eta],i\in[\ell] $$

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d})\mathrm{\ \ C C u} $$

$$ \mathcal{C}{1},...,\mathcal{C}{\eta}\in\mathbb{E}_{d} $$

$$ \hat{C} $$

$$ (\ell,\mathbb{E}{1},\ldots,\mathbb{E}{d-1}). $$

$$ \small\begin{aligned}{C_{1},:...,:C_{\eta}\in\mathbb{E}_{d}}\ \end{aligned} $$

$$ \ {vec X,\ }{{\vec{\ }} $$

$$ \mathbb{E}_{d}, $$

$$ \hat {C} = \left(\mathrm {x} _ {i}, \mathrm {y} _ {i}\right) + [ \delta ] \cdot H ^ {(d - 1)} \in \mathbb {E} _ {d - 1} $$

$$ \mathcal {R} ^ {(1 - \mathrm {L v l} - \mathrm {C r v T} - \mathrm {F r s t})} := \left{(i, j, r, \delta , \vec {\mathbf {x}}, \vec {\mathbf {y}}): \begin{array}{l} C _ {j} = \langle \vec {\mathbf {x}}, \vec {X} ^ {(\vec {t})} \rangle + \langle \vec {\mathbf {y}}, \vec {Y} ^ {(\vec {t})} \rangle + [ r ] \cdot H ^ {(d)} \ \wedge \hat {C} = (\mathbf {x} _ {i}, \mathbf {y} _ {i}) + [ \delta ] \cdot H ^ {(d - 1)} \end{array} \right} $$

√ ⁽¹-Lvl-CrvT-Frst) Remark 3(Simple n√Membership Proof). Note that R immediately provides a very simple mem- √ bership proof with O( n) prover/verifier complexity using η (ℓ, E₁*,E₂)-Curve Trees and letting η = ℓ = n: to ˆ(1) prove that a Pedersen commitment C = C_q+ [δ] · H ∈ E₁ is a rerandomization of a commitment from the (1) (1) (1) (1) (1) (1)√(2) list C₁ = (①₁,* ②₁),...,C_n= (①_n, ②_n) ∈ E₁. Let η = ℓ = n and for each i ∈ [η] compute: C_i= (1) (1) (1) ₍₁₎ ⟨⃗①*,X ⟩* + ⟨⃗②*,Y ⟩* i.e. commit to each chunk of ℓ children individually. Since the size of the [(i−1)·ℓ: i·ℓ] [(i−1)·ℓ: i·ℓ] “select and rerandomize” relation above is O(η + ℓ), by applying a proof system with (quasi)-linear verification time √ we obtain a membership proof with Oe( n) complexity.

$$ \sqrt{n} $$

$$ \mathcal{R}^{(1mathrm-v r T-F r s t)} $$

$$ O({\sqrt{n}}) $$

$$ \eta{\ \ (}ell,\mathbb{E}{1},\mathbb{E}{2}{} $$

$$ \eta=,\ell,=,{\sqrt{n}} $$

$$ \hat{\mathcal{C}},=,\mathcal{C}{q}+[\delta]\cdot\mathcal{H}^{(1)},\in,\mathbb{E}{1} $$

$$ C _ {1} ^ {(1)} = \left(\mathrm {x} _ {1} ^ {(1)}, \mathrm {y} _ {1} ^ {(1)}\right), \dots , C _ {n} ^ {(1)} = \left(\mathrm {x} _ {n} ^ {(1)}, \mathrm {y} _ {n} ^ {(1)}\right) \in \mathbb {E} _ {1} $$

$$ C_{i}^{(2)}\ = $$

$$ \langle\vec{\mathbb{X}}{[(i-1)\cdot\ell:i\cdot\ell]}^{(1)},X^{(1)}\rangle+\langle\vec{\mathbb{Y}}{[(i-1)\cdot\ell:i\cdot\ell]}^{(1)},Y^{(1)}\rangle $$

$$ i\ \in\ [\eta] $$

$$ \eta,=,\ell,=,{\sqrt{n}} $$

$$ O(\eta+\ell) $$

B Circuit Specifications

$$ \widetilde{O}({\sqrt{n}}) $$

Remark 4(Custom Gates). We keep the explication of our techniques as broadly applicable as possible: working for any elliptic curve on short wierstrass form and any commit-and-proof system for Pedersen commitments. However, the circuits in this section can be further optimized for particular curves (e.g. with non-trivial efficient endomorphisms) and proof systems (e.g. Plonk [GWC19] with custom gates for elliptic curve operations, and/or, Plookup [GW20]).

¹⁸ In terms of extraction.

We provide all circuit specifications as Rank-1 constraints systems (R1CS): the left side of any constraint consists of a product (×) of affine combinations, while the right side consists of an affine combination.

B.1 2-Set Membership

To constrain w ∈{v₁,v₂}, enforce the following R1CS constraint:

$$ w\in{v_{1},v_{2}} $$

$$ \left(w boldsymbol v-\boldsymbol{}boldsymbol v{}{1}\right)\times\left(\boldsymbol w\boldsymbol{}-\boldsymbol{}v{2}\right)=0 $$

(1)

Most commonly w ∈{0,1} (i.e. v₁ = 0 and v₂ = 1).

$$ v_{1}=0 $$

$$ w \in {0, 1 } $$

$$ v_{2}=1) $$

B.2 Not Zero

To enforce v ̸= 0, introduce t₁ and constrain:

$$ v\neq0 $$

$$ \mathbb{U}_{1} $$

(2)

$$ \mathtt{t}_{1}\times v=1 $$

B.3 Curve Check

For a point P = (①*,②) ∈ E(F), introduce t₁,*t₂ and constraints:

$$ P=(\mathtt{x},\mathtt{y})\in\mathbb{E}(\mathbb{F}) $$

$$ \mathbb{t}{1},\mathbb{t}{2} $$

(3)

$$ \mathbb{X}\times\mathbb{X}=\mathbb{t}_{1} $$

$$ \mathtt{X}\times\mathtt{t}{1}=\mathtt{t}{2} $$

(4)

$$ \mathbb{y}\times\mathbb{y}=\mathbb{t}_{2}+A\mathbb{x}+B $$

(5)

B.4 Incomplete Curve Addition

We denote by incomplete addition on the short Weierstrass curve E, formally:

$$ \begin{array}{l} \mathbb {E} \cup {\bot } \because \mathbb {E} \cup {\bot } \rightarrow \mathbb {E} \cup {\bot } \ \perp \because_ {-} \mapsto \perp \ _ {-} \because \bot \mapsto \bot \ 1 \because_ {-} \mapsto \perp \ _ {-} \because 1 \mapsto \perp \ P \because - P \mapsto \bot , P \in \mathbb {E} \ P \because P \mapsto \bot , P \in \mathbb {E} \ P \because Q \mapsto P + Q, P \in \mathbb {E}, Q \in \mathbb {E}, O t h e r w i s e \ \end{array} $$

In other words: for points (①₁, ②₁),(①₂, ②₂) ∈ E(F) the operation is undefined when ①₁= ①₂(and undefined on points not on the curve) or when one of the operands is the point at infinity. For three points (witnesses) (①₁, ②₁),(①₂, ②₂),(①₃, ②₃) we enforce (①₃, ②₃) = (①₁, ②₁) (①₂, ②₂), by introducing a free variable for the slope δ and the 3 constraints:

$$ \big(\mathtt{X}{1},\mathtt{Y}{1}\big),\big(\mathtt{X}{2},\mathtt{Y}{2}\big),\in,\mathbb{E}\big(\mathbb{F}\big) $$

$$ \mathrm {x} _ {1} = \mathrm {x} _ {2} $$

$$ \big(\mathtt{X}{1},\mathtt{Y}{1}\big),\big(\mathtt{X}{2},\mathtt{Y}{2}\big),\big(\mathtt{X}{3},\mathtt{Y}{3}\big) $$

$$ \left(\mathbb{X}{3},\mathbb{Y}{3}\right)=\left(\mathbb{X}{1},\mathbb{Y}{1}\right)\because\left(\mathbb{X}{2},\mathbb{Y}{2}\right) $$

(6)

$$ \delta\times\left(\mathbb{X}{2}-\mathbb{X}{1}\right)=\mathbb{Y}{2}-\mathbb{Y}{1} $$

$$ \delta\times\left(\mathbb{X}{3}-\mathbb{X}{1}\right)=-\mathbb{Y}{3}-\mathbb{Y}{1} $$

(7)

(8)

$$ \delta\times\delta=\mathtt{x}{3}+\mathtt{x}{1}+\mathtt{x}_{2} $$

B.5 Checked Curve Addition

When exceptional cases may occur, we can check for these by enforcing distinct ①-coordinates. i.e. to enforce:

$$ \left(\mathbb{X}{3},\mathbb{Y}{3}\right)=\left(\mathbb{X}{1},\mathbb{Y}{1}\right)+\left(\mathbb{X}{2},\mathbb{Y}{2}\right) $$

Enforce the constraints:

$$ \mathbb{X}{1}\neq\mathbb{X}{2} $$

(9)

$$ \left(\mathbb{X}{3},\mathbb{X}{3}\right)=\left(\mathbb{X}{1},\mathbb{Y}{1}\right)\div\left(\mathbb{X}{2},\mathbb{Y}{2}\right) $$

(10)

B.6 Secret 3-Bit Lookup

2 An n-dimensional secret lookup in a constant table, i.e. v = T [b₀ + 2 · b₁ + ² · b₂] for secret b₀,b₁,b₂ ∈{0,1}⊆ F n n aⁿd v ∈ F with T : N₈ → F. For a table T : N₈ → F the lookup requires 5 R1CS constants:

$$ v=T[b_{0}+2\cdot b_{1}+2^{2}\cdot b_{2}] $$

$$ b_{0},b_{1},b_{2}\in{0,1}\subseteq\mathbb{F} $$

$$ vboldsymbol\in\mathbb{F}^{n} $$

$$ T:\mathbb{N}_{8}\to\mathbb{F}^{n} $$

$$ T:\mathbb{N}_{8}\rightarrow\mathbb{F} $$

$$ b_{0}\in{0,1} $$

(11)

$$ b_{1}\in\left{0,1\right} $$

(12)

$$ b_{2}\in\left{0,1\right} $$

$$ b_{&}=b_{1}\times b_{2} $$

(13)

(14)

$$ b_{0}\times\left(\begin{matrix}{-T_{0}\cdot b_{k}+T_{0}\cdot b_{2}+T_{0}\cdot b_{1}-T_{0}\cdot b_{k}}\ {-T_{2}\cdot b_{1}+T_{4}\cdot b_{k}-T_{1}\cdot b_{2}-T_{6}\cdot b_{k}}\ {+T_{1}\cdot b_{k}-T_{1}\cdot b_{2}-T_{1}\cdot b_{1}+T_{1}-T_{3}\cdot b_{k}}\ {+T_{3}\cdot b_{1}-T_{3}\cdot b_{k}+T_{5}\cdot b_{2}+T_{7}\cdot b_{k}}\ \end{matrix}\right)=\begin{matrix}{T_{b}-T_{0}\cdot b_{k}+T_{0}\cdot T_{2}+T_{0}\cdot b_{1}-T_{0}\cdot b_{k}}\ {-T_{2}\cdot b_{1}+T_{4}\cdot b_{k}-T_{4}\cdot b_{2}-T_{6}\cdot b_{k}}\ \end{matrix} $$

n In general, for tables T : N₈ → F the technique above requires 4 +n constaints: repeating the last constaint for each additional coordinate.

$$ T:\mathbb{N}_{8}\to\mathbb{F}^{n} $$

B.7 Circuit for Fixed-Base Exponentiation

Abusing notation, we write (˜①*,* ②˜) = (①*,②) T for the constraint: (˜①,* ②˜) = (①*,②) (ˆ①,* ②ˆ) and (ˆ①*,* ②ˆ) ∈ T. Multiplying a constant curve point by a secret scalar is implemented by decomposing the scalar into 3-bit windows (b₀,b₁,b₂) and defining the tables T st. the exceptional cases does not occur (except for the last table – where we use the checked version). Let m = ⌊λ/3⌋ + 1, for for i ∈ 1*,...,m −* 1, define the table T_ias:

$$ \left(\tilde{\mathbb{X}},\tilde{\mathbb{y}}\right)=\left(\mathbb{X},\mathbb{y}\right)!!!\therefore! $$

$$ \left(\tilde{\mathbb{X}},\tilde{\mathbb{y}}\right)=\left(\mathbb{X},\mathbb{y}\right)\vdots\cdot\left(\tilde{\mathbb{X}},\hat{\mathbb{Y}}\right) $$

$$ \left(\hat{\mathbb{X}},\hat{\mathbb{Y}}\right)\in T $$

$$ (b_{0},b_{1},b_{2}) $$

$$ m=\lfloor\lambda/3\rfloor+1 $$

$$ i\in1,\ldots,m-1 $$

$$ T_{i} $$

$$ T _ {i} = \left{\left[ j \cdot 2 ^ {3 \cdot i} + 2 ^ {3 \cdot (i + 1)} \right] \cdot H \mid j \in 0, \dots , 2 ^ {3} - 1 \right} $$

Define T_mas follows:

$$ T_{m} $$

$$ T_{m}=\left{\left[j\cdot2^{3\cdot m}-\sum_{i=1}^{m-1}2^{3\cdot i}\right]\cdot H\ \Big|\ j\in0,\ldots,2^{3}-1\right} $$

To enforce (˜①*,* ②˜) = [r] · H + (①*,*②), we express it as:

$$ \left(\tilde{\mathbb{X}},\tilde{\mathbb{y}}\right)=\left[\boldsymbol{r}\right]\cdot\boldsymbol{H}+\left(\mathbb{X},\mathbb{y}\right) $$

$$ (\tilde{\mathtt{x}},\tilde{\mathtt{y}})=\mathsf{R e r a n d}(\mathtt{x,mathtt{y}}):=(\tilde{\mathtt{x}},\tilde{\mathtt{y}})=(\mathtt{x,,\mathtt{y}})+(T_{m}+(T_{m-1}\ ::\ (T_{m-2}\ \ :\ (\dots))) $$

(15)

And decompose with witness r ∈ Z_|⟨H⟩|as

$$ r\in\mathbb{D}_{|\langle H\rangle|} $$

$$ r=\sum_{i}v_{i}\cdot2^{3i} $$

B.8 Range Check

i A range check for v ∈ [0*,*2) requⁱres i constraints:

$$ v\in[0,2^{i}) $$

$$ \forall\ b_{i}\in{0,1} $$

(16)

$$ v=\sum_{i}2^{i}\cdot b_{i} $$

(17)

B.9 Selection

Selecting a single secret entry (hidden index) from a secret vector:

$$ \mathtt{x}=\mathtt{S e l e c t}(\vec{\mathtt{X}}):={(\mathtt{x},\vec{I},\vec{\mathtt{X}}):\forall j:I_{j}\in{0,1}\wedge\mathtt{x}={\sum_{j=1}}\mathtt{X}{i}\cdot I{i}\wedge1={sum\sum_{j=1}I_{j}}} $$

B.10 Spending Relation

The spending relation consists of a relation for each curve in the tower of curves (see Section 3.1). Below we describe the spending relation for a two cycle of curves (E*,* Eˆ). The spending relation for the commit-and-prove over E:

$$ \operatorname {S p e n d} (\mathrm {v}, \mathrm {p k}, C _ {1}) := \left{\left(\left(\vec {\mathbb {X}} _ {i}, \hat {\mathbf {x}} _ {i}, \hat {\mathbf {y}} _ {i}\right) _ {i \in 1, \dots , d / 2}, \mathrm {v}\right): \right. $$

// Open commitment to vector of ①-coordinates

$$ \tt{R o o t}=C_{1}=(x_{1},y_{1})=C\ m{m i t}(\vec{X_{1}}) $$

(18)

$$ \hat{\sf{x}}{1}={\sf S e l e c t}(\vec{\sf{X}}{1})\qquad\qquad\qquad\quad\mathrm{\ //S e l e c ta~c o o r d i n a t e.} $$

(19)

$$ (\hat{\mathsf{x}}{1},\hat{\mathsf{y}}{1})\in\mathcal{P}_{\hat{\mathsf{B}}}\qquad\qquad\qquad\qquad\qquad\qquad\ \ \ /\ \mathrm{}{\bf}\mathrm{}{\bfD e c o m p r o s st op e r m i s s i b l ep o i n t.} $$

// Rerandomize inner commitment.

(20)

$$ \hat{\mathcal{C}}{1}=\left(\hat{\mathbb{X}}{1}^{\prime},\hat{\mathbb{Y}}{1}^{\prime}\right)=\mathsf{R e r a n d}\ (\hat{\mathbb{X}}{1},\hat{\mathbb{Y}}_{1}) $$

(21)

$$ \vdots $$

(22)

$$ C _ {d / 2 - 1} = \left(\mathrm {x} _ {d / 2 - 1}, \mathrm {y} _ {d / 2 - 1}\right) = \operatorname {C o m m i t} \left(\mathbb {X} _ {d / 2 - 1} ^ {\rightarrow}\right) $$

$$ \hat{\mathbb{X}}{d/2-1}=\mathsf{S e l e c t}(\vec{\mathbb{X}{d/2-1}}) $$

(23)

(24)

$$ \left(\hat{\mathbb{X}}{d/2}-1,\hat{\mathbb{Y}}{d/2}-1\right)\in\mathcal{P}_{\hat{\mathbb{E}}} $$

$$ \hat{C}{d/2-1}=\big(\hat{\mathbb{X}}{d/2-1}^{\prime},\hat{\mathbb{Y}}{d/2-1}^{\prime}\big)=\mathsf{R e r a n d}\big(\hat{\mathbb{X}}{d/2-1},\hat{\mathbb{Y}}_{d/2-1}\big) $$

(25)

$$ \hat{C}_{d/2}=\mathsf{C o m m i t(p k,v)}\qquad\qquad $$

(26)

Note that pk is a part of the statement (public input). The spending relation for the commit-and-prove over Eˆ :

$$ \left{((\vec{\mathbb{X}}{i},\mathtt{x}{i},\mathtt{y}{i}){i\in1,\ldots,d/2}):\right. $$

$$ \hat{\mathbb{E}} $$

$$ \begin{array}{r l}{\hat{C}{1}=\big(\hat{\vec{x}}{1},\hat{\vec{y}}{1}\big)=\sf{C o m m i t}(vec\ {{Xcalcal}}{1})\qquad\qquad\int,p\ mathrm p p e n\ c o m m i t m e n t\ t o\ v e c t o r\ o f\ x\ c o o r d i n a t e s}&{{}\qquad\qquad\ \ mid,,,,}\end{array} $$

(27)

$$ \ _11\ =\ {\sf S e l e c t}(\overrightarrow{x_11}) $$

(28)

$$ (\mathtt{x}{1},\mathtt{y}{1})\in\mathcal{P}_{\mathbb{R}} $$

(29)

$$ C C_{1}=(\tt{1{}^{\prime}},\tt y{1}^{\prime})=\ \ R{r r r a n d}(\tt x_{1},\tt y_{1})\qquad\qquad/\ R{{{\ mathrm e r}}n d o m i z e\ i n n e r\ c o m m i t m e n t}. $$

(30)

$$ \hat{C}{d/2}=\left(\hat{\mathbb{X}}{d/2},\hat{\mathbb{Y}}{d/2}\right)=\mathsf{C o m m i t}(\vec{\mathbb{X}}{d/2}) $$

(31)

$$ \mathbb{X}{d/2}=\mathsf{S e l e c t}(\vec{\mathbb{X}{d/2}}) $$

(32)

$$ \big(\mathtt{X}{d/2},\mathtt{Y}{d/2}\big)\in\mathcal{P}_{\mathbb{E}} $$

(33)

$$ \left. C _ {d / 2} = \left(\mathbb {x} _ {d / 2} ^ {\prime}, \mathbb {y} _ {d / 2} ^ {\prime}\right) = \operatorname {R e r a n d} \left(\mathbb {x} _ {d / 2}, \mathbb {y} _ {d / 2}\right)\right} $$

(34)

The statement (public input) is defined by x = (pk*,* (C, Cˆ) d). Note that C₁ = Root is the root of the Curve i i i∈1,..., /2 Tree containing all prior transaction outputs.

B.11 Minting Relation

$$ x=\left(\operatorname{p k},(C_{i},\check{C}{i}){i\in1,\ldots,d/2}\right) $$

$$ C_{1}={\mathsf o o t} $$

The mintining relation is only over E and consists of a range check:

$$ {mathsf\mathsf M i n t}(\mathsf{v},\mathsf{p k},C):={(\mathsf{v},\mathsf{p k}): $$

(35)

$$ C=\mathsf{C o m m i t(,,k k)} $$

(36)

$$ \mathsf{V}\in[0,2^{64})\big} $$

(37)

Note that the pk is part of the witness.

B.12 2-to-2 UTXO Relation

The 2-to-2 UTXO relation consists of two instances of the spending relation, two instances of the minting relation and a check that the balances (minus a transaction fee) match.

$$ \sf{U T X O}o(\sf{R o o t},C_{o u t1},C_{o u t2}):={(sf v v_{i n1},v_{i n2},v_{o u t1},v_{o u t2},p k_{o u t1},p k_{o u t2}):} $$

(38)

$$ \mathsf{M i n t}(mathsf{v}{\mathsf{o u t1}},\mathsf{p k}{\mathsf{o u t1}},\mathsf{C}_{\mathsf{o u t1}}) $$

(39)

$$ \ i\ t\ i(v_{o u t2},p k_{o u t2},C_{o u t2}) $$

(40)

(41)

$$ \mathsf{S p e n d(v_{i n1},p k_{i n1},R o o t)} $$

$$ \mathsf{S p e n d(v_{i n2},p k_{i n2},R o o t)} $$

(42)

$$ v_{i n1}+v_{i n2}=v_{o u t1}+v_{o u t2}+v_{f e e} $$

(43)

Note that pk_in1and pk_in2are public, while pk_out1and pk_out2are part of the witness.

$$ \mathrm{p k}_{\mathsf{i n1}} $$

$$ \mathrm{p k}_{\mathsf{i n2}} $$

$$ \mathrm{p k_{o u t1}} $$

$$ \mathrm{p k_{o u t2}} $$