Function privacy in zkVMs

Cryptography Zoo
1

Context

ZEXE. Function privacy in ZEXE is achieved by producing inner proofs \pi_b,\pi_d to the satisfiability of the birth and death predicates \Phi_b,\Phi_b with a succinct pre-processing SNARK with prover and verifier keys (pk_{b},vk_{b}), (pk_{d},vk_{d}), respectively. An outer prover verifies the inner proofs \pi_b,\pi_d using the verifying keys vk_b,vk_d. Both, the proofs and the verifying keys are passed as witness to the outer prover, and the instances of the birth and death predicates are passed as instances. The outer proof system is zero-knowledge, hence the outer proof yields no information on what predicates have been verified.

This approach is expensive because the logic of the inner verifier must be arithmetized, resulting in large circuits.

VERIZEXE. Avoids running SNARK verification logic in zero-knowledge by instead using accumulation schemes. Thus, all the expensive logic of the inner verifier is postponed by pushing it into an accumulator. This already yields outer provers with lighter verification logic. The second point of improvement over ZEXE is to postpone the expensive logic of the accumulation scheme verifier to an outsider decider (i.e. the ledger)

Both approaches follow the same paradigm: verify in zero-knowledge the logic of some verifier, that attests to the validity of the inner (and private) predicates.

Function privacy in Cairo

The Cairo paper describes an alternative: loading programs for their hash, and running them.

Thus, the bootloader from Cairo paper, Section 2.2.1 would take the role of the ‘outer prover’ in the (veri)ZEXE approach. But, now there is no verification of ‘inner proofs’. The logic of the bootloader is:

  1. compute the hash of the predicate,
  2. write the bytecode of the predicate to memory, and set the program counter to that memory segment,
  3. run the predicate bytecode.

The output of the bootloader is the output of the predicate, as well as the hash of the predicate bytecode. To ensure function privacy:

  • the hash must be salted with a secret value,
  • and the AIR of the bootloader cannot leak any information about the executed predicate. At the very least, all predicates should give computational traces with the same length (e.g. by adding dummy instruction at the end)

Open questions

We could investigate further. Under what circumstances can we dispense the (veri)ZEXE approach and go with the Cairo approach.

More generally, under what circumstances we can move onto a zkVM approach. For example, what about using RISC Zero?

1 Like