Cannot STONE prove a program traced with `cairo1-run` due to missing `add_mod` segment #1889

tdelabro · 2024-12-06T20:44:27Z

Here is my program

lib.cairo

use core::ecdsa::check_ecdsa_signature;

#[derive(Drop, Debug, Serde)]
pub struct Inputs {
    signature: Sig,
}

#[derive(Drop, Debug, Serde)]
pub struct Sig {
    r: felt252,
    s: felt252,
}

// Only the private key linked to this public key can sign it
const EXPECTED_SIGNER_PUBKEY: felt252 = 0x548043afcf075c179133917ab6bcf8bca70ae547edadf3e14d7f32f35af0e5;
const EXPECTED_MESSAGE_HASH: felt252 =  0x1f73945d67e3020b5817cd7ebd96440384e2b90cd65544cac05cbc2d6a0652f;

fn main(
    raw_inputs: Array<felt252>,
) -> Array<felt252> {
    let inputs: Inputs  = {
    let mut inputs_ref = raw_inputs.span();
     Serde::deserialize(ref inputs_ref).expect('bad program arguments')
    };

    if !verify_signature(inputs.signature.r, inputs.signature.s) {
        panic!("bad signature");
    };

    return array![];
}

fn verify_signature(r: felt252, s: felt252) -> bool {
    check_ecdsa_signature(EXPECTED_MESSAGE_HASH, EXPECTED_SIGNER_PUBKEY, r, s)
}

Here is Scarb.toml:

[package]
name = "spending_conditions"
version = "0.1.0"
edition = "2024_07"

[dependencies]

[dev-dependencies]
snforge_std = { git = "https://github.com/foundry-rs/starknet-foundry", tag = "v0.33.0" }
assert_macros = "2.8.5"

[scripts]
test = "snforge test"

[cairo]
enable-gas = false
sierra-replace-ids = true

Here is my script to run compile, trace, prove:

#!/bin/bash

scarb --profile release build

readonly LAYOUT=all_cairo
readonly PROGRAM_NAME=spending_conditions
readonly CFG_AND_PARAMS_DIR=config_and_params

cairo1-run target/release/$PROGRAM_NAME.sierra.json \
  --args "[650157136941007917207724121471813482783483983289688285320161307177215463403 1655569645808460179723299787189716707852181277595105475126938070374837146371]"  \
  --layout=$LAYOUT

readonly TRACE_OUTPUT_DIR=outputs/$PROGRAM_NAME/trace

mkdir -p $TRACE_OUTPUT_DIR

cairo1-run target/release/$PROGRAM_NAME.sierra.json \
  --args "[650157136941007917207724121471813482783483983289688285320161307177215463403 1655569645808460179723299787189716707852181277595105475126938070374837146371]" \
  --layout=$LAYOUT \
  --air_public_input=$TRACE_OUTPUT_DIR/public-input.json \
  --air_private_input=$TRACE_OUTPUT_DIR/private-input.json \
  --trace_file=$TRACE_OUTPUT_DIR/trace.bin \
  --memory_file=$TRACE_OUTPUT_DIR/memory.bin \
  --proof_mode 

readonly PROOF_OUTPUT_DIR=outputs/$PROGRAM_NAME/proof

mkdir -p $PROOF_OUTPUT_DIR

cpu_air_prover \
  --out_file=$PROOF_OUTPUT_DIR/proof.json \
  --private_input_file=$TRACE_OUTPUT_DIR/private-input.json \
  --public_input_file=$TRACE_OUTPUT_DIR/public-input.json \
  --prover_config_file=$CFG_AND_PARAMS_DIR/cpu_air_prover_config.json \
  --parameter_file=$CFG_AND_PARAMS_DIR/cpu_air_params.json

The cpu_air_prover run fails with the following error:

