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

[Jesse Posner]

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
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/mailman/private/dlc-dev/attachments/20210301/3e657c0f/attachment.htm>