escrow_thresholds.md

Escrow Thresholds

There are two main strategies for implementing threshold signing policies in a taproot world right now

1. "Andrew's scheme". Advantage: m-of-n spends are always taproot key spends (maximally fungible) . Disadvantage: unproven (EDIT: the FROST paper proves a scheme very close to Andrew's scheme), interactive key setup.
2. n-choose-m many m-of-m MuSig taproot leaves. Advantage: non-interactive, easy to implement. Disadvantage: not key spends.

This document discusses a third way: escrow thresholds. They always allow key spends and the key setup is non-interactive for some parties (the escrows). The disadvantage is that they are not as general as normal thresholds and the number of possible spending transactions must be small. It's well suited for Lightning escrows and in some cases can be used in Simplicity Unchained.

Protocol

Let's look at how this works with an example. Assume Alice and Bob want to create a 2-of-3-like output with an escrow. Depending on some condition c, either Alice or Bob will get the coins of the output. If they disagree, the escrow will decide whether Alice or Bob gets the coins.

1. An unsigned funding transaction is created, sending coins to a 2-of-2 MuSig output between Alice and Bob.
2. Alice draws a scalar t_A uniformly at random, sends Bob an adaptor signature with adaptor t_A*G of a transaction sending the funding output to Bob. Alice also sends Bob a ciphertext which contains t_A encrypted to the escrows key E pay-to-contract-tweaked as E_c = E + hash(E, c)G.
3. Bob does the steps vice versa as Alice in 2.
4. Both Alice and Bob send the ciphertext and the contract c to the escrow and ask if it decrypts to the DLog of T_A = t_A*G and T_B = t_B*G respectively.
5. If so, the funding tx is signed and broadcasted.

Now if there's no dispute they can spend their 2-of-2 output however they want. If they can't agree on an outcome, either party can contact the escrow and ask reply with t_A or t_B, which would allow either of them to complete the adaptor signature and broadcast the closing transaction.

Improved Protocol

The problem with above protocol is step 4. Not only does it require interaction with the escrow even if there's no dispute, but also it requires revealing the contract. It may be possible to avoid the latter issue but I haven't found a way to do so (note that the protocol must ensure that the escrow is not tricked into decrypting for anything but Alice and Bob's shared contract) [TODO perhaps there's a way].

What we can do to get rid of step 4, is to have Alice and Bob create a NIZK proof to convince the other party that the ciphertext really is the adaptor secret encrypted to the tweaked escrow key. There obviously already exists the notion of verifiable encryption in the literature, but I have not found a scheme in the discrete-logarithm setting that works with secp256k1 and does not require special groups. This makes sense because if you're not stuck with secp256k1 you can use a more suitable group to find a way more efficient zero-knowledge proof.

From Alice's perspective, in order to encrypt the adaptor secret t_A to the pay-to-contract tweaked escrow key E_c she first creates an ephemeral key R = k*G and then computes v = t_a + f(k*E_c) where f is a "regular" function mapping elliptic curve points to integers. The ciphertext sent to Bob is then (R, v) and the escrow can decrypt the cyphertext as t_a = v - f(e_c*R) where e_c is the secret key corresponding to the tweaked E_c.

Inside the NIZK for convincing Bob that the escrow can indeed decrypt the ciphertext the costly scalar multiplication k*E_e needs to be computed. But if we use the Bulletproofs zero-knowledge proof system we can save computing t_a*G inside the circuit because bulletproofs natively support secret input scalars given in public commitments. For that reason we'll be only considering Bulletproofs from now on. Inside bulletproofs we can efficiently do arithmetic modulo secp256k1's curve order p. Therefore, in order to compute the scalar multiplication efficiently E_c should be a point in a curve E defined over a field modulo p. This means that R must also be in E. [TODO: can f just return the x-coordinate of the resulting point or do we need a more uniform distribution a la purify with a curve over an extension field?]

Extensions

It's easy to add more escrows to Alice and Bob's setup, even such that the policy is something like (Alice AND Bob) or ((Alice or Bob) and ((escrow1 and escrow2) or escrow3)). In that case Alice would encrypt t_A to escrow3's secret key, draw a random r and encrypt t_A + r to escrow1 and -r to escrow2 and show Bob (t_A + r)G and -r*G who can easily check that this sums up to t_A*G.

It's also relatively straightforward to extend this to more parties than just Alice and Bob. If we have a policy such as (Alice AND Bob AND Carol) OR (Alice AND escrow) OR (Bob AND escrow) OR (Carol AND escrow), Alice, Bob and Carol would send one adaptor signature to everyone else (each with a different adaptor secret) along with the adaptor secret encrypted to the escrow as above.

Comparison with true Thresholds

One problem with Escrow Thresholds is that the number of possible spends from the shared MuSig between Alice and Bob must be small. Because for any such possible spend, Alice and Bob must exchange adaptor signatures and proofs before funding the MuSig. In the simplest case this would be just either send the full amount to Alice or send the full amount to Bob. This limitation means that we can't use it for Simplicity Unchained contracts in general. Similarly, an important difference to true thresholds is that the escrows do not really have a say. Only after the MuSig has been funded they can pick among a couple of fixed settlement transactions, but they can not negotiate a new transaction with Alice or Bob.

One downside compared to m-of-m MuSig taproot leaves is that if you lose adaptor sigs you're out of luck. However, the funding output can always be set up with hidden m-of-m MuSig leaves with no downsides.

If we consider Lightning escrows where a payment can only be claimed if (payer AND recipient) OR (payer AND escrow) OR (recipient AND escrow) cooperate then we don't have the fallback of using taproot leaves obviously. The only known ways of setting this up are either using interactive key sharing with the escrows or Escrow Thresholds as described above.

If you know your recovery address beforehand it's also possible to use Escrow Thresholds in the 2-of-3 greenaddress setup.