Showing 1–14 of 14 results for author: Chitra, T

An Analysis of Intent-Based Markets

Authors: Tarun Chitra, Kshitij Kulkarni, Mallesh Pai, Theo Diamandis

Abstract: Mechanisms for decentralized finance on blockchains suffer from various problems, including suboptimal price execution for users, latency, and a worse user experience compared to their centralized counterparts. Recently, off-chain marketplaces, colloquially called `intent markets,' have been proposed as a solution to these problems. In these markets, agents called \emph{solvers} compete to satisfy… ▽ More Mechanisms for decentralized finance on blockchains suffer from various problems, including suboptimal price execution for users, latency, and a worse user experience compared to their centralized counterparts. Recently, off-chain marketplaces, colloquially called `intent markets,' have been proposed as a solution to these problems. In these markets, agents called \emph{solvers} compete to satisfy user orders, which may include complicated user-specified conditions. We provide two formal models of solvers' strategic behavior: one probabilistic and another deterministic. In our first model, solvers initially pay upfront costs to enter a Dutch auction to fill the user's order and then exert congestive, costly effort to search for prices for the user. Our results show that the costs incurred by solvers result in restricted entry in the market. Further, in the presence of costly effort and congestion, our results counter-intuitively show that a planner who aims to maximize user welfare may actually prefer to restrict entry, resulting in limited oligopoly. We then introduce an alternative, optimization-based deterministic model which corroborates these results. We conclude with extensions of our model to other auctions within blockchains and non-cryptocurrency applications, such as the US SEC's Proposal 615. △ Less

Submitted 6 March, 2024; v1 submitted 4 March, 2024; originally announced March 2024.

Comments: 27 pages, 2 figures

The Specter (and Spectra) of Miner Extractable Value

Authors: Guillermo Angeris, Tarun Chitra, Theo Diamandis, Kshitij Kulkarni

Abstract: Miner extractable value (MEV) refers to any excess value that a transaction validator can realize by manipulating the ordering of transactions. In this work, we introduce a simple theoretical definition of the 'cost of MEV', prove some basic properties, and show that the definition is useful via a number of examples. In a variety of settings, this definition is related to the 'smoothness' of a fun… ▽ More Miner extractable value (MEV) refers to any excess value that a transaction validator can realize by manipulating the ordering of transactions. In this work, we introduce a simple theoretical definition of the 'cost of MEV', prove some basic properties, and show that the definition is useful via a number of examples. In a variety of settings, this definition is related to the 'smoothness' of a function over the symmetric group. From this definition and some basic observations, we recover a number of results from the literature. △ Less

Submitted 12 October, 2023; v1 submitted 11 October, 2023; originally announced October 2023.

Towards a Theory of Maximal Extractable Value II: Uncertainty

Authors: Tarun Chitra

Abstract: Maximal Extractable Value (MEV) is value extractable by temporary monopoly power commonly found in decentralized systems. This extraction stems from a lack of user privacy upon transaction submission and the ability of a monopolist validator to reorder, add, and/or censor transactions. There are two main directions to reduce MEV: reduce the flexibility of the miner to reorder transactions by enfor… ▽ More Maximal Extractable Value (MEV) is value extractable by temporary monopoly power commonly found in decentralized systems. This extraction stems from a lack of user privacy upon transaction submission and the ability of a monopolist validator to reorder, add, and/or censor transactions. There are two main directions to reduce MEV: reduce the flexibility of the miner to reorder transactions by enforcing ordering rules and/or introduce a competitive market for the right to reorder, add, and/or censor transactions. In this work, we unify these approaches via \emph{uncertainty principles}, akin to those found in harmonic analysis and physics. This provides a quantitative trade-off between the freedom to reorder transactions and the complexity of an economic payoff to a user in a decentralized network. This trade off is analogous to the Nyquist-Shannon sampling theorem and demonstrates that sequencing rules in blockchains need to be application specific. Our results suggest that neither so-called fair ordering techniques nor economic mechanisms can individually mitigate MEV for arbitrary payoff functions. △ Less

Submitted 25 September, 2023; originally announced September 2023.

Attacks on Dynamic DeFi Interest Rate Curves

