# Hardware-friendliness of HyperPlonk In this note we provide the hardware perspective on [HyperPlonk](https://eprint.iacr.org/2022/1355.pdf). We focus on the main building block, the Multivariate SumCheck protocol and compare its computational and memory complexity to that of an NTT (Number Theoretic Transform). ## Background - HyperPlonk Plonk is one of the most widely adopted SNARKs in the industry. In vanilla Plonk after arithmetization, the resulting execution trace is interpolated into univariate polynomials and thus the resulting protocol relies heavily on NTTs. HyperPlonk is a new adaptation of Plonk, where the execution trace is interpolated on a boolean hypercube. Thus the polynomial representation of the trace is a multivariate polynomial with linear degree in each variable. This is known as an MLE (MultiLinear Extension). A good overview of Hyperplonk can be found in Benedikt Bunz [ZKSummit8 talk](https://www.youtube.com/watch?v=2JDBD5oMS0w&t=279s). One key advantage of HyperPlonk is the elimination of large NTTs, a major computational bottleneck in Plonk over large-circuits. By moving to the boolean hypercube, we no longer need univariate polynomials. Instead, HyperPlonk relies on multivariate polynomial arithemetic. Section 3 in the Hyperplonk paper is devoted to developing the toolbox for working with multivariate polynomials. The figure below, taken from the paper, shows how HyperPlonk is built out of this toolbox. As can be seen, at the root of it all we have the classical SumCheck protocol, which is bound to become the main computational problem in HyperPlonk (polynomial commitments aside), replacing NTTs all together. ![](https://i.imgur.com/GusntWV.png) ## Sumcheck in HyperPlonk ### A toy example Consider an execution trace unrolled in the form of a vector. We illustrate the general idea using a vector of length $8$, constituted of the polynomial evaluations $\left\{ f_{i}\right\} _{i=0}^{7}$, where $f_i\in \mathbb{F}$. We interpolate these values using a multivariate polynomial $F(X_3,X_2,X_1)$ as follows <font size="2"> | $f_{0}$ | $f_{1}$ | $f_{2}$ | $f_{3}$ | $f_{4}$ | $f_{5}$ | $f_{6}$ | $f_{7}$ | | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | ---------- | | $F(0,0,0)$ | $F(0,0,1)$ | $F(0,1,0)$ | $F(0,1,1)$ | $F(1,0,0)$ | $F(1,0,1)$ | $F(1,1,0)$ | $F(1,1,1)$ | </font> <font size="3"> The elements in the first row are finite field elements, and the second row represents the interpolation idea. We interpolate the values using the Lagrange interpolation \begin{align} F(X_3,X_2,X_1) = & f_0 (1-X_3) (1-X_2) (1-X_1) + f_1 (1-X_3)(1-X_2) X_1\\ & + f_2 (1-X_3) X_2 (1-X_1) + f_3 (1-X_3) X_2 X_1) \\ & + f_4 X_3 (1-X_2) (1-X_1) + f_5 X_3 (1-X_2) X_1 \\ & + f_6 X_3 X_2 (1-X_1) + f_7 X_3 X_2 X_1 \end{align} where $X$ and $1-X$ are Lagrange base polynomials defined in a binary field. This unique polynomial $F(X_3,X_2,X_1)$ is known as the MultiLinear Extension of a vector. Let the sumcheck problem in this case be defined as follows \begin{equation} \sum_{X_i\in \{0,1\}} F(X_3,X_2,X_1) \stackrel{?}{=} C \end{equation} where $C\in \mathbb{F}$. The protocol proceeds with the following steps, where in each round the prover computes and commits to a univariate polynomial (Linear), and recieves a challenge from the verifier. </font> | Round | Prover $\mathcal{P}$ | Communication | Verifier $\mathcal{V}$ | |:-----:| ---------------------------------------------------- |:-------------------------------------------------------------- |:-------------------------------------------------------------------------------------------------------------------- | | 1 | $r_1(X) := \sum_{X_{2,3}\in \{0,1\}} F(X_3, X_2,X)$ | $r_1(X)\longrightarrow\\\longleftarrow \alpha_1\in \mathbb{F}$ | $C\stackrel{?}{=} \sum_{X\in\{0,1\}} r_1(X)$ | | 2 | $r_2(X) := \sum_{X_3\in \{0,1\}} F(X_3, X,\alpha_1)$ | $r_2(X)\longrightarrow\\\longleftarrow \alpha_2\in \mathbb{F}$ | $r_1(\alpha_1)\stackrel{?}{=} \sum_{X\in\{0,1\}} r_2(X)$ | | 3 | $r_3(X) := F(X, \alpha_2,\alpha_1)$ | $r_3(X)\longrightarrow$ | $r_2(\alpha_2)\stackrel{?}{=} \sum_{X\in\{0,1\}} r_3(X)\\r_3(\alpha_3)\stackrel{?}{=} F(\alpha_3,\alpha_2,\alpha_1)$ | What we would like to estimate is the complexity of the prover in the evaluation of the polynomials in each round. The commitment of each of the linear univariate polynomials by the prover is not a computational bottleneck, since it is a simple EC addition or a small MSM. After a short calculation we find that the structure of the polynomial at the end of round 1 is \begin{align} r_1(X) &= \sum_{X_i\in\{0,1 \}} F(X_2,X_2,X) =\sum_{i=0}^3 r_1^{(i)}(X)\\ r_1^{(i)}(X) &= f_{2i} (1-X) + f_{2i+1} X \end{align} It is obvious that \begin{equation} \sum_{X\in \{0,1\}} r_1(X) = r_1(0) +r_1(1) = \sum_{i=0}^3 (f_{2i} + f_{2i+1}) = C \end{equation} Let the challenge at the end of round 1 be $\alpha_1 \in\mathbb{F}_p$. Then the polynomial in round 2 can be written as \begin{align} r_2(X) & = \sum_{X_i\in\{0,1 \}} F(X_2,X,\alpha_1)= \sum_{i=0}^1 r_2^{(i)}(X)\\ r_2^{(i)}(X) &=r_1^{(2i)}(\alpha_1) (1-X) + r_1^{(2i+1)}(\alpha_1) X \end{align} Similarly let the challenge at the end of round 2 be $\alpha_2 \in\mathbb{F}_p$. Then the polynomial in round 3 can be written as \begin{align} r_3(X) & = F(X,\alpha_2,\alpha_1)\\ &= r_2^{(0)}(\alpha_2) (1-X) + r_2^{(1)}(\alpha_2) X \end{align} The prover algorithm in this case is presented graphically in the following figure ![](https://i.imgur.com/kKkEsH0.png) And the prover complexity is summarized in the following table (The notation $x \mathbb{F}$ refers to $x$ finite field elements in memory) | Round | Action | Memory | Mult | Add | | ----- | ------------------------------------------------------------------------------------------------------- | ------------- | ---- | --- | | pre | Store $f_i$, $\forall i=0,1,\ldots ,7$ | $8\mathbb{F}$ | - | - | | 1 | Read $f_i$ ,$\forall i=0,1,\ldots ,7$ <br /> commit $r_1(X)$ and receive $\alpha_1$ | | | | | | Read $f_i$, $\forall i=0,1,\ldots ,7$ <br /> compute $r_1^{(i)}(\alpha_1)$ , $\forall i=0,1,2,3$ | - | $8$ | $4$ | | | Clear $f_i$ ,$\forall i=0,1,\ldots ,7$ <br /> store $r_1^{(i)}(\alpha_1)$ , $\forall i=0,1,2,3$ | $4\mathbb{F}$ | - | - | | 2 | Read $r_1^{(i)}(\alpha_1)$ ,$\forall i=0,1,2,3$ <br /> commit $r_2(X)$ and receive $\alpha_2$ | | | | | | Read $r_1^{(i)}(\alpha_1)$, $\forall i=0,1,2,3$ <br /> compute $r_2^{(i)}(\alpha_2)$ , $\forall i=0,1$ | - | $4$ | $2$ | | | Clear $r_1^{(i)}(\alpha_1)$ ,$\forall i=0,1,2,3$ <br /> store $r_2^{(i)}(\alpha_2)$ , $\forall i=0,1$ | $2\mathbb{F}$ | - | - | | 3 | Read $r_2^{(i)}(\alpha_2)$ ,$\forall i=0,1$ <br /> commit $r_3(X)$ | | | | | | Clear $r_2^{(i)}(\alpha_2)$ ,$\forall i=0,1$ | | | | ### General form The general form of the algorithm is easily extrapolated from this simple example. We consider an execution trace of size $T=2^n$ (for simplicity we assume that the trace is always zero padded to a power of 2). This trace can be interpolated using a multivariate polynomial $F(X_n,\ldots,X_1)$. The prover algorithm is then as follows: * In round 1 the prover computes the linear polynomials \begin{align} r_1^{(i)}(X) = & (1-X) f_{2i} + X f_{2i+1},\ \forall i=0,\ldots,T/2-1\\ \end{align} and commits their sum \begin{align} r_1(X) = & \sum_{i=0}^{T/2-1} r_1^{(i)}(X) = \sum_{X_i\in\{0,1\}} F(X_n,\ldots ,X_{2}, X) \end{align} the prover then receives the challenge $\alpha_1$ from the verifier. * In the $k$-th round the prover computes the linear polynomials \begin{align} r_k^{(i)}(X) = & (1-X) r^{(2i)}_{k-1}(\alpha_{k-1}) + X r^{(2i+1)}_{k-1}(\alpha_{k-1}),\ \forall i=0,\ldots,T/2^k-1\\ \end{align} and commits their sum \begin{align} r_k(X) = & \sum_{i=0}^{T/2^k-1} r_k^{(i)}(X) = \sum_{X_i\in\{0,1\}} F(X_n,\ldots ,X_{k+1}, X,\alpha_{k-1},\dots,\alpha_1) \end{align} the prover then receives the challenge $\alpha_k$ from the verifier. * In the final $n$-th round the prover computes and commits the linear polynomial \begin{equation} r_{n}(X) = (1-X)r_{n-1}^{(0)}(\alpha_{n-1}) + X r_{n-1}^{(1)}(\alpha_{n-1}) \end{equation} The overall prover complexity is thus $2T-4$ multiplications and $T-2$ additions, along with a memory requirement of $T$ field elements. In fact, one can do somewhat better by noting that \begin{align} r_k^{(i)}(X) = & (1-X) r^{(2i)}_{k-1}(\alpha_{k-1}) + X r^{(2i+1)}_{k-1}(\alpha_{k-1})\\ = & r^{(2i)}_{k-1}(\alpha_{k-1}) + X(r^{(2i+1)}_{k-1}(\alpha_{k-1}) - r^{(2i)}_{k-1}(\alpha_{k-1})) \end{align} Which halves the number of required multiplications. ## Enter Fiat-Shamir The Fiat-Shamir transformation takes an interactive public coin proof such as the sumcheck protocol, and converts it into a non-interactive proof. Instead of having the challenges $\alpha_i$ be sent by the verifier, the transformation produces them at each round by computing a hash function of the previous transcript of the protocol. The transcript for which each hash function is calculated must include all of the verifiable results from the previous round, to avoid security vulnerabilities. An analysis of these vulnerablities is presented [here](https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/) and in much more technical detail [here](https://eprint.iacr.org/2016/771.pdf). As a consequence, each round in the sumcheck protocol must be performed sequentially, with no parallelization of the calculations between rounds. As is shown below, this fact seriously reduces the ability to parallelize computations in HyperPlonk. ## SumCheck in Hardware Based on the above presentation of non-interactive SumCheck, we can identify the following pattern for each round $i$: - Read $2^i$ elements from memory - Compute $a_i = hash(transcript)$ - Compute new $2^{i-1}$ elements - Write $2^{i-1}$ elements to memory Concretely, say we have $2^{30}$ field elements. In order to progress to the next round with $2^{29}$ elements, we must use (read from memory) all the $2^{30}$ elements. We cannot proceed to the next round, with $2^{28}$ elements, until we complete the round with the $2^{29}$ elements. This *hard stop* means we need to return to the memory in each round. So for example, for size $2^{30}$ we must read and write from/to the memory 30 times. For small enough sizes, say $2^{18}$ this memory can be SRAM, which is fast and unlikely to form bottlenecks. However, for large SumCheck sizes, e.g. $2^{30}$, which is what we expect to encounter in practice, there will be rounds that must work with the DRAM, i.e. DDR or HBM, which is slow and will become the bottleneck instead of the SumCheck computation. The figure below illustrates the data flow for this SumCheck. ![](https://i.imgur.com/R1zYuiQ.png) Memory bottleneck such as the one we just described is what we usually want to avoid when designing hardware accelerators - simply because there is not much we can do to accelerate these types of computations. By its nature, the vanilla SumCheck round-structure is extremely serial, and therefore there is not much room for acceleration. ### NTT in Hardware The obvious comparison here is to how NTT is handled in hardware. In this note we will not discuss NTT at the same level of depth we discussed the SumCheck. For the sake of comparison, we provide the following diagram: ![](https://i.imgur.com/ByNZJhA.png) NTT holds a good degree of parallelism such that multiple rounds can happen without returning to memory. Observe that for NTT we do not have a *hard stop* due to Fiat-Shamir - the output of one computation (partial result of a round) can immediately feed the input to a second computation (partial input of the next round). As a rule of thumb: We can compute a full NTT of size $1k$ elements with just one access to memory. This is $10$x better than SumCheck! As an example - we can solve an NTT of size $1$ trillion with only $3$ round trips to memory, in this case reading and writing all elements. This makes NTT computationally bottlenecked, and not memory bottlenecked. In fact, our implementations of NTT in GPUs and FPGAs managed to accelerate the NTT computation so much that for all relevant sizes even the compute is no longer a bottleneck! The next bottleneck in line, faced by these implementations is the PCIe bandwidth, used for communication with the host. ## Conclusions After all - are we better off with Plonk and NTT rather than with HyperPlonk and MLE-SumCheck? At least from the hardware point of view, NTT, while obviously not significantly parallel, is still way more hardware friendly than the MLE-SumCheck. We note that the same structure is found in FRI, for example, check out plonky2 FRI [implementation](https://github.com/mir-protocol/plonky2/blob/769175808448cecc7b431d7293e2d689af635a4b/plonky2/src/fri/prover.rs#L69). We assume that the problem with hardware acceleration of FRI was not raised before because FRIs in existing systems such as STARKs take only a small fraction of the overall computation, especially compared to the many, and much larger NTTs. ### Take this note with a grain of salt! We focused here only on the "vanilla" SumCheck and its structure and did not address the solution space at all. The hardware acceleration of SumCheck is an understudied problem, especially compared to an NTT. It is likely that the techniques to improve the hardware-friendliness of the SumCheck exist or will be invented in the future: ranging from cryptography (Fiat-Shamir plays a role here), through new variants of SumCheck, and to ideas enabling parallelism in higher levels of the protocol design (some of them presented in the HyperPlonk paper, such as Batching). **Departing thought:** Have we reached a point where ZK protocols must be co-designed with hardware in mind? *Thanks to Tomer, Kobi, Suyash, Miki, Karthik, Oren and Yuval*
Last changed by  
 
