In this note we provide the hardware perspective on HyperPlonk. 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. 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. 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
12/28/2022or: 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/2021In 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/2021or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up