summaryrefslogtreecommitdiff
path: root/a9/7473fcf437359816247afe52d72546a8dcc059
blob: fe5bb9eaf905b8b923614b1fc9b3772979ac30ed (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
Return-Path: <lloyd.fourn@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 56488C002F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 24 Jan 2022 08:01:45 +0000 (UTC)
Received: by mail-lf1-x135.google.com with SMTP id z19so10774489lfq.13
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <lloyd.fourn@gmail.com>
Date: Mon, 24 Jan 2022 19:01:17 +1100
Message-ID: <CAH5Bsr2vxL3FWXnJTszMQj83jTVdRvvuVpimEfY7JpFCyP1AZA@mail.gmail.com>
To: dlc-dev@mailmanlists.org, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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:

```
<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 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 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

<div dir=3D"ltr"><pre>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&#39;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&#39=
;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&#39;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 &gt;=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:

```
&lt;CET-hash_i&gt; CHECKTEMPLATEVERIFY &lt;CET_i&gt; 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&#39;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&#39;re using script it&#39;s very easy to do a threshold along =
with the script. e.g. a 2/3:

```
&lt;CET-hash&gt; CHECKTEMPLATEVERIFY
&lt;attestation-point1&gt; CHECKSIG
&lt;attestation-point2&gt; CHECKSIGADD
&lt;attestation-point3&gt; 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&#39;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=
&#39;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&#39;s public key.
I don&#39;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&#39;t care abo=
ut someone being able to forge signatures under the oracle&#39;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&#39;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&#39;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]: <a href=3D"https://adiabat.github.io/dlc.pdf">https://adiabat.github.i=
o/dlc.pdf</a>
[2]: <a href=3D"https://github.com/bitcoin/bips/blob/master/bip-0119.mediaw=
iki">https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki</a>
[3]: <a href=3D"https://github.com/discreetlogcontracts/dlcspecs">https://g=
ithub.com/discreetlogcontracts/dlcspecs</a>
[4]: <a href=3D"https://bitcoinproblems.org/problems/secure-dlcs.html">http=
s://bitcoinproblems.org/problems/secure-dlcs.html</a>
[5]: <a href=3D"https://mailmanlists.org/pipermail/dlc-dev/2021-March/00006=
5.html">https://mailmanlists.org/pipermail/dlc-dev/2021-March/000065.html</=
a>
[6]: <a href=3D"https://github.com/LLFourn/dlc-sec/blob/master/main.pdf">ht=
tps://github.com/LLFourn/dlc-sec/blob/master/main.pdf</a>

</pre></div>

--0000000000001c85b805d64f6100--