libc++abi: terminating with uncaught exception of type starkware::StarkwareException: src/starkware/air/cpu/board/memory_segment.h:50: add_mod segment is missing from mem_segment_addresses.
Stack trace (most recent call last):
#9    Object "cpu_air_prover", at 0x104c795d3, in main + 535
#8    Object "cpu_air_prover", at 0x104c8684b, in starkware::ProverMainHelper(starkware::Statement*, starkware::ProverVersion const&) + 171
#7    Object "cpu_air_prover", at 0x104c93137, in starkware::ProverMainHelperImpl(starkware::Statement*, starkware::JsonValue const&, starkware::JsonValue const&, starkware::JsonValue const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, bool, starkware::ProverVersion const&) + 95
#6    Object "cpu_air_prover", at 0x104e4af83, in starkware::cpu::CpuAirStatement::GetAir() + 655
#5    Object "cpu_air_prover", at 0x104e692cb, in std::__1::__unique_if<starkware::cpu::CpuAir<starkware::PrimeFieldElement<252, 0>, 9> >::__unique_single std::__1::make_unique[abi:ue170006]<starkware::cpu::CpuAir<starkware::PrimeFieldElement<252, 0>, 9>, unsigned long long const&, std::__1::vector<starkware::cpu::MemoryAccessUnitData<starkware::PrimeFieldElement<252, 0> >, std::__1::allocator<starkware::cpu::MemoryAccessUnitData<starkware::PrimeFieldElement<252, 0> > > > const&, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, unsigned long long, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, unsigned long long> > > const&, unsigned long long const&, unsigned long long const&, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, starkware::cpu::MemorySegment, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, starkware::cpu::MemorySegment> > > const&>(unsigned long long const&, std::__1::vector<starkware::cpu::MemoryAccessUnitData<starkware::PrimeFieldElement<252, 0> >, std::__1::allocator<starkware::cpu::MemoryAccessUnitData<starkware::PrimeFieldElement<252, 0> > > > const&, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, unsigned long long, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, unsigned long long> > > const&, unsigned long long const&, unsigned long long const&, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, starkware::cpu::MemorySegment, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, starkware::cpu::MemorySegment> > > const&) + 203
#4    Object "cpu_air_prover", at 0x104e6949b, in starkware::cpu::CpuAir<starkware::PrimeFieldElement<252, 0>, 9>::CpuAir(unsigned long long, std::__1::vector<starkware::cpu::MemoryAccessUnitData<starkware::PrimeFieldElement<252, 0> >, std::__1::allocator<starkware::cpu::MemoryAccessUnitData<starkware::PrimeFieldElement<252, 0> > > >, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, unsigned long long, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, unsigned long long> > > const&, unsigned long long, unsigned long long, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, starkware::cpu::MemorySegment, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, starkware::cpu::MemorySegment> > > const&) + 359
#3    Object "cpu_air_prover", at 0x105955c87, in starkware::cpu::CpuAirDefinition<starkware::PrimeFieldElement<252, 0>, 9>::CpuAirDefinition(unsigned long long, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, unsigned long long, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, unsigned long long> > > const&, starkware::PrimeFieldElement<252, 0> const&, starkware::PrimeFieldElement<252, 0> const&, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, starkware::cpu::MemorySegment, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, starkware::cpu::MemorySegment> > > const&, starkware::PedersenHashContext<starkware::PrimeFieldElement<252, 0> > const&) + 2775
#2    Object "cpu_air_prover", at 0x104e5135f, in starkware::cpu::GetSegment(std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, starkware::cpu::MemorySegment, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, starkware::cpu::MemorySegment> > > const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) + 315
#1    Object "cpu_air_prover", at 0x105a7842f, in starkware::ThrowStarkwareException(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, char const*, unsigned long) + 335
#0    Object "cpu_air_prover", at 0x105a78653, in (anonymous namespace)::PrintStackTrace(std::__1::basic_ostream<char, std::__1::char_traits<char> >*) + 55

./scripts/flow.sh: line 35: 83531 Abort trap: 6           cpu_air_prover --out_file=$PROOF_OUTPUT_DIR/proof.json --private_input_file=$TRACE_OUTPUT_DIR/private-input.json --public_input_file=$TRACE_OUTPUT_DIR/public-input.json --prover_config_file=$CFG_AND_PARAMS_DIR/cpu_air_prover_config.json --parameter_file=$CFG_AND_PARAMS_DIR/cpu_air_params.json

I think the most explicit part is

