Zero knowledge proof - Shuang's Crypto Notes

Logup GKR – 3: Air constraint for STARK

Table of Contents

…

Logup GKR 2

following previous post

Table of Contents

Input Layer Encoding (witness encoding)

…

Logup GKR

following this post

Table of Contents

Witness encoding:

trace columns are interpreted as functions, the inputs of the function are bits, enough number of bits that can present \(n\) number of witness in this column.

for trace …

Commonly used tricks in Multilinear polynomials

Table of Contents

Equation function

Turn a function in binary field to its multilinear extension.

let \(\mathcal{G}\) be a function in binary field, its multi-linear extension can be presented as:

$$\mathcal{G}(r_1,…,r_m)=\sum\limits_{x\in\{0,1\}^m}\mathcal{G}(x)\prod\limits^{m}_{i=1}\underbrace{(r_i\cdot x_i + (1-r_i)(1-x_i))}_{x_i=0 \rightarrow 1-r_i, x=1 …

High degree constraint in Plonky3 and Stwo

Table of Contents

…

The bus_id in Bus

I am using a simplified circuit for case demonstration purpose:

The bus statement to be proved is:

\([x_0,x_1]\) in [0] with \(bus_{id}\)=a,

this case has only one valid witness [0,0], with multiplicity to be 2

Table of Contents

…

Note for bus in stwo 2

continue from this blog

Table of Contents

…

Notes for bus in stwo

related to this PR

Test case

cargo install --path ./cli-rs

compile with the correct field

powdr-rs compile riscv/tests/riscv_data/keccak -o output --field bb

cargo run --features stwo pil  output/keccak.asm --linker-mode native  -o output --force --field m31  --prove-with stworesult.txt

This can give keccak_opt.pil file with lookup identity, it is native lookup, …

Spartan 5

following previous posts: 1,2,3,4

Table of Contents

An \(O(n)\)-sized circuit for evaluating \(\widetilde{M}\)

talking about this circuit:

notes:

for witness: \(row, col, val\) are enough to describe a multilinear extension \(\widetilde{M}\)

\(e_{row}, e_{col}\) should be

…

Native logup implementation of Stwo backend Powdr -2

following the first post 1

test command

RUST_LOG=stwo=trace cargo test --package powdr-pipeline --test pil --features stwo -- witness_lookup --exact --show-outputresult.txt

Table of Contents

…