I was actually just about to dive into the new publication – it was featured in last week’s Research Pulse (a curation of the top papers posted that week).
Appreciate the mention, thank you.
URE also seems to be highly complementary to strategies that decrease the profitability of Sandwich Attacks, whereby a single swap is split into many using a relatively straigtforward algorithm. Is this something you have considered in URE’s design?
Yes, in fact, for the worst case input trades, such as the “threshold” batch (T, 1, \ldots, 1) \in \mathbb{R}^T, you have to split up trades to preserve any notion of privacy. The main improvement of this paper is that we construct a combinatorial object that coarsely measures “how much” you need to split the big tree to a) preserve privacy while b) not causing too much impact. This trade-off between cost of privacy vs. excess price impact (e.g. a loss felt by users) is a natural way to formulate MEV. The analysis in the paper provides a formal way to measure this cost for any CFMM that has non-zero curvature (e.g. isn’t constant sum).
Another thing to note is that we split trades in a different manner than the paper you cited. Instead of deterministically splitting them, we sample a splitting from a Dirichlet distribution. Recall, that a Dirichlet distribution of dimension d is a distribution on the probability simplex \mathcal{P}^d = \{ x \in \mathbb{R}^d : \sum_i x_i = 1\;\; \forall i \, x_i \geq 0\}. We take a trade of size T and split it into d trades of size T\pi_i for \pi \in \mathcal{P}^d. We choose the parameter of the Dirichlet distribution such that the sizes of the trades are close but (crucially) not predictable. Recent work has shown how to differentially privately sample Dirichlet distributions (e.g. so that an adversary can’t perfectly guess the parameter — which would lead to grinding attacks).
How would you implement this in practice? If you have a layer 1 that provides randomness from consensus (as a VRF or VDF) to smart contracts, one can sample a) a random permutation and b) a Dirichlet distribution to get a splitting and ordering that guarantee (\epsilon, \delta)-differential privacy