partially-blind-swap.md

Partially Blind Atomic Swap Using Adaptor Signatures

In this scheme one of the participants of the swap does not learn which coins are being swapped. For example if a service provider engages in a partially blind atomic swap with the users Bob and Carol, the server would not be able to determine if a swapped output belongs to Bob or Carol (assuming the transaction amounts are identical or confidential). This property is very similar to TumbleBit but in the form of a scriptlessscript and therefore purely in the elliptic curve discrete logarithm setting.

The basic idea is that the discrete logarithm of the auxiliary point T in the adaptor signature is not chosen uniformly at random by the server. Instead, the user computes T = t*G where t is a blind Schnorr signature of the server over a transaction spending the funding transaction without knowing t (similar to Discreet Log Contracts).

Protocol description

Assume the server has a permanent public key A = a*G, ephemeral pubkey A1 = A + h*G where h is a tweak that is known to Bob, and ephemeral pubkey A2 which has a secret key known only to the server and doesn't have to be derived from A. Bob has two pubkeys B1 = b1*G and B2 = b2*G and H is a cryptographic hash function. Public key aggregation in "2-of-2" scripts is achieved with MuSig and the signature scheme is adapted from Bellare-Neven. The partially blind atomic swap protocol with the server and Bob as a user works as follows.

1. Setup

   • Bob anonymously asks the server to put coins into a key aggregated output O1 with public key P1 = H(A1,B1,A1)*A1 + H(A1,B1,B1)*B1.
   • Bob puts coins into a key aggregated output O2 with P2 = H(A2,B2,A2)*A2 + H(A2,B2,B2)*B2. As usual, before sending coins server and Bob agree on timelocked refund transactions in case one party disappears.

2. Blind signing

   Bob creates a transaction tx_B spending O1. Then Bob creates an auxiliary point T = t*G where t is a Schnorr signature over tx_B in the following way:

   • Bob asks the server for nonce Ra = ka*G
   • Bob creates nonce Rb = kb*G
   • Bob computes
     • the combined nonce R = Ra+Rb
     • the "blinded" nonce alpha,beta = rand, R' = R + alpha*G + beta*A
     • the challenge c1 as the Bellare-Neven style challenge hash of tx_B with respect to P1 and input 0 for aggregated key P1: c1 = H(P1, 0, R', tx_B)
     • the challenge c' for A1 as part of P1: c' = c1*H(A1,B1,A1)
     • the blinded challenge c = c'+beta
     • and the blinded signature of A times G: T = R + c*A
   • Bob sends c to the server
   • The server replies with an adaptor signature over tx_A spending O2 with auxiliary point T = t*G, t = ka + c*a where a is the discrete logarithm of permanent key A.

3. Swap

   • Bob gives the server his contribution to the signature over tx_A.
   • The server adds Bob's contribution to her own signature and uses it to take her coins out of O2.
   • Due to previously receiving an adaptor signature Bob learns t from step (2).

4. Unblinding

   • Bob unblinds the server's blind signature t as t' = t + alpha + c'*h where c' is the unblinded challenge h is the tweak for A1. This results in a regular signature (R', t') of the server (A1) over tx_B.
   • Bob adds his contribution to t' completing (R', s), s = t' + kb + c1*H(A1,B1,B1)*b1 which is a valid signature over tx_B spending O1:

     s*G = t' + kb + c1*H(A1,B1,B1) * b1
         = (ka + (c'+beta)*a + alpha + c'*h + kb + c1*H(A1,B1,B1) * b1)*G
         = R + beta*A + alpha*G + c1*(H(A1,B1,A1) * (a+h) + H(A1,B1,B1) * b1)*G
         = R' + H(P1, 0, R', tx_B)*P1
     

   • Bob waits to increase his anonymity set and then publishes the signature to take his coins from O1 resulting in the following transaction graph:

     +------------+  (R', s)   +------------+
     |         O1 +----------->|         ...|
     +------------+            +------------+
     the server's setup tx     tx_B
     
     +------------+            +------------+
     |         O2 +----------->|         ...|
     +------------+            +------------+
     Bob's setup tx            tx_A
     

As a result, the server can not link Bob's original coins and his new coins. From the server's perspective tx_B could have been just as well the result of a swap with someone else.

Blind Schnorr signatures suffer from a vulnerability known as "parallel attack" (Security of Blind Discrete Log Signatures Against Interactive Attacks, C. P. Schnorr) where the attacker collects a bunch of nonces R and sends specially crafted challenges c. The responses can be combined to create a signature forgery. Among proposed countermeasures is a simple, but currently unproven trick by Andrew Poelstra in which the signer randomly aborts after receiving a challenge.

A simpler scheme that would be broken by Aggregated Signatures

Note that Bob can get a signature of A over anything including arbitrary messages. Therefore, the server must only use fresh ephemeral keys A1 when creating outputs. This complicates the protocol because at the same time the server must not be able to determine for which exact input she signs. As a result, It's Bob's job to apply tweak h to convert a signature of A to A1.

A simpler protocol where the server uses A instead of A1 is broken by aggregated signatures because it allows spending multiple inputs with a single signature. If Bob creates many funding txs with the server, he can create a tx spending all of them, and prepares a message for the server to sign which is her part of the aggregate signature of all the inputs. The server just dumbly signs any blinded message, so can't decide if it's an aggregated sig or not. For example Bob may send the server a challenge for an aggregate signature covering output 1 with pubkeys L1 = {A, B1} and output 2 with pubkeys L2 = {A, B2} as c'=H(P1, 0, R', tx_B)*H(L1,A) + H(P2, 1, R', tx_B)*H(L2,A).

Similarly, the SIGHASH_SINGLE bug for example would have been disastrous for this scheme. In general, the Blockchain this is used in must not allow spending more than one output with a single signature.