Idea: Consider using Merkle-Damgard rather than the "linear" variant

[cjpatton]

Each call to vidpf.eval_next() updates the onehot proof as follows (excerpted from the spec):

# Compute and correct the node proof and update the onehot proof.
# Each update resembles a step of Merkle-Damgard compression. The
# main difference is that we XOR each block (i.e., corrected node
# proof) with the previous hash (or IV) rather than compress.
#
#             corrected node proof
#                 |
#                 |
#                 v
# current      +-----+     +------+     +-----+      updated
# proof  --+-->| XOR |---->| Hash |---->| XOR |----> proof
#          |   +-----+     +------+     +-----+
#          |                               ^
#          |                               |
#          +-------------------------------+
#
# [MST24]: \tilde\pi = H_1(x^{\leq i} || s^\i)
#          \pi = \tilde \pi \xor
#             H_2(\pi \xor (\tilde\pi \xor t^\i \cdot \cs^\i)

This is Merkle-Damgard-ish: the difference is that we XOR the next block (i.e., the node proof) with the current state (i.e., the current proof) then hash to get the next state, rather than compress the next block and the current state to get the next state. This comes from [CP22], but why do they do this? If we can get away with plain Merkle-Damgard, then it might be a good idea to use it here.

[cjpatton]

I reached out to the [CP22] authors about this is and here's what I heard back:

In general, there’s nothing special that is required from the hash function to make this construction work. If I recall correctly, the two hash functions were defined simply to differentiate the output sizes and support the smallest possible communication between the servers. Regarding the hashing technique, any method of hashing a vector that is safe against permutation attacks should be fine to use. In particular, I don’t see an issue with using Merkel-Damgard, and I believe the only reason we didn’t use this is to cut down on the number of hash function calls.

I'm not sure what's meant by "permutations attacks", but otherwise I think it's clear we have some freedom here. All we're doing is hashing the node proofs.