The ADVZ VID scheme calls for a KZG proof to be sent to each storage node. If it were the case that these proofs are all for the a single polynomial then we could use the FK23 method to batch compute the proofs in quali-linear time. Unfortunately, that's not the case---each storage node has a different polynomial (as per hotshot paper) and so we cannot use FK23. Thus, we must compute a separate KZG proof for each storage node, giving us a quadratic-time bottleneck. 😢
Solution
Maybe we could use the same polynomial for all storage nodes if we compute the pseudorandom scalar t in the hotshot paper so that it includes all the evaluations p_i(j) in the hash. Need to do this in a way that still allows each storage node to recover t using only his own evaluations. So like:
t = hash(commit(B), root)
where root is the root of a merkle tree whose leaves are p_1(j),...,j_k(j) for each j. Each storage node j gets his evaluations p_1(j),...,j_k(j) plus a merkle path to root. That way we avoid the attack described in the github comment, yet we still get the same polynomial for each storage node and can therefore use FK23. :thinking: Of course, this adds log(num_storage_nodes) data to the dispersal message sent to each storage node.
(If merkle proof size is a problem then we could replace merkle root with some other vector commitment with constant-size openings. KZG anyone? 😛 To start we'll just use an ordinary merkle path.)
Problem
The ADVZ VID scheme calls for a KZG proof to be sent to each storage node. If it were the case that these proofs are all for the a single polynomial then we could use the FK23 method to batch compute the proofs in quali-linear time. Unfortunately, that's not the case---each storage node has a different polynomial (as per hotshot paper) and so we cannot use FK23. Thus, we must compute a separate KZG proof for each storage node, giving us a quadratic-time bottleneck. 😢
Solution
Maybe we could use the same polynomial for all storage nodes if we compute the pseudorandom scalar
tin the hotshot paper so that it includes all the evaluationsp_i(j)in the hash. Need to do this in a way that still allows each storage node to recovertusing only his own evaluations. So like:where
rootis the root of a merkle tree whose leaves arep_1(j),...,j_k(j)for eachj. Each storage nodejgets his evaluationsp_1(j),...,j_k(j)plus a merkle path toroot. That way we avoid the attack described in the github comment, yet we still get the same polynomial for each storage node and can therefore use FK23. :thinking: Of course, this addslog(num_storage_nodes)data to the dispersal message sent to each storage node.(If merkle proof size is a problem then we could replace merkle root with some other vector commitment with constant-size openings. KZG anyone? 😛 To start we'll just use an ordinary merkle path.)