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

cwgoes · 2021-02-15T14:33:08Z

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

cwgoes · 2021-03-24T20:23:53Z

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 · 2021-04-28T14:45:04Z

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 · 2021-05-26T13:28:35Z

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 · 2021-05-26T13:32:48Z

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

ghost · 2021-05-27T06:43:00Z

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.

ghost · 2021-05-28T02:20:40Z

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 · 2021-05-28T10:26:32Z

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.

ghost · 2021-06-01T02:01:05Z

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:

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.

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.

ghost · 2021-06-01T02:06:20Z

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.

ghost · 2021-06-02T17:29:48Z

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 · 2021-06-07T06:46:10Z

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.

ghost · 2021-06-08T06:55:33Z

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)

ghost · 2021-06-08T07:19:42Z

OK, here is a (tentative) plan:

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
Implement VPSpend and VPOutput circuits for MASP that are like MASP, but are coupled with a blinded VP proof to authorize Spend or Output.
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 · 2021-06-09T11:11:45Z

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.

👍

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:

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

Implement VPSpend and VPOutput circuits for MASP that are like MASP, but are coupled with a blinded VP proof to authorize Spend or Output.

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 · 2021-06-09T13:53:06Z

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.

ghost · 2021-06-10T05:26:59Z

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

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)

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.

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:

Fully private accounts require spend authorization signature, as before
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 · 2021-06-10T21:15:19Z

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.

ghost · 2021-06-10T22:03:12Z

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 + 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.

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

ghost · 2021-06-10T22:21:25Z

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 · 2021-06-11T10:28:00Z

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.

ghost · 2021-06-12T07:19:21Z

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

ghost · 2021-08-12T10:19:20Z

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 · 2021-08-13T12:53:11Z

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?

ghost · 2021-08-14T01:00:40Z

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.

ghost · 2021-08-19T00:20:59Z

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).

ghost · 2021-08-19T08:44:19Z

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:

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.
For each blinded VP in a transaction, there is a CheckVP circuit that checks that the blinded VP matches an unspent VP note.
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.
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:

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.
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)
There are probably logic bugs in this scheme, plz find them

ghost · 2021-08-20T05:19:10Z

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:

Do we do this accumulation in every Action circuit? If not, where do we check the accumulation of VP?
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)

ghost · 2021-08-23T23:50:56Z

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:

A tx consists of some number of Action circuits, blinded VPs, and VP proofs
Action takes as additional input the correct private VP (and public commitment)
Blinded VPs take public input the ordered list of nullifiers/note commitments, and private input the openings that are relevant
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:

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.
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).

ghost · 2021-08-27T23:43:36Z

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

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 (zcash/zcash#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.

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.

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.

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".

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.

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.

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.

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!)

clvv · 2021-11-02T21:10:31Z

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 · 2021-11-03T12:03:45Z

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.

ghost · 2021-11-04T04:24:43Z

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:

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.
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.
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.
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.

clvv · 2021-11-04T22:18:24Z

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.

Sure. Intent VP could persist in the ledger and keep a state.

The main conceptual difference between user and intent VP is this: validity of an user VP is proved by the user (in the form of signature or what not), while the validity of the intent VP is proved by the matchmaker. For the example of asset swaps, Alice can construct an intent VP AtoBVP authorizing payment of 10 tokens of A to get back at least 5 tokens of B. This is a VP that take (among other things) two integer inputs to output a bit denoting validity. The exact input to this AtoBVP is not determined until the matchmaker finds a counter party.

The main benefit of considering intent VPs is to clearly abstract what is being constructed and proved at the client versus by the matchmaker, as well as the exact information leakage from the client to the matchmaker. Intent VP encodes information that is revealed to the matchmaker, which include trade information (trade sizes, NFT properties) but exclude identifying information about the user (Alice). In the finalized ledger transaction, a matchmaker must prove satisfaction of the intent VP (of course in zero-knowledge, hence hiding the trade details from external observers).

the point of that application is that the transfer happens indefinitely, automatically over time, without active interaction from Alice.

This model requires Bob to request payment every time period. The other method (NFT-based subscription) require Alice to pay for an subscription every time period. They are very different approaches realizing the same application. At this stage, we should probably keep the design space open. One advantage that the NFT-based subscription has is that it might remove the need for a stateful VP (that authorizes the payment).

the tag does not need to be processed in-circuit and we don't have to define any special behavior in-circuit.

Semantically, tag is any information that identify the NFT, which include properties such as expiration date or color. To enable property based trades, intent VP should take input the tag. More generally, I think tag can serve as a "record" as in Zexe, allowing us to realize the functionality of Zexe.

ghost · 2021-11-05T00:36:07Z

The main benefit of considering intent VPs is to clearly abstract what is being constructed and proved at the client versus by the matchmaker, as well as the exact information leakage from the client to the matchmaker. Intent VP encodes information that is revealed to the matchmaker, which include trade information (trade sizes, NFT properties) but exclude identifying information about the user (Alice). In the finalized ledger transaction, a matchmaker must prove satisfaction of the intent VP (of course in zero-knowledge, hence hiding the trade details from external observers).

OK, so my question right now is how much we should handle this in the protocol level (instead of programming all of this into VPs). I think some of the exact details (e.g. who/what/when/where certain information is revealed) can be entirely handled within VPs without specifically designing it into the base ledger or our circuits - which allows for more flexibility later.

