Previously we had discussed handling path verifiability at a higher level, in Mastic itself. Indeed, it's possible to use the current VIDPF in a black-box manner and perform the same calculation. However, the resulting algorithm would have asymptotic runtime that is far worse than optimal. Instead, I followed @hannahdaviscrypto's suggestion to modify VIDPF so that it does the path verification itself. The resulting algorithm is as fast as we can hope for, at least asymptotically. (Concretely there is more room for optimization.)
When specifying a complex algorithm like this, it's often useful to write down the asymptotically-optimal version. I think it makes sense to do the same thing here.
This PR also stacks some minor changes to vidpf that are technically separate. It may help to review commit-by-commit.
As discussed here in https://github.com/jimouris/draft-mouris-cfrg-mastic/pull/20#discussion_r1362349956, for each node in the prefix tree we wish to check that the children sum up to the same value.
Previously we had discussed handling path verifiability at a higher level, in Mastic itself. Indeed, it's possible to use the current VIDPF in a black-box manner and perform the same calculation. However, the resulting algorithm would have asymptotic runtime that is far worse than optimal. Instead, I followed @hannahdaviscrypto's suggestion to modify VIDPF so that it does the path verification itself. The resulting algorithm is as fast as we can hope for, at least asymptotically. (Concretely there is more room for optimization.)
When specifying a complex algorithm like this, it's often useful to write down the asymptotically-optimal version. I think it makes sense to do the same thing here.
This PR also stacks some minor changes to
vidpfthat are technically separate. It may help to review commit-by-commit.