Comments (8)
The degree of equation 4 is not 6.
Denoting
This is an equation of degree 2, the maximum between
- degree of temporary variable
$m_i$ + degree of cell$A_{i,0}$ - degree of temporary variable
$m_{i+1}$ + degree of cell$A_{i,0}$
(note that both are of same degree)
from winterfell.
In your evaluate_transition function, you wrote
if num_from_state(current) == E::ONE {
return;
}
You cannot return early while evaluating the constraints, this doesn't mean anything valid algebraically speaking. When the prover constructs the original execution trace, it fills it with the actual values of the program. Here, it consists on the different number of the Collatz sequence, plus some additional variables like binary values.
To prove consistency of this trace without explicitly disclosing it, among other things (I insist on this), the prover will allow the verifier to check correctness of the constraints on two consecutive rows of an extended trace, defined over the LDE domain. On this domain, the relations look rubbish, i.e. you'll never (with high probability) get a cell element that equals to one, as you expect it in your code.
If you want your statement to be "I want to prove to you that starting number N reaches 1 under Collatz conjecture after k steps", you may want to include the number of steps k in your public inputs, and define a trace exemption (you can see how it is done in vdf/exempt/air.rs
example), to define which rows should be ignored. This will maintain the algebraic properties when extending the trace to a larger domain (but I won't cover the details on how this works here) and should make your example work.
from winterfell.
I found there are rescue::enforce_round constraints which have degree of 3 for the above first six terms
Merkle example uses the Rescue implementation over the 128 bit field implemented here. The degree of the forward s-box is 5 (the value by which we exponentiate each element). Hence the degree is 5, and not 3.
Hashing is applied when the periodic column hash_flag
is on. When it is not, (i.e. hash_init_flag
is on), we do not compute any Rescue permutation, but just ensure we placed the previously computed hash into the correct position. This is reflected by:
result.agg_constraint(0, hash_init_flag, not_bit * are_equal(current[0], next[0]));
result.agg_constraint(1, hash_init_flag, not_bit * are_equal(current[1], next[1]));
result.agg_constraint(2, hash_init_flag, bit * are_equal(current[0], next[2]));
result.agg_constraint(3, hash_init_flag, bit * are_equal(current[1], next[3]));
Here, current[i]
and next[j]
are both of degree 1. are_equal
does not increase the degree (only subtraction, no multiplication). Hence the total degree is 2 (ignoring the periodic flag), as we multiply by either bit
or not_bit
. Because this degree is lower than the Rescue permutation degree, we indicate 5 when defining the transition contraint degrees.
from winterfell.
You may want to familiarize yourself with the Degree of a polynomial, especially section Behavior under polynomial operations.
from winterfell.
Thank @Nashtare for the helpful answer! What a friendly community!
Finally, I completed my first STARK try using winterfell. Here is the fixed version collatz sequence example, I update it for people who are interested.
Confusion was resolved, so I close the issue.
from winterfell.
@Nashtare Thank you, sir. I got your explanation about the merkle tree example. But I am still confused about the rule of setting constraint degree. For example, I try to implement The Collatz Sequence Execution Trace example in the Starkware Arithmization I blog for study.
Take 52 as the input, the trace table is shown below.
It is noted that the trace table has a length of 12, which is not a power of 2. So I just pad the trace table using zero, so that it has a length of 16. I am not sure whether this will have a pact on constraints' degrees.
The collatz sequence CI statement has 4 constraints, the first two are boundary constraints, which will be expressed in get_assertions
using a vector of winterfell::Assertion
. The other two are normal constraints, which should correspond to a Vec<TransitionConstraintDegree>
. Here I write the third constraint as a sum of is_binary
. Since the sum operation does not increase the degree, we only consider the square operation in is_binary
, then I determine the degree is 2.
// TransitionConstraintDegree::new(2)
for i in 0..TRACE_WIDTH {
result[0] += is_binary(current[i]);
}
For the fourth constraint, the first column multiplies every six columns in the trace table, so I think the degree is 6. But it did not work. I am not sure whether the pad impacts the degree or if I made a false degree.
What's the right degree here, or should I pad the trace table? what's the right way to implement the collatz sequence example?
from winterfell.
Thank you, sir, you mentioned the behavior under polynomial operations, and I suddenly understood.
Now, I am sure the degree of the fourth constraint is 2. I changed it in my implementation code, however, it still panics with the below error. Seems I got something else wrong.
set assertion for initial number BaseElement(52) and step BaseElement(11)
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `[15, 15]`,
right: `[15, 31]`: transition constraint degrees didn't match
expected: [ 15, 15]
actual: [ 15, 31]', D:\devnow\paper-2023\winterfell\prover\src\constraints\evaluation_table.rs:221:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
from winterfell.
I upload my buggy code of the above example. Here is diff.
from winterfell.
Related Issues (20)
- Will it be made into zkvm in the future? HOT 1
- Remove duplicate query check in FRI HOT 3
- Implementing Keccak256 HOT 4
- mulfib8 example circuit is underconstrained
- `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
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.