Comments (5)
Thank you for looking into this! Yes, the issue is exactly where you've identified.
Basically, when we serialize field elements, they are serialized according to their internal representation, which for f62 field is in the range [0, 2M)
. But then we try to de-serialize them, we only accept elements in the range [0, M)
.
The proper way to handle this is to serialize elements according to canonical representation (to make sure they are in [0, M)
range. We also need to make sure that when we hash the elements, we hash them in canonical form as well (so that hashes are consistent between the prover and the verifier). There are a couple potential ways to go about this - but I'm not sure which one of them will have least performance impact. So, there is still some work that needs to be done before the f62 examples work.
In terms of performance impact, I'd expect switching to f62 field to speed up proving time by a factor of 4x - 5x.
from winterfell.
I was getting for same security level a speed up factor of only ~x1.8, or maybe it:s because the AIR for the Fib sequence is extremely simple?
Yes - that's right! In general, only the first 5 steps of the protocol are executed in the base field (from trace generation to constraint evaluation). The rest is executed in the extension field. And the complexity of the first 5 steps is much more dependent on the complexity of AIR than that of all the remaining steps. For example, for something like simple Fibonacci example, the first 5 steps take up about 50% of proving time. While for something like like Lamport signature aggregation (one of the more complicated examples), the first 5 steps take up 85% - 90% of proving time.
So, I'd expect that as AIR gets more complex, the benefit of using smaller fields increases - but I think it would be interesting to see if it actually gets closer to 4x - 5x I quoted or it would be more in the 3x - 4x range.
Would the speed-up factor of x4/x5 be similar between a field of size 256bit and the current 128-bit field?
I'd expect something in the similar ballpark but hard to say without running actual experiments. Btw, for a larger prime, it is probably beneficial to go with a 252-bit prime which is actively being used in various projects (primarily by StarkWare). The prime is 2251 + 17 * 2192 + 1.
from winterfell.
Is there anything to be done outside of the Air circuit and some helper functions?
I thought that both prover and verifier were generic over the size of the field, and I tried to make a dummy example with f62 to get a grasp of performance difference but verification is failing, always at the same step (trace query deserialization, with whatever value the program is holding):
Failed to verify proof: proof deserialization failed: trace query deserialization failed: invalid field element: value 5911323183101409168 is greater than or equal to the field modulus
I made a very basic example (by just copying the fib repo in example/ and changing the field, nothing to be considered serious!). The code is here: Nashtare@5615d8d
While investigating, I realized that function mul
of both f62 and f128 implementations are mentioning a and b are assumed to be in [0, 2M).
which is not ensured in other functions calling mul
. I haven't checked further whether this could have a negative impact, or whether there were other related mismatch between documentation and actual code.
from winterfell.
Ah thanks for the explanation! I thought I was doing something wrong 😅
As for the performance comparison on the prover side, is it at the same level of security? Like default f128 vs quadratic extension of f62? Because with the Fibonacci example, I was getting for same security level a speed up factor of only ~x1.8, or maybe it:s because the AIR for the Fib sequence is extremely simple? Would the speed-up factor of x4/x5 be similar between a field of size 256bit and the current 128-bit field (granted we use a nice prime for f256)?
from winterfell.
Closing this as we already have FibSmall example which uses f64
field.
from winterfell.
Related Issues (20)
- `f64` field: `BaseElement` should not be convertible from `u64` or `u128` without error HOT 1
- Add serialization/deserialization for `usize` type HOT 1
- Accomodating more expressive transition constraints HOT 3
- `TraceTable::with_meta()` should be marked `unsafe`
- Suggestion: Remove outdated griffin hash implementation HOT 1
- Generalize auxiliary trace building logic HOT 2
- Simplify 2-d matrix types
- Generalize `TransitionConstraints` and `BoundaryConstraints` HOT 1
- Consider using the standard benchmark harness instead of criterion HOT 1
- DEEP polynomial with Lagrange kernel HOT 1
- `Deserializable` should have an associated type error
- `Proof::security_leve()` should take into account auxiliary proof
- `group_vector_elements` panics during account code compilation HOT 2
- Verify GKR proof in `Trace::validate()`
- FFT-based division to improve DEEP composition polynomial computation
- GKR-LogUp: additional required API changes HOT 3
- Add `Sync` as a required trait for `ElementHasher`.
- Make a `DomainLength` trait for `VectorCommitment::Proof` and `VectorCommitment::MultiProof`
- Add `Item` associated type to `VectorCommitment`
- Refactor LogUp-GKR
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 winterfell.