Authors: Tarun Chitra, Peteris Erins, Kshitij Kulkarni

Abstract: As decentralized money market protocols continue to grow in value locked, there have been a number of optimizations proposed for improving capital efficiency. One set of proposals from Euler Finance and Mars Protocol is to have an interest rate curve that is a proportional-integral-derivative (PID) controller. In this paper, we demonstrate attacks on proportional and proportional-integral controll… ▽ More As decentralized money market protocols continue to grow in value locked, there have been a number of optimizations proposed for improving capital efficiency. One set of proposals from Euler Finance and Mars Protocol is to have an interest rate curve that is a proportional-integral-derivative (PID) controller. In this paper, we demonstrate attacks on proportional and proportional-integral controlled interest rate curves. The attack allows one to manipulate the interest rate curve to take a higher proportion of the earned yield than their pro-rata share of the lending pool. We conclude with an argument that PID interest rate curves can actually \emph{reduce} capital efficiency (due to attack mitigations) unless supply and demand elasticity to rate changes are sufficiently high. △ Less

Submitted 24 July, 2023; originally announced July 2023.

Credible, Optimal Auctions via Blockchains

Authors: Tarun Chitra, Matheus V. X. Ferreira, Kshitij Kulkarni

Abstract: Akbarpour and Li (2020) formalized credibility as an auction desideratum where the auctioneer cannot benefit by implementing undetectable deviations from the promised auction and showed that, in the plain model, the ascending price auction with reserves is the only credible, strategyproof, revenue-optimal auction. Ferreira and Weinberg (2020) proposed the Deferred Revelation Auction (DRA) as a com… ▽ More Akbarpour and Li (2020) formalized credibility as an auction desideratum where the auctioneer cannot benefit by implementing undetectable deviations from the promised auction and showed that, in the plain model, the ascending price auction with reserves is the only credible, strategyproof, revenue-optimal auction. Ferreira and Weinberg (2020) proposed the Deferred Revelation Auction (DRA) as a communication efficient auction that avoids the uniqueness results from Akbarpour and Li (2020) assuming the existence of cryptographic commitments and as long as bidder valuations are MHR. They also showed DRA is not credible in settings where bidder valuations are $α$-strongly regular unless $α> 1$. In this paper, we ask if blockchains allow us to design a larger class of credible auctions. We answer this question positively, by showing that DRA is credible even for $α$-strongly regular distributions for all $α> 0$ if implemented over a secure and censorship-resistant blockchain. We argue ledgers provide two properties that limit deviations from a self-interested auctioneer. First, the existence of smart contracts allows one to extend the concept of credibility to settings where the auctioneer does not have a reputation -- one of the main limitations for the definition of credibility from Akbarpour and Li (2020). Second, blockchains allow us to implement mechanisms over a public broadcast channel, removing the adaptive undetectable deviations driving the negative results of Ferreira and Weinberg (2020). △ Less

Submitted 29 January, 2023; originally announced January 2023.

Dynamic Pricing for Non-fungible Resources: Designing Multidimensional Blockchain Fee Markets

Authors: Theo Diamandis, Alex Evans, Tarun Chitra, Guillermo Angeris

Abstract: Public blockchains implement a fee mechanism to allocate scarce computational resources across competing transactions. Most existing fee market designs utilize a joint, fungible unit of account (e.g., gas in Ethereum) to price otherwise non-fungible resources such as bandwidth, computation, and storage, by hardcoding their relative prices. Fixing the relative price of each resource in this way inh… ▽ More Public blockchains implement a fee mechanism to allocate scarce computational resources across competing transactions. Most existing fee market designs utilize a joint, fungible unit of account (e.g., gas in Ethereum) to price otherwise non-fungible resources such as bandwidth, computation, and storage, by hardcoding their relative prices. Fixing the relative price of each resource in this way inhibits granular price discovery, limiting scalability and opening up the possibility of denial-of-service attacks. As a result, many prominent networks such as Ethereum and Solana have proposed multi-dimensional fee markets. In this paper, we provide a principled way to design fee markets that efficiently price multiple non-fungible resources. Starting from a loss function specified by the network designer, we show how to compute dynamic prices that align the network's incentives (to minimize the loss) with those of the users and miners (to maximize their welfare), even as demand for these resources changes. Our pricing mechanism follows from a natural decomposition of the network designer's problem into two parts that are related to each other via the resource prices. These results can be used to efficiently set fees in order to improve network performance. △ Less

