Tuxedo: Maximizing Smart Contract Computation in PoW Blockchains

Sourav Das, Nitin Awathare, Ling Ren, Vinay J. Ribeiro, Umesh Bellur

Research output: Contribution to journalArticlepeer-review


Proof-of-Work (PoW) based blockchains typically allocate only a tiny fraction (e.g., less than 1% for Ethereum) of the average interarrival time∼ between blocks for validating smart contracts present in transactions. In such systems, block validation and PoW mining are typically performed sequentially, the former by CPUs and the latter by ASICs. A trivial increase in validation time introduces the popularly known Verifier's Dilemma, and as we demonstrate, causes more forking and hurts fairness. Large τ also reduces the tolerance for safety against a Byzantine adversary. Solutions that offload validation to a set of non-chain nodes (a.k.a. off-chain approaches) suffer from trust and performance issues that are non-trivial to resolve. In this paper, we present Tuxedo, the first on-chain protocol to theoretically scale approx 1 in PoW blockchains. The key innovation in Tuxedo is to perform CPU-based block processing in em parallel to ASIC mining. We achieve this by allowing miners to delay validation of transactions in a block by up to blocks, where ζ is a system parameter. We perform security analysis of Tuxedo considering all possible adversarial strategies in a synchronous network with maximum end-to-end delay Δand demonstrate that Tuxedo achieves security equivalent to known results for longest chain PoW Nakamoto consensus. Our prototype implementation of Tuxedo atop Ethereum demonstrates that it can scale τ without suffering the harmful effects of naïve scaling up of τ in existing blockchains.

Original languageEnglish (US)
Pages (from-to)63-64
Number of pages2
JournalPerformance Evaluation Review
Issue number1
StatePublished - Jun 2022


  • proof-of-work blockchains
  • scalability
  • smart contracts

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Tuxedo: Maximizing Smart Contract Computation in PoW Blockchains'. Together they form a unique fingerprint.

Cite this