Analysis of Swap-or-Not SSLE proposal


Swap-or-Not is an SSLE technique designed by Buterin. Recall that SSLE aims to select W out of N validators in a fair and uniform way over the course of W shuffles of validators’ commitments, so that only the commitment owner knows his position in the final order.


Swap-or-Not mixes 32 commitments per single stir using only secret swaps (i.e. mixes of 2). First, two positions are determined by a RANDAO call and secret swapped. The RANDAO usage ensures the positions are unknown in advance.

Then they are exchanged with two others, then with 4 others, and so on. The offsets of those positions are determined in the very first RANDAO call.

Therefore each of the first two commitments can end up in any of the 32 positions.

Each tree layer is handled by a different shuffler.

To mix better, trees run in parallel (but we can ignore it)


In order to demonstrate the insecurity of this proposal, we expose some its non-obvious features.

  1. Only the first two commitments’ positions are unknown at the time of the swap. As next layers are stirred by next shufflers, the latter know the positions to be swapped.

  2. Even though the first-touch commitment can end up in any of 32 positions, each output commitment origins from at most 6 input ones!

  1. Every commitment owner can trace its own commitment and effectively destroy all swaps it undergoes.

  2. Moreover, malicious owners can share their traces and kill many swaps.

  3. Malicious shufflers share their swaps and reduce the anonymity even further.

In this picture, only 10 swaps out of 31 survive, whereas we have <0.5 fraction of malicious.

  1. Malicious shufflers can even choose their swap to decrease the overall anonymity. Swapping right would destroy one more swap.

  1. In concrete numbers. For malicious fraction of \frac{1}{2} of shufflers&commitments with N=2^{14}:
  • \frac{1}{2} of swaps are instantly killed
  • \frac{1}{2} of honest commitments undergoing a tree are not secretly swapped.
  • >5 commitments are fully known (no anonymity gain) after the full shuffle.
  • Anonymity further degrades as honest proposers reveal themselves.


  1. Anonymity set for Swap-or-Not outputs is too small.
  2. Malicious shufflers reduce it a lot.
  3. We need way more iterations of it to get security compared to Whisk.

The attack does not work on Whisk

Whisk is an SSLE method, where N=2^{14} commitments are shuffled by M=2^{13} shufflers. Each shuffler makes his own stir of K=128 commitments

and provides a zero-knowledge proof of correctness. Whisk tolerates up to 1/2 corrupted or offline shufflers.

The attack does not apply to Whisk because the Whisk shuffles are much bigger (128 by default) and remain privacy-preserving even if a large fraction of the commitments is corrupt.


Hi khovratovich, i have some questions after reading in your post:
“Moreover, malicious owners can share their traces and kill many swaps.”
I don’t get it, why do malicious shufflers kill swaps by sharing them? In the Buterin’s design, “Size-2 blind-and-swap proves that two output commitments (OL1, OR1), (OL2, OR2) are re-encryptions of two given input commitments (IL1, IR1), (IL2, IR2) , without revealing which is a re-encryption of which”, so, it seems that the shuffler himself can not distinguish in his swap which one was the original commitment before the swap. So please explain why sharing swaps can kill them? Or, share what? the two commitments, or the positions of the two commitments?