[dlc-dev] Scaleable Multi-Oracle Idea

[Nadav Kohen]

Hi all,

For those who don't know, the current proposal for multi-oracle support in
dlcs (https://github.com/discreetlogcontracts/dlcspecs/pull/128)
essentially specifies t-of-t support wherein a single primary oracle has a
digit prefix and then the interval corresponding to this prefix is covered
(with some buffer on either side as required) by one or two secondary digit
prefixes which constitute agreement. In the case that only one secondary
prefix is needed, there is no scaling issue and all aggregate points of
secondary oracles for that prefix are added to the primary aggregate point.
However, in the case of two (or more if one was to require better error
precision) prefixes there is an exponential (in the number of oracles)
number of points and corresponding signatures needed. This is because if
one oracle's attestation falls under the first prefix and another under the
second prefix then this still constitutes agreement with the primary
oracle, and as such, all 2^(t-1) adaptor points need to be constructed.

Furthermore, in the case that there is only one secondary prefix needed to
cover the primary prefix, then one could imagine using some kind of
threshold verifiable encryption (in place of the current singular adaptor
signatures) where-by a single threshold adaptor signature could be used to
enforce all agreement cases for a given primary digit prefix. Note that
currently (n Choose t) such signatures are required because the t-of-t
construction is applied that many times with each of the (n Choose t)
combinations of oracles.

*All of this to say, wouldn't it be nice if it were always the case that a
single secondary adaptor point fully represented agreement with a primary
adaptor point?*

It just so happens that similar things have been thought about over in
PTLC-land with regard to "taking the OR" of two points, which in this case
may be applicable so that if there are two (or more) points for a given
oracle representing agreement with another, then these points may be
combined into a single "agreement point" and such can also be done with all
of the other oracles so as to reduce all constructions to the nice case
where a single point from each oracle can be used to represent agreement
with the primary oracle.

Thus, as a high level illustration, rather than having to describe
agreement of t-1 secondary oracles with the primary oracle as 2^(t-1)
distinct adaptor points and corresponding adaptor signatures where adding a
new oracle means double the number of signatures needed for a case, we
could instead take the two digit prefixes constituting agreement and OR
them together to get a single point which can then be added to the other
oracles' OR points leading to no multiplier.

I am very open to any way of doing such "ORing" but the current best
proposal I am aware of is to use verifiable discrete log encryption. That
is to say, If I have two points P1 and P2 and I wish to construct a point X
such that the scalar to X (i.e. x such that X = x*G) will become known only
if either the scalar to P1 or P2 is known, then I can construct a random
key pair (x, X) and verifiably encrypt x (the discrete log of X) twice,
using P1 and P2 respectively as encryption keys: c1 = VEnc(x, P1), c2 =
VEnc(x, P2). Should either the scalar to P1 or P2 be discovered by my
counter-party, then x can be recovered by decrypting either c1 or c2. As
such, the point X can be used semantically by my counter-party to represent
P1 OR P2.

For our specific use case, a threshold verifiable encryption scheme would
be optimal (where n keys are needed to encrypt but only t <= n are needed
to decrypt) as this would remove both the 2^(t-1) (and bases greater than 2
in schemes with more precision) and the (n Choose t) exponential growth
factors! If such a verifiable encryption scheme existed and was practical
(i.e. fast enough), then I believe that adding new oracles to a numeric
outcome with differences allowed DLC would create reasonable linear or
quadratic growth in place of the current scheme which has multiple
exponential growth factors in the number of oracles.

Aside from just getting this idea out there, I was also curious if anyone
is aware of any potential practical proposals for Verifiable Encryption of
Discrete Logarithms? It would be awesome to attempt a proof of concept for
the algorithm and do some analysis and running of numbers to see if this is
a viable future path for multi-oracle DLCs.

Best,
Nadav
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/mailman/private/dlc-dev/attachments/20210319/03481ee7/attachment.htm>