Zero knowledge proof - Shuang's Crypto Notes

Add bus interactions for plonk circuit

how the plonkChip get the AIR?

we first check how the powdrChip gets its air:

it takes a machine as input, generate a PowdrAir.

check how the new function of powdrAir is implemented?

but it needs to define PlonkAir data structure

PowdrAir has this

it make sense to have machine …

PowdrChip and PlonkChip

Note taken for PR review

Table of Contents

PowdrChip and its traits

Defined in powdr_extension, probably follow the format of adding extension to openvm

as it follows the format of adding extension to openvm, which means …

Powdr Autopre-compile

From lib.rs, there is test, checking prove simple:

check what this prove simple means

there are some prove and compile, prove recursion basic function in this file.

Table of Contents

Compile:

In the compile function, there are two functions til now I think …

About Keccak

Table of Contents

Performance metrics

When people talking about the performance of the hash functions in SHA-3 family, what are the key performance metrics they …

Compiler Concept

Transpiler:

A transpiler (short for source-to-source compiler) is a tool that transforms code from one representation to another, typically at the same or similar level of abstraction.

Table of Contents

…

Logup-GKR batching concept

Table of Contents

IOP: prove evaluation of a multi-linear extension polynomial

a cyclic group in base Field \( \mathbb{H} \) (STARK trace …

Logup GKR in an example

Table of Contents

traces:

\(a: [a_0,a_1,a_2,a_3,a_4,a_5,a_6,a_7]\)

\(b: [b_0,b_1,b_2,b_3,b_4,b_5,b_6,b_7]\)

goal:

prove logup relation:

\(\sum\limits_{i=0}^{i=7}\frac{1}{a_i+\alpha}=\sum\limits_{i=0}^{i=7}\frac{1}{b_i+\alpha}\)

what are available:

commitments to the traces via FIR:

\(\text{commit}[a(x)]\)

\(\text{commit}[b(x)]\)

note: \(a(x),b(x)\) denote the polynomials’ evaluation in trace domain, \(x\) comes from cyclic group.

GKR circuit: give a

…

logup GKR stwo implementation steps

Table of Contents

Include challenge in input MLE

…

Stwo logup-GKR : build test example

Table of Contents

step 1: get the most important 2 ingredients:

when create a component like this:

there are two important thing:

FrameworkComponent

eval that implement FrameworkEval

we can see the example actually use two types of Component, one …

Stwo Logup with GKR: extra traces for GKR

GKR circuit:

a layer in GKR : proversrccorelookupsgkr_prover.rslayer

they take Mle: multi-linear extension as “input”.

Mle: corelookupsmle.rs

stored its evaluations on boolean hypercube, which is enough to uniquely determined the MLE

come back to the GKR layer struct, search where LogUpGeneric is used.…