pedersen-swap.md

Atomic Pedersen Swap Using Adaptor Signatures

An atomic Pedersen swap exchanges a coin with the opening (r, x) of a Pedersen commitment r*G + x*H. By using adaptor signatures this can be done as a scriptless script such that a Bitcoin output that requires revealing an opening appears like a normal payment on-chain. Therefore, it can be a replacement for scripts involving OP_SHA256 <hash> OP_EQUAL when it's not required to commit or open publicly.

Additionally, it allows using Pedersen commitments in Bitcoin or any other crypto-currency supporting adaptor signatures without adding Pedersen commitment in the consensus code (for example in the form of a new opcode). Pedersen commitments are homomorphic commitments which enables many interesting applications. For example, proving knowledge of the opening of a commitment in zero knowledge or re-blinding a given commitment by adding r'*G (maybe useful in lightning). Current applications of Pedersen commitments in crypto-currencies include Confidential Transactions, Confidential Assets and Mimblewimble.

One important ingredient for these swaps is a multiplication proof of Pedersen commitments described below.

Multiplication Proof for Pedersen Commitments

This is a non-interactive zero knowledge proof that for given Pedersen commitments Q = r*G + x*H, T1 = t1*G and T2 = t2*G it holds that r = t1*t2. The given construction is a special case (commitment to 0) of the proof from the paper Zero-knowledge proofs of knowledge for group homomorphisms by Ueli Maurer section 6.7 with the addition of the Fiat-Shamir heuristic.

Informally, the scheme consists of the two algorithms "generate" and "check":

• Generate

  select `k1, k2` to be uniformly random scalars and compute
  R1 <- k1*G
  R2 <- k1*t2*G + k2*H
  s1 <- k1 + H(R1, R2)*t1
  s2 <- k2 + H(R1, R2)*x
  return proof (R1, R2, s1, s2)
  

• Check proof (R1, R2, s1, s2)

  s1*G ?= R1 + H(R1, R2)*T1
  s1*T2 + s2*H ?= R2 + H(R1, R2)*Q
  

It helps to get some intuition for the proof by verifying completeness:

s1*G = k1*G + H(R1, R2)*t1*G
     = R1 + H(R1, R2)*T1
s1*T2 + s2*H = k1*T2 + H(R1,R2)*t1*T2 + k2*H + H(R1,R2)*x*H
             = k1*t2*G + k2*H + H(R1,R2)*(t1*T2 + x*H)
             = R2 + H(R1, R2)*Q

Protocol rationale

Assume someone wants to buy the opening (r, x) of a Pedersen commitment Q = r*G + x*H from a seller. The seller can't just use r*G as the adaptor point in a partial signature and send it to the buyer. Upon receiving r*G the buyer would compute Q - r*G = x*H and since x can belong to a small set, the buyer could simply brute-force x without paying. This is where the multiplication proof for Pedersen commitments comes into play: the seller chooses t1 and t2 s.t. t1*t2 = r, sends T1 = t1*G and T2 = t2*G as adaptor points to the buyer along with the multiplication proof. Obtaining r from T1 and T2 is the computational Diffie-Hellman problem, but learning t1 and t2 during the swap allows the buyer to compute r.

Because x is multiplied by H and not G there is no straightforward way to similarly put x*H in a partial signature. Let xi be the i-th bit of x. The seller creates one Pedersen commitment Qi = ri*G + xi*G for every bit of x. After learning all ri during the swap, the buyer can reconstruct x bitwise by checking whether Qi is a commitment to 0 or 1. Committing to each bit of a value in a Pedersen commitment in a verifiable way is exactly what the range proof in confidential transactions. So we can abuse that scheme not to prove ranges, but to prove that each Qi commits to a bit of x.

As a result, the seller must send partial signatures for the factors ti1 and ti2 of each ri. In general, in order to reveal multiple secret adaptors u1, ..., un with a single signature the seller must create partial signatures (si, R + sum(uj over j)*G - ui*G, ui*G). This ensures that all partial signatures commit to the same Schnorr signature nonce R + sum(uj over j)*G.

However, simply sending multiple partial signatures in that way is problematic. Say the seller sends one adaptorless signature with adaptor Ti1=ti1*G and one with adaptor Ti2=ti2*G. Then even without seeing the actual signature, by just subtracting the signatures the buyer learns -ti1 + ti2. Instead, the seller uses adaptor H(Ti1)*ti1*G and H(Ti2)*ti2*G revealing H(Ti1)ti1 - H(Ti2)ti2 which is meaningless for the buyer.

Protocol description

Assume someone wants to buy the opening (r, x) of a Pedersen commitment Q = r*G + x*H from a seller.

1. Setup

   • The seller publishes a range proof to allow potential buyers to later reconstruct x from just Q and r. Assuming a prime order group with an order close to 2^256 the seller publishes (Q0, ..., Q255, e, s0, ..., s255) where sum(Qi) = Q and e = hash(si*G + hash(si*G + e*Qi)*(Qi-2^i*H)).
   • The buyer checks the range proof and sends the agreed-upon amount of coins to a key-aggregated multisig output of the buyer and seller (after receiving a timelocked refund transaction signed by the seller).

2. Adaptor signatures

   • Just as in regular atomic swaps using adaptor signatures, the parties agree on an R for the signature. The seller creates a transaction spending the coins from the multisig output and computes a Bellare-Neven challenge c for the transaction.
   • For each bit commitment Qi, seller generates a uniformly random scalar ti1 and sets ti2, such that ti1*ti2*G = ri*G = Qi-xi*H. Then the seller computes adaptors Ti1 = ti1*G and Ti2 = ti2*G and sends partial signatures (si1, R + sum(Ai) - H(Ti1)*Ti1, H(Ti1)*Ti1) and (si2, R + sum(Ai) - H(Ti2)*Ti2, H(Ti2)ti2) where Ai is the sum of both adaptors. The seller also sends a multiplication proof for Pedersen commitments proving the multiplicative relationship of the blinding factors of Ti1, Ti2 and Qi.

3. Swap

   • The buyer verifies the partial signatures and multiplication proofs and sends his contribution to the signature.
   • The seller completes the signature (R, s) and publishes it along with the transaction to take her coins.
   • Just as in regular atomic swaps using adaptor signatures, the buyer can recover the discrete logarithm of the adaptor by subtracting the partial signature from the corresponding s. So for each bit commitment, the buyer is able to recover ti1 and ti2.
   • Because it holds that ti1*ti2 = ri, the buyer can reconstruct x by setting the i-th bit of x to 0 if Qi == ti1*ti2*G + 0*H and to 1 otherwise.