About the null entries used to complete the leaf set

[AdamISZ]

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