$\newcommand{\pair}{\mathcal{e}}$ $\newcommand{\Gone}{\mathbb{G}_1}$ $\newcommand{\Gtwo}{\mathbb{G}_2}$ $\newcommand{\Gt}{\mathbb{G}_t}$ $\newcommand{\SP}{SnarkPack}$ $\newcommand{\vA}{\mathbf{A}}$ $\newcommand{\vB}{\mathbf{B}}$ $\newcommand{\vC}{\mathbf{C}}$ Last Major Update: May 16th 2021 Approach, Scope and Limitations of This Audit The general approach is convincing (as I elaborate below), so I focused on the specific building blocks, MIPP and TIPP Since MIPP and TIPP are mostly applications of the GIPA protocols in BMM+19, I mostly focused on the security aspects that were specific to SnarkPack. I have read the discussions and some of the proofs in BMM+19; I have not checked all their details. I have reviewed the top-level approach in the code---which seems correct. I spent additional time looking at the code portions related to the issues I mention below. Summary of This Audit

Syntax and notiation for sealing/unsealing NB: We always assume that sealing and unsealing have access to a random oracle $H_\text{salt}$ where $\text{salt} = (sid||dig_D)$ where $sid$ is some session id and $dig_D$ is a digest of the data $D$ (for example the root of the Merkle Tree computed on the data $D$). We keep these parameters implicit when obvious from the context. $\mathsf{Seal}(D) \to R$: sealing data $D$ computes a replica $R$ $\mathsf{Unseal}(R) \to D$: unsealing a replica $R$ allows to recompute the data We define $T_\text{seal}$ as the (parallel) time required to run seal. We consider the setting of asymmetric constructions where the time to seal and unseal may be different. We describe the ratio between sealing and unsealing time through a constant $k \in \mathbb{N}$ so that the time to unseal is $\frac{T_\text{seal}}{k}$. We also consider the time $T_\text{chal}$ "allowed for responding to a challenge". This time is always such that $T_\text{seal} > T_\text{chal}$. Later in this note we will consider the ratio $T_\text{seal}/T_\text{chal}$.

$\def\RR{{\bf R}}$ $\def\bold#1{{\bf #1}}$ $\def\pL{{{\mathbf{p}}^{(i)}{\leftarrow}}}$ $\def\bold#1{{\bf #1}}$ $\def\pLm{{{\mathbf{P}}{\leftarrow}}}$ $\def\pR{{{\mathbf{p}}^{(i)}{\rightarrow}}}$ $\def\pRm{{{\mathbf{P}}{\rightarrow}}}$ $\def\fLm{{{\mathbf{F}}{\leftarrow}}}$ $\def\fRm{{{\mathbf{F}}{\rightarrow}}}$ $\def\Nint{{N_{int}}}$ $\def\sparse#1{{\bbox[1px, border: 1.5px solid red]{\bold{#1}}}}$ $\def\vstack#1#2{{\overset{#1}{\underset{#2}{=}}}}$

The setting for lookups When proving a relation (think in a SNARK), standard arithmetic gates can be an awkward way to express what you want to prove. For example, byte-to-byte XOR (ubiquitous, e.g., in hashing) requires several arithmetic gates to be expressed. A more compact way to express this and other constraints is a lookup table:precompute all possible values of the table and store them in a commitment at proving time, just prove you know a row in that table. This is tantamount to of showing that you know, say, A,B,C such that A XOR B = C. A building block for this setting can be composed with other SNARKs and get a significantly more efficient prover. Useful, but how do we build this? If you ignore that a table is actually composed of "multiple columns"[^col], then this sounds like a vector commitment problem: just lookup, say, XOR outputs, by proving some values are inside a precommitted vector. This is what a vector commitment does! [^vc] Except, that we actually have a few more problems to solve (explained below) This is why vector commitments are inadequate for the job. We need a better primitive!

This is a draft of the proof Current proof for pUT: Claim of security is: assume a sUT for distribution D(z) defined as follows: let T = z sample epk-s return $F^{resh}_{T,epk-s}$ then the pUT built with that sUT is secure.