[dlc-dev] Scaleable Multi-Oracle Idea

[Nadav Kohen]

A shorter explanation of how OR points are used to improve scaling:

Rather than having a new oracle in the two secondary prefix case requiring
(written recursively)

(new_oracle_left + all_others_agree) | (new_oracle_right + all_others_agree)

it is now just

(new_oracle_left | new_oracle_right) + all_others_agree

which scales linearly instead of exponentially as only a single
(tail-)recursive call is required rather than two calls.

If it turns out that simple DLog VEnc isn't too bad then it might be more
practical than what we currently do and if it is simple then it likely
admits a shamir threshold variant which would lead to actual linear scaling
of the whole thing in place of the current exponential scheme (noting that
even without threshold encryption it would still vastly improve things by
making at least double the current limits practical).

-Nadav

On Fri, Mar 19, 2021 at 12:43 AM Nadav Kohen <nadavk25 at gmail.com> wrote:

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