- Optimal Routing for Constant Function Market Makers
Authors: Guillermo Angeris, Tarun Chitra, Alex Evans, and Stephen Boyd
We consider the problem of optimally executing an order involving multiple cryptoassets, sometimes called tokens, on a network of multiple constant function market makers (CFMMs). When we ignore the fixed cost associated with executing an order on a CFMM, this optimal routing problem can be cast as a convex optimization problem, which is computationally tractable. When we include the fixed costs, the optimal routing problem is a mixed-integer convex problem, which can be solved using (sometimes slow) global optimization methods, or approximately solved using various heuristics based on convex optimization. The optimal routing problem includes as a special case the problem of identifying an arbitrage present in a network of CFMMs, or certifying that none exists.
Link: https://web.stanford.edu/~guillean/papers/cfmm-routing.pdf
- A Note on the Security of GG18
Authors: Nikolaos Makriyannis and Udi Peled
We present attacks for information disclosure in two variants of the Gennaro and Goldfeder (CCS’2018) protocol for threshold-ECDSA signing, including the “full” variant prescribed by the paper. Although we could not expand this leakage into full blown key-extraction for neither variant, we consider this leakage to be highly problematic. The two attacks target the so-called multiplicative-to-additive phase (MtA) allowing the parties to perform two-party multiplication. Lastly, we propose simple remediation steps to foil the attacks.
Link: https://info.fireblocks.com/hubfs/A_Note_on_the_Security_of_GG.pdf
- Efficient Set Membership Proofs using MPC-in-the-Head
Authors: Aarushi Goel, Matthew Green, Mathias Hall-Andersen, and Gabriel Kaptchuk
Set membership proofs are an invaluable part of privacy preserving systems. These proofs allow a prover to demonstrate knowledge of a witness w corresponding to a secret element x of a public set, such that they jointly satisfy a given NP relation, i.e. R(w, x) = 1 and x is a member of a public set {x1, . . . , x`}. This allows the identity of the prover to remain hidden, eg. ring signatures and confidential transactions in cryptocurrencies.
In this work, we develop a new technique for efficiently adding logarithmic-sized set membership proofs to any MPC-in-the-head based zero-knowledge protocol (Ishai et al. [STOC’07]). We integrate our technique into an open source implementation of the state-of-the-art, post quantum secure zero-knowledge protocol of Katz et al. [CCS’18]. We find that using our techniques to construct ring signatures results in signatures (based only on symmetric key primitives) that are between 5 and 10 times smaller than state-of-the-art techniques based on the same assumptions. We also show that our techniques can be used to efficiently construct post-quantum secure RingCT from only symmetric key primitives.
Link: https://eprint.iacr.org/2021/1656.pdf
- SoK: Mitigation of Front-running in Decentralized Finance
Authors: Carsten Baum, James Hsin-yu Chiang, Bernardo David, Tore Kasper Frederiksen, and Lorenzo Gentile
Front-running is the malicious, and often illegal, act of both manipulating the order of pending trades and injecting additional trades to make a profit at the cost of other users. In decentralized finance (DeFi), front-running strategies exploit both public knowledge of user trades from transactions pending on the network and the miner’s ability to determine the final transaction order. Given the financial loss and increased transaction load resulting from adversarial front-running in decentralized finance, novel cryptographic protocols have been proposed to mitigate such attacks in the permission-less blockchain setting. We systematize and discuss the state-of-the-art of front-running mitigation in decentralized finance, and illustrate remaining attacks and open challenges.