Refactor token ZKP tree

[JanBobolz]

The quick pitch

Currently, there are two "leaf" statements for the "Spend" ZKP: TokenPointsZkp and TokenUpdateZkp. Each of those can do ... basically anything: range proofs, equality, you name it.

This is done for performance reasons: every leaf proof needs to prove knowledge of the point vector and commitment opening (see #90), before being able to do any actual work; so aggregating everything into a single leaf makes sense performance-wise.

It comes with disadvantages though:

• The API for setting up one such leaf is quite cumbersome, having to operate on several arrays.
• The performance savings are stopping short slightly for some (somewhat specific) statements where I need to prove something about the old vector and the new one, forcing me to AND-compose both types of leafs, incurring some overhead.
• If we ever wanted to extend this, say, by proving set membership of some point vector value, or proving something about a weighted sum of vector entries, we'd have to make those two classes even bigger.

Proposal

Ideally for the API and class complexity (the first and last bullet point), every leaf just does a small specialized thing, i.e. we'd have small leaf nodes like "new LinearRelationLeafNode(new[i].equals(old[i].add(5))" or "new InqualityLeafNode(new[i], 20)".

To make this work with good performance, it would be up to the "tree compiler" (SpendDeductBooleanZkp) to greedily aggregate leaf nodes connected by ANDs into a single SchnorrProof (which would then correspond to a merge of TokenPointsZkp and TokenUpdateZkp).

For example, take ((A and B and C) or (D and E)) as a SpendDeduct tree, where each letter is any statement over the old and new point vectors.
Every such leaf statement has a method List<SchnorrFragment> getAsSchnorrFragments(Vector<ZnWitness> oldVector, Vector<ZnWitness> newVector) that outputs the SchnorrFragment corresponding to the statement (say, a range proof about some weighted sum of old and new entries, or whatever).

In that scenario, the tree conversion should set up two SigmaProtocols of type ZkpLeafProof. One to handle A and B and C and one to handle D and E.

The ZkpLeafProof would work as follows:

• The list of statements it should handle (e.g., A,B,C) is passed in the constructor.
• ZkpLeafProof asks each statement whether it intends to state something about the old vector and/or the new vector.
• ZkpLeafProof sets up a proof consisting of
  • the "I can open the old/new point commitment" statement (depending on which one is needed, or both)
  • the fragments returned by getAsSchnorrFragments of A,B,C.

If none of the statements say they want to prove something about newVector, then ZkpLeafProof would just pass null for newVector in the getAsSchnorrFragments call.

Better API for TokenUpdateLeaf

I'm not crazy about the "pass arrays of BigIntegers or null" interface design for TokenUpdateLeafs. The incentive system user should probably be spared this and be allowed to specify their constraints more naturally.
This would indeed be the case here because now users would just add one leaf node for every inequality/linear relation they want checked instead of having to aggregate them into arrays.

Related

Issue #90 asks to have subproofs do their statements over a small committed vector. This is orthogonal to this issue, but is easily done within the same rework.

One open API issue

Being able to write things like new LinearRelationLeafNode(new[i].equals(old[i].add(5)) would require there to be some variables new[i] and old[i] at the time of instantiating those.
I'd recommend doing this using the Cryptimeleon variable framework somehow. Let me know if you want to discuss ideas.

Time to implement

This might sound like a complex change now, but I'm pretty sure this is mostly copy/pasting existing code cleverly into new classes and simplifying it a bit; plus a little bit of tree logic and API improving.

[this-kramer]

@JanBobolz great vision for a v2 of the ZKP trees. I think we can classify this as one of the next features to implement after the checkout process is finished.
I'll then come back to you for discussing the cryptimeleon variable framework.