leo

leo copied to clipboard

🐛 Bug Report

related to #608. multiple i128 division operations using input causes an OOM during the setup stage.

while isolating this bug from leo-fuzzer programs i found several examples that would OOM during the build stage instead of setup, although i was incapable of reproducing them a few minutes later. if i find a repeatable example of this bug that OOM's during the build step then ill make sure to report that as well

Code snippet to reproduce

input:

[main]
x: i128 = 2i128;

code:

function main (
    x: i128,
) {
    for i in 0..10 {
        let y = x / x;
    }
}

Stack trace & error message

D:\Work\leo_playground>D:\Work\leo_repos\leo\target\release\leo clean && D:\Work\leo_repos\leo\target\release\leo run
      Done Finished in 182 milliseconds 

     Build Starting...
     Build Compiling main program... ("D:\\Work\\leo_playground\\src/main.leo")
     Build Complete
      Done Finished in 48876 milliseconds 

     Setup Starting...
     Setup Saving proving key ("D:\\Work\\leo_playground\\outputs/leo_playground.lpk")
memory allocation of 4294967296 bytes failed

Your Environment

• leo's latest master commit 6fb1e713ed7e3b16e233d5221fc3dcaa0891cf6a
• rustc version 1.49.0
• Windows 10.0.19042 (Windows 10 Pro) [64-bit]

i found several examples that would OOM during the build stage instead of setup, although i was incapable of reproducing them a few minutes later

Are they reproducible once you remove the outputs folder?

Other than that, I can confirm that this doesn't OOM (full execution) on my PC with the ConstraintSystem cleanups (1 in Leo, 2 in snarkVM) in place (can certainly still be improved, though):

i found several examples that would OOM during the build stage instead of setup, although i was incapable of reproducing them a few minutes later

Are they reproducible once you remove the outputs folder?

unfortunately no. although im looking for OOM's on a machine with 32gb ram so it could be that they still over-consume memory but not to the point of causing an OOM. im going to run it overnight with exponent operations disabled. hopefully ill find some more examples of these non-exponent build stage OOM's that way. in the mean time, this is the code that caused a build-stage OOM that i couldnt reproduce

[main]
JIiy: [[[[i128; 1]; 2]; 2]; 2] = [-68958346217887456069304585350699959121i128; (2, 2, 2, 1)];

function main (
    JIiy: [[[[i128; 1]; 2]; 2]; 2],
) {  
    console.log("{}", JIiy[1u32][1u32][0u32][0u32]);
    let b = JIiy[0u32][1u32][0u32][0] / -2i128 * -2 / JIiy[1u32][1][1u32][0] / -47851246994993642890324197017718595459i128;
    console.log("b: {}", b);  //0
    let x = b / JIiy[1u32][1u32][0u32][0u32];
    console.log("x: {}", x);  //0
}

this code also causes #688 (proving key fails to load)

Wasn't able to reproduce on master. It took almost an hour but no oom was spotted.

Build Starting...
     Build Compiling main program... ("tmp/array/src/main.leo")
     Build Number of constraints - 5559198
     Build Complete
      Done Finished in 325671 milliseconds 
     Setup Starting...
     Setup Saving proving key ("tmp/array/outputs/array.lpk")
     Setup Complete
     Setup Saving verification key ("tmp/array/outputs/array.lvk")
     Setup Complete
      Done Finished in 3027761 milliseconds 
   Proving Starting...
   Proving Saving proof... ("tmp/array/outputs/array.proof")
      Done Finished in 857087 milliseconds 
 Verifying Starting...
 Verifying Proof is valid
      Done Finished in 74 milliseconds 

Wasn't able to reproduce on master. It took almost an hour but no oom was spotted.

Build Starting...
     Build Compiling main program... ("tmp/array/src/main.leo")
     Build Number of constraints - 5559198
     Build Complete
      Done Finished in 325671 milliseconds 
     Setup Starting...
     Setup Saving proving key ("tmp/array/outputs/array.lpk")
     Setup Complete
     Setup Saving verification key ("tmp/array/outputs/array.lvk")
     Setup Complete
      Done Finished in 3027761 milliseconds 
   Proving Starting...
   Proving Saving proof... ("tmp/array/outputs/array.proof")
      Done Finished in 857087 milliseconds 
 Verifying Starting...
 Verifying Proof is valid
      Done Finished in 74 milliseconds 

hmmm good to know. i wonder if more loops would cause an OOM still

@0rphon @gluax @acoglio

If this takes long but doesn't produce OOM, should we consider it a bug?

In general, some program analysis or transformation algorithms may take an impractically long time without running out of memory: they may be stuck in a loop that takes long to converge, and things like that. So this may or may not be a bug, vs. just something that takes long. The example program doesn't look like it has anything really large (like a loop with many iterations), other that u128 division, which is probably somewhat expensive in R1CS, but the loop here has only 10 iterations. So I think it's worth investigating what's happening here, before we can classify this as a bug or just something that takes long; in the second case, perhaps it can be addressed via an estimation and warning approach similar to the one I mentioned in #733.

I've run the original snippet of code on Leo v1.6.2 and the program does not OOM (MacOS M1).