$$ \def\F{\mathbb{F}} \def\type{{\thinspace \textbf{:}\ }} \def\PubInputs{\textsf{PubInputs}} \def\CommROld{\textsf{CommROld}} \def\CommDNew{\textsf{CommDNew}} \def\CommRNew{\textsf{CommRNew}} \def\Groth{\textsf{Groth16}} \def\line#1{{{\small \rm \rlap{#1.}\hphantom{10.}} \ \ }} \def\tab{\quad\quad\ \ } \def\ngroth{n_{\small \textsf{Groth16}}} \def\PartitionCount{\textsf{PartitionCount}} $$ # SuperSnaps Spec ## Notation • $\texttt{const}\ \textsf{PartitionCount} = 16$ The number of Groth16 proofs per SnapDeals proof. • $k \in [0, \textsf{PartitionCount})$ A partition index, i.e. the index of a Groth16 proof in a SnapDeals proof containing $\textsf{PartitionCount}$ Groth16 proofs. • $n \in \mathbb{N}_{\ge 1}$ The number of SnapDeals proofs aggregated. • $(\CommROld, \CommDNew, \CommRNew) \in \F^3$ The three sector commitments associated with a SnapDeals proof. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; • $\CommROld$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; A commitment to the CC sector's PoRep replica. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; • $\CommDNew$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; A commitment to the updated sector's unreplicated data. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; • $\CommRNew$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; A commitment to the sector's SnapDeals replica. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; • $[(\CommROld, \CommDNew, \CommRNew); n]$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; An array containing the sector commitments of all $n$ SnapDeals proofs being aggregted. • $[\textsf{Groth16Proof}; \PartitionCount]$ A single SnapDeals proof consisting of $\PartitionCount$ Groth16 proofs. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; • $[[\textsf{Groth16Proof}; \PartitionCount]; n]$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; The Groth16 proofs of all $n$ SnapDeals proofs being aggregated. ## Implementation ### 1) $\texttt{create_transcript}$ Takes the sector commitments of all $n$ SnapDeals proofs being aggregated and returns their digest; this digest is included in the transcript of the SnapDeals proofs' aggregate SnarkPack proof. $\overline{\underline{\text{Function:}\ \texttt{create_transcript}([(\CommROld, \CommDNew, \CommRNew); n]) \rightarrow [\texttt{u8}; 32]}}$ $\line{1} \textsf{preimage} \type [\texttt{u8}; 96n] =$ $\tab \CommROld_0 \mathbin\Vert \CommRNew_0 \mathbin\Vert \CommDNew_0$ $\tab \mathbin\Vert \dots$ $\tab \mathbin\Vert\CommROld_{n - 1} \mathbin\Vert \CommRNew_{n - 1} \mathbin\Vert \CommDNew_{n - 1}$ $\line{2} \texttt{sha256}(\textsf{preimage})$ <br /> ### 2) $\texttt{aggregate_proofs}$ Aggregates $n$ SnapDeals proofs (equivalently, $n * \PartitionCount$ Groth16 proofs) into a single SnarkPack proof. The three sector commitments of each SnapDeals proof being aggregated are included in the transcript of the SnarkPack proof. $\overline{\text{Function:}\ \texttt{aggregate_proofs}( \hphantom{xxxxxxxxxxxxxxxxxx}}$ $\quad\ \textsf{proofs} \type [[\textsf{Groth16Proof}; \PartitionCount]; n],$ $\quad\ \textsf{commits} \type [(\CommROld, \CommDNew, \CommRNew); n],$ $\underline{)\phantom{} \rightarrow \textsf{SnarkPackProof}\hphantom{xxxxxxxxxxxxxxxxxxxxxxxxxxxxx}}$ $\line{1} \textsf{num_groth16} = n * \PartitionCount$ $\line{2} \textsf{num_groth16_padded} = 2^{\lceil \log_2(\textsf{num_groth16})\rceil}$ $\line{3} \textsf{pad_len} = \textsf{num_groth16_padded} - \textsf{num_groth16}$ $\line{4} \textsf{proofs} \type [\textsf{Groth16Proof}; \textsf{num_groth16}] = \textsf{proofs}\textbf{.}\texttt{flatten}()$ $\line{5} \textsf{proofs_padded} \type [\textsf{Groth16Proof}; \textsf{num_groth16_padded}] = \textsf{proofs} \mathbin\Vert [\textsf{proofs}_{\textsf{num_groth16} - 1}; \textsf{pad_len}]$ $\line{6} \textsf{transcript} \type [\texttt{u8}; 32] = \texttt{create_transcript}(\textsf{commits})$ $\line{7} \texttt{return}\ \texttt{snarkpack_prove}(\textsf{proofs_padded}, \textsf{transcript})$ <br /> ### 3) $\texttt{verify_aggregate_proof}$ Verifies a SnarkPack proof against $n$ SnapDeals sector commitments. $\overline{\text{Function:}\ \texttt{verify_aggregate_proof}( \hphantom{xxxxxxxxxxxxxxxx}}$ $\quad\ \textsf{aggregate_proof} \type \textsf{SnarkPackProof},$ $\quad\ \textsf{commits} \type [(\CommROld, \CommDNew, \CommRNew); n],$ $\underline{)\phantom{} \rightarrow \{0, 1\} \hphantom{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}}$ $\line{1} \textsf{num_groth16} = n * \PartitionCount$ $\line{2} \textsf{num_groth16_padded} = 2^{\lceil \log_2(\textsf{num_groth16})\rceil}$ $\line{3} \textsf{pad_len} = \textsf{num_groth16_padded} - \textsf{num_groth16}$ $\line{4} \textsf{pub_inputs}: [[\F; 4]; \textsf{num_groth16}]$ $\line{5} \texttt{for}\ i \in [0, n) \type$ $\line{6} \tab \texttt{for}\ k \in [0, \PartitionCount) \type$ $\line{7} \tab\tab \textsf{pub_inputs}\textbf{.}\texttt{push}(\texttt{groth16_pub_inputs}(\CommROld_i, \CommDNew_i, \CommRNew_i, k) )$ $\line{8} \textsf{pub_inputs_padded} \type [[\F; 4]; \textsf{num_groth16_padded}] = \textsf{pub_inputs} \mathbin\Vert [\textsf{pub_inputs}_{\textsf{num_groth16} - 1}; \textsf{pad_len}]$ $\line{9} \textsf{transcript} \type [\texttt{u8}; 32] = \texttt{create_transcript}(\textsf{commits})$ $\line{10} \texttt{return}\ \texttt{snarkpack_verify}(\textsf{aggregate_proof}, \textsf{pub_inputs}, \textsf{transcript})$ <br /> ### 4) $\texttt{groth16_pub_inputs}$ Takes a sector's SnapDeals commitments and a partition index $k$ (i.e. Groth16 proof index) and returns the public inputs for that sector's $k^{th}$ SnapDeals Groth16 proof. • $[\F; 4]$ The four public inputs to a single SnapDeals Groth16 proof. • $\texttt{const}\ \textsf{h_mask} = (1 \ll 3) \ll \log_2(\PartitionCount) = \textsf{0b}10000000$ The bitwise OR-mask that is applied to each Groth16 proof's partition index $k$ to produce that proof's first public input $k \vee \textsf{h_mask}$, i.e. the first public input to each SnapDeals Groth16 proof is the binary representation of $k$ and the SnapDeals $h$ value. $\overline{\underline{\text{Function:}\ \texttt{groth16_pub_inputs}(\CommROld, \CommDNew, \CommRNew, k) \rightarrow [\F; 4]}}$ $\line{1} \texttt{return}\ [k \vee \textsf{h_mask}, \CommROld, \CommDNew, \CommRNew]$
Last changed by  
 
