Bulletproof

Bulletproofs form part of the family of distinct Zero-knowledge Proof systems, such as Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARK); Succinct Transparent ARgument of Knowledge (STARK); and Zero Knowledge Prover and Verifier for Boolean Circuits (ZKBoo). Zero-knowledge proofs are designed so that a prover is able to indirectly verify that a statement is true without having to provide any information beyond the correctness of the statement, e.g. to prove that a number is found that solves a cryptographic puzzle and fits the hash value without having to reveal the Nonce

The Bulletproofs technology is a Non-interactive Zero-knowledge (NIZK) proof protocol for general Arithmetic Circuits with very short proofs (Arguments of Knowledge Systems) and without requiring a trusted setup. They rely on the Discrete Logarithm (DL) assumption and are made non-interactive using the Fiat-Shamir Heuristic. The name “Bulletproof” originated from a non-technical summary from one of the original authors of the scheme’s properties: “Short like a bullet with bulletproof security assumptions”

Bulletproofs also implement a Multi-party Computation (MPC) protocol, whereby distributed proofs of multiple provers with secret committed values are aggregated into a single proof before the Fiat-Shamir challenge is calculated and sent to the verifier, thereby minimizing rounds of communication. Secret committed values will stay secret.

The essence of Bulletproofs is its inner-product algorithm originally presented by Groth and then further refined by Bootle et al. The latter development provided a proof (argument of knowledge) for two independent (not related) binding vector Pedersen Commitments that satisfied the given inner-product relation. Bulletproofs build on these techniques, which yield communication-efficient, zero-knowledge proofs, but offer a further replacement for the inner product argument that reduces overall communication by a factor of three.