[dlc-dev] New oracle signing mode optimized for multi-oracle DLCs

Nadav Kohen nadavk25 at gmail.com
Thu Feb 11 11:18:43 CET 2021


Nevermind, public hardened derivation isn't a thing, this is still unsolved
(at least I don't know a solution and would love to hear if anyone else
does)

On Thu, Feb 11, 2021 at 4:01 AM Nadav Kohen <nadavk25 at gmail.com> wrote:

> I may be wrong here but if I understand BIP 32 correctly, I think that I
> can just use a simple hardened derivation path to solve this problem, where
> *next* is hardened derivation on the extended private key, and
> *next_point* is the corresponding public version of the derivation. If I
> understand correctly this should mean all points can be computed from the
> root extended public key P_0 and that from x_i, andy x_j with j > i can be
> derived but not for j<i.
>
> -Nadav
>
> On Thu, Feb 11, 2021 at 3:31 AM Nadav Kohen <nadavk25 at gmail.com> wrote:
>
>> Hi all,
>>
>> Me from the future here: Wow this email is long and mostly not worth
>> reading, I have one important question at the very bottom of the email
>> (where the *bold* text starts) and everything else is just context and
>> motivation for a purely cryptographic question. Feel free to skip ahead to
>> that :)
>>
>> ----------------------------
>>
>> In the current multi-oracle CET model, one computes the single-oracle CET
>> sets and then for each CET in that set, corresponding to an outcome in some
>> interval [a, b], one computes a (minimal) set of secondary CETs
>> corresponding to some interval [a-x, b+y] where both x and y are between
>> the minSupport and maxError parameters.
>>
>> ---------------- Skip this section if you want to get to the new stuff
>> ----------------
>>
>> I have recently been trying to see if I can reliably make these secondary
>> sets have only a single CET, meaning that numeric outcomes with bounded
>> differences allowed can scale (in CET terms) just as well as enumerated
>> outcomes.
>>
>> The original thinking was to split into cases where sometimes we can just
>> "ignore some digits" to get a single secondary CET that satisfies our
>> needs, but if the primary CET it is too close to a multiple of maxError
>> (where close means within minSupport) then a second secondary CET is
>> required to cover the other side of the nearby multiple of maxError.
>>
>> The newer and better thinking is to have oracles sign the same event
>> under multiple bases and then to take intersections of intervals resulting
>> from prefixes in two (possibly different) bases in order to cover [a-x,
>> b+y]. For many parameters (minSupport, maxError, payoutCurve) this performs
>> perfectly pretty reliably (meaning a "match" (intersection) is found
>> satisfying the constraints and resulting in a single secondary CET) but for
>> certain parameters many cases cannot be covered requiring multiple
>> secondary CETs (leading to further exponential growth of CETs in the number
>> of oracles).
>>
>> Another idea I thought might help this is to have oracles sign "shifted
>> versions" of outcomes as well (e.g. sign x + 1000 too) but preliminary
>> experiments don't seem to yield this approach much promise.
>>
>> ---------------- New stuff starts here ----------------
>>
>> My newest idea is that perhaps oracles could partition their outcome
>> domain into nearly equal parts (e.g. [0, 9], [10, 19], [20, 29], ..., [90,
>> 99] for the domain [0, 99]) and then attest to an event begin less than
>> some value (or greater than but everything is symmetrical so I will focus
>> on less than).
>>
>> If oracles were to follow such a protocol for both greater than and less
>> than, then custom intersections could be taken so that covering CETs can be
>> generated between any two partition points so that if maxDiff(p_i, p_(i+1))
>> < maxError - minSupport, then we can guarantee singleton secondary CET sets
>> meaning any scaling solution (exp growth -> linear) applicable to enum
>> outcome multi-oracle will be applicable anywhere.
>>
>> Here is my high-level idea for how to accomplish this. The oracle will
>> generate a single random private key for this example event, x_0, which
>> corresponds to "outcome < 10." Then a deterministic one-way function is
>> used to compute x_1 = next(x_0) which will correspond to "outcome < 20" and
>> so on with x_i+1 = next(x_i) and where x_i means "outcome < (i+1)*10." Now
>> say that the outcome is 35, the oracle will release x_3 from which any user
>> can compute x_i for any i >= 3. Thus they can construct a single CET for
>> the event "i*10 < outcome < j*10" for any i and j.
>>
>> The key complication is that we need a one-way point derivation function
>> P_i = derive_point(x_i) such that there exists a deterministic (doesn't
>> have to be one-way) function such that next_point(P_i) = P_(i+1).
>>
>> *----------------- MY QUESTION IS DOWN HERE
>> -----------------------------------*
>>
>> If such a triple,
>> (*next*: Scalar => Scalar, *derive_point*: Scalar => Point, *next_point*:
>> Point => Point),
>> of deterministic functions were to exist satisfying the properties:
>>
>>    1. *next* is one-way
>>    2. *derive_point* is one-way
>>    3. *next*(x) = y => *next_point*(*derive_point*(x)) = *derive_point*
>>    (y)
>>
>> Then there is a simple algorithm to convert my single-base, single-oracle
>> CET compression solution into an algorithm that supports (still
>> single-base) multiple oracles with bounded differences allowed.
>>
>> Essentially we need a kind of homomorphic encryption where the encryption
>> function (*derive_point*) converts applications of *next* on its domain
>> to applications of *next_point* on its range where we can choose any
>> one-way function *next* and any function *next_point* to make this work.
>>
>> I don't (off the top of my head) know if such a suite of functions,
>> hopefully simple ones, exist and was writing to the mailing list hoping
>> that someone else might have an idea for how this may be accomplished.
>> Anyone have any ideas?
>>
>> Best,
>> Nadav
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/mailman/private/dlc-dev/attachments/20210211/903eeadb/attachment.htm>


More information about the dlc-dev mailing list