Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Decomposing quantities into multiple signatures #65

Closed
LLFourn opened this issue Aug 22, 2020 · 10 comments · Fixed by #110
Closed

Decomposing quantities into multiple signatures #65

LLFourn opened this issue Aug 22, 2020 · 10 comments · Fixed by #110

Comments

@LLFourn
Copy link
Contributor

LLFourn commented Aug 22, 2020

In my URI format proposal a point came up about "exponent + mantissa" vs decimal decomposition came up. This deserves it's own discussion I think.

WRT to what @Tibo-lg said:

I considered this as well, but I think the mantissa exponent as described in the original paper is actually better because you only need 2 R-values for any case and you don't have issues of going out of bounds.

I have not done a rigorous investigation into this topic and perhaps it deserves one but in my mind exponent + mantissa is in practice much less efficient for users than decimal decomposition (which is less efficient for Oracles but I think that is ok).

How many possible mantissas should there be for BTC/USDT for example? 1,024? Then every contract has to make a transaction covering all 1,024 mantissas. Covering all possible relevant exponents then may double or triple this number.

Decimal decomposition is having one signature for each digit and having an upper limit on the value e.g. $999,999 for BTC/USDT requires 6 oracle signatures. I claim that this means users have to create far fewer transactions (see the referenced text for an example) and they are simpler from an implementation perspective. Furthermore, they are not lossy (unless the price goes over the threshold) which means you can determine what the exact price was from the signatures up to the digit resolution (rather than an approximation of it).

There is another reason you want full resolution: you want people making a contract a year ago on the price tomorrow and people making a contract today on the price tomorrow to use the same event/oracle signatures. If the price has changed a lot e.g. 10x in the last year then the mantissa will not be covering the lower digits of the actual outcome which may be very relevant to people who are betting on short daily price swings.

I don't think the bounds really differentiates the two schemes except that in one the bounds move exponentially and the other they move linearly. In theory there should be a cap on the exponents too in case the USD or (USDT) goes full Zimbabwe and you need the entire supply of USDT to buy one satoshi!

More than happy to be proven wrong about this.
I think the goal of this issue is for someone to "do the math" and plot this scheme against exponent/mantissa for number of signatures needed by oracles vs number of outcomes users need to cover.

@Tibo-lg
Copy link
Member

Tibo-lg commented Aug 24, 2020

Thanks for raising this. I spent some time thinking and I think I convinced myself that you are right and that decimal composition leads to less transactions to be created in general.

Though just to clarify, I'm not sure I understand what you mean by "how many possible mantissa should there be". In my mind the mantissa is just a decimal number and its length doesn't necessarily need to be capped, which is why I mentioned that you don't have "out-of-bound" issues on the oracle side. Though you are right that it would still require the users to create transaction for as many exponent as they think is necessary, so the issue does not completely disappear.

Also I'm not sure I see a precision issue with mantissa/exponent, but I guess that's related to the reason for having a cap on the length of the mantissa which I'm not sure I get.

Finally just a random thought, but a way to tackle the out of bound issue for the decimal decomposition would be to actually add the exponent to it. For example, the oracle could provide six values for the decomposition, but in addition sign how many numbers are actually used to represent the number (so basically the exponent). Clients can then use this values to cover the case of >$999,999 and also to further reduce the number of transactions that need to be created for values not relevant to their contract (not by a lot though).

@nkohen
Copy link
Contributor

nkohen commented Aug 24, 2020

I'd just like to signal my support for decimal composition over single exponent/mantissa as I believe that the former is orders of magnitude more efficient for users at the cost of a couple extra signatures from oracles. Furthermore I think it is less prone to loss of precision as there can be no ambiguity to what the precision of the number being signed is (due to pre-committed R values) whereas it can be unclear what precision number the mantissa is which would lead to useless oracle signatures

@Tibo-lg Tibo-lg mentioned this issue Aug 24, 2020
@LLFourn
Copy link
Contributor Author

LLFourn commented Sep 1, 2020

Though just to clarify, I'm not sure I understand what you mean by "how many possible mantissa should there be". In my mind the mantissa is just a decimal number and its length doesn't necessarily need to be capped, which is why I mentioned that you don't have "out-of-bound" issues on the oracle side. Though you are right that it would still require the users to create transaction for as many exponent as they think is necessary, so the issue does not completely disappear.

If you are making a contract you need to cover every single possible mantissa so that if the oracle publishes it you have a viable transaction to broadcast? Are you saying the set of mantissas are fixed per exponent?

