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

[Jesse Posner]

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