许可

根据以下任一许可授权：

• Apache License，版本2.0，(LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT许可 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

由您选择。

贡献

除非您明确说明，否则根据Apache-2.0许可定义，您有意提交以包含在作品中的任何贡献，都应如上所述双许可，不得附加任何额外条款或条件。

lib.rs:

基于Goldilocks域的基于FRI的STARK实现，支持通过plonky2 SNARK后端进行递归证明验证。

该库旨在提供证明、验证和递归验证STARK语句所需的所有必要工具。虽然该库针对单个STARK系统进行了优化，但它也足够灵活，可以支持多STARK系统，即可能共享公共值的独立STARK语句系统。有关如何定义此类系统的更多信息，请参阅下文。

定义STARK语句

STARK系统通过一个StarkConfig进行配置，该配置定义了生成与语句关联的证明时使用的所有参数。通过Stark特质定义了如何在STARK迹上定义约束，该特质接受一个StarkEvaluationFrame，该特质包含连续两行的评估框架和一个公开输入列表。

示例：斐波那契序列

要构建一个从两个用户提供的值 x0 和 x1 开始的修改版斐波那契序列的STARK，可以执行以下操作

// Imports all basic types.
use plonky2::field::extension::{Extendable, FieldExtension};
use plonky2::field::packed::PackedField;
use plonky2::field::polynomial::PolynomialValues;
use plonky2::hash::hash_types::RichField;

// Imports to define the constraints of our STARK.
use starky::constraint_consumer::{ConstraintConsumer, RecursiveConstraintConsumer};
use starky::evaluation_frame::{StarkEvaluationFrame, StarkFrame};
use starky::stark::Stark;

// Imports to define the recursive constraints of our STARK.
use plonky2::iop::ext_target::ExtensionTarget;
use plonky2::plonk::circuit_builder::CircuitBuilder;

pub struct FibonacciStark<F: RichField + Extendable<D>, const D: usize> {
    num_rows: usize,
    _phantom: PhantomData<F>,
}

// Define witness generation.
impl<F: RichField + Extendable<D>, const D: usize> FibonacciStark<F, D> {
    // The first public input is `x0`.
    const PI_INDEX_X0: usize = 0;
    // The second public input is `x1`.
    const PI_INDEX_X1: usize = 1;
    // The third public input is the second element of the last row,
    // which should be equal to the `num_rows`-th Fibonacci number.
    const PI_INDEX_RES: usize = 2;

    /// Generate the trace using `x0, x1, 0` as initial state values.
    fn generate_trace(&self, x0: F, x1: F) -> Vec<PolynomialValues<F>> {
        let mut trace_rows = (0..self.num_rows)
            .scan([x0, x1, F::ZERO], |acc, _| {
                let tmp = *acc;
                acc[0] = tmp[1];
                acc[1] = tmp[0] + tmp[1];
                acc[2] = tmp[2] + F::ONE;
                Some(tmp)
            })
            .collect::<Vec<_>>();

        // Transpose the row-wise trace for the prover.
        trace_rows_to_poly_values(trace_rows)
    }
}

// Define constraints.
const COLUMNS: usize = 3;
const PUBLIC_INPUTS: usize = 3;

impl<F: RichField + Extendable<D>, const D: usize> Stark<F, D> for FibonacciStark<F, D> {
    type EvaluationFrame<FE, P, const D2: usize> = StarkFrame<P, P::Scalar, COLUMNS, PUBLIC_INPUTS>
    where
        FE: FieldExtension<D2, BaseField = F>,
        P: PackedField<Scalar = FE>;

    type EvaluationFrameTarget =
        StarkFrame<ExtensionTarget<D>, ExtensionTarget<D>, COLUMNS, PUBLIC_INPUTS>;

    // Define this STARK's constraints.
    fn eval_packed_generic<FE, P, const D2: usize>(
        &self,
        vars: &Self::EvaluationFrame<FE, P, D2>,
        yield_constr: &mut ConstraintConsumer<P>,
    ) where
        FE: FieldExtension<D2, BaseField = F>,
        P: PackedField<Scalar = FE>,
    {
        let local_values = vars.get_local_values();
        let next_values = vars.get_next_values();
        let public_inputs = vars.get_public_inputs();

        // Check public inputs.
        yield_constr.constraint_first_row(local_values[0] - public_inputs[Self::PI_INDEX_X0]);
        yield_constr.constraint_first_row(local_values[1] - public_inputs[Self::PI_INDEX_X1]);
        yield_constr.constraint_last_row(local_values[1] - public_inputs[Self::PI_INDEX_RES]);

        // Enforce the Fibonacci transition constraints.
        // x0' <- x1
        yield_constr.constraint_transition(next_values[0] - local_values[1]);
        // x1' <- x0 + x1
        yield_constr.constraint_transition(next_values[1] - local_values[0] - local_values[1]);
    }

    // Define the constraints to recursively verify this STARK.
    fn eval_ext_circuit(
        &self,
        builder: &mut CircuitBuilder<F, D>,
        vars: &Self::EvaluationFrameTarget,
        yield_constr: &mut RecursiveConstraintConsumer<F, D>,
    ) {
        let local_values = vars.get_local_values();
        let next_values = vars.get_next_values();
        let public_inputs = vars.get_public_inputs();

        // Check public inputs.
        let pis_constraints = [
            builder.sub_extension(local_values[0], public_inputs[Self::PI_INDEX_X0]),
            builder.sub_extension(local_values[1], public_inputs[Self::PI_INDEX_X1]),
            builder.sub_extension(local_values[1], public_inputs[Self::PI_INDEX_RES]),
        ];

        yield_constr.constraint_first_row(builder, pis_constraints[0]);
        yield_constr.constraint_first_row(builder, pis_constraints[1]);
        yield_constr.constraint_last_row(builder, pis_constraints[2]);

        // Enforce the Fibonacci transition constraints.
        // x0' <- x1
        let first_col_constraint = builder.sub_extension(next_values[0], local_values[1]);
        yield_constr.constraint_transition(builder, first_col_constraint);
        // x1' <- x0 + x1
        let second_col_constraint = {
            let tmp = builder.sub_extension(next_values[1], local_values[0]);
            builder.sub_extension(tmp, local_values[1])
        };
        yield_constr.constraint_transition(builder, second_col_constraint);
    }

    fn constraint_degree(&self) -> usize {
        2
    }
}

然后可以实例化一个新的 FibonacciStark 实例，生成相关的STARK跟踪，并为其生成证明。

#
#
const D: usize = 2;
const CONFIG: StarkConfig = StarkConfig::standard_fast_config();
type C = PoseidonGoldilocksConfig;
type F = <C as GenericConfig<D>>::F;
type S = FibonacciStark<F, D>;

fn main() {
    let num_rows = 1 << 10;
    let x0 = F::from_canonical_u32(2);
    let x1 = F::from_canonical_u32(7);

    let public_inputs = [x0, x1, fibonacci(num_rows - 1, x0, x1)];
    let stark = FibonacciStark::<F, D>::new(num_rows);
    let trace = stark.generate_trace(public_inputs[0], public_inputs[1]);

    let proof = prove::<F, C, S, D>(
        stark,
        &CONFIG,
        trace,
        &public_inputs,
        &mut TimingTree::default(),
    ).expect("We should have a valid proof!");

    verify_stark_proof(stark, proof, &CONFIG)
        .expect("We should be able to verify this proof!")
}