Base ledger private trade circuit design [ex-issue-16]

[cwgoes]

Discussion of private trade circuits we should aim to ship along with Anoma's initial launch.

[cwgoes]

Important categories of private trades to consider:

• Private fungible token exchange (simple swap, price for a token pair)
• Private non-fungible token exchange (simple swap)
• More complex private exchange (predicates)

Separately, we also want to think about private ways to gossip liquidity across the orderbook.

[cwgoes]

Additional background reading:

• Section 6.2, 6.3 of ZEXE paper
• Section here on Aztec docs

Likely we'll need a more general record system for private asset tracking.

I'd like to reason through what it would take to craft a maximally general private trade circuit as well - e.g. this would require private state (only Merkle roots stored), private validity predicates, WASM validation in a circuit, etc. - likely far too expensive but in the far future we'll want this, and a useful basis for comparison.

I'm also now reasonably convinced that we need to include direct negotiation in the intent gossip system.

[cwgoes]

Notes from pondering:

• We should implement private trades in a way which allows users to keep their assets in the shielded pool (e.g. MASP).
  • For this reason, a separate records system is not ideal.
  • One option is to generalise the MASP into a records system.
• What would it be to directly lift the validity predicate model to a ZKP?
  • Set of "accounts" with VM instruction sequences.
  • Proof must prove that all involved accounts whose state was written accept.
  • Then the MASP could check user validity predicates for senders of transfers, they could check signatures, etc.
  • How should we compare this with the asset-based approach?
  • More natural to "keep state"
  • Someone has to know the private state but not the ledger
  • Two-layer proofs would be nice (VP proof verification in main proof verification, so VP proofs can be separate)
    • Actually the VP proofs can just be verified separately outside - but how to deal with (private) state changes?

[cwgoes]

Another note - we should investigate delegated proving, it would be very nice for edge clients.

[joebebel]

So, here's what I've been pondering as well:

• There are two main models of private transactions: the UTXO/"note" like schemes, and the account balance type schemes (referred to as "ElGamal" by AZTEC)
  • The MASP design is fairly strongly tied to the note-like scheme, so a natural extension is to continue this; ZEXE+AZTEC both use this approach by default, for various good reasons
  • The account balance method has some nice attributes (eg. opportunities for FHE, no blockchain scanning) but does put more work onto the validator and is trickier to shield addresses
• In terms of private state, there are some things we should keep track of:
  • Private state that is shared between the parties in the transaction is not an issue; indeed, even in the MASP design, the value, asset type, and address keys are shared knowledge. So whoever creates the ZKP can easily use the shared private state in a verifiable way.
  • Private state that belongs to one party can be used by that party to make ZKPs, but the other party can't. Generally speaking, we won't be able to compute general functions on more than one party's private state, without something like FHE. I think we should intentionally try to avoid such arbitrary functions on multiple non-shared private states, unless the benefits outweigh the technical issues that have to be overcome
  • Limited computation on nonshared private state is possible by ANDing ZKPs together. For example, party 1 can make a ZKP of predicate P_1 on their private+shared private state x_1, party 2 makes a ZKP of predicate P_2 on their state x_2, then if both ZKPs are valid then we know P_1(x_1)*P_2(x_2) = 1 as well. I think this is probably enough for what we need.

OK, now let's address the records system:

• The ZEXE approach is quite compatible with MASP; specifically I think that MASP notes and generalized records can exist in the same shielded pool/merkle tree.
  • The idea would be that leafs can represent notes or records, which can be distinguished by personalization of the Pedersen hash (in the same way that different levels of the merkle tree have distinct personalizations from notes and other levels)
  • Whether this is necessary or not depends a little bit on what records need to be published to chain. Anything that goes on chain can go into the pool, and if all negotiation of the tx happens off chain, then possibly only notes (and not generalized records) need to be in the pool.
  • How might this look? Suppose that two parties have agreed on an exchange with certain shared private state s (exchange data like asset types, values, etc). Then one party can write a ZKP authorizing Spend of its notes subject to a matching Output ZKP with the same exchange data. This isn't possible with the existing MASP Spend and Output circuits, but new circuits should be able to it. Therefore the tx validity check is now different, because the validator needs to check new ExchangeSpend and ExchangeOutput proofs, but the notes that are input/output do not necessarily need to change.

