# Python/Rust implementations and notes from Proofs Arguments and Zero Knowledge study group

### Related tags

Command-line pazk

# What is this?

This is where I'll be collecting resources related to the Study Group on Dr. Justin Thaler's Proofs Arguments And Zero Knowledge Book. The notes posted here will be copied out of my personal Obsidian note client; certain features like image and latex embedding will not render on Github, though should still be readable. If you would like to read them with latex rendering, a hack solution might be to copy them to a HackMD document.

The group open to everyone, and runs out of the ZK hack discord server by myself and the nice folks at the Zero Knowledge Podcast.

• Bryan's explainer on multilinear Lagrange interpolation
• A Zoo to visit weird and wonderful Complexity classes (note that complexity theory is not required or even core knowledge for this book, but exists as one of many rabbit holes to dive into)
##### decaf377-rdsa is a randomizable signature scheme using the decaf377 group.

decaf377-rdsa is a variant of RedDSA, instantiated using the decaf377 group. Signatures are parameterized by domain (for instance, Binding and SpendAu

##### Librarian runs pre-configured commands against a group of files that match a set of filters

Filesystem Librarian Librarian runs pre-configured commands against a group of files that match a set of filters. The group of files is called a libra

##### Interpreted, optimized, JITed and compiled implementations of the Brainfuck lang.

Interpreted, Optimized, JITed and Compiled Brainfuck implementations This repo contains a series of brainfuck implementations based on Eli Bendersky b

##### Rust library to convert RGB 24-bit colors into ANSI 256 (8-bit) color codes with zero dependencies and at compile-time.

rgb2ansi256 rgb2ansi256 is a small Rust library to convert RGB 24-bit colors into ANSI 256 (8-bit) color codes with zero dependencies and const fn. Th

##### A "Hello, Rust!" program for the Flipper Zero

"Hello, Rust!" for the Flipper Zero This is an example of how to build a Rust-based Flipper application that runs from the SD-card. Note: This depends

##### Pure rust library for reading / writing DNG files providing access to the raw data in a zero-copy friendly way.

DNG-rs   A pure rust library for reading / writing DNG files providing access to the raw data in a zero-copy friendly way. Also containing code for re

##### zero-dependency 3d math library in rust

dualquat A lightweight, zero-dependency 3d math library for use in Dual Quaternion based physics simulation. Capable of representing and transforming

##### A zero-dependency crate for writing repetitive code easier and faster.

akin A zero-dependency crate for writing repetitive code easier and faster. Check Syntax for information about how to use it. Why? Example Syntax NONE

##### A truly zero-dependency crate providing quick, easy, reliable, and scalable access to the name "jordin"

jordin Finally! A truly zero-dependency crate providing quick, easy, reliable, and scalable access to the name "jordin". Additionally, this one-of-a-k

• #### Question on the 4.5.1 (Super-Efficient IP for counting triangle)

I was thinking to post this question in the discord, but feeling the timeline style of conversion there is difficult to track of. Not sure if this is the best place to ask implementation questions relating the knowledge in the survey paper. If not, please let me know if there is an alternative.

The sum check and the triangle counting example is intriguing. Currently I am making an implementation to demonstrate the sumcheck protocol over the triangle counting, with the MatMul IP optimization described in the section 4.4.2 of the survey paper. While implementing for the example definitely helps me understand the concepts thoroughly, I think this might serve as another examples to help others enhance the understanding the combination usage of the related concepts in addition to the existing vanilla sumcheck implementations.

One area in the protocol puzzles me for quite a while is how the two sum check protocols used in the triangle counting example wire up. To describe the question in details, I outline my understanding of the procedures of invoking the sum check and MatMul IP protocols below.

### 1st sumcheck

1.1 Prover calculates the MLEs give the entries of matrix $A$ and $A^2$, and invokes the sumcheck protocol using the following equation and send univariate $g$ polynomial to verifier $$\tilde{f}_{A^2}(X, Y) \cdot \tilde{f}_A(X, Y)$$ 1.2 Verifier recursively checks $$g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$$ 1.3 until the last round $$g_v\left(X_v\right)=g\left(r_1, \ldots, X_v\right)$$

Because it is expensive for the verifier to validate the result in the last round by evaluating the $g(r_1,r_2,...,r_v)$, which corresponds to $\widetilde{f}_{A^{2}} \cdot \widetilde{f}_A$ given the entries of $A$ matrix, so it invokes the matmul IP to complete the check for the final round in the 1st sumcheck.

### 2nd sumcheck

2.1 Verifier chooses $(r_1, r_2)$ and invokes MatMul IP 2.2 Prover responses $$s(X):=\widetilde{f}_A\left(r_1, X\right) \cdot \widetilde{f}_A\left(X, r_2\right)=\left(r_1(1-X)+\left(1-r_1\right) X\right) \cdot\left(X\left(1-r_2\right)+r_2(1-X)\right)$$ 2.3 Verifier evaluates $$\tilde{f}_{A^2}\left(r_1, r_2\right)=s(0)+s(1)=r_1 r_2+\left(1-r_1\right)\left(1-r_2\right)$$, and multiplies it with $\tilde{f}_A\left(r_1, r_2\right)$ in order to get the target result $$\widetilde{f}_{A^{2}}\left(r_1, r_2\right) \cdot \widetilde{f}_A\left(r_1, r_2\right)$$ In my understanding, to convince the verifier the result of the double sumcheck protocol, the values from the equations of (1.3) and (2.3) should be equal.

However, in the first sumcheck, the random values $(r_1, r_2,...,r_{v-1})$ are already bounded(or I should call it "determined"). But in the second sumcheck in the matmul IP, the $(r_1, r_2)$ are newly chosen random values, unrelated to the corresponding ones although synthetically the same.

If $(r_1, r_2)$ doesn't represent the same random numbers as in the first sumcheck, the resulting value in the (1.3) won't be equal to (2.3). So I assume applying a new random number $r_3$ to both $s(X)$ in (2.2) and $g_v(X_v)$ in (1.3) neither makes them equal.

Then how can the verifier be convinced of the whole process? It is probably something I am missing during the process described above. Appreciate any hints.

opened by katat 1
zk wink
###### parse command-line arguments into a hashmap and vec of positional args

parse command-line arguments into a hashmap and vec of positional args This library doesn't populate custom structs, format help messages, or convert types.

17 Aug 11, 2022
###### ddi is a wrapper for dd. It takes all the same arguments, and all it really does is call dd in the background

ddi A safer dd Introduction If you ever used dd, the GNU coreutil that lets you copy data from one file to another, then you may have encountered a ty

80 Sep 8, 2022
###### Parse command line arguments by defining a struct.

StructOpt Parse command line arguments by defining a struct. It combines clap with custom derive. Documentation Find it on Docs.rs. You can also check

2.6k Jan 5, 2023
###### Notes on learning the Rust programming language syntax.

notes-on-rust Notes on learning the Rust programming language syntax. Resources https://www.rust-lang.org/learn/get-started https://doc.rust-lang.org/

1 Jan 2, 2022

9 Dec 18, 2022
###### ⚡️ A blazing fast way of maintaining powerful notes with connections between them.

Zettl ⚡️ A blazing fast way of maintaining powerful notes with connections between them. Installing Zettl To install Zettl, you will need the Rust too

26 Dec 2, 2022
###### Rust Imaging Library's Python binding: A performant and high-level image processing library for Python written in Rust

ril-py Rust Imaging Library for Python: Python bindings for ril, a performant and high-level image processing library written in Rust. What's this? Th

13 Dec 6, 2022
###### VICTOR: An Arcane Connect Four AI using Ancient Knowledge from the 80s

VICTOR VICTOR is a program based on 'A Knowledge-based Approach of Connect-Four' by Victor Allis. The original program written in C has been lost to h

2 Jan 6, 2022
###### An NTP implementation in Rust, supported by Internet Security Research Group's Prossimo project.

NTPD-rs NTPD-rs is an implementation of NTP completely written in Rust, with a focus on exposing a minimal attack surface. The project is currently in

302 Jan 4, 2023
###### Yet Another Kalman Filter Implementation. As well as Lie Theory (Lie group and algebra) on SE(3). [no_std] is supported by default.

yakf - Yet Another Kalman Filter Yet Another Kalman Filter Implementation, as well as, Lie Theory (Lie group, algebra, vector) on SO(3), SE(3), SO(2),

7 Dec 1, 2022