zkLedger: Privacy-Preserving Auditing for Distributed Ledgers


Neha Narula, MIT Media Lab; Willy Vasquez, University of Texas, Austin; Madars Virza, MIT Media Lab


Distributed ledgers (blockchains) enable financial institutions to efficiently reconcile cross-organization transactions. For example, banks might use a distributed ledger as a settlement log for digital assets. Unfortunately, these ledgers are either entirely public to all participants, revealing sensitive strategy and trading information, or are private but do not support third-party auditing. Auditing and financial oversight are critical to proving institutions are complying with regulation.

This paper presents Auditable Private Ledgers (APL), a system that protects blockchain participants’ privacy and provides fast, provably correct auditing. Banks create digital asset transactions that are visible to only the organizations involved in the transaction, but are publicly verifiable. An auditor sends queries to banks, for example “What is the the outstanding amount of a certain digital asset on a bank’s balance sheet?” and gets a response and cryptographic assurance that the response is correct. APL has three important benefits over previous work: first, guarantees strong transaction privacy by hiding the \emph{transaction graph}, or linkages between transactions. Second, APL provides fast, rich auditing with a new proof scheme using Schnorr-type non-interactive zero-knowledge proofs. Unlike zk-SNARKs, our techniques do not require trusted setup and only rely on widely-used cryptographic assumptions. Third, APL uses a columnar ledger construction so that banks cannot omit transactions, and auditors can use rolling caches to verify answers quickly.

We implement an optimized distributed version of APL that can produce provably-correct answers to auditor queries on a transaction ledger with tens of thousands of transactions in less than 30 milliseconds.

@inproceedings {211273,
author = {Neha Narula and Willy Vasquez and Madars Virza},
title = {zkLedger: Privacy-Preserving Auditing for Distributed Ledgers},
booktitle = {15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18)},
year = {2018},
address = {Renton, WA},
url = {https://www.usenix.org/conference/nsdi18/presentation/narula},
publisher = {{USENIX} Association},