Articles
Collections
Write Article
Create Collection
Import from medium
Loading...
Sign in
POSTED 09 May 2019 09:09

Building Identity-linked zkSNARKs with ZoKrates

zokrates
ethereum
blockchain
zksnarks
zero-knowledge-proofs
OWNER
0
0x5a05...a4b7

ZoKrates is a toolbox for zkSNARKs on Ethereum. It includes an easy-to-use domain specific language for developers to leverage the power of zero-knowledge proofs in their decentralized applications. With the latest release, we’re excited to announce that the BabyJubJub elliptic curve was added to the ZoKrates standard library , as well as various cryptographic primitives such as signature schemes! This is a major milestone as it finally enables running cryptography inside of ZoKrates programs.

Cryptography in a zkSNARK?

zkSNARKs are often described as enabling someone to prove that they know some secret without revealing it. However, zkSNARKs do not in themselves carry any notion of identity, so it would be more accurate to say that they only prove that someone knows some secret. For many applications, this is an issue: you would not want a minor to be allowed to buy alcohol just by presenting a proof of age generated by an adult! In this blogpost, we describe how this missing link between proofs and identities can be established using ZoKrates, as an example of why and how to run elliptic curve cryptography (ECC) inside a SNARK. First, we show how to use ECC from the standard library by proving knowledge of a private key. We then analyze two use cases that require linking identities with proofs.

Setting the Scene: Pre-Image Proofs with ZoKrates

Arithmetic Circuits, Rank-1 Constraints Systems (R1CS), and Quadratic Arithmetic Programs (QAPs): it can be confusing to get started with zkSNARKs. ZoKrates greatly simplifies this by providing an imperative programming language that is easy to use and reason about. Instead of designing circuits, you write programs with well-known concepts such as variables, functions or loops. Here is how you would prove that you know of the pre-image of a given public hash:

import "hashes/sha256/512bitPacked.code" as sha256
def main(private field[4] i) -> (field[2]):
    return sha256(i)
  • The main function is the entry point of the program. One can create a valid proof if and only if main ran without error.

  • The visibility tags of the parameters ( private and public) define which information will be revealed to the verifier and which remains hidden. The default visibility tag is public ; outputs are always public. In the example above, the verifier will only learn the main function’s return value.

  • The hash function used in this example is SHA256 applied to an array of four 128-bit words. It is available as part of the standard library.

  • The execution can efficiently be verified — for example on the Ethereum Blockchain — given only the public inputs and the outputs. To write your first zero-knowledge program and verify proofs on Ethereum, check out our tutorial !

Identity-linked Proofs of Knowledge

One of the most common uses of zero-knowledge proofs is proving knowledge of a secret to someone without revealing it. This could be proving that you submitted a bid to an auction without revealing its price, or that you voted in an election without anyone knowing who you voted for. Let’s call that a Proof of Knowledge. As an example, we will use the simple hash pre-image proof we just presented as a Proof of Knowledge. But don’t worry: everything we will discuss also applies to more advanced Proofs of Knowledge. The following figure shows how Alice uses ZoKrates to create a pre-image proof. When she inputs her secret pre-image labeled private , she can execute the program fully, which returns the hash and a proof.

Alice wants to prove knowledge of the pre-image to Bob. Hence, she sends both the hash and the proof she generated on her machine to him. Bob can easily verify the correctness of the proof and thus be convinced that Alice knows the secret. Right? Well, no. Consider the following case where Charlie knows the secret and Alice does not.

Charlie uses the secret to create a Proof of Knowledge. She then sends it to Alice, who forwards it to Bob. Note that Alice does not learn the pre-image and could hence not create the proof herself. Obviously, something is missing here: there is no link between the Proof of Knowledge and the identity who claims it. How about signing the proof? Alice could just as well sign the proof she got from Charlie, so that does not work. It’s now clear: proving knowledge and proving the creator’s identity must happen at the same time. Since the proof of pre-image happens in the zkSNARK, this means that we need the identity to also be proven in the zkSNARK!

Proof of Private Key Ownership

In the context of public key cryptography, the simplest way to prove one’s identity is using key derivation: this one-way process takes a private key as input and returns the associated public key. Using ECC functions from the ZoKrates standard library, we can run key derivation inside a zkSNARK, so that the prover can expose their public key and prove that they know the associated private key. This constitutes a Proof of Private Key Ownership.

import "ecc/edwardsAdd.code" as add
import "ecc/edwardsScalarMult.code" as multiply
import "utils/pack/unpack256.code" as unpack256

