Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Pay-to-verification-key payments #2425

Open
ebfull opened this issue Jun 5, 2017 · 16 comments
Open

Pay-to-verification-key payments #2425

ebfull opened this issue Jun 5, 2017 · 16 comments
Labels
C-research Category: Engineering notes in support of design choices M-requires-nu A network upgrade is required to implement this. not in Sapling S-blocking-programmability Status: Blocks on programmability R&D S-blocking-scalability Status: Blocks on scalability R&D

Comments

@ebfull
Copy link
Contributor

ebfull commented Jun 5, 2017

The idea of "paying to a verification key" was floated around in discussions a year ago surrounding #608 but never really written up. Ian recently revived it.

Essentially, add an additional field to the note commitment which commits to a zk-SNARK verification key. Inside of the zk-SNARK we will need to "randomize" them with a secret r and reveal the randomized key through a public input to the circuit. The outside consensus rules can verify this zk-SNARK, given additional contextual inputs like the block height and other things that may be useful to scripts.

I believe this allows us to support, in one fell swoop, private multisig, private HTLC, BOLT, and other exotic payment schedules and protocols that we've discussed before. It also comes at significantly less up-front engineering effort; we can have a Sapling hardfork in the pipeline while we're designing a multisig interface.

I think this is much preferable to hardcoding in specific workflows for particular protocols, which additionally complicates security proof and analysis.

@ebfull ebfull added the NU1-sapling Network upgrade: Sapling-specific tasks label Jun 5, 2017
@nathan-at-least
Copy link
Contributor

This is good stuff!

Clarification

Can you explain this more:

Inside of the zk-SNARK we will need to "randomize" them with a secret r and reveal the randomized key through a public input to the circuit.

What is 'them'?

Use Cases

What I'd like to do is sketch out designs for implementing these cases on top of this proposal so that we're sure we're capturing the requirements for these use cases:

  • pay to spend authority - currently inherent in the JS circuit; can we reify it as one of these programmatic predicates, then remove the spend-authority requirement from our 'base transaction circuit'? The reason I suggest this is that there may be potential smart contracty things that don't have any particular spend authority, but unless we do this, the spender must always control a spend authority.
  • pay to spend authority only if blockheight is greater than parameter H chosen by the note committer.
  • pay to any K of N spend authorities.
  • XCAT (pay to spend authority A if hash preimage P is given OR pay to spend authority B if block height is > H, both P and H chosen by note committer).
  • BOLT and/or Lightning channel establishment/close integrations.
  • Integration with a to-be-disclosed research project I'll call sparpink for now.

Parameterization:

If we use those cases as strictly defining of the requirements, then we may nail down a specific set of predicate inputs to meet those cases. Some of these inputs are within the note commitment (eg hash image requirement), and some are public consensus values (eg block height).

OTOH, that may preclude some smart contracts we're not thinking of. So now I'm wondering what if the note commitment contains both the predicate's verification key commitment, and then it also contains an arbitrary 'predicate parameter input' that might be a large arbitrary bitfield. We then see if we can sensibly pack the committed inputs for different cases there. For example, for an XCAT-like predicate there's (addr_a, hash_image, addr_b, blockheight) for the two cases (two destinations, one requiring a hash preimage, the other a block height). Meanwhile for 2-of-4 multisig, maybe there is 4 pubkeys and a '2' encoding.

Along the same lines, we may with to provide a lot of public consensus parameters to enable a broader range of smart contracts: block height, arbitrary coinbase data, difficulty level, coin supply, shielded coin supply.

Privacy

In terms of privacy, this would add a distinguisher of at least the verification key. Can we nail this down so that only the verification key is the only distinguisher? Furthermore, this is only disclosed on spending the input, so the privacy is similar to MAST (https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki) in that on a spend the predicate is revealed. (The obvious difference here is that the details of the predicate are not disclosed in our scheme.)

Transitive Predicates

There may be some new valuable applications that rely on transitive predicates where P places some constraint or requirement on outputs. This is probably a qualitative step up in complexity, but it might be worth looking into for feasibility.

@ebfull
Copy link
Contributor Author

ebfull commented Jun 8, 2017

Can you explain this more:

Inside of the zk-SNARK we will need to "randomize" them with a secret r and reveal the randomized key through a public input to the circuit.

What is 'them'?

Them is the verification keys.

I originally thought that it would be feasible to randomize them in the circuit, but after some calculations it seems far too inefficient. As such, your statement...

In terms of privacy, this would add a distinguisher of at least the verification key. Can we nail this down so that only the verification key is the only distinguisher?

... is correct. The verification key will be distinguishable. I am pretty sure everything else can be kept indistinguishable though, yes.

