VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries

Rust implementation of the VeRSA family of verifiable registries

ACM CCS 2022: Nirvan Tyagi, Ben Fisch, Andrew Zitek, Joseph Bonneau, Stefano Tessaro. VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries. ACM CCS 2022.

ePrint (full version): Nirvan Tyagi, Ben Fisch, Andrew Zitek, Joseph Bonneau, Stefano Tessaro. VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries. Cryptology ePrint Archive, Report 2021/627. https://eprint.iacr.org/2021/627. 2021.

Overview

This repository is organized as a Rust workspace with a number of modular packages. The following packages make up the core of the implementation for the VeRSA verifiable registries:

• crypto_primitives: Implementation of various helper cryptographic primitives.
  • sparse_merkle_tree: Implementation and constraints for a sparse Merkle tree.
• rsa: Implementation of RSA primitives and constraints.
  • bignat: Wrapper around rug crate for integer arithmetic using GMP and constraints ported from bellman-bignat (implementing optimizations from xJsnark).
  • hog: Implementation and constraints for RSA groups of hidden order.
  • hash: Implementation and constraints for hash-to-integer and hash-to-prime using optimized Pocklington certificate circuit encodings ported from bellman-bignat.
  • poker: Implementation and constraints of the generalized proof of knowledge of exponent representation for integers proposed by [BBF19].
  • kvac: Implementation of RSA-based key-value commitment originally proposed by [AR20] with extensions from VeRSA.
• single_step_avd: Interface for authenticated dictionary along with various implementations.
  • merkle_tree_avd: Implementation and constraints for an authenticated dictionary from a sparse Merkle tree (with open addressing optimization).
  • rsa_avd: Implementation and constraints for an authenticated dictionary from an RSA key-value commitment.
• full_history_avd: Interface for authenticated history dictionary along with various implementations.
  • history_tree: Implementation and constraints for a vector commitment from a sparse Merkle tree.
  • recursion: Implementation of an authenticated history dictionary using SNARK recursion.
  • aggregation: Implementation of an authenticated history dictionary using SNARK aggregation [BMMTV21].
  • rsa_algebraic: Implementation of an authenticated history dictionary using algebraic update proofs for an RSA authenticated dictionary.

We provide a number of tests and benchmarks which we expand on below. Benchmarks are co-located in a separate package while tests are interspersed across the above packages.

• benches: Microbenchmarks for VeRSA authenticated history dictionaries.

We also evaluate the costs of running a public bulletin board via a smart contract on Ethereum (or any blockchain supporting EVM).

• bulletin_board: Smart contracts and benchmarks for publishing digests to the blockchain.
• ethereum_test_utils: Helper methods for compiling solidity and benchmarking gas costs.

Lastly, the above implementations for authenticated (history) dictionaries store state in-memory using standard Rust structs. We implement a storage interface allowing for the data structures to store state persistently in an external database like Redis in an experimental branch storage-layer.

Installation/Build

The packages and benchmarks are easy to compile from source. The following sequence of commands may be helpful especially if on a fresh machine. A Dockerfile has also been provided which will run the equivalent of these commands and spin up an instance of Ubuntu.

Install basic prerequisites and dependencies:

apt update && apt install -y curl
apt install git m4 z3 cmake libboost-all-dev build-essential

Install rust using any method (Rust offical installation site):

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
source "$HOME/.cargo/env"

Clone the repository:

git clone https://github.com/nirvantyagi/versa.git
cd versa/

Build using cargo:

cargo build

Tests and Benchmarks

The versa packages come with a suite of tests and benchmarks.

Running Tests

To run the tests:

cargo test

Some expensive tests have been omitted from the default test run. To run an expensive test, specify it by name as follows:

cargo test name_of_expensive_test --release -- --ignored --nocapture

Running Benchmarks

To run a benchmark:

cargo bench --bench name_of_benchmark -- [--optional-arg arg1 arg2...]

We provide the following benchmarks:

• update_epoch_0_mt: Cost to prove and verify update from epoch 0 to 1 for registries based off of Merkle tree authenticated dictionaries.
• update_epoch_0_rsa: Cost to prove and verify update from epoch 0 to 1 for registries based off of RSA authenticated dictionaries.
• aggregate_rsa: Cost to prove and verify algebraic update proof for RSA authenticated dictionary.
• aggregate_groth16: Cost to prove and verify Groth16 SNARK aggregation.
• compute_witnesses_rsa: Cost to compute witness proofs for all entries in RSA authenticated dictionary.
• update_witness_rsa: Cost to maintain witness for RSA authenticated dictionary over many dictionary updates.
• verify_witnesses_rsa: Cost to verify witness for RSA authenticated dictionary.
• update_merkle_tree: Cost to prove update from epoch 0 to 1 for baseline Merkle tree authenticated dictionary without efficient history.
• verify_merkle_paths: Cost to verify update from epoch 0 to 1 for baseline Merkle tree authenticated dictionary without efficient history.