Kartik Nayak
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Kartik Nayak has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
- Elaine Shi
Computer Science Department Carnegie Mellon University
5 shared publications - Ling Ren
University of Illinois Urbana-Champaign
4 shared publications - T. -H. Hubert Chan
The University of Hong Kong, Hong Kong, China
4 shared publications - Aniket Kate
Purdue University, West Lafayette, Indiana, USA
3 shared publications - Gilad Asharov
Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel
3 shared publications - Ittai Abraham
VMware Research
3 shared publications
Latest Publications
- Open Access
- 22 April 2026
- Published by Elsevier in SSRN Electronic Journal
Perils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty
Modern blockchains increasingly rely on parallel execution to improve throughput. We show several industry and academic transaction fee mechanisms (TFMs) struggle to simultaneously account for execution parallelism while remaining performant and fair. First, if parallelism affects fees, adversarial protocol manipulations that offset possible benefits to throughput by introducing fake transactions become rational: users can insert functionally useless parallel transactions solely to reduce fees, and schedulers can create useless sequential transactions to increase revenue. Execution contingency, a core feature of expressive programming languages, both exacerbates the aforementioned threats and introduces new ones: (1) users may overpay for unused resources, and (2) scheduler revenue is harmed when reserved scheduling slots go unused due to contingency. We introduce a framework for this challenging setting, and prove an impossibility, highlighting an inherent tension: both parallelism and contingency involve a trade-off between minimizing risks for users and schedulers, as favoring one comes at the expense of the other. To complete the picture, we introduce fee mechanisms and prove that they achieve the boundaries of this trade-off. Our results provide rigorous foundations for evaluating designs advanced by notable blockchains, such as Sui and Monad.
- 22 April 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessPerils of Parallelism: Transaction Fee Mechanisms under Execution Uncertainty
Modern blockchains increasingly rely on parallel execution to improve throughput. We show several industry and academic transaction fee mechanisms (TFMs) struggle to simultaneously account for execution parallelism while remaining performant and fair. First, if parallelism affects fees, adversarial protocol manipulations that offset possible benefits to throughput by introducing fake transactions become rational: users can insert functionally useless parallel transactions solely to reduce fees, and schedulers can create useless sequential transactions to increase revenue. Execution contingency, a core feature of expressive programming languages, both exacerbates the aforementioned threats and introduces new ones: (1) users may overpay for unused resources, and (2) scheduler revenue is harmed when reserved scheduling slots go unused due to contingency. We introduce a framework for this challenging setting, and prove an impossibility, highlighting an inherent tension: both parallelism and contingency involve a trade-off between minimizing risks for users and schedulers, as favoring one comes at the expense of the other. To complete the picture, we introduce fee mechanisms and prove that they achieve the boundaries of this trade-off. Our results provide rigorous foundations for evaluating designs advanced by notable blockchains, such as Sui and Monad.
- 2 January 2026
- Published by Springer Nature
- p. 327-344
Communication and Round Efficient Parallel Broadcast Protocols
- 2 January 2026
- Published by Springer Nature
- p. 327-344
Communication and Round Efficient Parallel Broadcast Protocols
- Open Access
- 19 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 3780-3794
Optimistic, Signature-Free Reliable Broadcast and Its Applications
- 19 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 3780-3794
Open AccessOptimistic, Signature-Free Reliable Broadcast and Its Applications
- Open Access
Attacking and Improving the Tor Directory Protocol
The Tor network enhances clients' privacy by routing traffic through an overlay network of volunteered intermediate relays. Tor employs a distributed protocol among nine hard-coded Directory Authority (DA) servers to securely disseminate information about these relays to produce a new consensus document every hour. With a straightforward voting mechanism to ensure consistency, the protocol is expected to be secure even when a minority of those authorities get compromised. However, the current consensus protocol is flawed: it allows an equivocation attack that enables only a single compromised authority to create a valid consensus document with malicious relays. Importantly the vulnerability is not innocuous: We demonstrate that the compromised authority can effectively trick a targeted client into using the equivocated consensus document in an undetectable manner. Moreover, even if we have archived Tor consensus documents available since its beginning, we cannot be sure that no client was ever tricked. We propose a two-stage solution to deal with this exploit. In the short term, we have developed and deployed TorEq, a monitor to detect such exploits reactively: the Tor clients can refer to the monitor before updating the consensus to ensure no equivocation. To solve the problem proactively, we first define the Tor DA consensus problem as the interactive consistency (IC) problem from the distributed computing literature. We then design DirCast, a novel secure Byzantine Broadcast protocol that requires minimal code change from the current Tor DA code base. Our protocol has near-optimal efficiency that uses optimistically five rounds and at most nine rounds to reach an agreement in the current nine-authority system. We are communicating with the Tor security team to incorporate the solutions into the Tor project.
Open AccessAttacking and Improving the Tor Directory Protocol
The Tor network enhances clients' privacy by routing traffic through an overlay network of volunteered intermediate relays. Tor employs a distributed protocol among nine hard-coded Directory Authority (DA) servers to securely disseminate information about these relays to produce a new consensus document every hour. With a straightforward voting mechanism to ensure consistency, the protocol is expected to be secure even when a minority of those authorities get compromised. However, the current consensus protocol is flawed: it allows an equivocation attack that enables only a single compromised authority to create a valid consensus document with malicious relays. Importantly the vulnerability is not innocuous: We demonstrate that the compromised authority can effectively trick a targeted client into using the equivocated consensus document in an undetectable manner. Moreover, even if we have archived Tor consensus documents available since its beginning, we cannot be sure that no client was ever tricked. We propose a two-stage solution to deal with this exploit. In the short term, we have developed and deployed TorEq, a monitor to detect such exploits reactively: the Tor clients can refer to the monitor before updating the consensus to ensure no equivocation. To solve the problem proactively, we first define the Tor DA consensus problem as the interactive consistency (IC) problem from the distributed computing literature. We then design DirCast, a novel secure Byzantine Broadcast protocol that requires minimal code change from the current Tor DA code base. Our protocol has near-optimal efficiency that uses optimistically five rounds and at most nine rounds to reach an agreement in the current nine-authority system. We are communicating with the Tor security team to incorporate the solutions into the Tor project.
- Open Access
- 2 December 2024
- Published by Association for Computing Machinery (ACM)
- p. 378-392
Data Independent Order Policy Enforcement: Limitations and Solutions
Order manipulation attacks such as frontrunning and sandwiching have become an increasing concern in blockchain applications such as DeFi. To protect from such attacks, several recent works have designed order policy enforcement (OPE) protocols to order transactions fairly in a data-independent fashion. However, while the manipulation attacks are motivated by monetary profits, the defenses assume honesty among a significantly large set of participants. In existing protocols, if all participants are rational, they may be incentivized to collude and circumvent the order policy without incurring any penalty. This work makes two key contributions. First, we explore whether the need for the honesty assumption is fundamental. Indeed, we show that it is impossible to design OPE protocols under some requirements when all parties are rational. Second, we explore the tradeoffs needed to circumvent the impossibility result. In the process, we propose a novel concept of rationally binding transactions that allows us to construct AnimaguSwap, the first content-oblivious Automated Market Makers (AMM) interface that is secure under rationality. We report on a prototype implementation of AnimaguSwap and performance evaluation results demonstrating its practicality.
- 2 December 2024
- Published by Association for Computing Machinery (ACM)
- p. 378-392
Open AccessData Independent Order Policy Enforcement: Limitations and Solutions
Order manipulation attacks such as frontrunning and sandwiching have become an increasing concern in blockchain applications such as DeFi. To protect from such attacks, several recent works have designed order policy enforcement (OPE) protocols to order transactions fairly in a data-independent fashion. However, while the manipulation attacks are motivated by monetary profits, the defenses assume honesty among a significantly large set of participants. In existing protocols, if all participants are rational, they may be incentivized to collude and circumvent the order policy without incurring any penalty. This work makes two key contributions. First, we explore whether the need for the honesty assumption is fundamental. Indeed, we show that it is impossible to design OPE protocols under some requirements when all parties are rational. Second, we explore the tradeoffs needed to circumvent the impossibility result. In the process, we propose a novel concept of rationally binding transactions that allows us to construct AnimaguSwap, the first content-oblivious Automated Market Makers (AMM) interface that is secure under rationality. We report on a prototype implementation of AnimaguSwap and performance evaluation results demonstrating its practicality.
- Open Access
- 8 July 2024
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (2)
Synchronous Distributed Key Generation without Broadcasts
Distributed key generation (DKG) is a key building block in developing many efficient threshold cryptosystems. This work initiates the study of communication complexity and round complexity of DKG protocols over a point-to-point (bounded) synchronous network. Our key result is the first synchronous DKG protocol for discrete log-based cryptosystems with O ( κ n 3 ) communication complexity ( κ denotes a security parameter) that tolerates any t < n / 2 Byzantine faults among n parties. We present two variants of the protocol: (i) a protocol with worst-case O ( κ n 3 ) communication and O ( t ) rounds, and (ii) a protocol with expected O ( κ n 3 ) communication and expected constant rounds. In the process of achieving our results, we design (1) a novel weak gradecast protocol with a communication complexity of O ( κ n 2 ) for linear-sized inputs and constant rounds, (2) a protocol called “recoverable-set-of-shares” for ensuring recovery of shared secrets, (3) an oblivious leader election protocol with O ( κ n 3 ) communication and constant rounds, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with O ( κ n 3 ) communication complexity for linear-sized inputs and expected constant rounds. Each of these primitives is of independent interest.
- 8 July 2024
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (2)
Open AccessSynchronous Distributed Key Generation without Broadcasts
Distributed key generation (DKG) is a key building block in developing many efficient threshold cryptosystems. This work initiates the study of communication complexity and round complexity of DKG protocols over a point-to-point (bounded) synchronous network. Our key result is the first synchronous DKG protocol for discrete log-based cryptosystems with O ( κ n 3 ) communication complexity ( κ denotes a security parameter) that tolerates any t < n / 2 Byzantine faults among n parties. We present two variants of the protocol: (i) a protocol with worst-case O ( κ n 3 ) communication and O ( t ) rounds, and (ii) a protocol with expected O ( κ n 3 ) communication and expected constant rounds. In the process of achieving our results, we design (1) a novel weak gradecast protocol with a communication complexity of O ( κ n 2 ) for linear-sized inputs and constant rounds, (2) a protocol called “recoverable-set-of-shares” for ensuring recovery of shared secrets, (3) an oblivious leader election protocol with O ( κ n 3 ) communication and constant rounds, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with O ( κ n 3 ) communication complexity for linear-sized inputs and expected constant rounds. Each of these primitives is of independent interest.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 135-144
Lumiere: Making Optimal BFT for Partial Synchrony Practical
The view synchronization problem lies at the heart of many Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) protocols in the partial synchrony model, since these protocols are usually based on views. Liveness is guaranteed if honest processors spend a sufficiently long time in the same view during periods of synchrony, and if the leader of the view is honest. Ensuring that these conditions occur, known as Byzantine View Synchronization (BVS), has turned out to be the performance bottleneck of many BFT SMR protocols. A recent line of work [7, 12] has shown that, by using an appropriate view synchronization protocol, BFT SMR protocols can achieve O(n2) communication complexity in the worst case after GST, thereby finally matching the lower bound established by Dolev and Reischuk in 1985 [9]. However, these protocols suffer from two major issues, hampering praticality: (i) When implemented so as to be optimistically responsive, even a single Byzantine processor may infinitely often cause Ω(nΔ) latency between consecutive consensus decisions. (ii) Even in the absence of Byzantine action, infinitely many views require honest processors to send Ω(n2) messages. Here, we present Lumiere, an optimistically responsive BVS protocol which maintains optimal worst-case communication complexity while simultaneously addressing the two issues above: for the first time, Lumiere enables BFT consensus solutions in the partial synchrony setting that have O(n2) worst-case communication complexity, and that eventually always (i.e., except for a small constant number of "warmup" decisions) have communication complexity and latency which is linear in the number of actual faults in the execution.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 135-144
Open AccessLumiere: Making Optimal BFT for Partial Synchrony Practical
The view synchronization problem lies at the heart of many Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) protocols in the partial synchrony model, since these protocols are usually based on views. Liveness is guaranteed if honest processors spend a sufficiently long time in the same view during periods of synchrony, and if the leader of the view is honest. Ensuring that these conditions occur, known as Byzantine View Synchronization (BVS), has turned out to be the performance bottleneck of many BFT SMR protocols. A recent line of work [7, 12] has shown that, by using an appropriate view synchronization protocol, BFT SMR protocols can achieve O(n2) communication complexity in the worst case after GST, thereby finally matching the lower bound established by Dolev and Reischuk in 1985 [9]. However, these protocols suffer from two major issues, hampering praticality: (i) When implemented so as to be optimistically responsive, even a single Byzantine processor may infinitely often cause Ω(nΔ) latency between consecutive consensus decisions. (ii) Even in the absence of Byzantine action, infinitely many views require honest processors to send Ω(n2) messages. Here, we present Lumiere, an optimistically responsive BVS protocol which maintains optimal worst-case communication complexity while simultaneously addressing the two issues above: for the first time, Lumiere enables BFT consensus solutions in the partial synchrony setting that have O(n2) worst-case communication complexity, and that eventually always (i.e., except for a small constant number of "warmup" decisions) have communication complexity and latency which is linear in the number of actual faults in the execution.
- 1 December 2023
- Published by Springer Nature
- p. 56-74
Player-Replaceability and Forensic Support Are Two Sides of the Same (Crypto) Coin
- 1 December 2023
- Published by Springer Nature
- p. 56-74
Player-Replaceability and Forensic Support Are Two Sides of the Same (Crypto) Coin
- Open Access
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 1571-1584
TrustBoost: Boosting Trust among Interoperable Blockchains
Currently there exist many blockchains with weak trust guarantees, limiting applications and participation. Existing solutions to boost the trust using a stronger blockchain, e.g., via checkpointing, requires the weaker blockchain to give up sovereignty. In this paper, we propose a family of protocols in which multiple blockchains interact to create a combined ledger with boosted trust. We show that even if several of the interacting blockchains cease to provide security guarantees, the combined ledger continues to be secure - our Trustboost protocols achieve the optimal threshold of tolerating the insecure blockchains. This optimality, along with the necessity of blockchain interactions, is formally shown within the classic shared memory model, tackling the long standing open challenge of solving consensus in the presence of both Byzantine objects and processes. Furthermore, our proposed construction of Trustboost simply operates via smart contracts and require no change to the underlying consensus protocols of the participating blockchains, a form of "consensus on top of consensus''. The protocols are lightweight and can be used on specific (e.g., high value) transactions; we demonstrate the practicality by implementing and deploying Trustboost as cross-chain smart contracts in the Cosmos ecosystem using approximately 3,000 lines of Rust code, made available as open source [52]. Our evaluation shows that using 10 Cosmos chains in a local testnet, Trustboost has a gas cost of roughly $2 with a latency of 2 minutes per request, which is in line with the cost on a high security chain such as Bitcoin or Ethereum.
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 1571-1584
Open AccessTrustBoost: Boosting Trust among Interoperable Blockchains
Currently there exist many blockchains with weak trust guarantees, limiting applications and participation. Existing solutions to boost the trust using a stronger blockchain, e.g., via checkpointing, requires the weaker blockchain to give up sovereignty. In this paper, we propose a family of protocols in which multiple blockchains interact to create a combined ledger with boosted trust. We show that even if several of the interacting blockchains cease to provide security guarantees, the combined ledger continues to be secure - our Trustboost protocols achieve the optimal threshold of tolerating the insecure blockchains. This optimality, along with the necessity of blockchain interactions, is formally shown within the classic shared memory model, tackling the long standing open challenge of solving consensus in the presence of both Byzantine objects and processes. Furthermore, our proposed construction of Trustboost simply operates via smart contracts and require no change to the underlying consensus protocols of the participating blockchains, a form of "consensus on top of consensus''. The protocols are lightweight and can be used on specific (e.g., high value) transactions; we demonstrate the practicality by implementing and deploying Trustboost as cross-chain smart contracts in the Cosmos ecosystem using approximately 3,000 lines of Rust code, made available as open source [52]. Our evaluation shows that using 10 Cosmos chains in a local testnet, Trustboost has a gas cost of roughly $2 with a latency of 2 minutes per request, which is in line with the cost on a high security chain such as Bitcoin or Ethereum.
- Open Access
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 519-533
Abraxas: Throughput-Efficient Hybrid Asynchronous Consensus
Protocols for state-machine replication (SMR) often trade off performance for resilience to network delay. In particular, protocols for asynchronous SMR tolerate arbitrary network delay but sacrifice throughput/latency when the network is fast, while partially synchronous protocols have good performance in a fast network but fail to make progress if the network experiences high delay. Existing hybrid protocols are resilient to arbitrary network delay and have good performance when the network is fast, but suffer from high overhead (''thrashing'') if the network repeatedly switches between being fast and slow, e.g., in a network that is typically fast but has intermittent message delays. We propose Abraxas, a generic approach for constructing a hybrid protocol from any ''fast'' protocol Πfast and asynchronous protocolΠslow to achieve (1) security and performance equivalent to Πslow under arbitrary network behavior, and (2) performance equivalent to Πfast when conditions are favorable. We instantiate Abraxas with the best existing protocols for Πfast (Jolteon) and Πslow (\mbox2-chain VABA), and show experimentally that the resulting protocol significantly outperforms Ditto, the previous state-of-the-art hybrid protocol.
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 519-533
Open AccessAbraxas: Throughput-Efficient Hybrid Asynchronous Consensus
Protocols for state-machine replication (SMR) often trade off performance for resilience to network delay. In particular, protocols for asynchronous SMR tolerate arbitrary network delay but sacrifice throughput/latency when the network is fast, while partially synchronous protocols have good performance in a fast network but fail to make progress if the network experiences high delay. Existing hybrid protocols are resilient to arbitrary network delay and have good performance when the network is fast, but suffer from high overhead (''thrashing'') if the network repeatedly switches between being fast and slow, e.g., in a network that is typically fast but has intermittent message delays. We propose Abraxas, a generic approach for constructing a hybrid protocol from any ''fast'' protocol Πfast and asynchronous protocolΠslow to achieve (1) security and performance equivalent to Πslow under arbitrary network behavior, and (2) performance equivalent to Πfast when conditions are favorable. We instantiate Abraxas with the best existing protocols for Πfast (Jolteon) and Πslow (\mbox2-chain VABA), and show experimentally that the resulting protocol significantly outperforms Ditto, the previous state-of-the-art hybrid protocol.