6
$\begingroup$

It would be great if you can point out the mathematical formulation or R1CS form of the NP statement of Zcash.

$\endgroup$
2
$\begingroup$

I found your question intriguing enough to take a dive in the source code. Note that I have absolutely no experience with ZCash; I know a few ins and outs of Monero though, and I have done some tinkering with some very simple R1CS systems.

Since the ZCash "Sapling" update, it seems like the knowledge proof protocols are based on the bellman library. Their proofs are conveniently stored in the zcash-proofs directory of the ZCash Rust library. Their individual circuit "gadgets" are in the sapling-crypto/circuit directory, in which you'll find the Spend and Output circuits. These all build upon the other circuits in that directory, among which a SHA256 hash and a blake2s implementation, and ECC cryptography running in a circuit.

All the above should already give you some insight in what happens: the precise NP-statement and the complete R1CS system will be way too long to present in a simple Stack Exchange answer. I think, even presenting all the constraints on a high level would take us to far, but I think that an illustration of a few constraints may give you a lot of insight! For a high-level overview, I think the ZCash blog gives a good starting point. If you want to dive in depth, there's also the protocol specification; especially "4.15: Zk-SNARK statements" will interest you.


From the above blog, these are some high level constraints:

  1. the input values sum to the output values for each shielded transfer.
  2. the sender proves that they have the private spending keys of the input notes, giving them the authority to spend.
  3. The private spending keys of the input notes are cryptographically linked to a signature over the whole transaction, in such a way that the transaction cannot be modified by a party who did not know these private keys.

Let's explore 1, for example. Each transaction has a sequence of Spend descriptions and a sequence of Output descriptions. The latter is the simplest of both, so let's go with that.

The spec contains four constraints:

  1. Note commitment integrity: the commitment of the note is honestly and correctly generated.
  2. Value commitment integrity: the value commitment of a transaction is the commitment of a value.
  3. Small order check; the point $g_d$ should not be of small order -- implementation detail in the specific curve they use.
  4. Ephemeral public key integrity: the ephemeral public key of the transaction equals $[esk]\times g_d$.

I encourage you to look at the other statements yourself from here; especially the protocol spec is quite detailed in this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.