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

[Lloyd Fournier]

Hey Nadav,

I am fairly certain I understand what you are after. Unfortunately I am
just as certain that no such thing can be constructed efficiently using a
simple prime order group.

A scheme that lets you take a secret key and derive other secret keys
"below" it is called a *key regression scheme* [1]. These are also very
related to the idea of *constrained pseudorandom functions [2].* The one
that is close to what you are looking for is in [3] which demonstrates a
PRF with range constrained keys. Unfortunately, I have not come across a
constrained PRF that lets you get an image of the outputs you are not able
to evaluate it for -- at least not in a prime order group. It may be
possible to construct something like that with richer primitives like
pairings but I am doubtful you can do it with secp256k1.

[1] https://eprint.iacr.org/2005/303.pdf
[2] https://eprint.iacr.org/2013/352.pdf
[3] https://eprint.iacr.org/2013/379.pdf

Cheers,

LL



On Thu, 11 Feb 2021 at 21:20, Nadav Kohen via dlc-dev <
dlc-dev at mailmanlists.org> wrote:

> 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
>>>
>>
> dlc-dev mailing list
> dlc-dev at mailmanlists.org
> https://mailmanlists.org/mailman/listinfo/dlc-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/mailman/private/dlc-dev/attachments/20210212/579c29fa/attachment.htm>