Replying to Avatar waxwing

A train of thought coming from: "we can't do ZKPs using sigma protocols or bulletproofs on chain, because we only have ECC operations against one generator (G)":

Imagine one of the very simplest things you can do with 2 generators: proof of discrete log equivalence or DLEQ for short. This is basically the simplest possible generalization of Schnorr; one secret, two bases. This requires two ephemeral commitments (the nonce k mult. the 2 generators) and only one scalar response (one "signature", if you like).

Of course, you can't verify such a thing on chain; you can't check sJ = R_2 + hash(..)Q where Q = xJ and P = xG. You can only verify the first version, w.r.t. G: sG = R + eP, which is ofc standard Schnorr, here bip340.

But .. is there a way adaptors could help? Because an adaptor is something you verify offchain, and so it isn't restricted to one base/ generator.

Imagine your goal is "unlock a payment only if P and Q have the same DL wrt G, J" (yes I know, bizarre, but I'm fumbling towards the first sentence, here).

Obviously if we're including "verify something offchain before taking an action", we'll find it sanest to stick to a 2 party protocol first. Let's see:

1. Alice sends Bob P, Q, R1, R2 (having calculated from a random k, R1 = kG, R2 =kJ, and already knowing x_a s.t. Q=x_a J and P=x_a G); her private key is x_a

2. Alice pays into a 2-2 multisig with Bob, where her key is P, and the aggregate key is Pagg, with U1. When Alice signs it (not yet), the signature will look like:

s_a = k1 + H(R_agg + T, Pagg, txmsg_U1)x_a

Notice the +T which will be for an adaptor that Alice adds. This process is already well understood for Schnorr multisig. I am glossing over Musig related details, claiming they don't change the following.

3. Alice provides an adaptor over J for ``spending'' U1. Before writing this out, consider: we want the s-value to be the same over J as it is over G. This is problematic, because the s value comes from a structure that is basically : s = k + e*x, where e is the hash, and as per bip340, that hash *must* be exactly: H(R, P, m) where P is the onchain key, R is the onchain nonce and m is the actual transaction message. So if we do things naively, i.e. make an adaptor over the J base like:

s'J = R2 + H(R2+T, Q, message)Q

.. then we're going to fail to create the desired scenario: that the real signature 's' is the same between the J and G bases. In order to solve this we have to play a trick. We don't change the nonce or public key fields in the hash at all, i.e. we do:

s' = k2 + H(R_agg + T, Pagg, txmsg_U1)x

and have Bob verify:

s'J =?= R2 + H(R_agg + T, Pagg, txmsg_U1)Q

Superficially that is unsound; the reason is that such signatures can be forged if the corresponding nonce point R2 is not fixed into the hash/FS challenge, which it appears it isn't (also not "key-prefixing" by including the public key, here Q, in the same challenge is, at the least, problematic). However this can be solved, albeit in an unorthodox way: include both R2 and Q, which are curve points, as data inside the bitcoin transaction! (spending U1). It will just be "dead" data (e.g. OP_DROP) because you won't be able to sign against them; they use the wrong basepoint, but it is still easy).

4. Bob verifies this adaptor using (to repeat): s'J =?= R2 + H(R_agg + T, Pagg, txmsg_U1)Q.

5. Now Bob knows that if he sees the valid s for this equation, he gets the private key t of T w.r.t. J. Importantly, he also knows that if that one s corresponds to the s that is needed to spend U1, then Q and P have the discrete log equivalence property we are proving. But simply convincing Bob of a fact like that is uninteresting in itself; you can do that by simply directly sending him ZKPs of various types. So, :

6. Alice also provides offchain a DLEQ proof that T = tJ and T2 = tG

7. Alice makes another adaptor on a payment of another utxo U2, using the same t: s'_2 = k_3 + H(R_3 + T2, P2, m)P2.

8. Bob now knows that if U1 is spent, it reveals s, proves that DL Q/J = P/G, and that he can spend U2 using s_2 = s'_2 + t, having extracted t from s - s', and knowing that that t value corresponds to T2.

This could be seen as "just an adaptor based atomic swap with a bunch of extra steps", but I'd call it more "atomic swap gated by DLEQ", i.e. it will fail unless Q/J = P/G holds.

Oof, i dumped that in a text file this morning and unsurprisingly, typos:

where you see k1 and k2, it should be just "k".

This is critical, the whole point is that R1 and R2 correspond to the same secret nonce k.

Reply to this note

Please Login to reply.

Discussion

No replies yet.