Pixiu: Optimal Block Production Revenues on Cardano

Cardano is a blockchain protocol based on proof-of-stake and an extended UTXO model which also supports arbitrary smart contracts. Its primary currency, Ada, is currently one of the global top ten cryptocurrencies with a market cap of more than 16 billion USD. In Cardano, new blocks are produced by stake pools. Any holder of Ada can delegate their stake to a pool. The underlying proof-of-stake consensus protocol is Ouroboros Praos, which divides time into a number of epochs and each epoch into a number of slots, each corresponding to one second. In each slot, leaders are randomly selected to produce and add new blocks to the blockchain, with their selection probability being proportional to their stake. Each block can contain a sequence of transactions and block production 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 to include in their blocks. Thus, they are incentivized to maximize the total transaction fees. In this work, we consider the natural optimization problem of forming a block with maximum transaction fees given a set of unmined Cardano transactions. We show that by exploiting the sparsity of interrelations between transactions, i.e, the small treedepth of dependency -conflict graphs, it is possible to obtain a polynomial-time algorithm that outputs optimal blocks. We implemented our algorithm in a free and open-source tool called Pixiu. Using Pixiu, we provide extensive experimental results over real-world transaction data on the Cardano blockchain demonstrating that our approach increases the block producers' revenue by almost 1,357.82 USD/day = 495,604.3 USD/year<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup>A longer version of this work is available at [1]..