alt_bn128 use stack instead of heap

[ppoliani]

Problem

I'm currently trying to use alt_bn128 to verify Groth16 ZKP. I'm using this repository which in turns uses the alt_bn128 module from the solana-program crate.

The problem I face when I run my program is:

Error: memory allocation failed, out of memory

Let me share some details about my circuit. It has 246 outputs i.e. public inputs. I've checked the code and I noticed the usage of the following functions:

• https://github.com/solana-labs/solana/blob/973d05c098b24364ad29a5066e78884c5c3a7537/sdk/program/src/alt_bn128/mod.rs#L306
• https://github.com/solana-labs/solana/blob/973d05c098b24364ad29a5066e78884c5c3a7537/sdk/program/src/alt_bn128/mod.rs#L326

These functions return a vector of data on the heap which means they allocate data on the heap not stack. Looking into the non-solana version of the functions I can see the following line

let mut input = input.to_vec();
input.resize(ALT_BN128_MULTIPLICATION_INPUT_LEN, 0);

//  pub const ALT_BN128_MULTIPLICATION_INPUT_LEN: usize = 128;

For circuits like mine which has 246 inputs this will result in allocating 246 times a vector of size 128 which would quickly hit the Solana heap size limits.

Proposed Solution

I wonder if could use the stack instead of creating vectors on the heap. The issue with the heap is that there is no way to free a previously allocated memory. However, with stack (correctly if I'm wrong) we still have a limit but the stack at least can grow and shrink, so as long as a function call stays within the stack limit we should be (in theory ok).

Most of the practical circuits will have public inputs of that size if not bigger. As it stands, it's hard to use the alt_bn128 for any practical circuit.

[samkim-crypto]

Hi @ppoliani, do you have an example program that you are running using the bn128 operations? and also where are you running the program (testnet, devnet, mb?).

It appears to me that the size of the return vector should be fixed and small enough to fit inside either the stack or the heap. My guess is that you are running out of memory because the operation is being invoked as bpf instructions rather than natively as syscalls.