Migrate to next release of Winterfell

Al-Kindi-0 commented 1 month ago

Describe your changes

Checklist before requesting a review

Repo forked and branch created from next according to naming convention.
Commit messages and codestyle follow conventions.
Relevant issues are linked in the PR description.
Tests added for new functionality.
Documentation/comments updated according to changes.

bobbinth commented 3 weeks ago

Thank you! Not a review yet, but one interesting thing to check would the performance between this and the next branch (and maybe even vs. main branch as well).

Al-Kindi-0 commented 3 weeks ago

I am seeing a bit of a degradation between this branch and next:

This branch

============================================================
Generated a program to compute 50000-th Fibonacci term; expected result: 8488067465521884829
--------------------------------
INFO     prove_program [ 8.30s | 2.14% / 100.00% ]
INFO     ┝━ execute_program [ 119ms | 1.43% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 262144 steps (41% padded) in 119 ms
INFO     ┝━ build_domain [ 3.93ms | 0.05% ] trace_length: 262144 | lde_domain_size: 2097152
INFO     ┝━ commit_to_main_trace_segment [ 3.67s | 0.00% / 44.18% ]
INFO     │  ┝━ extend_execution_trace [ 3.28s | 39.54% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 385ms | 4.64% ] commitment_domain_size: 2097152
INFO     ┝━ commit_to_aux_trace_segment [ 984ms | 0.00% / 11.85% ]
INFO     │  ┝━ extend_execution_trace [ 724ms | 8.72% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 260ms | 3.13% ] commitment_domain_size: 2097152
INFO     ┝━ evaluate_constraints [ 2.04s | 24.54% ] ce_domain_size: 2097152
INFO     ┝━ commit_to_constraint_evaluations [ 1.01s | 0.00% / 12.20% ]
INFO     │  ┝━ build_composition_poly_columns [ 116ms | 1.40% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 658ms | 7.93% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 239ms | 2.87% ] log_domain_size: 21
INFO     ┝━ build_deep_composition_poly [ 147ms | 1.78% ]
INFO     ┝━ evaluate_deep_composition_poly [ 87.4ms | 1.05% ]
INFO     ┝━ compute_fri_layers [ 46.1ms | 0.55% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 226µs | 0.00% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 18.4ms | 0.22% ]
--------------------------------
Executed program in 8301 ms
Stack outputs: [8488067465521884829]
Execution proof size: 87 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 1.07ms | 100.00% ]
Execution verified in 1 ms

NEXT

============================================================
Generated a program to compute 50000-th Fibonacci term; expected result: 8488067465521884829
--------------------------------
INFO     prove_program [ 8.16s | 2.11% / 100.00% ]
INFO     ┝━ execute_program [ 118ms | 1.45% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 262144 steps (41% padded) in 118 ms
INFO     ┝━ build_domain [ 2.76ms | 0.03% ] trace_length: 262144 | lde_domain_size: 2097152
INFO     ┝━ commit_to_main_trace_segment [ 3.68s | 0.00% / 45.05% ]
INFO     │  ┝━ extend_execution_trace [ 3.31s | 40.52% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 370ms | 4.53% ] tree_depth: 21
INFO     ┝━ commit_to_aux_trace_segment [ 862ms | 0.00% / 10.56% ]
INFO     │  ┝━ extend_execution_trace [ 724ms | 8.87% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 138ms | 1.69% ] tree_depth: 21
INFO     ┝━ evaluate_constraints [ 2.15s | 26.35% ] ce_domain_size: 2097152
INFO     ┝━ commit_to_constraint_evaluations [ 886ms | 0.00% / 10.86% ]
INFO     │  ┝━ build_composition_poly_columns [ 113ms | 1.38% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 661ms | 8.09% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 113ms | 1.38% ] tree_depth: 21
INFO     ┝━ build_deep_composition_poly [ 137ms | 1.67% ]
INFO     ┝━ evaluate_deep_composition_poly [ 92.5ms | 1.13% ]
INFO     ┝━ compute_fri_layers [ 44.8ms | 0.55% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 211µs | 0.00% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 18.2ms | 0.22% ]
--------------------------------
Executed program in 8164 ms
Stack outputs: [8488067465521884829]
Execution proof size: 87 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 1.12ms | 100.00% ]

Al-Kindi-0 commented 3 weeks ago

I have run the Fibonacci example as I am getting the following error when running the Blake one:

INFO     prove_program [ 149ms | 0.01% / 100.00% ]
INFO     ┕━ execute_program [ 149ms | 99.99% ]
Error:   x Main thread panicked.
  |-> at miden/src/examples/mod.rs:129:82
  `-> called `Result::unwrap()` on an `Err` value: OutputStackOverflow(8)
  help: set the `RUST_BACKTRACE=1` environment variable to display a
        backtrace.

I have also tried to benchmark main but I am getting an error at the assembler level:

--> assembly/src/assembler/mod.rs:180:40
    |
180 |                     let mutable_self = &mut *(self as *const _ as *mut Assembler);
    |                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: for more information, visit <https://doc.rust-lang.org/book/ch15-05-interior-mutability.html>
    = note: `#[deny(invalid_reference_casting)]` on by default

