Bit Commitment

A bit commitment scheme is a two-phase protocol between a committer and a verifier. In the commit phase, the committer locks in a secret bit b by sending an encrypted or hashed value, called the commitment, to the verifier. At this point, the verifier cannot determine b (the hiding property). In the later reveal phase, the committer sends additional information that opens the commitment, allowing the verifier to check that the revealed bit matches the original commitment, preventing the committer from changing it (the binding property).

The core security properties are non-negotiable. Hiding ensures the verifier gains zero knowledge about the bit before the reveal, typically achieved using a one-way function or encryption with a random nonce (also called a salt or blinding factor). Binding guarantees that once the commitment is sent, the committer cannot find two different openings for different bits, which is often enforced by the collision resistance of a cryptographic hash function like SHA-256. These properties make the protocol analogous to sealing a value in a locked box and handing it over, with only the committer holding the key.

Bit commitment is a critical building block for more complex protocols. It is the essential engine behind zero-knowledge proofs, where a prover commits to information before a challenge is issued. It underpins secure coin tossing over a network, verifiable random functions (VRFs), and many blockchain-specific mechanisms. In blockchain, a simplified form of commitment is seen in transactions: you commit to a set of inputs and outputs by publishing their hash in the mempool, and later reveal the full details when the transaction is mined, binding you to the original terms.

Practical implementations often use a hash-based commitment: commitment = H(nonce || bit), where H is a cryptographic hash function and || denotes concatenation. To reveal, the committer provides the (nonce, bit) pair. The verifier recomputes the hash to verify. This method is binding if the hash is collision-resistant and hiding if the nonce is sufficiently random. More advanced schemes, like Pedersen commitments, provide additional properties like homomorphism, allowing for commitments to be combined mathematically, which is vital for confidential transactions in cryptocurrencies like Monero.

The concept extends beyond single bits to string commitment or vector commitment, where an entire message or set of values is committed. In blockchain scalability solutions, such as rollups, commitments to batches of transactions (often as a Merkle root) are posted to a base layer like Ethereum. This acts as a powerful bit commitment to the entire batch state, allowing for trust-minimized verification and dispute resolution through fraud proofs or validity proofs.

A bit commitment scheme is a two-phase protocol between a committer and a verifier. In the commit phase, the committer locks in a secret bit b by generating and sending a piece of data called a commitment. This commitment, often a cryptographic hash, conceals the bit's value. In the subsequent reveal phase, the committer sends additional information (the opening) that allows the verifier to check that the revealed bit matches the original commitment. The scheme must satisfy two core properties: hiding, which ensures the commitment reveals no information about b, and binding, which prevents the committer from changing the bit after the commitment is sent.

The classic analogy is writing the bit on a piece of paper, locking it in a safe, and giving the safe to the verifier. Later, you provide the key. The safe's contents are hidden until opened, and you cannot change the note inside after handing over the safe, making the commitment binding. In practice, this is achieved using cryptographic functions. A simple method uses a cryptographic hash function H. To commit to bit b, the committer selects a random nonce r and computes the commitment c = H(b || r), sending only c. To reveal, they send the pair (b, r). The verifier recomputes H(b || r) and checks it equals c.

More robust implementations, essential for blockchain systems, often use Pedersen commitments or schemes based on the discrete logarithm problem. These provide perfect hiding and computational binding, or vice-versa, under specific cryptographic assumptions. This flexibility is crucial for advanced protocols like zero-knowledge proofs and confidential transactions. The binding property is typically enforced by the computational difficulty of finding collisions for the commitment function, making it infeasible for the committer to find two different openings (b, r) and (b', r') that hash to the same value c.

In blockchain and cryptocurrency contexts, bit commitment is a foundational building block. It is used directly in protocols like coin flipping and secure auctions, and forms the basis for more complex constructs. For instance, Merkle trees can be seen as a form of vector commitment, committing to a set of data. The concept is also integral to Lightning Network payment channels, where hashed timelock contracts (HTLCs) use a hash commitment to lock funds contingent on revealing a secret preimage. This ensures that a payment can be securely routed across untrusted nodes.