Actually, I do have another question. We've been talking about intents (as defined in ZEXE) but, formally, intents themselves are merely tools for matchmaking and not part of the transaction building process itself (in particular, the VPs have nothing to do with this part). Rather, the VPs are only used in the tx building phase where parties who have agreed on terms finalize and commit to the final transaction.

So let's see how this might work in practice. One approach is: Alice gossips an intent to trade X for Y at rate R up to max M. Bob accepts this offer and signs a partial tx exchanging some amount of Y for X at rate R, and sends the partial tx to Alice. Alice completes her partial tx and the tx is posted on chain.

This finalizes the intent based trade, but it comes at a cost that Alice can drop offline at any time because maybe she just wanted to leak info about Bob, maybe the market shifted (Bob is giving a free option to Alice for some time period) or maybe Alice just wants to frustrate Bob's attempts to trade.

A more "order based" approach would be to make intents themselves binding as orders. Alice offers X for Y at rate R up to max M, and encodes in her VP state to accept that rate. Then Alice gives the VP data to a matchmaker or releases it publicly. Bob can complete the whole transaction himself (or give his partial tx to the matchmaker) and either Bob or the matchmaker proves Alice's VP.

One approach along these lines is for Alice to reveal (publicly or to MM) her collection of X notes along with her VP and its state. The VP says that anyone can "spend" Alice's X notes but if the value goes to anyone besides Alice, there has to be a correct amount of Y also sent to Alice. (Residual unexchanged X from spent X notes gets returned to Alice)
Then Bob or MM can spend them to make exchanges - but that collection of X notes will decrease over time as people make trades and unexchanged X in spent notes gets returned to Alice. If Alice gives viewing key authority to Bob/MM, then this residual value becomes available again, but this means they can see the values of any other trades that Alice is doing as well. It's not ideal.

A slightly better way is that Alice moves her X into many small, fixed value notes in a separate payments address. As Alice accumulates "loose change" in a different address, she occasionally manually moves it back to the source address. She can give incoming viewing keys to this address to Bob/marketmakers/etc and doesn't leak too much.

So, can we use a special intent VP protocol to simplify this? It feels more like a problem with viewing authority than anything else, actually.

This model requires Bob to request payment every time period. The other method (NFT-based subscription) require Alice to pay for an subscription every time period. They are very different approaches realizing the same application. At this stage, we should probably keep the design space open. One advantage that the NFT-based subscription has is that it might remove the need for a stateful VP (that authorizes the payment).

I see - they're basically mirror images. Either Alice submits payment and gets an automatically issued NFT, or Bob automatically deducts payment and issues an NFT in return. Both cases are quite compelling - although the application details might be slightly different. For example, issuing this NFT may or may not need to be stateful - if the subscription is for a physical object there might be a limit to how many can be issued at a time).

Semantically, tag is any information that identify the NFT, which include properties such as expiration date or color. To enable property based trades, intent VP should take input the tag. More generally, I think tag can serve as a "record" as in Zexe, allowing us to realize the functionality of Zexe.

Oh, I see. OK, so the Action circuit doesn't need to be aware of this at all (as long as NFTs with distinct tags are distinct assets) but the VP circuit most certainly does need to know these details.

ghost · 2021-11-05T02:05:33Z

Here's a tentative framework for how to proceed:

Make changes to the Action description and circuit to the new format:

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

which supports incoming/outgoing VPs and multiple asset types. For now, include a "dummy" check for C^enc pending verifiable encryption details.

Make a new circuit VPCheck that takes in a Merkle tree of current valid addresses and VP circuit descriptions:

(rt^vp, vp, pi)

which checks that vp is a commitment to both an address and a VP circuit description, and that this matches the address<->VP matching in the Merkle tree rt^vp

Define a standardized VP circuit input format, something like:

{ (sum cv^in, sum cv^out, vp)_i }

which basically gives a summary list of Action descriptions to the VP. Action descriptions with vp=vp^in are summed into sum cv^in, vp^out to sum cv^out (aggregating commitments).

I think this is reasonably straightforward to implement, and while it has some major deficiencies (most specifically, checking the VP proofs is not private, since that requires halo 2)

clvv · 2021-11-05T03:08:16Z

This finalizes the intent based trade, but it comes at a cost that Alice can drop offline at any time because maybe she just wanted to leak info about Bob, maybe the market shifted (Bob is giving a free option to Alice for some time period) or maybe Alice just wants to frustrate Bob's attempts to trade.

Right. It seems to me we are aiming for the "order book" approach and partial tx are actionable by MM or a counter party. The interactive approach can be realized utilizing the order book approach, the matching of Alice and Bob can be done externally (to PBC) in that case.

So, can we use a special intent VP protocol to simplify this? It feels more like a problem with viewing authority than anything else, actually.

I don't think we need to give MM viewing authority. Let us examine the trade intent VP more closely. Alice wants to spend an note (containing 10 token A) to obtain a new note containing at least 5 token B. What could happen is the following:

Alice reveals a nullifier nf spending her 10 tokens of A, say contained in noteA
Alice creates a partial note noteB, containing 1 token of B and value is committed to homomorphically
Alice needs to prove that she can use notaA using her spending key
Alice also use her spending key to sign / authorize an intent VP AtoBVP, which is a circuit taking the value commitment of noteA and noteB to return a boolean.
Alice submits a partial tx containing noteA, noteB, AtoBVP to a MM, along with secret information so that MM can open the value commitment for noteA and noteB