bobbinth commented 3 weeks ago

I have also tried to benchmark main but I am getting an error at the assembler level:

--> assembly/src/assembler/mod.rs:180:40
    |
180 |                     let mutable_self = &mut *(self as *const _ as *mut Assembler);
    |                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: for more information, visit <https://doc.rust-lang.org/book/ch15-05-interior-mutability.html>
    = note: `#[deny(invalid_reference_casting)]` on by default

Is it possible that you have a really old version of main/next? This line of code doesn't exist in the current branches.

Al-Kindi-0 commented 3 weeks ago

main is indeed behind but next is up to date

Al-Kindi-0 commented 3 weeks ago

Here is the numbers for main:

============================================================
Generated a program to compute 50000-th Fibonacci term; expected result: 8488067465521884829
--------------------------------
INFO     prove_program [ 8.15s | 2.20% / 100.00% ]
INFO     ┝━ execute_program [ 125ms | 1.53% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 262144 steps (41% padded) in 124 ms
INFO     ┝━ build_domain [ 2.76ms | 0.03% ] trace_length: 262144 | lde_domain_size: 2097152
INFO     ┝━ commit_to_main_trace_segment [ 3.62s | 0.00% / 44.45% ]
INFO     │  ┝━ extend_execution_trace [ 3.27s | 40.10% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 355ms | 4.35% ] tree_depth: 21
INFO     ┝━ commit_to_aux_trace_segment [ 869ms | 0.00% / 10.66% ]
INFO     │  ┝━ extend_execution_trace [ 722ms | 8.86% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 147ms | 1.80% ] tree_depth: 21
INFO     ┝━ evaluate_constraints [ 2.17s | 26.57% ] ce_domain_size: 2097152
INFO     ┝━ commit_to_constraint_evaluations [ 887ms | 0.00% / 10.88% ]
INFO     │  ┝━ build_composition_poly_columns [ 127ms | 1.56% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 649ms | 7.96% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 111ms | 1.36% ] tree_depth: 21
INFO     ┝━ build_deep_composition_poly [ 145ms | 1.78% ]
INFO     ┝━ evaluate_deep_composition_poly [ 89.2ms | 1.09% ]
INFO     ┝━ compute_fri_layers [ 45.5ms | 0.56% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 3.03ms | 0.04% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 17.1ms | 0.21% ]
--------------------------------
Executed program in 8151 ms
Stack outputs: [8488067465521884829]
Execution proof size: 88 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 1.08ms | 100.00% ]
Execution verified in 1 ms

Al-Kindi-0 commented 3 weeks ago

Here are the current results after fixing a bug when using partitioned hashing for commitment:

Current

============================================================
Generated a program to compute 50-th iteration of BLAKE3 1-to-1 hash; expected result: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
--------------------------------
INFO     prove_program [ 8.18s | 2.35% / 100.00% ]
INFO     ┝━ execute_program [ 167ms | 2.04% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 262144 steps (8% padded) in 166 ms
INFO     ┝━ build_domain [ 2.78ms | 0.03% ] trace_length: 262144 | lde_domain_size: 2097152
INFO     ┝━ commit_to_main_trace_segment [ 3.73s | 0.00% / 45.60% ]
INFO     │  ┝━ extend_execution_trace [ 3.34s | 40.87% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 387ms | 4.74% ] commitment_domain_size: 2097152
INFO     ┝━ commit_to_aux_trace_segment [ 871ms | 0.00% / 10.64% ]
INFO     │  ┝━ extend_execution_trace [ 731ms | 8.94% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 139ms | 1.70% ] commitment_domain_size: 2097152
INFO     ┝━ evaluate_constraints [ 2.02s | 24.68% ] ce_domain_size: 2097152
INFO     ┝━ commit_to_constraint_evaluations [ 902ms | 0.00% / 11.03% ]
INFO     │  ┝━ build_composition_poly_columns [ 114ms | 1.39% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 667ms | 8.15% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 121ms | 1.48% ] log_domain_size: 21
INFO     ┝━ build_deep_composition_poly [ 136ms | 1.67% ]
INFO     ┝━ evaluate_deep_composition_poly [ 94.7ms | 1.16% ]
INFO     ┝━ compute_fri_layers [ 46.3ms | 0.57% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 1.75ms | 0.02% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 17.7ms | 0.22% ]
--------------------------------
Executed program in 8181 ms
Stack outputs: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
Execution proof size: 86 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 1.10ms | 100.00% ]
Execution verified in 1 ms

