From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 56488C002F for ; Mon, 24 Jan 2022 08:01:48 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 364DE4015C for ; Mon, 24 Jan 2022 08:01:48 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.199 X-Spam-Level: X-Spam-Status: No, score=-0.199 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id wXpt0iVIqAyC for ; Mon, 24 Jan 2022 08:01:46 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-lf1-x135.google.com (mail-lf1-x135.google.com [IPv6:2a00:1450:4864:20::135]) by smtp2.osuosl.org (Postfix) with ESMTPS id 108FA400F1 for ; Mon, 24 Jan 2022 08:01:45 +0000 (UTC) Received: by mail-lf1-x135.google.com with SMTP id z19so10774489lfq.13 for ; Mon, 24 Jan 2022 00:01:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:from:date:message-id:subject:to; bh=ASxayiJJc952bAsPuMUd3kn5p7NsoEVOhcTkjTOnmzk=; b=JkrfT3eng3tfFolcdzrUxL9cpee71rd0zQK/WSJLHp+Gv6Uv1JRy8yyXLRfE1wI2KN IEntmk99OrNjx0mvf+uNPFzoffWHg2vre5n4dES85bVWnDIhrPYoDcuZ0yyhERmViQVQ t/h5fcgSPqLwEzbHWZzFza510FZcSLjy0uTUy5zS5HFNZkC8sXEQcW/IpO9UN7l4GBoE eeDbcp9WFD41DmBE7bYvS+pMoHlnlQ5YCKfjsQ5yeFfJMvjKd72qdKYCx+ax6kH21dt3 X9yORH21akQsvOg5ccYFYgDExr9hK9PO+O4yuxL5/AD/PTN0eFKsgabnJhV6+3YnssyN JUqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=ASxayiJJc952bAsPuMUd3kn5p7NsoEVOhcTkjTOnmzk=; b=I+koFzr8DcEYNmfNhBldVQFl58B5JysVBPfymYW2/+ABKKYI3NIgShDgJVSO5PuK3S yV3tBIf2i8Jh/xvmBG5vR3sY2qdag6HoQQl8hVRhP8QLe8GCipBZUWZWugH9NxpFLEhV 6K8bFyoBL1cREpf9Tol0rIBRSwuwAFK4yoOn/GrAQx4ulBhjnBg+YQp2RvA6xaZkTI11 C+64EKircAB8N3agg3jF4WlTjEbvu5G55+mOOLjB2Kw/EKaxsab50ZByI7REz9cB8clM 0/TZE9D3T7lXlPQgVJzhE3uhFs9Sw7syVj9AvBwzg7Oy/b3mOcT0S3tLl1198qbdt2E6 ljPg== X-Gm-Message-State: AOAM532i9KBPfMTbCtTRBbdpvtPUraBl+8oSjiL6LU5phq2CPpVNxkzh lcGDZrDobv6HCLS0M4wVkdUcgIdhDEs3FL6dXPsu6nwIGsH6/A== X-Google-Smtp-Source: ABdhPJzCqCmiIGfvNAjOavsa4sZS0AMxZUT+wWC+SNy5tthNX4uLuEgyxNjwyqVaBTg/YSaEDoNasDDf84X78dqZzuU= X-Received: by 2002:ac2:4438:: with SMTP id w24mr12232543lfl.142.1643011303571; Mon, 24 Jan 2022 00:01:43 -0800 (PST) MIME-Version: 1.0 From: Lloyd Fournier Date: Mon, 24 Jan 2022 19:01:17 +1100 Message-ID: To: dlc-dev@mailmanlists.org, Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="0000000000001c85b805d64f6100" X-Mailman-Approved-At: Mon, 24 Jan 2022 11:03:20 +0000 Subject: [bitcoin-dev] CTV dramatically improves DLCs X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 24 Jan 2022 08:01:48 -0000 --0000000000001c85b805d64f6100 Content-Type: text/plain; charset="UTF-8" Hi dlc-dev and bitcoin-dev, tl;dr OP_CTV simplifies and improves performance of DLCs by a factor of *a lot*. ## Introduction Dryja introduced the idea of Discreet Log Contracts (DLC) in his breakthrough work[1]. Since then (DLC) has become an umbrella term for Bitcoin protocols that map oracle secret revelation to an on-chain transaction which apportions coins accordingly. The key property that each protocol iteration preserves is that the oracle is an *oblivious trusted party* -- they do not interact with the blockchain and it is not possible to tell which event or which oracle the two parties were betting on with blockchain data alone. `OP_CHECKTEMPLATEVERIFY` (CTV) a.k.a. BIP119 [2] is a proposed upgrade to Bitcoin which is being actively discussed. CTV makes possible an optimized protocol which improves DLC performance so dramatically that it solves several user experience concerns and engineering difficulties. To me this is the most compelling and practical application of CTV so I thought it's about time to share it! ## Present state of DLC specification The DLC specifications[3] use adaptor signatures to condition each possible payout. The protocol works roughly like this: 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 `i`th is the outcome transpired. 6. Either of the parties takes the `s_i`s 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 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 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: ``` CHECKTEMPLATEVERIFY 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 thresholds Now that we're using script it's very easy to do a threshold along with the script. e.g. a 2/3: ``` CHECKTEMPLATEVERIFY CHECKSIG CHECKSIGADD 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 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] short we can get rid of the hash and do the following instead for the `outcome_i`: ``` 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 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). ## Credits 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 --0000000000001c85b805d64f6100 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 
Hi dlc-dev and bitcoin-dev,

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

