Comments (4)
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.
from genstark.
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 2n, each query roughly contributes n bits of security.
This is about FRI proofs. So, it seems like FRI proof soundness can be calculated as:
log2([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.
from genstark.
To sum up the previous two posts, it seems like soundness of STARK proofs can be approximated as:
soundness = min(log2((f/d)q1), log2(f) * q2, c)
where:
- f is the extension (or blow-up) factor,
- d is max constraint degree,
- q1 is the number of execution trace queries,
- q2 is the number of FRI proof queries,
- c is collision resistance level of the hash function.
Example 1: when f = 16, d = 4, q1 = 48, q2 = 24, and c = 128, the soundness is ≈ 96 bits.
Example 2: when f = 16, d = 4, q1 = 64, q2 = 32, and c = 128, the soundness is ≈ 128 bits.
Some open questions:
- In the above formula, constraint degree doesn't seem to impact soundness of FRI proof - is that right?
- 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?
- Is the way I'm thinking about the security of the hash function correct?
- Are there any other considerations I'm missing?
from genstark.
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
from genstark.
Related Issues (16)
- Add an example STARK for proving knowledge of hash preimage HOT 1
- Refactor arithmetic script parsing HOT 1
- Cannot define repeated readonly registers with only 2 values HOT 1
- Conflicting node versions HOT 2
- Reduce proof size
- Determine appropriate defaults
- Implement example STARK for a Poseidon hash function HOT 1
- Typescript compilation error: cannot find namespace 'WebAssembly' HOT 3
- Low degree proof fails for small number of steps HOT 1
- error when running examples HOT 2
- the link of AirScript is invalid
- Use expressions to define transition function and constraints HOT 1
- Proof size should not depend on the number of boundary and transition constraints HOT 1
- Add an example STARK for proving Merkle tree membership HOT 1
- Potentially simplify linear combination for low degree proof HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from genstark.