Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Non-empty stack overflow table #1537

Open
plafer opened this issue Oct 18, 2024 · 1 comment
Open

Non-empty stack overflow table #1537

plafer opened this issue Oct 18, 2024 · 1 comment
Labels
bug Something isn't working

Comments

@plafer
Copy link
Contributor

plafer commented Oct 18, 2024

The following test fails with error OutputStackOverflow(1), presumably because there were 2 PUSH instructions, and one ADD (which shifts stack left), and so the overflow table contains a 0 entry at the end and is contained non-empty. This is probably a new behavior since #1456.

I'm not sure why this doesn't occur in more tests yet, but it seems like the behavior we want is: if a 0 is pushed onto the stack overflow table, and the table is empty, then don't populate the overflow table (since when we shift right on an empty overflow table, we populate s[15] with 0).

#[test]
fn test() {
    use crate::{prove, Assembler, DefaultHost, Program, ProvingOptions, StackInputs};
    // instantiate the assembler
    let mut assembler = Assembler::default();

    // this is our program, we compile it from assembly code
    let program = assembler.assemble_program("begin push.3 push.5 add end").unwrap();

    // let's execute it and generate a STARK proof
    let (outputs, proof) = prove(
        &program,
        StackInputs::default(),    // we won't provide any inputs
        DefaultHost::default(),    // we'll be using a default host
        ProvingOptions::default(), // we'll be using default options
    )
    .unwrap();

    // the output should be 8
    assert_eq!(8, outputs.first().unwrap().as_int());
}
@plafer plafer added the bug Something isn't working label Oct 18, 2024
@bobbinth
Copy link
Contributor

In most tests, we ensure that stack overflow table is empty at the end of the program by manually dropping extra items.

if a 0 is pushed onto the stack overflow table, and the table is empty, then don't populate the overflow table (since when we shift right on an empty overflow table, we populate s[15] with 0).

This would be very cool - but we'll need to think through how complex the constraints would need to be to support this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants