Security level of a STARK

[bobbinth]

There should be a getter on the Stark object to calculate security level of a specific STARK instance. Something as simple as Stark.SecurityLevel will do. The security level probably depends on:

• Constraint degree
• Extension factor
• Execution trace query count
• FRI proof query count
• Security of the underlying hash function
• Size of the underlying field
• Anything else?

Need to come up with the exact formula for how all these come together.

[bobbinth]

It seems like probability of an invalid execution trace being accepted can be calculated as:

([constraint degree] / [extension factor])^[execution trace queries]

For example, if constraint degree = 4, extension factor = 8, and number of execution trace queries = 80, an invalid execution trace has about 8.3 / 10^-25 chance of being accepted. This should be roughly equivalent to 80-bit security level.

Similarly, if constraint degree = 4, extension factor = 16, and number of execution trace queries = 64, the probability is 2.9 / 10^-39 (which is roughly equivalent to 128-bit security level).

This is only for the execution trace security - so, a formula for FRI proof security is still needed, and hash function security / field size probably also come into play.

[bobbinth]

From here: https://medium.com/starkware/starkdex-deep-dive-the-stark-core-engine-497942d0f0ab

In order to achieve the required soundness of the protocol, the query phase is repeated multiple times. For a blowup factor of 2ⁿ, each query roughly contributes n bits of security.

This is about FRI proofs. So, it seems like FRI proof soundness can be calculated as:

log₂([extension factor]) * [fri proof queries]

For example, if extension factor = 8 and the number of FRI proof queries = 40, we get soundness of of about 120 bits.

Similarly, if extension factor = 16 and the number of queries is 32, the soundness is 128 bits.

If this (and the previous posts) is correct, the only remaining pieces left are: (1) security of the hash function and (2) size of the field used. The latter one may not be relevant at all.

[bobbinth]

To sum up the previous two posts, it seems like soundness of STARK proofs can be approximated as:

soundness = min(log₂((f/d)^q₁), log₂(f) * q₂, c)

where:

• f is the extension (or blow-up) factor,
• d is max constraint degree,
• q₁ is the number of execution trace queries,
• q₂ is the number of FRI proof queries,
• c is collision resistance level of the hash function.

Example 1: when f = 16, d = 4, q₁ = 48, q₂ = 24, and c = 128, the soundness is ≈ 96 bits.

Example 2: when f = 16, d = 4, q₁ = 64, q₂ = 32, and c = 128, the soundness is ≈ 128 bits.

Some open questions:

1. In the above formula, constraint degree doesn't seem to impact soundness of FRI proof - is that right?
2. For FRI proofs, StarkWare always increases polynomial degree to the nearest power of 2 (see "Degree Adjustment" here). We don't do that. Does this make any difference?
3. Is the way I'm thinking about the security of the hash function correct?
4. Are there any other considerations I'm missing?

[bobbinth]

Seems like soundness of FRI does depend on constraint degree - so, the formula should be adjusted. Great analysis is here: https://eprint.iacr.org/2019/1020