Skip to content

Potentially wrong constraints in GlReduce #5

@shuklaayush

Description

@shuklaayush

Shouldn't the Reduce function constrain that both r and d are less than the Order() p instead of just constraining that they're less than 2^64?

// Gl: Goldilocks
// range check d < 1 << N
template GlReduce(N) {
signal input x;
signal output out;
var r = x % Order();
var d = (x - r) \ Order();
out <-- r;
signal tmp0 <-- d;
tmp0 * Order() + out === x;
component c0 = LessNBits(N);
c0.x <== tmp0;
component c1 = LessNBits(64);
c1.x <== out;
}

Eg. If x is p + 1, then both (d, r) = (1, 1) and (0, p + 1) are valid witnesses with the current code

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions