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

[Lloyd Fournier]

Iv'e updated https://github.com/LLFourn/dlc-sec/blob/master/main.pdf with
some discussion of oracle aggregation and mulit-party attestation. No new
proofs but some useful discussion. It should probably be re-read starting
with the "simple" scheme section again. Feedback welcomed.

LL

On Tue, 2 Mar 2021 at 17:49, Lloyd Fournier <lloyd.fourn at gmail.com> wrote:

> Hi Jesse, Nadav,
>
> Thanks for putting some effort towards poking holes in this Jesse. What
> Nadav says is correct in my mind. I haven't modelled this announcement
> signing but it is super important (I am disappointed I didn't discuss this
> anywhere in the paper linked by Nadav).
>
> To fix this I am about to add the following two sentences to the
> attestation unforgeability section:
>
> In the real world we assume that announcements are signed under a
> different key (also known to belong to the oracle) so that each user can
> verify an announcement did indeed come from an oracle before using it.
> Forcing announcements to be signed under the attestation key would
> needlessly complicate the security analysis since it would also give us the
> extra task of proving that the announcement signature scheme remains
> unforegable when composed with an attestation scheme.
>
> I think that's worth discussing tomorrow.
>
> LL
>
> On Tue, 2 Mar 2021 at 14:37, Nadav Kohen via dlc-dev <
> dlc-dev at mailmanlists.org> wrote:
>
>> Ah I see what you're saying now, so I believe this is currently protected
>> against by the fact that oracle announcements are signed by the oracle
>> signing keys (and the nonces are part of the message signed).
>>
>>
>> https://github.com/discreetlogcontracts/dlcspecs/blob/master/Oracle.md#version-0-oracle_announcement
>> (where the nonces are in the event).
>>
>> That said, it is likely worth mentioning in resources describing the
>> process (such as the paper if it does not already).
>>
>> Best,
>> Nadav
>>
>> On Mon, Mar 1, 2021 at 8:52 PM Jesse Posner <jesse.posner at gmail.com>
>> wrote:
>>
>>> Hi Nadav
>>>
>>> If the forger can influence the oracle announcement such that the
>>> forger's R is used as the pre-commitment (e.g. attacker takes control of an
>>> oracle's communication channels but isn't able to gain access to their
>>> signing key), then I think there's still a forgery risk. I agree that a
>>> proof-of-knowledge of R would prevent the attack. Thanks for the link to
>>> the paper, looks very helpful, I will review it and see how it might
>>> address this issue.
>>>
>>> All the best,
>>>
>>> Jesse
>>>
>>> On Mon, Mar 1, 2021 at 5:02 PM Nadav Kohen <nadavk25 at gmail.com> wrote:
>>>
>>>> Hey Jesse,
>>>>
>>>> I think the crux is that R is already committed to in the oracle
>>>> announcement and is used in the construction of DLCs so that we don't run
>>>> the risk of forgery as the forger must use the pre-committed R. Have you
>>>> had a chance to look at
>>>> https://github.com/LLFourn/dlc-sec/blob/master/main.pdf ? It was a fun
>>>> read :)
>>>>
>>>> Also in case this is relevant, we will likely be requiring proofs of
>>>> knowledge on the pre-committed Rs in the oracle announcements as it is
>>>> required for the security of the multi-oracle scheme if I understand
>>>> correctly (and I believe Lloyd is working on formalizing that).
>>>>
>>>> Best,
>>>> Nadav
>>>>
>>>> On Mon, Mar 1, 2021 at 4:48 PM Jesse Posner via dlc-dev <
>>>> dlc-dev at mailmanlists.org> wrote:
>>>>
>>>>> Hi Lloyd,
>>>>>
>>>>> If I'm understanding the scheme correctly, I think there might be a
>>>>> forgery issue.
>>>>>
>>>>> When c_i is the result of a hash function that includes R, then R is
>>>>> committed to prior to the computation of s. If c_i = i then this is no
>>>>> longer the case. This would allow the oracle to produce a valid s for c_i
>>>>> without knowledge of x. To do this, the oracle first chooses a random
>>>>> scalar s prior to computing R. Then the oracle computes R = (s * G) - (c_i
>>>>> * X).
>>>>>
>>>>> This will only work for a single event (e.g. c_i = 2) that relates to
>>>>> R. However, it seems like the anticipation scheme should have the security
>>>>> property that s is a proof of knowledge of x for all c_i.
>>>>>
>>>>> All the best,
>>>>>
>>>>> Jesse
>>>>>
>>>>>
>>>>>
>>>>> 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
>>>>>
>>>>
>> 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/20210302/64b640e2/attachment.htm>