@ebfull
Copy link
Contributor Author

ebfull commented Jun 8, 2017

I've been working a little harder to figure out how to achieve full indistinguishability of the verification keys, which would be nice if it were possible.

As in #2247, we rely on a modified form of Jens Groth's 2016 protocol that extends the CRS such that all possible circuits (of reasonable size) may rely on fixed alpha/beta. This extension seems intuitively correct, and I've gotten good feedback from Groth/@arielgabizon about it. Hopefully it can be proven soon.

I take an additional step now to evaluate gamma for all circuits with one public input (a hash, which can represent the context to the zk-SNARK) that is subsequently made available to be copied by the internal circuit. This is clearly correct and requires no formal proof. (It's also possible that gamma could be eliminated entirely from the CRS, which I've also asked @arielgabizon to look at proving as well.) At any rate, gamma becomes fixed and thus requires no randomization.

Now, only delta in G2 must be randomized. Groth's construction is proven correct if delta is available in both G1 and G2. Inside the circuit, it is a matter of randomizing delta in G1, and using a pairing outside the circuit to make the randomized delta correctly available to the zk-SNARK verification later.

The question now is: can we efficiently randomize g_1 * delta within the circuit?

@ebfull
Copy link
Contributor Author

ebfull commented Jun 12, 2017

I estimate that G1 affine point additions can be performed about as efficiently as SHA256 hashes are, which isn't too bad, but leads me to believe we will need to split the "randomization" off into another circuit so that users that aren't using pay-to-verification-key don't have to pay for it.

I believe we can allow for 128-bit scalar multiplications of delta in the circuit through the use of precomputed window tables queried with merkle tree lookups. 16-bit window tables would require around 155 CRH's and 7 G1 point additions, which puts it at around 100 - 300k constraints depending on the CRH used.

@nathan-at-least
Copy link
Contributor

IIUC that we need a common format for public and private parameters to the predicate circuits. Those public parameters are at risk of compromising distinguishability if directly exposed in a transaction.

Brainstorms of kinds of predicate inputs:

a. secrets committed to within a note. Examples: blockheight lock, multisig pubkeys.
b. inputs provided by the prover which must be verified by consensus rules. Examples: blockheight attestation (*)
c. inputs provided by the prover which should remain secret. Examples: predicate has a conditional branch unlocked by producing a preimage, but the application requires the pre-image to be private from the blockchain.
d. inputs provided by the prover which are unconstrained by consensus rules, but which should be globally visible for a given application. Examples: XCAT preimages.

(*) A block height attestation is an integer, k, selected by the prover who claims that the block height, H is at least that or greater. A miner sees k and requires, as a consensus rule, that k ≤ H when validating transactions. This can probably be generalized to any "consensus-enforced attestation" category of predicate inputs.

Imagine one or more predicates rely on block height attestations. For indistinguishability, every transaction must either include a block height attestation, even if most transactions are not predicated on block height. The same is true of every general "consensus-enforced attestation".

This seems to limit some of the expressiveness of these predicates: either we must anticipate all of them in advance, or we must sacrifice indistinguishability for this kind of input.

@ebfull
Copy link
Contributor Author

ebfull commented Jul 3, 2017

This seems to limit some of the expressiveness of these predicates: either we must anticipate all of them in advance, or we must sacrifice indistinguishability for this kind of input.

One solution is to have, as part of this interface, a merkle tree (or other layered commitment) of information that we anticipate these scripts will need. If we want to change the consensus rules and supply even more information, we can do so without changing the interface or affecting the scripts.

@nathan-at-least
Copy link
Contributor

nathan-at-least commented Jul 3, 2017

More thoughts on category b - "generalized consensus-enforced attestation inputs":

We should scour all of the "blockchain query" style opcodes from Ethereum and see which are applicable to Zcash blockchain as one way to anticipate which of these would be useful. A quick stab based on this list:

0x42    TIMESTAMP   Get the block's timestamp
0x43    NUMBER      Get the block's number
0x44    DIFFICULTY  Get the block's difficulty

There are some other Ethereum queries that could be adapted for Zcash, but that feels too radical to me, atm. For examples:

0x41    COINBASE    Get the block's beneficiary address

We could expose the coinbase recipients and/or fee amount? (Not clear to me which helpful use cases this enables.)

Thinking along the same lines of expanding the potential use cases by exposing more and more consensus inputs:

  • block header versions or other compatibility flags.
  • generic block header scoped commitments (?)

Anyway this all feels very speculative except for the first batch (block height, timestamp, difficulty).

@ebfull
Copy link
Contributor Author

ebfull commented Jul 4, 2017