After the MM receives the partial tx from Alice and finds a counter order, it will do the following.

Compute exactly the B tokens that Alice should receive in the trade, and modify the value commitment of noteB accordingly. MM also needs to be able to modify the note commitment cm here without invalidating other values.
Prove that AtoBVP considers the trade valid. MM can do this since it knows the opening of the value commitment that are the input to the AtoBVP
Prove that all other VPs (namely for token A, token B, and Bob) are also valid (also using the fact that value commitment are revealed to it)

Make changes to the Action description and circuit to the new format:
(rt, cv^in, cv^out, nf^old, cm, vp^in, vp^out, vp^token, C^enc, pi)

Why is C^enc needed? Am I understanding it correctly that a verifiable note encryption is needed since the MM is creating the new note in this model? If yes, then I'm not sure if we need to have the MM create any note. We can design the system so that all notes are basically created by the users, the MM simply modify the homomorphic value commitments (which results in note cm changing) and prove satisfaction of VPs.

which checks that vp is a commitment to both an address and a VP circuit description, and that this matches the address<->VP matching in the Merkle tree rt^vp

It seems to me we would need something more than just a plain Merkle tree for storing the VPs. As you pointed out, we need to make sure there is exactly one VP for each address (and token) at each state. This sounds to be a "hash map" type structure to me. Such verifiable data structures have been studied (e.g. https://eprint.iacr.org/2020/1161).

ghost · 2021-11-05T05:15:59Z

1. Alice reveals a nullifier nf spending her 10 tokens of A, say contained in `noteA`
2. Alice creates a partial note `noteB`, containing 1 token of B and value is committed to homomorphically
3. Alice needs to prove that she can use `notaA` using her spending key
4. Alice also use her spending key to sign / authorize an intent VP `AtoBVP`, which is a circuit taking the value commitment of `noteA` and `noteB` to return a boolean.
5. Alice submits a partial tx containing `noteA, noteB, AtoBVP` to a MM, along with secret information so that MM can open the value commitment for `noteA` and `noteB`

Who constructs the Action proof (or similar) for noteA? Alice could create the proof, and link it to AtoBVP(committing in vp^in) so that it will only be usable if an AtoBVP proof is also attached. If MM creates it, then MM needs to open the note commitment to make the proof.

After the MM receives the partial tx from Alice and finds a counter order, it will do the following.
1. Compute exactly the B tokens that Alice should receive in the trade, and modify the value commitment of noteB accordingly. MM also needs to be able to modify the note commitment cm here without invalidating other values.

OK, this means the MM needs to make the Action proof for noteB because modifying the note commitment will invalidate the proof.

2. Prove that `AtoBVP` considers the trade valid. MM can do this since it knows the opening of the value commitment that are the input to the `AtoBVP`
3. Prove that all other VPs (namely for token A, token B, and Bob) are also valid (also using the fact that value commitment are revealed to it)

Alright, I think I like it :) Maybe a slight simplification, basically Alice and Bob prove the spend of their notes separately, and Alice signs an AtoBVP. In the case of all-or-nothing fill, Bob also creates his own output note at the same time. Then the MM creates a note returning any excess A to Alice, and proves the two VPs. MM learns nothing other than Alice's address.

A little bit more complex is the case of "partial fill". In principle this can be handled by Bob's BtoAVP, but there are some subtle issues about keeping track of how much has been filled (again...statefulness)

Make changes to the Action description and circuit to the new format:
(rt, cv^in, cv^out, nf^old, cm, vp^in, vp^out, vp^token, C^enc, pi)

Why is C^enc needed? Am I understanding it correctly that a verifiable note encryption is needed since the MM is creating the new note in this model? If yes, then I'm not sure if we need to have the MM create any note. We can design the system so that all notes are basically created by the users, the MM simply modify the homomorphic value commitments (which results in note cm changing) and prove satisfaction of VPs.

Verifiable encryption is mandatory any time a note is spent conditioned on creating the output note, because otherwise it's possible to censor or burn the output note (there might not be incentive to do so, but we shouldn't risk it).

In this case I don't think you can avoid it, because someone has to write the Action proof that outputs the note, and if it's Alice, then the MM cannot homomorphically change the value later (without invalidating the proof), so Alice would need to write the proof after the terms were agreed, but that is an additional round of interaction, etc.

It seems to me we would need something more than just a plain Merkle tree for storing the VPs. As you pointed out, we need to make sure there is exactly one VP for each address (and token) at each state. This sounds to be a "hash map" type structure to me. Such verifiable data structures have been studied (e.g. eprint.iacr.org/2020/1161).

I agree this would be great, but it's not clear to me how to do it. The specific construct in that paper seems to require group of unknown order which won't hold in the EC group

clvv · 2021-11-05T06:42:24Z

Verifiable encryption is mandatory any time a note is spent conditioned on creating the output note

because someone has to write the Action proof that outputs the note

MM cannot homomorphically change the value later (without invalidating the proof)

Right. I understand the approach here and the need to verifiable encryption. But I think we can get around this and never have the MM creating notes from scratch.

My thinking is that we should redesign the action circuit so that (1) users prove validity of "partial notes" and authorize intent vp, and (2) MM prove that they turn partial notes into valid full notes and that the intent vp is honored. More specifically,

