Algorithm improvement

[ichorid]

The algorithms we use for detecting outliers in the stream of transaction-related events and building the reputation score are simplistic and insufficient for the role. We should do a small research on state-of-the-art to improve.

Related links: https://github.com/tdunning/t-digest https://github.com/marlinprotocol/mev-inspect-py

[grimadas]

Updates on the algorithm design.

We have two metrics that we can measure each having different confidence level.

Given the total number of transactions finalised by the miner/validator - NT

1. Violations. For that we need to record and report the total number of violations (NV). Relative violations (RV) = NV/ NT.
2. Outliers. Specifically we are interested only in extremely fast transactions, which are in top quantile compared to all other transactions. Calculate number of such outliers - NO. We can use RO = NO / NT.

Finally, the miner/validator who has produced many blocks and finalised many transactions should have higher score than miners/validators who only create few blocks. For that we introduce miner productivity coefficient comparing. This coefficient shows how the miner compares against the top finalising miner.

$c_i = \frac{NTi}{max{j \in N}(NT_j)}$ - the relative number of transaction processed by the miner against the maximum.

We use this coefficient with a sigmoid function to introduce a decay to the miner $i$:

$d_i\ =\ \frac{1}{1+e^{-12\left(c_i-0.4\right)}}$

Two metrics on outliers and violations can/should be reported in the dashboard: RO + NO, RV + NV.

Finally, the miner score is calculated as:

$score_i = (0.8 RO_i + 0.2 RV_i) * d_i$

Time aspect

Taking into account only last $k$ blocks will introduce a natural time decay if required. A miner who had violations in the past will be thus redeemed.

[ichorid]

Seems like a reasonable alternative that is relatively easy to understand and explain. Though, we should dig into the literature for fraud-resistant reputation function more in the future.

[ichorid]

Done