Before describing ExchangeSpend and ExchangeOutput further, one important observation. In MASP (and Sapling) the sender of a tx can actually send garbage to the recipient and there is nothing in the protocol to externally detect or prevent this (of course, the recipient immediately realizes they got garbage, and generally one can rely on the sender of a tx to not destroy the asset they're sending). However in a DEX we want to ensure that one party doesn't end up with garbage, in case a party has some incentive to burn their outgoing asset instead of sending.

One idea is to check the output note commitments in the ExchangeSpend as well as the ExchangeOutput. In this case, each recipient would verifiably have enough information to spend a note before the tx is processed. So then the shared state includes asset types, amounts, keys, and output note commitments; the tx verifier checks that all ZKPs in the tx have this same shared state as input, and therefore ExchangeSpend can only be used in a tx if accompanied by the correct other proofs.

This approach doesn't handle the "cancel" case (as described in ZEXE). In ZEXE style, a tx can also be accepted with a subset of ExchangeSpend proofs along with a Cancel proof, with some consistency checks. This prevents the other party from indefinitely holding a free option to either execute the exchange or not; alternatively ExchangeSpend proofs can also come with an expiration timeout (avoiding tx fees for a Cancel)

Unfortunately a Cancel leaks information because the nullifer is revealed in ExchangeSpend, and the same nullifier is revealed later in another ExchangeSpend or Spend. I'm not immediately sure how to cure this issue.

[joebebel]

In terms of delegated proving, it's notable that Sapling (and therefore MASP) allow delegated proving as described in the Sapling protocol spec. It does require revealing viewing keys to the delegated prover as well as spend authority for the note being spent, but I think this existing method would possibly work well for ExchangeSpend as well.

[cwgoes]

Possibly worth consulting here w.r.t. checking encrypted data - Henry de Valence's notes on building up encryption from Poseidon using something like the Strobe protocol framework, which as I understand it would then make the encryption relatively inexpensive to check in the circuit itself.

[joebebel]

I think between traditional commitments and building encryption from Poseidon, it should be feasible to do what we want.

Now on checking validity predicates: I already observed that there is a limited version of this check already in place in Sapling/MASP as the nsk is checked in the Spend circuit, verifying that the note spender has authority. The question then is how to generalize this to other validity predicates, ultimately to the same level of flexibility as WASM validity predicates will for transparent transactions.

Some observations about properties we might want:

• Fully private validity predicates - meaning that even the builder of the transaction doesn't know details of each party's validity predicate - is potentially theoretically possible but probably impractical in the near term as it requires fancy crypto (FHE/FE/iO). But someday perhaps
• Fixed set of preprogrammed validity predicates: initially, there may be a small number of predicates that anyone might use (standard signature, standard token, etc) and it would be easy to hardcode a small set into a circuit
• General circuit predicates: the user/address provides a plonk circuit that serves as their shielded VP. Unfortunately now the VP circuit itself must be encrypted (otherwise, it likely uniquely identifies the user/address) which presents a problem for verification
• Fully unified validity predicates: the user specifies a single VP, ideally in a high level language, and the compiler guarantees behavior to be consistent between the WASM version and the circuit version

I'll leave it as an open question whether preprogrammed validity predicates are a good short term idea.

Hiding the VP circuit is the primary technical challenge. The tx builder, knowing the circuit, must write a proof of the form "the VP circuit was satisfied by the tx plaintext". Two ideas:

1. This is possible using one-layer proof composition

In one-layer composition the tx builder proves the VP circuit, then verifies the proof inside another circuit. I think this will have scaling issues. If the VP circuit is small, then the VP circuit can be proved using PLONK/IPA (say, over JubJub) and then verified in the "main" circuit which is PLONK/KZG over BLS12-381. The size of the largest allowed VP dictates the performance. There is also a mismatch problem between the scalar field of VP circuit and the scalar field of the MASP circuit.

Alternatively BLS12-377 can be the inner curve and MNT the outer. This allows much bigger VP at the cost of much more expensive verification. There is a mismatch between the scalar field of VP circuit over BLS12-377 and the scalar field of the MASP circuit over BLS12-381, unless we change MASP to BLS12-377.

Alternatively PLONK/IPA over Pasta curves can be used for everything: MASP, VP, etc. This solves all mismatches with a large concrete cost increase which can be amortized away in the Halo 2 style.

2. Another "wild" idea is the possibility of blinding the circuit check to hide which circuit is being used. The idea is that the block verifier just needs to know what inputs of the pairing to use, and not the circuit, so the commitments to the wire polynomials are enough. This idea requires further exploration to decide feasibility, but it would be far more practical than one layer proof composition if feasible.

[joebebel]

Another quick note, there is another alternative to PLONK/IPA for one layer proof composition: R1CS via Spartan. This would have some more scalability than PLONK, allowing for larger VP, at a greater engineering cost to design and build such a scheme.

[joebebel]

I think the simplest approach to checking validity predicates right now is blinding the PLONK polynomials, and checking the blinding takes roughly 7 non-native scalar multiplies in circuit. Assuming the blinding details work out.

The alternative, which is likely to work well, is to use BLS12-377 over MNT - checking all the proofs of validity predicates as private data. This might also be rather straightforward, since it requires less novel code than blinding PLONK.

[cwgoes]

Limited computation on nonshared private state is possible by ANDing ZKPs together. For example, party 1 can make a ZKP of predicate P_1 on their private+shared private state x_1, party 2 makes a ZKP of predicate P_2 on their state x_2, then if both ZKPs are valid then we know P_1(x_1)*P_2(x_2) = 1 as well. I think this is probably enough for what we need.

I think this is a reasonable limitation for the initial set of private bartering circuits; later on or more long-term we can try to pursue more advanced options allowing computation over shared private state.

The idea would be that leafs can represent notes or records, which can be distinguished by personalization of the Pedersen hash (in the same way that different levels of the merkle tree have distinct personalizations from notes and other levels)

This is fine, but I wonder if we need it - can't records also do shielded transfers (perhaps a bit less efficiently)?

One idea is to check the output note commitments in the ExchangeSpend as well as the ExchangeOutput. In this case, each recipient would verifiably have enough information to spend a note before the tx is processed. So then the shared state includes asset types, amounts, keys, and output note commitments; the tx verifier checks that all ZKPs in the tx have this same shared state as input, and therefore ExchangeSpend can only be used in a tx if accompanied by the correct other proofs.

Does the recipient need any other information (besides output note commitments) which we'd have to check, or just those?

This prevents the other party from indefinitely holding a free option to either execute the exchange or not; alternatively ExchangeSpend proofs can also come with an expiration timeout (avoiding tx fees for a Cancel)

I think we want to avoid this specific approach because it requires an extra on-chain transaction to create the record (escrow).

In terms of delegated proving, it's notable that Sapling (and therefore MASP) allow delegated proving as described in the Sapling protocol spec. It does require revealing viewing keys to the delegated prover as well as spend authority for the note being spent, but I think this existing method would possibly work well for ExchangeSpend as well.

Aye; let's aim to preserve this capability wherever possible.

I'll leave it as an open question whether preprogrammed validity predicates are a good short term idea.

We should certainly have examples, but ideally users would also be able to write their own (private) VP circuits.

If the VP circuit is small

Do we have any idea "how small is small" ?

This solves all mismatches with a large concrete cost increase which can be amortized away in the Halo 2 style.

That is, by accumulating, e.g. all proofs within a single block?

I think the simplest approach to checking validity predicates right now is blinding the PLONK polynomials, and checking the blinding takes roughly 7 non-native scalar multiplies in circuit. Assuming the blinding details work out.

What do we need to do to investigate the possibility of so blinding? If that works, this proposal seems compelling.

[joebebel]

I think this is a reasonable limitation for the initial set of private bartering circuits; later on or more long-term we can try to pursue more advanced options allowing computation over shared private state.

Hopefully, for quite a while; I think a pairwise shared private state model can handle all the cases laid out in the Anoma vision/whitepaper. For example, if an n-party exchange is needed because (for example) exchanging coin A to D via A-B-C-D is only possible by A-B, B-C, C-D intermediate exchanges (with 3 different counterparties), then the only shared private state needs to be pairwise between each party/counterparty; say, party 1 can request A-D from party 2; party 2 negotiates A-B with party 3, B-C with party 3, C-D with party 4, all incorporated into a single tx.

This is fine, but I wonder if we need it - can't records also do shielded transfers (perhaps a bit less efficiently)?

Yeah, you're right; I don't think we need to record intent in the merkle tree.

Does the recipient need any other information (besides output note commitments) which we'd have to check, or just those?

There's a few components to the note plaintext, but it's really quite small (except for the memo field). It's a relatively easy check and I don't even think it will require anything fancy, but I think it wasn't a requirement of the Sapling security model to require output ciphertext checking whereas here it does.

I think we want to avoid this specific approach because it requires an extra on-chain transaction to create the record (escrow).

Sure, I think I better understand this approach now and none of it has to be on-chain except for the final Exchange or Cancel transaction. There can be a timeout on the Exchange operation, if we want, but the Cancel is necessary to avoid leakage of the nullifier.

We should certainly have examples, but ideally users would also be able to write their own (private) VP circuits.

I think the overall complexity of the system is largely determined by the complexity of the most complex VP, but if supporting complex VPs is important, then we must.

Do we have any idea "how small is small" ?

Let's say the biggest VP circuit is negligible compared to the size of the Spend circuit, then checking the VP with PLONK/IPA in the Spend circuit over PLOMK/BLS12-381 only incurs a modest penalty on everyone with simpler VP. Basically one-layer proof composition with no curve issues, at the cost of increased prover time for everyone, up to the biggest VP circuit.

I think this is reasonable if validity predicates check simple circuit friendly signatures and such. I can't really envision a use case for a huge VP that has to do many (say) hashes but of course I don't want to limit the system arbitrarily either.

That is, by accumulating, e.g. all proofs within a single block?

Yes, I think managing the complexity is much easier with accumulation. However, accumulation does put maximum size restrictions on the VP in a similar way since the VP is written in PLONK/IPA. I don't see a straightforward way around this, which is why I hesitate to outright recommend it.

What do we need to do to investigate the possibility of so blinding? If that works, this proposal seems compelling.

The primary implementation task is probably plookup non-native arithmetic, and the primary brain task is writing out the blinding and proving the relevant soundness and hiding properties. The downside is probably slightly larger tx sizes (1 extra circuit description + 1 VP plonk proof per party, which is probably about 1.5 plonk proof sizes)

[joebebel]

OK, here is a (tentative) plan:

1. Implement an Exchange which combines the Spend and Output circuits
   • The Exchange authorizes spending a note of one asset/value and produces a note of a different asset/value at the agreed rate
2. Implement VPSpend and VPOutput circuits for MASP that are like MASP, but are coupled with a blinded VP proof to authorize Spend or Output.
3. Add a similar blinded VP check to the Exchange circuit

Actually, in this case, the Exchange proof creator can create their own output note commitment. So maybe we don't even need a ciphertext check.

I think the only complication that I don't understand now is that Spend/Exchange authorization always requires secret knowledge from the note holder, and then the note enters the (permanent) spent state. So there's a limited amount of authorization that a validity predicate can provide.

Let's take the "subscription" example from the whitepaper. I want to subscribe to a site that is $1/month, for 12 months, and I have a note worth $15. So I can send one tx that splits my $15 note into 12 $1 notes and one $3 note. Once I have the $1 notes I can send to the site all 12 VPSpend proofs for the 12 notes, along with a signed message authorizing my VP to accept a spend of the i'th note on the 1st of the i'th month. Then the site can submit once per month a tx to the chain with a valid VPSpend proof, proof of satisfying the VP, etc.

This achieves the desired goal, but seems a little clunky to me. For one, I need to set up all the notes in advance. Even if the VP only authorized spending part of a note, the new note output from a tx can't be VPSpend before it's produced; hence the need to split my $15 note beforehand.

[cwgoes]

Hopefully, for quite a while; I think a pairwise shared private state model can handle all the cases laid out in the Anoma vision/whitepaper. For example, if an n-party exchange is needed because (for example) exchanging coin A to D via A-B-C-D is only possible by A-B, B-C, C-D intermediate exchanges (with 3 different counterparties), then the only shared private state needs to be pairwise between each party/counterparty; say, party 1 can request A-D from party 2; party 2 negotiates A-B with party 3, B-C with party 3, C-D with party 4, all incorporated into a single tx.

We'll need to think a little bit about how this negotiation will work, since the parties want to avoid creating proofs during negotiation which can be used to settle trades that they didn't want (e.g. not the full swap), but presumably this is possible since their validity predicates can tie different pieces together and require that all be present before accepting.

There's a few components to the note plaintext, but it's really quite small (except for the memo field). It's a relatively easy check and I don't even think it will require anything fancy, but I think it wasn't a requirement of the Sapling security model to require output ciphertext checking whereas here it does.

:+1:

Sure, I think I better understand this approach now and none of it has to be on-chain except for the final Exchange or Cancel transaction. There can be a timeout on the Exchange operation, if we want, but the Cancel is necessary to avoid leakage of the nullifier.

Hmm, can we investigate this a little? Is it possible to craft a way in which potential exchanges can by default timeout (with no transaction settled) without leaking a nullifier, or not?

OK, here is a (tentative) plan:

1. Implement an Exchange which combines the Spend and Output circuits

   • The Exchange authorizes spending a note of one asset/value and produces a note of a different asset/value at the agreed rate
2. Implement VPSpend and VPOutput circuits for MASP that are like MASP, but are coupled with a blinded VP proof to authorize Spend or Output.
3. Add a similar blinded VP check to the Exchange circuit

Actually, in this case, the Exchange proof creator can create their own output note commitment. So maybe we don't even need a ciphertext check.

Let's try this!

I think the only complication that I don't understand now is that Spend/Exchange authorization always requires secret knowledge from the note holder, and then the note enters the (permanent) spent state. So there's a limited amount of authorization that a validity predicate can provide.

Let's take the "subscription" example from the whitepaper. I want to subscribe to a site that is $1/month, for 12 months, and I have a note worth $15. So I can send one tx that splits my $15 note into 12 $1 notes and one $3 note. Once I have the $1 notes I can send to the site all 12 VPSpend proofs for the 12 notes, along with a signed message authorizing my VP to accept a spend of the i'th note on the 1st of the i'th month. Then the site can submit once per month a tx to the chain with a valid VPSpend proof, proof of satisfying the VP, etc.

This is a little clunky, yes. That said, it's not that different from what our intent gossip network is doing already, so at least architecturally it wouldn't be difficult to provide software which tracks these messages and proofs for the site operator, or even for someone else to track them - as they don't contain any confidential information, right? Actually I think maybe the key distinction on whether this is too clunky or not is whether the roles can be split so that the site operator can outsource this data management to a third party who can receive a small fee for doing so.

However, what we'd really like to enable in this case is something different, I think - we want a subscription that is "$1/month, out of this account, until cancelled" - that means that the subscriber needs to sign something authorising splitting their note of "$x" each month into "$1" and "$x-1", until they submit another transaction to the chain which revokes this subscription authorisation. Is this possible, or not? Could this be accomplished by something like the website or third party operator creates the new notes but has to send the "$x-1" note back to the subscriber?

[simonmasson]

The primary implementation task is probably plookup non-native arithmetic, and the primary brain task is writing out the blinding and proving the relevant soundness and hiding properties. The downside is probably slightly larger tx sizes (1 extra circuit description + 1 VP plonk proof per party, which is probably about 1.5 plonk proof sizes)

I wrote a small note on a possibility of blinding the circuit here.

[joebebel]

I think the plan makes sense now. To summarize with more detail:

1. The Exchange circuit is exactly a Spend and Output circuit combined together, potentially with some tiny optimizations (e.g. combine value commitments)

The nice thing is that for this circuit it should Just Work; no issues with output ciphertext validity, etc. In fact to do an exchange from A-B you can just write an Exchange proof consuming your notes of A and creating your notes of B, and the exchange maker can fill in the rest of the tx (there are some details where multiple input notes produce multiple output notes of the same exchange value, which may have some rounding error in the rate, etc; we can discuss more)

2. VPSpend/VPOutput. Basically what changes here is that the spend authorization check gets removed from the circuit, and is replaced by a validity predicate blinding check of the form:
   • public input "blinded PLONK circuit" and "hiding commitment to a PLONK circuit"
   • private inputs "unblinded PLONK circuit" and "blinding polynomials"
   • it is checked that the blinded circuit is the unblinded circuit in the commitment. The important property is that the correct validity predicate circuit is blinded.

It's actually an interesting question whether to check the validity predicate in the Output circuit. Because in Sapling the assumption is that it's always allowed to receive a note, but this might be prohibited in a validity predicate for some reason.

3. VPExchange should work in the same way. Actually, it could be worth implementing a fully general VPAction to replace all existing circuits hiding whether a transfer or exchange occurred.

The validity predicate works in the following way:

1. Fully private accounts require spend authorization signature, as before
2. Validity predicate accounts have to delegate full viewing key authority to one or more online third-parties who are permitted to check the validity predicate and prove the VPAction circuit. Spend authority is not delegated per se; the ledger should allow the third party to spend a note iff the spend satisfies the VP.

The reason for delegation in 2 is because, in general, full viewing authority is needed to prove the VPAction circuit and prove the VP circuit. For example, even just to know what notes are available to spend. Fortunately, this seems like a mild restriction and perhaps a great service that can be provided by an appropriate trusted party.

[lopeetall]

Here's my idea for using a second snark to prove the expected VP was used.

Say the blinding is done as in Simon's note above:

q'(x) = q(x) + b(x)Z_H(x) where b(x) = b_0 + b_1*x for some random b_0 and b_1 of the Prover's choice.

The commitment [q'] is published and used in the first proof.

In a second proof, [q'] is included as a public input, while [q], b_0, and b_1 are private inputs. In the second proof, the prover shows they know a [q], b_0, and b_1 such that [q'] = [q] + [b_0 + b_1*x]*[Z_H]. To get around elliptic curve point multiplication issues we'd hardcode the points [Z_H(x)] and [x*Z_H(x)] into the circuit and check the equation as [q'] = [q] + b_0*[Z_H] + b_1[x*Z_H].

Because it's a snark, the Prover is not bound to using the exact same polynomials q and b as they actually did in the first proof. But they can't cheat (I think) because if they found alternatives p and c such that q' = p + c*Z_H, then p = q + (b-c)*Z_H meaning that p takes on the same values as q on H, so it is just another valid circuit description of the same VP.

[joebebel]

This looks really nice, I think this will be very practical. In fact I wonder if there's a simple way to implement the [q'] = [q] + b_0*[Z_H] + b_1[x*Z_H] without plookup (simple meaning easy to implement, not small circuit) that we could prototype quickly. Since there's only a small number of arithmetic ops.

