Zero Knowledge Proofs with Bulletproof

    2024, Aug 13

    [TOC]

    Bulletproofs have been developed in 2017 by a Stanford Applied Cryptography Group composed of Jonathan Bootle (University College London), Benedict Bunz (Stanford University), Dan Boneh, Andrew Poelstra, Pieter Wuille and Greg Maxwell.

    This protocol is defined in this specification paper: Bulletproofs: Short Proofs for Confidential Transactions and More

    Bulletproofs are short non-interactive zero-knowledge proofs (NIZK) that:

    • require no trusted setup.
    • Work with any Elliptic Curve such as Ristretto
    • The verifier cost scales linearly with the computation size.

    A bulletproof can be used to convince a verifier that:

    • an encrypted plaintext is well formed.
    • an encrypted number is in a given range, without revealing anything else about the number.

    Reference: Bulletproofs - Dimitry Khovratovich

    General presentation

    According to the Stanford presentation, Bulletproofs

    • Shrink the size of the cryptographic proof from over 10kB to less than 1kB.
    • Support proof aggregation, so that proving that m transaction values are valid adds only O(log(m)) additional elements to the size of a single proof.

    Overview

    Pros

    +: Compared to SNARKs, Bulletproofs require no trusted setup, like zkSTARKs.

    +: they are smaller than zkSTARKs

    +: batch verification available

    +: They require no interaction between prover and verifier since they are non-interactive zero-knowledge proofs

    Cons

    -: verifying a bulletproof is more time consuming than verifying a SNARK proof.

    -: linear verification time (O(N))

    -: No post-quantum secure (based on discrete log)

    Reference: crypto.stanford.edu - bulletproofs/, academy.bit2me - What are Bulletproofs?

    Applications and use-case

    Bulletproofs have many other applications in cryptographic protocols:

    • Shortening proofs of solvency
    • Short verifiable shuffles,
    • Confidential smart contracts / transactions,
    • Created range proof on committed values (p.1)
      • they enable proving that a committed value is in a range using only 2log2(n)+9 group and field elements, where n is the bit length of the range. Proof generation and verification times are linear in n.
    • A general replacement for Sigma-protocols, which are 3 phase protocols for proving knowledge of values without disclosing the values themselves.

    Bitcoin

    If all Bitcoin transactions were confidential and used Bulletproofs, then the total size of the UTXO set would be only 17 GB, compared to 160 GB with the currently used proofs according to the group behind Bulletproof, see crypto.stanford.edu - bulletproofs/

    MPC protocol

    Bulletproofs can be combined with a MPC protocol to aggregate proofs from multiple parties. Through a simple MPC protocol, the different parties can generate a single proof without revealing their inputs for constructing Bulletproofs.

    In this video from Stanford University, Benedikt Bünz has presented an overview of such architecture:

    • Custom MPC to generate proofs
    • Works if circuits are disjoint, e.g n range proofs for n provers
    • Simply aggregate proofs in each round and compute Fiat-Shamir challenge
    • Either log(n) rounds and log(n) communication

    Implementation details

    • They rely on the Discrete Logarithm assumption. This means that given an output, it is not possible to compute the input used (one-way computation). This also means that these proofs are probably not post quantum resistant since problems relying on the discrete logarithm are not

    • They are made non-interactive using the Fiat-Shamir Heuristic. This algorithm creates a digital signature based on an interactive zero-knowledge proof, converting thus this proof to a non-interactive one.

    • They use an efficient algorithm to calculate an inner-product argument for two independent (not related) binding vector Pedersen Commitment.

      What is the inner product ? It is the component by component product of two vector. it is a generalization of the dot product in a vector space: a way to multiply vectors together, with the result of this multiplication being a scalar. References: tlu.tarilabs.com - the bulletproof protocols, dankradfeist.de - Inner Product Arguments, mathworld.wolfram.com - InnerProduct

    Reference:

    Use

    Monero

    A use-case of bulletproofs is in confidential transactions. Notably, Monero, a privacy focus chain, uses them to power its RingCT technology. They switched from using Schnorr signatures and Borromean ring signatures to lightweight bulletproofs. The initial ring signatures were effective, but they increased the size of an average RingCT exponentially.

    Monero has made some improvement to Bulletproof with a new range-proving system called Bulletproofs+. When you transfer coins on the Monero blockchain, for instance, Bulletproofs+ proves that your payment is a positive number without revealing how much you paid.

    References:getmonero.org - Bulletproofs+ in Monero, panther - Bulletproofs In Crypto – An introduction to a Non-Interactive ZKP

    Mimblewimble

    MimbleWimble is a blockchain solution designed for Confidential Transactions, where the transaction addresses and amounts are hidden, providing a high level of privacy for blockchain users.

    • Validators in MimbleWimble only store Unspent Transaction Outputs (UTXOs) instead of the entire transaction history for the blockchain, enabling space savings and faster sync.
    • The design of MimbleWimble relies on Elliptic Curve Cryptography, which is easy to understand and audit.

    A Mimblewimble blockchain relies on two complementary aspects to provide security:

    • Pedersen Commitments to provide perfectly hiding and computationally binding commitments.
    • Range proofs (in the form of Bulletproof range proofs) : it would only grow with the number of transactions that have unspent outputs, which is much smaller than the size of the UTXO set. Range proofs assures that all values are positive and not too large

    Reference: Confidential Assets on MimbleWimble tarilabs -Mimblewimble, What consensus algorithm is MimbleWimble/Grin using? Does it use Zero Knowledge Proofs as well?

    Implementation

    • MimbleWimble Extension Blocks (MWEB) is the MimbleWimble implementation on Litecoin.
    • Grin is an in-progress implementation of the Mimblewimble protocol.
    • beam is a mimblewimble L1 privacy blockchain, completely concealing transactions
    • Epic Cash is a MimbleWimble blockchain implementation that yields advances in scalability as a result of space efficient design that sheds redundant transaction data.

    Bulletproof Commitment Scheme

    Not sure this term (“Bulletproof Commitment Scheme) is very common but the goal is to refer to the way Bulletproofs can be used with commitments. A commitment scheme allows one to commit to a value while keeping it hidden, with the ability to reveal it later.

    In this case, the scheme relies on Pedersen commitments, which allow zero-knowledge verification of values using a mathematical trick. This can be used in a utxo blockchain like Monero to reveal that the sum of the inputs is of a greater value than the sum of the outputs without disclosing any of the values.

    A Pedersen commitment (C) uses a point on an elliptic curve to create a one-way function. A Pedersen commitment to a value v is of the form C = vG + sQ, where G and Q are known generator points on an elliptic curve, and s is a secret blinding factor.

    Key Characteristics:

    • Binding: Once a value is committed, the committer cannot change it.
    • Hiding: The committed value remains hidden from others until it is revealed.
    • Use with Bulletproofs: When combined with Bulletproofs, the commitment scheme allows proving properties about the committed values (e.g., range proofs) efficiently and privately.

    Applications: Used in confidential transactions to commit to transaction amounts and then use Bulletproofs to prove that these amounts are within a certain range without revealing the amounts themselves.

    Reference: zk-learnin.org - Polynomial Commitments based on Pairing and Discrete Logarithm, p.40, blog.rachitasrivastava - Bulletproof Commitment Schemes: Integrating Cryptography and Mathematics, RareSkills - What are Pedersen Commitments and How They Work

    This summary is taken from the project Awesome zero knowledge proofs (zkp) by Matter labs:

      SNARKs STARKs Bulletproofs
    Used by Zcash, ZkSync StarkWare Monero
    CRS Size* n 0 n
    Algorithmic complexity: prover O(N * log(N)) O(N * poly-log(N)) O(N * log(N))
    Algorithmic complexity: verifier ~O(1) O(poly-log(N)) O(N)
    Communication complexity (proof size) ~O(1) O(poly-log(N)) O(log(N))
    - size estimate for 1 TX Tx: 200 bytes, Key: 50 MB 45 kB 1.5 kb
    - size estimate for 10.000 TX Tx: 200 bytes, Key: 500 GB 135 kb 2.5 kb
    Ethereum/EVM verification gas cost ~600k (Groth16) ~2.5M (estimate, no impl.) N/A
    Trusted setup required? ☑ ☒ ☒
    Post-quantum secure ☒ ☑ ☒
    Crypto assumptions DLP + secure bilinear pairing Collision resistant hashes Discrete log

    *Reference: eprint.iacr.org/2019/099.pdf, page 3

    Other reference used: ethereum.stackexchange - zk-SNARKs vs. Zk-STARKs vs. BulletProofs? (Updated)

    Known implementation

    From Matter labs - awesome-zero-knowledge-proofs and crypto.stanford.edu/bulletproofs/

    References

    Feel free to contact me on
    # ethereum # solidity # security # code4Arena

    Share button

    You might also enjoy

    Hypergraph and Hypertree - Overview

    Tornado Cash Circuits - Overview

    Recurrent Neural Networks (RNNs) - Overview