libc++abi: terminating with uncaught exception of type starkware::StarkwareException: src/starkware/air/cpu/board/memory_segment.h:50: add_mod segment is missing from mem_segment_addresses.

add_mod segment is missing from the public-input.json file. Two possibilities:

cairo1-run is wrong to not add it to the public inputs, and STONE is right to expect it
cairo1-run is right not to include this segment, and STONE is bugged for expecting it.

I also ran this program with a different layout, including dynamic with this file:

{
    "rc_units": 4,
    "log_diluted_units_per_step": 4,
    "cpu_component_step": 8,
    "memory_units_per_step": 8,
    "uses_pedersen_builtin": true,
    "pedersen_ratio": 256,
    "uses_range_check_builtin": true,
    "range_check_ratio": 8,
    "uses_ecdsa_builtin": true,
    "ecdsa_ratio": 2048,
    "uses_bitwise_builtin": true,
    "bitwise_ratio": 16,
    "uses_ec_op_builtin": true,
    "ec_op_ratio": 1024,
    "uses_keccak_builtin": true,
    "keccak_ratio": 2048,
    "uses_poseidon_builtin": true,
    "poseidon_ratio": 256,
    "uses_range_check96_builtin": true,
    "range_check96_ratio": 8,
    "range_check96_ratio_den": 1,
    "uses_add_mod_builtin": true,
    "add_mod_ratio": 128,
    "add_mod_ratio_den": 1,
    "uses_mul_mod_builtin": true,
    "mul_mod_ratio": 256,
    "mul_mod_ratio_den": 1
}

And it still failed with the same error.

The text was updated successfully, but these errors were encountered:

FrancoGiachetta · 2024-12-06T20:58:39Z

check if this helps #1888 (comment)

tdelabro · 2024-12-06T22:10:10Z

It's better, but now I get this error when running cpu_air_prover

libc++abi: terminating with uncaught exception of type starkware::StarkwareException: src/starkware/stark/stark.cc:187: Fri parameters do not match stark degree bound. Expected FRI degree from FriParameters: 8192. STARK: 1048576

tdelabro · 2024-12-06T22:13:40Z

@FrancoGiachetta I'm using this cpu_air_params.json

{
    "field": "PrimeField0",
    "stark": {
        "fri": {
            "fri_step_list": [
                0,
                4,
                3
            ],
            "last_layer_degree_bound": 64,
            "n_queries": 18,
            "proof_of_work_bits": 24
        },
        "log_n_cosets": 4
    },
    "use_extension_field": false
}

Can you provide a replacement? And maybe explain me why this one don't work

tdelabro · 2024-12-06T22:19:56Z

@LandauRaz maybe you will know this?

LandauRaz · 2024-12-06T23:10:39Z

I do :) The Stone CLI should do that for you, but even without it there's this script for that

tdelabro · 2024-12-07T10:22:48Z

@LandauRaz your third link is broken, but I was able to find an equivalent program there

I'm now using

{
    "field": "PrimeField0",
    "stark": {
        "fri": {
            "fri_step_list": [
                4,
                4,
                4,
                3
            ],
            "last_layer_degree_bound": 32,
            "n_queries": 18,
            "proof_of_work_bits": 30
        },
        "log_n_cosets": 4
    },
    "use_extension_field": false
}

And the error is now the following:

libc++abi: terminating with uncaught exception of type starkware::StarkwareException: src/starkware/air/components/trace_generation_context.cc:29: Virtual column 'add_mod/p0/addr' not found
  --out_file=$PROOF_OUTPUT_DIR/proof.json \
  --private_input_file=$TRACE_OUTPUT_DIR/private-input.json \
  --public_input_file=$TRACE_OUTPUT_DIR/public-input.json \
  --prover_config_file=$CFG_AND_PARAMS_DIR/cpu_air_prover_config.json \
  --parameter_file=$CFG_AND_PARAMS_DIR/cpu_air_params.json