Omer Shlomovits
3799

Read more

Identity is the Key

or: what I learned from working on decentralized identity and some future research directions Intro I have worked in ZenGo, a crypto wallet company, for several years. My role was to explore and expand the boundaries of key management for wallets, that is, the custody, safe usage, and applications of permissionless, ledger-based, crypto-currencies. Recently, I started looking at the design principles of a somewhat related kind of system for self-sovereign identity, or as I will refer to it in this blog - decentralized identity (DID). My initial instinct was to apply the familiar frameworks of crypto wallets, yet quickly I realized that there is much more to DID systems: despite similarities at the key management level, there are in addition many unique features to DID. In this write-up, I will try to account for my humble journey going from a crypto wallet to a DID system, while uncovering some new, at least for me, research questions in DID. The Rabbit Hole In September 2021 I was supposed to present my work on DID recovery using a timestamping service in the Future of Personal Identification workshop (FoPI). The paper was accepted after shepherding and later I withdrew it. Why?

12/23/2021
"Alpha-Rays" behind the scenes

In a recently published paper, we describe two attacks on threshold ECDSA implementations. The uniqueness of the attacks is that they are rooted in issues found in the protocol itself. We hereby describe the events that surrounded the discovery, handling, and patching of the impacted code. Intro March 1, 2018. Ariel Gabizon, a cryptographer employed by the Zcash Company at the time, discovered a subtle cryptographic flaw in the BCTV14 paper that describes the zk-SNARK construction used in the original launch of Zcash. This vulnerability is so subtle that it evaded years of analysis by expert cryptographers focused on zero-knowledge proving systems and zk-SNARK. The vulnerability could have allowed for infinite counterfeiting. October 1, 2021. GG18, a paper published in CCS 2018, described a protocol for t out of n threshold ECDSA. This protocol, together with a follow-up work by the same authors, GG20, became a popular choice for implementation by many custody operators and protocols, securing equivalent of billions worth of USD. Moreover, cited more than 100 times and considered the first practical multiparty ECDSA protocol, GG18 is a cornerstone in the evolution of threshold ECDSA protocols. As a result, the paper has gone through intensive peer review and multiple independent audits, receiving the attention that only a select few papers, that ever crossed from academy to industry, get. While implementation bugs, some critical, had been found in the wild, GG18 construction remained flawless. Until now. What we have found

12/18/2021
FS-DKR: One Round Distributed Key Rotation

Intro In this note we aim to re-purpose the Fouque-Stern Distributed Key Generation (DKG) to support a secure Distributed Key Refresh (DKR). As we claim, FS-DKR is well suited for rotation of threshold ECDSA keys. Background The FS-DKG protocol is a one round DKG based on Publicly Verifiable Secret Sharing (PVSS) and the Paillier cryptosystem. There are two major security shortcomings to FS-DKG: It introduces a factoring assumptions (DCRA) it is insecure against rushing adversary Rushing adversary is a common assumption in Multiparty Computation (MPC). In FS-DKG, an adversary waiting to receive messages from all other parties will be able to decide on the final public key. In the worst case it can lead to a rouge-key attack, giving full control of the secret key to the attacker. This is the main reason, in our opinion, why FS-DKG, altough with prominent features, was over-looked for the past 20 years.

8/29/2021
Read more from Omer Shlomovits
Published on HackMD