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

Related tags

Command-line pazk
Overview

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.

Have a nice repo of your own? I'd love to link to it! Questions about this resource? DM me on Twitter.

Links

  • 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)
You might also like...
`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.
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

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

    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
Owner
Thor
zk wink
Thor
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.

James Halliday 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

Tomás Ralph 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

Guillaume P. 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/

Fred Snyder 1 Jan 2, 2022
Create tasks and save notes offline from your terminal

Create tasks and save notes offline from your terminal

null 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

Tirth Jain 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

Cryptex 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

null 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

Prossimo (ISRG) 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),

null 7 Dec 1, 2022