Approval Voting Rewards

[eskimor]

More details here.

[burdges]

I've done some analysis in https://hackmd.io/@rgbPIkIdTwSICPuAq67Jbw/S1fHcvXSF which lands on the median based UDP variant, but it's still lacking (a) discussion of why state channels look heaver, and (b) the median based TCP variant.

[eskimor]

Related idea, which might be complimentary or even a replacement: PVF lottery. @burdges could you fill in some details on how this would actually work:

1. Which VRF would be used how?
2. How do we ensure that validators need to actually execute the PVF with the PoV to determine whether they won or not?

[burdges]

Any lottery needs a safe-ish randomness source, like relay chain VRFs at inclusion times, but inclusion could be delayed by not including some availability votes, which permits bias and gaming the rewards. We'd need this game to pay worse than whatever we pay for including one availability vote, which sounds impossible.

[ordian]

I would really prefer a design where we don't put nˆ2 messages on-chain, even if once per session. I am not sure what is the current allocation limit in one-go, but it could break among other things like being overweight. Would putting them into DA with a commitment on chain work as well? We would need to prove a median computation given commitment to the data somehow, but that should be solvable.

[burdges]

Ain't clear availability helps, but we've various options in general.

If you first compute a median off chain, then you can prove it on-chain cheaply. It'd need this n^2 storage somewhere though, and you still put the votes into blocks. You'd need a penalty for wasting our time if the proposed median being proven winds up incorrect.

We could've folks vote upon the hashes of their median list, which avoids the penalties. I'd first envisioned some related protocols where you lose era points if you miss some gossip messages, but I think just voting on hashes works, or else nobody gets paid and governance solves it.

If scores are coarser grained, then scores could be collected more easily by exploiting that almost everyone votes alike. In fact, scores could perhaps be +/- from some statistic across validators, perhaps subjective. We'd want to check the failure modes of the first and how the second biased counting.

Approximation might be manipulable too https://arxiv.org/pdf/1902.04023.pdf

[burdges]

I'll spell out the vote-on-hashes protocol in details:

1. All validators gossip their assessments of everyone but themselves, which they hide for tit-for-tat.
2. All validators compute the median of everyone's assessments.
3. All validators compute the merkle tree of their median computations, and sign its hash.
4. If more than half sign the same hash, then that median list gets posted on-chain.
5. If fewer than half sign the same hash, then no rewards this era. In principle, governance hands out rewards manually whenever we fix the bug, but the bug is likely due to gossip failure due to network conditions, so probably no rewards.