Alexander Chepurnoy

The Web of Mind

Authenticated Dynamic Dictionaries, With Applications to Cryptocurrencies

| Comments

This article is about the paper “Improving Authenticated Dynamic Dictionaries, with Applications to Cryptocurrencies” to appear at Financial Cryptography'2017. It was presented also at RealWorldCrypto'2017 and I highly recommend to watch impressive Leonid’s presentation from the conference:

Some background. Previously I worked for the Nxt platform which has assets and much more cool features. The problem is, the blockchain processing becomes incredibly heavyweight (considering pretty low number of transactions, in comparison with Bitcoin) with new features added. The same problem with Ethereum these days - after Autumn attacks, it is nearly impossible to wait until processing being finished on an ordinary laptop.

The problem is in a state (e.g. UTXO set in Bitcoin) persistence. Once it hits a secondary storage (HDD or SSD), processing becomes very slow.

Thus two considerations behind our work on AVL+ trees and a proposed scheme for cryptocurrencies:

  • It should be feasible to run a fullnode (maybe not a mining node) on commodity hardware

  • Initial blockchain processing, and then block processing must use RAM only

As commodity hardware is pretty limited in RAM, the idea is not to store the state for full nodes at all. The scheme is as follows:

  1. The state is authenticated with the help of a 2-party dynamic authenticated dictionary.

  2. A mining node is storing the whole state. When packing transactions into a block, it generates proofs of the authenticated state transformations and announce a new root hash after the transformations being done in a blockcheader. Proofs are to be included into the block.

  3. A full-node receiving the block checks that 1) transactions are correct(format & signatures are correct etc) 2) State transformation operations derived from the transactions are corresponding to the proofs 3) Proofs are correct 4) Resulting roothash (a verifier is getting it just by processing proofs) is the same as the announced one. Thus the node is checking everything, but without holding the state (e.g. UTXO set).

Then the paper is about to find a most efficient structure out of many candidates (and the winner is custom-tailored authenticated AVL+ trees).

Not mentioned in the paper but worth to say is that proofs in a block could be authenticated themselves (with the help of a Merkle tree which is perfect for static data) with a root hash included in a blockheader. Then if node is holding the state it could skip downloading proofs from the network, also there is possibility to prune them in the future (this scheme reminds the SegWit proposal for Bitcoin).

Proofs are adding a significant burden regarding block size (actually a proof can be longer than the corresponding transaction), so decreased throughput is to be considered seriously.

The code had been released during RealWorldCrypto (, section “Authenticated data structures”). There are some possible further minor optimizations (possibly reducing proof size by few percent in total) we are now discussing.