starkware-libs · alon-f · May 25, 2025 · May 22, 2025
diff --git a/stwo_cairo_prover/Cargo.lock b/stwo_cairo_prover/Cargo.lock
diff --git a/stwo_cairo_prover/crates/cairo-air/Cargo.toml b/stwo_cairo_prover/crates/cairo-air/Cargo.toml
@@ -5,6 +5,7 @@ edition.workspace = true
 
 [dependencies]
 itertools.workspace = true
+log.workspace = true
 num-traits.workspace = true
 paste.workspace = true
 # TODO(Ohad): Add parallel config.
@@ -18,6 +19,7 @@ starknet-types-core.workspace = true
 stwo-cairo-serialize = { path = "../cairo-serialize" }
 stwo-prover.workspace = true
 thiserror.workspace = true
+serde_json.workspace = true
 
 [dev-dependencies]
 rand.workspace = true
diff --git a/stwo_cairo_prover/crates/cairo-air/src/air.rs b/stwo_cairo_prover/crates/cairo-air/src/air.rs
@@ -64,16 +64,18 @@ where
     }
 }
 
+pub type RelationUsesDict = HashMap<&'static str, u64>;
+
 /// Accumulates the number of uses of each relation in a map.
 pub fn accumulate_relation_uses<const N: usize>(
-    relation_counts: &mut HashMap<&'static str, u32>,
+    relation_uses: &mut RelationUsesDict,
     relation_uses_per_row: [RelationUse; N],
     log_size: u32,
 ) {
     let component_size = 1 << log_size;
     for relation_use in relation_uses_per_row {
         let relation_uses_in_component = relation_use.uses.checked_mul(component_size).unwrap();
-        let prev = relation_counts.entry(relation_use.relation_id).or_insert(0);
+        let prev = relation_uses.entry(relation_use.relation_id).or_insert(0);
         *prev = prev.checked_add(relation_uses_in_component).unwrap();
     }
 }
@@ -153,7 +155,7 @@ impl CairoClaim {
         TreeVec::concat_cols(log_sizes_list.into_iter())
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         let Self {
             public_data: _,
             opcodes,
@@ -175,26 +177,26 @@ impl CairoClaim {
         // - verify_bitwise_xor_*
         // - memory_address_to_id
 
-        opcodes.accumulate_relation_uses(relation_counts);
-        builtins.accumulate_relation_uses(relation_counts);
-        blake_context.accumulate_relation_uses(relation_counts);
-        pedersen_context.accumulate_relation_uses(relation_counts);
-        poseidon_context.accumulate_relation_uses(relation_counts);
+        opcodes.accumulate_relation_uses(relation_uses);
+        builtins.accumulate_relation_uses(relation_uses);
+        blake_context.accumulate_relation_uses(relation_uses);
+        pedersen_context.accumulate_relation_uses(relation_uses);
+        poseidon_context.accumulate_relation_uses(relation_uses);
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             verify_instruction::RELATION_USES_PER_ROW,
             verify_instruction.log_size,
         );
 
         // TODO(ShaharS): Look into the file name of memory_id_to_big.
         // memory_id_to_value has a big value component and a small value component.
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             memory_id_to_big::RELATION_USES_PER_ROW_BIG,
             memory_id_to_value.big_log_size,
         );
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             memory_id_to_big::RELATION_USES_PER_ROW_SMALL,
             memory_id_to_value.small_log_size,
         );
