About Me:
–My main research focusses on the science of blockchains using tools from applied cryptography, game theory and consensus. I get most excited about problems that both require novel theoretical insights and also have realworld applications.
–I am an Assistant Professor in Computer Science at NYU Courant
–I am a cofounder and chief scientist of Espresso Systems.
–You can find my CV (might be outdated) here.
Teaching
–I am teaching a course on the cryptography of blockchains at NYU in the Spring 2024 semester. You can find the course material here
Publication Highlights
–Ph.D. Thesis Improving the Privacy, Scalability, and Ecological Impact. You can find my defense talk here, and find a video of my job talk here.
–Bulletproofs is a zeroknowlede proof system that has extremly short proofs while requiring minimal trust assumptions. It is general purpose but specificially designed for confidential blockchain transactions. Bulletproofs is deployed on multiple blockchains and secures tens of thousands of private transactions on blockchains like Monero or Mobilecoin.
–Verifiable Delay Functions or VDFs are functions that take a long time to evaluate but are efficient to verify. VDFs have many applications and are a key building block for enviormentally friendly consensus mechanisms. They are being used in blockchain systems like Chia and Filecoin and are a part of the Ethereum 2.0 design. The VDF alliance is an industry alliance focussed on building VDF hardware.
–HyperPlonk is a SNARK that is specifically designed for proving large complex statements. It removes the requirment for FFTs which makes HyperPlonk more scalable and parallelizable. It also enables highdegree custom gates for complex circuits, such as ZKEVMs.
Publications (Google Scholar):
Cryptography and Cryptocurrencies
 Authors

B. Bünz, Pratyush Mishra, Wilson Nguyen, William Wang

Paper
 TLDR
 We build an accumulation scheme that does not require homomorphism but can be built from hashfunctions and errorcorrecting codes.
 Authors

B. Bünz, Jessica Chen

Paper
 TLDR We build an accumulation scheme for read and write operations that only requires committing to 612 elements per read and write, independent of the memory size. This yields an efficient IVC scheme with the same parameters. Along the way we also build an accumulation scheme for GKR that can be used to outsource determnistic computations without committing to the intermediate results of the computation.
 Authors

