How can we order transactions in a replicated state machine "fairly?" In the model of prior work [2, 8, 9, 13], each of n replicas observes transactions in a different order, and the system aggregates these observed orderings into a single order. We argue that this problem is best viewed through the lens of the classic preference aggregation problem of social choice theory, in which rankings on candidates are aggregated into an election result. Two features make this problem novel and distinct. First, the number of transactions is unbounded, and an ordering must be defined over a countably infinite set. And second, decisions must be made quickly and with only partial information. Additionally, some faulty replicas might misreport their observations; the influence of faulty replicas on the output should be well understood. Prior work studies a "γ-batch-order-fairness" property, which divides an ordering into contiguous batches. If a γ fraction of replicas receive a transaction τ before another transaction τ′, then τ′ cannot be in an earlier batch than τ. This definition holds vacuously, so we strengthen it to require that batches have minimal size, while accounting for faulty replicas. This lens gives a protocol with both strictly stronger fairness and better liveness properties than prior work. We specifically adapt the Ranked Pairs [12] method to this streaming setting. This algorithm can be applied on top of any of the communication protocols (in various network models) of prior work for immediate liveness and fairness improvements. Prior work relies on a fixed choice of γ and a bound on the number of faulty replicas f, but we show that Ranked Pairs satisfies our definition for every ½ < γ ≤ 1 simultaneously and for any f, where fairness guarantees degrade as f increases.
Constant function market makers (CFMMs) are a popular decentralized exchange mechanism and have recently been the subject of much research, but major CFMMs give traders no privacy. Prior work proposes randomly splitting and shuffling trades to give some privacy toall users \citechitra2022differential, or adding noise to the market state after each trade and charging afixed 'privacy fee' to all traders \citefrongillo2018bounded. In contrast, we propose a noisy CFMM mechanism where users specify personal privacy requirements and pay personalized fees. We show that the noise added for privacy protection createsadditional arbitrage opportunities. We call a mechanismpriceable if there exists a privacy fee that always matches the additional arbitrage loss in expectation. We show that a mechanism is priceable if and only if the noise added is zero-mean in the asset amount. We also show that priceability and setting the right fee are necessary for a mechanism to betruthful, and that this fee is inversely proportional to the CFMM's liquidity.
Constant Function Market Makers (CFMMs) are a tool for creating exchange markets, have been deployed effectively in prediction markets, and are now especially prominent in the Decentralized Finance ecosystem. We show that for any set of beliefs about future asset prices, an optimal CFMM trading function exists that maximizes the fraction of trades that a CFMM can settle. We formulate a convex program to compute this optimal trading function. This program, therefore, gives a tractable framework for market-makers to compile their belief function on the future prices of the underlying assets into the trading function of a maximally capital-efficient CFMM. Our convex optimization framework further extends to capture the tradeoffs between fee revenue, arbitrage loss, and opportunity costs of liquidity providers. Analyzing the program shows how the consideration of profit and loss leads to a qualitatively different optimal trading function. Our model additionally explains the diversity of CFMM designs that appear in practice. We show that careful analysis of our convex program enables inference of a market-maker's beliefs about future asset prices, and show that these beliefs mirror the folklore intuition for several widely used CFMMs. Developing the program requires a new notion of the liquidity of a CFMM, and the core technical challenge is in the analysis of the KKT conditions of an optimization over an infinite-dimensional Banach space.