@@ -826,7 +828,7 @@ mod tests {
 
     #[test]
     fn test_accumulate_relation_uses() {
-        let mut relation_counts = HashMap::from([("relation_1", 4), ("relation_2", 10)]);
+        let mut relation_uses = HashMap::from([("relation_1", 4), ("relation_2", 10)]);
         let log_size = 2;
         let relation_uses_per_row = [
             RelationUse {
@@ -839,10 +841,10 @@ mod tests {
             },
         ];
 
-        accumulate_relation_uses(&mut relation_counts, relation_uses_per_row, log_size);
+        accumulate_relation_uses(&mut relation_uses, relation_uses_per_row, log_size);
 
-        assert_eq!(relation_counts.len(), 2);
-        assert_eq!(relation_counts.get("relation_1"), Some(&12));
-        assert_eq!(relation_counts.get("relation_2"), Some(&26));
+        assert_eq!(relation_uses.len(), 2);
+        assert_eq!(relation_uses.get("relation_1"), Some(&12));
+        assert_eq!(relation_uses.get("relation_2"), Some(&26));
     }
 }
diff --git a/stwo_cairo_prover/crates/cairo-air/src/blake/air.rs b/stwo_cairo_prover/crates/cairo-air/src/blake/air.rs
@@ -1,6 +1,5 @@
 use num_traits::Zero;
 use serde::{Deserialize, Serialize};
-use stwo_cairo_adapter::HashMap;
 use stwo_cairo_serialize::CairoSerialize;
 use stwo_prover::constraint_framework::TraceLocationAllocator;
 use stwo_prover::core::air::ComponentProver;
@@ -9,7 +8,7 @@ use stwo_prover::core::channel::Channel;
 use stwo_prover::core::fields::qm31::QM31;
 use stwo_prover::core::pcs::TreeVec;
 
-use crate::air::{accumulate_relation_uses, CairoInteractionElements};
+use crate::air::{accumulate_relation_uses, CairoInteractionElements, RelationUsesDict};
 use crate::components::{
     blake_g, blake_round, blake_round_sigma, triple_xor_32, verify_bitwise_xor_12,
 };
@@ -32,9 +31,9 @@ impl BlakeContextClaim {
             .unwrap_or_default()
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         if let Some(claim) = &self.claim {
-            claim.accumulate_relation_uses(relation_counts);
+            claim.accumulate_relation_uses(relation_uses);
         }
     }
 }
@@ -69,7 +68,7 @@ impl Claim {
         TreeVec::concat_cols(log_sizes)
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         let Self {
             blake_round,
             blake_g,
@@ -83,17 +82,17 @@ impl Claim {
         // - verify_bitwise_xor_12
 
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             blake_round::RELATION_USES_PER_ROW,
             blake_round.log_size,
         );
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             blake_g::RELATION_USES_PER_ROW,
             blake_g.log_size,
         );
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             triple_xor_32::RELATION_USES_PER_ROW,
6D47
             triple_xor_32.log_size,
         );

diff --git a/stwo_cairo_prover/crates/cairo-air/src/builtins_air.rs b/stwo_cairo_prover/crates/cairo-air/src/builtins_air.rs
@@ -1,7 +1,6 @@
 use itertools::chain;
 use num_traits::Zero;
 use serde::{Deserialize, Serialize};
-use stwo_cairo_adapter::HashMap;
 use stwo_cairo_serialize::CairoSerialize;
 use stwo_prover::constraint_framework::TraceLocationAllocator;
 use stwo_prover::core::air::ComponentProver;
@@ -11,7 +10,7 @@ use stwo_prover::core::fields::qm31::{SecureField, QM31};
 use stwo_prover::core::pcs::TreeVec;
 
 use super::air::CairoInteractionElements;
