credential presentation at input registrations

[nothingmuch]

If credentials are only issued in output registrations and redeemed at input registration, then inputs and outputs are the vertices and credentials are (obscured) edges of a bipartite graph with maximum in/out degree k.

This is problematic for several reasons:

• clients have to know in advance what output amounts they wish to register
• clients with many small inputs must consolidate them in advance, linking them with intermediate outputs on the blockchain
• the k is an upper bound for the size of partitions when analyzing the resulting coinjoin
• requests are larger if k is made larger to compensate

These issues can largely be resolved by adding a reissuance operation, which introduces intermediate nodes on the graph so that it's no longer bipartite. Unfortunately this is a potential privacy leak since only some clients/rounds will require reissuance.

Instead we can simply add credential presentation to each input registration, and issue change credentials in each output registration, effectively unifying the two operations so that each registration is potentially a reissuance.

This is attractive since it allows k to be small without restricting the graph topology, since input registrations and output registrations may be arbitrarily strung together making all outputs plausibly connected to all inputs.

If credential presentation is optional this re-introduces the same kind of privacy leak that reissuance does, namely that initial vs. merging input registrations are distinguishable by the coordinator. A simple fix is to make credential presentation mandatory at input registration, but that presents a bootstrapping problem: how do users obtain initial credentials.

The bootstrapping could be solved by modifying the Show protocol to require a proof of a logical disjunction of a proof of knowledge of a valid MAC on the attributes, or a proof of knowledge that M_{v_i} = {G_g}^{r_{v_i}} <=> v_i = 0.

However, a simpler approach described here which achieves the same effect cryptography is to just add an auxiliary operation that issues null credentials that users can include in their initial registration.

[nothingmuch]

hmm, i seem to have pushed the wrong commit, converted to draft PR

[nothingmuch]

so somehow I managed to fat finger my way into deleting a whole section while committing, hence the extra }. fortunately it was still in my emacs undo history, so i managed to recover it for the most part.

aside: @seresistvanandras i'm not sure about having the boxes as floating figures, as that breaks up the flow unless they are combined into one figure in the new section, and we haven't put in references to the figures.

[nothingmuch]

pushed new commit with proper Co-authored-by trailer and up to date bibtex

[nothingmuch]

blech, i noticed some more errors in the commit message, i won't push again until it's ready to merge though