Presented at the 15th USENIX Symposium on Networked Systems Design and Implementation in 2018

Abstract

Distributed ledgers (e.g. blockchains) enable financial in- stitutions to efficiently reconcile cross-organization trans- actions. 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, re- vealing sensitive strategy and trading information, or are private but do not support third-party auditing without revealing the contents of transactions to the auditor. Au- diting and financial oversight are critical to proving insti- tutions are complying with regulation.

This paper presents zkLedger, the first system to protect ledger participants’ privacy and provide fast, provably cor- rect auditing. Banks create digital asset transactions that are visible only to the organizations party to the transac- tion, but are publicly verifiable. An auditor sends queries to banks, for example “What is the outstanding amount of a certain digital asset on your balance sheet?” and gets a response and cryptographic assurance that the re- sponse is correct. zkLedger has two important benefits over previous work. First, zkLedger 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. Second, zk- Ledger provides completeness; it uses a columnar ledger construction so that banks cannot hide transactions from the auditor, and participants can use rolling caches to produce and verify answers quickly. We implement a dis- tributed version of zkLedger that can produce provably- correct answers to auditor queries on a ledger with a hundred thousand transactions in less than 10 millisec- onds.