Asymmetric payment construction

[ebfull]

This is a casual overview of the payment construction that Matthew, Ian and I have been playing with.

The first intuition is to treat nullifiers as randomized public keys, i.e., (g^sk)^r where r is the output of a PRF, and g is the generator of the fast ECC curve group from #2230. Outside of the zk-SNARK, the person in possession of sk can also sign using a Schnorr signature. As far as we're aware, this is compatible with standard threshold signature schemes.

There are two benefits to this: first, the zk-SNARK prover does not have spend authority, which allows us to achieve delegated proving for hardware wallets, mobile devices, businesses, etc. Second, there is no longer a need for h_Sig-style ephemeral public keys.

The first thing to notice is that the PRF for r cannot be keyed by sk without revealing it to the prover. We can solve this by making g^sk the key, which means that addresses must be a commitment to g^sk. However, the ultimate construction of the nullifier (g^sk)^PRF_gskρ is difficult to write a proof for. We need the addresses to be a commitment to two keys: g^sk and h^prf_key instead.

At this point, there are many approaches for designing the addresses. Pedersen commitments are one option, but in order to achieve key plurality as in #570 we need to reduce the number of bases for the DH key exchange, so something like GH(i)^{H(gsk || hprf_key)} is ideal.

Notes can be Pedersen commitments to the address/value/ρ and any additional metadata. During spending, the prover need only know how to decommit the note and the address. Note that it is not secure to allow the spender to decommit from any base, but instead only outputs of GH. If GH is expensive to compute inside of the zk-SNARK, its domain would need to be small enough that we can precompute all of the bases and bake them into the circuit.

The actual concrete constructions for H or PRF_rho are not fully fleshed out. If truncating CRH(g^sk || h^prf_key) were acceptable, that would be great for H. But it's not clear to us that it is safe. Additionally, we can cheaply calculate (g^1/(x+m) h^x j^m) inside the circuit and use this for the PRF (this is provably collision resistant, needed to prevent sniping), but for some reasons that @matthewdgreen could explain there are some technical difficulties with this approach. Thus only with some clever crypto engineering could we avoid using something like MiMC or a full-blown hash function for these purposes.

The general gist of this is: make sure the prover doesn't know the signing key, and use the nullifier to communicate spend authority to the outside consensus rules.

[daira]

@ebfull wrote:

If GH is expensive to compute inside of the zk-SNARK, its domain would need to be small enough that we can precompute all of the bases and bake them into the circuit.

It needn't be expensive; it could be based on MiMC, for example. Note that hashing into the curve is easy in this context because we only need to check in the circuit that the curve equation holds for the hash of the given i. (The search for suitable i, of which about half will work, is done outside the circuit.)

[daira]

g^sk.h^prf_key, where the discrete log of h wrt g is unknown, is already a collision-resistant hash of sk and prf_key, correct? So does it suffice to use GH(d)^{(gsk.hprf_key) mod s}, where s is the group order, directly? (The "mod s" biases the exponents because the field size q is only a little greater than s, but I believe this can still be proven safe at least if the number of diversified public keys for a given private key is limited.)

If we're not convinced of the safety of that, we can use something like GH(d)^{BLAKE2b(gsk || hprf_key) mod s}, and since 2⁵¹² >> s, we are definitely safe from bias-related weaknesses.

@imichaelmiers What were the technical difficulties with g^1/(x+m) h^x j^m ?

[Edit: rename the group order from r to s to avoid a naming collision with the PRF output r.] [Edit: rename i to d.]

[daira]

[deleted comment that was confusing the inner and outer curves]

[daira]

So if I'm understanding correctly, the nullifier is [PRF^rand_{prf_key}(ρ)] [sk] G and the prover has to be given prf_key and [sk] G. Presumably, if we want to keep private keys small, then we should derive sk and prf_key from a single sk_spend (using a PRF that does not need to be checked in the circuit).

For the variant with diversified keys, the address is (d, pk_enc,d) where pk_enc,d = [vk_enc] GH(d) and vk_enc = H([sk] G, h^prf_key). (I've renamed sk_enc to vk_enc to make it clearer that it is a viewing key.) The note encryption is done with GH(d) as the base and pk_enc,d as the public key. The note_plaintext is (d, pk_enc,d, v, ρ, r, meta, rcm). A spend proves knowledge of (d, pk_enc,d, v, ρ, r, meta, rcm, prf_key, [sk] G) and a Merkle tree path from cm = Commit_rcm(d, pk_enc,d, v, ρ, r, meta) to anchor, such that r = PRF_{prf_key}(ρ) and nf = [r] [sk] G. It can also optionally prove that the note encryption is correct (if the prover is also given the ephemeral secret esk). The spend reveals the proof, anchor, nf, and a Schnorr signature proving knowledge of r.sk such that nf = [r.sk] G. Do I have that right?

Where is the construction of vk_enc as Hash(g^sk, h^prf_key) (in additive notation, Hash([sk] G, [prf_key] H)) checked? Why does it need to be constructed this way? It seems as though if it is, then the prover has to be given prf_key and [sk] G which allows computing vk_enc, but it is undesirable for the (possibly delegated) prover to be able to decrypt/detect note plaintexts.

[Edit: rename the diversifier i to d, and use additive notation for the inner curve.] [Edit: switch to the notation [z] P for scalar multiplication of P by z.] [Edit: rename the randomness for the note commitment to rcm.]

[daira]

It seems as though vk_enc could instead be derived directly from sk_spend; everything else would still work, but the delegated prover wouldn't be able to decrypt.

We can combine this with delegated JoinSplit detection, providing "PALC" from #288. The address becomes (d, [vk_enc] GH(d), [vk_detect] GH(d)), and the note plaintext is double-encrypted, the inner encryption being to [vk_enc] GH(d) and the outer to [vk_detect] GH(d). Alternatively, the ciphertext can just include a tag encrypted to [vk_detect] GH(d); if the correctness of the encryptions is ensured by the circuit, this is equivalent.

[Edit: notation, as above.]

[daira]

So we know how to do (delegated proving + threshold signatures + delegated detection + diversified addresses + enforced encryption correctness + incoming viewing keys). Let's see if we can also add outgoing viewing keys.

If we don't require that someone could know an incoming viewing key vk_in = (vk_enc, vk_detect) without knowing the corresponding outgoing viewing key vk_out, then we can set vk_out = Hash(vk_in), and derive dk = PRF^dk(vk_out, u), where u is unique for each JoinSplit. Then, we encrypt the output note addresses and esk to dk (similar to what was specified in section 6.1 of the protocol spec before viewing keys were removed). We give vk_out to the prover so that the circuit can prove that dk is derived correctly. A disadvantage is that we might not want a delegated prover to be able to decrypt other JoinSplits spending notes with the same address; to solve that we could use asymmetric encryption (which can be proven correct without having the decryption key).

Note that this satisfies the criterion that if we have an address (d, [vk_enc] GH(d), [vk_detect] GH(d)) and an incoming viewing key vk_in = (vk_enc, vk_detect), we can derive the outgoing viewing key vk_out, and verify that (vk_in, vk_out) are correct for that address.

[Edit: notation, as above.]

[daira]

Another possibility is to define:

• vk_detect = Hash^detect(vk_all)
• vk_enc = Hash^enc(vk_all)
• vk_out = Hash^out(vk_all)
• vk_all = Hash^all(sk_spend)
• sk = Hash^sk(sk_spend)
• prf_key = Hash^prf_key(sk_spend).

Then:

• vk_detect can be used to detect incoming payments;
• (vk_enc, vk_detect) can be used to detect and decrypt incoming payments;
• vk_all can be used to detect and decrypt both incoming and outgoing payments
• sk_spend can be used to spend, and to derive all the above keys

and any of these can be confirmed to match any of the diversified addresses for that key, whereas

• vk_out can be used to detect and decrypt only outgoing payments, but cannot be confirmed to match an address.

[ebfull]

One of the missing objectives here which influenced the original design was a desire to make addresses smaller. Two group elements doesn't really gain much on the previous construction.

[daira]

Well, it's two group elements in exchange for additional functionality (delegated detection). Without the asymmetric payment construction idea, that would have made addresses the same size as three group elements.

[ebfull]

It's interesting to consider how the construction can be designed so that the delegated prover doesn't have enough information to decrypt all of the sender's notes. However, note that there is already a huge privacy loss to the prover that is hard to describe to users, so I would rather have the smaller addresses and just tell users to expect that they are forfeiting their privacy to the delegated prover but not their spend authority.

In some situations this is already the case, like with hardware wallets and so on.

[daira]

Are you confusing delegated proving with delegated detection? Delegated proving (including the improvement of not revealing viewing keys to the prover) doesn't require two group elements in addresses; delegated detection does.

[ebfull]

Why would the detector need two group elements? The exponent of the group element in the address can be known to the detector because it's merely a commitment to the actual public key later randomized and used to sign.

[daira]

Because we don't want the detector to be able to decrypt.

[daira]

By the way, sorry for derailing this ticket a bit with discussion of other features. The original "asymmetric payment construction" idea is great, and I agree it's a good candidate for inclusion in Sapling (subject to further security analysis).

[daira]

@matthewdgreen @imichaelmiers @ebfull Can you look at https://github.com/zcash/zcash/issues/2277#issuecomment-294968426 and check whether I've understood the proposal correctly?

[daira]

@ebfull replied on Slack that I had.

[daira]

[Edit: the following change would introduce a security problem; see here.]

Currently we have r = PRF^rand_{prf_key}(ρ), and we also have to make sure that ρ is unique, so if we did that in the same way as Sprout we would have ρ = PRF^ρ_φ(i, hSig). Also vk_enc must be derived from [sk] G, and prf_key must also be derived in a way that allows its consistency with the address to be checked in the circuit.

Instead, we can combine several hashes/PRFs into one. Drop prf_key, and replace r in the nullifier computation with ρ. When creating a new note, ρ = PRF^ρ_φ(i, hSig). A note plaintext is (d, pk_enc,d, v, ρ, rcm, meta). The holder of a spending key also computes ak = [sk] G.

Now a spend must prove knowledge of private inputs (d, v, ρ, rcm, meta, ak) and a Merkle tree path from the input note cm to anchor, such that:

• cm = Commit_rcm(d, pk_enc,d, v, ρ, meta) where
  • pk_enc,d = [vk_enc] GH(d) and
  • vk_enc = PRF^addr_ak("vk_enc")
• nf = [ρ] ak

and reveal a Schnorr signature over the transaction proving knowledge of the discrete log of nf wrt G (which we can infer is ρ.sk since ak = [sk] G). hSig is computed as in Sprout.

For new notes, we also prove that ρ^new = PRF^ρ_φ(i, hSig).

(Another equivalent way of expressing this is to rename ρ to r. I prefer the way it is expressed above because in Sprout, a nullifier was computed from ρ and a_sk, therefore preserving that keeps the role of ρ the same as in Sprout.)

[Edit: fix a bug; the creator of a new note does not know its ak, so ak should not be an input to PRF^ρ. It doesn't need to be.] [Edit: rename r to rcm to avoid confusion.]

[daira]

Ah, that construction breaks the property that a delegated prover cannot decrypt (because vk_enc is derived only from ak). Working on possible fixes.

[daira]

We need to be able to prove in the circuit that pk_enc,d from the input note commitment is consistent with ak. (Both of these are known only in the circuit.) We also want vk_enc (the private decryption key associated with pk_enc,d) to be secret from the delegated prover. These sound to be in conflict, but maybe not.

pk_enc,d needs to be consistent with ak, but that does not imply that vk_enc needs to be derived only from ak. The property we really need is that whoever generated the address intended that this ak be used to authorize spends of notes sent to that address.

We also want to avoid increasing the address size, and that's what makes this tricky. (@ebfull said as much above, but I didn't grok why at the time.)

First let's solve the problem without the constraint of keeping the address size the same. As in Sprout, we could have the public key contain a_pk which is a hash of ak, and include a_pk in the note plaintext. Now we only need to check consistency of a_pk, not pk_enc,d (also as in Sprout). This allows vk_enc to be kept secret from the delegated prover at the expense of adding the a_pk field to an address. It also breaks diversified key unlinkability, but we can fix that by letting a_pk be a hash of (d, ak). We still get the improvement over Sprout that we can do delegated proving for shielded inputs without loss of privacy.

[I'm pretty sure there is a better solution, I'll get back to this later.]

[ebfull]

@str4d and I may have figured it out. Here's a construction that doesn't involve GH() stuff (for key diversification) but I bet it could be changed to support key diversification easily. It has short addresses currently.

Alice is the recipient. Bob is the sender. Carol is the designated prover.

Alice creates a key, sk. She computes g^sk. She computes g^vk = (g^sk)^H1(gsk). She computes g^prf_key = (g^sk)^H2(gsk).

g^prf_key is used for PRF(rho), the result of which is used to randomize g^sk. g^vk is the payment address.

This has all of the following properties, assuming the derivations above are one-way functions:

• Bob doesn't know when the note is spent. (He knows g^vk which is not enough to find g^prf_key.)
• Carol doesn't know sk, vk or prf_key.
• The address is just a single group element.
• The viewing key doesn't provide spend authority.

[daira]

BTW that's a semi-private key construction (see section 6 of https://eprint.iacr.org/2012/524). Specifically (sk, g^sk, g^vk) and (sk, g^sk, g^prf_key) are (private, semi-private, public) key triples.

[ebfull]

We're hanging out with Brian Warner at PETS and he finds it entertaining that this idea keeps getting reinvented.

We haven't had any luck making a proof of it, but everyone who looks at it says it looks fine.

Imagine we did have a proof of it, I don't know how to get public key diversification from this! Maybe that's okay?

[ebfull]

@str4d and Brian noticed the Tor people needed something similar and they wrote a sorta-kinda-proof about it:

https://www-users.cs.umn.edu/~hopper/basic-proof.pdf

[ebfull]

@str4d points out that we can add another layer after the viewing key (another derivation step) for delegated detection without giving the detector the ability to decrypt the notes, with some added cost to the size of the transaction.

[daira]

OK, my simplification that drops the prf_key can be merged with the semi-private key construction:

When creating a new note, ρ = PRF^ρ_φ(hSig). A note plaintext is (pk_enc, v, ρ, meta, rcm). The holder of a spending key also computes ak = [sk] G.

Now a spend must prove knowledge of private inputs (v, ρ, meta, rcm, ak) and a Merkle tree path from the input note cm to anchor, such that:

• cm = Commit_rcm(pk_enc, v, ρ, meta) where
  • pk_enc = [PRF^addr_ak()] ak
• nf = [ρ] ak

and reveal a Schnorr signature over the transaction proving knowledge of the discrete log of nf wrt G (which we can infer is ρ.sk since ak = [sk] G). hSig is computed as in Sprout.

For new notes, we also prove that ρ^new = PRF^ρ_φ(hSig).

[Edit: rename r to rcm and reorder fields of note plaintext for consistency.]

[daira]

I worked out how to combine the diversification with the semi-private key idea:

ρ is as before. An address is (d, pk_enc,d). A note plaintext is (d, pk_enc,d, v, ρ, meta, rcm). The holder of a spending key also computes ak = [sk] G and dk_d = [sk] GH(d). The viewing key is vk_enc = PRF^addr_ak().sk.

Now a spend must prove knowledge of private inputs (d, v, ρ, meta, rcm, ak, dk_d, π_Schnorr) and a Merkle tree path from the input note cm to anchor, such that:

• cm = Commit_rcm(d, pk_enc, v, ρ, meta) where
  • pk_enc,d = [PRF^addr_ak()] dk_d
• nf = [ρ] ak
• π_Schnorr is a NIZK "proof of same discrete logarithm" showing that the spender knows sk such that (ak = [sk] G and dk_d = [sk] GH(d) for the same sk) — for example, apply Fiat-Shamir to an elliptic curve version of this

and reveal a Schnorr signature over the transaction proving knowledge of the discrete log of nf wrt G (which we can infer is ρ.sk since ak = [sk] G).

Note that the verification of π_Schnorr has to be done inside the circuit, because ak and dk_d are not public. This verification does not require sk.

[Edit: rename r to rcm and reorder fields of note plaintext for consistency.]

[ebfull]

Yes! Wonderful.

• Right now the viewing keys can see every key associated with the secret key. Can we go even further and have a viewing-key per address? Or a viewing key for a set of addresses?
• Maybe we can extend this for per-output viewing keys? (For payment disclosure, in a way that doesn't require us to prove encryption in the circuit.)

[ebfull]

Let's consider the fact that because our delegated prover knows a^sk, they will also know when you spend your money, because they know rho. (Maybe the designated prover pays its (former?) client.) Can we do something about that?

[ebfull]

I think that's a privacy threat we should solve because if your designated prover goes rogue, we don't want it to be able to send our address payments (which it can because it knows at least one of our addresses) and since they would know when it is spent...

[ebfull]

One solution to that might be to use rho in a group hash to produce a base over which we exponetiate by sk, and prove as much inside the circuit using the same zero-knowledge protocol. CDH protects the sender from knowing GH(rho)^sk I believe.

[ebfull]

Oh, wait, that wouldn't work since GH(rho) would need to be public in order to verify the signature outside the circuit...

[ebfull]

I suggest instead that GH(rho)^sk be used as the randomization for g^sk.

[daira]

@ebfull wrote:

Yes! Wonderful.

Glad you like it :-) I'm working on a further simplification that might be able to get rid of π_Schnorr. (It's kind-of-neat that you can feasibly verify proofs within proofs, but it would be good to not have that complexity/cost.) I see this mainly as a demonstration of what should be possible.

