Paper 2021/183

Efficient State Management in Distributed Ledgers

Dimitris Karakostas, Nikos Karayannidis, and Aggelos Kiayias


Distributed ledgers implement a storage layer, on top of which a shared state is maintained in a decentralized manner. In UTxO-based ledgers, like Bitcoin, the shared state is the set of all unspent outputs (UTxOs), which serve as inputs to future transactions. The continuously increasing size of this shared state will gradually render its maintenance unaffordable. Our work investigates techniques that minimize the shared state of the distributed ledger, i.e., the in-memory UTxO set. To this end, we follow two directions: a) we propose novel transaction optimization techniques to be followed by wallets, so as to create transactions that reduce the shared state cost and b) propose a novel fee scheme that incentivizes the creation of "state-friendly" transactions. We devise an abstract ledger model, expressed via a series of algebraic operators, and define the transaction optimization problem of minimizing the shared state; we also propose a multi-layered algorithm that approximates the optimal solution to this problem. Finally, we define the necessary conditions such that a ledger’s fee scheme incentivizes proper state management and propose a state efficient fee function for Bitcoin.

Available format(s)
Publication info
Published elsewhere. Minor revision. Financial Cryptography and Data Security 2021
blockchaintransaction optimizationincentivesBitcoin
Contact author(s)
dimitris karakostas @ ed ac uk
2021-02-20: received
Short URL
Creative Commons Attribution


      author = {Dimitris Karakostas and Nikos Karayannidis and Aggelos Kiayias},
      title = {Efficient State Management in Distributed Ledgers},
      howpublished = {Cryptology ePrint Archive, Paper 2021/183},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.