Jake
79

Read more

Synth-PoRep Spec

\def\C\{\text{C}} \def\Csyn\{\text{C}^{\text{syn}}} \def\N\{\text{N}} \def\Nsyn\{\text{N}^\text{syn}} \def\Ch\{\text{Ch}} \def\csyn_#1{c^\text{syn}_{#1}} \def\Bit\{\{0, 1\}} \def\par\{\mathbin\Vert} \def\TreeD\{\text{TreeD}} \def\TreeC\{\text{TreeC}} \def\TreeR\{\text{TreeR}} \def\CommR\{\text{CommR}} \def\SectorSize\{\textsf{SECTOR_SIZE}} \def\SectorNodes\{\textsf{SECTOR_NODES}} \def\Gib\{\text{GiB}} \def\ReplicaID\{\text{ReplicaID}}

3/10/2023
PLONK Arithmetization

$$ \def\Zp{{\mathbb{Z}_p}} \def\F{{\mathbb{F}}} \def\Bit{{{0, 1}}} \def\PI{{\textsf{PI}}} \def\bold#1{\boldsymbol{#1}} \def\stop{{\rlap{\quad.}\hphantom{}}} \def\qed{{\rlap{\quad \tiny\blacksquare}\hphantom{}}} \def\par{{\thinspace {\parallel} \thinspace}} \def\hso{{\hspace{1pt}}}

10/7/2022
Halo2 Circuits

Groth16 Uses R1CS Arithmetization R1CS encodes an arithmetic computation (addition and multiplication). $\text{Public Inputs: } (1, x_1, \dots, x_m)$ $\text{Private Inputs: } (x_{m + 1}, \dots, x_n)$ $\text{Constraints: }(A_1B_1 = C_1, \dots, A_kB_k = C_k)$ Variables $x_i$ are stored in two vectors (public and private). A constraint is a degree-1 or degree-2 polynomial equation: $\text{polynomial}_A * \text{polynomial}_B = \text{polynomial}_C$

10/7/2022
Circuit-Efficient Labeling

During sealing, we perform a labeling function for each node in each layer (sha256 of a 20-block preimage). let label = sha256([ replica_id, // 0.5 blocks layer_index, // 0.25 blocks node, // 0.25 blocks parent_1_label, // 0.5 blocks ..., parent_37_label, // 0.5 blocks ]);

9/10/2022
Read more from Jake
Published on HackMD