Submitted 3 November, 2022; v1 submitted 16 August, 2022; originally announced August 2022.

Towards a Theory of Maximal Extractable Value I: Constant Function Market Makers

Authors: Kshitij Kulkarni, Theo Diamandis, Tarun Chitra

Abstract: Maximal Extractable Value (MEV) refers to excess value captured by miners (or validators) from users in a cryptocurrency network. This excess value often comes from reordering users' transactions to maximize fees or from inserting new transactions that front-run users' transactions. One of the most common types of MEV involves a `sandwich attack' against a user trading on a constant function marke… ▽ More Maximal Extractable Value (MEV) refers to excess value captured by miners (or validators) from users in a cryptocurrency network. This excess value often comes from reordering users' transactions to maximize fees or from inserting new transactions that front-run users' transactions. One of the most common types of MEV involves a `sandwich attack' against a user trading on a constant function market maker (CFMM), which is a popular class of automated market maker. We analyze game theoretic properties of MEV in CFMMs that we call \textit{routing} and \textit{reordering} MEV. In the case of routing, we present examples where the existence of MEV both degrades and, counterintuitively, \emph{improves} the quality of routing. We construct an analogue of the price of anarchy for this setting and demonstrate that if the impact of a sandwich attack is localized in a suitable sense, then the price of anarchy is constant. In the case of reordering, we show conditions when the maximum price impact caused by the reordering of sandwich attacks in a sequence of trades, relative to the average price, impact is $O(\log n)$ in the number of user trades. Combined, our results suggest methods that both MEV searchers and CFMM designers can utilize for estimating costs and profits of MEV. △ Less

Submitted 30 April, 2023; v1 submitted 24 July, 2022; originally announced July 2022.

Unity is Strength: A Formalization of Cross-Domain Maximal Extractable Value

Authors: Alexandre Obadia, Alejo Salles, Lakshman Sankar, Tarun Chitra, Vaibhav Chellani, Philip Daian

Abstract: The multi-chain future is upon us. Modular architectures are coming to maturity across the ecosystem to scale bandwidth and throughput of cryptocurrency. One example of such is the Ethereum modular architecture, with its beacon chain, its execution chain, its Layer 2s, and soon its shards. These can all be thought as separate blockchains, heavily inter-connected with one another, and together form… ▽ More The multi-chain future is upon us. Modular architectures are coming to maturity across the ecosystem to scale bandwidth and throughput of cryptocurrency. One example of such is the Ethereum modular architecture, with its beacon chain, its execution chain, its Layer 2s, and soon its shards. These can all be thought as separate blockchains, heavily inter-connected with one another, and together forming an ecosystem. In this work, we call each of these interconnected blockchains "domains", and study the manifestation of Maximal Extractable Value (MEV, a generalization of "Miner Extractable Value") across them. In other words, we investigate whether there exists extractable value that depends on the ordering of transactions in two or more domains jointly. We first recall the definitions of Extractable and Maximal Extractable Value, before introducing a definition of Cross-Domain Maximal Extractable Value. We find that Cross-Domain MEV can be used to measure the incentive for transaction sequencers in different domains to collude with one another, and study the scenarios in which there exists such an incentive. We end the work with a list of negative externalities that might arise from cross-domain MEV extraction and lay out several open questions. We note that the formalism in this work is a work in progress, and we hope that it can serve as the basis for formal analysis tools in the style of those presented in Clockwork Finance, as well as for discussion on how to mitigate the upcoming negative externalities of substantial cross-domain MEV. △ Less

Submitted 5 December, 2021; v1 submitted 2 December, 2021; originally announced December 2021.

A Note on Privacy in Constant Function Market Makers

Authors: Guillermo Angeris, Alex Evans, Tarun Chitra

