ZKP: Proving knowledge of a variable length hash preimage

Question

I am currently trying to implement a proof of knowledge of the preimage to a public hash image using different zkp system implementations.

There are a lot of examples that do exactly this (see this question for some further reference). But: All of these have a fixed input size to the hash function (often two times 256-bits to do merkle tree proofs). Now while this is very convenient for examples, I would like to allow the preimage to be variable in length.

I have some questions on this:

1. Is a variable length input possible in zkSNARKs, where the verifier and prover keys have to be calculated beforehand? Can I create a prover key that permits arbitrary input lengths? To my understanding this is not possible and the prover would have to reveal the preimage length before the trusted setup.

2. In Bulletproofs I have to split up the preimage into 32 byte chunks, represent them as scalars and commit to each. Is there a way to avoid a linear amount of commitments to the size of the preimage?

Answer 1

(I'm writing this all with Bulletproofs in the back of my head)

Variable length inputs

As far as I know, it's not possible to achieve literal variable/secret-length inputs, except if I'm allowed to tweak your definition a bit. If you would allow input lengths up to a certain amount $n_{max}$, then you can vary the length below it. To achieve this, you can for example always commit to $n_{max}$ inputs, where you set the first $n$ inputs to your real inputs $v_1,\dots,v_n$, and the last $n_{max} - n$ to a semantically meaningless input. Then your proof protocol can be:

$$ \bigvee_{i=1}^{n_{max}} \text{statement when length = }i\text{ using } \{v_1,\dots,v_i\} $$

I.e., you write a proof that is the disjunction of the statements for proofs of length $i$. Of course, this makes your statement more complex, but a system like Bulletproofs compresses it well. You would need $n_{max}-1$ additional multipliers for the disjunction, thus if your statement for length $i$ needs $\text{poly}(i)$ multipliers, the total statement length would be something like $$\mathcal{O}(\log(n_{max}\cdot \text{poly}(n_{max}))) = \mathcal{O}(\log(n_{max}) + \log(\text{poly}(n_{max}))),$$ which gives you a constant overhead.

Constant-size commitments

Contrary to popular believe, Bulletproof witnesses don't necessarily need to be input commitments. The Bulletproofs paper actually does two main things to the original 2016 protocol of Bootle et al: reduce the complexity of the inner-product argument, and add support for Pedersen commitments. The latter just means that you don't have to implement Pedersen commitments inside the circuit (which would hurt the performance a lot). So, the way to avoid chunking and committing, is to avoid committing completely. After all, you could see your hash as a (imperfectly hiding) commitment already.

If you want to see how this works inside the main Bulletproofs equation ($W_L\cdot\vec a_L + W_R\cdot \vec a_R + W_O\cdot \vec a_O = W_V\cdot \vec v + \vec c$), notice that $\vec v$ is not the whole witness; $\vec a_L, \vec a_R \text{ and } \vec a_O$ are also part of the witness.

If you want an example of how this could work in practice, have a look at the excellent Rust-implementation of Bulletproofs arithmetic circuits. Their r1cs-integrated-range-proof test for example, decomposes a witness number in 64 different bit-variables, constrains the bits and only then binds it to the commitment. You could perfectly modify that code to bind the bits to a hash input gadget, and constrain the output of the hash gadget to your hash value.

This all of course requires knowledge of the input length, but the trick from above can then be used to hide the length up to a certain bound.

I hope this helps your case!