implement exponential decay curve

[pifragile]

This PR introduces a new curve ExponentialDecay in the referenda pallet. For the implementation we rely on Encointer's substrate-fixed, which provides efficient fixed point numbers and implements transcendental functions like exp and log.

Changes at unrelated locations in the code were necessary because substrate-fixed introduces some conflicting impls and we got errors along the lines of type annotations needed multiple impls satisfying usize: PartialOrd<_> found in the following crates: core, substrate_fixed

[cla-bot-2021[bot]]

User @pifragile, please sign the CLA here.

[brenzi]

@shawntabrizi @kianenigma as discussed at parachain summit

full disclosure : I asked @pifragile to implement this PR with two objectives. the indirect one being a tangible demonstration of substrate-fixed because we would very much like to have the substrate-fixed crate included in the substrate/polkadot codebase or parity-common - and have its primitives supported by ecosystem tools like js/apps

On the topic of this PR:

After discussing Gov2 ideas with @joepetrowski, I had the strong feeling that linear curves will not be satisfactory. Non-linear curves for approval and turnout thresholds will be much more powerful and much closer to the behaviour we actually desire.

Of course, piecewise-linear curves are an alternative option, but they offer worse dev experience when setting them up and they naturally come with discontinuities of the first derivative. (Taking the example of bitcoin mining rewards, such discontinuities can cause a lot of unnecessary turbulence).

With this PR, it is possible to define smooth curves with reasonable computational complexity with only few easy-to-understand parameters:

• starting point
• offset
• halving-time (relative to decision period)

If desired, flipping such an exponential decay curve such that it starts at 50% and ends at 100% could even be used to approximate the behavior of previous adaptive quorum biasing. (Let turnout threshold decrease to zero while approval threshold raises towards 100% over time).

[brenzi]

@pifragile please fix the reported CI errors

[kianenigma]

note that I think the first step in this is: https://github.com/paritytech/substrate/issues/12040, and then we can re-export fixed from common or sp-arithmetic.

I am not the best person to judge of the change to the referendum pallet is sensible, but I will have a look.

[stale[bot]]

Hey, is anyone still working on this? Due to the inactivity this issue has been automatically marked as stale. It will be closed if no further activity occurs. Thank you for your contributions.

[brenzi]

Waiting for #12509

[Polkadot-Forum]

This pull request has been mentioned on Polkadot Forum. There might be relevant details there:

https://forum.polkadot.network/t/community-suggestions-and-requests-for-the-opengov-model-on-kusama/1179/6

[Polkadot-Forum]

This pull request has been mentioned on Polkadot Forum. There might be relevant details there:

https://forum.polkadot.network/t/community-suggestions-and-requests-for-the-opengov-model-on-kusama/1179/7

[stale[bot]]

Hey, is anyone still working on this? Due to the inactivity this issue has been automatically marked as stale. It will be closed if no further activity occurs. Thank you for your contributions.

[brenzi]

not sure how to move on, still waiting for https://github.com/paritytech/substrate/pull/12509

[stale[bot]]

Hey, is anyone still working on this? Due to the inactivity this issue has been automatically marked as stale. It will be closed if no further activity occurs. Thank you for your contributions.

[brenzi]

note that I think the first step in this is: #12040, and then we can re-export fixed from common or sp-arithmetic.

I am not the best person to judge of the change to the referendum pallet is sensible, but I will have a look.

As #12040 has been aborted as a won't fix, is there another way to move ahead with substrate-fixed? If not for this PR, it still would be valuable for us to see support in this codebase and I still believe the implementation is more computationally efficient than the current one, but benchmarking that is an effort we can't currently do.