1. Improving Authenticated Dynamic Dictionaries, with Applications to Cryptocurrencies 2017 Blockchains FinancialCryptography
    Leonid Reyzin, Dmitry Meshkov, Alexander Chepurnoy, Sasha Ivanov
    [View PDF on fc17.ifca.ai]
    [Show BibTex Citation]

    author = {Leonid Reyzin and
    Dmitry Meshkov and
    Alexander Chepurnoy and
    Sasha Ivanov},
    editor = {Aggelos Kiayias},
    title = {Improving Authenticated Dynamic Dictionaries, with Applications to
    booktitle = {Financial Cryptography and Data Security - 21st International Conference,
    {FC} 2017, Sliema, Malta, April 3-7, 2017, Revised Selected Papers},
    series = {Lecture Notes in Computer Science},
    volume = {10322},
    pages = {376--392},
    publisher = {Springer},
    year = {2017},
    url = {https://doi.org/10.1007/978-3-319-70972-7\_21},
    doi = {10.1007/978-3-319-70972-7\_21},
    timestamp = {Tue, 14 May 2019 10:00:38 +0200},
    biburl = {https://dblp.org/rec/bib/conf/fc/ReyzinMCI17},
    bibsource = {dblp computer science bibliography, https://dblp.org}

We improve the design and implementation of two-party and three-party authenticated dynamic dictionaries and apply these dictionaries to cryptocurrency ledgers.

A public ledger (blockchain) in a cryptocurrency needs to be easily verifiable. However, maintaining a data structure of all account balances, in order to verify whether a transaction is valid, can be quite burdensome: a verifier who does not have the large amount of RAM required for the data structure will perform slowly because of the need to continually access secondary storage. We demonstrate experimentally that authenticated dynamic dictionaries can considerably reduce verifier load. On the other hand, per-transaction proofs generated by authenticated dictionaries increase the size of the blockchain, which motivates us to find a solution with most compact proofs.

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 compressed together, reducing their total length by approximately an additional factor of 2.

We simulate blockchain verification, and show that our verifier can be about 20 times faster than a disk-bound verifier under a realistic transaction load.