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:

• solana/sdk/program/src/alt_bn128/mod.rs

  Line 306 in 973d05c

  pub fn alt_bn128_addition(input: &[u8]) -> Result<Vec<u8>, AltBn128Error> {

• solana/sdk/program/src/alt_bn128/mod.rs

  Line 326 in 973d05c

  pub fn alt_bn128_multiplication(input: &[u8]) -> Result<Vec<u8>, AltBn128Error> {

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.

[github-actions]

This repository is no longer in use. Please re-open this issue in the agave repo: https://github.com/anza-xyz/agave