Skip to content

FRI parameters

the code

def "math cartesian-product" [...iters]: [ nothing -> list ] {
    match ($iters | length) {
        0 => [],
        1 => $iters.0,
        _ => {
            $iters.0 | each { |a|
                math cartesian-product ...($iters | skip 1) | | each { |b|
                    $a | append $b
                }
            }
            | flatten
        },
    }
}

math cartesian-product 1..10 1..10 1..10 1..10 [16, 32] | each { |it|
    let progress = $"it: ($it | to nuon)" | fill --width (term size).columns --character " " --alignment left
    print --no-newline $"($progress)\r"

    let res = cargo run --quiet --example fri --features fri -- ...[
        --seed                      1234
        --hash                      blake3
        --finite-field              fp128
        --data-size                 1025
        -k                          $it.0
        --blowup-factor             $it.1
        --remainder-degree-plus-one $it.2
        --folding-factor            $it.3
        --nb-queries                $it.4
    ] | complete

    let params = $"k=($it.0),bf=($it.1),rdpo=($it.2),ff=($it.3),q=($it.4)"
    let res = if $res.exit_code != 0 {
        let panic = $res.stderr | lines | parse "thread '{thread}' panicked at {file}:{line}:{column}:" | into record
        if $panic != {} {
            $"panic:($res.stderr | lines | get 1):($panic.thread):($panic.file):($panic.line):($panic.column)"
        } else {
            $"err:($res.stderr | lines | str join '|')"
        }
    } else {
        "ok"
    }

    $"($params):($res)"
} out> out.txt

the file

out.txt

the good parameters (90)

let good = open out.txt
    | lines
    | find ok
    | parse --regex '(?<params>.*):ok'
    | update params { split row "," | parse "{k}={v}" | transpose --header-row | into record }
    | flatten params
    | into int line column

the bad parameters (19910)

let bad = open out.txt
    | lines
    | find panic
    | parse --regex '(?<params>.*):panic:(?<msg>.*):(?<thread>.*):(?<file>.*):(?<line>\d+):(?<column>\d+)'
    | update params { split row "," | parse "{k}={v}" | into int v | transpose --header-row | into record }
    | flatten params
    | into int line column

Script to generate the following table

def issue-fn [msg: string]: [ table<file: string, line: int, column: int> -> table<source: string, count: int> ] {
    $in
        | where msg =~ $msg
        | insert __uniq_by_key { $"($in.file):($in.line):($in.column)" }
        | uniq-by __uniq_by_key --count
        | flatten value
        | reject __uniq_by_key
        | insert external { $in.file | str starts-with ($env.CARGO_HOME | path join registry src) }
        | each { |it|
            let source = if $it.external {
                $it.file
                    | str replace ($env.CARGO_HOME | path join registry src) ''
                    | path split
                    | skip 2
                    | path join
                    | parse "{crate}-{version}/{path}"
                    | into record
                    | $"[`($in.crate)@($in.version):($in.path):($it.line):($it.column)`]\(https://gitlab.isae-supaero.fr/dragoon/fri/-/blob/($in.version)/($in.path)#L($it.line)\)"
            } else {
                let file = $it.file | str replace $"(pwd)/" ''
                $"[`($file):($it.line):($it.column)`]\(https://gitlab.isae-supaero.fr/dragoon/komodo/-/blob/main/($file)#L($it.line)\)"
            }

            { source: $source, count: $it.count }
        }
}
def "math ilog2" []: [ int -> int ] {
    math log 2 | math floor
}

[
    'Domain size must be a power of two'
    'Invalid remainder degree \d+ for polynomial of degree \d+ and folding factor \d+ (would result in degree truncation)'
    'attempt to subtract with overflow'
    'called `Result::unwrap()` on an `Err` value: InvalidFriProof(BadDomainSize(\d+))'
    'index out of bounds: the len is \d+ but the index is \d+'
    'not implemented: Unexpected folding factor \d+'
    'range start index \d+ out of range for slice of length \d+'
]
    | each { |msg|
        $bad
            | issue-fn ($msg | str replace --all '(' '\(' | str replace --all ')' '\)')
            | into record
            | default "" source
            | default "" count
            | merge { msg: $msg }
    }
    | select count msg source
    | sort-by --reverse count
    | tee { print ($in.count | math sum) }
    | insert _ { |row|
        let test = $bad | where msg =~ $row.msg | match $row.msg {
            'Domain size must be a power of two'                                                                                   => { each { $in.k * $in.bf } | where ($it | math log 2) == ($it | math ilog2) | length },
            'not implemented: Unexpected folding factor \d+'                                                                       => { get ff | where ($it | math log 2) == ($it | math ilog2) and $it > 1 | length },
            'attempt to subtract with overflow'                                                                                    => { where ($it.k | math ilog2) >= ($it.rdpo | math ilog2) | length },
            'index out of bounds: the len is \d+ but the index is \d+'                                                             => { where ($it.k | math ilog2) != ($it.rdpo | math ilog2) | length },
            'Invalid remainder degree \d+ for polynomial of degree \d+ and folding factor \d+ (would result in degree truncation)' => { where (($it.k | math ilog2) - ($it.rdpo | math ilog2)) mod ($it.ff | math ilog2) == 0 | length },
            'range start index \d+ out of range for slice of length \d+'                                                           => { where $it.rdpo <= (generate { |d| if $d <= $it.rdpo * $it.bf {{ out: $d }} else {{ next: ($d / $it.ff) }} } ($it.k * $it.bf) | get 0) | length },
            'called `Result::unwrap()` on an `Err` value: InvalidFriProof(BadDomainSize(\d+))'                                     => { where ($it.k * $it.bf) <= $it.k | length },
            _ => null,
        }

        if $test == null { ":grey_question:" } else if $test == 0 { ":white_check_mark:" } else { ":x:" }
    }
    | to md --pretty
    | str replace --all '[`examples/fri.rs:195:29`](https://gitlab.isae-supaero.fr/dragoon/komodo/-/blob/main/examples/fri.rs#L195)' '[`dragoonfri@0.1.0:src/lib.rs:399`](https://gitlab.isae-supaero.fr/dragoon/fri/-/blob/0.1.0/src/lib.rs#L399)'
count msg source _
14000 not implemented: Unexpected folding factor \d+ dragoonfri@0.1.0:src/lib.rs:399 ✅
5040 Domain size must be a power of two dragoonfri@0.1.0:src/utils.rs:207:5 ✅
456 attempt to subtract with overflow dragoonfri@0.1.0:src/commit.rs:72:13 ✅
204 index out of bounds: the len is \d+ but the index is \d+ dragoonfri@0.1.0:src/lib.rs:178:27 ✅
144 Invalid remainder degree \d+ for polynomial of degree \d+ and folding factor \d+ (would result in degree truncation) dragoonfri@0.1.0:src/commit.rs:71:9 ✅
48 range start index \d+ out of range for slice of length \d+ dragoonfri@0.1.0:src/utils.rs:233:20 ✅
18 called Result::unwrap() on an Err value: InvalidFriProof(BadDomainSize(\d+)) src/fri.rs:127:10 ✅
Edited by STEVAN Antoine