• Right now the viewing keys can see every key associated with the secret key. Can we go even further and have a viewing-key per address? Or a viewing key for a set of addresses?

Well, part of the idea behind diversified addresses was that you didn't have to do trial decryption for as many keys as you have addresses. Otherwise you could just use multiple independent addresses (perhaps in a hierarchical derivation scheme so that you have fewer keys to back up). You can certainly have multiple (spending, viewing) key pairs each with its own set of diversified addresses, though; that doesn't require any further change to the protocol.

The protocol above doesn't have delegated detection, and I suspect that we're not going to find a delegated detection scheme that keeps address sizes to one group element. However, if you did have delegated detection, it would be possible (I can see how to do it) to have a single detection key correspond to multiple decryption keys. I'd wary of the conceptual complexity of that, though.

• Maybe we can extend this for per-output viewing keys? (For payment disclosure, in a way that doesn't require us to prove encryption in the circuit.)

I'd assumed we were going to revert the optimization to use the same ephemeral key for multiple outputs if we have N^new > 1 in Sapling.

Let's consider the fact that because our delegated prover knows a^sk, they will also know when you spend your money, because they know rho.

Yes that's true. (Incidentally, can we agree whether to use additive or multiplicative notation for the inner curve? I prefer additive as is conventional for elliptic curves.) It seems difficult to avoid this because we must prove that the note commitment opens to values that determine the nullifier. ~You can imagine separating ρ from the rest of the commitment opening and using a similar trick to the one with π_Schnorr to prove that ρ is correct without revealing it, maybe.~ [Nope; see below.]

[daira]

@str4d points out that we can add another layer after the viewing key (another derivation step) for delegated detection without giving the detector the ability to decrypt the notes, with some added cost to the size of the transaction.

I don't think this works. In an extended semi-private key scheme, where keys are indexed in order of increasing publicness, the public key at index i derives from the private key at index i-1. So semi-private keys don't allow you to give out two public keys in an address without also giving out the private key to one of them, unless you put additional group elements in the address. (We already know how to do delegated detection if we have two group elements in the address: https://github.com/zcash/zcash/issues/2277#issuecomment-294989899 combined with https://github.com/zcash/zcash/issues/2277#issuecomment-316103630 .)

[daira]

I wrote:

We already know how to do delegated detection if we have two group elements in the address...

Well on second thoughts that's not obvious, so I'll write it out:

ρ is as before. An address is (d, pk_enc,d, pk_detect,d). A note plaintext is (d, pk_enc,d, pk_detect,d, v, ρ, meta, rcm). The holder of a spending key also computes ak = [sk] G and dk_d = [sk] GH(d). The viewing key is vk_enc = [PRF^addr_ak("enc")] sk, and the detection key is vk_detect = [PRF^addr_ak("detect")] sk.

Now a spend must prove knowledge of private inputs (d, v, ρ, meta, rcm, ak, dk_d, π_Schnorr) and a Merkle tree path from the input note cm to anchor, such that:

• cm = Commit_rcm(d, pk_enc, pk_detect, v, ρ, meta) where
  • pk_enc,d = [PRF^addr_ak("enc")] dk_d
  • pk_detect,d = [PRF^addr_ak("detect")] dk_d
• nf = [ρ] ak
• π_Schnorr is a NIZK "proof of same discrete logarithm" showing that the spender knows sk such that (ak = [sk] G and dk_d = [sk] GH(d) for the same sk).

and reveal a Schnorr signature over the transaction proving knowledge of the discrete log of nf wrt G (which we can infer is ρ.sk since ak = [sk] G).

[Corrected] Note that in this variant the delegated prover cannot compute vk_enc or vk_detect, because they do not know sk.

[Edit: rename r to rcm and reorder fields of note plaintext for consistency.]

[daira]

Let's consider the fact that because our delegated prover knows a^sk, they will also know when you spend your money, because they know rho.

Wait, it's necessarily the case that the prover learns the linkage between the commitment of the note being spent (so, the transaction that created it) and the transaction that they're proving. That's dependent only on the fact that we use the zk-SNARK to verify the Merkle tree commitment, and does not depend on the part of the protocol that we're designing here; their knowledge of ρ is a red herring.

It is not necessarily the case that they learn anything about when output notes are going to be spent. If they are sent to a different address, then they would need to also be the prover for that address. If they are sent to the same address, then that's just the same situation as above.

[str4d]

I don't think this works. In an extended semi-private key scheme, where keys are indexed in order of increasing publicness, the public key at index i derives from the private key at index i-1. So semi-private keys don't allow you to give out two public keys in an address without also giving out the private key to one of them, unless you put additional group elements in the address.

I must have a different understanding of semi-private keys then. Here's what I was envisaging:

Layer	Private	Public
1	a	ga
2	b = a.H(ga)	gb = ga.H(ga)
3	c = b.H(gb)	gc = gb.H(gb)

So if you give someone the layer i-1 public key, they can derive the layer [i, i+1, ...] public keys, but not any private keys. If you give someone the layer i-1 private key, they can derive the layer [i, i+1, ...] private keys, and the layer [i-1, i, i+1, ...] public keys.

In the delegated detection setting, Alice gives Bob g^b as pk_enc, from which they derive g^c as pk_detect. Alice then gives Carol c as vk_detect.

Am I missing something?

[daira]

~Oh sorry yes, you're right.~

I explained the problem poorly in my previous comment.

Suppose you give an adversary g^b and c. Then, they can compute b = c / H(g^b).

So, you can't use semi-private keys to give Bob g_b = pk_enc and Carol c = vk_detect, because those can be combined to get b = vk_enc.

[ebfull]

@daira said:

Yes that's true. (Incidentally, can we agree whether to use additive or multiplicative notation for the inner curve? I prefer additive as is conventional for elliptic curves.) It seems difficult to avoid this because we must prove that the note commitment opens to values that determine the nullifier.

I don't understand why it's difficult unless you're trying to avoid schnorr proofs.

It should be as simple as changing the nullifier from now being [ρ] [sk] G to being [[sk] GH(ρ)] [sk] G where [sk] GH(ρ) is interpreted as a scalar. The sender cannot possibly know what [sk] GH(ρ) is going to be, even if they know [sk] G.

[Edit by @daira: notation]

[daira]

I don't see how this works. Previously, the circuit checked that nf was computed as [ρ] [sk] G. (This was not done by a Schnorr proof, if I understood correctly, because that wouldn't allow verifying that this ρ is the same one committed to by the note commitment.)

So, how does the circuit check that nf = [scalar([sk] GH(ρ))] [sk] G without the prover knowing scalar([sk] GH(ρ))? Also, what exactly are you trying to keep unlinkable here, bearing in mind https://github.com/zcash/zcash/issues/2277#issuecomment-316992037 ?

[daira]

Oh, I see what you're trying to prevent now. If the delegated prover learns ak for a given address and ρ for a note sent to that address (perhaps in different proof requests), then they can compute the nullifier and detect when the note is spent even if they are not the prover for that spend.

[ebfull]

Oh, I see what you're trying to prevent now. If the delegated prover learns ak for a given address and ρ for a note sent to that address (perhaps in different proof requests), then they can compute the nullifier and detect when the note is spent even if they are not the prover for that spend.

Yes. In fact, I'm worried about the delegated prover sending money to the person, since their address is known, in an attempt to link their transactions, since they know when the recipient spends the money.

(Also the delegated prover could "sell" your ak to people who are more interested in attacking you in that way...)

[daira]

I'm still not sure how your suggested approach using GH(ρ) works though. How do you prove that the nullifier is correct for the opened note commitment?

Oh wait, I may see how to do it.

@madars had an idea that it was possible to compute the nullifier from the commitment, i.e. something like nf = PRF^nf_ask(cm). This preserves the property that nullifiers are in 1:1 correspondence to commitments, but does not require ρ. Now, suppose we adjust this to nf = [sk] cm where cm is now a group element (maybe you define the note commitment scheme using GH). Then it's possible to use a proof-of-same-discrete-logs to show that log_cm(nf) = log_G(ak) = log_GH(d)(dk_d), and verify that proof in the circuit. As before, this doesn't reveal sk because the proof-of-same-discrete-logs is zero-knowledge to the delegated SNARK prover.

[ebfull]

@daira

I'm still not sure how your suggested approach using GH(ρ) works though. How do you prove that the nullifier is correct for the opened note commitment?

I'll reiterate my proposal:

I think the nullifier should be [[sk] GH(ρ)] [sk] G.

Inside the circuit, given ρ, compute GH(ρ). The spender provides the delegated prover with [sk] GH(ρ) and a proof-of-same-discrete-log with [sk] G just like we will end up doing with the addresses inside the circuit.

The sender cannot know what the randomization will be even if they know ak, but it is still fixed. :)

