Pixiu: Optimal Block Production Revenues on Cardano (Long Version)

Abstract

Cardano is a blockchain protocol based on proof-of-stake and an extended UTXO model which also supportsarbitrary smart contracts. Its primary currency, Ada, is cur-rently one of the global top ten cryptocurrencies with amarket cap of more than 16 billion USD. In Cardano, newblocks are produced by stake pools. Any holder of Ada candelegate their stake to a pool. The underlying proof-of-stakeconsensus protocol is Ouroboros Praos, which divides time intoa number of epochs and each epoch into a number of slots, eachcorresponding to one second. In each slot, leaders are randomlyselected to produce and add new blocks to the blockchain, withtheir selection probability being proportional to their stake.Each block can contain a sequence of transactions and blockproduction is rewarded in two ways: (i) transaction fees and(ii) monetary expansion. The producers have no control over(ii), but can optimize (i) by choosing which transactions toinclude in their blocks. Thus, they are incentivized to maximizethe total transaction fees.In this work, we consider the natural optimization problemof forming a block with maximum transaction fees givena set of unmined Cardano transactions. We show that byexploiting the sparsity of interrelations between transactions,i.e. the small treedepth of dependency-conflict graphs, it ispossible to obtain a polynomial-time algorithm that outputsoptimal blocks. We implemented our algorithm in a freeand open-source tool called Pixiu. Using Pixiu, we provideextensive experimental results over real-world transaction dataon the Cardano blockchain demonstrating that our approachincreases the block producers’ revenue by almost 1,357.82USD/day = 495,604.3 USD/year.