Winterfell

此包包含 Winterfell STARK 推理器和验证器。它简单导出在 推理器 和 验证器 包中定义的组件。

许可证

此项目遵循 MIT 许可证。

lib.rs:

此包包含 Winterfell STARK 推理器和验证器。

STARK 是一种新型的计算证明方案，用于创建可高效验证的计算正确执行证明。该方案由以色列理工学院 Eli Ben-Sasson、Michael Riabzev 等人开发。STARK 不需要初始可信设置，并且依赖于非常少的加密假设。有关更多信息，请参阅 参考文献。

证明生成

要生成一个证明来证明计算已正确执行，您需要执行以下操作：

1. 为您的工作定义一个 代数中间表示 (AIR)。这可以通过实现 [Air] 特性来完成。
2. 为您的工作定义一个执行跟踪。这可以通过实现 [Trace] 特性来完成。或者，您可以使用已经实现 [Trace] 特性的 [TraceTable] 结构体，在通用实现适用于您的用例时。
3. 执行您的计算并记录其执行跟踪。
4. 通过实现 [Prover] 特性来定义您的证明器。然后，执行 [Prover::prove()] 函数，将上一步生成的跟踪作为参数传递给它。该函数将返回一个 [Proof] 实例。

此 Proof 可以序列化并发送给 STARK 验证器进行验证。证明的大小取决于特定计算的具体情况，但对于大多数计算，它应在 15 KB（用于非常小的计算）到 300 KB（用于非常大的计算）之间。

生成证明的时间也高度依赖于特定计算的具体情况，同时也取决于用于生成证明的机器的能力（即CPU核心数和内存带宽）。

当使用具有concurrent功能的crate编译时，证明生成将在多个线程中执行（通常，线程数与机器上的逻辑核心数相同）。线程数可以通过RAYON_NUM_THREADS环境变量进行配置。

证明验证

要验证如前几节所述生成的[证明]，你需要执行以下操作

1. 为你的计算定义一个代数中间表示（AIR）。这个AIR必须与证明生成过程中使用的相同。
2. 执行[verify()]函数，并提供你的计算AIR以及[证明]和相关公共输入作为参数。

证明验证非常快，几乎与被验证计算的复杂性无关。在绝大多数情况下，在现代中端笔记本电脑CPU（使用单个核心）上，证明可以在3 - 5毫秒内完成验证。

然而，有一个例外：如果一个计算需要大量的sequence断言（有关更多信息，请参阅[断言]），验证时间将随断言值的数量线性增长。但是，要使影响明显，断言值的数量需要达到数万。即使对于数十万个不同值，验证时间也不应超过50毫秒。

示例

要理解STARK证明生成和验证过程，最好的方法是从头到尾完成一个简单的示例。首先，我们需要选择一个用于生成和验证STARK证明的计算。为了简化问题，我们将使用以下

use winterfell::math::{fields::f128::BaseElement, FieldElement};

fn do_work(start: BaseElement, n: usize) -> BaseElement {
   let mut result = start;
   for _ in 1..n {
       result = result.exp(3) + BaseElement::new(42);
   }
   result
}

这个计算从一个有限域中的元素开始，然后经过指定的步骤，将元素立方，并加上值42。

假设，我们运行这个计算一百万步，并获得一些结果。使用STARKs，我们可以证明我们正确地完成了工作，而不需要任何验证方重新执行计算。下面是如何操作的

首先，我们需要为我们的计算定义一个执行跟踪。这个跟踪应该捕获计算在执行过程中的每个步骤的状态。在我们的例子中，跟踪只是一个执行循环后中间值的单列。例如，如果我们从值3开始，并运行计算1,048,576步（等于2²⁰），则执行跟踪将如下所示

为了记录跟踪，我们将使用[TraceTable]结构。下面的函数只是do_work()函数的一个修改版本，该函数将计算在[TraceTable]结构中的每个中间状态记录下来

use winterfell::{
    math::{fields::f128::BaseElement, FieldElement},
    TraceTable,
};

pub fn build_do_work_trace(start: BaseElement, n: usize) -> TraceTable<BaseElement> {
    // Instantiate the trace with a given width and length; this will allocate all
    // required memory for the trace
    let trace_width = 1;
    let mut trace = TraceTable::new(trace_width, n);

    // Fill the trace with data; the first closure initializes the first state of the
    // computation; the second closure computes the next state of the computation based
    // on its current state.
    trace.fill(
        |state| {
            state[0] = start;
        },
        |_, state| {
            state[0] = state[0].exp(3u32.into()) + BaseElement::new(42);
        },
    );

    trace
}

接下来，我们需要为我们的计算定义代数中间表示（AIR）。这个过程通常被称为算术化。我们通过实现[Air]特质来完成。从高层次来看，下面的代码做了三件事

