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

[Lloyd Fournier]

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/ba6fdcff/attachment.htm>