The Neophyte's Guide to Zero-Knowledge Proofs

27 August 2023

kevincharm.eth

0x77fb..e693

As eloquently chronicled by gubsheep in his EthCC ‘23 talk The Elixir of Life and the Language of Truth ¹, we live in a golden age in which we have discovered a hypothesised endgame state for a branch of magic — that is — how to speak The Language of Truth; a language wherein you can only utter words that you believe to be true in your heart of hearts and in your soul of souls. Sit down, grab a cup of mead, and let me tell you about the magical language of zero-knowledge proofs, and how you can wield this great power.

1) What

First off, we shouldn’t sugar-coat the fact that ZKPs are just straight-up black magic. Maybe one day I’ll try to explain the mathematics behind it all, but I certainly don’t grasp all the foundations of ZKPs. Indeed, the foundations span many different maths-heavy subjects — polynomials, modular arithmetic and elliptic curves, to name a few. Luckily, however, I don’t believe that it is necessary to understand all the magic underneath to be able to effectively utilise ZKPs.

Essentially, ZKPs enable you to create succinct proofs of computation on a set of inputs. And you can choose to hide some of those inputs if you so desire. With these succinct proofs, you can be sure that the truth has been spoken by simply running the proof through a verifier program, without actually having to run the computation yourself. It might be useful to draw some parallels to how we use cryptographic hash functions (e.g. SHA-256) to verify the integrity of arbitrarily large pieces of data using short 32-byte proofs, without having to exhaustively inspect all of the data.

What does succinct mean, you ask? In the context of ZKPs, succinctness describes how relatively short a proof is, even for very large computations.

ZKPs are produced by writing programs that are eventually encoded into a polynomial equation. The answers to the polynomial equation can be used to generate proofs. As of today, we can use tools such as circom+snarkjs and Noir to write these programs and generate onchain verifier contracts.

An important point to note is that ZKPs are not oracles. For example, you can’t just create a ZKP of some REST API response payload and be sure that it came from the source you expected. In this case, you’d need to integrate some sort of public-key cryptography attestation. Similarly, ZKPs don’t simply allow you to create proofs that some execution happened on another chain without integrating cryptographic verification of other parts of the system (i.e. consensus proofs, storage proofs). Basically, you still need to learn some other stuff to be able to write useful ZKP programs!

Synthesis

Now that we (kinda) know what ZKPs are, let’s talk about what new things we can build using them. One of the most exciting affordances of ZKPs is programmable cryptography.

We’ve long lamented about the nondeterministic & malleable nature of ECDSA signatures and how their misuse has led to countless exploits. It’s time to make our own deterministic and non-malleable public-key signature scheme — with a ZKP program of our own 😎

First, we’ll lay out the constraints of our scheme, in a way that can be easily written as a ZKP program:

• A prover should have a keypair: a secret key, and a public key
• A prover should be able to sign an arbitrary message using their secret key to produce a signature
• Anyone should be able to verify that a signature was signed over a specific message by a prover using only the prover’s public key

An important difference between our scheme compared to a more “native” public-key cryptography DSA scheme like ECDSA or EdDSA is that — while signatures in ECDSA/EdDSA also serve as the proof — a zero-knowledge proof is a necessary addition in our scheme to prove that the prover does indeed hold the corresponding secret key (i.e. the prover must deliver both the signature and an additional proof).

Anyway, continuing on with the exercise… If we define our scheme in more maths-y terms, we might do it like so:

• Let $\text{PK}$, $\text{Msg}$, $\text{Sig}$ be public inputs
• Let $\text{SK}$ (secret key) be a private input
• $\text{PK} \overset{!}{=} \operatorname{H}(\text{SK})$
• $\text{Sig} \overset{!}{=} \operatorname{H}(\text{SK}, \text{Msg})$
• Where:
  • $\text{PK}$ is a public key
  • $\text{Msg}$ is a message digest
  • $\text{Sig}$ is a signature
  • $\text{SK}$ is a secret key
  • $\operatorname{H}$ is a cryptographic hash function

So basically we’re saying that a prover knows some preimage $\text{SK}$ to $\text{PK}$. Normally we can’t prove that we know a preimage without revealing it, but we can with ZKPs! And indeed, you might have noticed that we defined $\text{SK}$ as a private input, which means that the verifier will only need the public inputs $\text{PK}$, $\text{Msg}$, $\text{Sig}$, accompanied with the zero-knowledge proof to be able to verify the validity of the signature.

Next up, we’re going to turn this design spec into an actual ZKP program using Noir. Make sure you have Noir tooling installed to keep following along. Now that we have well-defined constraints, let’s translate that into Noir (and we’ll use Poseidon as $\operatorname{H}$):

fn main(
    private_key: Field,
    public_key: pub Field,
    message_hash: pub Field
) -> pub Field {
    assert(public_key == poseidon::bn254::hash_1([private_key]));
    poseidon::bn254::hash_2([private_key, message_hash])
}

If you’d like to test it out, here’s a set of example inputs for your Prover.toml:

message_hash = "0x3f46cee85de01c829c15a96765a024b48687825bca602b2124485dad9612a4"
private_key = "0x01c8bdf6686d4c8ba09db5f15ffee3c470a5e0ff54d6fbac3a548f9a666977"
public_key = "0x15d76b9641dc1e52de6f9530a4161f077c348b1329efaeb0e052f13b5bf1ce49"

Running nargo execute should output the signature over message_hash. After doing so, we can generate a zero-knowledge proof using nargo prove, which we can pass (along with the signature, message_hash, and public_key) to the verifier.

Because we did all that using Noir, we can generate proofs in the browser, and we can even verify the generated proofs in smart contracts on Ethereum! 😳

Imagine dragons

What was the point of creating our own deterministic public-key signature scheme? The purpose was to illustrate how easily the average programmer would be able to design their own custom cryptographic schemes (yes, yes, I know — here be dragons and all that). For example, our custom public-key signature scheme could be the foundation of a new verifiable random function protocol, since it produces deterministic & non-malleable signatures!

This has been but a small taste of the brave new world enabled by ZKPs. What kind of magicks will you conjure?

References