1. 定义了我们计算应具有的公共输入的外观。这些输入被称为“公共的”，因为它们必须为证明者和验证者所知晓。
2. 定义了一个具有单个转换约束的转换函数。这个约束必须对所有有效状态转换评估为零，对于任何无效状态转换评估为非零。这个约束的次数为3（有关约束次数的更多信息，请参阅[Air]特质文档中的“约束次数”部分）。
3. 针对我们的计算执行跟踪定义两个断言。这些断言将一组特定的公共输入与特定的执行跟踪相关联（关于断言的更多信息，请参阅[Air]特质文档的“Trace断言”部分）。

以下是实际代码

use winterfell::{
    math::{fields::f128::BaseElement, FieldElement, ToElements},
    Air, AirContext, Assertion, GkrVerifier, EvaluationFrame,
    ProofOptions, TraceInfo, TransitionConstraintDegree,
    crypto::{hashers::Blake3_256, DefaultRandomCoin},
};

// Public inputs for our computation will consist of the starting value and the end result.
pub struct PublicInputs {
    start: BaseElement,
    result: BaseElement,
}

// We need to describe how public inputs can be converted to field elements.
impl ToElements<BaseElement> for PublicInputs {
    fn to_elements(&self) -> Vec<BaseElement> {
        vec![self.start, self.result]
    }
}

// For a specific instance of our computation, we'll keep track of the public inputs and
// the computation's context which we'll build in the constructor. The context is used
// internally by the Winterfell prover/verifier when interpreting this AIR.
pub struct WorkAir {
    context: AirContext<BaseElement>,
    start: BaseElement,
    result: BaseElement,
}

impl Air for WorkAir {
    // We'll specify which finite field to use for our computation, and also how
    // the public inputs must look like.
    type BaseField = BaseElement;
    type PublicInputs = PublicInputs;
    type GkrProof = ();
    type GkrVerifier = ();

    // Here, we'll construct a new instance of our computation which is defined by 3
    // parameters: starting value, number of steps, and the end result. Another way to
    // think about it is that an instance of our computation is a specific invocation of
    // the do_work() function.
    fn new(trace_info: TraceInfo, pub_inputs: PublicInputs, options: ProofOptions) -> Self {
        // our execution trace should have only one column.
        assert_eq!(1, trace_info.width());

        // Our computation requires a single transition constraint. The constraint itself
        // is defined in the evaluate_transition() method below, but here we need to specify
        // the expected degree of the constraint. If the expected and actual degrees of the
        // constraints don't match, an error will be thrown in the debug mode, but in release
        // mode, an invalid proof will be generated which will not be accepted by any verifier.
        let degrees = vec![TransitionConstraintDegree::new(3)];

        // We also need to specify the exact number of assertions we will place against the
        // execution trace. This number must be the same as the number of items in a vector
        // returned from the get_assertions() method below.
        let num_assertions = 2;

        WorkAir {
            context: AirContext::new(trace_info, degrees, num_assertions, options),
            start: pub_inputs.start,
            result: pub_inputs.result,
        }
    }

    // In this method we'll define our transition constraints; a computation is considered to
    // be valid, if for all valid state transitions, transition constraints evaluate to all
    // zeros, and for any invalid transition, at least one constraint evaluates to a non-zero
    // value. The `frame` parameter will contain current and next states of the computation.
    fn evaluate_transition<E: FieldElement + From<Self::BaseField>>(
        &self,
        frame: &EvaluationFrame<E>,
        _periodic_values: &[E],
        result: &mut [E],
    ) {
        // First, we'll read the current state, and use it to compute the expected next state
        let current_state = &frame.current()[0];
        let next_state = current_state.exp(3u32.into()) + E::from(42u32);

        // Then, we'll subtract the expected next state from the actual next state; this will
        // evaluate to zero if and only if the expected and actual states are the same.
        result[0] = frame.next()[0] - next_state;
    }

    // Here, we'll define a set of assertions about the execution trace which must be
    // satisfied for the computation to be valid. Essentially, this ties computation's
    // execution trace to the public inputs.
    fn get_assertions(&self) -> Vec<Assertion<Self::BaseField>> {
        // for our computation to be valid, value in column 0 at step 0 must be equal to the
        // starting value, and at the last step it must be equal to the result.
        let last_step = self.trace_length() - 1;
        vec![
            Assertion::single(0, 0, self.start),
            Assertion::single(0, last_step, self.result),
        ]
    }

    // This is just boilerplate which is used by the Winterfell prover/verifier to retrieve
    // the context of the computation.
    fn context(&self) -> &AirContext<Self::BaseField> {
        &self.context
    }
}

接下来，我们需要定义我们的证明器。这可以通过实现[Prover]特质来完成。这个特质很简单，只有几个必需的方法。以下是我们实现的样子：

