7 minute read

Nested proofs, one-layer proof composition, 2-chain curves, or 2-pairing zk-SNARK refer all to the concept of proving a zk-SNARK proof inside another zk-SNARK. In this blog, we will dive into the topic of such composable proofs and their advantages.

This tutorial assumes a good knowledge of zk-SNARKs and familiarity with Zokrates. If this is not the case, we recommend that you visit the ZoKrates basic tutorials first, e.g., [here] (https://zokrates.github.io/introduction.html), and work your way up. All the source code displayed on this page was compiled using ZoKrates 0.8.3 and is not guaranteed that it will work in future versions. All the material used in this tutorial can be found in our tutorials repository.

Advantages

There are several advantages to using nested proofs over simple proofs for blockchain-based verification.

  • Saving Transaction Costs: For example, imagine a prover, Pauline, who has many zk-SNARKs that need to be verified on the blockchain. However, each invocation of a smart contract incurs gas costs. Verifying all proofs could end up being very costly for Pauline. If Pauline could create a nested proof that verifies 5 other proofs before it is verified on-chain, Pauline would reduce her gas costs by 80%.

  • Execution on Constrained Machines: Furthermore, Pauline may only have access to constraint hardware that is not capable of executing a single large proof. With nested proofs, she can break down the larger proof into smaller and more manageable chunks and execute them consecutively on her machine. The generated proofs can then be aggregated into a single proof and verified on-chain as a single instance.

  • Parallel Execution: In another scenario, Pauline must execute many proofs in short time and has access to a horizontally scalable compute infrastructure. She can use nested proofs to execute the proofs in parallel on this infrastructure and then aggregate them in a single proof. Through concurrent execution and a high level of parallelization the overall execution time can be reduced significantly.

Remarks

For the sake of clarity, the nested proof will be referred to as the “inner” proof, we will use a Merkle proof validation as an example, whereas the “outer” proof is the proof that verifies the inner proof.

Due to their efficiency, we will use the BLS12_377 and BW6_761 curves to compile the inner and outer proofs respectively. Moreover, at the moment of writing, ZoKrates only supports proof composition for the BLS12_377 and BW6_761 curves. Although BLS12 curves can be nested on a specific BW6 curve, not all BLS12 curves can be efficiently composed (e.g. BLS12_381). Please note that the choice of these two curves is not arbitrary and should be taken into account when developing your own zk-SNARK logic. For example, a program compiled on BLS12_377 will not be able to verify signatures created by the BLS12_381 curve.

For verification on the blockchain, below are some of the blockchains which currently support the BW6_761 curve:

Generating a 2-Pairing zk-SNARK

First of all, we need to create a zk-SNARK proof with zokrates, whose correctness will be later verified by another zokrates program.

Generating the inner proof

For this tutorial, we have chosen a simple but representative inner proof: a Merkle proof for a Merkle tree of depth 3. All the files needed for the inner proof are stored in the merkle_proof directory. Below is the ZoKrates code to prove a Merkle tree of depth 3, which we will save in a file called merkle_proof.zok:

// example taken from zokrates documentation https://github.com/Zokrates/ZoKrates/blob/deploy/zokrates_cli/examples/merkleTree/sha256PathProof3.zok
import "hashes/sha256/512bitPadded" as hash;
import "hashes/utils/256bitsDirectionHelper" as multiplex;

// leave the root out of the struct as all the variables 
// in the struct are all private and the root is public
struct MerkleTreeProofStruct<DEPTH> {
  u32[8] leaf;
  bool[DEPTH] directionSelector; 
  u32[DEPTH][8] path;
}

// directionSelector => true if current digest is on the rhs of the hash
def select(bool condition, u32[8] left, u32[8] right) -> (u32[8], u32[8]) {
  return (condition ? right : left, condition ? left : right);
}

// Merkle-Tree inclusion proof for tree depth <DEPTH> using sha256
def merkleTreeProof<DEPTH>(u32[8] root, MerkleTreeProofStruct<DEPTH> proof) -> bool {
    // Start from the leaf
    u32[8] mut digest = proof.leaf;

  // Loop up the tree
  for u32 i in 0..DEPTH {
    (u32[8], u32[8]) s = select(proof.directionSelector[i], digest, proof.path[i]);
    digest = hash(s.0, s.1);
  }

    return digest == root;
}

const u32 TREE_DEPTH = 3;

def main(u32[8] treeRoot ,private MerkleTreeProofStruct<TREE_DEPTH> proof) {
    
    assert(merkleTreeProof(treeRoot, proof));
}

Next, compile merkle_proof.zok with the curve bls12_377 and run the setup which will generate the proving.key and verification.key. The proving.key is needed to generate a valid inner proof. The format of the proof and the verification.key will be needed later as input for the outer proof.

  $ zokrates compile -i merkle_proof.zok -o merkle_proof --curve bls12_377
  $ zokrates setup --proving-scheme gm17 --backend ark -i merkle_proof

Following the JSON structure specified in the abi.json file, create valid Merkle proof inputs and save it to a file merkle_proof_inputs.json. You can use the following sample for it:

[
    [
        "1159282642",
        "536390195",
        "167191670",
        "1416315119",
        "681460705",
        "991515991",
        "122440708",
        "1063238814"
    ],
    {
        "leaf": [
            "1561916891",
            "4211370407",
            "325730111",
            "2515823419",
            "499073870",
            "530421079",
            "1322832911",
            "2319503601"
        ],
        "directionSelector": [
            true,
            false,
            false
        ],
        "path": [
            [
                "2461223175",
                "3968173898",
                "3069881770",
                "533932862",
                "2260803868",
                "2411279626",
                "2347842517",
                "3404857129"
            ],
            [
                "1091838458",
                "1450848522",
                "3964138857",
                "1709311820",
                "1572859154",
                "2699827626",
                "2817560340",
                "2598221492"
            ],
            [
                "394873722",
                "2783260277",
                "3519802010",
                "2183791896",
                "1523256712",
                "803315438",
                "301579635",
                "216263908"
            ]
        ]
    }
]

with the above JSON file, we are ready to generate a valid witness, and subsequently a valid proof:

$ zokrates compute-witness --abi -i merkle_proof --stdin < merkle_proof_inputs.json
$ zokrates generate-proof --proving-scheme gm17 --backend ark -i merkle_proof

After successfully running all the previous commands you will find the resulting SNARK in proof.json file.

Generating the outer proof

Once we have a valid inner proof(merkle_proof/proof.json) and its verification key(merkle_proof/verification.key), we can use these two arguments to verify the validity of the inner proof in the outer proof. We leave the merkle_proof directory and store the code for the outer proof in nested_proof.zok which looks as follows:

from "snark/gm17" import main as verify, Proof, VerificationKey;

const u32 SIGNATURE_PROOF_INPUTS = 8;
const u32 SIGNATURE_VERIFICATION_KEY_SIZE = SIGNATURE_PROOF_INPUTS + 1;

def main(Proof<SIGNATURE_PROOF_INPUTS> signatureProof, VerificationKey<SIGNATURE_VERIFICATION_KEY_SIZE> signatureKey) {
    assert(verify(signatureProof, signatureKey));
}

The code imports the snark/gm17 module from the Zokrates standard library and verifies the inner proof given the verification key size (SIGNATURE_VERIFICATION_KEY_SIZE) and the number of inputs (SIGNATURE_PROOF_INPUTS). To create the outer proof, we first need to know the verification key and proof size for the inner proof. The verification key and input proofs are parsed as arguments to the outer proof.

We now proceed to compile the program with the curve bw6_761, followed by the setup step.

$ zokrates compile --curve bw6_761 -i nested_proof.zok
$ zokrates setup --proving-scheme gm17 --backend ark

Now we need to consolidate the inputs of the inner proof and the values of the inner proof’s verification key, which we have calculated in the previous step. For that, we need to parse the merkle_proof/proof.json and merkle_proof/verification,key in a way that matches the structure defined in nested_proof.zok. The structure of merkle_proof_inputs.json can be also found in abi.json. We have stored a sample witness in the file gm17.json, or you can use the following bash command (which requires you to have jq installed):

$ echo "[\n$(cat merkle_proof/proof.json | jq '{proof, inputs}'), $(cat merkle_proof/verification.key | jq 'del(.scheme,.curve)')\n]" > jq > gm17.json

The previous command should create the file gm17.json which content should look as follows:

[
{
  "proof": {
    "a": [
      "0x004aa820...",
      "0x00c5ba03..."
    ],
    "b": [
      [
        "0x009c65c2...",
        "0x0127ff85..."
      ],
      [
        "0x013cd26c...",
        "0x01ae0d1a..."
      ]
    ],
    "c": [
      "0x0075307a...",
      "0x0113e458..."
    ]
  },
  "inputs": [
    "0x00000000...",
    ...
  ]
}, {
  "h": [
    [
      "0x00014870...",
      "0x00f3e0e9..."
    ],
    [
      "0x00f01057...",
      "0x0107d52c..."
    ]
  ],
  "g_alpha": [
    "0x0118749d...",
    "0x00da30bf..."
  ],
  "h_beta": [
    [
      "0x0027e4c8...",
      "0x00e8190b..."
    ],
    [
      "0x013b82f6...",
      "0x00ce1a0f..."
    ]
  ],
  "g_gamma": [
    "0x01528db5...",
    "0x00ad9aec..."
  ],
  "h_gamma": [
    [
      "0x00014870...",
      "0x00f3e0e9..."
    ],
    [
      "0x00f01057...",
      "0x0107d52c..."
    ]
  ],
  "query": [
    [
      "0x01730e63...",
      "0x00f10ea6..."
    ],
    ...
  ]
}
]

At last, Compute a valid witness from the gm17.json file and generate the json proof. The proof generated from the outer proof can be found in the file proof.json.

$ zokrates compute-witness --abi --stdin < gm17.json
$ zokrates generate-proof --proving-scheme gm17 --backend ark

Conclusion

At this point, you should know how to create nested zk-SNARKs using ZoKrates. In this blog, we have used a simple example that only verifies a single inner proof. But this example can easily be extended to have multiple inner proofs being verified by the outer proof. If there is a dependency among inner proofs, it is possible to link them by defining a common public input and reusing this input in the different inner proofs.

At last, I want to highlight the benefits of nested proofs again: On the verification side, nested proofs can be used to reduce the cost of verification on the blockchain by reducing the number of proofs that need to be verified on the chain. You can aggregate multiple inner proofs in one outer proof and have the outer proof verified once. On the prover side, you can break down big proofs into smaller logical units. This can be beneficial if you have limited memory when calculating proofs. It can also lead to performance improvements if the inner proofs are calculated in parallel. Lastly, nested proofs enable new computation models. For example, distributing the computation of the zk-SNARK among multiple parties.

Leave a comment