Optimize GF2 → BN256 Groth16 recursion using lookup tables for GF2ext128 operations

[zhenfeizhang]

Background

We previously avoided implementing GF2 expander → BN256 Groth16 recursion due to the high cost of non-native emulation of GF2ext128 operations.

Proposed Approach

We can potentially optimize this by using lookup tables for GF2ext128 operations:

struct LookupEntry {
    key: (a, b),  // two 128-bit integers, can be cast as either GF2ext128 or BN254::Fr
    value: op(a, b),  // op can be either addition or multiplication, result is also 128 bits
}

With this approach, each GF2 operation becomes a lookup entry in the recursion scheme, effectively transforming the recursion into a large lookup table combined with SHA/Keccak operations.

Potential Extension

We could even implement a two-stage recursion:

GF2 expander → BN256 expander → BN256 Groth16

This way, we would only need to perform lookups + SHA in the first recursion step (both circuits exist), while the second recursion is already implemented.

Next Steps

• Evaluate the size of lookup tables needed for common GF2ext128 operations. This can be done by counting the total number of add and mul in GF2ext128 (LogUp will optimize for duplicated entries; so this count will be the worst case scenario)

Questions to Consider

What is the size overhead of the lookup table for typical circuits?
How does this approach compare to other optimization techniques?
Are there specific circuits where this approach would be particularly beneficial?