In the second proof, the prover shows they know a [q], b_0, and b_1 such that [q'] = [q] + [b_0 + b_1x][Z_H]

I did forget one step here - the circuit needs to check not only knowledge of [q], but that [q] is the correct validity predicate for the owner of the note. I had assumed that [q] would just be signed, but this does not handle the case where someone changes their validity predicate (they cannot undo the old signed VP). So somehow we need to keep track of all the current validity predicates, say in a merkle tree, then the prover has to prove correctness of the [q'] and validity of the [q].

To get around elliptic curve point multiplication issues we'd hardcode the points [Z_H(x)] and [x*Z_H(x)] into the circuit

Actually this does beg a question, what is [Z_H(x)] here? If it's the same H for each VP, then that determines the maximum size VP. I think we can choose H here to be maximal (the largest 2^n size subgroup) and it will work for any circuit as Z_H(X) should still be 0 mod any Z_\hat{H}(X) for a subdomain \hat{H} ... right?

Because it's a snark, the Prover is not bound to using the exact same polynomials q and b as they actually did in the first proof. But they can't cheat (I think) because if they found alternatives p and c such that q' = p + cZ_H, then p = q + (b-c)Z_H meaning that p takes on the same values as q on H, so it is just another valid circuit description of the same VP.

I think this is ok, what do you think @simonmasson?

[joebebel]

In my opinion, a cheater would be able to deal with all circuits: he chooses his proper circuit polynomial qq, and then choose b and q'= qq + b*Z_H as required.

Right, so the original plan is not good enough. The authenticity of the [q] private input needs to be checked, so then the only values a cheater can choose are b_0, b_1. Then I think by @lopeetall's argument it works.

If necessary, we can also require that b_0,b_1 are derived though a PRF so it is difficult to choose malicious values.

[cwgoes]

Actually, it could be worth implementing a fully general VPAction to replace all existing circuits hiding whether a transfer or exchange occurred.

This would be nice, substantial privacy benefits for whichever of transfers or exchanges happens less frequently (esp. at first).

So somehow we need to keep track of all the current validity predicates, say in a merkle tree, then the prover has to prove correctness of the [q'] and validity of the [q].

This would be nice. If it's too expensive, a validity predicate could also in principle itself keep in state the verification key for a second circuit, which it could then use to verify, using an additional layer of recursion, right? This is analogous to what we do at the moment where validity predicates can eval WebAssembly.

[joebebel]

This would be nice, substantial privacy benefits for whichever of transfers or exchanges happens less frequently (esp. at first).

The main argument against lumping everything into one circuit is probably increased memory requirements for proving. We might have to evaluate if it becomes prohibitive.

This would be nice. If it's too expensive, a validity predicate could also in principle itself keep in state the verification key for a second circuit, which it could then use to verify, using an additional layer of recursion, right? This is analogous to what we do at the moment where validity predicates can eval WebAssembly.

Maybe, though I'm not sure this helps. The main problem is being able to cancel or replace a VP, there has to be some tracking of that. Since the prover can replay old signed validity predicates, there has to be a public input that verifies that the validity predicate is current, without revealing the VP; hence the need for a cryptographic accumulator like a Merkle Tree.

I think the current idea is sound but it is just constraint-expensive to check a second Merkle path in circuit; however in the long run maybe this can be optimized with plookup/Sinsemella

[joebebel]

So, I rather like the idea that the merkle trees contain both "regular notes" and "VP notes" (where the note doesn't represent any asset or value, but rather an allowed validity predicate for that address). This makes updates of the VP's part of the same anonymity set as the asset notes, which is nice.

Then it's actually quite straightforward to check the blinding - it's almost exactly like spending a regular note, except that if the "VP note" is "spendable" then we know that's an OK validity predicate to use for that address.

I should note that @42ndTowel's suggestion about consuming the note is necessary here. When a "VP note" is "spent", which reveals it's nullifier, it cannot be used again, so the transaction has to output a new "VP note" to replace it. Otherwise, there is no way to check if a "VP note" is still valid or not (since the merkle tree of notes is append-only)

We still have a serious problem, that I didn't fully appreciate until now: the recipient of notes must receive private information that allows them to spend the notes., probably through the Sapling/Orchard in-band distribution mechanism.

The problem? In the Zcash model, the creator of a transaction is not likely to want to burn the output of the transaction by withholding the critical information from the recipient (it's equivalent to them destroying their own money, which they can always do by different means). But if a third party is now constructing transactions, they can use someone's VP to validate the tx, but then skip the distribution step, effectively spending the sender's money but the recipient gets nothing.

[cwgoes]

But if a third party is now constructing transactions, they can use someone's VP to validate the tx, but then skip the distribution step, effectively spending the sender's money but the recipient gets nothing.

Can we check this (check that the correct private information is encrypted) in the circuit itself?

[joebebel]

This would use the "SNARK-verifiable encryption" idea: there's some symmetrically encrypted payload that we want to verify the contents of.

But while it's technically feasible I would rather come up with some clever workaround that doesn't depend on something like that.

[joebebel]

After chatting with Pratyush and str4d I think we should do a verifiable encryption scheme to solve this. Basically Zcash will start using Poseidon as the PRF to get randomness for transcript aggregation, so we might as well start depending on the Poseidon assumption for other things as well.

There is a question in my mind whether we go for the quick approach (encrypt the relevant values asset type, value, diversifier, randomness seed directly, without symmetric key encryption - this costs an extra PRF to derive rcm from rseed) or the complex approach (implement a whole Poseidon based AEAD and use that for note encryption).

[joebebel]

Let's see. The Action circuit could be changed in these ways:

A validity predicate is a PLONK circuit given by some polynomial commitments together with an owning address/key. A blinded VP is the polynomial commitments, hidden with some blinding factor.

Note commitments can be either regular note commitments, or a commitment to a validity predicate (the type of note is indicated by a flag)

The Action circuit, and a new CheckVP circuit, takes public input two "blinded" VPs, one for the spent note and one for the new note, and private input the corresponding VP note commitment and blinding factor.

The public input to a validity predicate is the ordered list of incoming nullifiers, and outgoing note commitments, for every Action with that blinded VP as public input. The private input is the opening of the note commitments (both incoming and outgoing).

An Action circuit is given a regular (value) note to spend, instead of checking the spend authorization, it checks the key in the spending VP note commmitment against the spent note, and checks the blinding of the VP. (Then the same with the output note)

A CheckVP circuit is given a VP note to spend, it checks the VP note against the blinding of the VP, and checks that the VP note is in the merkle tree, which ensures that the blinded VP is valid. The CheckVP is given as public input the nullifier of the "spent" VP note, ensuring that the VP note is "current". The output note is the new VP note, whose owning key must be the same as the incoming VP note.

Both Action and CheckVP circuits use verifiable encryption on the output notes to ensure proper distribution.

We want the following properties:

1. An Action can only spend or output a note if the provided blinded VP circuit approves it; this should follow because the validator will provide the spent or output note commitments as public inputs to the blinded VP.
2. For each blinded VP in a transaction, there is a CheckVP circuit that checks that the blinded VP matches an unspent VP note.
3. A VP note commitment can only contain a certain key, if that key authorized an original VP which approved a chain of VP that ends with that newest VP.
4. An Action can only spend or output a note if owner (key) of that note has an authorized VP approve that spend or output; this is because the Action and CheckVP have common public input (the blinded VP), the Action circuit checks the spending/output key against the VP note commitment; the CheckVP checks that the VP note is valid and current; and the VP checks that the transaction is authorized.

There's probably at least 5 remaining problems with this:

1. The output address diversifier is a problem. There would need to be a separate VP note for each diversified payment address, which is not infeasible, but is annoying.
2. The VP is given a lot of inputs, this might make the circuit unreasonably large (although it does not need to check merkle paths or anything for these notes)
3. There are probably logic bugs in this scheme, plz find them

[joebebel]

I think I don't like this approach, because it's not using the full power of the accumulation scheme. For example, it's actually not necessary at all to have the blinded PLONK circuit or the VP proof be part of the transaction at all; it would be better to have the VP proof added directly to the accumulator (potentially with a blinding factor; but there would be not need a separate check of the blinding factor, only to include it in the accumulator's proof)

However, there are some parts which aren't clear to me at all:

1. Do we do this accumulation in every Action circuit? If not, where do we check the accumulation of VP?
2. What are we accumulating on top of? Unlike the case where (for example) everything in a block is accumulated into the accumulator for the previous block, there are going to be many transactions with many VPs in a block, and each needs to be accumulated onto something. Even more complicated is that the prover for a transaction doesn't even know which block might be the previous block.

At least for problem 1, I think the solution is still to have a separate CheckVP circuit. Instead of sharing a blinded VP with each Action circuit, we would only need to share the commitment to the VP, which is a lot simpler.

(Side note: One problem with a separate CheckVP circuit is that it breaks the anonymity set between regular notes and VP notes; we might want to merge it all into the Action circuit, as long as we can ensure that the VP is checked somewhere)

Problem 2 is much trickier. I have no idea how to do this (although I am confident that it is theoretically possible - we just have to figure it out). It might be ok to just have a separate VP proof accumulator for each transaction (that might get accumulated into other accumulators later, but that's besides the point)

[joebebel]

So things are still a bit unclear, except that I think the question I just asked (what do we accumulate on top of?) is actually not important. Each block should have 1 accumulator (or maybe 2; one each for Pallas and Vesta, we'll have to look at what Zcash is planning carefully) which will accumulate all proofs within that block.

In the long run, the next block will simply accumulate onto the previous block (this is a separate thing we can discuss independently)

But for now, since we already need block-level accumulation, we shouldn't (or at least don't need to) accumulate at the transaction level, which avoids the question of what gets accumulated. This might make transaction size larger, but since they get accumulated into a block, it doesn't consume more space on chain.

Therefore, we should probably just go back to the blinded VP approach:

1. A tx consists of some number of Action circuits, blinded VPs, and VP proofs
2. Action takes as additional input the correct private VP (and public commitment)
3. Blinded VPs take public input the ordered list of nullifiers/note commitments, and private input the openings that are relevant
4. Some of the Action proofs do the "CheckVP" step instead of regular "Action" (we can distinguish by a private flag)

The issues I'm still unsure how to do are:

1. We have to make sure that there is an exact 1-1 correspondence between notes that are opened in the VP, and notes that are used in an Action circuit linked to that VP. Basically I want to prevent the scenario where a VP is given more notes than are actually used in Action circuits, or vice versa, notes are used in an Action circuit but not given to the correct VP. We might need some kind of "transaction level commitment" which is given to all the circuits, I'm not sure.
2. Related to 1, but we have to make sure that at least one of the "Action" circuits is doing the "checkVP" step instead of a regular "Action" (a transaction cannot contain only "Action" and no "CheckVP" for example).

[joebebel]

Subprojects and sub-subprojects (thanks @lopeetall for the notes!)

1. Making the Orchard circuit multi-asset

We need to add multiple-asset support to Orchard, either in a similar way that we did to Sapling, or in a way more like Zcash Shielded Assets (https://github.com/zcash/zcash/issues/830). Since Zcash will be adding support anyways, there's some possibility for shared effort, but in the worst case, we're not reliant on their approach.

2. How to write VPs that compile to Plonk

We will need a proving system for VPs, which at first will be written by hand and later by some tools like Juvix etc. Fortunately we have a couple good options for this - and once the transaction format is finalized we can design some example VP circuits.

3. Enforcing VP privacy

We already have some good ideas on how to prove (and check proofs) of blinded VPs, though we need to convert it to the Halo 2/IPA commitments scheme. This includes implementing an in-circuit blinding check (to make sure that the blinded VP is a blinding of a correct VP) and proving that the soundness of the proof system is still ok.

4. Transaction level processing/out-of-circuit checks

This is the main challenge - we need some kind of metadata processing to ensure consistency among all the circuits (including VPs) in a tx. In Sapling/Orchard, this is the value commitment balancing - each circuit is only concerned with the value of it's own note(s) and none of the circuits actually check that the transaction balances correctly. Instead, the value commitments are added and checked outside of the circuit (avoiding any need for each circuit to consider transaction-level metadata).

However, validity predicates aren't homomorphic so this makes it trickier to check. We'll need some clever idea here. In the worst case, the entire transaction should be committed to and opened in each circuit - this is "feasible" but not necessarily "efficient".

5. Efficiency (shrinking large circuits and transactions)

Once the circuits are all designed, the transactions are going to be rather large, since Halo 2 proofs are on the scale of kilobytes (and we will have more of them, since VP circuits and proofs are included).

So at minimum we will need Halo 2 accumulation at least at the block level: mempool transactions are large, but the block proposer accumulates them so only 1-2 proofs are needed per block. Fortunately, Zcash will be working on this as well, so shared effort is possible (although our situation is more complicated because of accumulating different VP circuits)

In the worst case, we can also do transaction level accumulation (accumulate all proofs within a tx) although I don't think this will be necessary.

6. Information leakage VS Transaction size (how much to rely on trusted 3rd parties to handle metadata)

Ultimately an exchange will only work if some information is leaked - otherwise there is no way to match people to trade (without fancy crypto like FHE/iO). So we have to figure out when and where to leak. Leaking exchange rate publicly is probably not that bad - in fact it could be a feature as it helps the market do price discovery. This can maybe be incorporated with the unshielded intent gossip system.

Alternatively this could be a role for a trusted/centralized third party. At least, leaking to a third party is more private than leaking publicly. However, since there's not a perfect way to handle this, we should add as much flexibility as possible.

7. Verifiable symmetric encryption

Since the transaction creator can output invalid note ciphertexts (potentially burning the output notes), the system has to make sure that VP-authorized transaction-creation authority (which so far only requires viewing key authority for the relevant keys) doesn't allow burning-authority as well. Probably the way to do this is with Poseidon-based verifiable encryption of the note ciphertext.

In principle this doesn't require any new ideas, however the implementation might be somewhat complex.

8. VP discovery 8a. How to find a current VP

Sending to an address now requires knowledge of the recipient VP, which could be included in the address (which would be quite unwieldy), or maybe the VP can be posted transparently on the blockchain (also unwieldy). The large size of VP circuits compared to addresses is a problem. At least for right now, this is more of a "usability" problem than a "technical" problem, although we should try to solve it by engineering some kind of better solution.

8b. How to find the new VP after a former one is consumed?

Related to 8a, this is additionally complicated if VPs are not simple static objects but instead are created and consumed with each tx (e.g if VP commitments are stored in a note merkle tree) The same properties which ensure that VPs are always up to date, also make it difficult for senders to keep track of the relevant data (e.g. the VP commitment in the merkle tree) which is needed to send notes. This is also somewhat of a "usability" issue, but is also a privacy issue, since if Bob knows Alice's VP commitment note, then Bob also knows which transaction which created that VP note (although not the contents)

In short, as you can tell, adding validity predicate support is a major project with subprojects that range from "some implementation required" to "the entire scheme needs to be designed" - and nothing is set in stone yet (which is good since we haven't met all the design requirements, yet!)

[joebebel]

So if a transaction is made up of "partial transactions" (without the requirement that the value balances), each partial transaction can be checked by all VP within the partial transaction. This handles the Alice-Bob-Charlie trade as follows:

Alice wants to exchange X for Y Bob wants to exchange Y for Z Charlie wants to exchange Z for X

Alice (or Alice's VP agent) constructs a partial tx which consists of 1 or more Action circuits spending her asset X notes and creating the desired number of asset Y notes. The partial tx contains Alice's VP, which is given the input/output notes in Alice's partial tx, and approves of the exchange.

Bob constructs a partial tx spending Y notes and creating Z notes, with Bob's VP approving.

Charlie constructs a partial tx spending Z and creating X, with Charlie's VP approving.

Someone (for example, Bob, but it can be anyone with visibility into the asset types and values) can combine the partial tx into a full, balancing tx that can get posted.

Now consider the subscription model. Only one partial tx is required: Alice writes a VP that authorizes $10/month payment to Bob. Bob then creates a partial tx with one or more Action circuits spending Alice's notes, containing both Alice and Bob's VPs. Each VP is given all the details for all Action circuits in the partial tx.

The contents of a partial tx can be accumulated and blinded at the partial tx level, then accumulated further at the tx and at the block level. This should give a good tradeoff between giving the VPs all the tx information (which is potentially inefficient, if each VP must have large circuit size) vs limiting the tx information that a VP receives (which adds complexity in making sure that each VP is given enough information)

[joebebel]

So, I think we've reached a tradeoff-point in terms of subproject 4 (how is checking validity predicates integrated with the overall checking transaction validity)

The fundamental problem is that someone (conceptually, a verifier, either a transparent one or a ZK circuit verifier) needs to enforce that the transaction is allowed if and only if every field of the tx (e.g. Action circuit inputs) is also provided to the correct validity predicates.

The first option, which is simple, is to provide every field to all VPs in a transaction. This probably will work, but I have questions about efficiency, and also it limits who can write VP proofs, because it has to be someone with full visibility after the tx is constructed, which is somewhat less flexible in the Alice-Bob-Charlie bartering example above.

The second option is to split tx into "partial" tx as described above; tx that don't need to balance, but otherwise are valid tx on their own, and VPs are given all fields from their partial tx (but not other partial tx in the same transaction). This case handles what seems like the majority of use cases, but is also not 100% flexible, while remaining somewhat simple, and also more efficient than the first option.

The third option is to try to design a system where VPs are only given data for Actions that are relevant to them. For example, a tx creator can commit to this data in a structured way (e.g. the 4th Action circuit has input note x and output note y) and then opening this commitment in both the VP and the Action circuit. Then the transaction-level verifier somehow checks consistency (details to be decided). This adds complexity to the circuits (which may or may not be efficient) but hopefully allows maximum flexibility.

Potentially another way (perhaps simpler) to accomplish the third option might be to use separate value balances for each VP. At the cost of one PRF hash (which is Not Cheap) we could commit to the sending or receiving address in the value base (much like we commit to the asset type) in a way that only the correct VP could balance (although I'm not certain of the details)

I think it's quite possible to do the third option, I'm just concerned about the potential complexity of such a design (it's difficult to tell without layout of all the details)

[lopeetall]

I'd like to work toward drawing some diagrams and forming a common language around this topic so it is easier to visualize and communicate what is going on.

Can we clarify who the participants in a transaction are, their roles, and how they relate to one another? For instance, we talk about transaction builders, matchmakers, provers, verifiers, validators, counterparties, etc. Who's who and what's what?

Also, I'm confused by what we mean exactly when we talk about a "validity predicate". Is a VP a Plonk circuit? Is it WASM? What is it concretely?

[cwgoes]

Also, I'm confused by what we mean exactly when we talk about a "validity predicate". Is a VP a Plonk circuit? Is it WASM? What is it concretely?

Conceptually, a validity predicate is the logical predicate which determines whether a particular transaction (state transition) is valid or not from the perspective of an agent whose permission is required to execute the transaction (e.g. the owner of a particular asset). On the public ledger, validity predicates are written in WASM and associated with accounts. In the private bartering circuit, validity predicates will necessarily themselves be circuits, and they will be associated with accounts (terminology to be clarified).

[joebebel]

Recall the Orchard Action "record" looks like: (rt, cv^net, nf^old, rk, cm, pi) where (roughly) rt = the Merkle tree root, cv^net = the net value commitment, nf^old = the nullifier for the spent note, rk = the spend authorization signature, cm = the new outgoing note commitment, and pi = the PLONK proof of Action with this public input

We could change this record to: (rt, cv^in, cv^out, nf^old, rk, cm, vp^in, vp^out, vpcheck, pi), where:

• cv^net splits into cv^in and cv^out, because incoming and outgoing values will need to be treated separately;
• vp^in and vp^out are hiding commitments to the incoming and outgoing validity predicates (as represented by their unblinded PLONK circuit descriptions)
• vp^in also commits to "ivk" (incoming viewing key)
• vp^out also commits to "pk_d" and "g_d"
• vpcheck is a boolean flag (or a hiding commitment to a boolean flag) that indicates whether the nf/cm notes are a "VP notes"

The Action circuit should check the "ivk/pk_d" part of the vp^in/out commitments, against the incoming and outgoing note commitments.

The Action circuit, when vpcheck = 1 and given a VP note to "spend", should also check the VP circuit description in the incoming and outgoing note commitments, against the circuit description in vp^in and vp^out.

Collect all records which share a vp^in or vp^out input into a "partial transaction" (note that a record may belong to more than one partial transaction)

For each partial transaction, the shared validity predicate circuit is given a list (cv^in, vp^in) and (cv^out, vp^out) as public input, of all value and VP commitments in that partial transaction. The "VP" record is then ((cv^in, vp^in), (cv^out, vp^out), pi) where pi is the PLONK proof of the VP.

Then in principle a partial tx can be checked (if the VP circuit is known) by:

1. Checking all Action proofs with their public input records
2. Checking that at least one of them has vpcheck = 1 (if vpcheck are hiding commitments, this can be done by homomorphically adding all vpcheck and opening)
3. Checking the VP proof on its record

Now, when incorporating this into an accumulation scheme, the proofs are not checked directly but rather an accumulator circuit checks that the proofs are accumulated correctly. This is perfectly reasonable to accumulate both Action proofs and VP proofs together, and the accumulator can be given the VP circuit description as private input.

However, the one part that does not work here (yet) is that the accumulator circuit needs to check the private VP circuit description against the vp^in or vp^out commitment. This would work wonderfully - except that these commitments are over the "wrong" curve (and therefore not efficient to open). So there's still one missing bit - but I think this otherwise works?

[jan-ferdinand]

[jan-ferdinand]

A bunch of questions:

1. If in transaction tx, Carol is only receiving a (single) note but not spending anything, my current understanding is that her partial transaction consists of exactly one Action Description. How is Carol's vp^out tied to her account? I.e.,

   1. how does the PBC transaction ensure that vp^out actually belongs to Carol, and

   2. how does the PBC transaction ensure that vp^out is satisfied?

      Are these exactly the same problems we are facing with vp^in and the reason why Joe introduced the vpcheck flag, or are there differences?

2. How are the tokenVPs involved in a transaction checked?
3. Are cv^in and cv^out of an Action Description with vpcheck=1 ignored?

[joebebel]

Right, so if we're checking everything from "outside" the circuit, since vp^out and vp^in are public inputs, we can enforce that, for each vp^in or vp^out commitment (call it V in a vpcheck=0 Action description, there is exactly one vpcheck=1 Action description with vp^in = V.

This way, we know that the vp^in or vp^out value commitment is correct (assuming the vpcheck=1 Action circuit does its job and can verify that vp^in or vp^out belongs to Carol) so this handles 1.i.

Then for 1.ii., this is trickier - basically the process is "open the vp^in or vp^out commitment, and check Carol's VP proof against Carol's VP circuit description". But of course this reveals private values, so we want to do this (conceptually) inside another circuit (to avoid having to open vp^in or vp^out publicly). We can't actually check the VP proof inside this "another circuit", but we (hopefully) can use the already-planned accumulation scheme to do this.

Of course, it's not clear to me how to open the vp^in or vp^out commitment, either (an issue with the alternating cycles of curves)

for 2, to be honest I haven't considered tokenVP in this context at all, but we could probably just add a third vp value (e.g. vp^token) and have one more partial tx to handle this VP as well.

for 3, we can either enforce cv^in and cv^out to 0 when vpcheck=1, or we can use it for some other (crazy) purpose - maybe we could even shove vp^in and vp^out in there, somehow.

[joebebel]

OK, so here's the latest proposal: each Action description A consists of:

(rt, cv^in, cv^out, nf^old, cm, vp^in, vp^out, vp^token, vpcheck, C^enc, pi)

where rt is the note Merkle tree root, cv^in/cv^out are the incoming and outgoing value commitments, nf^old is the incoming note nullifier, cm is the outgoing note commitment, vp^in, vp^out, and vp^token are the sender/recipient/token's validity predicate commitments (a Pedersen commitment to an address addr and addr's VP circuit description), vpcheck a boolean flag indicating that the Action is checking the validity of vp^in and vp^out instead of spending value (side note: it may be better to have a different circuit instead of a flag; this depends on the details of Halo 2), and C^enc is the in-band secret distribution ciphertext.

The Action circuit, in addition to the usual checks, also checks that:

1. vp^in and the note of nf^old commit to the same address
2. vp^out and cm commit to the same address
3. vp^token commits to the same asset type of nf^old and cm
4. C^enc is a valid ciphertext and its contents are correct
5. If vpcheck=1, then vp^in also commits to the same VP circuit contained in the note of nf^old

A "partial transaction of an address addr and validity predicate commitment vp" is a set of Action descriptions where at least one of: vp^in, vp^out, or vp^token in each Action is equal to vp and vp commits to address addr. In addition, the partial tx includes a proof pi_vp of the validity predicate circuit committed in vp.

A transaction consists of the union of partial transactions, such that the sum of value commitments opens to 0 (or, more generally, to the transparent value change)

A transaction is valid if and only if the sum of value commitments is correct and each partial transaction is valid.

For simplicity, let us assume that a public verifier has knowledge of the opening of vp. Then the steps a public verifier must do to verify a partial tx, where all Actions share vp:

1. Check each Action description's proof pi.
2. Check that the Action description with vpcheck=1 has vp^in equal to the shared vp
3. Open the commitment vp and extract the circuit description
4. Check the proof pi_vp against the circuit description, with public input all the Action descriptions in the partial tx

These steps, together, verify the properties:

1. The validity predicate committed to in vp belongs to the address committed to in vp
2. Each Action related to an address (sender/recipient/token) is linked to the associated vp commitment
3. The circuit committed to in vp must be satisfied when given all Action descriptions

Now, the end goal is to take this public verifier and move all of its checks into a "verifier circuit", where now the opening of vp is a private input. Then checking the verifier circuit proof should verify all of the Action descriptions for that partial tx.

However, the unresolved issues:

1. Opening vp in both the Action circuit and "verifier" circuit is problematic, because the Action circuit is over the Vesta curve and the "verifier" circuit is over the Pallas curve. So it's not clear to me how to do this opening at all. However, we probably just need one clever idea to get around this.
2. This approach leans very heavily on the Halo 2 accumulation scheme, both for efficiency and also for security/integrity. While this should work "in theory" there are a lot of details omitted and problems might come up.

I think that once we have a suitable workaround for the commitment curve mismatch problem, we should do a proof of concept implementation and see if any other problems come up.

[jan-ferdinand]

3. vp^token commits to the same asset type of nf^old and cm

In the transparent ledger, Alice can trade USD 1 for EUR 1 with Bob using a transaction where Alice's Action Description spends USD 1 and creates EUR 1, while Bob's Action Description spends EUR 1 and creates USD 1. If the Action Circuit enforces that the asset type of nf^old and cm are equal, this seems no longer possible.

5. If vpcheck=1, then vp^in also commits to the same VP circuit contained in the note of nf^old

If Carol only receives but doesn't send any tokens, which nf^old is Carol's vp^in compared to in her partial's transaction Action Description for which vpcheck=1? Should the VP “contained” in vp^in be compared to the VP “contained” in cm in such a case?

2. Check that the Action description with vpcheck=1 has vp^in equal to the shared vp

How is the shared vp of a partial transaction defined if not by the property ‘is the vp^in of the one Action Description with vpcheck=1’?

[joebebel]

If the Action Circuit enforces that the asset type of nf^old and cm are equal, this seems no longer possible.

Ah right, and this is mildly annoying because this means there might need to be many token VP proofs floating around; for example, in the 3 party exchange where Alice exchanges X for Y, Bob Y for Z, and Charlie Z for X, if we want each to construct their exchange separately, then there could be up to 6 VP proofs in this tx (and just 3 Actions) if Alice proves one of X's VP and Charlie proves another X VP (while in theory only one X VP is necessary, this requires someone to have visibility into both Alice and Charlie's partial tx, which might not exist before they're matched.

If Carol only receives but doesn't send any tokens, which nf^old is Carol's vp^in compared to in her partial's transaction Action Description for which vpcheck=1? Should the VP “contained” in vp^in be compared to the VP “contained” in cm in such a case?

I didn't address this yet, but nf^old could be a "dummy note" in this case (vp^in must be a "dummy VP" then). I suppose this could be rather wasteful, however, doing a vpcheck circuit for no reason (other than obfuscation).

How is the shared vp of a partial transaction defined if not by the property ‘is the vp^in of the one Action Description with vpcheck=1’?

Right, I suppose this follows from the partitioning of a tx's Action descriptions into partial txs, which doesn't require verification again.

[joebebel]

OK, I think there's a few directions forward from here:

1. Begin to write down some example use cases (for example, transfers, simple exchanges, VPs, etc) and show how each use case is possible to accomplish in a transaction. This includes @lopeetall's suggestion of documenting the roles of all participants (transaction builders, market makers, etc)
2. Fork the Orchard documentation, remove anything that is irrelevant or unchanged, and begin documenting formally what our changes would look like.
3. Ignore the issues of VP privacy for now, and begin a proof of concept implementation of the entire PBC system. This probably takes two forms: a. Fork the orchard repo and make changes to the Action circuit and other related code (in Rust) b. Without a proposed Halo 2/accumulation scheme implementation in Rust, we can do a proof of concept in Python/Sage first, unless we find it is easier to do ourselves in Rust first.

Some of the more concrete tasks can also be split into their own issues for discussion and this issue can remain open for high level planning/open problem solving.

[joebebel]

Another lower-priority "meta" task that can be done (related to writing down use cases) is to analyze Zcash Sapling shielded transactions to figure out some rough real-world statistics on things (for example, average/90th percentile number of notes in a transaction). It's possible someone already has statistics like this.

The purpose of collecting this data is to make some informed guesses about how many inputs our VPs need to take. Since it seems like a VP needs to input lots of notes, it's worth knowing how many "lots" is; is it 10? 50? 200? Although this is "tuneable" later it would be nice to know since it affects the efficiency of things.

[joebebel]

I had a realization that this "opening the commitment over two different curves" problem would also happen in Zexe's recursive circuits, and sure enough, they describe essentially the same problem and how they solve it (obviously without reference to Halo 2, of course)

The problem and solution are under "Problem 5: sharing information between NP relations is costly" and "Solution 5: hash predicate verification keys and commit to local data" on page 40 of the Zexe paper.

The short answer (translated into our context) is to commit to the VP circuit description using a Pedersen commitment that opens in the Verifier circuit. This commitment cm_vp is not opened in the Action circuit, but instead cm_vp is committed again using Blake2s. This Blake2s commitment is efficiently (well, relatively efficiently) openable in both the Action and Verifier circuits.

The critical properties are that the "large" VP circuit description gets Pedersen hashed down to a relatively small commitment, so the Blake2s hash doesn't have to hash very much input. The Action circuit doesn't need to open the Pedersen commitment, so it doesn't matter how efficient it is. The Blake2s hash can be optimized with lookup gates, so it's not as expensive as it could be. Unfortunately Poseidon is not really a great option here, as the field mismatch problem also affects Poseidon-based commitments.

Some details remain to be figured out (e.g. I'm not sure if we need a "local storage" for each VP, how to handle that in commitments) but I think this mostly resolves the open problem

[vveiln]

Here is another bunch of questions:

1. If Alice and Bob exchange assets, then in her partial tx Alice:

   1. spends her note and outputs Bob’s new note OR
   2. spends her note and [partially] outputs her new note
      1. It looks like two completely unrelated actions, and if that is possible, what prevents Alice from just outputting notes for herself (and spending dummy notes, maybe)?
      2. If it is possible to partially output a note, how would the process of combining these parts into a single tx look like? At which point the proofs are created?
   3. both cases are possible

2. In vpcheck=1 descriptions the vptoken field is ignored?

3. Token's partial tx includes just one vpcheck=1 description that checks vptoken (no regular note action descriptions)?

[joebebel]

1. In this example, I think we want Alice to spend her old note (1 of asset A) and create a new note to herself (1 of asset B) and from Alice's view, this is all she sees - she doesn't need to know anything about Bob's side of the exchange. In the end, Alice's partial tx is unbalanced - it creates and destroys assets - so it cannot be included in a full tx unless the overall value commitment is 0 (meaning that the other partial tx's create and destroy those assets in exactly the opposite amounts) As long as Bob's partial tx spends the same amount as Alice creates, and Alice's partial tx spends the same amount that Bob creates, sum of homomorphic value commitments should balance.

(I should note that in the Zcash Shielded Assets proposal, each asset's value base (for the value commitment) is assigned at the tx level; this might make it tricky to build partial tx's first, that get combined into a tx later.

(I should also note that, to handle this use case, we would need vp^token_in and vp^token_out since the spent and created notes are different token types)

2. I guess so - at least I don't see any checks that are needed.

3. Well, I guess it depends on how we define "partial tx". I would argue that we should put all Action descriptions with that asset type into that asset's partial tx, because that token's VP needs to verify the contents of all those Actions.

[joebebel]

Let me revisit the state of the task list before the meeting tomorrow:

1. Making the Orchard circuit multi-asset

For compatibility reasons I think it's best to conform with Zcash Shielded Assets (zcash/zcash#830) as much as possible, but I am a bit concerned about the dependency structure in tx building (all assets in a tx must be known prior to generating any proofs in that tx) which I think is going to be undesirable. We might want to collab on this issue and try to figure out some solution.

2. How to write VPs that compile to Plonk

As part of the prototyping effort, we should have (at first) some really simple VPs: always-allow, always-deny, and verify-signature. Ideally, maybe we can have these for both Plonkup and Halo 2 proving systems so the implementation issues become clear.

3. Enforcing VP privacy

This might have to be deferred initially as we implement everything else and then we can address it if/when the Halo 2 accumulation scheme implementation is available. As time goes on, we should also implement our own prototype accumulation circuit to make sure that we understand it top-to-bottom.

4. Transaction level processing/out-of-circuit checks

Validity predicates will be checked by the double commit method (Pedersen commitment then Blake2s) as described above. In general, checking VPs will be the biggest circuit changes we have to introduce, so this is a nontrivial project.

5. Efficiency (shrinking large circuits and transactions)

To start, let's use the existing Orchard plan ("Bundle" all Halo 2 proofs within a transaction) as that will probably be acceptable for production use (blinding the validity predicates is a bigger issue than proof size, I think)

We should also see how large the circuits end up before prematurely optimizing. Despite all the complexity we are adding to the circuits, the biggest inefficiency is probably the 3-4 Blake2s hashes (3 VP commitment openings and 1 potential verifiable encryption) which may not be too bad.

6. Information leakage VS Transaction size (how much to rely on trusted 3rd parties to handle metadata)

We haven't discussed this more than superficially. This is an entirely separate project, which is also somewhat delicate, but I think it will have nothing to do with the circuits or txs and so neither project is blocking the other.

7. Verifiable symmetric encryption

Another very independent project. The output notes need to be encrypted with verifiable encryption, either Poseidon-based or a more traditional scheme (both should be analyzed). This shouldn't have anything to do with circuit or tx design.

8. VP discovery

We need to push this issue more forward: given Alice's (diversified?) payment address, how does Bob know Alice's validity predicate and/or "find Alice's VP note" to build a tx? We need to figure out the details and, since this design may affect how "VP Check" is done in the circuits, it does block the final design of the circuits.

I think I'll make issues in the pbc repo for some of these.

[joebebel]

Some more thoughts from the meeting today.

1. Making Orchard multi-asset: this is largely an "optimization" question because we can always use the original approach (hash the asset type in the circuit) and it will work.

On VP discovery: there is a fundamental issue which is making it challenging. VPs that authorize spending must be stateful - they have to have some state, otherwise the same spend could be authorized over and over. For example, in the subscription VP example, the VP might allow payment to Bob every 10000 blocks; the state keeps track of the next allowed payment (e.g. "allow next payment after block 10^6", which gets updated to "allow next payment after block 10^6 + 10000", and so on).

It's natural to store this state in a "note" - because the requirements for updating VP state are pretty much exactly the same as spending a note of value. The old state cannot be reused again, and the state update happens in a shielded way that's not publicly linkable to other state updates. Keeping track of this VP state very naturally overlaps with keeping track of the notes of value - whoever has viewing key authority can easily track both VP state and unspent notes.

On the contrary, VPs that authorize receiving tokens have an entirely different problem. The more stateful they are, the more difficult it is to send tokens to that address. Fundamentally, the sender needs to know the VP state, but usually does not, because the sender generally has no viewing key authority over the recipient address. A continuously updating VP is a moving target which is impossible for a sender to keep track.

I think the million dollar question is: how much statefulness do we need? Can or should we have asymmetry between sending and receiving? We have some flexibility with diversified payment addresses - the same private key can potentially have several different incoming addresses with different properties (allow-all, different VPs, etc). Of course, this adds a lot of complexity as well.

[clvv]

I'm writing down some notes here to help me organize my thoughts on PBC. My main goal is to separate out the core semantics and mathematical functionalities that PBC should achieve without reasoning about the implementation specifics.

Some preliminary definitions

• Set of all users: User. Diversified addresses are considered distinct addresses.
• Set of all tokens: Token. These are user-definable, each token could be fungible or not.
• Possible fungible values: V, which is a set of integers from 0 to some maximum value.

Private state kept track by the shielded pool

• We work in UTXO model, so that each user owns a sequence of notes, meaning the state of the ledger is st = Note*, where Note is the set of possible notes.
• In ZCash, Note = User × V, meaning each note simply encodes the owner and a fungible value.
• To support multi-asset, we expand notes to encode a token type, i.e. Note = Token × User × V, for some set Token. Each user now owns a sequence of notes, each of which specifies its token type, owner, and value. There are multiple ways to encode token. MASP uses PRF to derive a unique commitment base. ZCash might use fixed distinct bases. There are tradeoffs to which approach we take.
• We can add additional token type to support NFTs, i.e. Note = Token × Tag × User × V, meaning each user own a sequence of notes, each of which now additionally specifies its tag t ∈ Tag. The semantics here is that notes are only fungible if they specify the same tag. For some applications, it suffices to take T = V, but in general maybe applications need to encode more data inside an NFT.
• Now, the question is do we want notes to encode more arbitrary data similar to Zexe? It seems to me that the answer is no, since we are reasoning directly with values in application scenarios.
• Implementation consideration: the fungible values in set V are committed homomorphically, which enables aggregation (more on this below).

Transactions

• Working in the UTXO mode, a transaction is simply a sequence of note spending and creations, i.e. tx ∈ Note* × Note* where the first components are the spends and the second component are the "mints". (In implementation, spends are revealed via nullifiers, but to intuitively reason about transactions, spends refer to existing notes.)
• In ZCash, transactions are valid if some inflation rules are met, meaning transaction validity depends on (besides spending authorization) the net value change of the transaction. The most simple rule is balance(tx) defined as 1 if and only if 0 = ∑_{note ∈ tx} note.v and 0 otherwise.
• To support multi-asset: naively, the inflation rules would be applied to each token type. For applications, each token will have its own minting rule.
• In Anoma, a transaction tx is valid if associated VPs decides that it is valid, which bring our discussion to VPs.

Validity predicates (VPs)

• Let's define three types of VPs: token VP, user VP, and intent VP. This is just my interpretation, and it might be insufficient for the "userflows". Semantically, each VP independently evaluates the validity of a transactions, and the transaction is valid if and only if all VPs say that it is.
• Some consideration that applies to all types of VP: arbitrary arity and reference to overall user state is very hard to deal with. I think VPs should deal with the semantic of notes directly without taking input other implementation details unless otherwise necessary. For example, verification of signatures should be modeled/implemented "out of band".
• To deal with arbitrary arity, one optimization is to aggregate the fungible values. This definitely prevents certain applications, but it seems crucial and inherent to me if we want to make the system work in the UTXO-style. Specifically, a transaction tx ∈ Note* × Note* is aggregated by their fungible values using User, Token, and Tag as keys.
• Token VP: a token vp takes input some mapping tx_token_vp: Tag ⟶ V, representing the aggregated net change in value. It can make sure that no new tokens are minted unless some special minting condition is satisfied.
• User VP: a user vp takes input some mapping tx_user_vp: Token × Tag ⟶ V, that gives the net value change of the transaction for that user given a token and tag pair. To tie this into the userflow example, a user VP can decide to use different underlying authorization checks (simple signature, threshold, or delay). UserVP should also be "proved" purely by the user.
• Intent VP works similarly to a user VP in that it takes the same input tx_user_vp: Token × Tag ⟶ V. However, intent VPs are "ephemeral" in the applications and are discarded once a transaction is processed. In applications, these VPs can make sure that exchange rates and honored. Another crucial difference between intent and user VP is that intent VP should be "proved" by the matchmaker, once it has found all the counter orders for a complete transaction.
• With the above formulation. The ledger now needs to store two maps, User_VP_Map: User ⟶ UserVP and Token_VP_Map: Token ⟶ TokenVP. Intent VP should be supplied in partial transactions.
• Implementation considerations: it is relatively easy (for a matchmaker) to prove that for some given (commited) inputs, a given (committed) VP accepts. However, what is more involved is to prove that for a transaction tx, all involved VPs accepts and are given the appropriate inputs. This likely involve some significant re-engineering of the ZCash circuit.
• More specifically, the "circuit" needs to show, for a particular transaction tx, that (1) for each involved note in tx, correct VPs are retrieved from User_VP_Map and Token_VP_Map, (2) value commitments are aggregated correctly across all notes of tx, (3) the correct aggregated value commitments are used as (committed) inputs into the VPs (4) all involved VPs accept.
• Note that in this model VPs are stateless. The question is of course can this approach realize the useful user workflows as given in https://github.com/heliaxdev/spec/issues/13. This brings us to the next point.

Evaluations against user workflows

• Spends and n-party trades are relatively straight-forward. Each user intent is encoded in the intent VP.
• It seems to me that the only application inherently requiring "stateful VP" is the subscription application. But exactly as Christopher points out, maybe we could let Bob issue "subscription tokens" instead of Alice giving out "payable" accounts. The "subscription token" approach is a lot easier to reason about: Bob creates a (non-fungible) token, with tag specifying the expiration time (in epoch). Alice can purchase a token to gain subscription. (1) Alice intent VP verifies the correct spending on purchase (2) Token VP verifies correct payment amount and sets expiration time of token (encoded in tag). Now, to prove active membership, Alice simply needs to prove ownership of a token with special (public) properties.
• I think that (1) adding states to VPs adds significant amount of complexity (2) utility gained from stateful VP might not be significant enough to justify the complexity.

[cwgoes]

Now, the question is do we want notes to encode more arbitrary data similar to Zexe? It seems to me that the answer is no, since we are reasoning directly with values in application scenarios.

I think we do, since we want NFTs to be able to have arbitrary properties which can be reasoned about in the validity predicate. Each NFT can still have a unique tag, however.

I think that (1) adding states to VPs adds significant amount of complexity (2) utility gained from stateful VP might not be significant enough to justify the complexity.

This may be the case, if we can ensure that the important userflows work without stateful VPs then that's fine.

[joebebel]

OK, these are some good ideas. I had been picturing that intents could be expressed as "user VP" (e.g. a new address for each intent), but maybe it's better to split it out separately as an "intent VP". Here's what I think so far:

1. As long as some userflows require VP state, I don't think it's much additional effort to make that state fairly generic (determined by the VP). But I think it is a smart idea to separate out VP state from the VPs themselves. In particular, the difference between stateful and stateless VPs is probably not really important - we should have some mechanism for VP initiation/discovery/expiration, and we should have some other mechanism for managing state (e.g. "state notes" along with "value notes"). Of course, what is "state"? (versus data that's part of the VP)? It's information that is private, updateable, or ephemeral in some way.

2. In terms of user/token/intent VPs, we can probably have a generic framework for all of these as well. It might be difficult to treat token VPs exactly the same as user VPs, but a lot is going to overlap.

3. The intent VP, by itself without state, doesn't seem to need to be very ephemeral - in fact, we could write one that is generic over different assets/rates, and encode the terms of the intent in the state.

4. I'm not sure I understand the subscription token example, now - I think the point of that application is that the transfer happens indefinitely, automatically over time, without active interaction from Alice. So there still has to be a value transfer from Alice that gets authorized for Bob to issue a subscription token.

The remaining details sound good - I think we should use the MASP PRF model right now, and write the first spec around that. For NFTs (or really any other asset type with extra metadata), the tag does not need to be processed in-circuit and we don't have to define any special behavior in-circuit.