Hey! Really sweet proposal!
I like the simplicity and I think the numbers are pretty good as well (and could potentially get even better). I also like the overhead balance of the width=2048 and swaps=31 combo.
Some thoughts on the scheme:
Anonymity set analysis
While the numbers on the Simulation Results table look reasonable, we should also take into account the potential for malicious and offline validators, as well as the fact that the total number of validators corresponds to a smaller number of P2P nodes.
I hence modded your simulation script to support offline validators: I’m attaching a table (like yours above) but just for the width=2048/swaps=31 configuration with various percentages of offline shufflers, while also estimating the number of nodes that correspond to that anonymity set (using a 20%-80% Pareto distribution).
| Validators | Nodes | |
|---|---|---|
| Offline == 0% | 193 | 130 |
| Offline == 5% | 180 | 122 |
| Offline == 10% | 169 | 116 |
| Offline == 15% | 156 | 109 |
| Offline == 20% | 149 | 104 |
| Offline == 25% | 139 | 98 |
| Offline == 30% | 138 | 98 |
| Offline == 35% | 133 | 95 |
| Offline == 40% | 128 | 91 |
From the above we see that even with significant offline percentages, there is still some anonymity set provided by this scheme
Strengthening the scheme using a shuffle list
If the anonymity set provided by this scheme is not satisfactory to us, we can strengthen it by separating the list that gets shuffled and the list where proposers get chosen from. That brings us slightly closer to the Whisk design, without Whisk’s cryptography.
For example, we would still use blinded_commitments for shuffling, but after 2048 slots have passed we would copy blinded_commitments into another list shuffled_commitments and we would pop proposers out of shuffled_commitments (either FIFO or randomized).
This approach allows the maximum amount of shuffles to go through before any index gets chosen as the proposer, and based on some sloppy analysis it quickly converges to optimal results for any reasonable width/swaps combo.
The drawback is that we will need consensus code that moves the commitments between the two lists, and we will also need double the BeaconState space.
Adversarial analysis
The next step in the security analysis here would be to think of what kind of attacks an adversary could pull off in this setup.
For example, if an adversary controls 10% of the validators, not only she controls 10% of the shuffles, but she can also void another 10% of the shuffles since any 2-shuffle that includes the attacker’s commitment is basically transparent to the attacker (she knows where her token went, and hence also the other token).
I’m also curious about backtracking attacks: When Alice proposes, the adversary immediately learns some paths of her shuffle-tree; since there is only a limited number of 2-shuffle paths that her token could have taken to end up where it did. An adversary could potentially use that knowledge to get bits of information about other future proposers.
There is also various types of RANDAO attacks that could happen in get_swap_positions().
Cheers!