Abstract: Constant function market makers (CFMMs) such as Uniswap, Balancer, Curve, and mStable, among many others, make up some of the largest decentralized exchanges on Ethereum and other blockchains. Because all transactions are public in current implementations, a natural next question is if there exist similar decentralized exchanges which are privacy-preserving; i.e., if a transaction's quantities are… ▽ More Constant function market makers (CFMMs) such as Uniswap, Balancer, Curve, and mStable, among many others, make up some of the largest decentralized exchanges on Ethereum and other blockchains. Because all transactions are public in current implementations, a natural next question is if there exist similar decentralized exchanges which are privacy-preserving; i.e., if a transaction's quantities are hidden from the public view, then an adversary cannot correctly reconstruct the traded quantities from other public information. In this note, we show that privacy is impossible with the usual implementations of CFMMs under most reasonable models of an adversary and provide some mitigating strategies. △ Less

Submitted 1 March, 2021; originally announced March 2021.

Why Stake When You Can Borrow?

Authors: Tarun Chitra, Alex Evans

Abstract: As smart contract platforms autonomously manage billions of dollars of capital, quantifying the portfolio risk that investors engender in these systems is increasingly important. Recent work illustrates that Proof of Stake (PoS) is vulnerable to financial attacks arising from on-chain lending and has worse capital efficiency than Proof of Work (PoW) \cite{fanti_pos_econ}. Numerous methods for impr… ▽ More As smart contract platforms autonomously manage billions of dollars of capital, quantifying the portfolio risk that investors engender in these systems is increasingly important. Recent work illustrates that Proof of Stake (PoS) is vulnerable to financial attacks arising from on-chain lending and has worse capital efficiency than Proof of Work (PoW) \cite{fanti_pos_econ}. Numerous methods for improving capital efficiency have been proposed that allow stakers to create fungible derivative claims on their staked assets. In this paper, we construct a unifying model for studying the security risks of these proposals. This model combines birth-death Pólya processes and risk models adapted from the credit derivatives literature to assess token inequality and return profiles. We find that there is a sharp transition between 'safe' and 'unsafe' derivative usage. Surprisingly, we find that contrary to \cite{fanti2019compounding} there exist conditions where derivatives can \emph{reduce} concentration of wealth in these networks. This model also applies to Decentralized Finance (DeFi) protocols where staked assets are used as insurance. Our theoretical results are validated using agent-based simulation. △ Less

Submitted 16 June, 2020; originally announced June 2020.

Competitive equilibria between staking and on-chain lending

Authors: Tarun Chitra

Abstract: Proof of Stake (PoS) is a burgeoning Sybil resistance mechanism that aims to have a digital asset ("token") serve as security collateral in crypto networks. However, PoS has so far eluded a comprehensive threat model that encompasses both Byzantine attacks from distributed systems and financial attacks that arise from the dual usage of the token as a means of payment and a Sybil resistance mechani… ▽ More Proof of Stake (PoS) is a burgeoning Sybil resistance mechanism that aims to have a digital asset ("token") serve as security collateral in crypto networks. However, PoS has so far eluded a comprehensive threat model that encompasses both Byzantine attacks from distributed systems and financial attacks that arise from the dual usage of the token as a means of payment and a Sybil resistance mechanism. In particular, the existence of derivatives markets makes malicious coordination among validators easier to execute than in Proof of Work systems. We demonstrate that it is also possible for on-chain lending smart contracts to cannibalize network security in PoS systems. When the yield provided by these contracts is more attractive than the inflation rate provided from staking, stakers will tend to remove their staked tokens and lend them out, thus reducing network security. In this paper, we provide a simple stochastic model that describes how rational validators with varying risk preferences react to changes in staking and lending returns. For a particular configuration of this model, we provide a formal proof of a phase transition between equilibria in which tokens are predominantly staked and those in which they are predominantly lent. We further validate this emergent adversarial behavior (e.g. reduced staked token supply) with agent-based simulations that sample transitions under more realistic conditions. Our results illustrate that rational, non-adversarial actors can dramatically reduce PoS network security if block rewards are not calibrated appropriately above the expected yields of on-chain lending. △ Less

Submitted 4 February, 2020; v1 submitted 27 November, 2019; originally announced January 2020.

Comments: 25 pages, Accepted to Stanford Blockchain Conference and MIT Cryptoeconomic Systems '20

