A hash-based commitment c = H(v || r) is computationally hiding and computationally binding. What would happen if we used c = H(v) without the random nonce r?
Think about your answer, then reveal below.
Model answer: Without randomness, the commitment is deterministic — an adversary who knows the set of possible values (e.g., 'yes' or 'no') can compute H(yes) and H(no) and compare with c to determine v. The random nonce r ensures that c = H(v || r) is uniformly distributed even for small value spaces, making the commitment indistinguishable from random. Without r, the scheme has no hiding property for low-entropy values.
This is analogous to why encryption must be randomized (semantic security): deterministic commitments leak the committed value through exhaustive search over the value space. The nonce r must be long enough (128+ bits) to prevent brute-force search over both v and r.
Question 2 Multiple Choice
The hiding and binding properties of a commitment scheme are in tension — perfect hiding and perfect binding cannot both be achieved simultaneously. Why?
AThe commitment would require infinite storage
BPerfect hiding means that for any value v, there exists a randomness r' that makes c consistent with a different value v'. But if this is true, the committer CAN find v' and r' to change their commitment — violating perfect binding. Conversely, perfect binding means c uniquely determines v, but then an unbounded adversary could search for the unique v, violating perfect hiding
CQuantum computers break both properties simultaneously
DThe two properties require contradictory key lengths
This is a fundamental impossibility result. Commitment schemes must choose: information-theoretic hiding + computational binding (Pedersen: the commitment statistically reveals nothing, but changing the value requires solving DLP), or computational hiding + information-theoretic binding (hash-based: the commitment computationally hides the value, but is information-theoretically bound to exactly one value because the hash is deterministic given v and r). The choice depends on which adversary you're more worried about — a computationally unlimited observer or a computationally unlimited committer.
Question 3 Multiple Choice
Pedersen commitments (c = g^v * h^r mod p, where the discrete log relationship between g and h is unknown) provide information-theoretic hiding. Why?
AThe modular exponentiation is a one-way function
BFor any commitment c and any target value v', there exists a randomness r' such that c = g^{v'} * h^{r'} — the commitment is consistent with every possible value. An unbounded adversary cannot determine v because every v is equally plausible. Finding r' requires knowing the discrete log of g base h, so opening to a different value (binding) is computationally hard
CThe Pedersen commitment uses a random oracle
DThe prime p is so large that brute force is infeasible
This is the cleanest example of information-theoretic hiding: the commitment is literally a uniform random group element regardless of v (given uniform r). No amount of computation reveals v. Binding relies on the DLP assumption: to open c as both v and v' (with different r and r'), you'd need g^{v-v'} = h^{r'-r}, which reveals log_g(h) — assumed hard. Pedersen commitments are heavily used in zero-knowledge proofs and blockchain privacy (Monero's confidential transactions).
Question 4 True / False
Commitment schemes are essential for fair coin-flipping over a telephone line (Blum's protocol). Without commitments, the first party to announce their coin flip can cheat by choosing based on the other's announcement.
TTrue
FFalse
Answer: True
Blum's protocol: Alice commits to a random bit a (sends commitment c_a to Bob). Bob sends his random bit b in the clear. Alice opens her commitment, revealing a. The coin flip result is a XOR b. Alice cannot cheat because she committed to a before seeing b (binding). Bob cannot cheat because he doesn't know a when choosing b (hiding). Without the commitment, if Alice announced a first, Bob could choose b to make a XOR b whatever he wants.
Question 5 Short Answer
Vector commitments generalize standard commitments: instead of committing to a single value, you commit to a vector (v_1, ..., v_n) and can later open any individual position i without revealing other positions. Why is this useful for blockchain?
Think about your answer, then reveal below.
Model answer: A blockchain block contains thousands of transactions. A vector commitment to all transactions in a block lets anyone verify that a specific transaction is included in the block by opening just that position — without downloading or processing the other transactions. Merkle trees are the most common vector commitment: the root hash commits to all leaves, and a Merkle proof (O(log n) hashes) opens one leaf. Polynomial commitments (KZG) achieve constant-size openings but require trusted setup. These are used in light clients, state proofs, and blockchain interoperability.
Vector commitments with efficient opening proofs are fundamental to scalable blockchain architecture. Light clients (like mobile wallets) trust the block header's commitment and verify individual transactions on demand, without storing the full blockchain. Ethereum's state tree is essentially a vector commitment over all account balances and contract states.