libc++abi: terminating with uncaught exception of type starkware::StarkwareException: src/starkware/air/components/trace_generation_context.cc:29: Virtual column 'add_mod/p0/addr' not found
Stack trace (most recent call last):
#12   Object "cpu_air_prover", at 0x102cf15d3, in main + 535
#11   Object "cpu_air_prover", at 0x102cfe84b, in starkware::ProverMainHelper(starkware::Statement*, starkware::ProverVersion const&) + 171
#10   Object "cpu_air_prover", at 0x102d0e143, in starkware::ProverMainHelperImpl(starkware::Statement*, starkware::JsonValue const&, starkware::JsonValue const&, starkware::JsonValue const&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::alloc
#9    Object "cpu_air_prover", at 0x102d2d00f, in starkware::StarkProver::ProveStark(std::__1::unique_ptr<starkware::TraceContext, std::__1::default_delete<starkware::TraceContext> >) + 119
#8    Object "cpu_air_prover", at 0x102f242d7, in starkware::cpu::CpuAirTraceContext<starkware::PrimeFieldElement<252, 0>, 9>::GetTrace() + 79
#7    Object "cpu_air_prover", at 0x102f25b83, in starkware::cpu::CpuAir<starkware::PrimeFieldElement<252, 0>, 9>::GetTrace(gsl::span<starkware::cpu::TraceEntry<starkware::PrimeFieldElement<252, 0> > const>, starkware::MaybeOwnedPtr<starkware::cpu::CpuMemory<starkw
#6    Object "cpu_air_prover", at 0x102f2c93f, in starkware::cpu::AddModBuiltinProverContext<starkware::PrimeFieldElement<252, 0>, 4ul>::AddModBuiltinProverContext(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, starkwa
#5    Object "cpu_air_prover", at 0x102f2ce4f, in starkware::cpu::ModBuiltinProverContext<starkware::PrimeFieldElement<252, 0>, 4ul>::ModBuiltinProverContext(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, starkware::Tr
#4    Object "cpu_air_prover", at 0x102f2dc57, in starkware::cpu::ModBuiltinProverContext<starkware::PrimeFieldElement<252, 0>, 4ul>::InitValue(starkware::MemoryCell<starkware::PrimeFieldElement<252, 0> >*, std::__1::basic_string<char, std::__1::char_traits<char>,
#3    Object "cpu_air_prover", at 0x102eefcf3, in starkware::MemoryCellView<starkware::PrimeFieldElement<252, 0> >::MemoryCellView(starkware::MemoryCell<starkware::PrimeFieldElement<252, 0> >*, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, starkware::TraceGenerationContext const&) + 207
#2    Object "cpu_air_prover", at 0x103aefe5f, in starkware::TraceGenerationContext::GetVirtualColumn(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) const + 355
#1    Object "cpu_air_prover", at 0x103af042f, in starkware::ThrowStarkwareException(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&, char const*, unsigned long) + 335
#0    Object "cpu_air_prover", at 0x103af0653, in (anonymous namespace)::PrintStackTrace(std::__1::basic_ostream<char, std::__1::char_traits<char> >*) + 55

[1]    91954 abort      cpu_air_prover --out_file=$PROOF_OUTPUT_DIR/proof.json

 src/starkware/air/components/trace_generation_context.cc:29: Virtual column 'add_mod/p0/addr' not found

Same with dynamic layout btw

tdelabro · 2024-12-07T10:36:08Z

Btw, I tried running zk-security stone-cli rather than cairo1-run + cpu_air_prover

cairo1-run executed successfully.
Running prover...
Error: Failed to run stone prover: failed to run stone prover with version: V6, status: signal: 6 (SIGABRT), stderr: libc++abi: terminating with uncaught exception of type starkware::StarkwareException: src/starkware/air/cpu/board/memory_segment.h:50: add_mod segment is missing from mem_segment_addresses.

This even after modifying their Cargo.toml to use the cairo-vm with mod_builtin feature

cairo-vm = { git = "https://github.com/zksecurity/cairo-vm", features = ["extensive_hints", "mod_builtin"] }

LandauRaz · 2024-12-10T07:17:38Z

Fixed the third link, will TAL and update ASAP.

mellowcroc · 2024-12-11T14:43:13Z

