如何用gnark实现以公开输入n迭代的斐波那契电路？

原代码的问题 #

• api.ConstantValue(circuit.N) 在Define方法阶段无法获取输入的实际数值：Define是用于构建电路约束结构的阶段，此时所有输入变量（包括N）还未被赋值，无法作为静态循环的次数条件。
• 常规for循环是静态编译的，次数在编译时确定，但N是动态公开输入，需要电路支持任意合法N值的约束验证，静态循环无法满足需求。

正确实现思路 #

要实现动态次数的迭代，需要用循环不变量+条件选择的方式，在电路中维护：

1. 当前斐波那契的两个状态值（a, b）
2. 当前迭代次数计数器（count）
3. 每次迭代判断count是否小于N，若是则更新状态和计数器，否则保持不变
4. 当计数器等于N时，最终的b值就是斐波那契结果

完整实现代码 #

package main

import (
    "github.com/consensys/gnark/frontend"
    "github.com/consensys/gnark/std/math/bits"
)

type Circuit struct {
    A1  frontend.Variable `gnark:",public"` // 斐波那契初始值F(0)
    A2  frontend.Variable `gnark:",public"` // 斐波那契初始值F(1)
    N   frontend.Variable `gnark:",public"` // 迭代次数（求F(N)）
    Res frontend.Variable `gnark:",public"` // 结果F(N)
}

// Define 构建斐波那契电路约束
func (circuit *Circuit) Define(api frontend.API) error {
    // 初始化状态：a=F(0), b=F(1)
    a := circuit.A1
    b := circuit.A2
    count := frontend.Variable(0)

    // 设置最大迭代位数，支持N的最大范围（此处为2^32-1）
    maxBits := 32
    for i := 0; i < maxBits; i++ {
        // 判断当前是否需要继续迭代：count < N
        lessThanN := api.Sub(N, count)
        isLess := bits.IsNonZero(api, lessThanN)

        // 计算迭代后的状态值
        newA := api.ConditionalSelect(isLess, b, a)
        newB := api.ConditionalSelect(isLess, api.Add(a, b), b)
        newCount := api.ConditionalSelect(isLess, api.Add(count, 1), count)

        // 更新状态变量
        a, b, count = newA, newB, newCount
    }

    // 绑定结果约束：最终b即为F(N)
    api.AssertIsEqual(circuit.Res, b)

    return nil
}

代码说明 #

• bits.IsNonZero：通过计算N - count的非零性，判断是否需要继续迭代。
• api.ConditionalSelect：实现条件式状态更新，确保所有可能的N值都对应正确的约束逻辑。
• 固定最大迭代位数：这里设置为32位，支持N最大为2^32-1，可根据实际需求调整位数范围。

内容的提问来源于stack exchange，提问作者kang wang