Verifying a proof of representation onchain

This is a continuation of the line of thinking outlined in the previous post Adaptors Generalised.

So consider that we wanted to only release a coin if a zero knowledge proof of knowledge (or ZkPOK) of the opening of a representation is known. A "representation" here is as described in that earlier post; imagine that we have a curve point \(C\) which we have calculated against a set of bases \(G_1, \ldots, G_n\), i.e. \(C = x_1G_1 + x_2G_2 + \ldots + x_n G_n\).

It's easy for a prover to provide such a proof (it's a sigma protocol, as was discussed) but it's not easy to force the verifier to unlock a coin on the blockchain if such a proof is provided. We attempt to do that here.

This may have use in, or be a step towards, verifying certain zero knowledge proving systems on chain, for example Bulletproofs (see e.g. verification (65) in that paper, which is an equation in a list of bases, but this can be converted into a proof of representation; it's the same thing).

The prover holds the secret tuple \((x)\), and provides \(C\) as above. Then they execute the protocol to create a "generalised adaptor". We will work with \(n=2\) so that we can show the complete protocol concretely:

Choose \(k_1, k_2\) and \(t_1, t_2\) at random. Calculate \(R=k_1 G_1 + k_2 G_2\) and \(T = t_1G_1 + t_2G_2\). We will also make use of the individual components of that sum: \(T_1 = t_1 G_1, T_2 = t_2G_2\).

Calculate the Fiat-Shamir challenge \(e= \mathbb{H}(R+T, C)\).

Calculate the adaptor tuple: \(\sigma'_1 = k_1 + ex_1, \sigma'_2 = k_2 + ex_2\).

Send all of the following to the Verifier: \((R, T_1, T_2, \sigma'_1, \sigma'_2)\)

The Verifier reconstructs \(T = T_1 + T_2\), then \(e= \mathbb{H}(R+T, C)\) and verifies the adaptor with \(\sigma'_1G_1 + \sigma'_2G_2 \stackrel{?}{=} R + e C\).

As was noted extensively in the previous post, this is not yet a proof of knowledge (we showed there how to forge it, and noted that this is very much part of the intended mechanic of adaptors, not a new observation).

However, if the prover can provide \(t_1, t_2\) such that \(T = t_1 G_1 + t_2 G_2\), then the proof of knowledge of the representation is complete.

Thus, we can tie this atomically to the release of a signature on an onchain transaction in, I believe, two ways. The first is as was described there under the "DLEQ half-adaptor" which involves an extra trick of fixing nonces in the transaction message. Alternatively, more simply, as follows:

Define \(\Pi_{DLEQ,i}(T_i, T_{i,G})\) as a proof of discrete log equivalence with respect to the two bases: \(G_i, G\) where the subscriptless \(G\) is the generator of secp256k1.

So if the Prover sends \((R, T_1, T_2, \sigma'_1, \sigma'_2, \Pi_{DLEQ,1}(T_1, T_{1,G}), \Pi_{DLEQ,2}(T_2, T_{2,G})) \) (in our pre-agreed limited case of \(n=2\), and the Verifier verifies the given adaptors as described above, as well as the two discrete log equivalence proofs, successfully, then all that remains is for the Verifier to set up the spending condition to include the requirement of release of the secrets corresponding to \(T_{1,G}, T_{2,G}\) - which is something he can do with "normal" adaptors.

Filling in the final details: imagine the Prover's receiving address is A and the transaction TX spends from some Verifier-owned utxo and pays the value into A. The utxo would have to be arranged such that it can be spent using \(n\) signatures (in this case, 2); for example it could be locked with a scriptPubKey that requires signatures on two public keys \(P_1 = p_1 G, P_2 = p_2G\) (there are various ways this can be set up; most importantly, there needs to obviously be a lock (perhaps with a time limit) so that the Verifier can't just spend it while ignoring the above! (Multisig, timelocks, yada yada). So the Verifer creates two adaptors like:

\(\sigma_{1,TX}' = k_{1,TX} + \mathbb{H}(R_{1,TX}+T_{1,G}, P_1,TX)p_1\)

\(\sigma_{2,TX}' = k_{2,TX} + \mathbb{H}(R_{2,TX}+T_{2,G}, P_2,TX)p_2\)

The Verifier of course passes \(\sigma_{1,TX}' , \sigma_{2,TX}'\) to the Prover, who verifies the validity of these adaptors in the normal way, and then can broadcast the transaction by adding \(t_1, t_2\) to these values, thus proving atomically that he knows the representation of \(C\).

At the beginning we used the term "attempt"; that's because there's one detail in this flow that is unorthodox: the Prover doesn't only provide a single group element \(T\) but the tuple \(T_i\) which add to \(T\) also. I don't see a way in which this could violate zero knowledgeness, but I'm not entirely sure for now.

Also a reminder of the restriction of this model, as we noted in the previous post: the Verifier can be assured that the coin won't get spent by someone who can't provide the proof, but the "someone" part isn't really what counts here; we may really want a proof that a statement is true, not a proof that a particular person possesses that proof. But the two things can be tied together; for example, to prove that a secret number A is in a range 0..2^64, we can prove that we know a list of 64 bits such that their sum (with powers of 2), in an encrypted form, is correctly represented by that list. In cases like this, we are proving knowledge of a witness, but it's that the witness exists that we care about. A more trivial example would be proving knowledge of a solution of a sudoku, which also proves that the statement "the sudoku is soluble" is true.