As I mentioned stone-cli repo, this is actually a known issue in the stone-prover (starkware-libs/stone-prover#38), so stone-cli doesn't support mod_add/mod_mul builtins as of now. I recommend removing the mod_add/mod_mul uses in your code and running again.

tdelabro · 2024-12-11T15:20:00Z

This is my program
Do you know if check_ecdsa_signature uses mod_add internally?
If not what can be causing the use of this builtin?

use core::ecdsa::check_ecdsa_signature;

#[derive(Drop, Debug, Serde)]
pub struct Inputs {
    signature: Sig,
}

#[derive(Drop, Debug, Serde)]
pub struct Sig {
    r: felt252,
    s: felt252,
}

// Only the private key linked to this public key can sign it
const EXPECTED_SIGNER_PUBKEY: felt252 = 0x548043afcf075c179133917ab6bcf8bca70ae547edadf3e14d7f32f35af0e5;
const EXPECTED_MESSAGE_HASH: felt252 =  0x1f73945d67e3020b5817cd7ebd96440384e2b90cd65544cac05cbc2d6a0652f;

fn main(
    raw_inputs: Array<felt252>,
) -> Array<felt252> {
    let inputs: Inputs  = {
    let mut inputs_ref = raw_inputs.span();
     Serde::deserialize(ref inputs_ref).expect('bad program arguments')
    };

    if !verify_signature(inputs.signature.r, inputs.signature.s) {
        panic!("bad signature");
    };

    return array![];
}

fn verify_signature(r: felt252, s: felt252) -> bool {
    check_ecdsa_signature(EXPECTED_MESSAGE_HASH, EXPECTED_SIGNER_PUBKEY, r, s)
}

mellowcroc · 2024-12-12T15:16:26Z

Looks like it does https://github.com/starkware-libs/cairo/blob/55d2e0dd81201b458bb93f85938467f4475a3729/corelib/src/ecdsa.cairo#L102

tdelabro added the bug Something isn't working label Dec 6, 2024

tdelabro mentioned this issue Dec 7, 2024

Failed to prove my program with stone-cli zksecurity/stone-cli#27

Closed

gabrielbosio closed this as not planned Won't fix, can't repro, duplicate, stale Jan 6, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Cannot STONE prove a program traced with `cairo1-run` due to missing `add_mod` segment #1889

Cannot STONE prove a program traced with `cairo1-run` due to missing `add_mod` segment #1889

tdelabro commented Dec 6, 2024

FrancoGiachetta commented Dec 6, 2024

tdelabro commented Dec 6, 2024 •

edited

Loading

tdelabro commented Dec 6, 2024

tdelabro commented Dec 6, 2024

LandauRaz commented Dec 6, 2024 •

edited

Loading

tdelabro commented Dec 7, 2024 •

edited

Loading

tdelabro commented Dec 7, 2024 •

edited

Loading

LandauRaz commented Dec 10, 2024

mellowcroc commented Dec 11, 2024

tdelabro commented Dec 11, 2024

mellowcroc commented Dec 12, 2024

Cannot STONE prove a program traced with cairo1-run due to missing add_mod segment #1889

Cannot STONE prove a program traced with cairo1-run due to missing add_mod segment #1889

Comments

tdelabro commented Dec 6, 2024

FrancoGiachetta commented Dec 6, 2024

tdelabro commented Dec 6, 2024 • edited Loading

tdelabro commented Dec 6, 2024

tdelabro commented Dec 6, 2024

LandauRaz commented Dec 6, 2024 • edited Loading

tdelabro commented Dec 7, 2024 • edited Loading

tdelabro commented Dec 7, 2024 • edited Loading

LandauRaz commented Dec 10, 2024

mellowcroc commented Dec 11, 2024

tdelabro commented Dec 11, 2024

mellowcroc commented Dec 12, 2024

Cannot STONE prove a program traced with `cairo1-run` due to missing `add_mod` segment #1889

Cannot STONE prove a program traced with `cairo1-run` due to missing `add_mod` segment #1889

tdelabro commented Dec 6, 2024 •

edited

Loading

LandauRaz commented Dec 6, 2024 •

edited

Loading

tdelabro commented Dec 7, 2024 •

edited

Loading

tdelabro commented Dec 7, 2024 •

edited

Loading