[dlc-dev] Oracle attestations can be simplified and be more much more efficient

[Thibaut Le Guilly]

Hi again,

After sending the previous email, I finally put my finger on why I had the
feeling that my benchmarks were favoring Lloyd's approach. When
constructing all of the possible signature points with it, I was first
constructing the signature points for each nonce (so in a binary
decomposition that would be computing two sigpoint per nonce),
before computing all their possible combinations (and adding them). It hit
me that it is possible to do exactly the same with the regular hash based
approach and that it would probably be much faster than my factorized
approach, as the number of EC multiplication to be computed would only be
nb_nonces * nb_outcome_per_nonce (compared to nb_outcomes for the factored
version, which is a huge difference).

I assumed that as the number of outcomes grew, the difference between
hashed and non hashed versions would shrink as computing the combinations
sum would become more expensive than computing the initial signature
points. Doing some experiments showed that this was indeed the case. The
following shows the average time taken to compute the signature point for
all possible outcomes pre-computing points with and without hashing
messages, with an increasing number of nonces and two outcomes per nonce:

Number of nonces                           With Hash
      Without Hash                            Without hash aggregated
6                                       7,116,791 ns/iter (+/- 1,681,303)
     5,113,783 ns/iter (+/- 1,014,534)       1,508,463 ns/iter (+/- 112,188)
7                                     13,178,718 ns/iter (+/- 839,907)
   12,454,108 ns/iter (+/- 2,264,169)       3,743,936 ns/iter (+/-
1,042,749)
8                                     28,154,685 ns/iter (+/- 3,183,984)
  26,512,112 ns/iter (+/- 3,409,204)       8,003,315 ns/iter (+/- 704,669)
9                                     62,004,122 ns/iter (+/- 8,454,819)
  62,535,089 ns/iter (+/- 11,949,455)   17,702,449 ns/iter (+/- 1,018,206)
10                                 138,226,956 ns/iter (+/-
13,278,376) 138,874,094
ns/iter (+/- 11,392,584)   40,799,016 ns/iter (+/- 2,767,983)

So indeed as the number of outcomes grows, the performance gain disappears.
And while the aggregated version is still roughly ~3 times faster, it is
mainly because of the multi-oracle setting where all oracles have the same
outcome. In the case of multi-oracle with bounded error the gains will
likely decrease by quite a lot, even though there could be some
optimization that might be applied that couldn't with hashes (it's quite a
lot of work to implement everything that would be required to benchmark
that properly unfortunately).

Note that one reason that the non-hashing version doesn't provide great
benefits here (as Lloyd already previously remarked) is that we use binary
decomposition and thus have only two possible outcomes per nonce. If the
number of possible outcomes per nonce grew large, I expect that Lloyd's
approach would outperform by quite a lot. But I am also rather unsure that
we will have such a setup.

Best,

Thibaut

On Fri, Feb 26, 2021 at 4:33 PM Thibaut Le Guilly <
thibaut at cryptogarage.co.jp> wrote:

