Scriptless-script-thinking.md

Explanation of how using Schnorr signatures, we can achieve an atomic swap of the "scriptless script" style.

This is based on Poelstra's ideas as summarised in https://download.wpsoftware.net/bitcoin/wizardry/mw-slides/2017-05-milan-meetup/slides.pdf ; also see the earlier outline in https://lists.launchpad.net/mimblewimble/msg00086.html.

Note that the details here are just my thoughts, so if you come to this randomly, don't take it as some kind of well established protocol!

Preliminaries:

We'll use || for concatenation and capitals for elliptic curve points and lower case letters for scalars.

The reader is assumed to be familiar with the basic concept of the Schnorr signature, here written in the form:

s = r + ex
e = H(P||R||m)

(Note: we can hash, as "challenge" a la sigma protocol, just R||m in some cases, and more complex things than just P||R||m, too; this is just the most fundamental case, fixing the signature to a specific pubkey; the nonce point R is always required).

For clarity, in the above, x is the private key, m is the message, r is the "nonce" and s is the signature. The signature is published as either (s, R) or (s, e), the former will be used here if necessary.

Apologies if people are more used to s = r - ex, for some reason it's always + to me!

Construction of an "adaptor" signature

Alice (P = xG), constructs for Bob:

• Calculate T = tG, R = rG
• Calculate s = r + t + H(P || R+T || m) * x
• Publish (to Bob, others): (s', R, T) with s' = s - t (so s' should be "adaptor signature"; this notation is retained for the rest of the document).

Bob can verify the adaptor sig s' for T,m:

s' * G ?= R + H(P || R+T || m) * P

This is not a valid sig: hashed nonce point is R+T not R;

Bob cannot retrieve a valid sig : to recover s'+t requires ecdlp solve.

After validation of adaptor sig by Bob, though, he knows:

Receipt of t <=> receipt of valid sig s = s' + t

Deniability:

Given any (s, R) on chain, create (t, T), and assert that the adaptor signature was: s' = s - t, with R' = R - T, so adaptor verify eqn was: s'G = R' + H(P || R'+T || m)P

Moving to the 2-of-2 case, with Schnorr

Start by assuming Alice key (x_A, P_A), Bob (x_B, P_B). Each chooses a random nonce point r_A/R_A, r_B/R_B and exchange.

2-of-2 Schnorr without adaptor sig

To avoid related-key attacks (if you don't know what that means see e.g. the "Cancelation" section in https://diyhpl.us/wiki/transcripts/scalingbitcoin/milan/schnorr-signatures/), the "hash challenge" is made more complex here, as was noted in the first section on Schnorr signatures. The two parties Alice and Bob, starting with pubkeys P_A, P_B, construct for themselves a "joint key" thusly:

P_A' = H(H(P_A||P_B) || P_A) * P_A ,
P_B' = H(H(P_A||P_B) || P_B) * P_B ,
joint_key = P_A' + P_B'

Note that Alice possesses the private key for P_A' (it's H(H(P_A||P_B) || P_A) * x_A, we call it x_A' for brevity), and likewise does Bob. From now on, we'll call this "joint_key" J(A, B) to save space.

Common hash challenge:

H(J(A, B) || R_A + R_B || m) = e
s_agg = = r_A + r_B + e(x_A' + x_B')
-> s_agg * G = R_A + R_B + e * J(A, B)

Alice's sig: s_A = r_A + e * x_A', Bob's sig: s_B = r_B + e * x_B' and of course: s_agg = s_A + s_B

2-of-2 with adaptor sig

Now suppose Bob chooses t s.t. T = t * G, and Bob is going to provide an adaptor signature for his half of the 2-of-2.

Then:

1. Alice, Bob share P_A, P_B, R_A, R_B as above; Bob gives T to Alice
2. Alice and Bob therefore agree on e = H(J(A, B) || R_A + R_B + T || m) (note difference, T)
3. Bob provides adaptor s' = r_B + e * x_B' (as in previous section, not a valid signature, but verifiable)
4. Alice verifies: s' * G ?= R_B + e * P_B'
5. If OK, Alice sends to Bob her sig: s_A = r_A + e * x_A'
6. Bob completes, atomically releasing t: first, construct s_B = r_B + t + e * x_B', then combine: s_agg = s_A + s_B and broadcast, then Alice sees s_agg
7. Alice subtracts: s_agg - s_A - s' = (r_B + t + e * x_B') - (r_B + e * x_B') = t

Thus the desired property is achieved: t is revealed by a validating "completion" of the adaptor signature.

Note, however that this has no timing control, Bob can jam the protocol indefinitely at step 6, forcing Alice to wait (assuming that what we're signing here is a transaction out of a shared-control outpoint); this is addressed in the fleshed out protocol in the next section, though.

For the remainder, we'll call the above 7 steps the 22AS protocol, so 22AS(Bob,t, Alice) for Bob, secret t, and Alice. Bob is listed first because he holds t.

So this 22AS was a protocol to swap a coin for a secret, to do atomic swaps we need to extend it slightly: have two transactions atomic via the same secret t.

The Atomic Swap construct, using 2-of-2 schnorr + adaptor signatures

This is now fairly straightforward, inheriting the main design from the existing "atomic swap" protocol.

A. Alice and Bob agree on a pair of scriptPubkeys which are based on 2 of 2 pubkeys using Schnorr, let's name them using D for destination address (A is taken by Alice): D_1 being 2-2 on (P_A1, P_B1) and D_2 being 2-2 on (P_A2, P_B2). Note that these pubkeys, and therefore destination addresses, are not dependent in any way on "adaptor" feature (which is a property only of nonces/sigs, not keys).

B. Alice prepares a transaction TX1 paying 1 coin into D_1, shares txid_1, and requires backout transaction signature from Bob. Backout transaction pays from txid_1 to Alice's destination but has locktime L1.

C. Bob does the (nearly) exact mirror image of the above: prepares TX2 paying 1 coin into D_2, shares txid_2, requires backout transaction signature from Alice. Backout transaction pays from txid_2 to Bob's destination with locktime L2 which is significantly later than L1.

D. Then Alice and Bob broadcast TX1 and TX2 respectively and both sides wait until both confirmed. If one party fails to broadcast, the other uses their backout to refund.

E. If both txs confirmed (N blocks), Alice and Bob follow steps 1-4 of 22AS(Bob, t, Alice) (described in previous section) for some t, for both the scriptPubkeys D_1 and D_2, in parallel, but with the same secret t in each case (a fact which Alice verifies by ensuring use of same T in both cases). For the first (D_1) case, they are signing a transaction spending 1 coin to Bob. For the second, D_2, they are signing a transaction spending 1 coin to Alice. Note that at the end of these steps Alice will possess a verified adaptor sig s' for both of the spend-outs from D_1, D_2.

E(a). Any communication or verification failure in those 1-4 steps (x2), both sides must fall back to timelocked refunds.

F. The parties then complete (steps 5-7) the first 22AS(Bob, t, Alice) for the first transaction TX1, spending to D_1 to give Bob 1 coin. Alice receives t as per step 7.

F(a). As was mentioned in the previous section, Bob can jam the above protocol at step 6: if he does, Alice can extract her coins from her timelocked refund from D_1 in the period between L1 and L2. The fact that L2 is (significantly) later is what prevents Bob from backing out his own spend into D_2 and claiming Alice's coins from D_1 using the signature provided in step 5. (Note this time asymmetry is common to all atomic swap variants).

G. (Optionally Bob may transmit t directly over the private channel, else Alice has to read it from the blockchain (as per above 22AS protocol) when Bob publishes his spend out of D_1).

H. Alice can now complete the equivalent of steps 5-7 without Bob's involvement for the second parallel run for D_2: she has t, and adds it to the already provided s' adaptor sig for the transaction paying her 1 coin from D_2 as per first 4 steps. This s' + t is guaranteed to be a valid s_B, so she adds it to her own s_A to get a valid s_agg for this spend to her of 1 coin, and broadcasts.

Privacy implications

In absence of backouts being published (ie in cooperative case), these scriptPubkeys will be the same as any other Schnorr type ones (N of N multisig will not be distinguishable from 1 of 1). The signatures will not reveal anything about the shared secret t, or the protocol carried out, so the 2 transaction pairs (pay-in to D_1,D_2, pay out from same) will not be tied together in that regard. The issue of amount correlation, however, has not been in any way addressed by this, of course.