Shuang's Crypto Notes - Learning new things!

Parallel Computing in Rust and C++ part 1

Parallelism in Rust usually means one of three things:

Data-parallel CPU work (split work across cores)
Task parallelism (run independent CPU tasks concurrently)
Async concurrency (lots of I/O, not CPU parallel by default)

When making things go parallel, there are following things to consider. Safe parallel code comes from being …

What a procedural macro is (in one sentence)

A procedural macro is Rust code that runs at compile time and generates Rust code by programmatically transforming syntax trees.

Normal Rust code runs at runtime

Procedural macros run while the compiler is compiling

How to use procedural macro

Define the macro

…

Transpiler, Interpreter, Runtime

A transpiler:

takes code in one high-level language
rewrites it into another high-level language
while preserving semantics

Classic examples:

TypeScript → JavaScript
Modern JS → older JS
Wasm → C
DSL → Rust

What an interpreter is

An interpreter is a program that executes another program directly, instruction …

Ownership in Rust

Every value in Rust has exactly one owner at a time, and when the owner goes away, the value is automatically cleaned up.

Let’s build this step by step.

1️⃣ The three ownership rules

Rust enforces these at compile time:

Each value has one owner
There can only be one

…

Rust dynamic and static dispatch

Static Dispatch

What it is

The function implementation is chosen at compile time
Used by generics (T: Trait, impl Trait)

How it works

The compiler monomorphizes generic code
A separate, concrete version of the function is generated for each type
All types and sizes are known at

…

Sumcheck optimization 2: Quasilinear Time and Square-Root Space old implementation

explanation for this equation:

\(\underbrace{p(r_1, …, r_i, x’)}_{x’\in\{0,1\}^{i-l}}= \sum\limits_{y\in \{0,1\}^l}\widetilde{eq}(r_1, …, r_i, x’,y)\cdot p(y)\)

\(=\sum\limits_{y\in \{0,1\}^l}\underbrace{\widetilde{eq}(r_1, …, r_i, y)}_{y\in \{0,1\}^{i}}\underbrace{\widetilde{eq}(x’,y)}_{y\in \{0,1\}^{l-i}}\cdot \underbrace{p(y)}_{y\in \{0,1\}^l}\)

\(=\sum\limits_{y\in \{0,1\}^i}\underbrace{\widetilde{eq}(r_1, …, r_i, y)}_{y\in \{0,1\}^{i}}\underbrace{\cdot p(y, x’)}_{y\in \{0,1\}^{i}}\)

…

Stream prover

what stream prover exactly means? find definition here (page 5):

So the “streaming” means that the witness of the sumcheck protocol, i.e., the evaluations of a multilinear polynomial, is not counted in the RAM of the prover, prover doesn’t need to store this information, but only re-generated it when every …

Debugging Rust in VS code

follow the instruction in this video

…

Coding skills keywords

This post collects the concepts people mentioned for different programming languages, so I can understand what they are talking about.

Rust:

ownership,

lifetimes,

memory safety

Tokio

async await,

event driven Rust systems

asynchronous programming and concurrency patterns

C++:

template meta-programming, SFINAE, RAII, constexpr,

multithreading, web protocol (e.g. websocket, RESTful)

event-driven …

Sumcheck optimization 1: linear space and linear time old implementation

protocol:

Optimization in special case:

linear time, linear space prover:

Analysis:

To what I can think of:

\(d\cdot (d-1) \cdot 2^{l-1}\) small multiplication come from that \(s_1(u)\) is a \(d\) degree polynomial, that means prover needs to send \(d\) points to the verifier(shouldn’t be d+1?), for each points, there will …