Abstract

At the core of the fastest known SNARKs is the sum-check protocol. In this paper, we describe two complementary optimizations that significantly accelerate sum-check proving in key applications.

Abstract

Introducing zkDL++, a novel framework designed for provable AI. Leveraging zkDL++, we address a key challenge in generative AI watermarking—maintaining privacy while ensuring provability. By enhancing the watermarking system developed by Meta, zkDL++ solves the problem of needing to keep watermark extractors private to avoid attacks, offering a more secure solution. Beyond watermarking...

Abstract

Integrating implementation of pairing functions into the Icicle fancy cryptography library. This paper explains the implementation in detail, together with a review of the theory of pairing functions.

Abstract

In this chapter, we explore sum-check protocols from the point of view of parallelizable computation in devices such as GPUs. We explore algorithmic modifications to the sum-check protocol, for products of Multi-Linear Extensions (MLE) to improve parallel compute and address memory bottlenecks.

Abstract

Introducing Polar Bear and Teddy Bear: two novel small primes for cryptographic use, that are NTT- and hardware- friendly, and enjoy fast modular reduction.

Abstract

Reed-Solomon (RS) codes [RS60], representing evaluations of univariate polynomials over distinct domains, are foundational in error correction and cryptographic protocols. Traditional RS codes leverage the Fourier domain for efficient encoding and decoding via Fast Fourier Transforms (FFT). However, in fields such as the Reals and some finite prime fields, limited root-of-unity orders restrict these methods. Recent research, particularly in the context of modern STARKs...

Abstract

This note aims to provide a comprehensive yet concise introduction and tutorial on the efficient implementation of field and polynomial arithmetic within the M31 field, specifically in the context of Circle STARKs [UH24]. By addressing both the advantages and challenges associated with this field choice, the note seeks to equip practitioners with the knowledge necessary to optimize their cryptographic systems effectively.

Abstract

This document provides a comprehensive exploration of Number Theoretic Transform (NTT) hardware design, emphasizing both theoretical foundations and practical implementation. It begins with an in-depth discussion of Fourier transforms, their discrete variants, and the transition into NTT over finite fields, including applications such as Groth16 in zero-knowledge proofs.

Abstract

Danksharding is the new sharding design proposed for the Ethereum 2.0 blockchain, which introduces significant simplifications compared to previous designs. This report provides...

Abstract

In this work we present our research on applications of graph methods to parallelize the quotient polynomial in the Halo2 Zero Knowledge Proof (ZKP) system. The evaluation of the quotient polynomial has a complex data-interdependency which makes it a serious compute and memory bottleneck in halo2 applications. We achieve partitioning of quotient polynomial evaluation for large circuits, into groups...

Abstract

A theoretical deep dive into the Marlin protocol. This note takes the reader in a walkthrough of the R1CS construction, Algebraic Holographic proof, and univariate sumcheck used in the protocol.

Abstract

Presenting a detailed analysis of the RISC0 prover and its compatibility for hardware acceleration using either GPU or FPGA.

Abstract

Lookup arguments are a strong tool in the field of Zero-Knowledge Proofs, that allows to extend ZKP capabilities to non-arithmetic constraints. We present here an overview of uses for Lookup arguments, as well as a comparative history of Lookup protocols, from Plookup (2017) to cq (2022)

Abstract

The Barrett-Domb modular multiplication is a low-complexity, hardware-friendly modular multiplication algorithm based on the novel Barrett modular reduction scheme. In this work, we introduce a multi-precision, GPU/CPU friendly, version of the Barrett- Domb algorithm. We show that our scheme is competitive with the widely used Mont- gomery modular multiplication, potentially retiring the need for the cumbersome Mont- gomery conversions.

Abstract

Polynomial arithmetic is at the heart of modern Zero Knowledge Proving (ZKP) systems. The Number Theoretic Transform (NTT) is a crucial tool in facilitating efficient computational complexity over large polynomials encountered in ZKPs. NTTs are dominated by the number of field multiplications. In this short note we focus on the specific case of NTT in the 64 bit Goldilocks field. Following the observation that 2^48...

Abstract

We report on the Winograd-based implementation for the Number Theoretical Transform. It uses less multiplications than the better-known Cooley-Tuckey alternative. This optimization is important for very high order finite-fields. Unfortunately, the Winograd scheme is difficult to gen- eralize for arbitrary sizes and is only known for small-size transforms. We open-source our hardware implementation for size 32 based on [1].

Abstract

In this article we present a systematization of knowledge (SoK) on the usage of hash functions in Zero Knowledge Proofs (ZKP’s). Since ZKP’s operate on finite fields, traditional time-tested hash functions like SHA256 are unsuitable due to overhead in proving and verification of large number of bitwise operations. ZK-friendly hash functions are optimized for modular arithmetic in a finite field which reduces the circuit complexity...

Abstract

Modular multiplication is arguably the most computationally-dominant arithmetic primitive in any cryptographic system. This note presents an efficient, hardware- friendly algorithm that, to the best of the author’s knowledge, outperforms existing algorithms to date.