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

[Lloyd Fournier]

 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/20201229/0f113d75/attachment.htm>