@Tibo-lg
Copy link
Member

Tibo-lg commented Sep 1, 2020

If you are making a contract you need to cover every single possible mantissa so that if the oracle publishes it you have a viable transaction to broadcast?

I guess in practice that's not possible, but yes I guess you should try to cover as many as you think is necessary.

If you are making a contract you need to cover every single possible mantissa so that if the oracle publishes it you have a viable transaction to broadcast? Are you saying the set of mantissas are fixed per exponent?

That was my thinking indeed. If you have an integer and you use some kind of normalized form for the mantissa, you should be fine. If you have a decimal, you should fix its precision and then the problem boils down to the same as with the integers. But maybe I'm just missing something?

Also what do you think about adding the "size" (there is probably a better term) of the result to the decimal composition? I think it can make it convenient to cover a large number of cases.

@matthewjablack
Copy link
Contributor

Has binary composition been considered?

This will be more efficient than decimal composition

@matthewjablack
Copy link
Contributor

Nevermind, this was already discussed: https://github.com/discreetlogcontracts/dlcspecs/pull/63/files#r475770609

@LLFourn
Copy link
Contributor Author

LLFourn commented Sep 15, 2020

@Tibo-lg

That was my thinking indeed.

Ah. I never considered that. That does make much more sense than my interpretation of the paper. It still seems sub-optimal since for a given exponent you are interested in you still have to consider every possible mantissa.

Also what do you think about adding the "size" (there is probably a better term) of the result to the decimal composition? I think it can make it convenient to cover a large number of cases.

My interpretation of this is: "why don't oracle's sign how many significant digits the outcome has".
This is obviously the same as mantissa and exponent but from the meeting I think you are suggesting to combine this with decimal decomposition.
I think that only saves exactly 9(n - m) signatures for a DLC where n is the number of digits the oracle is signing and m is the number of significant digits in the outcome.

E.g. if bitcoin is 12,500 today and we want to make a 48 hour bounded CFD for 12,000 - 12,999. Let's say the oracle is signing 7 digits. Clearly we are only interested in the last three digits and only where the first four are 0012. To set up this bet we would have to sign an extra 4x9 transactions to settle the CFD at the maximum bound for one of the parties (there are 9 cases where the first digit is not 0 etc and same for the second etc).

By signing the number of significant digits you would only have this down to 1 + 1 + 9 + 9. i.e. if the oracle signs "6 digits" or "7 digits" it means you don't need to sign a transaction for each alternative to the leading 0s.

Do you agree with this analysis? I think if this is all it gives us then it's not worth it.

@matthewjablack

Has binary composition been considered?

This will be more efficient than decimal composition

This is a good question. I chose decimal because humans I likely to make bets around large decimals. e.g. Bets where each increment for each discrete transaction is $100. This allow you to ignore the lower two digits when computing outcome points. If in practice decimal numbers are not relevant then binary is more efficient (at the expense of the oracle announcing more nonces). I think decimal will be more efficient "per nonce" in practice.

@Tibo-lg
Copy link
Member

Tibo-lg commented Sep 15, 2020

Do you agree with this analysis? I think if this is all it gives us then it's not worth it.

My main point for using this approach was to protect against overflows. I added a description here you can have a look, and there is also another nice suggestion from @devrandom in the comments.

The slight gain of efficiency is to me just a nice side effect.

@LLFourn
Copy link
Contributor Author

LLFourn commented Sep 16, 2020

@Tibo-lg Ok I see. From reading the thread there you want to be able to "update" an event with more R values should the number you originally proposed be insufficient. I think what you're saying works and is quite elegant. Is this practical though? If the oracle thinks 5 digits is enough then in your proposal they would commit 6 R values. Then if 5 is insufficient they could add more. But if they just committed to 6 digits instead (and didn't commit to significant digits) they would most likely never have needed to update the event. The advantage of your proposal is limited to cases where there is a several order of magnitude error in what the oracle was anticipating for the range. IMO in the rare case that we have these massive errors I think it is sufficient to announce a new event.

I guess if there is another shitcoin bull run the idea might apply!

@Tibo-lg
Copy link
Member

Tibo-lg commented Sep 16, 2020

Yeah I kept thinking but at the end the best option is probably to create a different event (or I would personally prefer to say "a different version of the event") and as @devrandom mentioned just have the oracle sign the maximum possible that it can in the case of an overflow (as much as I can think adding an extra R for signing an overflow flag actually doesn't really bring anything useful).

@nkohen nkohen mentioned this issue Dec 4, 2020
4 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants