Some commitment schemes permit a proof to be given of only a portion of the committed value. In these schemes, the secret value X is a vector of many individually separable values. :X = (x_1, x_2, ..., x_n) The commitment C is computed from X in the commit phase. Normally, in the reveal phase, the prover would reveal all of X and some additional proof data (such as R in
simple bit-commitment). Instead, the prover is able to reveal any single value from the X vector, and create an efficient proof that it is the authentic ith element of the original vector that created the commitment C. The proof does not require any values of X other than x_i to be revealed, and it is impossible to create valid proofs that reveal different values for any of the x_i than the true one.
Vector hashing Vector hashing is a naive vector commitment partial reveal scheme based on bit-commitment. Values m_1, m_2, ... m_n are chosen randomly. Individual commitments are created by hashing y_1=H(x_1||m_1), y_2=H(x_2||m_2), .... The overall commitment is computed as :C=H(y_1||y_2||...||y_n) In order to prove one element of the vector X, the prover reveals the values :(i, y_1, y_2, ..., y_{i-1}, x_i, m_i, y_{i+1}, ..., y_n) The verifier is able to compute y_i from x_i and m_i, and then is able to verify that the hash of all y values is the commitment C. Unfortunately the proof is O(n) in size and verification time. Alternately, if C is the set of all y values, then the commitment is O(n) in size, and the proof is O(1) in size and verification time. Either way, the commitment or the proof scales with O(n) which is not optimal.
Merkle tree A common example of a practical partial reveal scheme is a
Merkle tree, in which a binary hash tree is created of the elements of X. This scheme creates commitments that are O(1) in size, and proofs that are O(\log_2{n}) in size and verification time. The root hash of the tree is the commitment C. To prove that a revealed x_i is part of the original tree, only \log_2{n} hash values from the tree, one from each level, must be revealed as the proof. The verifier is able to follow the path from the claimed leaf node all the way up to the root, hashing in the sibling nodes at each level, and eventually arriving at a root node value that must equal C.
KZG commitment A Kate–Zaverucha–Goldberg (KZG) commitment uses
pairing-based cryptography to build a partial reveal scheme with O(1) commitment sizes, proof sizes, and proof verification time. In other words, as n, the number of values in X, increases, the commitments and proofs do not get larger, and the proofs do not take any more effort to verify. A KZG commitment requires a predetermined set of parameters to create a
pairing, and a trusted trapdoor element. For example, a
Tate pairing can be used. Assume that \mathbb{G}_1, \mathbb{G}_2 are the additive groups, and \mathbb{G}_T is the multiplicative group of the pairing. In other words, the pairing is the map e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T. Let t \in \mathbb{F}_p be the trapdoor element (if p is the prime order of \mathbb{G}_1 and \mathbb{G}_2), and let G and H be the generators of \mathbb{G}_1 and \mathbb{G}_2 respectively. As part of the parameter setup, we assume that G \cdot t^i and H \cdot t^i are known and shared values for arbitrarily many positive integer values of i, while the trapdoor value t itself is discarded and known to no one.
Commit A KZG commitment reformulates the vector of values to be committed as a polynomial. First, we calculate a polynomial such that p(i)=x_i for all values of x_i in our vector.
Lagrange interpolation allows us to compute that polynomial :p(x)=\sum_{i=0}^{n-1}x_i\prod_{0\leq j Under this formulation, the polynomial now encodes the vector, where p(0)=x_0, p(1)=x_1, .... Let p_0, p_1, ..., p_{n-1} be the coefficients of p, such that p(x)=\sum_{i=0}^{n-1} p_i x^i. The commitment is calculated as :C=\sum_{i=0}^{n-1} p_i G t^i This is computed simply as a
dot product between the predetermined values G \cdot t^i and the polynomial coefficients p_i. Since \mathbb{G}_1 is an additive group with associativity and commutativity, C is equal to simply G \cdot p(t), since all the additions and multiplications with G can be distributed out of the evaluation. Since the trapdoor value t is unknown, the commitment C is essentially the polynomial evaluated at a number known to no one, with the outcome obfuscated into an opaque element of \mathbb{G}_1.
Reveal A KZG proof must demonstrate that the revealed data is the authentic value of x_i when C was computed. Let y=x_i, the revealed value we must prove. Since the vector of x_i was reformulated into a polynomial, we really need to prove that the polynomial p, when evaluated at i, takes on the value y. Simply, we just need to prove that p(i)=y. We will do this by demonstrating that subtracting y from p yields a root at i. Define the polynomial q as :q(x)=\frac{p(x)-y}{x-i} This polynomial is itself the proof that p(i)=y, because if q exists, then p(x)-y is divisible by x-i, meaning it has a root at i, so p(i)-y=0 (or, in other words, p(i)=y). The KZG proof will demonstrate that q exists and has this property. The prover computes q through the above polynomial division, then calculates the KZG proof value \pi :\pi=\sum_{i=0}^{n-1} q_i G t^i This is equal to G \cdot q(t), as above. In other words, the proof value is the polynomial q again evaluated at the trapdoor value t, hidden in the generator G of \mathbb{G}_1. This computation is only possible if the above polynomials were evenly divisible, because in that case the quotient q is a polynomial, not a
rational function. Due to the construction of the trapdoor, it is not possible to evaluate a rational function at the trapdoor value, only to evaluate a polynomial using linear combinations of the precomputed known constants of G \cdot t^i. This is why it is impossible to create a proof for an incorrect value of x_i.
Verify To verify the proof, the bilinear map of the
pairing is used to show that the proof value \pi summarizes a real polynomial q that demonstrates the desired property, which is that p(x)-y was evenly divided by x-i. The verification computation checks the equality :e(\pi, H \cdot t - H \cdot i)\ \stackrel{?}{=}\ e(C - G \cdot y, H) where e is the bilinear map function as above. H \cdot t is a precomputed constant, H \cdot i is computed based on i. By rewriting the computation in the pairing group \mathbb{G}_T, substituting in \pi=q(t) \cdot G and C=p(t) \cdot G, and letting \tau(x)=e(G,H)^x be a helper function for lifting into the pairing group, the proof verification is more clear. :e(\pi, H \cdot t - H \cdot i) = e(C - G \cdot y, H) :e(G \cdot q(t), H \cdot t - H \cdot i) = e(G \cdot p(t) - G \cdot y, H) :e(G \cdot q(t), H \cdot (t-i)) = e(G \cdot (p(t) - y), H) :e(G, H)^{q(t)\cdot(t-i)} = e(G, H)^{p(t) - y} :\tau(q(t) \cdot (t-i)) = \tau(p(t)-y) Assuming that the bilinear map is validly constructed, this demonstrates that q(x)(x-i) = p(x)-y, without the validator knowing what p or q are. The validator can be assured of this because if \tau(q(t) \cdot (t-i)) = \tau(p(t)-y), then the polynomials evaluate to the same output at the trapdoor value x=t. This demonstrates the polynomials are identical, because, if the parameters were validly constructed, the trapdoor value is known to no one, meaning that engineering a polynomial to have a specific value at the trapdoor is impossible (according to the
Schwartz–Zippel lemma). If q(x)(x-i) = p(x)-y is now verified to be true, then q is verified to exist, therefore p(x)-y must be polynomial-divisible by (x-i), so p(i)-y=0 due to the
factor theorem. This proves that the ith value of the committed vector must have equaled y, since that is the output of evaluating the committed polynomial at i. {{hidden The utility of the bilinear map pairing is to allow the multiplication of q(x) by x-i to happen securely. These values truly lie in \mathbb{G}_1, where division is assumed to be computationally hard. For example, \mathbb{G}_1 might be an
elliptic curve over a finite field, as is common in
elliptic-curve cryptography. Then, the division assumption is called the
elliptic curve discrete logarithm problem, and this assumption is also what guards the trapdoor value from being computed, making it also a foundation of KZG commitments. In that case, we want to check if q(x)(x-i) = p(x)-y. This cannot be done without a pairing, because with values on the curve of G \cdot q(x) and G \cdot (x-i), we cannot compute G \cdot (q(x)(x-i)). That would violate the
computational Diffie–Hellman assumption, a foundational assumption in
elliptic-curve cryptography. We instead use a
pairing to sidestep this problem. q(x) is still multiplied by G to get G \cdot q(x), but the other side of the multiplication is done in the paired group \mathbb{G}_2, so, H \cdot (t-i). We compute e(G \cdot q(t), H \cdot (t-i)), which, due to the
bilinearity of the map, is equal to e(G, H)^{q(t)\cdot(t-i)}. In this output group \mathbb{G}_T we still have the
discrete logarithm problem, so even though we know that value and e(G, H), we cannot extract the exponent q(t)\cdot(t-i), preventing any contradiction with discrete logarithm earlier. This value can be compared to e(G \cdot (p(t) - y), H)=e(G, H)^{p(t) - y} though, and if e(G, H)^{q(t)\cdot(t-i)} = e(G, H)^{p(t) - y} we are able to conclude that q(t) \cdot (t-i) = p(t)-y, without ever knowing what the actual value of t is, let alone q(t)(t-i). }} Additionally, a KZG commitment can be extended to prove the values of any arbitrary k values of X (not just one value), with the proof size remaining O(1), but the proof verification time scales with O(k). The proof is the same, but instead of subtracting a constant y, we subtract a polynomial that causes multiple roots, at all the locations we want to prove, and instead of dividing by x-i we divide by \prod_i x-i for those same locations. ==Quantum bit commitment==