Organization
- @OpenVM
Engagement Type
Cantina Reviews
Period
-
Findings
Low Risk
1 findings
1 fixed
0 acknowledged
Informational
5 findings
5 fixed
0 acknowledged
Low Risk1 finding
FRI parameters do not strictly provide 100 bits of provable security
Description
The
standard_fri_params_with_100_bits_securitydefines FRI parameters to reach 100 bits of provable security. These parameters relies on several assumptions:- the challenge field has size at least 2^123
- for
log_blowup = 1, multi-FRI will be run with at most width 30000 at any level - for
log_blowup > 1, multi-FRI will be run with at most width 2000 at any level
Considering the equation
extension_field_bits - log2(2^max_height * (num_columns - 1))and the worst-case scenario, we end up with the following calculations.The OpenVM configuration specifies an extension degree of . Since the BabyBear prime is slightly smaller than , the resulting extension field size is strictly less than 124 bits. This satisfies the documented assumption that "the challenge field has size at least " (treating 123 bits as the conservative lower bound).
Executing the full calculations results in the query security reaching 100 bits. However, the commit phase security is a bit lower than 100 bits (99.X bits).
Proof of Concept
Using extension field bits: 123.48====================================================================== --- Analyzing Configuration for log_blowup = 1 ---[Commit Phase] Max Columns: 30,000 Batching Loss: 39.87 bits (log2(Rows * Cols)) Base Security: 83.61 bits + PoW Grinding: 16 bits >> Total Commit Security: 99.61 bits[Query Phase] Code Rate: 0.5 Unique Decoding: 0.25 Bits Per Query: 0.4150 Query Bits: 80.10 bits (193 queries) + PoW Grinding: 20 bits >> Total Query Security: 100.10 bits >> FINAL PROVABLE SECURITY: 99.61 bits-------------------------------------------------- --- Analyzing Configuration for log_blowup = 2 ---[Commit Phase] Max Columns: 2,000 Batching Loss: 35.97 bits (log2(Rows * Cols)) Base Security: 87.51 bits + PoW Grinding: 12 bits >> Total Commit Security: 99.51 bits[Query Phase] Code Rate: 0.25 Unique Decoding: 0.375 Bits Per Query: 0.6781 Query Bits: 80.01 bits (118 queries) + PoW Grinding: 20 bits >> Total Query Security: 100.01 bits >> FINAL PROVABLE SECURITY: 99.51 bits-------------------------------------------------- --- Analyzing Configuration for log_blowup = 4 ---[Commit Phase] Max Columns: 2,000 Batching Loss: 35.97 bits (log2(Rows * Cols)) Base Security: 87.51 bits + PoW Grinding: 12 bits >> Total Commit Security: 99.51 bits[Query Phase] Code Rate: 0.0625 Unique Decoding: 0.46875 Bits Per Query: 0.9125 Query Bits: 80.30 bits (88 queries) + PoW Grinding: 20 bits >> Total Query Security: 100.30 bits >> FINAL PROVABLE SECURITY: 99.51 bits--------------------------------------------------The following Python script was used for the full calculation.
import mathimport argparse # OpenVM Trace Height Parameters (from codebase analysis):# # 1. DEFAULT_MAX_TRACE_HEIGHT_BITS = 22 # -> Default segment size limit: 2^22 = 4,194,304 rows# Found in: openvm/crates/vm/src/arch/execution_mode/metered/segment_ctx.rs## 2. NATIVE_MAX_TRACE_HEIGHTS (component-specific limits):# -> Maximum: 2^25 = 33,554,432 rows for FriReducedOpeningAir# Found in: openvm/extensions/native/circuit/src/extension/mod.rs## 3. Notable component limits:# - Program: 2^22 (4,194,304)# - FriReducedOpeningAir: 2^25 (33,554,432) <- LARGEST# - FieldArithmeticAir: 2^24 (16,777,216)# - AccessAdapter: 2^23 (8,388,608)## For security analysis, we use the maximum (2^25) for worst-case calculations. def calculate_fri_security(log_blowup, num_queries, commit_pow, query_pow, extension_field_bits): print(f"--- Analyzing Configuration for log_blowup = {log_blowup} ---") # ========================================== # 1. CONSTANTS (Implicit Assumptions) # ========================================== # Field Size: BabyBear (approx 31 bits) extended to degree 4 (~124 bits) # The comment says "at least 2^123", we use 124 for the exact calculation. EXTENSION_FIELD_BITS = extension_field_bits # Max Trace Height (Rows): From OpenVM codebase # - Default: 2^25 (DEFAULT_MAX_TRACE_HEIGHT_BITS = 25) # - Maximum component: 2^25 (FriReducedOpeningAir in NATIVE_MAX_TRACE_HEIGHTS) # Using the maximum for worst-case security analysis MAX_HEIGHT_LOG2 = 25 MAX_ROWS = 2**MAX_HEIGHT_LOG2 # Max Columns (Batching): Varies by blowup factor as per dev reply if log_blowup == 1: MAX_COLS = 30_000 else: MAX_COLS = 2_000 # ========================================== # 2. COMMITMENT PHASE SECURITY (Batching) # ========================================== # Formula: Security = FieldBits - log2(Rows * Cols) + PoW # Note: Developer used (num_columns - 1), but for approx we use num_columns batching_loss_bits = math.log2(MAX_ROWS * (MAX_COLS -1)) base_commit_security = EXTENSION_FIELD_BITS - batching_loss_bits total_commit_security = base_commit_security + commit_pow print(f"[Commit Phase]") print(f" Max Columns: {MAX_COLS:,}") print(f" Batching Loss: {batching_loss_bits:.2f} bits (log2(Rows * Cols))") print(f" Base Security: {base_commit_security:.2f} bits") print(f" + PoW Grinding: {commit_pow} bits") print(f" >> Total Commit Security: {total_commit_security:.2f} bits") # ========================================== # 3. QUERY PHASE SECURITY (Soundness) # ========================================== # Formula: Bits = -NumQueries * log2(1 - delta) + PoW # delta (Unique Decoding Radius) = (1 - Rate) / 2 # Rate = 2^(-log_blowup) rate = 2**(-log_blowup) delta = (1.0 - rate) / 2.0 # Probability of cheating on one query = 1 - delta # If delta is 0.25, prob is 0.75. log2(0.75) is negative. bits_per_query = -math.log2(1.0 - delta) query_security_from_queries = num_queries * bits_per_query total_query_security = query_security_from_queries + query_pow print(f"[Query Phase]") print(f" Code Rate: {rate}") print(f" Unique Decoding: {delta}") print(f" Bits Per Query: {bits_per_query:.4f}") print(f" Query Bits: {query_security_from_queries:.2f} bits ({num_queries} queries)") print(f" + PoW Grinding: {query_pow} bits") print(f" >> Total Query Security: {total_query_security:.2f} bits") # ========================================== # 4. CONCLUSION # ========================================== min_security = min(total_commit_security, total_query_security) print(f"\n>> FINAL PROVABLE SECURITY: {min_security:.2f} bits") print("-" * 50 + "\n") # ==========================================# Run Checks for OpenVM Parameters# ========================================== def main(): parser = argparse.ArgumentParser(description='Calculate FRI security parameters for OpenVM') parser.add_argument('--extension-bits', '-e', type=float, default=30.87 * 4, help='Extension field size in bits (default: 30.87 * 4 = 123.48 for BabyBear^4)') args = parser.parse_args() extension_bits = args.extension_bits print(f"Using extension field bits: {extension_bits:.2f}") print("=" * 70 + "\n") # Case 1: log_blowup = 1 (Wide mode) # Params: queries=193, commit_pow=16, query_pow=20 calculate_fri_security(log_blowup=1, num_queries=193, commit_pow=16, query_pow=20, extension_field_bits=extension_bits) # Case 2: log_blowup = 2 (Standard mode) # Params: queries=118, commit_pow=12, query_pow=20 calculate_fri_security(log_blowup=2, num_queries=118, commit_pow=12, query_pow=20, extension_field_bits=extension_bits) # Case 3: log_blowup = 4 (High Blowup mode) # Params: queries=88, commit_pow=12, query_pow=20 calculate_fri_security(log_blowup=4, num_queries=88, commit_pow=12, query_pow=20, extension_field_bits=extension_bits) if __name__ == "__main__": main()Recommendation
Review the FRI parameters in
standard_fri_params_with_100_bits_security. Consider adding a formal calculations as part of the code with an assertion to ensure 100 bits of security.OpenVM
Fixed.
In PR231, we provide a security calculator to calculate the Fiat-Shamir soundness of the protocol overall. In doing so, we changed the
max_log_domain_size = BabyBear::TWO_ADICITY = 27to support all trace height, with some adjustments to the parameters to ensure 100 bits.However in the course of adding the calculator, we realized that our previous calculations to arrive at 100 bits of security did not account for the error contribution from the DEEP-ALI part of the protocol. See Protocol 3 of "A summary on the FRI low degree test", Ulrich Haböck. Due to the nature of the DEEP step, the only way to reach 100 bits of security with the current BabyBear^4 extension field is to introduce a small additional round of grinding prior to sampling of the
zetaopening point.- The prover and verifier changes to add this grinding have been added to stark-backend in stark-backend PR231
- Updated max constraint count to support openvm standard config in stark-backend PR233
- The recursion circuit changes correspond to it have been added in openvm PR2361
Cantina
Fixed.
The calculator ensures that 100 bits of security is reached with the FRI parameters configuration. Additionally, the DEEP-ALI bits of security calculations are executed in this calculator.
These DEEP-ALI security calculations led to discovering that a PoW grinding phase was needed to ensure a security of 100 bits. It has been added in the stark-backend repository and related changes have been made in openvm repository.
The DEEP PoW grinding configuration is included in the verification key (
VK) and verified by the verifier before thezetachallenge.With the new parameters, the total provable security for the worst-case scenario (trace height ) is raised to >100 bits, fully resolving the finding.
Informational5 findings
100 bits of provable security calculations could be documented
Description
The
standard_fri_params_with_100_bits_securityprovides parameters to reach 100 bits of provable security.Pre-defined FRI parameters with 100 bits of provable security, meaning we do not rely on any conjectures about Reed–Solomon codes (e.g., about proximity gaps) or the ethSTARK Toy Problem Conjecture.
However, these calculations are not documented for each
FriParametersstructure.Recommendation
For transparency purposes, consider adding a comment that details the calculation to reach 100 bits of provable security for each
FriParametersconfiguration.Another solution is to implement a
get_provable_security_bits()function that calculates the provable security bits with an assertion instandard_fri_params_with_100_bits_securityto ensure that it is greater than or equal to 100. This is similar to theget_conjectured_security_bitsfunction and its assertion instandard_fri_params_with_100_bits_conjectured_security.OpenVM
Fixed in PR231.
Cantina
Fixed. The
test_params_provable_securitytest has been added. It details all security bits calculations and assert that the result is greater than or equal to100.stark-backend and openvm versions are not correct
Description
The
openvm/Cargo.tomlfile shows version1.4.2instead of1.5.0.Also, the
stark-backend/Cargo.tomlfile shows version1.2.2instead of1.3.0.Recommendation
Fix the versions for
openvmandstark-backend.OpenVM
Fixed, stark-backend version set to
v1.3.0-rc.0in PR229 and openvm version set tov1.5.0-rc.0in PR231.We will move out of
-rcprior to the final release.Cantina
Fixed.
v1.3.0-rc.0andv1.5.0-rc.0are set in theCargo.tomlfiles.Fibonacci E2E benchmark is not working by default
Description
The Fibonacci E2E benchmark binary panics when it is executed in debug mode.
This is because an assertion is executed to ensure that
max_trace_heightis a power of two, however its default value is1_000_000which is not a power of two.Proof of Concept
Run the
fib_e2ebenchmark without any argument.cargo run --package openvm-benchmarks-prove --bin fib_e2eA
debug_assert!is triggered because themax_trace_heightis not a power of two.thread 'main' panicked at crates/vm/src/arch/execution_mode/metered/segment_ctx.rs:54:9:max_trace_height should be a power of twonote: run with `RUST_BACKTRACE=1` environment variable to display a backtraceRecommendation
Modify the default
max_segment_lengthto be a power of two.diff --git a/benchmarks/prove/src/bin/fib_e2e.rs b/benchmarks/prove/src/bin/fib_e2e.rsindex aa01c90f4..dfbc1c0ea 100644--- a/benchmarks/prove/src/bin/fib_e2e.rs+++ b/benchmarks/prove/src/bin/fib_e2e.rs@@ -12,7 +12,7 @@ async fn main() -> Result<()> { let args = BenchmarkCli::parse(); // Must be larger than RangeTupleCheckerAir.height == 524288- let max_segment_length = args.max_segment_length.unwrap_or(1_000_000);+ let max_segment_length = args.max_segment_length.unwrap_or(1_048_576); let mut config = SdkVmConfig::from_toml(include_str!("../../../guest/fibonacci/openvm.toml"))?.app_vm_config;OpenVM
Fixed in PR2364 by using
1 << 20instead of1_000_000.Cantina.
Fixed. The Fibonacci benchmark does not panic anymore.
todo! can be changed to more appropriate alternative
Description
todo!is used inside of match statement which indicates not yet complete while the current implementation is complete as-is.Recommendation
though the runtime behaviour is same, It should be replaced with more appropriate alternative:
panic!=> for explicit errorunreachable!=> if inputs are sanitized elsewhere
Kitchen-sink benchmark panics
Description
The kitchen-sink benchmark is meant to be a broad, integration-style workload that uses all zkVM functionalities. With this benchmark, OpenVM’s proving/aggregation stack is exercised with all major chips/extensions at once.
This benchmark is supposed to be runnable in both
releaseanddebugmode.However, both execution panics in the current state of the codebase.
Proof of Concept
Execute the benchmark in
releasemode.cargo run --package openvm-benchmarks-prove --bin kitchen_sink --releaseThe
releasemode execution ends up panicking with the following logs:openvm build: Compiling openvm-kitchen-sink-program v0.0.0 (/.../openvm/benchmarks/guest/kitchen-sink)[init] complex #0 = Bn254Fp2 (mod_idx = 4)[init] complex #1 = Bls12_381Fp2 (mod_idx = 6)openvm build: Finished `release` profile [optimized] target(s) in 10.17s thread 'main' panicked at benchmarks/prove/src/bin/kitchen_sink.rs:38:9:assertion `left == right` failed left: 9 right: 1note: run with `RUST_BACKTRACE=1` environment variable to display a backtraceExecute the benchmark in
debugmode.cargo run --package openvm-benchmarks-prove --bin kitchen_sinkThe
debugmode execution ends up panicking with the following logs:openvm build: Compiling openvm-kitchen-sink-program v0.0.0 (/.../openvm/benchmarks/guest/kitchen-sink)[init] complex #0 = Bn254Fp2 (mod_idx = 4)[init] complex #1 = Bls12_381Fp2 (mod_idx = 6)openvm build: Finished `release` profile [optimized] target(s) in 10.18s thread 'main' panicked at /.../openvm/crates/vm/src/arch/execution_mode/metered/memory_ctx.rs:244:9:align_bits (2) must be <= size_bits (0)note: run with `RUST_BACKTRACE=1` environment variable to display a backtraceRecommendation
Fix the kitchen-sink benchmark.
OpenVM
Fixed.
The problems were distinct for debug versus release mode.
For release mode: the fix was done in PR2361. It happened because we extract the max heights in a roundabout way, and we needed to initially turn off segmentation limits (the change was due to an unrelated change in behavior in main).
For debug mode, the reason was that some debug info was being lost in between leaf prover runs. That is fixed in PR2364.
Cantina
Fixed. The kitchen-sink is now runnable in both release and debug mode.