Lets say Alice has a list of values, and Bob sends Alice a Merkle root that he claims is for this list of values. The Merkle tree construction algorithm is mutually known of course.
Alice can then pick arbitrary values from the list and ask Bob for their Merkle proof.
Lets say Alice wants to avoid constructing the whole tree to verify Bob's Merkle root. How sure can she be that Bob's Merkle root is correct after Bob has supplied N Merkle proofs? In other words what is the probability that Bob has lied about the Merkle root after N queries?
I have an answer in mind but I don't think it's right. Lets say we have a tree with M nodes in total (counting all layers), and each proof in that tree contains N hashes as data points in the proof. If Alice asks for K distinct proofs, then she can be sure the root is correct with a certainty of (N*K)/M.
Seems naive and like this would only be a lower bound though, since there's more to it than that. The tree is made of hashes that have preimage resistance, so it's not a mere question of counting known data points vs. total data points... or is it?
Given a known vector of arbitrary values V and a Merkle root R constructed by building a Merkle tree for V, if I have N Merkle proofs how sure can I be that R was constructed honestly and correctly from V?
Obviously I could rebuild the tree since I have (or can compute) all of V, but lets say I don't want to because it's time consuming etc.