Key image scheme isn't unlinkable for related keys

[kayabaNerve]

For two keys K1 = R + o G, K2 = R + o' G, where R is the root key and o is some offset, their key images will be distinct by o' - o J. This allows anyone who knows the relationship of two keys to identify their key images and link them.

Defining J = H(K), a unique generator per key, prevents this under the DDH assumption.

[AdamISZ]

Thanks for taking the time to note this here; I'm assuming (unless I misread something) that you're writing the same flaw as you mentioned here, correct?

Yes I should have noted it as an Issue, here, at the time. One thing I didn't think about when I responded then, was, apart from the Silent Payments use case (well, the fact that if you were to use such related utxos in a scheme like this, you would be revealing a link, which is no bueno since the whole point is not to do that!), don't we have a similar issue with BIP32 public derivation? As far as I can tell, yes: the difference between private keys at index i and j in a public derivation (i.e. "unhardened keys") from a given master public key P, is the difference between the tweaks at i and j, which is calculable by anyone who knows P. So the difference in key images is J *(tweak_j - tweak_i). This is the same flaw but having a way wider applicability to any wallet where the MPK has been published, right?

Defining J = H(K), a unique generator per key, prevents this under the DDH assumption.

Hmm, indeed this is very simple and, let's say, actionable! Will get on to it when I get a chance.

[kayabaNerve]

It is the same, it just wasn't tracked here :)

If I send to your stealth address twice, I know the relation of the two derived keys. I can then reasonably determine what their key images are if both are ever used with the same generator (even in separate contexts).

BIP32 derivations also have the same problem but parent keys generally aren't public. Stealth addresses are, making them my preferred example here.

[AdamISZ]

BIP32 derivations also have the same problem but parent keys generally aren't public. Stealth addresses are, making them my preferred example here.

Yes I can see both sides though, because while MPKs aren't broadcast to the world, there are a lot of use-cases involving third parties where they are given to those third parties (yes I know, it's kind of awful, to say the least ...). Heck there were even block explorers out there that would publish the relevant MPK if they "happened to know it" ... And obviously those numbers dwarf Silent Payments usage for now, but I suppose - it's academic, either way, this construction is just ... bad.

[kayabaNerve]

The main complexity will be in the dual-set membership gadget. I'd recommend forking the FCMP++ libs. It also represents the amount which is useful as you can have a single tree while still making assertions on UTXO value (for a minimum amount requirement, subtract the amount from the commitment and require a range proof).

The GBP lib is audited and the rest will be. The FCMP is 24ms to verify for ~200b set membership. The FCMP does assume the curves are less than 256-bits, but I am planning a fork which supports 256-bit curves (specifically for use with secp256k1). The edits necessary shouldn't be notable, the variable layout will just change slightly as we now can't cram a scalar's bits and a flag into a 256-bit slot. The scalar alone will take that full slot.

[AdamISZ]

I confess I don't understand what you mean by "The main complexity will be in the dual-set membership gadget." but then it has been a long time since I read through some of your FCMP paper. What's wrong with just doing, as you say, for each keypair, say (x, P=xG), have a key image I_P = xH(P) where H() is hash-to-curve? May be just a brain fart here but, did I miss a step?

I don't doubt that this project could potentially be substantially improved by basing it off your library, but to be fair current performance is good enough (10s of ms of verif, 1-2 seconds proof for typical keyset sizes). Also I don't know if you noticed but I have another "audit" function in here now, which proves statements like "I own between 1m and 1.2m satoshis spread across N utxos in the keyset". Kind of fun; "privacy preserving proof of assets" type of thing.

Edit: still I must agree that basing it off a lib that has some audit would be an idea if it were ever something to be used "in anger" so to speak, plus the not-reinventing-wheels aspect. My only concern is the vague perception that since you started from a different place, elliptic-curve speaking and functionality-wise, the task would be fairly substantial.

[kayabaNerve]

What's wrong with just doing, as you say, for each keypair, say (x, P=xG), have a key image I_P = xH(P) where H() is hash-to-curve? May be just a brain fart here but, did I miss a step?

You have to build the tree with (P, I_P), do dual-set membership (I am outputting a rerandomization of this tuple in tree and not selecting elements across tuples), and then extend the opening proof accordingly. It's a modified circuit compared to proving a single output point is the re-randomization of a point in-tree.

The FCMP++ libs, beyond audits and perf, already model all of this.

Also I don't know if you noticed but I have another "audit" function in here now, which proves statements like "I own between 1m and 1.2m satoshis spread across N utxos in the keyset". Kind of fun; "privacy preserving proof of assets" type of thing.

While I haven't looked at your implementation (my guess is it turns the output key into the randomness of a Pedersen Commitment for the amount, which is what's added to the tree, and then follows the same techniques I posit here), just as an FYI for the sake of completeness, that should be trivial to replicate with the FCMP++ libs.

1. Do n instances of FCMPs, outputting n amount commitments
2. Sum the commitments
3. Subtract a commitment to 1m
4. Do a range proof to prove the amount is between 0..2**64
5. Subtract another 200k, negate the resulting commitment
6. Do a range proof to prove the amount is between 0..2**64

The FCMP code also does allow using a single proof for n outputs.

My only concern is the vague perception that since you started from a different place, elliptic-curve speaking and functionality-wise, the task would be fairly substantial.

My main reasoning is due to the audits. The GBP code is generic to the curves. The elliptic curve gadgets (scalar mul) is also generic. I've already done a secq256k1 lib I use with those and plan to have audited: https://github.com/serai-dex/serai/tree/next/crypto/evrf/secq256k1

The FCMP code is also generic to the curves, but assumes 255-bit scalars when committing variables for optimizing the commitments. It'd have to be slightly tweaked in that regard. I don't believe that too much work but that may be due to my experience I come in with.

Also, regarding functionality, I'm proposing entirely reusing the FCMP++ definition of output tuple (key, key image generator, amount commitment) and SAL proof (which proves the key image). They wouldn't have any distinctions there.

Though it's your project and you should do what you see best :) Feel free to maintain the diversity, seek your own audits, or decide this fine as an experiment which doesn't need such auditing. I, with my own specific background, would do this one specific way but I don't mean to demerit how you would do it or try to assume powers of decision-making of your work. I apologize if I've been too strong an advocate. Just giving my advice and trying to save you work if you do want to resolve with an audited codebase.

[kayabaNerve]

As an update, I did see how yes, you so squash the amount into the commitment for your auditing function.

[AdamISZ]

You have to build the tree with (P, I_P),

Oh duh, of course. I_P can't be reconstructed publically 🤦. I'm going to claim it was late last night when I asked that, lol.

[kayabaNerve]

It's also a point as a secret, not a scalar, which is anmoying. You have to output it re-randomized and a commitment to the rerandomization as the prover can't trivially open a blinding commitment to the key image generator.

That was one of the problems solved with the FCMP++ architecture and SAL proof. You can definitely shave off a bit for the Bitcoin premise here (presumably, one can squash the amount into the output key), but by and large, it just seems (to me) to be the right fit.