Next

============================================================
Generated a program to compute 50-th iteration of BLAKE3 1-to-1 hash; expected result: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
--------------------------------
INFO     prove_program [ 8.32s | 2.35% / 100.00% ]
INFO     ┝━ execute_program [ 169ms | 2.03% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 262144 steps (8% padded) in 168 ms
INFO     ┝━ build_domain [ 2.70ms | 0.03% ] trace_length: 262144 | lde_domain_size: 2097152
INFO     ┝━ commit_to_main_trace_segment [ 3.71s | 0.00% / 44.54% ]
INFO     │  ┝━ extend_execution_trace [ 3.35s | 40.22% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 360ms | 4.32% ] tree_depth: 21
INFO     ┝━ commit_to_aux_trace_segment [ 889ms | 0.00% / 10.69% ]
INFO     │  ┝━ extend_execution_trace [ 750ms | 9.01% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 139ms | 1.67% ] tree_depth: 21
INFO     ┝━ evaluate_constraints [ 2.14s | 25.75% ] ce_domain_size: 2097152
INFO     ┝━ commit_to_constraint_evaluations [ 884ms | 0.00% / 10.63% ]
INFO     │  ┝━ build_composition_poly_columns [ 122ms | 1.47% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 644ms | 7.74% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 118ms | 1.41% ] tree_depth: 21
INFO     ┝━ build_deep_composition_poly [ 172ms | 2.06% ]
INFO     ┝━ evaluate_deep_composition_poly [ 95.4ms | 1.15% ]
INFO     ┝━ compute_fri_layers [ 45.3ms | 0.54% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 823µs | 0.01% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 18.1ms | 0.22% ]
--------------------------------
Executed program in 8320 ms
Stack outputs: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
Execution proof size: 88 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 1.18ms | 100.00% ]
Execution verified in 1 ms

Al-Kindi-0 commented 3 weeks ago

Here are the result after the most recent patch to Winterfell:

Next

============================================================
Generated a program to compute 50-th iteration of BLAKE3 1-to-1 hash; expected result: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
--------------------------------
INFO     prove_program [ 8.19s | 2.09% / 100.00% ]
INFO     ┝━ execute_program [ 157ms | 1.91% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 262144 steps (8% padded) in 156 ms
INFO     ┝━ build_domain [ 2.77ms | 0.03% ] trace_length: 262144 | lde_domain_size: 2097152
INFO     ┝━ commit_to_main_trace_segment [ 3.65s | 0.00% / 44.64% ]
INFO     │  ┝━ extend_execution_trace [ 3.28s | 40.09% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 372ms | 4.55% ] tree_depth: 21
INFO     ┝━ commit_to_aux_trace_segment [ 867ms | 0.00% / 10.59% ]
INFO     │  ┝━ extend_execution_trace [ 717ms | 8.75% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 150ms | 1.83% ] tree_depth: 21
INFO     ┝━ evaluate_constraints [ 2.16s | 26.42% ] ce_domain_size: 2097152
INFO     ┝━ commit_to_constraint_evaluations [ 879ms | 0.00% / 10.74% ]
INFO     │  ┝━ build_composition_poly_columns [ 119ms | 1.46% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 640ms | 7.82% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 119ms | 1.46% ] tree_depth: 21
INFO     ┝━ build_deep_composition_poly [ 140ms | 1.71% ]
INFO     ┝━ evaluate_deep_composition_poly [ 89.8ms | 1.10% ]
INFO     ┝━ compute_fri_layers [ 46.1ms | 0.56% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 2.31ms | 0.03% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 14.5ms | 0.18% ]
--------------------------------
Executed program in 8187 ms
Stack outputs: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
Execution proof size: 87 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 1.21ms | 100.00% ]
Execution verified in 1 ms

This

