Lower bandwidth relays don't receive their fair share due to Bitcoin's dust limit

[DonnchaC]

The current implementation of donation splitting is simple but crude and has some issues.

A maximum transaction fee is calculated in advance depending on the number of relays which have been selected to receive a donation. The donation minus the transaction fee is then divided amongst each relay according to their consensus weight until a relay's share is below the bitcoin dust limit (the minimum value of an output to be accepted as standard transactions on the blockchain. For reference the dust limit is currently about $0.03). All of these below dust limit shares are then redistributed amongst the larger relays.

The Problem

In effect, the current implementation means that as the number of relays increases, smaller relays will only receive their respective donation share for relatively large donations, whereas higher bandwidth relays will retrieve their share of every donation.

The Proposal

I'm planning to implement a proposal by @joepie91 which aims to distribute the donations in a eventually fair way but I am very open to better suggestions or criticism. @joepie91's proposal has the advantage of being stateless which reduces much of the potential difficulty around dealing with relay churn.

The simple proposal is to distribute the sum of all the below dust limit shares by means of a (consensus) weighted lottery, The sum of all below dust limit shares would be split into dust limit valued outputs and sent to a subset of the below dust limit relays. As the selection would be weighted by consensus weight, after a sufficient number of donations each relay, no matter how small should receive their fair share of donations, working around bitcoin's dust limit limitation.

If anyone can see a problem with that proposal, or can suggest something better I'd be delighted to hear it! Please let me know.

[eragmus]

Clever solution; has it been implemented already?