Opportunistic note merging and splitting

[nathan-at-least]

Synopsis: Whenever creating a JoinSplit which has other-wise unallocated inputs or outputs, use those inputs/outputs to a. reduce the number of notes, and/or b. increase the minimum note value. This has efficiency and privacy gains with no notable cost.

High-level Spec: Whenever a JoinSplit is to be created with unallocated inputs and a change output, add the smallest extent notes to the unallocated inputs. Whenever a JoinSplit is to be created without a change output, but also with an unallocated output and two unallocated inputs, add a change output that merges the new notes in the unallocated inputs.

Background: A zaddr controls funds held in notes. In order to send X ⓩ to a destination, notes totallying ≥ X ⓩ must be consumed, with excess sent as change. The JoinSplit circuit arity is 2 input notes x 2 output notes, so consuming more than 2 notes requires more than 1 JoinSplit which degrades privacy and is at least twice as expensive to generate. Therefore, the larger the value held in notes, the more likely sending ⓩ to a destination will require fewer JoinSplits.

Furthermore, the wallet must calculate witnesses for each note, as these are required in order to spend the notes in a JoinSplit. Witnesses must be updated for a recent block to improve privacy (and this can be done lazily on spend or greedily as new blocks arrive; the current wallet uses the greedy indexing strategy). The fewer notes are held by the wallet, the less indexing resource cost is required. Therefore, the fewer notes held, the better wallet indexing performance.

Assumptions:

For a 2x2 JS circuit:

• assume concrete inputs/outputs are randomized to improve privacy against recipient analysis, so the rest of this discussion uses 'logical' indices, not 'concrete' indices.
• assume the second input (or output) is not utilized unless the first input (or output) is utilized.
• assume at least one input or output must be utilized.
• assume every utilized output is either a change destination, or a transfer destination, determined completely by whether the destination zaddr is the sending zaddr or not.
• assume if there are both transfer and change destinations, the transfer destinations are always at lower logical indices; change destinations always come last.
• assume selecting new notes or creating new outputs late in the JoinSplit input-gathering process is not expensive compared to JoinSplit creation.

Implications:

Given assumptions, [FIXME: How many possible combinations of I/O are there? -and which can be modified to do opportunistic note merging?]

[tromer]

Very minor drawback: JoinSplits that consume disjoint sets of notes can be created in parallel. Merging notes reduces the probability of such disjoint sets existing.

But if we were serious about enabling parallel JoinSplits, we would need to have some scheme for intentionally maintaining multiple, suitably-sized notes.

[nathan-at-least]

@tromer: Good point. However, I think for our current code architecture this doesn't come into play:

We currently have a 'work queue' that serializes the generation of proofs. I assume proof generation in libsnark already takes full advantage of parallelism, so there's not much throughput gain by farming out multiple proofs to separate worker threads to process the queue. (Can someone let me know if my assumption about libsnark is true or not?)

So one edge case / usage we haven't anticipated well would be multiple wallet machines operating the same zkey (secret key for the same zaddr).

[tromer]

Consider the case where you send out multiple payments from the same z-address, using multiple z_sendmany commands (which is not the best way, but certainly a natural one). Even if proofs are generated sequentially, you would hope they're generated back to back without waiting for blockchain roundtrip. But if you start with a single note, then each transaction can be generated only after the previous one has been mined.

(To answer your question: Libsnark uses available cores during most of the proving, but it's an open question whether running parallel instances with fewer core each will give higher bandwidth.)

[nathan-at-least]

@tromer Yes, I realized this later. So we need to balance the number of notes versus their sizes in some way.

[str4d]

We already have #1360 for deciding on a new note-selection heuristic. @daira outlined an algorithm for performing a "MultiJoinSplit" in #1360 (comment), which would be a good basis for handling the OP from this issue (which ze had also already mentioned in #1360 (comment)). I'll let @nathan-at-least decided whether to keep discussion on this issue here, or close this as duplicate.

[daira]

I believe the approach in the comment @str4d mentioned has essentially the same effect as described in this ticket.

[nathan-at-least]

@str4d, @daira: I disagree unless I [mis]understand that linked comment, #1360 (comment). Here's one way to describe the difference:

The algorithm in the linked comment starts with sorted lists of inputs and outputs. Opportunistic merge strategy is a decision about which inputs and outputs to add to the set of constraints such that a. no new JoinSplits are required to meet the constraints, and b. either the number of notes held by the sender is reduced due to opportunistic merge or the distribution of notes held.

Edit: Maybe we could distinguish the purpose of the algorithms by introducing a taxonomy of sub-problems: 'circuit composition', 'note selection', 'transaction composition'. I include transaction composition because in the future we may want to use multiple transactions to achieve a 'user requested transfer goal' (such as to maximize privacy or work around transaction size limits).

[nathan-at-least]

Hm, there are at least two kinds of 'opportunistic merge': the kind I originally described in this ticket uses a strategy summarized as 'attempt to use unallocated input or output notes in already selected join-splits composition' (*).

The other I had not carefully considered (and which might not be called 'opportunistic') is: 'when selecting input notes for a transaction, whenever there is a choice between combinations of inputs notes with all else being equal, choose the combination that merges the most notes.'

An example of the latter: Notes available are worth [50, 60, 100]. The user requests sending 70 to a recipient. A single JS can consume the [100] note, send 70 and create change in a 30 note, resulting in [30, 50, 60] distribution, or a single JS can consume [50, 60] notes, sending 70 and creating a 40 change note, resulting in a [40, 100] distribution.

(*) in this case for the goal of merging notes, but perhaps the same technique can be used for other goals.

[daira]

The prototype multijoinsplit algorithm in #1360 (comment) implements opportunistic note merging.

[nathan-at-least]

Kicked out of 1.0.9 since this is a big new feature that's not (directly) related to stabilization / safety.

[nathan-at-least]

Note: This was in Continuous Impovement triage queue. I removed in since Beswick and JoinSplit privacy are more specific and higher priority.

[daira]

I'm not sure we're going to get around to this before Sapling. In Sapling, there will be no "spare" input slots as there are for JoinSplits. OTOH the performance of Spend proofs is good enough that we might consider automatically adding inputs just for consolidation.