-use crate::air::accumulate_relation_uses;
+use crate::air::{accumulate_relation_uses, RelationUsesDict};
 use crate::components::{
     add_mod_builtin, bitwise_builtin, indented_component_display, mul_mod_builtin,
     pedersen_builtin, poseidon_builtin, range_check_builtin_bits_128, range_check_builtin_bits_96,
@@ -77,7 +76,7 @@ impl BuiltinsClaim {
                 .into_iter(),
         ))
     }
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         let Self {
             add_mod_builtin,
             bitwise_builtin,
@@ -93,7 +92,7 @@ impl BuiltinsClaim {
             ($field:ident, $module:ident) => {
                 if let Some(field) = $field {
                     accumulate_relation_uses(
-                        relation_counts,
+                        relation_uses,
                         $module::RELATION_USES_PER_ROW,
                         field.log_size,
                     );

diff --git a/stwo_cairo_prover/crates/cairo-air/src/opcodes_air.rs b/stwo_cairo_prover/crates/cairo-air/src/opcodes_air.rs
@@ -1,7 +1,6 @@
 use itertools::{chain, Itertools};
 use num_traits::Zero;
 use serde::{Deserialize, Serialize};
-use stwo_cairo_adapter::HashMap;
 use stwo_cairo_serialize::CairoSerialize;
 use stwo_prover::constraint_framework::TraceLocationAllocator;
 use stwo_prover::core::air::ComponentProver;
@@ -12,7 +11,7 @@ use stwo_prover::core::pcs::TreeVec;
 
 use super::air::CairoInteractionElements;
 use super::components::display_components;
-use crate::air::accumulate_relation_uses;
+use crate::air::{accumulate_relation_uses, RelationUsesDict};
 use crate::components::{
     add_ap_opcode, add_opcode, add_opcode_small, assert_eq_opcode, assert_eq_opcode_double_deref,
     assert_eq_opcode_imm, blake_compress_opcode, call_opcode, call_opcode_op_1_base_fp,
@@ -104,7 +103,7 @@ impl OpcodeClaim {
         ))
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         let Self {
             add,
             add_small,
@@ -134,7 +133,7 @@ impl OpcodeClaim {
             ($field:ident, $module:ident) => {
                 $field.iter().for_each(|c| {
                     accumulate_relation_uses(
-                        relation_counts,
+                        relation_uses,
                         $module::RELATION_USES_PER_ROW,
                         c.log_size,
                     )

diff --git a/stwo_cairo_prover/crates/cairo-air/src/pedersen/air.rs b/stwo_cairo_prover/crates/cairo-air/src/pedersen/air.rs
@@ -1,11 +1,10 @@
 use num_traits::Zero;
-use stwo_cairo_adapter::HashMap;
 use stwo_prover::constraint_framework::TraceLocationAllocator;
 use stwo_prover::core::air::ComponentProver;
 use stwo_prover::core::backend::simd::SimdBackend;
 use stwo_prover::core::fields::qm31::QM31;
 
-use crate::air::{accumulate_relation_uses, CairoInteractionElements};
+use crate::air::{accumulate_relation_uses, CairoInteractionElements, RelationUsesDict};
 use crate::components::prelude::*;
 use crate::components::{indented_component_display, partial_ec_mul, pedersen_points_table};
 
@@ -27,9 +26,9 @@ impl PedersenContextClaim {
             .unwrap_or_default()
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         if let Some(claim) = &self.claim {
-            claim.accumulate_relation_uses(relation_counts);
+            claim.accumulate_relation_uses(relation_uses);
         }
     }
 }
@@ -55,7 +54,7 @@ impl Claim {
         TreeVec::concat_cols(log_sizes)
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         let Self {
             partial_ec_mul,
             pedersen_points_table: _,
@@ -65,7 +64,7 @@ impl Claim {
         // - pedersen_points_table
 
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             partial_ec_mul::RELATION_USES_PER_ROW,
             partial_ec_mul.log_size,
         );

diff --git a/stwo_cairo_prover/crates/cairo-air/src/poseidon/air.rs b/stwo_cairo_prover/crates/cairo-air/src/poseidon/air.rs
@@ -1,11 +1,10 @@
 use num_traits::Zero;
-use stwo_cairo_adapter::HashMap;
 use stwo_prover::constraint_framework::TraceLocationAllocator;
 use stwo_prover::core::air::ComponentProver;
 use stwo_prover::core::backend::simd::SimdBackend;
 use stwo_prover::core::fields::qm31::QM31;
 
-use crate::air::{accumulate_relation_uses, CairoInteractionElements};
+use crate::air::{accumulate_relation_uses, CairoInteractionElements, RelationUsesDict};
 use crate::components::prelude::*;
 use crate::components::{
     cube_252, indented_component_display, poseidon_3_partial_rounds_chain,
@@ -30,9 +29,9 @@ impl PoseidonContextClaim {
             .unwrap_or_default()
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         if let Some(claim) = &self.claim {
-            claim.accumulate_relation_uses(relation_counts);
+            claim.accumulate_relation_uses(relation_uses);
         }
     }
 }
@@ -67,7 +66,7 @@ impl Claim {
         TreeVec::concat_cols(log_sizes)
     }
 
-    pub fn accumulate_relation_uses(&self, relation_counts: &mut HashMap<&'static str, u32>) {
+    pub fn accumulate_relation_uses(&self, relation_uses: &mut RelationUsesDict) {
         let Self {
             poseidon_3_partial_rounds_chain,
             poseidon_full_round_chain,
@@ -80,22 +79,22 @@ impl Claim {
         // - poseidon_round_keys
 
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             poseidon_3_partial_rounds_chain::RELATION_USES_PER_ROW,
             poseidon_3_partial_rounds_chain.log_size,
         );
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             poseidon_full_round_chain::RELATION_USES_PER_ROW,
             poseidon_full_round_chain.log_size,
         );
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             cube_252::RELATION_USES_PER_ROW,
             cube_252.log_size,
         );
         accumulate_relation_uses(
-            relation_counts,
+            relation_uses,
             range_check_felt_252_width_27::RELATION_USES_PER_ROW,
             range_check_felt_252_width_27.log_size,
         );

diff --git a/stwo_cairo_prover/crates/cairo-air/src/verifier.rs b/stwo_cairo_prover/crates/cairo-air/src/verifier.rs
@@ -1,5 +1,6 @@
 use num_traits::{One, Zero};
 use paste::paste;
+use serde_json::to_string_pretty;
 use stwo_cairo_adapter::builtins::{
     ADD_MOD_MEMORY_CELLS, BITWISE_MEMORY_CELLS, MUL_MOD_MEMORY_CELLS, PEDERSEN_MEMORY_CELLS,
     POSEIDON_MEMORY_CELLS, RANGE_CHECK_MEMORY_CELLS,
@@ -63,17 +64,34 @@ fn verify_claim(claim: &CairoClaim) {
     assert!(initial_ap <= final_ap);
 
     // Assert that each relation has strictly less than P uses.
-    let mut relation_uses = HashMap::<&'static str, u32>::new();
+    let mut relation_uses = HashMap::<&'static str, u64>::new();
     claim.accumulate_relation_uses(&mut relation_uses);
-    for (name, uses) in relation_uses {
-        assert!(uses < PRIME, "Relation {} has {} uses.", name, uses);
+    check_relation_uses(&relation_uses);
+}
+
+fn check_relation_uses(relation_uses: &HashMap<&'static str, u64>) {
+    let all_relation_uses_pretty = to_string_pretty(&relation_uses).unwrap();
+    log::info!("All relation uses:\n{}", all_relation_uses_pretty);
+
+    let outstanding_relations = relation_uses
+        .iter()
+        .filter(|(_, &uses)| uses >= PRIME.into())
+        .collect::<Vec<_>>();
+
+    if !outstanding_relations.is_empty() {
+        let outstanding_relations_pretty = to_string_pretty(&outstanding_relations).unwrap();
+        panic!(
+            "Found {} outstanding relations:\n{}",
+            outstanding_relations.len(),
+            outstanding_relations_pretty
+        );
     }
 }
 
 #[derive(Clone)]
 pub struct RelationUse {
     pub relation_id: &'static str,
-    pub uses: u32,
+    pub uses: u64,
 }
 
 struct BuiltinClaim {