I believe that the ring signature scheme achieves this. The sampling is a permutation without repetitions. I call it “perfect fairness” in the original post.
Regarding deposit sizes, my latest (not too strongly held) opinion is that fixed-size deposits beat variable-size deposits:
- Granularity: Multiple fixed-size validators can be ultimately controlled by the same entity. So from the point of view of the freedom to choose the deposit amount, fixed-size deposits allow for variable-size deposits, just with less granularity. For large deposits the added value of greater granularity dies off quickly, and for small deposits the added value is limited by the minimum deposit size.
- Decentralisation: By breaking down large validators into smaller equally sized sub-validators we can increase decentralisation and improve incentive alignment. The reason is we can use cryptographic techniques to force a fixed amount of non-outsourceable non-reusable work per identity. (For example, we may be able to enforce proof-of-storage per identity, or maybe proof-of-work per identity using a proof of sequential work, or maybe proof of custody can help with outsourceability.) I believe the dfinity project is partly taking the fixed-size deposit approach for this reason. One could try to argue that variable-size deposits are good because they allow for batching and pooling, reducing node count, hence reducing overheads at the consensus layer. The potential problem is incentive misalignment, whereby the cost of validation grows “sublinearly” with deposit size.
So all in all I think the ring signature scheme has the right properties: perfect privacy (going beyond private lookahead with private lookbehind), fixed-size deposits, and perfect fairness.