I've been reading about ZK-STARK. There's an example that appears in several blogs. The most detailed explanation of that specific example which I have found so far is in this blog.
The description of the example (the requirement) is:
Suppose that you want to prove that you have a polynomial $P$ such that $P(x)$ is an integer with $0 \leq P(x) \leq 9$ for all $x$ from 1 to 1 million.
I will quote the summary of the explanation:
We know that this proof has perfect completeness - if you actually know a suitable $P(x)$, then if you calculate $D(x)$ and construct the proof correctly it will always pass all 16 checks. But what about soundness - that is, if a malicious prover provides a bad $P(x)$, what is the minimum probability that they will get caught? We can analyze as follows. Because $C(P(x)$ is a degree-10 polynomial composed with a degree-1,000,000 polynomial, its degree will be at most 10,000,000. In general, we know that two different degree-$N$ polynomials agree on at most $N$ points; hence, a degree-10,000,000 polynomial which is not equal to any polynomial which always equals $Z(x) \cdot D(x)$ for some $x$ will necessarily disagree with them all at at least 990,000,000 points. Hence, the probability that a bad $P(x)$ will get caught in even one round is already 99%; with 16 checks, the probability of getting caught goes up to $1 - 10^{-32}$; that is to say, the scheme is about as hard to spoof as it is to compute a hash collision.
What confuses me is that I see at least two reasons why the soundness argument is not so sound:
If the prover truly has valid $P, D$, he can build the Merkle tree, and then tamper with the tree by changing one leaf for which $1 \leq x \leq 1,000,000$ to a wrong value so that $P(x) = 42$. The prover may even adjust the Merkle tree hashes accordingly (this adjustment is not essential). The tampered tree is the one that the prover will use when answering the verifier's questions.
Now, this tree does not represent valid $P, D$ polynomials, because $P$, as represented by the tree, does not satisfy the requirement. But this fact does not significantly increase the number of errors.
So I've seen in a video lecture by the team that develops STARK, that they introduce the concept of trusted notary, which is a middleman between the prover and verifier. But if the notary is used to verify that the Merkle tree indeed matches the $P, D$ that the prover claims to have, then why should the verifier trust that notary (and why should the prover trust the notary with exposing to him the secret $P$)? And if the verifier already trusts the notary, then why not just take his word that indeed the prover has valid $P, D$?
I also thought that the T in STARK stands for transparent, i.e. trustless.
Even if the verifier trusts the notary, but the notary does not check that $P, D$ satisfy the requirement, and instead only makes sure that the Merkle tree faithfully represents $P, D$ ― I still see the following problem:
The argument in the summary above depends on the assumption that $P$ is a degree-1,000,000 polynomial. But $P$ could have been in fact a degree-1,000,000,000 polynomial that still satisfies the stated requirement. And we can find its matching polynomial D.
Now, instead of $P$ we can choose a slightly different polynomial $Q$, for which, like in case (1) above, $Q(x) = 42$ for some $1 \leq x \leq 1,000,000$. We can still use the same $D$ as we found earlier for $P$. Now, in the Merkle tree we use $Q, D$.
$Q$ is not a valid secret, because it does not satisfy the requirement. But it's very hard to find it out, because $P, D$ and $Q, D$ have the same values throughout the whole range $1 \leq x \leq 1,000,000,000$, except for the single $x$ which makes $Q$ unqualified for satisfying the requirement.
