[REPOST - for better readability]

Hi dlc-dev and bitcoin-dev,

tl;dr OP_CTV simplifies and improves performance of DLCs by a factor of a lot.

IntroductionIntroduction

Dryja introduced the idea of Discreet Log Contracts (DLC) in his
breakthrough work

[1]

OP_CHECKTEMPLATEVERIFY (CTV) a.k.a. BIP119

[2]

Present state of DLC specificationPresent state of DLC specification

The DLC specifications

[3]

1. Oracle(s) announce events along with a nonce R for each event.
   Let's say each event has N outcomes.
2. Two users who wish to make a bet take the R from the oracle announcement and construct a set of attestation points S and their corresponding payouts.
3. Each attestation point for each of the N outcomes is calculated like S_i = R + H(R || X || outcome_i) * X where X is the oracle's static key.
4. The users combine the attestation points into contract execution transaction (CET) points e.g CET_i = S1_i + S2_i + S3_i.
   
   Here CET_i is the conjunction (AND) between the event outcomes represented by S1_i, S2_i, S3_i.
5. The oracle(s) reveals the attestation s_i where s_i * G = S_i if the ith is the outcome transpired.
6. Either of the parties takes the s_is from each of the attestations and combines them e.g. cet_i = s1_i + s2_i + s3_i and uses cet_i to decrypt the CET adaptor signature encrypted by CET_i and broadcast the transaction.

Performance issues with DLCsPerformance issues with DLCs

In the current DLC protocol both parties compute:

• E * N attestation points where E is the number of events you
  are combining and N is the number of outcomes per event. (1 mul)
• C >= E * N CET adaptor signatures and verify them. (2 mul -- or
  with MuSig2, 3 muls).

Note that the number of CETs can be much greater than the number of
attestation points. For example,
if an oracle decomposes the price of BTC/USD into 20 binary digits
e.g. 0..(2^20 -1), you could have
E=20,N=2,C=2^20. So the biggest concern for worst case performance
is the adaptor signatures multiplications.

If we take a multiplication as roughly 50 microseconds computing
MuSig2 adaptor signatures for ~6000 CETs would take around a second of
cpu time (each) or so.
6000 CETs is by no means sufficient if you wanted, for example, to bet
on the BTC/USD price per dollar.
Note there may be various ways of precomputing multiplications and
using fast linear combination algorithms and so on but I hope this
provides an idea of the scale of the issue.
Then consider that you may want to use a threshold of oracles which
will combinatorially increase this number (e.g. 3/5 threshold would
10x this).

You also would end up sending data on the order of megabytes to each other.

committing to each CET in a tapleaf with CHECKTEMPLATEVERIFYcommitting to each CET in a tapleaf with CHECKTEMPLATEVERIFY

What can we do with OP_CTV + Taproot to improve this?

Instead of creating an adaptor signature for every CET, commit to the
CET with OP_CTV in a tapleaf:

<CET-hash_i> CHECKTEMPLATEVERIFY <CET_i> CHECKSIG

When the oracle(s) reveals their attestations either party can combine
them to get the secret key
corresponding to CET_i and spend the coins to the CET (whose CTV
hash is CET-hash) which
distributes the funds according to the contract.

This replaces all the multiplications needed for the adaptor signature
with a few hashes!
You will still need to compute the CET_i which will involve a point
normalisation but it still brings the computational cost per CET down
from hundreds of microseconds to around 5 (per party).
There will be a bit more data on chain (and a small privacy loss) in
the uncooperative case but even with tens of thousands of outcomes
it's only going to roughly double the virtual size of the transaction.
Keep in mind the uncooperative case should hopefully be rare too esp
when we are doing this in channels.

The amount of data that the parties need to exchange is also reduced
to a small constant size.

getting rid of combinatorial complexity of oracle thresholdsgetting rid of combinatorial complexity of oracle thresholds

Now that we're using script it's very easy to do a threshold along
with the script. e.g. a 2/3:

<CET-hash> CHECKTEMPLATEVERIFY
<attestation-point1> CHECKSIG
<attestation-point2> CHECKSIGADD
<attestation-point3> CHECKSIGADD
2 EQUAL

The improvement here is that the amount of computation and
communication does not increase with the number of oracles in the
threshold.
The size of the witness only increases linearly in the number of
oracles and only in the un-cooperative case.
This also solves a security issue with the current spec because
attestation points from different oracles are no longer summed (which
is a problem

[4]

Getting rid of the attestation point multiplicationGetting rid of the attestation point multiplication

It's possible to get rid of the EC multiplications from the
attestation point computation too.
This is optimistically a 10x improvement but in the most important
cases it's a negligible improvement since computing the E*N
attestion points is a small fraction of the total CET point
computation.

Recall the original Schnorr style DLC attestation point was computed like:

S_i = R + H(R || X || outcome_i) * X

So for each outcome we have to hash it and multiply the result by the
oracle's public key.
I don't think hashing is necessary

[6]

First note that an oracle attestation scheme is not a signature scheme:

1. The users need to be able to compute the attestation point beforehand (signature schemes do not require the verifier to be able to compute anything before hand).
2. There is a very different concept of a forgery -- you don't care about someone being able to forge signatures under the oracle's key in general you only care about them being able to forge an attestation corresponding to some previously announced event i.e. you only care about forgeries of things that people are actually betting on.

Long story

[6]

S_i = R + i * X

For each outcome_i the oracle will reveal a different linear
combination of R and X.
However, if we still want to preserve the ability to add attestation
points together to create an AND like condition for points
attestations from the same oracle so we have to do:

S_i = i * R + X

which when we combine two attestations from the same oracle becomes:

S1_i + S2_j = (i*R1 + X) + (j*R2 + X) = i*R1 + j*R2 + 2*X

As you can see the addition preserves the linear structure.
If you were to do the original suggestion it would be:

S1_i + S2_j = (i*X + R1 + (j*X + R2) = (i + j)*X + R1 + R2)

Which loses the structure and creates collisions e.g. S1_1 + S2_2 = S1_2 + S2_1 .
Note that this collision problem also exists in the current spec and
original paper[4,5] but requires a solving a hashing k-sum that should
be hard to do in practice.

So, when we compute for i in 1..N, S_1 = R + X and each subsequent
is S_i = S_{i-1} + R and so we only need to do one addition for each
attestation point.

In summaryIn summary

In the worst case this improves DLC performance by ~30x compared to
using MuSig2 adaptor signatures because it gets rid of all
multiplications for both parties.
In the case of a 3/5 threshold performance would be improved by another 10x.
Depending on the kind of event, removing the attestation point
multiplication will also help.
Communication complexity also becomes constant.

In other words, from the user's perspective everything can happen
pretty much instantly even on more resource constrained devices and
bad internet connections.

The downside of the protocol is that in the un-cooperative case, the
size of the witness is bigger and the transaction is distinguishable
from other protocols (it's not longer scriptless).

CreditsCredits

Special thanks to:

• Ruben Somsen who first made the observation that OP_CTV could be applied to DLCs in the way presented here.
• Thibaut Le Guilly who did benchmarking on getting rid of the attestation point multiplication.
• Nadav Cohen who pointed out that doing R + i*X was broken.

[1]: https://adiabat.github.io/dlc.pdf

[2]: https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki

[3]: https://github.com/discreetlogcontracts/dlcspecs

[4]: https://bitcoinproblems.org/problems/secure-dlcs.html

[5]: https://mailmanlists.org/pipermail/dlc-dev/2021-March/000065.html

[6]: https://github.com/LLFourn/dlc-sec/blob/master/main.pdf