Random collections of my notes and articles over the years, mostly about maths and/or engineering.
Work in progress. This note is a work in progress with many loose ends and unfinished sentences. Multi-Party Computation My goal here is to present semi-honest linear MPC in its most general algebraic form. The assumption here is that the MPC will compute a coSNARK which makes computational soundness externally verifiable. In this setting adversarial resistance is less important and we can work in…
Probabilistic Uniqueness Ground Truth Consider a set of observations \mathcal{O} and a binary relation \mathord{\sim} \subseteq \mathcal{O} \times \mathcal{O} such that a \sim b means that the observations are of the same entity. Then \sim is an equivalence relation and the unique entities are given by the quotient set \mathcal{O}/\mathord{\sim} . Noisy Equivalence Now consider we can not…
Physics QM from Decoherence
List Decoding MDS Codes \gdef\p#1{\left({#1}\right)} \gdef\set#1{\left\{{#1}\right\}} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\norm#1{\left|{#1}\right|} \gdef\setn#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}} \gdef\om{\mathrm{\omega}} \gdef\wt{\operatorname{wt}} \gdef\d{\operatorname{d}} \gdef\A{\operatorname{A}} \gdef\Aut{\operatorname{Aut}}…
Sumcheck \gdef\vec#1{\mathbf{#1}} \gdef\F{\mathbb{F}} Given a field \F , and a linear space V over \F given by the tensor product V = T_1 \otimes T_2 \otimes \cdots \otimes T_n \text{.} The prover has a tensor T \in V and wants to prove some linear functional f(T) = s . Verifiers perspective Verifier has a sum s_0 . In the first round it receives a (typically short) vector \vec v_1 . And verifies…
Merkle Multi-Proofs \gdef\p#1{\left({#1}\right)} \gdef\setp#1{\left\{{#1}\right\}} \gdef\stirlingii#1#2{{{#1} \brace {#2}}} \gdef\setn#1{\mathcal{#1}} \gdef\floor#1{\left\lfloor#1\right\rfloor} \gdef\ceil#1{\left\lceil#1\right\rceil} \gdef\vec#1{\mathbf{#1}} \gdef\H{\mathsf{hash}} \gdef\bar#1{\left\lvert{#1}\right\rvert} \gdef\Exp#1{\mathbb{E}\!\left[{#1}\right]}…
Inner Product Commitment Schemes \gdef\p#1{\left({#1}\right)} \gdef\Norm#1{\left\lVert{#1}\right\rVert} \gdef\range#1{\left[#1\right)} \gdef\setn#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}} Definition 1. An \F_q -Inner Product Commitment Scheme is a tuple of algorithms (\mathsf{commit} , \mathsf{open} , \mathsf{verify}) such that. \mathsf{commit} algorithm…
Succinct Multi-Linear Extensions \gdef\p#1{\left({#1}\right)} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\floor#1{\left\lfloor{#1}\right\rfloor} \gdef\set#1{\left\{#1\right\}} \gdef\range#1{\left[#1\right)} \gdef\setn#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}} Many interactive proof systems rely on multi-linear extensions (MLEs) that can be…
Embedding Inner Products \gdef\p#1{\left({#1}\right)} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\norm#1{\left|{#1}\right|} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}} \gdef\i{\mathrm{i}} \gdef\j{\mathrm{j}} In cryptographic protocols it's useful to compute inner products over small fields \F_p while using a large extension field \F_{p^d} . The naive approach of…
Nullifiers It’s important to note that the nullifiers exist for one purpose only: to provide anonymity while preventing an account from repeating an action. For this to make sense at all creating accounts needs to be gated somehow. For anonymous currency (where nullifiers originate) an account is created on receiving a coin. In our case it is created on biometrically proven uniqueness. Nullifiers…
Oluś: a Pure Continuation-Passing-Style Language fact n return : if ( is_zero n ) (: return 1 ) (:) return ( mul n ( fact ( sub n 1 ))) I've always been facinated by programming languages and proof systems (they are closely related). In particular I'm fascinated by expressive minimal languages like Lisp, Forth and Metamath. These repesent some stable local optima in the design space of…
Field Extensions \gdef\p#1{\left({#1}\right)} \gdef\norm#1{\left|{#1}\right|} \gdef\F{\mathbb{F}} \gdef\i{\mathrm{i}} \gdef\j{\mathrm{j}} \gdef\om{\mathrm{\omega}} Given a prime field \F_p with p = 2^{31} - 1 . Because p is a Mersenne prime, it can be implemented particularly efficiently. It also neatly fits into a 32-bit integer allowing fast SIMD and GPU implementations and efficient use of…
Hensel Lifting \gdef\p#1{\left({#1}\right)} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}} \gdef\Z{\mathbb{Z}} \gdef\vd{𝛅} There are many variants of Hensel's lemma and the one derived here is for quadratic lifting of multivariate roots. This is useful solving systems of polynomial equations in modular and Galois rings. One starts by finding a solution in the residue…
Winograd NTT \gdef\vec#1{\mathbf{#1}} \gdef\F{\mathbb{F}} \gdef\ω{\mathrm{ω}} \gdef\A{\mathsf{\small A}} \gdef\Mc{\mathsf{\small M^c}} Definition 1. (Number Theoretic Transform) . Given a finite field \F with primitive n -th root of unity \omega_n and a vector \vec a \in \F^n the number theoretic transform (NTT) \vec b \in \F^n of \vec a is \begin{equation} b_j = \sum_{i \in [n]} \ω_n^{i ⋅ j} ⋅…
WHIR Multilinear Polynomial Commitments. \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\eq{\operatorname{eq}} \gdef\∀{\mathop{\huge ∀}\limits} WHIR combines the ideas from STIR with those from Basefold to achieve a very performant polynomial commitment scheme…
Multivariate Lookup Arguments \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\vec#1{\mathbf{#1}} \gdef\eq{\operatorname{eq}} Most lookup protocols are based on univariate polynomials. In the multivariate sumcheck setting can use different techniques from the Lasso line of work. Lookup arguments and indexed lookup arguments .…
Brakedown and Shockwave \gdef\setn#1{\mathcal{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\enc{\mathsf{enc}} From GLS⁺21 . Like in Hyrax, we will create a commitment to a matrix \mat M ∈ 𝔽^{n×m} such that we can later compute double contractions s = \vec p ⋅ \mat M ⋅ \vec q = \sum_{ij} \mat M_{ij}⋅p_i⋅q_j for some arbitrary vectors \vec p, \vec q . Take a linear code \enc:…
Hyrax Commitments \gdef\p#1{\left({#1}\right)} \gdef\vec#1{\mathbf{#1}} \gdef\eq{\mathrm{eq}} \gdef\setn#1{\mathcal #1} Hyrax commitments are introduced in WTS⁺17 . They are a polynomial commitment scheme designed for multi-linear extenstions (MLEs). Certain Multivariate Sums as Tensor Contractions Given a finite multi-variate basis \setn B = \setn B_1 × \setn B_2 × ⋯ × \setn B_n with \setn B_i ⊂…
GKR \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\set#1{\mathcal #1} \gdef\vec#1{\bm #1} \gdef\eq{\mathrm{eq}} \gdef\mul{\mathsf{mul}} \gdef\add{\mathsf{add}} \gdef\addc{\mathsf{add^C}} Last year saw the publication of many interesting new proof systems that deviate from the pattern of doing…
Jolt \gdef\mat#1{\mathrm{#1}} \gdef\p#1{\left({#1}\right)} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\forall{\mathop{\huge ∀}\limits} Notes studying Jolt. Per Michael Zhu's suggestion I will follow the lineage from Spice SAGL18 , Spartan S19 , Lasso STW23 , Jolt AST23 , Binius DP23 . Spice Spartan Spartan ( S19 ) is a transparant zkSNARK for R1CS. Recal an R1CS instance over a field 𝔽…
\gdef\Z{\mathbb{Z}} \gdef\F{\mathbb{F}} Introduction to ZK-STARKs \gdef\F{\mathtt{F}} \gdef\X{\mathtt{X}} \gdef\Y{\mathtt{Y}} \gdef\Z{\mathtt{Z}} Disclaimer: contains math If you don't understand something Not your fault, this stuff is hard Nobody understands it fully If you don't understand anything My fault, anything can be explained at some level If you do understand everything…
\gdef\R{\mathbb{R}} \gdef\p#1{({#1})} \gdef\norm#1{\lVert{#1}\rVert} \gdef\setb#1#2{\{{#1} \mid {#2}\}} \gdef\Pr#1{\operatorname{Pr}\p{#1}} \gdef\sign{\operatorname{sign}} Locality-Sensitive Hashing \gdef\S{\mathrm{S}} \gdef\darc{d_{\mathrm{arc}}} \gdef\sign#1{\mathrm{sign}\p{#1}} Let \S_n be an n -dimensional unit n -sphere \begin{align} \mathrm{S}_n = \setb{\vec x ∈ \R^n}{\norm{\vec x}_2 = 1}…
Syntax Functions History of functions. Definition set of ordered pairs such that the first elements occurs at most once. \set{(x,y)} Multiple return values are natural, see the division algorithm. Nearly all programming language support multiple input value, some also multiple return values. Both are not strictly more expressive. Multiple return values can be implemented using tuples. Multiple…
Optimal filters https://dsp.stackexchange.com/questions/9745/which-iir-filters-approximate-a-gaussian-filter Gaussian blur can be approximated by a (fixed size) IIR filter: https://www.intel.com/content/dam/develop/external/us/en/documents/gaussian-filter-181134.pdf FIR are polynomials and IIR are rational functions:…
ZKP Gadgets \gdef\set#1{\mathcal{#1}} Binary check Constrain a ∈ {0, 1} : Constraints: a ⋅(1 - a) = 0 This is a special case of constraining a to a small set of values \{c_0, c_1, \dots \} : (a - c_0) ⋅(a - c_1) \cdots = 0 Zero check Given a construct b = \begin{cases} 0 & a \ne 0 \\ 1 & a = 0 & \end{cases} Constraints: \begin{aligned} b &= 1 - a ⋅ w & a ⋅ b &= 0 \end{aligned} Witness: w = a^{-1}…
\gdef\p#1{({#1})} \gdef\ceil#1{\lceil{#1}\rceil} \gdef\e{\mathrm{e}} \gdef\g{\mathrm{g}} Groth16 Tweaks \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\e{\mathrm{e}} Ethereum cost model See evm.codes and the yellow paper . Calldata costs 16 gas per zero bytes with a discounted price of 4 for zero bytes. So the expected cost of a uniformly random byte is 15.95 gas. On L1 calldata-gas and gas are the…
Hard Problems A list of CS problems for which great heuristics exists, but no optimal algorithm is known. Matrix multiplication Pre-processed polynomial evaluation Sorting networks Addition matrices FFT kernels
\gdef\F{\mathbb{F}} \gdef\p#1{\left({#1}\right)} \gdef\set#1{\mathcal{#1}} \gdef\Union{\bigcup} \gdef\inprod#1#2{\langle{#1, #2}\rangle} \gdef\e{\mathrm{e}} \gdef\g{\mathrm{g}} Polynomial commitment schemes \gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{G}} \gdef\h{\mathtt{H}} \gdef\e{\mathrm{e}} I will discuss polynomial commitment schemes for n -term polynomials, so polynomials of…
\gdef\Z{\mathbb{Z}} \gdef\F{\mathbb{F}} \gdef\p#1{\left({#1}\right)} \gdef\set#1{\mathcal{#1}} Polynomials \gdef\F{\mathbb{F}} \gdef\Z{\mathrm{Z}} Polynomial basis We convert this to a polynomial problem by picking a basis \vec x ∈ \F^n . Define zero polynomials to mean \Z_{\mathcal S}(X) = \prod_{s ∈ \mathcal S} \p{X - s} When not otherwise specified, take \mathcal S to be \vec x . Take \overline…
\gdef\F{\mathbb{F}} Proof systems This post is a reframing of the evolution of proof systems from the contemporary perspective of LDE polynomial commitment protocols. While proof systems have thus far always been presented end-to-end, they often break down into two parts: an arithmetization technique and a polynomial commitment scheme. Despite being presented integral, these are mostly…
Produce a Stark proof. Input A ConstraintSystem which captures the claim that is made. A TraceTable which is the witness to this claim. A ProofParams object which configures the proof. Output A ProverChannel . Proof construction A new ProverChannel is initialized with the public input. Step 1: Low degree extension of the trace table. The trace table is interpolated to an evaluation domain that is…
Notes on Starky Currently it Forces constraints to be between two consecutive rows, except first and last, which are handled separately. Does not have abstractions allowing for the creation of complex proofs. Does not yet implement constant polynomials ('permutation checks'), but a lot of infra is there. Implements multiple OODS samples (?) Not optimized for very large traces. (no…
Folding Schemes \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\set#1{\mathcal{#1}} \gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\R{\mathrm{R}} \gdef\P{\mathsf{cm}} \gdef\H{\mathsf{H}} \gdef\Z{\mathrm{Z}} \gdef\bigop#1#2{\mathop{\Large #1}\limits_{#2}} \gdef\zkp#1#2#3{\p{…
Polynomial Modulo Soundness We want to proof a polynomial modular multiplication (PMM) A_i(X) ⋅ B_i(X) = R_i(X) \mod P(X) Where A,B,R are low degree. We can do this using an auxiliary low-degree polynomial Q_i(X) and evaluating the following in a random point z A_i(z) ⋅ B_i(z) = Q_i(z) ⋅ P(z) + R_i(z) To verify many such PMMs we can take a linear combination in a random α \sum_i α^i ⋅ A_i(X) ⋅…
Oblivious RAM Assume we can execute a program in a trusted environment (TEE), but we have only a limited amount of memory locally. We do have access to a lot of external memory, but this is not trusted. As a first step, we can generate a private key in the TEE and use authenticating encryption to make it so only the TEE can read and write external memory (in this context referred to as RAM).…
Polynomial Ring \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\delim\{{#1}\}} Given a commutative ring with unity R . The polynomial ring R[X] . Characterizing the underlying set of this ring is surprisingly difficult. Start with the set of infinite sequences with elements in R (denoted R^ω ) and restrict it to sequences that have a finite…
The User Experience of Transaction Confirmation https://news.ycombinator.com/item?id=35845540 Why the web is friendly and web3 isn't. Background Operations in an application generally work like this: ![[Decentralized Consent 2023-05-01 10.04.07.excalidraw|600]] The user interacts with the digital world through a user agent 1 . The user agent is typically a web browser, but…
Preprocessing Bilinear Algorithms \gdef\vec#1{\mathbf#1} \gdef\mat#1{\mathrm#1} \gdef\p#1{\left({#1}\right)} Giver vector spaces u,V,T over R , any bilinear map U × V → T can be uniquely represented using a rank-3 tensor over R where b(\vec u, \vec v) = \sum_{ijk} u_i ⋅ v_j ⋅ t_{ijk} ⋅ \vec e_k provided a basis for all three spaces. Examples of bilinear maps are plentiful: dot products, polynomial…
Approximate Fraction Matching Goal. We need to compare a fraction \frac{a}{b} < t where 0 \leq a \leq b \leq 12\,800 and t\in[0,1] . We want to approximate t by a fraction \hat{t} = \frac{c}{d \cdot p} where p = 65\,519 and d \cdot p < 2^{32} . The approximation error is the maximum observable discrepancy. \max \vert \frac{a}{b} - \hat{t} \vert Question. What are the optimal values of c and d ,…
Dot products in Galois rings \gdef\vec#1{\mathbf#1} \gdef\mat#1{\mathrm#1} \gdef\setn#1{\mathcal#1} \gdef\p#1{\left({#1}\right)} (These are my notes from studying an idea worked out by Bryan Gillespie) Galois Rings Informally, a Galois ring is a generalisation of a Galois field 𝔽_{p^m} to have coefficients from the ring of integers modulo p^s for some s ≥ 1 . It inherits much of the structure of…
Winograd Fast Inner Product \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ceil#1{\delim\lceil{#1}\rceil} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} PN23 mentions a clever trick due to Winograd W68 to compute inner products with half the number of multiplications after pre-processing. Observe for (a_0, a_1)⋅(b_0, b_1) we have a_0⋅b_0 + a_1 ⋅b_1 =…
Linear Secret Sharing Schemes \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\box#1{\delim[{#1}]} \gdef\floor#1{\delim\lfloor{#1}\rfloor} \gdef\ceil#1{\delim\lceil{#1}\rceil} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\setn#1{\mathcal{#1}} \gdef\Z{\mathrm{Z}} Thank you Daniel Kales, Roman Walch and others from TACEO…
Cholesky decomposition \gdef\mat#1{\mathrm #1} \gdef\T{\mathrm T} Positive definite matrices occur as covariance matrices. Given a positive definite matrix \mat M it can be factored into a triangular matrix \mat L such that \mat M = \mat L ⋅ \mat L^\T Computing the Cholesky decompostion https://en.wikipedia.org/wiki/Cholesky_decomposition#The_Cholesky_algorithm…
Gaussian Process inference \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\N{\mathcal N} \gdef\vec#1{\bm #1} \gdef\mat#1{\mathrm #1} \gdef\k{\mathrm k} \gdef\u{\mathrm u} \gdef\c{\mathrm c} \gdef\T{\mathrm T} Given \vec μ and \mat Σ such that \vec y is multivariate normal distributed. P\p{\vec y} ∼ \N\p{\vec μ, \mat Σ} Given a draw of standard normal…
Lookup arguments \gdef\vec#1{\bm{#1}} \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\mathcal{#1}} \gdef\mset#1{\mathrm{#1}} \gdef\g{\mathrm{g}} \gdef\F{\mathbb{F}} \gdef\S{\mathcal S} \gdef\X{\mathcal X} \gdef\Z{\mathrm{Z}} \gdef\∀{\mathop{\huge ∀}\limits} Zero polynomials Given a multiset \mset A over 𝔽 define the zero polynomial \Z_{\mset A} ∈…
Multi-party Computation notes. \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\box#1{\delim[{#1}]} \gdef\bbox#1{\mathopen{[\mkern-3mu[}{#1}\mathclose{]\mkern-3mu]}} \gdef\set#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} A Secure Multi-Party Computation Scheme (MPC) allows a set of parties \set P to compute…
Representing (masked) bits in rings \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\T{\mathsf{T}} \gdef\F{\mathsf{F}} \gdef\U{\mathsf{U}} \gdef\popcount{\mathtt{popcount}} \gdef\count{\mathtt{count}} \gdef\hamming{\mathtt{hamming}} \gdef\fhd{\mathtt{fhd}} \gdef\vsum{\mathtt{sum}} In cryptography it is often useful to represent bits in algebraic objects. I will specifically consider rings…
Sumcheck, MLEs and GKR Split up into two pages: Sumcheck GKR
Sumcheck and MLEs \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\set#1{\mathcal #1} \gdef\vec#1{\bm #1} \gdef\popcount{\mathrm{popcount}} \gdef\eq{\mathrm{eq}} \gdef\∀{\mathop{\huge ∀}\limits} \gdef\mul{\mathsf{mul}} \gdef\add{\mathsf{add}} \gdef\addc{\mathsf{add^C}} \gdef\bar#1{\overline{#1}} Sumcheck…
Abstract Algebra \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\delim\{{#1}\}} \gdef\floor#1{\delim\lfloor{#1}\rfloor} \gdef\ceil#1{\delim\lceil{#1}\rceil} \gdef\norm#1{\delim\vert{#1}\vert} \gdef\S{\mathcal S} \gdef\G{\mathcal G} \gdef\vec#1{\bf{#1}} \gdef\Z{\mathrm{Z}} A binary operation is a total function f:\S×\S →\S for some set \S .…