I am also in favor of some trick involving the commitment, haven't thought about that yet.

[Edit by @daira: notation]

[ebfull]

I just want to take the time to vocally support #2171. I am pretty sure our scheme will still be somewhat expensive per-input and per-output, especially with pay-to-verification-key. I don't think users should pay for what they aren't using. It is also fundamental to the way that we've currently been reasoning about other aspects of the paper we've been writing (stuff like UIT's etc.) and the stack-based approach we're taking to doing some stuff. Let's not keep this (ugly, IMO) 2x2 behemoth.

[ebfull]

Just to switch gears a little bit, how will we encode metadata into the address for pay-to-verification-key? I would prefer if pay-to-verification-key addresses were not distinguishable from normal addresses.

I suspect that we can piggyback on the derivation structure to add meta fields, at least one of which could be used for that purpose.

[daira]

@ebfull:

I think the nullifier should be [[sk] GH(ρ)] [sk] G.

Inside the circuit, given ρ, compute GH(ρ). The spender provides the delegated prover with [sk] GH(ρ) and a proof-of-same-discrete-log with [sk] G just like we will end up doing with the addresses inside the circuit.

I see now. That seems to work :-)

My approach that proves same-discrete-log for log_cm(nf) is probably slightly simpler and more efficient (because you don't need to compute GH(ρ), and in fact eliminate ρ entirely), provided that deriving the nullifier from cm works. I don't see any reason why it wouldn't, but it's more of a change relative to the Zerocash security proof.

I also don't want to keep the 2x2 JoinSplit, but haven't decided between a split circuit and a 1x2 (or 1xN) JoinSplit yet.

[ebfull]

Brian made a great observation while he was comparing what we were doing with petmail.

There is an attack where a sender can send money to one of your diversified addresses, but encrypt to another, in an attempt to see if they are linked. Depending on how the recipient acts or responds, it could leak that the addresses are related.

One solution would be to store the ephemeral private key inside the note plaintext. This serves two purposes: you can check that it was sent to the same address, and you now have the ephemeral private key for use in payment disclosures. What do you think?

[ebfull]

I noticed that the KDF can no longer work over the address in this scheme, so you won't be able to resist a quantum adversary without knowledge of your address.

@str4d points out that the d should be selected randomly. We also had a discussion about how much space we should allow for d.

[daira]

Actually it's not necessary for the KDF to take the address as an input in order to get post-quantum privacy for secret addresses; see https://github.com/zcash/zcash/issues/570#issuecomment-296450324

d needs to be large enough to avoid accidental collision when randomly chosen for (a conservative estimate of) as many diversified addresses are likely to be used for a given spending key. I suggest 80 bits.