Commitment Scheme

The hiding property ensures the commitment value (the commitment) reveals no information about the original secret message. An adversary cannot distinguish between commitments to different messages. This is typically achieved using cryptographic hash functions or random blinding factors.

• Computational Hiding: Security relies on computational assumptions (e.g., discrete log).
• Perfect Hiding: Information-theoretic security; the commitment reveals zero information, even to a computationally unbounded adversary.

The binding property guarantees that once a commitment is published, the committer cannot change the underlying secret message. They are bound to the original value and cannot open the commitment to a different value later.

• Computational Binding: It is computationally infeasible to find two different messages that produce the same commitment.
• Perfect Binding: It is impossible (information-theoretically) to open a commitment to more than one value.

Different cryptographic constructions prioritize one property over the other, creating a trade-off.

• Hash-based (SHA-256): Computationally binding and hiding. Simple: commitment = H(secret || nonce).
• Pedersen Commitment: Used in confidential transactions. Offers perfect hiding and computational binding.
• ElGamal Commitment: Another discrete-log based scheme that can be configured for perfect hiding or perfect binding, but not both simultaneously.

A fundamental theorem states that a commitment scheme cannot be both perfectly hiding and perfectly binding. One property must be computational.

• Choice Determines Use Case:
  • Perfect Hiding, Computational Binding: Prioritizes secrecy of the committed value (e.g., voting, sealed-bid auctions).
  • Perfect Binding, Computational Hiding: Prioritizes immutability of the commitment (less common). Most practical schemes, like Pedersen commitments, opt for perfect hiding and computational binding.

Commitment schemes are a core building block for privacy and scalability.

• Confidential Transactions: Hide transaction amounts while proving they are valid (e.g., Mimblewimble).
• ZK-SNARKs / ZK-STARKs: The prover commits to a witness before generating a proof.
• Verifiable Random Functions (VRFs): Used in consensus (Algorand) and lotteries.
• Merkle Trees: A leaf commitment can be a hash commitment to data, with the root acting as a binding commitment to the entire set.

The properties are formally defined through security games between a challenger and an adversary.

• Hiding Game: The adversary chooses two messages. The challenger commits to one at random. The adversary must guess which message was committed to. Success probability should be negligibly better than 1/2.
• Binding Game: The adversary creates a commitment. They must then produce two valid opening pairs (different messages, same commitment) that verify. Success probability should be negligible. These games provide a rigorous framework for proving a scheme's security.

The simplest and most widely used type, where a commitment is the cryptographic hash of the secret value and a random nonce (or salt).

• Properties: Computationally binding, perfectly hiding (if the hash function is modeled as a random oracle).
• Example: commitment = SHA256(value || nonce). To reveal, the committer provides the original value and nonce.
• Use Case: The basis for many blockchain data structures like Merkle trees and simple on-chain commitments.

An information-theoretically hiding and computationally binding scheme based on elliptic curve cryptography.

• Properties: Perfectly hiding, meaning the commitment reveals zero information about the value, even to a computationally unbounded adversary.
• Mechanism: A commitment to value v is computed as C = v*G + r*H, where G and H are public generator points and r is a secret blinding factor.
• Use Case: Fundamental to confidential transactions (e.g., Monero, Mimblewimble) and various zero-knowledge proof systems where hiding is paramount.

A scheme that allows committing to a polynomial, enabling efficient proofs about its evaluations without revealing the polynomial itself.

• Properties: Enables succinct proofs (e.g., KZG commitments) where the proof size is constant, independent of the polynomial's degree.
• Key Operation: Allows a prover to generate a proof that a committed polynomial evaluates to a specific value at a given point.
• Use Case: Core building block for zk-SNARKs (e.g., in PLONK, Marlin) and data availability schemes like Ethereum's Proto-Danksharding (EIP-4844).

A commitment to an ordered list (vector) of values, with the ability to open the commitment at specific positions.

• Properties: Provides position binding, guaranteeing that an opened value corresponds to a specific index in the original vector.
• Examples: Merkle trees are a common form of vector commitment. More advanced schemes like RSA Accumulators offer constant-sized commitments and proofs.
• Use Case: Verifying element inclusion in a list, such as proving a transaction is in a block (Merkle proof) or credential revocation lists.

Schemes like Bulletproofs that allow committing to a vector of values and later proving complex statements about them in a single, short proof.

• Properties: Zero-knowledge and short proofs. The commitment size is logarithmic in the number of values committed.
• Core Ability: Enables efficient range proofs and proof of inner-product relations on committed vectors.
• Use Case: Confidential transactions with multiple inputs/outputs, verifying asset balances fall within a valid range without revealing them.

A verifiable secret sharing scheme that acts as a commitment with homomorphic properties.

• Properties: Allows a dealer to commit to a secret and distribute shares, with the commitment enabling verification that shares are consistent.
• Mechanism: Based on discrete logarithm assumptions. The commitment is a set of public parameters (g^s, h^s) derived from the secret s.
• Use Case: Secure multi-party computation (MPC) setups, distributed key generation (DKG), and threshold cryptography where participants must verify the correctness of shared secrets.

Every commitment scheme must satisfy two key properties:

• Hiding: The commitment value does not reveal any information about the original secret. It is computationally infeasible for an observer to guess the committed value.
• Binding: Once a commitment is made, the committer cannot change the original secret to a different value when they later reveal it. The commitment is cryptographically bound to the original input.

The simplest and most common form, where a cryptographic hash function (like SHA-256) is used. To commit to a value v, the committer calculates C = H(v, r), where r is a random nonce (salt). The commitment C is published. Later, to reveal, they publish v and r, allowing anyone to verify that H(v, r) equals C. This is binding due to hash function collision resistance and hiding due to the randomness of r.

An advanced, information-theoretically hiding scheme widely used in confidential transactions (e.g., Monero, Mimblewimble). It uses elliptic curve cryptography. A commitment to a value v is computed as C = v*G + r*H, where G and H are public generator points and r is a secret blinding factor. It is perfectly hiding—the commitment reveals zero information about v—and computationally binding under the discrete log assumption. Allows for homomorphic addition of commitments.

Commitment schemes are foundational for numerous blockchain features:

• Merkle Trees: Leaf nodes are commitments to data, and the root hash commits to the entire dataset.
• Zero-Knowledge Proofs (ZKPs): Used to commit to secret witness data before generating a proof (e.g., in zk-SNARKs).
• Scalability Solutions: Data availability schemes like Data Availability Sampling (DAS) in modular blockchains rely on commitments (e.g., KZG polynomial commitments) to prove data exists without publishing it fully.
• Randomness Generation: Commit-Reveal schemes are used in decentralized random beacons (e.g., RANDAO).

A specialized scheme crucial for modern ZK-Rollups and Proto-Danksharding (EIP-4844). It allows a prover to commit to a polynomial P(x) with a single elliptic curve point. The committer can later generate a short proof that P(z) = y for a given point z (an evaluation proof). Key properties include:

• Constant-sized commitments and proofs.
• Support for batch verification.
• Required trusted setup, which is a significant cryptographic ceremony to generate initial parameters.

A two-phase protocol pattern built on top of a commitment scheme, used to prevent front-running and ensure fairness.

1. Commit Phase: All participants submit a commitment (e.g., H(secret_value)) to the network.
2. Reveal Phase: After a deadline, participants must reveal their original secret_value. The protocol only accepts reveals that match a previously submitted commitment.

This ensures choices (like votes or random numbers) are made before they are known, preventing last-second manipulation. Used in blockchain voting, auctions, and random number generation.

A cryptographic method where one party (the prover) can prove to another (the verifier) that a statement is true without revealing any information beyond the validity of the statement itself. They are often built on top of commitment schemes to hide the committed data while proving properties about it.

• Key Use: Enables privacy and scalability in blockchains (e.g., zk-SNARKs, zk-STARKs).
• Relation to Commitments: The prover often commits to a witness using a commitment scheme before generating the proof.

A hierarchical data structure that uses cryptographic hashes to efficiently and securely verify the contents of large datasets. A Merkle root acts as a single, short commitment to the entire dataset.

• How it Works: Data blocks are hashed, then paired and hashed repeatedly up to a single root hash.
• Key Property: Provides collision resistance and enables efficient proofs of inclusion (Merkle proofs).
• Blockchain Use: Fundamental for verifying transaction inclusion in blocks (Bitcoin, Ethereum).

Cryptographic functions that map data of arbitrary size to a fixed-size output (a hash or digest). They are the core engine for most commitment schemes, providing the binding and hiding properties.

• Properties for Commitments:
  • Pre-image Resistance: Hiding – cannot find the input from the output.
  • Collision Resistance: Binding – cannot find two different inputs with the same output.
• Common Algorithms: SHA-256, Keccak-256 (used in Ethereum), Blake3.

A cryptographic primitive that produces a pseudorandom output and a proof that the output was correctly computed from a given input and secret key. The output is deterministic yet verifiably random.

• Key Properties:
  • Uniqueness: Only one valid output for a given input/key pair.
  • Pseudorandomness: Output is indistinguishable from random.
• Relation to Commitments: Often used in consensus mechanisms (e.g., Algorand, Cardano) to select leaders fairly and verifiably, akin to committing to a random seed.

A mathematical scheme for verifying the authenticity and integrity of digital messages or documents. They provide non-repudiation—the signer cannot deny having signed.

• Core Mechanism: Uses a private key to sign and a corresponding public key to verify.
• Relation to Commitments: While distinct, they are often used together. A party can commit to a value and later sign the opening to prove they created the commitment (e.g., in blind auctions or voting).
• Common Schemes: ECDSA (Bitcoin/Ethereum), EdDSA.

A specific type of homomorphic commitment scheme based on elliptic curve cryptography. It allows for mathematical operations on committed values without opening them.

• Key Feature: Additive Homomorphism: The commitment to (x1 + x2) equals the product of commitments to x1 and x2. This enables private computations.
• Property: Information-theoretically hiding and computationally binding under the Discrete Log assumption.
• Primary Use: Foundational for confidential transactions (Monero, Mimblewimble) and many zero-knowledge protocols.