Action circuit can (as a separate mode) produce a "partial note" instead of a full note.
Given a partial note and any integer, anyone can turn the partial note into a full note. The integer parameter is used to modify the (homomorphic) value commitment.
A partial tx contains partial notes as well as intent vps that take input integer values, which should correspond to parameters used to turn partial notes into full notes.
A MM combines partial tx into a full tx by (1) selecting parameters, (2) turning partial notes into full notes using selected parameters, and (3) proving associated vps are valid wrt to the selected parameters.

Of course, these are only very high-level intuition sketches at the moment. But I think this should be possible.

The specific construct in that paper seems to require group of unknown order which won't hold in the EC group

Right, we will probably need other constructions.

ghost · 2021-11-05T07:57:22Z

Hmm. I'm still a little unsure. The problem in my mind is that it's just super difficult to ensure that Alice actually knows the entire contents of the output note commitment. In the simple case, Alice might be able to infer, but in other cases she might not, for example if the output note is an NFT and the intent VP was property-based, then there might be way too many possibilities.

Also, if we don't use verifiable encryption, we can't ever have offline spends (like the subscription example) since those probably will always return at least some kind of NFT or subscription token or something.

Let's explore further if there's a circuit efficient key-value store. I was thinking that it's not really a problem if an address has multiple VPs, so Merkle tree is always a backup option, but maybe a stronger guarantee is helpful.

I have a bigger issue with the VP merkle tree being different than the note commitment tree. Since meta-analysis of VP updates is probably way easier to do than note tree updates since they're less frequent, there's more potential for information leakage.

clvv · 2021-11-05T18:21:49Z

for example if the output note is an NFT and the intent VP was property-based, then there might be way too many possibilities.

This can work similarly to the example above. NFT simply has one or more commitments that needs to be verified by the intent VP.

we can't ever have offline spends

This is true. But more in the sense that we can only have one spend per partial tx. In the example above, the partial tx can only be turned into a full tx and processed once. After that, the partial tx is useless, since the "funding" note is already spent.

To achieve subscription even if Alice is offline. The previous approach (as I understand it) is having Alice creating a new address with a user vp that authorize spends and giving MM viewing authority. This could still be compatible and built alongside the intent vp example above. All of the other user flows besides subscription currently consider fall into the intent vp example I believe.

it's not really a problem if an address has multiple VPs

But how do you ensure the latest VP for an address is being used?

Merkle tree is semantically a set commitment, with efficient opening proofs. The structure we need is a map from address to VP, again with efficient opening proofs. However, maybe there's a way to augment Merkle trees to provide the semantics of a hash map.

Since meta-analysis of VP updates is probably way easier to do than note tree updates since they're less frequent, there's more potential for information leakage.

Not sure what you mean by meta-analysis. Information leakage could be minimize if a tx always appear to (1) modify notes merkle tree and (2) modify some entries of the VP map. Of course some operations would be "dummy" for real txs.

ghost · 2021-11-06T01:15:28Z

https://eprint.iacr.org/2021/1263.pdf <- potential key-value store

This can work similarly to the example above. NFT simply has one or more commitments that needs to be verified by the intent VP.

Sorry, I still don't understand? Let's suppose that Alice is willing to trade $1 for one of any 2^128 different NFTs with some particular property. She won't know at the time of intent which specific token it is, so the partial note has to be generic. Let's assume the MM creates a full note from this partial note, what prevents the MM from not telling Alice which token it is or the opening of the note commitment?

To achieve subscription even if Alice is offline. The previous approach (as I understand it) is having Alice creating a new address with a user vp that authorize spends and giving MM viewing authority. This could still be compatible and built alongside the intent vp example above. All of the other user flows besides subscription currently consider fall into the intent vp example I believe.

I'm not sure this is really what we had in mind, because it's not truly offline, it's pre-prepared: Alice needs to construct some set of potential output notes in case her VP authorizes an output to her. In any case, it doesn't seem very straightforward.

But how do you ensure the latest VP for an address is being used?

