Cryptology ePrint Archive: Report 2018/968

Edrax: A Cryptocurrency with Stateless Transaction Validation

Alexander Chepurnoy and Charalampos Papamanthou and Yupeng Zhang

Abstract: We present Edrax, a general architecture for building cryptocurrencies with stateless transaction validation. In Edrax, all cryptocurrency nodes, such as miners and validating nodes, can validate incoming transactions and subsequently update user balances simply by accessing the last confirmed block. This removes the current need for storing, off-chain and on-disk, order-of-gigabytes large validation state. We present and implement two instantiations of Edrax, one in the UTXO-based model of Bitcoin-like cryptocurrencies, where we use sparse Merkle trees, and one in the account-based model of Ethereum-like cryptocurrencies, where we show that Merkle trees cannot be used and where algebraic vector commitments are needed instead. Towards this goal, we construct, prove secure and implement the first practical algebraic vector commitment with logarithmic asymptotic costs that can scale to millions of accounts, as required by cryptocurrencies today. Our evaluation of Edrax shows that (i) for the current scale of Bitcoin and Ethereum our stateless transaction validation overhead is comparable to stateful transaction validation that requires gigabytes of local index data; (ii) while the scale increases, the performance of stateful validation deteriorates substantially due to expensive I/Os and our stateless validation is faster by up to approximately two orders of magnitude.

Category / Keywords: applications / cryptocurrency, blockchain, stateless transaction validation

Date: received 8 Oct 2018, last revised 14 Oct 2018

Contact author: cpap at umd edu

Available format(s): PDF | BibTeX Citation

Version: 20181014:152508 (All versions of this report)

Short URL: ia.cr/2018/968


[ Cryptology ePrint archive ]