Some potential performance improvements

[JanBobolz]

So first of all, we usually shouldn't blindly optimize performance, but rather check for performance hotspots and try to fix those.

That said, here are some few things I noticed during the code review:

TokenPointsZkp with additional commitment

In the TokenPointsZkp, it may be worth it (especially for policies with many leafs) to have the user create an additional commitment C' to just the point vector (without usk etc.), instead of always proving knowledge of usk, esk, dsrnd, etc. that open the "full" signed commitment every time they want to prove anything about the point vector. This costs basically nothing (just one more multiexponentiation and one more Zp element to prove that C' can be opened to the same values as in the signed commitment) in the "main" proof, but makes every statement about the point vector quite a bit smaller.

Tracing performance

When decrypting the (user's share of) esk* during tracing, the all possible w^b should be precomputed, ready in memory. Furthermore, more crucially, the inner loop shouldn't recompute the right hand side of the equality check anew every time.
Ideally, the code is something like:

// During setup
for b in {0,1, ..., ESK_DEC_BASE}: compute and store w^b in a HashMap w^b -> b;
//During decryption
for each digit i: decryption[i] = decrypt_elgamal(i).compute(); //start running those computations in parallel.
for each digit i:
  result[i] = HashMap(decryption[i])

generateEarnRequestResponse: concurrency

In generateEarnRequestResponse, start computing the new SPSEQ first (in the background), then run the checks, instead of the other way around. Only return the SPSEQ if the check succeeds, of course.

[this-kramer]

Thanks for your feedback and suggestions!

Regarding the C' improvement: Do I understand correctly that you propose to add a 'C=C'\cdot C_0', where:

• C_0 is the commitment without the points, and C' contains the commitment on the points vector only?
• If so, do you think of C' as a
  1. common input with above equation proved in the MetadataZkp?
     (I guess we then need to randomize it,e.g. C=C'\cdot g^{-r}C_0 and C'=g^{points}\cdot g^{r})
  2. shared witness -> I don't think ProofOfPartialKnowledge supports it, so I guess the latter?
  3. Something else?

Anyways, sounds like a nice improvement (even though this unfortunately does not reduce the number of pairings if I'm not totally wrong)!

[JanBobolz]

My proposal is:

• The SPSEQ and the signed commitment C stay exactly the same.
• At the start of the proving process, the user creates a commitment C' to the point vector (with fresh randomness, does not have to be consistent between spend retries, so no PRF involved).
  • One can view C' as a sendFirstValue in the terminology of the ProofOfPartialKnowledge implementations, i.e. it's just generated by the prover as part of the "root" protocol and sent alongside the first message.
• In the "metadata proof", we add a proof that C' is well-formed and contains the same values as in C.
• All of the leaf nodes for the point statement proofs now take C' as common input, instead of the signed commitment C as they do now.

(even though this unfortunately does not reduce the number of pairings if I'm not totally wrong)!

Right, this will not change the number of pairings. It's relatively small though, no? We just check the SPSEQ signature once?