“Cryptography”
重心插值
重心插值（Barycentric interpolation ）是拉格朗日插值的变换。有时候需要通过一组多项式点值直接计算另一个不同点处的值，例如，$p(x)$ 是一个度为 2 的多项式，可以在...
FRI PCS
FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) 协议用于证明多项式是低度的。Commit计算 domaindomain...
MMCS (Mixed Matrix Commitment Scheme)
MMCS (Mixed Matrix Commitment Scheme)Merkle Tree 用于对向量（单列数据）承诺，而 MMCS (Mixed Matrix Commitment Sc...
DFT NTT FFT
Radix-2 DITRadix-2 DIT FFT 由 Cooley 和 Tukey 于 1965 年发明，广泛应用于数字信号处理。它是一种分治算法，递归地将问题拆分为更小的子问题。复杂度为 ...
TSS ECDSA 中 Paillier 的替代方案
Paillier 的密文空间 N 大于椭圆曲线 ECDSA 的阶 q，对秘密 x 加密后，再解密时需要模 q。如果参与方是不诚实的，那么会发生模 q 后约减。所以为了协议安全，需要检查被加密的值...
Number Theoretic Transform (NTT)
非常好的教程：https://eprint.iacr.org/2024/585.pdf给定度为 n-1 的多项式 G(x) 和 H(x)，可以得到乘法：$$ Y(x)=G(x) \cdot H(...
EdDSA TSS: FROST vs CMP20
CMP20 Schnorr：https://aping-dev.com/index.php/archives/535/FROST Schnorr：https://aping-dev.com/in...
zkvm-brainfuck [4] 生成 proof
算术化：将计算问题转换为有限域 F 上的多项式代数问题。zkSTARK 算数化会构建程序的代数中间表达 (Algebraic Intermediate Representation, AIR)，...
zkvm-brainfuck [3] 约束
通过 chip 的 eval() 函数对 trace 表的列添加约束。本文列出每个 chip 的核心约束。列出如下变量/寄存器clk：每条指令运行的时间戳pc：指令指针，指向当前指令ci：当前指...
zkvm brainfuck [2] 生成 Trace
ExecutionRecord为了实现对 brainfuck 程序的约束，需要将每条指令运行过程中的一些信息收集起来，放到 ExecutionRecord 中。ExecutionRecord 中...