Content deleted Content added
m Reverted 1 edit by 105.66.131.149 (talk) to last revision by Kku |
m i wouldnt consider O(n) inefficient by any means, but as there is better runtimes its still worth a mention |
||
Line 198:
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===
| |||