Numeric multi-oracle support for non-equal num_digits

[nkohen]

This is part of the v0 Milestone.

I've been thinking about how best to handle multi-oracle numeric adaptor point construction in the case where oracles have different num_digits and here's what I've come up with:

Setup: m oracles for the same event have num_digits of n_0, n_0 + n_1, n_0 + n_2, ..., n_0 + n_{m-1} (that is to say, n_0 is the minimum num_digits and for i>0, n_i is how many more digits that oracle has from the minimum.

I have decided that the actual contract (in the contract descriptor) will only support num_digits = n_0 as no outcomes beyond this can truly support a t-of-m security scheme (treating the oracle with n_0 digits' 2^{n_0} - 1 as agreement can lead to less than m-t oracles being malicious and changing the outcome of the DLC). As such any mention below of constructing adaptor points for outcomes greater than 2^{n_0} - 1 should be understood to have the same payout as the maximal 2^{n_0} - 1 outcome.

1. Run the usual multi-oracle numeric algorithm on each group of t oracles where if n_k is the minimum num_digits in this group of t, then we run on the outcomes [0, 2^{n_k} - 2] using num_digits = n_k + 1 and dropping right cover digit prefixes for outcomes greater than 2^{n_k} - 1 for oracles with n_k digits. (Note that we run the algorithm with n_k + 1 so that the correct right cover digit prefixes are constructed for oracles with num_digits > n_k).
2. Pick the highest preferred oracle with n_k digits and use them as the preferred oracle for the 2^{n_k} - 1 outcome, constructing left cover digit prefixes as usual but using the set of right digit prefixes: 00...001_..., 00...01__..., 00...1___..., ..., 01_...____..., 1_...____... where the lengths of these digit prefixes for oracle with n_k + x_i digits are x_i, x_i - 1, x_i - 2, ..., 2, and 1.

Possible modification for step 2: The algorithm as stated requires x_1*x_2*...*x_{t-1} adaptor points and corresponding adaptor signatures (where any x_i=0 are omitted from the product) to right-cover the maximal case. For many oracles (or oracles with very large num_digits such as if n_0 = 10 but all other oracles have num_digits = 30), this can be a very significant amount much of which is used to cover cases when some oracles are attesting to very large outcomes that are considered nearly impossible (this is a reasonable assumption because n_0 is a num_digits acceptable to the user). As such, it may be useful to introduce a new parameter, n_max which makes it so that the first n_i - n_max digits are ignored entirely by the algorithm (possibly resulting in refund cases if oracles are attesting to outcomes greater than 2^{n_max} - 1). This creates an upper bound on the number of adaptor points needed to cover the maximal case which is (n_max - n_0)^{t-1} which can be made very manageable to avoid a new dominant source of asymptotic growth in adaptor signatures required.

Feedback would be appreciated before this is added to the specifications!

[nkohen]

One thought I just remembered: the 00...01_..._ prefixes could just be replaced with __..._1_...__ and this might be better for computation purposes (and for making n_max even less likely to be a problem). The reason I omitted this from the above proposal is using the 0-prefixed version makes it so that everything is still a digit prefix which might simplify code quite a bit as we won't have to worry about these new kinds of outcomes which aren't digit prefix-based, but I'm open to using this if we think we should.

[Tibo-lg]

I’m not really convinced with your first solution, because what happens if you have one oracle with n digits, one with n + 1, another with n + 2? Tbh I might not have understood fully your algorithm but it feels to me like it would become rather complex. I quite prefer the solution using n_max (which I guess should be set to the smallest n?). Though maybe instead of doing refund for cases above, we maybe could do something like:

• For all oracles with nb_digits > n, create adaptor sigs for all possible outcomes in that range.
• Do the same for n + 1, n + 2...
  Though skip the ones where no oracles has the number of digits (so if no oracle has nb_digits = n + 2 then just skip that and move to n + 3 covering the range between n + 1 and n + 3).
  Also stop once you have less oracles than required threshold.

I think that should result in quite a small number of extra adaptor signatures. There is still more chances of refunds than with you first solution, but still a bit less than if we just ignore everything above nb_digits = n. One criticism I guess could be that the acceptable difference requirements can be violated, but as it happens in a range that is not thought to be reached by the user (as you mentioned) I think it's ok.

I'm not sure I'm being very clear but hopefully you'll get the idea.