Enhancing Scalability with Improved Authenticated Dynamic Dictionaries

Leonid Reyzin, Dmitry Meshkov, Alex Chepurnoy and Sasha Ivanov have recently released a paper in which they detail the improvements made over existing implementations of two-party and three-party authenticated dynamic dictionaries. This approach will be implemented on the Waves Platform, improving its performance, scalability and ease-of-access.

With most cryptocurrencies, including Bitcoin, when a miner adds a block, other miners verify that every transaction within it is correct and accept the block into their version of the blockchain. Users that run a full node or an SPV node are required to watch the blockchain and/or perform partial verification. To verify each transaction, they need to know the balance of the payer’s account.

The simple solution is to have every verifier maintain a dynamic dictionary data structure of account addresses and account balances. Unfortunately, as this data structure grows, verifiers need to invest into more RAM (and thus can no longer operate with commodity hardware) or accept significant slowdowns that come with storing data structures in secondary storage.

Unlike the aforementioned system, authenticated dynamic dictionaries allow miners to hold the entire data structure and to modify it as transactions are processed. They publish proofs that every transaction resulted in the correct modification of the data structure. Verifiers are only required to hold a short version of the data structure that is modified to match its current state, as they verify these proofs, without ever having to store the structure itself. This system is especially useful in multi-asset systems where miners may choose to process transactions only for some types of assets but still need to verify all transactions.

Authenticated dynamic dictionaries can greatly reduce the load put on verifiers, allowing a lower amount of RAM to be used when verifying balances and transactions. This is an advantage compared to maintaining a data structure of all account balances. However, per-transaction proofs generated by authenticated dictionaries increase the size of the blockchain, which causes problems in terms of scalability. The team has therefore set on the search for a more efficient method of designing and implementing authenticated dynamic dictionaries.

In order to create a better authenticated dictionary data structure, the focus is put on reducing the length of a modification proof that is included into the block for each transaction, thus reducing the block size used. Furthermore, these data structures do not require the existence of a trusted author or setup or any secret keys. In order to ensure that miners do not make verification more time-consuming, Waves’ data structure will be deterministic and perform independently of the choices made by miners.

Another advantage is the ease with which a new user can enter the verifying process and not download the entire blocks with their respective lists of transactions, but only the block headers, which, in addition to demonstrating that the block has been correctly generated and linked to the chain, contain the digest of all the transactions processed and digests of every authenticated data structure that has changed since the previous block. This allows a new user to easily start validating new blocks, but if they want to process transactions, they must  obtain the full authenticated data structure.

“Our improvements to the design of authenticated dictionaries reduce proof size and speed up verification by 1.4–2.5 times, making them better suited for the cryptocurrency application. We further show that proofs for multiple transactions in a single block can be compressed together, reducing their total length by approximately an additional factor of 2.”

Full Paper – Improving Authenticated Dynamic Dictionaries, with Applications to Cryptocurrencies