use winterfell::{
    crypto::{hashers::Blake3_256, DefaultRandomCoin},
    math::{fields::f128::BaseElement, FieldElement, ToElements},
    matrix::ColMatrix,
    DefaultTraceLde, ProofOptions, Prover, StarkDomain, Trace, TracePolyTable, TraceTable,
};

#
#
#
#
#
#
#
#
#
// Our prover needs to hold STARK protocol parameters which are specified via ProofOptions
// struct.
struct WorkProver {
    options: ProofOptions
}

impl WorkProver {
    pub fn new(options: ProofOptions) -> Self {
        Self { options }
    }
}

// When implementing the Prover trait we set the `Air` associated type to the AIR of the
// computation we defined previously, and set the `Trace` associated type to `TraceTable`
// struct as we don't need to define a custom trace for our computation. For other
// associated types, we'll use default implementation provided by Winterfell.
impl Prover for WorkProver {
    type BaseField = BaseElement;
    type Air = WorkAir;
    type Trace = TraceTable<Self::BaseField>;
    type HashFn = Blake3_256<Self::BaseField>;
    type RandomCoin = DefaultRandomCoin<Self::HashFn>;
    type TraceLde<E: FieldElement<BaseField = Self::BaseField>> = DefaultTraceLde<E, Self::HashFn>;
    type ConstraintEvaluator<'a, E: FieldElement<BaseField = Self::BaseField>> =
        DefaultConstraintEvaluator<'a, Self::Air, E>;

    // Our public inputs consist of the first and last value in the execution trace.
    fn get_pub_inputs(&self, trace: &Self::Trace) -> PublicInputs {
        let last_step = trace.length() - 1;
        PublicInputs {
            start: trace.get(0, 0),
            result: trace.get(0, last_step),
        }
    }

    fn options(&self) -> &ProofOptions {
        &self.options
    }

    fn new_trace_lde<E: FieldElement<BaseField = Self::BaseField>>(
        &self,
        trace_info: &TraceInfo,
        main_trace: &ColMatrix<Self::BaseField>,
        domain: &StarkDomain<Self::BaseField>,
    ) -> (Self::TraceLde<E>, TracePolyTable<E>) {
        DefaultTraceLde::new(trace_info, main_trace, domain)
    }

    fn new_evaluator<'a, E: FieldElement<BaseField = Self::BaseField>>(
        &self,
        air: &'a Self::Air,
        aux_rand_elements: Option<AuxRandElements<E>>,
        composition_coefficients: winterfell::ConstraintCompositionCoefficients<E>,
    ) -> Self::ConstraintEvaluator<'a, E> {
        DefaultConstraintEvaluator::new(air, aux_rand_elements, composition_coefficients)
    }
}

现在，我们终于可以生成和验证STARK证明了。

在下面的代码中，我们将执行我们的计算并获取结果以及证明我们的计算被正确执行。然后，我们将使用这个证明（以及公共输入）来验证我们确实执行了计算并得到了声称的结果。

#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
// We'll just hard-code the parameters here for this example. We'll also just run the
// computation just for 1024 steps to save time during testing.
let start = BaseElement::new(3);
let n = 1024;

// Build the execution trace and get the result from the last step.
let trace = build_do_work_trace(start, n);
let result = trace.get(0, n - 1);

// Define proof options; these will be enough for ~96-bit security level.
let options = ProofOptions::new(
    32, // number of queries
    8,  // blowup factor
    0,  // grinding factor
    FieldExtension::None,
    8,  // FRI folding factor
    31, // FRI max remainder polynomial degree
);

// Instantiate the prover and generate the proof.
let prover = WorkProver::new(options);
let proof = prover.prove(trace).unwrap();

// The verifier will accept proofs with parameters which guarantee 95 bits or more of
// conjectured security
let min_opts = winterfell::AcceptableOptions::MinConjecturedSecurity(95);

// Verify the proof. The number of steps and options are encoded in the proof itself,
// so we don't need to pass them explicitly to the verifier.
let pub_inputs = PublicInputs { start, result };
assert!(winterfell::verify::<WorkAir,
                             Blake3_256<BaseElement>,
                             DefaultRandomCoin<Blake3_256<BaseElement>>
                            >(proof, pub_inputs, &min_opts).is_ok());

这就全部了！

参考文献

如果你对了解STARKs内部工作原理感兴趣，以下是一些开始学习的链接。从本库的角度来看，算术化是理解的最重要概念。

• STARKs白皮书： 可扩展、透明和后量子安全的计算完整性
• STARKs与SNARKs： 密码证明的 Cambrian 爆发

Vitalik Buterin的zk-STARKs博客系列

• STARKs，第1部分：多项式证明
• STARKs，第2部分：感谢上帝今天是FRI-day
• STARKs，第3部分：深入探讨

StarkWare的STARK Math博客系列

• STARK Math：旅程开始
• 算术化I
• 算术化II
• 低度测试
• 高效STARKs的框架