Blockchains like Bitcoin/Ethereum are highly replicated transactional databases. More uniquely, they employ a decentralized consensus that broadens the participation in the governance of the database as much as possible. Like any transactional database, they grow with use, as does the size of active state (e.g. information on account balances or valid records of ownership) that has to be remembered in order to check the validity of new transactions. This places a storage burden on consensus participants, hindering decentralization. Authenticated data structures (ADS), such as a Merkle tree, can be used to reduce the size of the state required for transaction validation, at the cost of an increased transaction size. However, a Merkle tree would have a very large impact on network communication, as well as the size of transaction logs required for replay. This talk will present a new ADS based on the cryptographic RSA accumulator, which can be applied to achieve the same result with minimal impact on network communication.
The talk is based on my recent paper “Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains”.