> Hi all,
>
> As I was doing some benchmarking to see how to optimize the creation of a
> signature point which seemed quite slow when using numerical decomposition,
> I ended up also benchmarking this proposal (with quite some help from
> Lloyd, thanks!). The following results were obtained by benchmarking the
> creation of signature points for all possible outcomes when using 3
> oracles, 5 nonces, and 2 outcomes per nonce.
>
> Original sequential:
>           31,071,116 ns/iter (+/- 3,749,403)
> Original outcome parallelized:
>     11,382,976 ns/iter (+/- 4,162,747)
> Factorized:
>              11,695,640 ns/iter (+/- 920,184)
> Factorized outcome parallelized:
>    4,407,871 ns/iter (+/- 2,431,375)
> Factorized oracle parallelized:
>      8,657,884 ns/iter (+/- 3,446,381)
> Factorized oracle and outcome parallelized:
>  4,362,859 ns/iter (+/- 2,637,939)
> Lloyd's technique:
>             2,387,935 ns/iter (+/- 205,201)
> Lloyd's technique + aggregate oracle nonces and pubkeys:     782,595
> ns/iter (+/- 66,201)
> Lloyd's technique + oracle parallelized
>  1,380,110 ns/iter (+/- 639,166)
>
> Outcome parallelized = computation of sigpoint for each outcome is
> parallelized
> Oracle parallelized = computation of sigpoint for each oracle is
> parallelized
>
> As you can see Lloyd's proposal outperforms the others by quite a lot, in
> particular when aggregating oracle nonces and public keys before computing
> sigpoints (which cannot be done when using hashes). We can note that the
> benchmark might favor Lloyd's approach slightly as it works particularly
> well for computing sigpoints of consecutive outcomes and that with
> compression we don't always need to compute all sigpoints, but the
> difference performance improvement is such that I don't think it will
> matter.
>
> You can find the benchmark code here:
> https://github.com/p2pderivatives/rust-dlc/tree/sig-point-bench-tmp
> (warning this is not pretty code, only meant for experimental purpose). Run
> `cargo bench --features unstable` to run the benchmarks.
>
> Best,
>
> Thibaut
>
> On Tue, Jan 26, 2021 at 10:31 AM Lloyd Fournier via dlc-dev <
> dlc-dev at mailmanlists.org> wrote:
>
>> Hi list,
>>
>> I want to expand on a nuance of the performance improvement. Since it
>> only saves ecmults when computing the anticipation points. it won't have
>> much of an effect on the performance of binary digit decomposition. If you
>> have a 16 bit number you will have 16 R values and do 32 ecmults. With this
>> proposal above you will instead only have to do 16 ec additions which would
>> make it ~20 times faster.
>>
>> But let's say we have 1k CETs for this event in binary digit
>> decomposition then you will have to do a few thousand EC additions to
>> produce the encryption key for each CET signature (each of the CETs takes
>> <16 additions). The time it takes to do these additions will make the
>> performance improvement offered by speeding up the anticipation point
>> calculation relatively insignificant. The performance improvement is mostly
>> felt when you have a single R value with many possible outcomes (i.e. not
>> binary digit decomposed).
>>
>> Having said that I still think this is a good idea since it is simpler to
>> implement and doesn't require maintaining a mangled BIP340 function to
>> produce the anticipation point. This idea can be implemented with
>> libsecp256k1's public API.
>>
>> Cheers,
>>
>> LL
>>
>>
>>
>> On Tue, Dec 29, 2020 at 1:23 PM Lloyd Fournier <lloyd.fourn at gmail.com>
>> wrote:
>>
>>> Merry Christmas list,
>>>
>>> A Schnorr signature has the form (R, s) where
>>> 1. R = r *G for some secret nonce r
>>> 2. s = r + c*x where c = H(R || X || m) for a message m and some hash
>>> function H
>>>
>>> The original DLC paper suggests re-using this structure but with R
>>> published upfront (in what we call the *announcement*) to create a list of
>>> anticipation points computed like P = R + c_i * X where c_i = H(R || X ||
>>> m_i) where m_i indicates the i'th possible outcome of the event.
>>>
>>> I make the claim that c_i need not be the result of a hash function. c_i
>>> can instead simply be set to i. So to attest to the 3rd outcome set c_i = 2
>>> and the oracle reveals s = r + 2 * x.
>>>
>>> == Security
>>>
>>> The only security property required for the point anticipation scheme is
>>> that (i) it reveals no information other than the list of points (zero
>>> knowledge) (ii) if the oracle reveals the secrets for two points then they
>>> lose their secret key (no equivocation).
>>> Clearly (i) holds since R is still just a random point.
>>> (ii) holds for the same reason as in the original -- two different c_i
>>> and c_j reveals x = (s_i - s_j) / (c_i - c_j). The change from hash of
>>> message to index is irrelevant.
>>>
>>> == Impact
>>>
>>> The main specification change would be to make outcome descriptors
>>> describe an ordered list of outcomes rather than a set of strings. e.g. the
>>> enumeration descriptor would simply assign the index to each outcome.
>>>
>>> The benefits of applying the above idea are:
>>> 1. It would reduce the time taken to compute the list of anticipation
>>> points to ~1/12 of the time currently taken since you can avoid doing any
>>> ec multiplications. You can incrementally add X to each previous value
>>> (starting with R) to get the next anticipation point. In the current
>>> protocol you have to verify ECDSA adaptor signatures so this would still
>>> lead to a time reduction of 1/2 to 1/3 since it removes 2/3 of the ecmults
>>> (depends a lot on implementation).
>>> 2. In the future you could capture the full speedup by not doing adaptor
>>> signatures and just putting each outcome in its own Taproot branch and
>>> using OP_CTV to enforce the outcome.
>>> 3. It removes arbitrary structure from the scheme and is easier to
>>> specify and implement (no need to talk about tagged hashes or to have a
>>> BIP340 implementation).
>>> 4. It gets rid of all concerns about utf8 and message encoding since
>>> outcomes are represented by integers.
>>>
>>> The downsides are mostly rhetorical:
>>> 1. We couldn't talk about "signing the outcome" because that's not what
>>> we're doing anymore (actually we were never really doing that but it was at
>>> least not too much of a lie since there was at least a signature at the end
>>> of it). I don't have an idea about the best way to talk about it yet.
>>> 2. The oracle's attestation could no longer provide useful information
>>> by itself. I liked the idea that systems who didn't care about DLCs could
>>> still use the oracles to get info about the world just from the signature
>>> and the message it signed. You can still use oracles in this way here but
>>> you *must* have the announcement with the attestation data to figure out
>>> what was attested to.
>>>
>>> Let me know your thoughts and hope you have a good break.
>>>
>>> Cheers,
>>>
>>> LL
>>>
>>
>> dlc-dev mailing list
>> dlc-dev at mailmanlists.org
>> https://mailmanlists.org/mailman/listinfo/dlc-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/mailman/private/dlc-dev/attachments/20210301/5ece8cfd/attachment.htm>