Cardano is a blockchain protocol based on proof-of-stake and an extended UTXO model which also supports arbitrary smart contracts. The underlying consensus protocol 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 presentation, 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 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.