Logup GKR

following this post

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 \(i\), with \(n\) number of rows (trace degree, trace length)

\(f_i(b_0,b_1,b_2,…,b_n)=a_{b_n,…,b_2,b_1,b_0} \)

the multi-linear polynomial for …

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

Original protocol:

The above statement essentially proves:

\(\frac{1}{\alpha -x_0}+\frac{1}{\alpha -x_1}=\frac{2}{\alpha}\)

where \(\alpha\) is a random …

Spartan 2 some basic terminologies

Follow my first post for Spartan

Closed-form expression for evaluating a polynomial

The closed-form expression for evaluating a polynomial \(\mathcal{G}(\cdot)\) at \((r_1,…,r_m)\in \mathbb{F}^m\) is

$$\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 …

Review, remove_trait_impls

Related type:

TraitsResolver

TraitsResolver helps to find the implementation for a given trait function and concrete type arguments.

TraitsResolver has a function resolve_trait_function_reference (see below) for a given polynomial reference, it resolves its trait

one of the input to this polynomialReference,

using fibo_no_public example, PolynomialReference looks like:

Understanding the remove_trait_impls

Rust notes

crate and trait

Crate
  1. Definition

The Short NIZK Argument in Pribank

We give a commit-and-prove zero-knowledge argument Protocol for the satisfiability of a QAP for an arithmetic circuit \(C\). For wires in the circuit \(\{a_i\}_{i=0}^n\), we denote the input witnesses are \(\{a_i\}_{i=0}^k\), the inner circuit witnesses are \(\{a_{i}\}_{i=k+1}^l\) and the statements wires are \(\{a_{i}\}_{i=l+1}^n\). The quadratic arithmetic program, Pedersen commitment and …