Computational Integrity and Privacy

Lack of auditability or inaccurate results from auditing can have devastating effects as demonstrated by the 2008 financial crisis. zkLedger combines techniques from modern cryptography to analyze private data, while ensuring the integrity of that analysis.

We propose a new form of proof systems: zk-SHARKs (zero-knowledge Succinct Hybrid ARguments of Knowledge). These combine the fast verification of zk-SNARKs with the no-trusted-setup of some non-succinct NIZKs.

A zk-SHARK has two verification modes: a prudent mode (relying on a uniform random string), and an optimistic mode (relying on a structured reference string).

Crucially, even complete corruption of the setup used by optimistic verification does not invalidate the prudent verification.

Moreover, old “prudent proofs” can be re-accelerated with a new optimistic mode setup (in case the old setup becomes unconvincing or compromised).

We propose a construction of zk-SHARKs, tailored for efficiency of both modes: it is competitive with both state-of-the-art SNARKs (in terms of prover and verifier time) and NIZKs (in terms of proof size). Our zk-SHARK construction acieves all three properties outlined above.

We also discuss the applicability to transaction and block verification in blockchain applications.

The US federal court system is exploring ways to im- prove the accountability of electronic surveillance, an opaque process often involving cases sealed from public view and tech companies subject to gag orders against informing surveilled users. One judge has proposed pub- licly releasing some metadata about each case on a papercover sheet as a way to balance the competing goals of (1) secrecy, so the target of an investigation does not dis- cover and sabotage it, and (2) accountability, to assure the public that surveillance powers are not misused or abused.

Inspired by the courts’ accountability challenge, we illustrate how accountability and secrecy are simultane- ously achievable when modern cryptography is brought to bear. Our system improves configurability while pre- serving secrecy, offering new tradeoffs potentially more palatable to the risk-averse court system. Judges, law enforcement, and companies publish commitments to surveillance actions, argue in zero-knowledge that their behavior is consistent, and compute aggregate surveil- lance statistics by multi-party computation (MPC).

We demonstrate that these primitives perform effi- ciently at the scale of the federal judiciary. To do so, we implement a hierarchical form of MPC that mir- rors the hierarchy of the court system. We also de- velop statements in succinct zero-knowledge (SNARKs) whose specificity can be tuned to calibrate the amount of information released. All told, our proposal not only offers the court system a flexible range of options for en- hancing accountability in the face of necessary secrecy, but also yields a general framework for accountability in a broader class of secret information processes.

ClockWork is a practical exchange protocol which gives an exchange the ability to prove to a user that it did not front-run their order. In ClockWork, users commit to and encrypt orders inside a timelock puzzle. By assuming a lower bound on the time it takes to solve the puzzle, we ensure that no one, including the exchange, can submit new orders or selectively drop orders after the batch is fixed, and that users cannot repudiate committed orders.Users interacting with the exchange are convinced that the exchange did not front-run, and the protocol creates a transcript between the exchange and the users that serves as evidence orders were matched correctly and has attestations from users who agree they were not front-run.Despite using computationally expensive timelock puzzles, ClockWork provides reasonable performance for batch auctions.