Research Which Exponent Library is Safest and Cheapest

andytudhope commented 5 years ago

The next step in writing this contract is to swap out all the current mathematical operations for safer ones that actually work in Solidity.

The core piece of work here is to figure out the best and cheapest way to calculate v_minted = d.available ** (1/d.rate) given that there is no floating point arithmetic in Solidity. A fractional exponent is the equivalent of a square root, so we need a gas-efficient library that will help us achieve this. Look into

https://github.com/dydxprotocol/protocol/blob/master/contracts/lib/Exponent.sol

and

https://github.com/extraterrestrial-tech/fixidity

to see which one is cheaper, as well as looking for other alternatives. Bancor has an interesting approach too: https://github.com/bogatyy/bancor/blob/master/solidity/BancorFormula.sol#L270 but I suspect that, because our exponent is dynamic, using a static table is not going to be the solution here.

Other Resources

Babylonian method: https://ethereum.stackexchange.com/questions/2910/can-i-square-root-in-solidity

Taylor Series: https://en.wikipedia.org/wiki/Taylor_series

Newton-Raphson: https://ethereum.stackexchange.com/questions/38468/calculate-the-nth-root-of-an-arbitrary-uint-using-solidity?rq=1

Easter Egg: https://en.wikipedia.org/wiki/Fast_inverse_square_root

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

This issue now has a funding of 320.0 DAI (320.0 USD @ $1.0/DAI) attached to it.

If you would like to work on this issue you can 'start work' on the Gitcoin Issue Details page.
- Want to chip in? Add your own contribution here.
- Questions? Checkout Gitcoin Help or the Gitcoin Slack
- $41,222.22 more funded OSS Work available on the Gitcoin Issue Explorer

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Cancelled

Workers have applied to start work.

These users each claimed they can complete the work by 3 weeks, 6 days ago. Please review their action plans below:

1) benschza has applied to start work _(Funders only: approve worker | reject worker)_.

Having recently looked at the Babylonian method and Bakhshali method for calculating square roots, I believe I have the right context to get started on this problem! There will be some shared value too, because the results of these tests will determine which method we should use in our bonding curve implementation.

Initial questions:

Can we assume a decimal scaling of 18 points (Eth/Wei default) to handle floating point arithmetic? (for the variables in the equation)
To what precision, in decimal places, does the result need to be?

Learn more on the Gitcoin Issue Details page.

andytudhope commented 5 years ago

Hey @benschza - @nanspro gets precedent as we have worked with him before.

But obviously, I back you hard to also produce some interesting results here, especially if you're coding to SAfrican Jazz, so will payout the same bounty to you if you also work on this and submit some tests and an efficient implementation as described above.

Yes, assume decimal scaling of 18 points.
Not exactly sure, but I would guess that 8-12 places would be more than enough. What I want to understand there is what effect on gas costs being more precise has, if any.

FWIW, I reckon this is the best bet from the links above: https://github.com/extraterrestrial-tech/fixidity/blob/master/contracts/ExponentLib.sol#L40 for what we need, but would love to see some other methods and compare gas costs if possible.

BenSchZA commented 5 years ago

Thanks for the vote of confidence @andytudhope! What else does one code to, but SA Jazz? If capacity allows I'll see what results I can produce within the allocated time.

gitcoinbot commented 5 years ago

@nanspro Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

@nanspro Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

[x] reminder (3 days)
[ ] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

bakasura980 commented 5 years ago

Hey @andytudhope , I don't know if this will help you, but here is the story :D Two weeks ago our team had a task to implement a SQRT functionality in Solidity. Because there is not floating points, the division returned only the whole part. So we decided to give a change to Vyper-Solidity communication in order to solve the SQRT.

In the end we have implemented two SQRT algorithms: 1) https://github.com/LimeChain/bonding_mathematics/blob/master/contracts/Math/SQRT.py 2) https://github.com/LimeChain/bonding_mathematics/blob/master/contracts/Math/SQRT_HFP.py

The first one is the standard Newton's method. This method use division in order to get the fraction approximation. Here we had a problem -> Vyper has decimals, but the fraction is rounded to 10th symbol. That is why we implemented another more unknown-algorithm

The second algorithm is from: http://www.afjarvis.staff.shef.ac.uk/maths/jarvisspec02.pdf This algorithm finds the SQRT digit by digit. With this in mind we can tell what length of fraction part we want.

If you need to have a high SQRT precision use the second method.

Both methods: We are returning to Solidity uint256(number with 18 symbols) which in case of tokens perfectly works for us.

Example Result: First method -> sqrt(2) -> 1414213562300000000000 Second method -> sqrt_hfp(2, 18) -> 1414213562373095048

I hope this will be useful for you. :)

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@nanspro due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

[x] reminder (3 days)
[x] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

@nanspro due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

[x] reminder (3 days)
[x] escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

andytudhope commented 5 years ago

Hey @nanspro @BenSchZA - any progress on this issue?

BenSchZA commented 5 years ago

Hi @andytudhope. I started creating a Jupyter notebook to test the efficiency of some of the nth root algorithms. Decided to take this approach because Python has great tools for testing a visualizing efficiency. Haven't had as much time as I'd have liked to work on this in my own time, but happy to share it and work on it further.

andytudhope commented 5 years ago

Yeah, please do share it when you're happy to! Am sure it'd help not only me, but also the one and only @bakasura980 ❤️

BenSchZA commented 5 years ago

@andytudhope I just came across this comparison for 4 nth root algorithms implemented in CPP - assuming they can be converted to work with Solidity and its float limitations, it might be useful: https://www.boost.org/doc/libs/1_69_0/libs/math/doc/html/math_toolkit/root_comparison/root_n_comparison.html ~ The Newton-Raphson method seems to come out top in terms of execution time, how that translates to Solidity gas use will need to be tested :)