Remember that the inputs to the proof are fixed at the time the proof is created. This means it is not possible to pass in things like the current block height or hash. You can pass in a "minimum" block height or something like that, and the outside consensus rules can guarantee it's sensible. I think you can pass in some normalized version of the transaction itself so that you can do covenants and other such things.

@nathan-at-least
Copy link
Contributor

Hey, I noticed something here that's incongruous with how I think of Bitcoin and I'm curious why there is a difference:

IIUC, this feature proposal places a predicate that's scoped to an address, whereas Bitcoin scriptPubkey is a predicate that is scoped to a specific UTXO. To me the latter seems more flexible, and I haven't wrapped my head around address-scoped predicates.

Oh, I guess multisig Bitcoin addresses are an example of address-scoped predicates?

@daira
Copy link
Contributor

daira commented Aug 8, 2017

It's possible to make pay-to-verification addresses indistinguishable from vanilla shielded addresses to the payer. (Recall that it's only when funds are spent from a pay-to-verification address that the verification key comes into play.) Consider the scheme in #2277 (comment) , which has:

  • ak = sk . G
  • vk = PRFvkak()
  • pkd = vk . GH(d)
  • an address is (d, pkd)

Change vk to be PRFvkak(verification_key). This allows the circuit [*] to check that verification_key, given as a private input, matches the randomized verification key that is made public in the spend description. The signature proving knowledge of ρ.sk and the address diversification work exactly as they do for vanilla shielded addresses.

[*] I'm assuming that pay-to-verification spends will have a second circuit that is like the main Sapling spending circuit but also has the randomization check. Something like that seems to be necessary to guarantee that balance is preserved, without encumbering the main circuit with the expense of randomization.

@daira
Copy link
Contributor

daira commented Sep 16, 2017

[Deleted incorrect comment.]

@tromer
Copy link
Contributor

tromer commented Oct 22, 2017

Is P2VK necessary for shielded XCAT in Sapling (using just z-addresses and hiding the ZEC amount)?
(cf. ZcashFoundation/GrantProposals-2017Q4#29 (comment))

@jackgavigan
Copy link
Contributor

Zexe: Enabling Decentralized Private Computation

@mms710
Copy link

mms710 commented Dec 13, 2018

This needs a lot of product validation to see if this should be implemented and if so, how.

@mms710 mms710 added the C-research Category: Engineering notes in support of design choices label Dec 13, 2018
@ebfull
Copy link
Contributor Author

ebfull commented Feb 12, 2019

One of the features of the Sonic proving system is that the circuit-specific verification key is publicly derivable. I haven't explored this entirely, but it is also possible to perfectly blind the result so that circuits are indistinguishable from each other. This would allow us to achieve p2vk payments without downstream users needing to perform their own trusted setups.

In fact, exploring this feature is partly responsible for how we managed to turn Sonic into a SNARK.

@zookozcash
Copy link

I think we shouldn't do this in NU3 for the following reasons:

  1. I think that "non-programmable" is a feature that makes Zcash more attractive to a lot of users. (Or to be more precise, "less programmable"). Unlike Ethereum and the numerous wannabe Ethereum-killers, Zcash is Just Money! Let's not trade-off this valuable feature until such a time as it brings clear wins to do so.

  2. Implementing more extensibility/programmability now could impose backward-compatibility constraints that slow or prevent other improvements in the future. For example, “Scalable Zcash” — limiting the kinds of transactions we have to support, and what state they are allowed to read and write, may be necessary to succeed at Scalable Zcash. If we implemented more extensibility now, and then later we wanted to implement scalability, this tension might force us to (a) forego scalability, (b) break backward-compatibility and remove support for programmability, or (c) chain-fork and have one chain with programmability and the other with scalability (https://z.cash/blog/future-friendly-fork/). (Note that if we — the Zcash community — were to try for (b) we'd probably get (c).)

  3. What are the use cases? We've finally seen some smart contracts on Ethereum that seem like they are getting real traction, aside from ICOs: Uniswap, Maker Dai, maybe CryptoKittes. Would any of these benefit from added privacy/data-security? Are there other smart contracts that people would want to use that are prevented by Ethereum's mandatory complete disclosure?

  4. I think that in a couple years we'll know a lot more about how to implement programmability thanks to work like Agoric, Starks, Sonic and a whole host of wannabe Ethereum killer projects out there. I think it is too early to commit to a specific technology like P2VK or ZEXE.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-research Category: Engineering notes in support of design choices M-requires-nu A network upgrade is required to implement this. not in Sapling S-blocking-programmability Status: Blocks on programmability R&D S-blocking-scalability Status: Blocks on scalability R&D
Projects
Protocol Team
  
Programmability
Development

No branches or pull requests

8 participants