B. Bünz, Binyi Chen
 Paper (To appear at ASIACRYPT 2023)
 TLDR
 ProtoStar is an Incrementale Verifiable Computation Scheme based on the [accumulation](#wacc)/folding approach. It is constructed using a general, but highly efficient recipe for constructing accumulation schemes from any specialsound, algebraic protocol. It enables the use of highdegree gates and lookups, all while requiring only 3 elliptic curve scalar multiplication inside the recursive circuit.
 Authors

Binyi Chen, B. Bünz, Dan Boneh, and Zhenfei Zhang
 Paper (Published at EUROCRYPT 2023)
 Talk at ZK Summit
 Slides
 TLDR
 Plonk is a recently developed proof system that has received a lot of attention due to its efficienct, low trust assumption, and customizability. We significantly improve on Plonk by building Hyperplonk. Hyperplonk removes the costlies component of Plonk (Fast Fourier Transforms). It also adds the ability to build proofs for circuits with highdegree custom gates.
 Authors

Alex Xiong, Binyi Chen, Zhenfei Zhang, B. Bünz, Ben Fisch, Fernando Krell, and Philippe Camacho
 Paper (To appear at CCS 2023)
 TLDR
 Traditional blockchain systems execute program state transitions onchain, requiring each network node participating in statemachine replication to recompute every step of the program when validating transactions. This limits both scalability and privacy. Recently, Bowe et al. introduced a primitive called decentralized private computation (DPC) and provided an instantiation called ZEXE, which allows users to execute arbitrary computations offchain without revealing the program logic to the network. Moreover, transaction validation takes only constant time, independent of the offchain computation. However, ZEXE required a separate trusted setup for each application, which is highly impractical. Prior attempts to remove this perapplication setup incurred significant performance loss. We propose a new DPC instantiation VERIZEXE that is highly efficient and requires only a single universal setup to support an arbitrary number of applications. Our benchmark improves the stateoftheart by 9x in transaction generation time and by 3.4x in memory usage. Along the way, we also design efficient gadgets for variablebase multiscalar multiplication and modular arithmetic within the plonk constraint system, leading to a Plonk verifier gadget using only ∼ 21k plonk constraints.
 Authors (alphabetical)

B. Bünz, Ben Fisch
 Paper (Published at TCC 2023)
 TLDR

The famous SchwartzZippel Lemma bounds the probability that a nonzero multivariate polynomial over a field evaluates to 0 at a random point. We prove an extension of the lemma that holds modulo a composite. The lemma applies to multilinear polynomials that are coprime with the modulus. We then use the lemma to prove that a lattice version of Bulletproofs is secure and the same proof also closes a crucial gap in the security proof of DARK.
 Authors (alphabetical)

B. Bünz, Y. Hu,Shin’ichiro Matsuo, E. Shi
 Paper (preprint)
 TLDR
 We built upon the recent work by Shi and Wu to build a noninteractive anonymour router. A noninteractive untrusted router receives n encrypted ciphertexts and converts them to n transformed ciphertexts that can be decrypted by a set of receivers. The ciphertexts are shuffled according to a permutation that is determined in a onetime trusted setup. We show that with a relaxed differentially private security notion a noninteractive router can be achieved with subquadratic router work.
 Authors (alphabetical)

B. Bünz, A. Chiesa, W. Lin, P. Mishra and N. Spooner
 Paper (Published at CRYPTO 2021)
 Talk at CRYPTO
 Slides
 TLDR
 Proofcarrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct noninteractive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme for their proofs. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any noninteractive argument of knowledge (e.g., with linearsize proofs) that has a split accumulation scheme, which is a weak form of accumulation that we introduce. We additionally construct a transparent noninteractive argument of knowledge for R1CS whose accumulation is verifiable via a constant number of group and field operations. This leads, via the random oracle heuristic and our result above, to efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for a simple polynomial commitment scheme based on Pedersen commitments. Our results are supported by a modular and efficient implementation.
 Authors (alphabetical)

B. Bünz, M. Maller, P. Mishra, Nirvan Tyagi and Psi Vesely
 Paper (Published at ASIACRYPT 2021)
 Talk at Simons Institute
 Slides
 Implementation
 TLDR
 We present several proof systems (innner pairing products) for proving algebraic relations over pairing equations. These proof systems efficiently allow a prover to show that committed group elements satisfy certain bilinear (pairing) equalities. We present them as a generalization of the innerproduct argument of Bulletproofs. We specialize and optimize them for several highly relevant applications. Firstly, we built the first succinct polynomial commitment scheme where the evaluation prover only has additive overhead over evaluating the polynomial. The commitment scheme has both a transparent variant with square root verifier time and one with universal updatable setup with logarithmic verifier time. As described in the DARK paper polynomial commitments can be used to build general purpose SNARKS. Additionally, we show that the inner pairing product can be used to efficiently outsource the verification of pairing equations such as BLS signatures. A prover can give a short proof that n BLS signatures are correct and the verifier can check this proof using 2n group exponentiations but only one expensive pairing. This protocol can be used in a blockchain where a block contains many signatures and fast verification of the block is vital. Finally, we use a variant of the inner pairing product to aggregate n pairing based SNARKs such as Groth 16 into a logarithmic sized proof. Verifiying this batched proof only takes O(log(n)) time. Aggregating SNARKs could only previously be achieved through expensive recursive proof techniques and NP reductions. The Inner Pairing Product on the other hand is fully algebraic and does not rely on expensive NP reductions.
 Authors (alphabetical)

B. Bünz, A. Chiesa, P. Mishra and N. Spooner
 Paper (Published at TCC 2020)
 Talk by Nick at BU
 Slides
 TLDR
 We present a new cryptographic tool called an accumulation scheme for proof systems (unrelated to set accumulators). An accumulation scheme for a predicate (such as proof verification) enables the accumulation of multiple invocations of the predicate and old accumulators into a new accumulator. Checking that the accumulation was done correctly is ideally much cheaper than deciding the predicate itself. In the end a decider can determine whether the final accumulator is valid and if so this implies that all accumulated predicate checks were valid. Together this enables delaying and combining expensive checks. This is particularly useful as we show that accumualtion schemes can be used to build very efficient recursive proofs. This approach was proposed by Bowe, Grigg and Hopwood in recent work called [Halo](eprint.iacr.org/2019/1021). We formalize and prove correctness of this approach. We also show that a variant of the accumulation scheme from Halo and an accumulation scheme based on bilinear maps satisfy our definitions and are secure. The resulting recursive proof constructions have significant new efficiency and security features.
 Authors (alphabetical)

B. Bünz, [Ben Fisch](https://sites.google.com/site/benafisch/) and A. Szepieniec
 Paper (Published at Eurocrypt 2020)
 Talk at Simons Institute
 Slides
 TLDR
 We present a new polynomial commitment scheme from groups of unknown order with logarithmic proof size and logarithmic verifier time. Plugged into proof systems like Sonic, Plonk or Marlin this leads to SuperSonic a SNARK with 10KB proofs and without trusted setup! This is the shortest practical SNARK without trusted setup today. We also provide an abstraction for proof systems like Sonic et al. called polynomial IOPs. We show that using a polynomial commitment scheme (such as DARKs) they can be compiled to SNARKs. Moreover all of the cryptographic assumptions and trusted setup assumptions (or lack thereof) are in the polynomial commitment scheme.
 Authors
 Paper (Published at IEEE S&P (Oakland) 2020)
 Talk at Zcon
 Slides
 TLDR
 We present Flyclient which is a protocol that lets a superlight client determine which is the correct (longest) proof of work chain. The client only needs to download a logarithmic number of block headers (say 200 instead of 1 million). The protocol is a noninteractive proof of proof of work (NiPoPoW) that shows that a chain has at least x amount of work put into it. It uses a random sampling of block headers to ensure that an adversary with limited mining power could not have produced this chain.
 Authors (alphabetical)

D. Boneh, B. Bünz and [Ben Fisch](https://sites.google.com/site/benafisch/)
 Paper (Published at Crypto 2019)
 Talk at Scaling Bitcoin 18
 Slides Technical Slides
 TLDR
 Accumulators are short commitment to a set that support efficient inclusion and exclusion proofs. We present several new batching techniques for accumulators and positional vector commitments in group of unknown order. Our techniques can be used in a stateless blockchain design where all users and miners only require a constant amount of storage. We also present a new vector commitment which can significantly reduce the proof size of IOP instantiations, such as STARKs.
 Authors

B. Bünz, S. Agrawal, M. Zamani and D. Boneh
 Paper (Published at FC 2020)
 Slides
 TLDR
 We propose Zether, a private payment mechanism that is compatible with Ethereum and other accountbased payment systems. Zether can provide both confidentiality (by hiding payment amounts) and anonymity (by hiding the identities of senders and recipients). Zether is designed to be interoperable with arbitrary smart contracts to support applications such as sealedbid auctions, private payment channels, stake voting, and confidential proofofstake. Zether uses an extension to Bulletproofs called SigmaBullets which combines Bulletproofs with Sigma protocols.
 Authors (alphabetical)

D. Boneh, J.Bonneau, B. Bünz and Ben Fisch](https://sites.google.com/site/benafisch/)
 Paper (Published at CRYPTO 2018)
 Talk by Ben Fisch at Crypto 2018
 TLDR
 We introduce verifiable delay functions (VDFs) which have 3 key properties: They are a functions so for every input there is a unique output. Evaluation incurs a delay, i.e. it takes a significant amount of time even on a highly parallel machine. VDFs are verifiable such that given a proof a verifier can efficiently check that the VDF was evaluated correctly. VDFs have many applications from randomness beacons to proofs of replication and cointossing.
 Authors

B. Bünz, J. Bootle, D. Boneh, Andrew Poelstra, Pieter Wuille and Greg Maxwell
 Paper (Published at IEEE S&P (Oakland) 2018)
 Talk at IEEE S&P
 Slides
 Implementations
 TLDR
 Confidential transactions are Bitcoin transactions which are publicly verifiable but do not reveal the amounts that are transferred. They rely on cryptographic commitments and so called zeroknowledge proofs of knowledge. We present a new kind of zeroknowledge proof which is much more efficient and can be used to drastically reduce the size of confidential transactions. On a more technical note bulletproofs are noninteractive zero knowledge proofs without trusted setup and with only logarithmic proof size. Proving and verification cost are linear with low constant overhead.
 Authors
 Paper (Published at CCS 2015)
 Talk at Next Context Conference
 Implementations
 Blog by Joseph Bonneau
 TLDR
 How can a Bitcoin exchange proof that they have enough funds to satisfy all their customers demands without revealing the customers balances, the bitcoin addresses they control or even the total amount of bitcoin they have.
 Authors

B. Bünz, S. Goldfeder, J. Bonneau
 Paper
 Talk at CESC
 Slides
 Code
 TLDR
 We show how one can generate an unpredictable randomness beacon that is publicly verifiable using a blockchain. The beacon can be used to verify the correct execution of randomized algorithms such as lotteries. The novel property of the beacon is that it is publicly verifiable in that a verifier is convinced that the beacon was unpredictable even if she did not partake in the generation of the beacon and without any trust assumptions. We also show how we can enable interactive verification using an efficient smart contract.
Game Theory (Combinatorial Auctions)
 Authors
 Paper (Published at AAAI 2015)
 Slides
 TLDR
 We significantly improve on the current state of the art algorithm for computing combinatorial auctions. These auctions were multiple related goods are sold in the same auction are for example used to allocated spectrum to cellular companies around the world. These auctions often generate billions of dollars in revenue but are often limited to a small number of bidders and goods. Faster algorithms for computing their outcome will enable larger scale applications.
 Authors

V. Bosshard, B. Bünz, B. Lubin, S. Seuken
 Paper (Published at IJCAI 2017)
 TLDR
 We design several new techniques for quickly computing bayes nash equilibria for combinatorial auctions.
Artificial Intelligence
 Authors

D. Selsam, M. Lamm, B. Bünz, P. Liang, L. de Moura,D. Dill
 Paper (To appear at ICLR 2019)
 Talk by Daniel Selsam at Microsoft Research
 [Code](https://github.com/dselsam/neurosat)
 TLDR
 We develop a neural network based solver for finding satisfying assignments to boolean formulas (SAT solver). At training time the network is given satisfying formulas and only the information of whether the formula has a solution or not. Despite this minimal supervision we are able to directly read of satisfying assignments from the activations of the network if it classifies a formula as satisfiable. Additionally we can even find contradictions if the formula is unsatisfiable. Given that classifying boolean formulas is an NPcomplete problem this an interesting exploration into the abilities and flexibilities of neural network and also raises interesting possibilities of using neural networks in the development of state of the art SAT solvers.