This module explains the inner workings of
commitment schemes. 

Commitment schemes
===================

To employ a commitment scheme, is simply to select a value 
from a finite set and commit to the value such that the 
new 'committed' value cannot be changed. 
Commitment schemes are used in cryptography, 
oft in conjunction with zero knowlegde proofs to 
allow a prover to commit to a polynomial, with values
represented by a short reference string. This is 
then used by verifiers to confirm or deny the claims 
made by the orginal committing party. With this process, 
the commitment, which the committer publishes, is bound, 
meaning it cannot be changed. This process is called *binding*. 
Additionally, the prover is able to make this commitment 
without revealing it - this is called *hiding*. After
the commitment has been made, a prover is able to 
reveal the committed message to a verifier so that 
the message can be compared, for consistency, with the 
commitment.


*Generic Example*

In a game of players P and V:

1. \\(P\\) writes down message \\(b\\) on a piece of paper
2. \\(P\\) places the message in a box and locks it using a padlock 
3. \\(P\\) gives the locked box and key to \\(V\\) 

From the above game, it can be that \\(V\\) is able to 
open the box, and see the committed message. \\(P\\) is 
unable to change the value after giving the 
box to \\(V\\), thus the message is *binding*. As \\(V\\) 
is unable to see the commitment prior to opening 
the box, the commitment is also *hiding*. 

Commitment schemes are defined by a \\(P\\) time 
public key *pk* generation algorithm \\(G\\). The 
input is \\(1^{l}\\), where \\({\mathbb l}\\) is the security parameter 
that directly relates to the length of the string. 
There is an outputted *pk*, which is the public key 
of the commitment scheme. In practice, the protocol 
is ran like this:

1. \\(P\\) or \\(V\\) executes \\(G\\) to return *pk*, as a string, 
and sends it to the other party.
2. To make the commitment, the recieving party calculates 
a random *r* from \\(({0,1})^{l}\\) and computes the commitment, 
\\(C\\):

\\[
\begin{aligned}
\operatorname{Commitment}(b,r) 
\end{aligned}
\\]

 
3. The commitment is opened, meaning \\(b\\) & \\(r\\) are revealed and 
\\(V\\) checks that the commitment, \\(C\\), satisfies: 
\\[
\begin{aligned}
\operatorname{Commitment}(b,r) 
\end{aligned}
\\]

The property of having either \\(P\\) *or* \\(V\\) running the 
algorithm affects the type of commitment scheme and the 
satisfied requirements. With respect to the *hiding* and 
*binding* properties, this commitment can be constructed
in two different ways.

When \\(V\\) generates the public key and sends it to \\(P\\), 
then the *binding* is computational and the *hiding* is 
unconditional. The *computational binding* in this commitment 
scheme, means the chance of being able to change the 
commitment is negligible. The *unconditional hiding* 
means that a commitment to b reveals no information about b. 

When \\(P\\) generates the public key and sends it to \\(V\\), then 
the *binding* is unconditional and the *hiding* is computational. 
The *unconditional binding* describes how \\(P\\) is unable to 
change the commitment value after it has been commited to. 
The *computational hiding* means the probability of \\(V\\) being 
able to guess the commitment value is negligible. 


Polynomial commitment schemes can be defined in the following way:



Let \\({\mathbb G}\\) be a group of prime order *p*. 
Let \\({\mathbb g}\\) and \\({\mathbb h}\\) be generators of \\({\mathbb G}\\),
such that:
\\[
\begin{aligned}
{\mathbf{g}}, {\mathbf{h}}  &\in {\mathbb G}
\end{aligned}
\\]

Either \\({\mathbf g}\\) or \\({\mathbf h}\\) are used to produce 
*pk*, which has a commitment appended to it by the committer. 

This commitment is equal to message \\({\mathbb m}\\),
where:
\\[
\begin{aligned} 
{\mathbf{m}}  &\in\ {\mathbb Z\_{p}},
\end{aligned}
\\]

The commitment which is made once these variables are derived, is:

\\[
\begin{aligned}
\operatorname{Commitment}\_{pk}(b,r) = 
{\mathbf{g}^{r}} 
\cdot 
{\mathbf{h}^{b}}
\end{aligned}
\\]



The above equation is generic to using short strings, 
as values, to commit to a polynomial and generate an evaluated 
value.