Following the example of "PoDLE" in Joinmarket - it is very likely that many potential applications will want multiple usages available per (u)txo/pubkey. For this reason it makes sense to do:

• J = hash(application-specific-label, counter)

(see #7 for some related concepts)

... where counter is just an incrementing integer (or anything similar). For now, this is already technically possible if both sides are prepared to fold the counter into the label; messy but it works.

An interesting practical point here: if we have to check a given token against multiple counters, does it degrade performance too much? I think the answer is no: this calculation is completely orthogonal to the (expensive) curve tree construction and the (cheap but non-zero) curve tree proof verification. That can be done first, and then we can simply iterate the Ped-DLEQ proof verification with different counters (exactly as is done in Joinmarket), because it's very cheap/quick.

Currently using hex, needs to be WIF (indeed, absent wallet integration, there is no version of this that isn't at the very least inconvenient, but raw hex 32 byte privkeys, while in some ways appropriate because only taproot is supported, are even more ridiculously inconvenient for anyone who isn't a bitcoin developer ...).

Both the original paper and the code assume that the input elements of the set used as leaves of the curve tree are already permissible points.

Thus if your input values (curve points) are not permissible, converting them to permissible is "left as an exercise for the reader", so to say.

However the conversion of points created as the tree is traversed, into permissible, is handled in the code using this simple algorithm:

define f(pt):
while (pt is not permissible)
  pt = pt + H
return pt

where H is the generator for the randomness of the Pedersen commitment.

This function f is not viable as a hash of the initial public key for the leaf, however, since it isn't in any sense a cryptographic hash - it doesn't have second preimage resistance. Speaking less fancily, if the value of f(P) is P+3H, then clearly the value of f(P+H) is also P+3H. So we have second preimages.

Does this matter? I think the answer is similar to the concern in #2 , i.e. it is not a problem for the full protocol including Ped-DLEQ but it may or may not be a problem for other protocols using a Curve Tree.

If H is generated as NUMS, which it must be, then the user does not know the private key of P+H (staying in the hypothetical scenario where f() changes P to P+3H, so P+H is a second preimage, as are P+2H and P+3H), so if the algorithm here includes a proof of knowledge of the private key of P, which it does in the form of the Ped-DLEQ attached protocol, then this second preimage cannot be used to create an overall valid proof.

All the same it is worth considering whether an alternative function to the f() described above, might be better, if it avoid such preimages.

The proving time is currently dominated by the call to create_permissible_points_and_randomness. Sample data:

Depth 2, branching factor 1024:
250K keys, total proving time 48s, CPPR call 31s
795K keys, total proving time 148s, CPPR call 103s

Notice that the CPPR call is roughly linear, and the rest of the operation is sublinear (though it probably could be better). But also, CPPR is not part of the proving time at all, it is a preprocessing step, necessary for keys derived from real world usage (like Bitcoin, nostr, etc.) that are not chosen automatically to be permissible (and in line with the philosophy of this project, which is to allow "spontaneous" proof creation, we do not expect non-users of the protocol to choose their pubkeys to suit our use-case).

To convert the code into rough English, the permissible_point function in permissible.rs in the Curve Trees repo, takes a given point on the curve (though it is called a "commitment" note that we dont' need it to have a blinding property at the leaves of the tree, for this use case; we pass through the pubkey directly), then increments +H, +2H, +3H,... until a permissible point is reached as checked by running the Universal Hash. As noted in the paper, there is a 1 in 4 chance, roughly, of a point being permissible by chance so we expect about 4 re-calculations on average.

Investigation is needed into how and to what extent this overhead can be reduced.

My best guess is that the culprit is a combination of 2 things: 1/ the factor of 4 mentioned above and 2/ the field operations required in each one of those steps for checking permissibility, as found in the is_permissible function call.

If there isn't an obvious way to optimize that, this overhead might be unavoidable - either way, as has been noted, this overhead is and must be linear, even if we make it small. However, as it is a preprocessing step, it could be cached upfront, or perhaps "streamed" by doing these (individually very cheap) transformations up front as new pubkeys come into the system (e.g. new blocks on Bitcoin Core). Or alternatively we could treat 50s as an acceptable cost for proving in some situations, where creating proofs is a rare event, but this isn't very attractive.

"Executive summary" because this is way too in the weeds for most:

There's no realistic way of reducing the proof size much below 2.7kB. By making them slightly bigger we can make proving nontrivially faster, if that is helpful.

The proof size varies more or less logarithmically with the branching factor (which he have as default 1024), and (in a very complicated way), approx linearly with the depth (which he have as default 2). As a result, since the set size is (branching factor) ** depth, we want to use the shallowest tree possible for the smallest proof size (which is what we are already doing), but worth noting that the size doesn't change very much if we switch from e.g. 1024 ** 2 to 32 ** 4. However for faster proving, it might be better to go with deeper trees, at a small extra cost in proof size.

This is more of an "informational" "Issue" for now. The idea is to write out in some detail where the proof sizes come from, with the idea that it becomes possible to know whether improvements in this area are possible, and to estimate more accurately what the proof sizes are for different parameters.

The full proof serialization produced by the rpc.RPCProver.prove function contains the following:

$D$ - the serialization of the point that is the reblinded form of the prover's taproot key
$E$ - the key image of that same key.
proof - this is the Ped-DLEQ proof of correctness of the above as explained in autct.pdf
p0proof - this is the Bulletproof of the circuit for the secp256k1 curve (the root and the leaves)
p1proof - this is the Bulletproof of the circuit for the secq256k1 curve (the intermediate layer)
path - the (reblinded) path to the root from the prover's leaf
root - the root of the Curve Tree

The only reason for this note/Issue is because of the 4th and 5th entries, the bulletproofs. Calculating their size as a function of the application variables is non trivial; the rest is easy, but we'll write it here for completeness:

$D$, $E$, root - curve points on secp256k1 serialized as 33 bytes, so 99 bytes total
proof - this, as per the referenced pdf, requires 2 curve points and 2 scalars, so roughly 33x4=130 bytes and this will not vary with proving parameters
path - $d=2$ ($d$ is depth) points on secp and secq from the leaf to the root (with reblinding of course). This is the serialization of a SelectandRerandomizePath object, which consists of 2 vectors, one for each of even and odd. In the case of $d=2$, each vector has length 1, but will have the 8 bytes extra for vector serialization, giving a total size of (8+33)*2.

Each of the two bulletproofs are more or less the same, but:

• as noted in the original paper, the size of 1 such proof is logarithmically dependent (assuming use of the inner product argument, which is of course the main advantage of Bulletproofs, so yes we do use it) on the number of multiplication gates in the circuit. Parallel arithmetic constraints (from $1 \ldots q$ as per the paper) don't affect the total size. So to know the size of the proofs provided by autct, you need to count the number of multiplication gates it uses.

Here is an attempt to audit that number:

This section:

https://github.com/AdamISZ/curve-trees/blob/08700f59427a36d8fb2b49a7e8bc7aaf6d27454e/relations/src/single_level_select_and_rerandomize.rs#L111-L117

... from the curve trees (my fork, but unchanged) repo shows the operations needed to do a single level Select and Rerandomize:

• First the select operation, which requires one multiplication gate per branching factor, so L multiplication gates. This is because the polynomial constructed is degree $L$, with one root per set member.
• Second, the permissible operation on the chosen point from the set. This requires 4 multiplication gates.
• Third, the rerandomize operation. This is the part that does elliptic curve arithmetic. The code splits the field element into three bit windows, so starting from a 256 bit value, it is split into 256/3 = 86 rounded up, windows. This requires ** $7 \times 86 + 3.5 \times 84 + 10 = 906$ multiplication gates**.

Taking all this together, and including the fact that we need one Select and Rerandomize per (even/odd) depth in a single bulletproof, gives us $\frac{d}{2}(L + 911)$ multiplication gates in each of the two bulletproofs.

That means that for the concrete case, in this application, of $L=1024$, we have a total of $n=1935$ multiplication gates.

Referring to the proof structure (R1CSProof) in curve-trees/bulletproofs/proof.rs, we can see that the generalized version of bulletproofs used, the formula for its size is not quite as simple as:

$$(2 \times \lceil (\log_{2}(n))\rceil + 8) \ \textrm{group elements} + 5 \ \textrm{scalar elements} $$

, where $n$ is the number of multiplication gates, as in the Bulletproofs original paper. It's actually:

$$ 2 \times \lceil (\log_{2}(n))\rceil +3 + \textrm{len}(T)\ \textrm{group elements} + 5 \ \textrm{scalar elements} $$

Now we can assum size(group el.)=33, size(scalar)=32, but we must also account for the vector serialization used, which always adds 8 more bytes to the length of vectors.

The vector $T$ is derived as part of "Generalized Bulletproofs" (link above) based on the number of additional pedersen (vector) commitments made, and in the case of $d=2$, we have only one additional commitment per bulletproof (one for the even depth(s), one for the odd. So we start with ncomm=1 in the notation of the source file bulletproofs/prover.rs, giving op_degree=2, giving length of t_poly = 6, and length of the vector $T = 7$.

As a function, if length(T) = $f_T(d)$:

$$ f_T(d) = 2\left(2 + 2 \lfloor \frac{d}{4} \rfloor + 1\right) + 1 $$

Actually, in case where the parent rerandomization scalar in the single level select and rerandomization is zero, as is the case always for the first proof from the root to the next layer, we have zero additional commitments, but as per the formula for $f_T(d)$, this still results in $T=7$.

Thus the overall size of the two bulletproofs uses $f_T(d) + f_T(d-1)$ in place of length(T), always, a fact we'll use at the end.

Back to the concrete $L=1024, d=2$ example: this results in a total size of a single bulletproof of:

$$ 2 \times \lceil (\log_{2}(1935))\rceil +3 + 7 \ \textrm{group elements} + 5 \ \textrm{scalar elements} + 1 + 8 + 8 + 8 $$

where the additional 8s are to account for the vector serialization of the terms: $T$ and the two vectors of $\lceil (\log_{2}(1935))\rceil$ items. The additional 1 byte encodes a flag for inclusion of extra data (unused for the moment I believe, i.e. it's just a zero byte).

In brief, this gives: (22 + 3 + 7) * 33 + 5 * 32 + 24 + 1 = 1241 bytes.

There are two such bulletproofs, resulting in 2482 bytes.

Then we add the other components from the start, giving $1241 \times 2 + 99 + 130 + 82 = 2793$

Which agrees with size on disk of proof files generated by autct -M prove: 2793 bytes.

Taking a high level view, the formula should be something like (where $L$ is branching factor and $d$ is depth; they are related by $N= L^d$, where $N$ is the size of the set we're proving over):

$$ 2 \times (2 \times \lceil (\log_{2}(\frac{d}{2}(L+911))\rceil + 3 + \textrm{len}(T)) + (5 + d) \ \textrm{group elements} + (5 \times 2 + 2) \ \textrm{scalar elements} + 2 + 8 * 8 $$

... where len(T) varies according to:

$$ \textrm{len}(T) = 2 \times (2 + 2 \lfloor \frac{d}{4} \rfloor + 1) + 1 $$

If approximately correct, one may wonder if a branching factor $L=32$ is a good idea, with $(2^5)^4 = (2^{10})^2$.

Proof size would then be:

$$ 2 \times (2 \times \lceil (\log_{2}(2 \times (32+911)))\rceil + 3 + \frac{f_T(4) + f_T(3)}{2}) + (5 + 4) \ \textrm{group elements} + (5 \times 2 + 2) \ \textrm{scalar elements} + 2 + 8 * 8 $$

where len(T) = 11. This gives a total proof size of: 2991 bytes (confirmed in tests), which is bigger. However it can reduce the proving time according to my tests, which arguably is more important given that the proving time is 15-30 seconds (especially if you include the deserialization of points from file storage). So this may be worth looking into further.

Finding optimal values is non trivial given the use of non differentiable functions floor, ceil, though certainly possible. It seems that the most shallow tree structure is usually optimal for proof size, but deeper trees would be faster (how to quantify this?), but would like to put a bit more analysis work into it.

After resolving #10 I realized that the biggest bottleneck in the proving time is having to call the deserialize routine on each pubkey (curve point) that was serialized into the keyset file (pre-converted to permissible, but that's not relevant here; it's still one curve point per pubkey).

The deserialization call here:

... now takes about 9.5 seconds, whereas calling deserialize_compressed, which includes extra sanity checks per point deserialization, takes over 100 seconds.

This 90% speedup by definition has solved "most" of the problem, but I am still not satisfied that a linear cost in simply reading in public keys ends up being the overwhelming part of the proof cost; this would mean that (probably), running a proof over a 1M pubkey set will have a 30 seconds cost in just reading the data, which will overwhelm the 2-5 seconds needed to actually run the cryptographic proof.

For now, the situation is acceptable as long as we are not working with keysets larger than a few hundred thousand, but it's very suboptimal.

PS.

Just to check I tried two different Rust syntaxes for reading in the keys, but unsurprisingly it made no noticeable difference in performance:

let leaf_commitments: Vec<Affine<P0>> = pts_bin.iter().map(|x| <Affine<P0>>::deserialize_compressed_unchecked(
        &x[..]).expect("Failed to deserialize point")
    ).collect();

or

    let mut leaf_commitments: Vec<Affine<P0>> = Vec::new();
    for a in pts_bin.into_iter(){
        let x = <Affine<P0>>::deserialize_compressed_unchecked(
            &a[..]).expect("Failed to deserialize point");
        leaf_commitments.push(x);
    }

In a practical usage of this primitive, you would almost always want the proof to "sign over" an ephemeral identity. Indeed, without this element, the protocol has a danger:

Imagine that you own a private key x for a utxo U of the utxo-set S, and you generate a proof P_a(S, U) where the subscript _a means 'for the context of application a' (this is currently handled by our context_label). This ensures that the proof cannot be reused in a different application b but does not tie the proof to anything else. Therefore, if the proof is to be used as a token for access to a service Q for application a, it is not safe to broadcast it, since another user can use P just as easily as you can, even if they cannot generate a new P themselves.

Since we are focused on anonymity, the solution is to attach an ephemeral user identity to the proof, as a message that is being signed over. Hence this ephemeral identity should be inside the challenge hash of the Pedersen-DLEQ proof (but note: it should not be in the preimage of the J point, since that would allow reuse of key images; that preimage should always be universal at the level at which we want to enforce scarcity).

Of course an ephemeral identity string might be the most common usage of this extra message field inside the Ped-DLEQ hash, but it makes sense for it to be an arbitrary length string whose semantics are defined by the application a. But it MUST include an identifying "user" string (or similar) if you want to allow users to gain benefit of it without the risk of it being stolen by a different user.

Finally, there is no reason I can see for now (?) to also include this message string in the Curve Tree proof hash challenge, since the mechanism already exists to tie the curve tree proof to the Ped-DLEQ proof so the former can't be reused by a non-key owner successfully (they would fail to create a new Ped-DLEQ proof).

The code currently reads the keysets config var as context_label:filepath but this is dumb: we want the second part of that string to represent the name of the keyset, shared by client and server (or peer and peer), whereas the location on disk is a different thing. We could try to force that to be the same for both parties using a default directory location for keysets, but it seems unnecessary. Instead, we'll add another config var with an easy default for the location of keysets, and then include only the name (the *.aks string as described here) in the keysets string.

I was thinking about creating python bindings for aut-ct so that it can be easily used in joinstr. Does it make sense or we have better alternatives?

If proving is an RPC call, it leaves an issue to be addressed about the threat model being addressed w.r.t. secret key material.

In the case of a wallet, we obviously encrypt the secret "at rest", in something like a wallet file. It's unlocked in memory and used only within-process.

The architectural problem here, however, is non-trivial. Consider that, the most plausible usage scenario for the app would be:

a wallet application exists, call it W.

W wants to support this as a feature for its user.

W calls AUTCT with a proving request; it needs to provide the private key to AUTCT to allow the proving request to work.

This means that AUTCT has to be kind of "owned" by A from a security point of view (it could run it as a subprocess or similar), and trust giving to AUTCT either a raw private key or a password to decrypt a wallet file. The latter might seem more normal, but AUTCT would need to "speak the language" of the decrypted wallet file of W (and be able to decrypt it), which doesn't seem to make sense.

But the alternative, that W passes to AUTCT the raw private key as part of the RPC call, also seems dangerous. A well known example of this insecure pattern is: imagine that W called AUTCT as a subprocess with a flag -i <privkey> - this would result in the private key being visible in the OS process list.

If the RPC prove call is via an encrypted/secure channel (TLS), then this problem is addressed, so long as that channel is actually authenticated and encrypted properly, preferably with forward secrecy. I think this option is a little annoying in terms of extra baggage (self signed certs will be required), but probably correct.

Opinions welcome, hence the label.

Considering two possible definitions for the independent NUMS generator, here J that is used for deriving key images:

• J = hash(application-specific-label,curve-tree-root)
• J = hash(application-specific-label)

The latter seems more appropriate for the most intuitively appealing test cases. As an example, consider making proofs over the utxo set. This is a set, and therefore a tree, that you may want to update regularly, e.g. every week or every day. Every time you update, you change the tree and therefore the root. With the first of the above options, you will be able to create new, unlinkable key images for a single utxo every time you update. It's hard to see when that would be preferable to a key image, and therefore token (or tokens) that are fixed to the same utxo over time.

For this reason, the second option will be chosen, for now.

This isn't technically an "Issue" if I understood it correctly, but it needs to be written down somewhere:

Obviously it is normal that the number of elements of the set you want to use (the number of bitcoin pubkeys let's say), will not be a power of 2.

As can be seen here:

... the strategy taken to deal with this case is that a value of '0' is inserted for the x-coordinate of the commitment point (for the leaf), if there is no actual leaf available.

This would tend to suggest an issue might arise when using '0' for x-coordinates. But it isn't that clear. Suppose there are four children, points on secp: P1, P2,P3, P4. And suppose "P4" is actually empty, represented in code by None (see x_coordinate() function). Then the scalar it is mapped to in secq for the next layer up the tree (here "x4") (suppose "C" is the parent of P1..P4) is zero. But C is constructed as (x1G1 + x2G2 + x3G3 + x4G4 + rH) with, here, x4=0. So clearly that will work fine (indeed, it must, for this fill out strategy to work!).

(An additional complication is permissible points: when you construct a curve point in this algorithm, it is incremented with +H (i.e. r+=1) as many times as needed, deterministically, then passed through the Universal Hash to see if we get a permissible point or not. But this is a deterministic process carried out by prover and verifier.)

However all this is moot if we consider the that the Ped-DLEQ component of our proof in aut-ct is in fact checking knowledge of the private key, more specifically, for a rerandomised point D, we check:

• the prover must prove knowledge of the secret witness (d, r) for D = dG + rH
• the prover must prove that E has same DL wrt J as D has wrt G (i.e. d)

The second, trivially, cannot work with d=0, because it would output the point at infinity, irrespective of the choice of any J on the curve. Most implementations of ECC just outright reject this, but it wouldn't matter if they allowed it.

To summarize: because of the output of the key image there's no way a forged proof using a zero private key can work. To analyze, instead, what could happen in a different Curve Trees-using protocol would need one to specify the exact way the Curve Tree was being used there, distinct from how it is being used here.

(I'm relegating this additional info to an "Addendum" because I think it happens not to be relevant; but it's still interesting and tangentially related:

secp256k1 does not have a point(s) with x-coordinate 0. Put another way, over the base finite field of secp256k1, there is no square root of 7 (reminder: y^2 = x^3 +7 and we want x==0).
It just so happens that this is also true of secq256k1:

sage: F = FiniteField(2**256-2**32-2**9 -2**8 - 2**7 - 2**6 - 2**4 - 1)
sage: a = 0
sage: b = 7
sage: n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: Fn = FiniteField(n)
sage: F(7).sqrt()
sqrt7 //<-- this is the return format for values without roots in the field
sage: F(9).sqrt()
3 //<-- if there is a root it is shown
sqrt115792089237316195423570985008687907852837564279074904382605163141518161494327
sage: Fn(7).sqrt() //<-- Fn is the scalar field of secp, so it is the base field of secq
sqrt7

Why is this irrelevant? Because the operation (x coord of a point on secp -> scalar in secq) doesn't have to pay attention to whether the input x-value is actually valid. To illustrate, consider what the code is doing if you provide an encoding of an x value which is not actually a valid x-coordinate on secp256k1 (this is is true for approx half of the integers in 0..N where N is the order of the secp256k1 group).
)

Currently the J generator used for the DLEQ (and therefore key image) is a hash of a random string. Need to standardise it with a customisable label from the label field in the config file, and then update the test cases to include the default value of this label.

Specified in config/command line for serve method with a comma separated list.

At the same time, change the specification from a file path to just a name, with a default location for the keyset file (because the server and client need to communicate it).

IIRC there is an example in toy-rpc, so this should be fairly easy, at least with self-signed certs.

Currently since the template parameter L for the CurveTree constructor is defined as const usize, we cannot read it in at runtime. Need a solution for this, as optimal tree structure depends on keyset size.

Currently we have a --version option in the arguments, but in this I was thinking specifically of the ability of the user to choose a communication protocol version (see docs/protocol-utxo.md for the current 1st draft).

The application version should be separate and --version should be reserved for this. So the probable action to take is: remove --version from the explicit command line, ensure that clap is taking version from the Cargo.toml setting, then add another option for communication protocol version.

This may need edits to the forked curve-trees repo.