There needs to be an authenticated method for addresses to add/update/delete VPs for themselves (I don't really know the best way to to do this yet), but I don't think we need to enforce 1 VP per account. The Merkle tree can just contain valid pairs (address, VP) and if an address creates two VPs for a single address, I think that's their problem.

Not sure what you mean by meta-analysis. Information leakage could be minimize if a tx always appear to (1) modify notes merkle tree and (2) modify some entries of the VP map. Of course some operations would be "dummy" for real txs.

Maybe I mean like a timing analysis or something. Because VP updates are likely to be much more rare than creating notes, it's easier to correlate a VP update with some real world activity.

clvv · 2021-11-06T06:29:24Z

what prevents the MM from not telling Alice which token it is or the opening of the note commitment?

You are right. For Alice to know the exact property, the commitment should be openable by Alice. So yes, naively the MM needs to verifiable encrypt the commitment randomness to Alice. Alternatively, maybe we could replace the commitment with e.g. ElGammal encryption (directly to the public key of the owner). Of course, the MM needs to again prove that it is done correctly. I agree, it seems some form of verifiable encryption is needed, but we can design it so that it is not of the full note but rather a small part of it (i.e. the part of the note that the MM changes).

In any case, it doesn't seem very straightforward.

Indeed. Perhaps the subscription use case should be taken care of separately.

if an address creates two VPs for a single address, I think that's their problem.

This might work.

Another thing I just realized: Merkle tree plus nullifier approach has the advantage of high parallelism. Multiple txs can be generated against the same root and be processed. Key-value maps might or might not support the same type of parallelism, which is a problem.

ghost · 2021-11-06T06:50:16Z

Yeah, it's worth thinking whether we need a full Poseidon-based symmetric key encryption, or if some kind of ElGamal is enough (since the amount of data is pretty small). I started to sketch some estimates in the VE issue but I didn't think about NFTs...so that would probably inflate the size of the encrypted note.

I think the biggest problem is not the verifiable encryption part (which is entirely feasible...we'd just have to implement it), it's that I don't think we want to dump the burden of proving output note validity on the MM. Since I think that would be the performance bottleneck if many tx are running through the same MM.

ghost · 2021-11-07T04:25:39Z

I'm trying to figure out how intent VP validity should get checked. Now, since the intent VP is probably not in the public commitment tree, Alice also needs to write some kind of "VPCheck" proof which will pass anyway. My initial thought was that it would work something along these lines:

Alice commits to the intent VP in vp^in, along with her address. She writes an Action proof spending some note with public input vp^in. The VPCheck private input can either be a Merkle path in the public VP tree OR a valid signature on vp^in.

The problem is that the RedPallas scheme is not particularly efficient in-circuit - it's designed to have re-randomizable keys so that the signature can be checked efficiently and privately outside the circuit. Except now, the existence of a signature check is public; so VPs from the public VP tree and signed VPs are easily distinguishable.

I'm not sure this is a major problem, but it's certainly a bit less elegant than I had hoped.

clvv · 2021-11-08T16:26:51Z

so VPs from the public VP tree and signed VPs are easily distinguishable.

I think intent VP would be a separate field of the transaction. User and token VPs are stored (in a merkle tree or other type of structure) and are referred to by notes. Intent VP are provided additional to each partial transaction.

I think there needs to be a circuit (additional to the modified action circuit) whose proof is generated by the MM to prove validity of the matched partial transaction.

There's also the question of whether we want to "blind" regular sends with more complex n-party transactions completed by MM. So perhaps simple sends now need to involve two proofs as well.

We are discussing PBC tomorrow at the retreat. Hopefully the overall structure becomes clearer then.

ghost · 2021-11-08T23:26:16Z

After thinking about it, it's only ~96 bytes to include a signature of the VP commitment for every single VPCheck description. In case the signature is valid, the VPCheck circuit checks the signature key rerandomization (in the same way that Action does right now); in case the VP commitment is stored in the public VP tree, the VPCheck circuit can check membership and ignore the randomized public key (the external signature attached can be a random dummy key)

This way at minimal cost, from outside the circuit, a signature is verified for each VPCheck and the situation looks identical. The MM needs to prove this VPCheck circuit, though.

The big detail remaining is how to prevent replay of this VP commitment signature in later transactions. VPCheck can easily manage state updates for us (either globally, by updating the public VP tree, or locally, by spending/outputting notes that contain VP state) but this is maybe more useful for VPs stored on-chain - it's not so clear to me how state is enforced for ephemeral VPs.

clvv · 2021-11-09T00:02:26Z

This way at minimal cost, from outside the circuit, a signature is verified for each VPCheck and the situation looks identical.

This looks to be a good approach if we want to "blind" the type of vp involved! However I'm not sure if we need to blind between user and intent vps. The main reason being that intent vp can be stateless (at least according to my consideration) and the "IntentVPCheck" circuits can be simpler than "UserOrTokenVPCheck" circuits.

This is the (intuitive) model I have in mind: user (and possible token) VPs are proved by the user, at partial tx preparation time, and intent VPs are proved by the MM at full tx preparation time. User and token vp are stateful, intent vps are not and only refer to value commitments within a tx (and hence can be ephemeral to each transaction). Intent vps are to ensure the fund security of the user when they are providing a partial tx. Intent vps are not present if the user is not engaging in multi-party bartering.

I believe this is expressive enough for most applications (besides subscription) and simpler to reason about.

ghost · 2021-11-09T00:38:12Z

Hmm, let's assume for now we are ok with splitting the privacy set between intent/barter tx and other tx.

I'm still not sure how to prevent an intent VP from being replayed later (for example, Alice gives the MM an intent to exchange X for Y at some rate, and then later gives the MM an intent to exchange X for Y at a different rate, what prevents the MM from using the old rate)

This is the (intuitive) model I have in mind: user (and possible token) VPs are proved by the user

I guess this depends on what we mean by "user". In general (except for when the user VP is a signature check) we should expect the user VP to be proven by someone else; otherwise, there's not really any need for programmability, since the user would just have signature authority (well, maybe some use case for cold storage of keys)

ghost · 2021-11-10T04:06:56Z

OK, just to give a quick summary of where I'm at with this.

We should distinguish between ephemeral and nonephemeral VPs and data. By nonephemeral, I mean VPs and data whose validity is determined by reference to already-verified public (or on-chain) data; for example, since the note commitment tree (and let's assume the VP commmitment tree) consists of commitments that are known to be valid, is it possible to check a VP or check some data/state by providing (as public input) the known-good Merkle tree root, and doing a lookup in a circuit.

By contrast, ephemeral VPs and data/state are ones whose validity cannot be determined directly because they are not long-lived (hence, ephemeral) and it is impractical to do an on-chain update for each one of these things. The most direct example of ephemeral data are intents: the bid/ask of an intent is too short lived to exist on-chain.

My first instinct was that ephemeral data is verified by signature. However, I think this is not the best idea (or at least incomplete) because:

We have to come up with some anti-replay scheme which prevents old intents from being reused far into the future
It's a significant limitation on the power of VPs, which would only be able to interface with the bartering system.
It doesn't match the transparent barter system. The semantic differences might be confusing to users.

I think the limitation is important enough not to ignore. Basically the only way to authorize an intent (either as a maker or taker) is by one-party signature, meaning any of the following cannot authorize intents directly:

Multi-sig or content based sig
DAOs/assets from joint funding of some good
Subscriptions (offline spend)

since all of the above are dependent on VPs to authorize a spend. Now, there are lots of details that we haven't figured out about how to implement all three of these things, which makes things difficult to reason about. For example, it's not clear at all how the intent should be constructed (at what rate? where does that data come from?).

I think there are two feasible paths forward from here:

Have two different formats for intents: signature authorized and VP authorized. VP authorized are much more limited since the output note must be fully determined at the time the user VP is proved, and the intent system is more complex because it has to handle two paths.
Design a proper system for authenticating ephemeral data such as intents (to be honest, the system for authenticating nonephemeral data needs refinement too)

I think we should make an attempt to do this the Right Way which means (2). Especially because I don't think it's going to be very difficult or complex to do - but it does need some engineering.

For example, suppose Alice, Bob, and Charlie have a hedge fund that invests in cryptokitties. The rules of the fund are that Alice, Bob, and Charlie each deposit some of asset X, which can only ever be used to buy and sell cryptokitties, and any 2-of-3 multisig can decide the properties and prices. We can set it up like:

The VP for the fund account allows deposits+withdraws of X from Alice/Bob/Charlie, and allows "issuing trade intent" (TBD) as long as the intent is X->cryptokitty or cryptokitty->X, and authorized by 2-of-3 multisig.
Alice and Bob decide blue cryptokitties are all worth at least 1 X, so they use the fund VP to authorize the spend of some X, but don't know what they will receive until the MM matches.
The MM matches, constructs the output note, and proves the intent VP showing that the intent was satisfied.

The fundamental issue is linking the intent approved by the fund VP with the intent VP. For example, in a sequence of on-chain transactions, Alice and Bob can trigger the fund can move some X into a temporary account whose (intent) VP is written to specifically authorize X->kitty swaps. The fund VP also updates the (intent) VP state with Alice and Bob's instructions (e.g. 1 X for every blue). Since every transfer or state update is checked as it happens, the MM only needs to prove the intent VP spending the funds in the temporary account, and it all works.

The most obvious idea is to allow state updates to be "fast forwarded" in some way. There is nothing special about a sequence of on-chain transactions - we just need to design the system so that we accomplish the same thing without establishing a temporary account with the intent VP and moving X into it. Instead, the fund VP creates some ephemeral VP+state encoding the intent, and the tx verifier checks that the fund VP authorized the ephemeral VP+state, and that the ephemeral VP+state approve the final tx.

ghost · 2021-11-10T07:14:51Z

Here's a concrete proposal for how this might work. Let's go back to a past concept we considered - sending notes to VPs instead of addresses.

Let a "VP address" be defined something like: addr = PRF(VP circuit description, VP data, diversifier). Note that this VP is "self verifying" with no VP commitment tree needed - a circuit just needs to compute the PRF and compare the address (e.g. from a note). If the PRF is efficient, we might not even need a separate VPCheck circuit.

VP addresses can be used to solve the intent problem because they allow ephemeral data to be exchanged between VPs in a tx. Continuing the hedge fund example from above:

The VPs would be fund_vp and intent_vp, which fund_addr and intent_addr derive from.

fund_vp says: Approve only partial tx that look like:

fund_addr spends any amount of X and outputs intent (cryptokitty, property, value) to intent_addr, AND 
2-of-3 have signed.

intent_vp says: Approve only partial tx that look like:

fund_addr spends Y amount of X and outputs intent (cryptokitty, property A, value, B) to intent_addr, AND 
intent_addr spends an intent (cryptokitty, A, B) outputs a cryptokitty with property A to fund_addr, AND
intent_addr spends an intent (cryptokitty, A, B) outputs a note of value (Y-1) of asset X to fund_addr

Alice and Bob can spend a note that looks like (fund_addr, asset X, value 10) by building an Action description:
fund_addr spends 10 amount of X and outputs intent (cryptokitty, any blue, <= 1 X) to intent_addr
(this output note only contains the trade intent, not the value 1 X)

Alice and/or Bob can write a proof of fund_vp for this partial tx since they can write the multisig and the Action meets the format required by fund_vp.

The MM finds a counterparty selling a blue for 1X. The intent can be executed by the MM creating more Actions:

intent_addr spends intent (cryptokitty, any blue, <=1X) outputs a blue cryptokitty to fund_addr,
intent_addr spends intent (cryptokitty, any blue, <=1X) outputs a note of value 9 of asset X to fund_addr,
intent_addr spends intent (cryptokitty, any blue, <=1X) outputs a note of value 1 of asset X to counterparty_addr

The MM can prove intent_vp because the four different Actions that reference intent_addr meet the template that intent_vp requires - if any details are missing or different, then intent_vp would not approve.

Now here is where the magic happens. The Action circuit should not check validity of intent notes at all - it's the VPs that check! So when an intent gets "spent" by intent_addr, we use some random nullifier and the Action statement approves. This is perfectly OK because intent_vp gets the intent from the Action where it's output, not where it's spent. The intent doesn't have to go into the note commitment tree at all for intent_vp to "receive" it from fund_vp

The best parts of this are:

No public management of VPs or VP data. In fact, maybe we should make all VPs ephemeral like this.
Should be relatively efficient. Maybe a cost of 1-2 PRFs per Action, and we use Poseidon or plookup Blake2s
We can handle ANY tx ephemeral data or VP in this way, even outside of the matchmaking system

(There are some details omitted/to be filled in...and also an interesting self-referential loop with fund_addr and intent_addr... but I think it's all workable)

ghost · 2021-11-13T03:27:00Z

OK, I think our current plan looks pretty good. I like the current intent and gossip fee proposals, and I think it handles all applications we've come up with.

(Though I'm still not convinced that we need to allow new notes to be spent in the same tx, because the exact same outcome can always be achieved by letting the value commitment balance, but we can discuss this more)

In terms of next steps:

If we're going to use the VP-PRF-address design, we should sketch it out more fully. The main issues in my mind are deriving the output note encryption keys, and solving this cyclic-address-dependency problem when VPs reference each others' addresses.
I think I underestimated how complex our VPs will be. So we should do proof of concept for all those, at least for sigs and multi-sigs and other essentials.
A proof of concept of the entire system (minus halo 2 accumulation), both to show that everything we've described so far is feasible, and to evaluate overall performance.
We should probably address the Elephant that is the halo 2 accumulator. I played around with Simon's code a bit and I didn't find the performance too objectionable. So maybe we should Just Try It and see how far we get.

ghost · 2021-12-04T07:47:28Z

Chain of VP integrity checks: @simonmasson

Let vp = ([q_M], [q_L], [q_R], [q_O], ...) be the polynomial commitments defining the VP (aka "VP circuit description" aka "Verifier preprocessed input")
It is assumed the correct VP is committed to in the note commitment cm stored in the public Merkle tree
- The note has an address field, and the address is (something like) CRH(CRH(vp), rcm)
The Action circuit takes public input nf^old (and/or cm^new), and checks:
- cm^old (and/or cm^new) opens to (address, value, asset_type, ...)
- address opens to CRH(CRH(vp), rcm_address)
- com_vp opens to PRF(CRH(vp), rcm_com_vp)
- CRH(VP polynomial commitments) is the same in both address and com_vp
The VPBlind circuit takes public inputs com_vp, blinded_vp checks:
- com_vp opens to PRF(CRH(vp), rcm_com_vp)
- for each polynomial commitment blinded_vp_i, vp_i in blinded_vp and vp
- blinded_vp_i = [(b_i1 X + b_i0) Z_H(X)] + vp_i for some random scalars b_i0, b_i1
VP circuit defined by vp should be satisfied by its public/private inputs iff the proof verifies against blinded_vp

Guarantees:

nf^old and/or cm^new contain address in their openings (Action circuit)
address and com_vp share the same vp inside (Action circuit)
Action and VPBlind share the same com_vp public input (publicly verifiable)
com_vp and blinded_vp are derived from the same vp (VPBlind circuit)
The VP proof verifies against blinded_vp (publicly verifiable)

The end conclusion (following the chain of cryptographic links) is that the VP proof is valid against blinded_vp if and only if it is valid for the vp committed in nf^old or cm^new

ghost · 2021-12-04T08:06:09Z

Also, it is notable that the prover probably must know the blinded VP because the polynomial commitment openings in the VP proof open against the blinded VP polynomial commitments, not the original VP polynomial commitments (even though the evaluations are the same), and also the last two verifier challenges u,v depend on the PC openings (and therefore depend on the blinded polynomial, not the original polynomials)

So I meant to say, the VP proof is valid against blinded_vp if and only if there exists a valid VP proof against vp committed to in nf^old or cm^new, since the VP proof will not verify against both simultaneously.

ghost · 2021-12-07T09:18:47Z

OK, here's a proposal for handling cyclic VP address references. At first, finding a "fixed point" of the address derivation function seems difficult, but taking some inspiration from Kleene's recursion theorem we can actually make some progress.

Suppose address =CRH(CRH(VP) || CRH(data) || rcm). The first step is to give the VP it's own address as private input (along with the openings CRH(VP), data, rcm). This must be checked (to make sure it's not some other VP's address), but that should be simple (check it against com_vp as public input, etc) and we have to verify the integrity of data anyway. We can't embed dependent addresses directly, but we can derive addresses within the circuit and check correctness. This directly gives a VP that can send to itself: compute self_address = CRH(CRH(VP) || CRH(data) || rcm).

Suppose we want two VPs which reference each other's addresses. The first VP will be address_1 = CRH(CRH(VP_1) || CRH(data_1) || rcm_1) and the second VP address_2 = CRH(CRH(VP_2) || CRH(data_2) || rcm_2). For now, we don't know data_1, data_2 yet. Let partial_data_1 and partial_data_2 denote other data we want in data_1, data_2 besides addresses.

Then VP_1 can derive address_2. Let data_1 = data_2 = CRH(VP_1) || partial_data_1 || rcm_1 || CRH(VP_2) || partial_data_2 || rcm_2

Extend the VP_1 circuit to read the values CRH(VP_2) || partial_data_2 || rcm_2 from data_1. Then VP_1 can compute address_2 = CRH(CRH(VP_2) || CRH(data_1) || rcm_2). Similarly, VP_2 can read CRH(VP_1) || partial_data_1 || rcm_1 from data_2 and reconstruct address_1 = CRH(CRH(VP_1) || CRH(data_2) || rcm_1).

Note that VP_1 and VP_2 circuits do not depend on each other, or on data, partial_data_1/2, address_1/2 (the circuits only depend on the format of data). Similarly, partial_data_1/2 does not depend on anything. data then depends on CRH(VP_1/2) and partial_data_1/2 only.

In particular, now address_1 only depends on CRH(VP_1), CRH(VP_2), partial_data_1, partial_data_2, rcm_1, rcm_2 and not on address_2. By fixing the circuits, partial_data, and rcm values, and simultaneously deriving the addresses from those, this "locks" the VPs to each others' addresses.

Suppose you want to have longer than a 2-cycle, like an n-cycle (address_1 can send to address_2, address_2 to address_3, address_n to address_1), or even arbitrary dependencies? Unfortunately its not the most efficient, but this is possible:

Let data = CRH(VP_1) || partial_data_1 || rcm_1 || ... || CRH(VP_n) || partial_data_n || rcm_n (same data for all VPs) . Then address_i can be derived in any of the circuits as CRH(CRH(VP_i), CRH(data), rcm_i).

Hopefully, complex interdependencies will be rare and the vast majority of dependencies only involve 2-3 addresses. Also, this is the kind of complexity that is ideal to abstract away from the VP writer as much as possible.

jan-ferdinand · 2021-12-07T10:42:08Z

The following statements are sanity checks on whether I understand your proposal:
The extension of VP_1 to read the right half of data_2, where H(VP_2) is living, needs to happen before data_2 is generated. In effect, the actual extended_VP_1 and thus its address depend on the number of VPs (respectively addresses) in the cycle as well as the index j¹ to read the missing address information from.

If the sanity checks have passed, I have the following questions:

Which entity fixes² the order of the fields in data?
Which entity performs the transformation of VP_i into extended_VP_i which reads the required data from index j?
1. If this entity is not the original creator of the VP,³ how can we prove that the only modification that happened to VP_i was adding the logic to read data[j]?

in the example, j=2 ↩
or which entities can globally consistent agree on a view to fix ↩
and I think it shouldn't, because that would require them to be online at all times ↩

cwgoes · 2023-01-17T16:48:29Z

Closing but archiving for posterity and entertainment.

cwgoes self-assigned this Feb 15, 2021

cwgoes transferred this issue from another repository Feb 3, 2022

cwgoes transferred this issue from another repository Dec 9, 2022

cwgoes closed this as completed Jan 17, 2023

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

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

Comments

cwgoes commented Feb 15, 2021

cwgoes commented Mar 24, 2021

cwgoes commented Apr 28, 2021 • edited Loading

cwgoes commented May 26, 2021

cwgoes commented May 26, 2021

ghost commented May 27, 2021

ghost commented May 28, 2021

cwgoes commented May 28, 2021

ghost commented Jun 1, 2021

ghost commented Jun 1, 2021

ghost commented Jun 2, 2021

cwgoes commented Jun 7, 2021

ghost commented Jun 8, 2021

ghost commented Jun 8, 2021

cwgoes commented Jun 9, 2021

simonmasson commented Jun 9, 2021

ghost commented Jun 10, 2021

lopeetall commented Jun 10, 2021

ghost commented Jun 10, 2021

ghost commented Jun 10, 2021

cwgoes commented Jun 11, 2021 • edited Loading

ghost commented Jun 12, 2021

ghost commented Aug 12, 2021

cwgoes commented Aug 13, 2021

ghost commented Aug 14, 2021

ghost commented Aug 19, 2021

ghost commented Aug 19, 2021

ghost commented Aug 20, 2021

ghost commented Aug 23, 2021

ghost commented Aug 27, 2021

clvv commented Nov 2, 2021

cwgoes commented Nov 3, 2021

ghost commented Nov 4, 2021

clvv commented Nov 4, 2021

ghost commented Nov 5, 2021

ghost commented Nov 5, 2021

clvv commented Nov 5, 2021

ghost commented Nov 5, 2021

clvv commented Nov 5, 2021

ghost commented Nov 5, 2021

clvv commented Nov 5, 2021

ghost commented Nov 6, 2021

clvv commented Nov 6, 2021

ghost commented Nov 6, 2021

ghost commented Nov 7, 2021 • edited by ghost Loading

clvv commented Nov 8, 2021

ghost commented Nov 8, 2021

clvv commented Nov 9, 2021 • edited Loading

ghost commented Nov 9, 2021 • edited by ghost Loading

ghost commented Nov 10, 2021

ghost commented Nov 10, 2021 • edited by ghost Loading

ghost commented Nov 13, 2021

ghost commented Dec 4, 2021

ghost commented Dec 4, 2021

ghost commented Dec 7, 2021 • edited by ghost Loading

jan-ferdinand commented Dec 7, 2021

Footnotes

cwgoes commented Jan 17, 2023

cwgoes commented Apr 28, 2021 •

edited

Loading

cwgoes commented Jun 11, 2021 •

edited

Loading

ghost commented Nov 7, 2021 •

edited by ghost

Loading

clvv commented Nov 9, 2021 •

edited

Loading

ghost commented Nov 9, 2021 •

edited by ghost

Loading

ghost commented Nov 10, 2021 •

edited by ghost

Loading

ghost commented Dec 7, 2021 •

edited by ghost

Loading