bakasura980 commented 5 years ago

@andytudhope what do you need ? nth root algorithm or SQRT algorithm, I got confused 😅. If SQRT will work for you, I could make a comparison between Newton and SQRT_HFP algorithms and provide you strengths, weaknesses, gas cost and etc. ?

andytudhope commented 5 years ago

It's nth root that we really need, as the calculation is available ^ (1/rate), and the rate varies as a function of the SNT staked, i.e. balance.

collincusce commented 5 years ago

Given that these are all Counting Numbers, I'm assuming you're ok with approximations? Can we bound in integer space rather than unint?

BenSchZA commented 5 years ago

Will post my brain-dump of a Jupyter Notebook later today. Nth root is looking pretty inefficient, depending on the range of n. @andytudhope Do you have some known limits for available and rate?

andytudhope commented 5 years ago

0 < rate < 1, but with a good deal of decimal precision required (the more the better).

0 < available < max is probably the safest bet there.

nanspro commented 5 years ago

Hey @andytudhope sorry for the inactivity but i was very busy with college work and other intern commitments, I think @BenSchZA has already done a lot of work here and will probably finish this so no point of me jumping on this now. I am stopping work on this. Really sorry for the inconvenience!

BenSchZA commented 5 years ago

@andytudhope Can I assume you meant 0 < 1/d.rate < 1? Or 0 < rate < max?

andytudhope commented 5 years ago

@BenSchZA no, what I wrote is correct. The rate is some number between 0 and 1, which means 1/d.rate ranges from 1 to basically infinity... But that's OK, right, because the numerator is all we're interested in for nth root, no? i.e. x^(1/3) == cubed root (x), so the same goes here, except the root we're interested in lies somewhere between 0 and 1, with a high degree of decimal precision... I've added a rate_proof array to the bottom of this observable notebook for you to help.

available is the amount of SNT staked that is available to vote with, so it must always be strictly less than the total SNT you can stake. No maths on that one, just logic.

@nanspro no problem brother, thanks for letting me know and good luck with all that work 👍

BenSchZA commented 5 years ago

@andytudhope

If the exponent is not a fraction, which exponent = 1/rate where 0 < rate < 1 is not, then it becomes a power problem, rather than an nth root problem.

So could you not scale all values by a set number of decimal points, such as the usual default of 1e18, and perform a power calculation? And then you'd scale back on the other side, assuming the result is not a float - but there are other libraries and ways to deal with floats. I'm possibly missing something though :slightly_smiling_face:

    function power_calculation() public pure returns (uint256 result) {
        uint256 decimals = 1e18;
        uint256 rate = 0.5*1e18;
        uint256 available = 100*decimals;

        return available**(decimals/rate);
    }

BenSchZA commented 5 years ago

The description definitely says exponent problem, I think I just led myself astray with the mention of nth root :+1:

andytudhope commented 5 years ago

Yeah, I know it's really an exponent problem (hence the shape of the curve and "the genius" of the whole game setup), but here's the issue. If we take your line of thinking:

    function createDApp(_from, _id, _amount) public {
        d.balance = _amount;
        uint256 decimals = 1e18;
        d.rate = (1 - (d.balance/max)) * decimals;         <--- high decimal precision, pref 10-18 points
        d.available = (d.balance * d.rate) / decimals;         <--- high decimal precision, pref 10-18 points
        uint256 exponent = decimals/rate;
        // It's this exponent which is really the issue. Here, Solidity would go back to
        // the nearest uint, but we need good decimal accuracy for what is essentially
        // 1/rate, which this doesn't give.
        d.votes_minted = d.available ** (exponent);
    }

If I'm wrong about how accurate we can be, let's just go with something similar to the above and write tests to check the sh*t out of ourselves.

andytudhope commented 5 years ago

Of course, I can almost get there in vyper (cc @bakasura980), like

    dapp.dappBalance: int128 = _amount
    decimals: int128 = 10 ** 18
    dapp.rate: int128 = (1 - (dapp.dappBalance / self.maxStake)) * decimals
    dapp.available: int128 = (dapp.dappBalance * dapp.rate) / decimals
    exponent: decimal = decimals / rate
    dapp.votes_minted: int128 = dapp.available ** (exponent)

but one does not implicitly convert decimal types into int128 types so easily and I really need good decimal accuracy for this to work 😞 Hence my continued issues here... The funny thing, of course, is that it works simply on the web in a JS notebook, but not in "smart" contracts 😂

andytudhope commented 5 years ago

@BenSchZA - I have been trying to wrap my head around the latest BancorFormula, as I think the solution may lie in there... Care to try help on that front? https://github.com/andytudhope/Recollections/commit/326ac60e13df55e4e326005ef8d9abff0271f2f3

BenSchZA commented 5 years ago

That does look promising (and dense). I'll take a look! Any specific issues/progress on that front yet?

andytudhope commented 5 years ago

Yeah, take a look here for all progress from here on out 👍

https://github.com/status-im/discover-dapps/tree/embark

gitcoinbot commented 5 years ago

Issue Status: 1. Open 2. Cancelled

The funding of 320.0 DAI (320.0 USD @ $1.0/DAI) attached to this issue has been cancelled by the bounty submitter

Questions? Checkout Gitcoin Help or the Gitcoin Slack
$57,761.47 more funded OSS Work available on the Gitcoin Issue Explorer

andytudhope / Recollections

Research Which Exponent Library is Safest and Cheapest #4

Other Resources