The security of a bit commitment scheme is defined by its resilience against a computationally bounded adversary. Hiding ensures the verifier cannot learn b from c faster than by brute force (computational hiding) or at all (perfect hiding). Binding ensures the committer cannot feasibly produce a valid opening for a different bit. These properties are often in tension; a scheme may be perfectly hiding but computationally binding, or perfectly binding but computationally hiding. The choice depends on the protocol's trust model and required security guarantees. Modern schemes strive for efficiency in both communication and computation, especially for use in scalable decentralized systems.

The concept of a bit commitment scheme is a fundamental cryptographic primitive that allows one party, the committer, to seal a value (traditionally a single bit, hence 'bit') in a digital envelope. This act of commitment binds the committer to that value without revealing it, while the reveal phase allows them to later prove what was sealed. This two-phase protocol—commit then reveal—creates a binding and hiding promise, forming the bedrock for more complex secure computations.

Its origins lie in the work of cryptographic pioneers Manuel Blum and Shafi Goldwasser in the early 1980s, though the formalization is often attributed to a 1988 paper by Gilles Brassard, David Chaum, and Claude Crépeau. Initially explored for coin-flipping over the telephone and zero-knowledge proofs, bit commitment solved a core problem in distributed systems without trust: how to make a verifiable, secret promise. The 'bit' refers to the simplest unit of information, representing a binary choice (0 or 1), upon which more complex commitments are built.

In blockchain, this abstract primitive manifests concretely. When a miner hashes transaction data into a block header, they are effectively committing to that specific set of transactions. Any change would alter the Merkle root and break the cryptographic link. Similarly, a cryptographic hash function acts as a practical commitment scheme: publishing H(value) is the commitment, and later revealing the value that produces that hash is the proof. This mechanism underpins everything from transaction ordering to consensus algorithms and smart contract logic.

Bit commitment is a cryptographic protocol that allows one party, the committer, to seal a value (often a single bit, 0 or 1) in a digital "envelope." This process has two distinct phases. In the commit phase, the committer sends an encrypted or hashed version of their chosen bit, called a commitment, to a verifier. Crucially, this commitment reveals nothing about the hidden bit, binding the committer to their choice without disclosing it. The verifier cannot determine the bit's value from the commitment alone.

The second phase is the reveal phase. Here, the committer discloses the original bit and any additional secret information (like a random nonce or salt used in creating the commitment). The verifier can then use this revealed data to check the commitment against the original message. If the recomputed commitment matches the one received earlier, the verifier is assured that the committer did not change their bit after the initial commitment. This property is known as binding. The protocol's security relies on the computational difficulty of reversing the commitment function (e.g., finding a hash collision).

In practice, a simple bit commitment scheme can be constructed using a cryptographic hash function like SHA-256. The committer generates a random secret r (the salt) and computes the commitment as C = H(r || b), where b is the bit and || denotes concatenation. Sending C constitutes the commit. Later, to reveal, the committer sends the pair (r, b). The verifier recomputes H(r || b) and confirms it equals the original C. This ensures both hiding (from C alone) and binding (changing b would require finding a different r that hashes to the same C, a cryptographically hard problem).

The two-phase structure of commit-then-reveal is fundamental to many advanced protocols. It is the building block for zero-knowledge proofs, secure coin flipping, auction systems where bids must remain secret until opening, and consensus algorithms that require nodes to commit to a block proposal before broadcasting it. In blockchain contexts, it underpins mechanisms like Ethereum's RANDAO for verifiable randomness and certain layer-2 scaling solutions where transaction data is committed before being fully available.

A critical property of any bit commitment scheme is that it must be concealing and binding. A perfectly concealing scheme gives the verifier zero information about the bit from the commitment, while a computationally binding scheme makes it infeasible for the committer to open the commitment to two different values. Some schemes, like those using Pedersen commitments, offer additional properties like homomorphism, allowing commitments to be combined, which is useful in privacy-preserving cryptocurrencies and cryptographic voting systems.