An analysis of Uniswap markets

Authors: Guillermo Angeris, Hsien-Tang Kao, Rei Chiang, Charlie Noyes, Tarun Chitra

Abstract: Uniswap -- and other constant product markets -- appear to work well in practice despite their simplicity. In this paper, we give a simple formal analysis of constant product markets and their generalizations, showing that, under some common conditions, these markets must closely track the reference market price. We also show that Uniswap satisfies many other desirable properties and numerically d… ▽ More Uniswap -- and other constant product markets -- appear to work well in practice despite their simplicity. In this paper, we give a simple formal analysis of constant product markets and their generalizations, showing that, under some common conditions, these markets must closely track the reference market price. We also show that Uniswap satisfies many other desirable properties and numerically demonstrate, via a large-scale agent-based simulation, that Uniswap is stable under a wide range of market conditions. △ Less

Submitted 9 February, 2021; v1 submitted 8 November, 2019; originally announced November 2019.

Agent-Based Simulations of Blockchain protocols illustrated via Kadena's Chainweb

Authors: Tarun Chitra, Monica Quaintance, Stuart Haber, Will Martino

Abstract: While many distributed consensus protocols provide robust liveness and consistency guarantees under the presence of malicious actors, quantitative estimates of how economic incentives affect security are few and far between. In this paper, we describe a system for simulating how adversarial agents, both economically rational and Byzantine, interact with a blockchain protocol. This system provides… ▽ More While many distributed consensus protocols provide robust liveness and consistency guarantees under the presence of malicious actors, quantitative estimates of how economic incentives affect security are few and far between. In this paper, we describe a system for simulating how adversarial agents, both economically rational and Byzantine, interact with a blockchain protocol. This system provides statistical estimates for the economic difficulty of an attack and how the presence of certain actors influences protocol-level statistics, such as the expected time to regain liveness. This simulation system is influenced by the design of algorithmic trading and reinforcement learning systems that use explicit modeling of an agent's reward mechanism to evaluate and optimize a fully autonomous agent. We implement and apply this simulation framework to Kadena's Chainweb, a parallelized Proof-of-Work system, that contains complexity in how miner incentive compliance affects security and censorship resistance. We provide the first formal description of Chainweb that is in the literature and use this formal description to motivate our simulation design. Our simulation results include a phase transition in block height growth rate as a function of shard connectivity and empirical evidence that censorship in Chainweb is too costly for rational miners to engage in. We conclude with an outlook on how simulation can guide and optimize protocol development in a variety of contexts, including Proof-of-Stake parameter optimization and peer-to-peer networking design. △ Less

Submitted 29 April, 2019; originally announced April 2019.

Comments: 10 pages, 7 figures, accepted to the IEEE S&B 2019 conference

Committee Selection is More Similar Than You Think: Evidence from Avalanche and Stellar

Authors: Tarun Chitra, Uthsav Chitra

Abstract: Increased interest in scalable and high-throughput blockchains has led to an explosion in the number of committee selection methods in the literature. Committee selection mechanisms allow consensus protocols to safely select a committee, or a small subset of validators that is permitted to vote and verify a block of transactions, in a distributed ledger. There are many such mechanisms, each with s… ▽ More Increased interest in scalable and high-throughput blockchains has led to an explosion in the number of committee selection methods in the literature. Committee selection mechanisms allow consensus protocols to safely select a committee, or a small subset of validators that is permitted to vote and verify a block of transactions, in a distributed ledger. There are many such mechanisms, each with substantially different methodologies and guarantees on communication complexity, resource usage, and fairness. In this paper, we illustrate that, despite these implementation-level differences, there are strong statistical similarities between committee selection mechanisms. We concretely show this by proving that the committee selection of the Avalanche consensus protocol can be used to choose committees in the Stellar Consensus Protocol that satisfy the necessary and sufficient conditions for Byzantine agreement. We also verify these claims using simulations and numerically observe sharp phase transitions as a function of protocol parameters. Our results suggest the existence of a "statistical taxonomy" of committee selection mechanisms in distributed consensus algorithms. △ Less

Submitted 7 April, 2019; originally announced April 2019.

Comments: 7 pages, 3 figures