Low degree proof fails for small number of steps

[marinthiercelin]

Hello,

I am playing with airscript and genstark to see how it works and I got the following problem:

I use this dummy airscript program :

define Foo over prime field (21888242871839275222246405745257275088548364400416034343698204186575808495617) {

        public input public_inputs: element[${num_public_inputs}];
        secret input secret_inputs: element[${num_secret_inputs}];

        // define transition function
        transition ${num_public_inputs+num_secret_inputs} registers {
            for each (public_inputs, secret_inputs) {
                init { yield [public_inputs, secret_inputs]; }
                for steps [1..${depth-1}] { yield $r; }
            }
        }

        // define transition constraints
        enforce ${num_public_inputs+num_secret_inputs} constraints {
            for all steps { enforce transition($r) = $n; }
        }
    }

Basically it takes a certain number of public and secret inputs, put them in the registers, and does nothing for a certain number of steps (called depth).

I want to prove the following assertions: At step 0: the registers initiated with public values have the correct value At step depth-1: all the registers still have their initial values.

When I use genstark to generate a proof with depth = 8, I get the following error :

StarkError: Low degree proof failed: Invalid array length

When I tried to debug I found the source of the problem:

In genstark/lib/components/LowDegreeProver.js:

class LowDegreeProver {

    ...

    prove(cEvaluations, domain, maxDegreePlus1) {
        
       ...

        const componentCount = getComponentCount(cEvaluations.length);
        const proof = {
            lcRoot: pTree.root,
            lcProof: lcProof,
            components: new Array(componentCount),
            remainder: []
        };

        ...

    }

With getComponentCount defined as:

function getComponentCount(valueCount) {
    let result = Math.ceil(Math.log2(valueCount) / 2); // round up log(valueCount, 4);
    result -= REMAINDER_SLOTS;
    return Math.min(result, 0);
}

Here in case of depth = 8, cEvaluations.length is 32 which means getComponentCount(cEvaluations.length) returns -1 !

Then, we try to initialize components: new Array(componentCount) with a size of -1, and get the error.

This problem disapears when I set depth >= 32.

Is that the expected behavior ?

Shouldn't it be return Math.max(result, 0); in getComponentCount ?

[bobbinth]

Hey - thanks for noticing!

Yes, this specific fix should work here - though, I should say that for such short execution traces there might be some other issues that have not been accounted for.

In general, in the current implementation, the base layer of FRI is expected to have length 256, and while it seems to work for some values smaller than this, I'll need to think through what exactly happens in such cases. So, it might be better to have steps * extensionFactor quantity be greater than 256.

I'll keep this issue open to circle back once I have a bit more time (ideally, this issue will be fixed once FRI implementation is replaced with DEEP-FRI - but not sure when I'll get to this yet).