Content deleted Content added
→Vector hashing: Vector hashing is a naive vector commitment partial reveal scheme based on bit-commitment. Values <math>m_1, m_2, ... m_n</math> are chosen randomly. Individual commitments are created by hashing <math>y_1=H(x_1||m_1), y_2=H(x_2||m_2), ...</math>. The overall commitment is computed as :<math>C=H(y_1||y_2||...||y_n)</math> In order to prove one element of the vector <math>X</math>, the prover reveals the values :<math>(i, y_1, y_2, ..., y_{i-1}, x_i, m_i, y_{i+1}, ..., y_n... Tags: Reverted section blanking Mobile edit Mobile web edit |
Reverted 1 edit by 60.62.105.19 (talk): WP:UCR |
||
Line 195:
===Vector hashing===
Vector hashing is a naive vector commitment partial reveal scheme based on bit-commitment. Values <math>m_1, m_2, ... m_n</math> are chosen randomly. Individual commitments are created by hashing <math>y_1=H(x_1||m_1), y_2=H(x_2||m_2), ...</math>. The overall commitment is computed as
:<math>C=H(y_1||y_2||...||y_n)</math>
In order to prove one element of the vector <math>X</math>, the prover reveals the values
:<math>(i, y_1, y_2, ..., y_{i-1}, x_i, m_i, y_{i+1}, ..., y_n)</math>
The verifier is able to compute <math>y_i</math> from <math>x_i</math> and <math>m_i</math>, and then is able to verify that the hash of all <math>y</math> values is the commitment <math>C</math>.
Unfortunately the proof is <math>O(n)</math> in size and verification time. Alternately, if <math>C</math> is the set of all <math>y</math> values, then the commitment is <math>O(n)</math> in size, and the proof is <math>O(1)</math> in size and verification time. Either way, the commitment or the proof scales with <math>O(n)</math> which is not optimal.
===Merkle tree===
| |||