Hash-Based Commitment Scheme

Table of contents

Open Table of contents

What it is

A commitment scheme ensures that a value one has committed to can’t be changed after the fact (i.e. one can’t cheat by pretending that (s)he has committed to a different value).

The commitment scheme enforces two important properties:

  1. The value that was committed to is hidden (i.e. no information leak)
  2. Once a value was committed to, it can’t be changed

How it works

In our example of a Hash-Based Commitment scheme we have two parties, Alice and Bob.

Alice commits to a value she then sends to Bob who checks that Alice in fact committed to the correct value.

As the name implies, we’ll be using a cryptographic hash function HH in this construction.

The first thing Alice does is deciding on which value vv she wants to commit to. The value vv could be any value like one sampled randomly from Z\mathbb{Z}:

v←$Zv \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}

Next up, Alice samples another random value rr from Z\mathbb{Z}:

r←$Zr \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}

Both values will be concatenated (indicated by ∥\mathbin\Vert) and hashed via the hash function HH to produce the commitment cc:

c=H(v∥r)c = H(v \mathbin\Vert r)

The value cc can now be shared with Bob.

Once Bob wants to verify which value vv Alice committed to, he requests vv as well as rr from Alice. He can then check if:

H(v∥r)=?cH(v \mathbin\Vert r) \overset{?}{=} c

Hash-Based Commitment Scheme

Why it works

Given that cryptographic hash functions will produce a randomly looking output that also ensure one-wayness (i.e. given the output, one cannot determine the input) Bob can’t figure out which value Alice committed to.

The usage of the random value rr during hashing further ensures that Bob can’t “reverse-engineer” Alice’s value vv by iterating over all possible values and creating a hash for each value to produce a lookup-table.

Because these measures guarantee that no information regarding Alice’s value vv is leaked, we can say that the aforementioned property #1 a commitment scheme needs to adhere to is satisfied.

Next, we should note that a cryptographic hash function aims to provide collision resistance, meaning that any potential input value maps to one and only one output.

Because Bob knows the hash function’s output cc before Alice reveals vv and rr, Alice would need to find a collision H(v′∥r′)=H(v∥r)H(v' \mathbin\Vert r') = H(v \mathbin\Vert r) to be able to convince Bob that she committed to v′v' (using also r′r') rather than vv (and rr respectively).

Given the likelihood of this happening is negligible for a cryptographic hash function, Alice won’t be able to convince Bob that she committed to another value. Given this we can see that the commitment scheme presented here also adheres to the aforementioned property #2.

Resources