Black-box non-black-box zero-knowledge via extendable Merkle tree

Abstract: Can we have a black-box protocol with a non-black-box proof?

We know black-box protocols for many fundamental tasks (zero-knowledge, MPC, etc.) which can be proven by black-box proofs (i.e., the simulator uses the adversary as a black-box). However, there are as many fundamental tasks (const. round concurrent ZK, concurrent MPC, sim-res ZK, etc.) that only admit non-black-box proofs, i.e. the simulator needs to use the code of the adversary. For the majority of such tasks we only know implementation based on the celebrated Barak's technique for non-black-box simulation. Implementing Barak's technique require that even cryptographic primitives (specifically, the hash function) are used in a non-black-box manner.

Is this inherent? Can we implement Barak's technique with a black-box protocol?

The crux of the difficulty is to hide the size of the witness (which cannot be a-priori bounded by any polynomial) without using the code of the hash function. In other words, how to build succinct proofs that are also black-box.

In this work we introduce a novel way of building a Merkle tree -- that we call extendable Merkle tree-- which allows for succinct and black-box proofs of committed values. Succinct black-box proofs along with PCP of Proximity, allow us to provide a black-box implementation of Barak's protocol. Additionally, we show that the extendable Merkle tree is interesting on its own right, as one can construct generalized black-box Zero-Knowledge sets.