Comments (6)
I think the first part will definitely work. The second part will also kind of work, but I doubt savings would be more than about 500 bytes in most cases.
The reason for the second part is that we still need to send most of the remainder. We can skip only positions which we get from folding. For example, if the remainder size is 128 elements, and and the proof contains 30 queries, then the best we could hope for is that 30 of 128 elements can be skipped. If we are in a 128-bit field, these 30 skipped elements would result in proof size reduction of 30 * 16 = 480 bytes.
from winterfell.
The first point of this was addressed in #128
from winterfell.
There is actually another optimization we can do which makes the second point here irrelevant. Specifically, instead of sending the actual codeword for the remainder (which we then need to interpolate into a polynomial in coefficient form), we can just send the polynomial in coefficient form. Then, the verifier would evaluate the polynomial and make sure the resulting evaluations match the commitment.
Depending on the blowup factor, this could result in signifiant savings (i.e.,g 1KB or more).
from winterfell.
Yes, but I think that this is exactly the optimization I mentioned at the start of issue 0xPolygonMiden/miden-vm#568 . Then, as mentioned there, the iNTT check becomes unnecessary as one can just evaluate at
from winterfell.
Actually, an NTT on the verifier side might make sense for remainder polynomials of large degree.
from winterfell.
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.