============================================================
Generated a program to compute 50-th iteration of BLAKE3 1-to-1 hash; expected result: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
--------------------------------
INFO     prove_program [ 8.17s | 0.76% / 100.00% ]
INFO     ┝━ execute_program [ 160ms | 1.95% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 262144 steps (8% padded) in 159 ms
INFO     ┝━ build_domain [ 3.11ms | 0.04% ] trace_length: 262144 | lde_domain_size: 2097152
INFO     ┝━ commit_to_main_trace_segment [ 3.65s | 0.00% / 44.71% ]
INFO     │  ┝━ extend_execution_trace [ 3.28s | 40.19% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 369ms | 4.52% ] commitment_domain_size: 2097152
INFO     ┝━ build_aux_trace [ 110ms | 1.34% ]
INFO     ┝━ commit_to_aux_trace_segment [ 864ms | 0.00% / 10.58% ]
INFO     │  ┝━ extend_execution_trace [ 721ms | 8.83% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 143ms | 1.75% ] commitment_domain_size: 2097152
INFO     ┝━ evaluate_constraints [ 2.15s | 26.27% ] ce_domain_size: 2097152
INFO     ┝━ commit_to_constraint_evaluations [ 876ms | 0.00% / 10.73% ]
INFO     │  ┝━ build_composition_poly_columns [ 120ms | 1.47% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 641ms | 7.85% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 115ms | 1.41% ] log_domain_size: 21
INFO     ┝━ build_deep_composition_poly [ 140ms | 1.72% ]
INFO     ┝━ evaluate_deep_composition_poly [ 91.0ms | 1.11% ]
INFO     ┝━ compute_fri_layers [ 45.6ms | 0.56% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 3.06ms | 0.04% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 14.2ms | 0.17% ]
--------------------------------
Executed program in 8167 ms
Stack outputs: [664088198, 4259451035, 218783966, 2579530912, 3535070201, 4210849069, 2460906358, 3194996903]
Execution proof size: 86 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 1.10ms | 100.00% ]
Execution verified in 1 ms

bobbinth commented 3 weeks ago

This is what i'm getting on my machine:

============================================================
Generated a program to compute 200-th iteration of BLAKE3 1-to-1 hash; expected result: [3273414978, 861395390, 3406933114, 1249690799, 3478855123, 2478635211, 4040123218, 3120808209]
--------------------------------
INFO     prove_program [ 8.02s | 1.29% / 100.00% ]
INFO     ┝━ execute_program [ 497ms | 6.20% ]
INFO     ┝━ ｉ [info]: Generated execution trace of 70 columns and 1048576 steps (8% padded) in 497 ms
INFO     ┝━ build_domain [ 7.81ms | 0.10% ] trace_length: 1048576 | lde_domain_size: 8388608
INFO     ┝━ commit_to_main_trace_segment [ 2.84s | 0.00% / 35.42% ]
INFO     │  ┝━ extend_execution_trace [ 2.00s | 24.91% ] num_cols: 70 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 843ms | 10.51% ] commitment_domain_size: 8388608
INFO     ┝━ build_aux_trace [ 260ms | 3.25% ]
INFO     ┝━ commit_to_aux_trace_segment [ 765ms | 0.00% / 9.53% ]
INFO     │  ┝━ extend_execution_trace [ 456ms | 5.69% ] num_cols: 7 | blowup: 8
INFO     │  ┕━ compute_execution_trace_commitment [ 309ms | 3.85% ] commitment_domain_size: 8388608
INFO     ┝━ evaluate_constraints [ 2.24s | 27.97% ] ce_domain_size: 8388608
INFO     ┝━ commit_to_constraint_evaluations [ 770ms | 0.00% / 9.60% ]
INFO     │  ┝━ build_composition_poly_columns [ 128ms | 1.59% ] num_columns: 8
INFO     │  ┝━ evaluate_composition_poly_columns [ 378ms | 4.72% ]
INFO     │  ┕━ compute_constraint_evaluation_commitment [ 263ms | 3.28% ] log_domain_size: 23
INFO     ┝━ build_deep_composition_poly [ 331ms | 4.13% ]
INFO     ┝━ evaluate_deep_composition_poly [ 65.6ms | 0.82% ]
INFO     ┝━ compute_fri_layers [ 77.6ms | 0.97% ] num_layers: 4
INFO     ┝━ determine_query_positions [ 2.82ms | 0.04% ] grinding_factor: 16 | num_positions: 27
INFO     ┕━ build_proof_object [ 56.8ms | 0.71% ]
--------------------------------
Executed program in 8021 ms
Stack outputs: [3273414978, 861395390, 3406933114, 1249690799, 3478855123, 2478635211, 4040123218, 3120808209]
Execution proof size: 100 KB
Execution proof security: 96 bits
--------------------------------
INFO     verify_program [ 904µs | 100.00% ]
Execution verified in 0 ms

This is roughly in-line with what we were getting before.

One thing that really stands out to me is that trace generation (main + auxiliary) takes up 0.75 seconds. Ideally, we should figure out how to bring this down to under 100ms.

Al-Kindi-0 commented 3 weeks ago

One thing that really stands out to me is that trace generation (main + auxiliary) takes up 0.75 seconds. Ideally, we should figure out how to bring this down to under 100ms.

Yes, that's high indeed. We should start investigating ways of "parallelizing" witness generation as this will be useful to us in many different places.

Al-Kindi-0 commented 3 weeks ago

I think one remaining thing is to make sure Metal prover is also updated to work with the lates interface. Are you able to check this on your end?

I wouldn't be able to test on my machine.

Al-Kindi-0 commented 2 weeks ago

Very cool, thanks!

0xPolygonMiden / miden-vm

Migrate to next release of Winterfell #1533

Describe your changes

Checklist before requesting a review