## Introduction

Dryja introduced the idea of Discreet Log Contracts (DLC) in his breakthrou=
gh work[1].
Since then (DLC) has become an umbrella term for Bitcoin protocols that map=
 oracle secret revelation to an on-chain transaction which apportions coins=
 accordingly.
The key property that each protocol iteration preserves is that the oracle =
is an *oblivious trusted party* -- they do not interact with the blockchain=
 and it is not possible to tell which event or which oracle the two parties=
 were betting on with blockchain data alone.

 `OP_CHECKTEMPLATEVERIFY` (CTV) a.k.a. BIP119 [2] is a proposed upgrade to =
Bitcoin which is being actively discussed.
CTV makes possible an optimized protocol which improves DLC performance so =
dramatically that it solves several user experience concerns and engineerin=
g difficulties.
To me this is the most compelling and practical application of CTV so I tho=
ught it's about time to share it!

## Present state of DLC specification

The DLC specifications[3] use adaptor signatures to condition each possible=
 payout.
The protocol works roughly like this:

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 announceme=
nt and construct a set of attestation points `S` and their corresponding pa=
youts.
3. Each attestation point for each of the `N` outcomes is calculated like `=
S_i =3D R + H(R || X || outcome_i) * X` where `X` is the oracle's stati=
c key.
4. The users combine the attestation points into *contract execution transa=
ction* (CET) points e.g `CET_i =3D S1_i + S2_i + S3_i`.
   Here `CET_i` is the conjunction (`AND`) between the event outcomes repre=
sented by `S1_i, S2_i, S3_i`.
5. The oracle(s) reveals the attestation `s_i` where `s_i * G =3D S_i` if t=
he `i`th is the outcome transpired.
6. Either of the parties takes the `s_i`s from each of the attestations and=
 combines them e.g. `cet_i =3D s1_i + s2_i + s3_i` and uses `cet_i` to decr=
ypt the CET adaptor signature encrypted by `CET_i` and broadcast the transa=
ction.

## Performance issues with DLCs

In the current DLC protocol both parties compute:
  - `E * N` attestation points where `E` is the number of events you are co=
mbining and `N` is the number of outcomes per event. (1 mul)
  - `C >=3D 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 attesta=
tion 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=3D20,N=3D2,C=3D2^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 ada=
ptor 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 t=
he BTC/USD price per dollar.
Note there may be various ways of precomputing multiplications and using fa=
st 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 co=
mbinatorially 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 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 w=
ith 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 norma=
lisation but it still brings the computational cost per CET down from hundr=
eds of microseconds to around 5 (per party).
There will be a bit more data on chain (and a small privacy loss) in the un=
cooperative 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 w=
e are doing this in channels.

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

## getting 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 do=
es not increase with the number of oracles in the threshold.
The size of the witness only increases linearly in the number of oracles an=
d 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 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 =3D R + H(R || X || outcome_i) * X
```

So for each outcome we have to hash it and multiply the result by the oracl=
e'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 (s=
ignature 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 abo=
ut someone being able to forge signatures under the oracle's key in gen=
eral you only care about them being able to forge an attestation correspond=
ing to some previously announced event i.e. you only care about forgeries o=
f things that people are actually betting on.

Long story[6] short we can get rid of the hash and do the following instead=
 for the `outcome_i`:

```
S_i =3D 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 =3D i * R + X
```

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

`S1_i + S2_j =3D (i*R1 + X) + (j*R2 + X) =3D 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 =3D (i*X + R1 + (j*X + R2) =3D (i + j)*X + R1 + R2)`

Which loses the structure and creates collisions e.g. `S1_1 + S2_2 =3D S1_2=
 + S2_1` .
Note that this collision problem also exists in the current spec and origin=
al 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 =3D R + X` and each subsequent is=
 `S_i =3D S_{i-1} + R` and so we only need to do one addition for each atte=
station point.

## In summary

In the worst case this improves DLC performance by ~30x compared to using M=
uSig2 adaptor signatures because it gets rid of all multiplications for bot=
h 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 multiplicati=
on will also help.
Communication complexity also becomes constant.

In other words, from the user's perspective everything can happen prett=
y 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 o=
f the witness is bigger and the transaction is distinguishable from other p=
rotocols (it's not longer scriptless).

## Credits

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.i=
o/dlc.pdf
[2]: https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki
[3]: https://g=
ithub.com/discreetlogcontracts/dlcspecs
[4]: http=
s://bitcoinproblems.org/problems/secure-dlcs.html
[5]: https://mailmanlists.org/pipermail/dlc-dev/2021-March/000065.html
[6]: ht=
tps://github.com/LLFourn/dlc-sec/blob/master/main.pdf
--0000000000001c85b805d64f6100--