An in-depth analysis of the complete security of STARK

原文：Safe and Sound — A Deep Dive into STARK Security
Translation and proofreading: "Starknet Chinese Community"
Featured Quick Facts
Non-interactive STARK is derived from Interactive Oracle Proofs (IOPs), compiled into non-interactive proofs in the stochastic oracle model.
This article explains the latest updates to the ethSTARK documentation and provides a comprehensive and detailed analysis of the security of the ethSTARK protocol in the random oracle model.
Detailed explanation of STARK security
The STARK proof system, or scalable transparent knowledge argument, is a powerful tool for computational integrity: it allows trustless verification of the correctness of computations performed on public data. In this article, we will dive into the security provided by STARK proofs, define them, and explore techniques for proving the security of schemes.
(Read section 6 of the ethSTARK documentation (version 1.2) for details, as well as the important and comprehensive independent work on this topic by Block et al.)
What are we trying to achieve with security analytics? We want to prevent "successful attacks" on the STARK system caused by a false statement and the STARK proof accepted by a STARK validator in response to that (false) statement. Because misrepresentations are dangerous and they can come in all sizes and forms, we want to be safe against them all. Any false statement, even as trivial as 1+1=3, when combined with a STARK proof accepted by a STARK validator, is considered a successful attack on the system. (Those with a background in cryptography may be interested to know that STARK can also satisfy stronger security concepts such as knowledge reliability, but for the sake of simplicity, this article will focus on the simple case of reliability).
How do we formally define the security of a STARK system? We determine this by analyzing "reliability error." The "reliability error" roughly measures the expected "cost" it would take for an attacker to launch a successful attack (i.e., find a STARK proof for a false statement that is accepted by a STARK validator). Mathematically speaking, the reliability error is a function (t) whose input is the time parameter t, representing the computational time the attacker is willing to spend to launch an attack, and the output is the probability that the attacker's attack will succeed (found for false statements convincing proof). The greater the "cost" t that the attacker is willing to spend, the higher his probability of success.
So far we have defined the security of STARK as a function (t), which is different from how security is discussed on crypto Twitter every day. On Twitter, you might hear: “This solution has 96 bits of security.” How does this translate into our definition of security? There’s no single answer to this, as people understand “x bits of security” slightly differently:
Strictly interpreted, this means that for any t between 1 and 2⁹⁶, the reliability error is (t) 2⁹⁶ . An attacker running for 2⁹⁶ or less has a very small probability of success, less than 2⁹⁶, which is less than 1 in a billion times 1 in a billion.
A looser, and perhaps more common, interpretation is that 96-bit security means that for any t, there is a case where t/(t) 2⁹⁶. This means that the probability of success is (inversely) linear with the running time. If the attacker has a running time of 2⁸⁶, then his probability of success is at most 2¹⁰.
In this article, we will discuss the second option.
From IOP to STARK with 96-bit security
So, how do we prove that a solution has 96 bits of security? To answer this question, we need to understand the high-level structure upon which STARK is built. STARK consists of three main parts: IOP (Interactive Oracle Proof), Merkle Tree, and Fiat-Shamir hash; our main focus is IOP. Once these component parts are specified, we can compile them to produce a STARK. We'll go over these components in detail, including what they are and how they fit together.
The first component we will review is the IOP: The IOP is similar to a standard interactive proof, where the prover and validator interact for multiple rounds (we are limited to public coin protocols, where the validator only sends random challenges to the prover). In an IOP, the verifier does not fully read the prover's message, but instead samples a small portion of the bits from each prover's message. This is why the later compiled STARK achieves its simplicity.
Given the IOP, how do I build a STARK from it? The prover's messages can be very long (in fact, they are longer than the computation itself). To compress this information, we use Merkle trees. A Merkle tree is a binary hash tree in which each leaf node represents a query or an answer in the IOP. The roots are the promise of the entire message. When a validator wants to read a specific location in a message, the prover provides the value of that location and the verification path. The validator can then use this path to verify that the value is correct. The IOP validator reads only a small amount of location information from the prover information. Therefore, concise protocols (protocols with low communication volume) can be implemented using Merkle trees.
Compression rounds
We can choose interactive STARK, but to simplify the process of generating STARK, we usually choose non-interactive STARK so that the validator does not need to wait for external information when building STARK. In fact, this is how all STARK systems are currently deployed, and how the ethSTARK protocol is built. Non-interactive STARKs are also a special case of transparent SNARKs (transparent means no trusted setup is required to instantiate them; "Arthur Merlin Protocol" or "Public Coin IOP"). To do this, the final step is to apply the Fiat-Shamir algorithm to compress multiple rounds of interactions into a single message, which we call a STARK proof. Fiat-Shamir transformation is a method of converting an interactive protocol into a non-interactive protocol. The prover simulates an interactive protocol while talking to the hash function. To derive the random challenge for round i, the prover hashes to the partial record for round i and interprets the output as the next challenge.
This ensures that the prover cannot change its answer after the challenge is generated. However, cheating provers have some new policy avenues that are not available in interactive IOPs. The prover can regenerate the validator challenge by modifying the last prover information, so that it will get a new record and thus a new challenge. It turns out that the standard reliability concepts of the IOP are not sufficient to demonstrate the safety of the Fiat-Shamir conversion.
For example, have an IOP of 96 rounds and add the following hack to the validator: If the first bit of the validator's randomness is 0 each of the 96 rounds, then the validator will accept it (without seeing any proof). We can see that adding this hack to the validator only adds a term of 2⁹⁶ to the reliability error of the IOP. However, after the Fiat-Shamir transformation, an attacker can easily modify the prover information to ensure that every hash value starts with 0, thereby compromising the system in a very short time. Rest assured, this dire scenario is just a theoretical example and does not apply to deployed STARKs. So, let’s take a look at why our STARK is safe after all. In short, we will show that, for an attacker running at most t steps, the probability of a successful attack is at most (t) t 2⁹⁶.
IOP and round-by-round reliability
STARK's security depends on its underlying IOPs. But what does it mean for an IOP to have 96 bits of security? By standard definition, IOP has a reliability error of 2⁹⁶: this means that the probability that any attacker (regardless of runtime) can fool a validator is at most 2-96. However, as we discussed, the reliability of the IOP is only one of the three components, which is not enough to achieve 96 bits of security from a STARK compiled from all three steps. In contrast, the safety of compiled STARK is proven assuming that STARK has a 96-bit round-by-round reliability error (a similar definition called state recovery reliability is sometimes used).
Intuitively, "round-by-round soundness" indicates that each round has 96 bits of security, not just the entire protocol. To be more specific, round-by-round reliability refers to the existence of a predicate that can obtain part of the record of the protocol and tell us whether this record is "deceptive": "empty record" is not "deceptive", and when And the complete record is "deceptive" only if accepted by the validator. Finally, for any partial record that is not "spoofing" the validator, the probability that the record becomes "spoofing" in the next round is at most 2⁹⁶. If there is a predicate with these properties, we say that the protocol has 96 bits of round-by-round reliability (this predicate does not require efficient computation).
In many cases, people only analyze the reliability of the IOP and not its round-to-round reliability. Admittedly, it's hard to think of an example (except for manufactured examples) of an IOP that has standard reliability but not round-to-round reliability. However, when deriving specific safety bounds, differences between the two may arise and every bit counts. Therefore, to derive tight and specific bounds, a rigorous analysis of the round-by-round reliability of IOP is necessary. This is exactly what we are doing with the FRI protocol and the ethSTARK IOP on which STARK IOP is based. The analysis itself is far from trivial and is beyond the scope of this article. Using the new analysis, we can set precise parameters for our proof.
Round-by-round reliability really gives us the assurance we need. The prover can regenerate the challenge multiple times, but we know that in any round, the probability of generating a fraudulent record is 2⁹⁶. Therefore, if the prover has t times (measured in the number of hash calls), then It can try at most t times to obtain a deceptive record, which limits its probability of success to (t) t 2⁹⁶.
Add all errors
Finally, for all of this to hold true, we need to ensure that the prover cannot tamper with the Merkle tree. We can show that as long as the prover finds no collisions in the hash function, he cannot cheat in the Merkle tree. The probability of an attacker finding a collision using t calls (random hash function) is at most t2/2, which is the output length of the hash function (caused by the "Birthday Paradox"). This is why we need to set the hash function The length is twice the required security. So if we have a hash function with an output length of 192 and an IOP with a round-by-round reliability of 96 bits, we get a compiled STARK that is reliable Sexual error (t)=t2-⁹⁶ + t2 2¹⁹⁶. Since t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, this scheme has 95 bits of security sex.
Summarize
Taken together, STARK provides a powerful method for trustlessly verifying the correctness of computations performed on public data. The security of STARK is usually measured by "reliability error", which represents the probability that an attacker successfully provides a false statement and convinces the validator with a proof. In order to achieve a required security level, such as 96 bits, the underlying IOP must meet round-by-round reliability, ensuring that a high security level is maintained every round. We analyzed the round-by-round reliability of the IOPs on which our STARK is based to derive specific safety bounds.