/// Verifies match of a given public/private keypair.
///
///    Checks if the following equation holds for the provided keypair:
///    pk = sk*G
///    where G is the chosen base point of the subgroup
///    and * denotes scalar multiplication in the subgroup
///
/// Arguments:
///    pk: Curve point. Public key.
///    sk: Field element. Private key.
///    context: Curve parameters (including generator G) used to create keypair.
///
/// Returns:
///     Return 1 for pk/sk being a valid keypair, 0 otherwise.
def main(field[2] pk, private field sk, field[10] context) -> (field):

    field[2] G = [context[4], context[5]]

    field[256] skBits = unpack256(sk)
    field[2] ptExp = multiply(skBits, G, context)

    field out =    if ptExp[0] == pk[0] && ptExp[1] == pk[1] then 1 else 0 fi

    return out

Putting the Pieces Together

Let’s recap:

  • we have one function which proves knowledge of a secret

  • we have another function which checks that a given public key was derived from a given private key We simply combine the two to complete our protocol:

import "ecc/babyjubjubParams.code" as context
import "ecc/proofOfOwnership.code" as proofOfOwnership
import "hashes/sha256/512bitPacked.code" as sha256packed
def hash(private field[4] secret) -> (field[2]):
    return sha256packed(secret)

def main(field[2] pkA, private field[4] secret, private field skA) -> (field[2]):
    // load BabyJubJub context
    context = context()
    // prove ownership of skA
    proofOfOwnership(pkA, skA, context) == 1
    // return hash
    return hash(secret)

Alice can now convince Bob that she knows the pre-image: Bob checks that the program returns the expected hash as well as Alice’s public key. If the proof is verified, then whoever created it:

  • knew Alice’s private key: it must be Alice!

  • knew the pre-image: she must know the secret!

Repudiable Identity-linked Proofs of Knowledge

Now that we’re able to link Alice’s identity to the Proof of Knowledge, Bob can be sure that Alice knows the secret pre-image. Interestingly, this is not only true for Bob, though. Consider the following case, where Bob forwards the message received from Alice to Dave.

From the forwarded message, Dave also learns that Alice knows the secret. Even though the secret itself is always only known to Alice, the proof can still be very sensitive: if Alice is proving to Bob that she holds more than 1000 bitcoins, that’s already a lot of information she would not want Dave to get, even if the exact amount is hidden.

Repudiation

While our solution elegantly links identity and proofs, there is an obvious shortcoming: Alice cannot plausibly deny creation of the proof. In cryptography, this is referred to as non-repudiation. How can Alice be protected from Bob leaking her proof to third parties like Dave? This is where the power of zero-knowledge proofs strikes again. We create a new program that guarantees either of the following things about the prover:

  • The prover knows the secret and the sender’s private key

  • The prover knows the receiver’s private key. Let’s see how this solves the issue.

  • Alice is able to create the proof because she knows her own private key as well as the secret (1.)

  • Bob is able to create valid proofs with only his private key (2.) We just added repudiation: No one (except Bob) can be convinced that Alice created a given proof, since it could trivially have been created by Bob. Technically, this can simply be done using a logical OR linking the original statement and a Proof of Private Key that succeeds for the receiver’s private key.

Let’s see how this idea can actually be implemented using ZoKrates.

import "ecc/babyjubjubParams.code" as context
import "ecc/proofOfOwnership.code" as proofOfOwnership
import "hashes/sha256/512bitPacked.code" as sha256packed

def proofOfKnowledge(private field[4] secret, field[2] hash) -> (field):
    // check that the computed hash matches the input
    hash == sha256packed(secret)
    return 1

def main(field[2] pkA, field[2] pkB, field[2] hash, private field skA, private field[4] secret, private field skB) -> (field):

    context = context()
    field AhasKnowledge = proofOfKnowledge(secret, hash)
    field AhasOwnership = proofOfOwnership(pkA, skA, context)
    field BhasOwnership = proofOfOwnership(pkB, skB, context)

    field isAwithKnowledge = if AhasKnowledge == 1 && AhasOwnership == 1 then 1 else 0 fi
    field out = if isAwithKnowledge == 1 || BhasOwnership == 1 then 1 else 0 fi

    return out

Conclusion

In this post, we showed how to prove identity in a zkSNARK with ZoKrates based on the cryptographic primitives available in the Standard Library. Then we derived Repudiable Identity-Linked Proofs of Knowledge as a mean to link proofs with identities. Looking at the ZoKrates implementation of these ideas showed how easy it is to leverage these primitives to guarantee correctness and privacy in decentralized applications. In academia, this basic principle has been described as Designated Verifier Proofs . We’d like to thank Jordi Baylina for sharing it with the community. Stay tuned for more guides on how to use ZoKrates to enhance your DApp’s privacy and scalability!

Special thanks go to Stefan Deml and Thibaut Schaeffer for their contributions to this article.

Diagrams by

Chloé Heinis

Outline
  • Cryptography in a zkSNARK?

  • Setting the Scene: Pre-Image Proofs with ZoKrates

  • Identity-linked Proofs of Knowledge

  • Repudiable Identity-linked Proofs of Knowledge

  • Conclusion