Lightnews — Scholar-powered news

ePrint Updates

@eprint.ing.bot

Dynark: Making Groth16 Dynamic (Tianyu Zhang, Yupeng Ouyang, Yupeng Zhang) ia.cr/2025/1897

$Abstract. In recent years, numerous new and more efficient constructions of zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) have been proposed, motivated by their growing practical applications. However, in most schemes, when the witness is changed, the prover has to recompute the proof from scratch even if the new witness is close to the old one. This is inefficient for applications where proofs are generated for dynamically changing witnesses with small changes. In this paper, we introduce DYNARK, a dynamic zkSNARK scheme that can update the proof in sublinear time when the change of the witness is small. DYNARK is built on top of the seminal zkSNARK protocol of Groth, 2016. In the semi-dynamic setting, for an R1CS of size n, after a preprocessing of O(nlog n) group operations on the original witness, it only takes O(d) group operations and O(dlog²d) field operations to update the proof for a new witness with distance d from the original witness, which is nearly optimal. In the fully-dynamic setting, the update time of DYNARK is $O(d\sqrt{n\log n})$ group operations and O(dlog²d) field operations. Both the proof size and the verifier time are O(1), which are exactly the same as Groth16. Compared to the scheme in a prior work by Wang et al. 2024, we reduce the proof size from $O(\sqrt{n})$ to O(1) without relying on pairing product arguments or another zkSNARK, and the update time and the verifier time of DYNARK are faster in practice. Experimental results show that for n = 2²⁰, after a one-time preprocessing of 74.3 seconds, it merely takes 3 milliseconds to update the proof in our semi-dynamic zkSNARK for d = 1, and 60 milliseconds to update the proof in our fully-dynamic zkSNARK. These are 1433× and 73× faster than Groth16, respectively. The proof size is 192 bytes and the verifier time is 4.4 milliseconds. The system is fully compatible with any existing deployment of Groth16 without changing the trusted setup, the proof and the verification algorithm.$ Image showing part 2 of abstract.

October 12, 2025 at 9:35 PM Everybody can reply

ePrint Updates

@eprint.ing.bot

Lattice-Based zk-SNARKs with Hybrid Verification Technique (Supriya Adhikary, Puja Mondal, Angshuman Karmakar) ia.cr/2025/1839

Abstract. Zero-knowledge succinct arguments of knowledge (zkSNARK) provide short privacy-preserving proofs for general NP problems. Public verifiability of zkSNARK protocols is a desirable property, where the proof can be verified by anyone once generated. Designated-verifier zero-knowledge is useful when it is necessary that only one or a few individuals should have access to the verification result. All zkSNARK schemes are either fully publicly verifiable or can be verified by a designated verifier with a secret verification key.

In this work, we propose a new notion of a hybrid verification mechanism. Here, the prover generates a proof that can be verified by a designated verifier. For this proof, the designated verifier can generate auxiliary information with its secret key. The combination of this proof and the auxiliary information allows any public verifier to verify the proof without any other information. We also introduce necessary security notions and mechanisms to identify a cheating designated verifier or the prover. Our hybrid verification zkSNARK construction is based on module lattices and adapts the zkSNARK construction by Ishai et al. (CCS 2021). In this construction, the designated verifier is required only once after proof generation to create the publicly verifiable proof. Our construction achieves a small constant-size proof and fast verification time, which is linear in the statement size.

October 8, 2025 at 3:36 AM Everybody can reply

ePrint Updates

@eprint.ing.bot

Zyga: Optimized Zero-Knowledge Proofs with Dynamic Public Inputs (Tiiago A. O. Alves, Vitor Py Braga) ia.cr/2025/1802

Abstract. We present Zyga, a pairing-based zero-knowledge proof system optimized for privacy-preserving DeFi applications. Our main contribution is an enhancement of existing zkSNARK constructions that enables dynamic public input substitution during verification while maintaining privacy of witness components through one-sided encoding. The one-sided encoding aspect favors practical deployment constraints on Solana where G2 scalar multiplications are computationally expensive. Zyga separates private values (blinded through trusted setup) from public values (instantiated on-chain), enabling applications like private trading against current market rates without reproofing. We provide rigorous security analysis under discrete logarithm and q-Strong Diffie-Hellman assumptions, demonstrating computational soundness, zero-knowledge, and completeness. Performance analysis shows verification requires only 3 pairings with constant proof size, making it practical for blockchain deployment where transaction costs are critical.

October 8, 2025 at 3:02 AM Everybody can reply

ePrint Updates

@eprint.ing.bot

DualMatrix: Conquering zkSNARK for Large Matrix Multiplication (Mingshu Cong, Tsz Hon Yuen, Siu-Ming Yiu) ia.cr/2025/1768

Abstract. We present DualMatrix, a zkSNARK solution for large-scale matrix multiplication. Classical zkSNARK protocols typically underperform in data analytic contexts, hampered by the large size of datasets and the superlinear nature of matrix multiplication. DualMatrix excels in its scalability. The prover time of DualMatrix scales linearly with respect to the number of non-zero elements in the input matrices. For n × n matrix multiplication with N non-zero elements across three input matrices, DualMatrix employs a structured reference string (SRS) of size O(n), and achieves RAM usage of O(N + n), transcript size of O(log n), prover time of O(N + n), and verifier time of O(log n). The prover time, notably at O(N + n) and surpassing all existing protocols, includes O(N + n) field multiplications and O(n) exponentiations and pairings within bilinear groups. These efficiencies make DualMatrix effective for linear algebra on large matrices common in real-world applications. We evaluated DualMatrix with 2¹⁵ × 2¹⁵ input matrices each containing 1G non-zero integers, which necessitate 32T integer multiplications in naive matrix multiplication. DualMatrix recorded prover and verifier times of 150.84s and 0.56s, respectively. When applied to 1M × 1M sparse matrices each containing 1G non-zero integers, it demonstrated prover and verifier times of 1, 384.45s and 0.67s. Our approach outperforms current zkSNARK solutions by successfully handling the large matrix multiplication task in experiment. We extend matrix operations from field matrices to group matrices, formalizing group matrix algebra. This mathematical advancement brings notable symmetries beneficial for high-dimensional elliptic curve cryptography. By leveraging the bilinear properties of our group matrix algebra in the context of the two-tier commitment scheme, DualMatrix achieves efficiency gains over previous matrix multiplication arguments. To accomplish this, we extend and enhance Bulletproofs to construct an inner product argument featuring a transparent setup and logarithmic verifier time.

September 30, 2025 at 2:49 AM Everybody can reply

ePrint Updates

@eprint.ing.bot

LastRings: Lattice-based Scalable Threshold Ring Signatures (Sohyun Jeon, Calvin Abou Haidar, Mehdi Tibouchi) ia.cr/2025/1633

Abstract. In this paper, we construct the first lattice-based threshold ring signature scheme with signature size scaling logarithmically in the size of the ring while supporting arbitrary thresholds. Our construction is also concretely efficient, achieving signature sizes of less than 150kB for ring sizes up to N = 4096 (with threshold size T = N/2, say). This is substantially more compact than previous work.

Our approach is inspired by the recent work of Aardal et al. (CRYPTO 2024) on the compact aggregation of Falcon signatures, that uses the LaBRADOR lattice-based SNARKs to combine a collection of Falcon signatures into a single succinct argument of knowledge of those signatures. We proceed in a similar way to obtain compact threshold ring signatures from , but crucially require that the proof system be zero-knowledge in order to ensure the privacy of signers. Since LaBRADOR is not a zkSNARK, we associate it with a separate (non-succinct) lattice-based zero-knowledge proof system to achieve our desired properties.

September 12, 2025 at 2:20 PM Everybody can reply

1 likes

1

javkrypto.bsky.social

@javkrypto.bsky.social

DAILY NEWS from the ##ETH KOSMOS: (1)

📰 𝗛𝗲𝗮𝗱𝗹𝗶𝗻𝗲𝘀

Boundless’ The Signal Expands to Base
##Boundless announced that The Signal, its decentralized zk proving network, is now expanding to Base, after previously only operating on Ethereum mainnet. The Signal provides distributed zkSNARK provin

September 5, 2025 at 11:12 AM Everybody can reply

1

GAGE

@g-age.bsky.social

Replaces: PL/SQL stored procedures

Bonus: zkSNARK-compatible for financial compliance

August 6, 2025 at 4:34 PM Everybody can reply

Samm💫

@sababa.bsky.social

#SheFi playlist today during break. Fabulous class today #ZKProof #ZKSnark with Midnight Network.

August 6, 2025 at 12:42 AM Everybody can reply

3 likes

3

ePrint Updates

@eprint.ing.bot

Collaborative zkSNARKs with Sublinear Prover Time and Constant Proof Size (Zhiyong Fang, Sanjam Garg, Bhaskar Roberts, Wenxuan Wu, Yupeng Zhang) ia.cr/2025/1388

$Abstract. Collaborative zkSNARKs, proposed by Ozdemir and Boneh in 2022, allow a prover to delegate the generation of zkSNARK proofs to multiple servers, without compromising the confidentiality of the secret witness. They enable the use of zkSNARK techniques on computational limited devices in critical applications such as blockchains. However, the running time of each server is at least as slow as computing the proof on a single server. Garg et al. attempted to improve the efficiency in their scheme named zkSaaS using packed secret sharing, but the scheme still requires a powerful central server with linear computation, communication and memory usage. In this paper, we propose a new collaborative zkSNARK scheme with $O(\frac{C}{n}\log\frac{C}{n})$ prover time and O(1) proof size with n servers for a circuit of size C. An adversary compromising less than $\frac{n}{4}$ servers cannot learn any information about the witness. The core of our technique lies in a new zkSNARK scheme for the Plonkish constraint system that is friendly to packed secret sharing. We utilize bivariate polynomials to avoid a large Fast Fourier Transform on the entire witness, which was the major bottleneck in prior work. We also construct permutation constraints based on logarithmic derivatives and univariate sumcheck to avoid the computation of prefix products. Finally, we build a bivariate polynomial commitment scheme that can be computed directly on packed secret shares. Experimental results show that for a circuit of size 2²⁰, with 128 servers, our scheme can accelerate the proof generation by 36.2× compared to running the zkSNARK on a single server. The prover time of our system is 25.9× faster than the prior work of zkSaaS. The proof size of our scheme is only 960 Bytes.$ Image showing part 2 of abstract.

July 31, 2025 at 2:23 PM Everybody can reply

Max Scherzer Consolation Prize Simulator 2025

@metamora.bsky.social

I'm sitting here bleary-eyed meticulously vibe-coding zkSNARK circuits on ramen noodles and bottles of Shasta while people are making millions of dollars leaving hundreds of gigs of PII in public buckets

the future is bright but goddamn is the intermediary period grim

July 26, 2025 at 1:54 AM Everybody can reply

3 likes

1 3

ePrint Updates

@eprint.ing.bot

Hobbit: Space-Efficient zkSNARK with Optimal Prover Time (Christodoulos Pappas, Dimitrios Papadopoulos) ia.cr/2025/1214

Abstract. Zero-knowledge succinct non-interactive arguments (zkSNARKs) are notorious for their large prover space requirements, which almost prohibits their use for really large instances. Space-efficient zkSNARKs aim to address this by limiting the prover space usage, without critical sacrifices to its runtime. In this work, we introduce Hobbit, the only existing space-efficient zkSNARK that achieves optimal prover time O(|C|) for an arithmetic circuit C. At the same time, Hobbit is the first transparent and plausibly post-quantum secure construction of its kind. Moreover, our experimental evaluation shows that Hobbit outperforms all prior general-purpose space-efficient zkSNARKs in the literature across four different applications (arbitrary arithmetic circuits, inference of pruned Multi-Layer Perceptron, batch AES128 evaluation, and select-and-aggregate SQL query) by $8−$56 in terms or prover time while requiring up to $$23 less total space.

At a technical level, we introduce two new building blocks that may be of independent interest: (i) the first sumcheck protocol for products of polynomials with optimal prover time in the streaming setting, and (ii) a novel multi-linear plausibly post-quantum polynomial commitment that outperforms all prior works in prover time (and can be tuned to work in a space-efficient manner). We build Hobbit by combining the above with a modified version of HyperPlonk, providing an explicit routine to stream access to the circuit evaluation.

July 7, 2025 at 2:33 AM Everybody can reply

1 likes

1

Cryptoforold

@cryptoforold.bsky.social

zk-SNARK is a unique kind of zero-knowledge proof that enables the verification of a statement without disclosing any details about the statement itself.
#cryptoforold #finance #crypto #zkSNARK
Read more at: cryptoforold.com/what-is-zk-s...

June 26, 2025 at 10:43 AM Everybody can reply

2 likes

2

xormetric

@tentacle.expert

zksnark attestation of a response from plc.directory that says so

did:plc Directory

plc.directory

May 31, 2025 at 11:54 PM Everybody can reply

2 likes

1 2

Poster | Crypto News

@cryptonews-poster.bsky.social

ZKsync proposes an upgrade to slash ZK proof verification costs by over 90%! Optimizing elliptic curve precompiles & adding ModExp slashes zkSNARK gas from ~6.8M to ~370k (~94% drop). Boosts crypto ops. Existing contracts work. Live on testnet.

#crypto #blockchain #news

May 20, 2025 at 2:44 PM Everybody can reply

2 likes

2

ePrint Updates

@eprint.ing.bot

HydraProofs: Optimally Computing All Proofs in a Vector Commitment (with applications to efficient zkSNARKs over data from multiple users) (Christodoulos Pappas, Dimitris Papadopoulos, Charalampos Papamanthou) ia.cr/2025/813

Abstract. In this work, we introduce HydraProofs, the first vector commitment (VC) scheme that achieves the following two properties. (i) The prover can produce all the opening proofs for different elements (or consecutive sub-arrays) for a vector of size N in optimal time O(N). (ii) It is directly compatible with a family of zkSNARKs that encode their input as a multi-linear polynomial, i.e., our VC can be directly used when running the zkSNARK on its pre-image, without the need to open” the entire vector pre-image inside the zkSNARK. To the best of our knowledge, all prior VC schemes either achieve (i) but are not efficiently pluggable” into zkSNARKs (e.g., a Merkle tree commitment that requires re-computing the entire hash tree inside the circuit), or achieve (ii) but take (NlogN) time. We then combine HydraProofs with the seminal GKR protocol and apply the resulting zkSNARK in a setting where multiple users participate in a computation executed by an untrusted server and each user wants to ensure the correctness of the result and that her data was included. Our experimental evaluation shows our approach outperforms prior ones by 4-16x for prover times on general circuits. Finally, we consider two concrete application use cases, verifiable secret sharing and verifiable robust aggregation. For the former, our construction achieves the first scheme for Shamir’s secret sharing with linear time prover (lower than the time needed for the dealer computation). For the second we propose a scheme that works against misbehaving aggregators and our experiments show it can be reasonably deployed in existing schemes with minimal slow-downs.

May 9, 2025 at 2:04 AM Everybody can reply

1 likes

1

Matthew Green

@matthewdgreen.bsky.social

(Maybe I should say: the most succinct thing out there. A lot of people are discussing using FRI or Sum-check proof systems, then recursively proving validity if the resulting arguments using a succinct pairing-based zkSNARK so they can post a short proof on a blockchain.)

April 24, 2025 at 1:24 PM Everybody can reply

1 likes

1

ePrint Updates

@eprint.ing.bot

Efficient Proofs of Possession for Legacy Signatures (Anna P. Y. Woo, Alex Ozdemir, Chad Sharp, Thomas Pornin, Paul Grubbs) ia.cr/2025/538

Abstract. Digital signatures underpin identity, authenticity, and trust in modern computer systems. Cryptography research has shown that it is possible to prove possession of a valid message and signature for some public key, without revealing the message or signature. These proofs of possession work only for specially-designed signature schemes. Though these proofs of possession have many useful applications to improving security, privacy, and anonymity, they are not currently usable for widely deployed, legacy signature schemes such as RSA, ECDSA, and Ed25519. Unlocking practical proofs of possession for these legacy signature schemes requires closing a huge efficiency gap.

This work brings proofs of possession for legacy signature schemes very close to practicality. Our design strategy is to encode the signature’s verification algorithm as a rank-one constraint system (R1CS), then use a zkSNARK to prove knowledge of a solution. To do this efficiently we (1) design and analyze a new zkSNARK called Dorian that supports randomized computations, (2) introduce several new techniques for encoding hashes, elliptic curve operations, and modular arithmetic, (3) give a new approach that allows performing the most expensive parts of ECDSA and Ed25519 verifications outside R1CS, and (4) generate a novel elliptic curve that allows expressing Ed25519 curve operations very efficiently. Our techniques reduce R1CS sizes by up to 200× and prover times by 3-22×.

We can generate a 240-byte proof of possession of an RSA signature over a message the size of a typical TLS certificate (two kilobytes) in only three seconds.

March 25, 2025 at 12:29 AM Everybody can reply

2 reposts 1 quotes 4 likes

2 4

ePrint Updates

@eprint.ing.bot

PMNS arithmetic for elliptic curve cryptography (Fangan Yssouf Dosso, Sylvain Duquesne, Nadia El Mrabet, Emma Gautier) ia.cr/2025/467

Abstract. We show that using a polynomial representation of prime field elements (PMNS) can be relevant for real-world cryptographic applications even in terms of performance. More specifically, we consider elliptic curves for cryptography when pseudo-Mersenne primes cannot be used to define the base field (e.g. Brainpool standardized curves, JubJub curves in the zkSNARK context, pairing-friendly curves). All these primitives make massive use of the Montgomery reduction algorithm and well-known libraries such as GMP or OpenSSL for base field arithmetic. We show how this arithmetic can be advantageously replaced by a polynomial representation of the number that can be easily parallelized, avoids carry propagation, and allows randomization process. We provide good PMNS basis in the cryptographic context mentioned above, together with a C-implementation that is competitive or faster than GMP and OpenSSL for performing basic operations in the base fields considered. We also integrate this arithmetic into the Rust reference implementation of elliptic curve scalar multiplication for Zero-knowledge applications, and achieve better practical performances for such protocols. This shows that PMNS is an attractive alternative for the base field arithmetic layer in cryptographic primitives using elliptic curves or pairings.

March 13, 2025 at 6:35 PM Everybody can reply

ePrint Updates

@eprint.ing.bot

Split Prover Zero-Knowledge SNARKs (Sanjam Garg, Aarushi Goel, Dimitris Kolonelos, Sina Shiehian, Rohit Sinha) ia.cr/2025/373

Abstract. We initiate the study of {}, which allow Alice to offload part of the zkSNARK computation to her assistant, Bob. In scenarios like online transactions (e.g., zCash), a significant portion of the witness (e.g., membership proofs of input coins) is often available to the prover (Alice) before the transaction begins. This setup offers an opportunity to Alice to initiate the proof computation early, even before the entire witness is available. The remaining computation can then be delegated to Bob, who can complete it once the final witness (e.g., the transaction amount) is known.

To prevent Bob from generating proofs independently (e.g., initiating unauthorized transactions), it is essential that the data provided to him for the second phase of computation does not reveal the witness used in the first phase. Additionally, the verifier of the zkSNARK should be unable to determine whether the proof was generated solely by Alice or through this two-step process. To achieve this efficiently, we require this two-phase proof generation to only use cryptography in a black-box manner.

We propose a split prover zkSNARK based on the Groth16 zkSNARKs [Groth, EUROCRYPT 2016], meeting all these requirements. Our solution is also , meaning it achieves the optimal second phase proof generation time for Groth16. Importantly, our split prover zkSNARK preserves the verification algorithm of the original Groth16 zkSNARK, enabling seamless integration into existing deployments of Groth16.

March 4, 2025 at 7:46 AM Everybody can reply

ePrint Updates

@eprint.ing.bot

DFS: Delegation-friendly zkSNARK and Private Delegation of Provers (Yuncong Hu, Pratyush Mishra, Xiao Wang, Jie Xie, Kang Yang, Yu Yu, Yuwen Zhang) ia.cr/2025/296

Abstract. Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zkSNARKs) lead to proofs that can be succinctly verified but require huge computational resources to generate. Prior systems outsource proof generation either through public delegation, which reveals the witness to the third party, or, more preferably, private delegation that keeps the witness hidden using multiparty computation (MPC). However, current private delegation schemes struggle with scalability and efficiency due to MPC inefficiencies, poor resource utilization, and suboptimal design of zkSNARK protocols.

In this paper, we introduce DFS, a new zkSNARK that is delegation-friendly for both public and private scenarios. Prior work focused on optimizing the MPC protocols for existing zkSNARKs, while DFS uses co-design between MPC and zkSNARK so that the protocol is efficient for both distributed computing and MPC. In particular, DFS achieves linear prover time and logarithmic verification cost in the non-delegated setting. For private delegation, DFS introduces a scheme with zero communication overhead in MPC and achieves malicious security for free, which results in logarithmic overall communication; while prior work required linear communication. Our evaluation shows that DFS is as efficient as state-of-the-art zkSNARKs in public delegation; when used for private delegation, it scales better than previous work. In particular, for 2²⁴ constraints, the total communication of DFS is less than 500KB, while prior work incurs 300GB, which is linear to the circuit size. Additionally, we identify and address a security flaw in prior work, EOS (USENIX’23).

February 20, 2025 at 9:16 PM Everybody can reply

2 reposts 1 likes

2 1

Patrick

@pck.rocks

Not really. See the start of zksnark stuff with ceremony etc etc. Ultimately down to meat space things.

November 20, 2024 at 7:00 PM Everybody can reply

3 likes

3

ePrint Updates

@eprint.ing.bot

Siniel: Distributed Privacy-Preserving zkSNARK (Yunbo Yang, Yuejia Cheng, Kailun Wang, Xiaoguo Li, Jianfei Sun, Jiachen Shen, Xiaolei Dong, Zhenfu Cao, Guomin Yang, Robert H. Deng) ia.cr/2024/1803

Abstract. Zero-knowledge Succinct Non-interactive Argument of Knowledge (zkSNARK) is a powerful cryptographic primitive, in which a prover convinces a verifier that a given statement is true without leaking any additional information. However, existing zkSNARKs suffer from high computation overhead in the proof generation. This limits the applications of zkSNARKs, such as private payments, private smart contracts, and anonymous credentials. Private delegation has become a prominent way to accelerate proof generation. In this work, we propose Siniel, an efficient private delegation framework for zkSNARKs constructed from polynomial interactive oracle proof (PIOP) and polynomial commitment scheme (PCS). Our protocol allows a computationally limited prover (a.k.a. delegator) to delegate its expensive prover computation to several workers without leaking any information about the private witness. Most importantly, compared with the recent work EOS (USENIX’23), the state-of-the-art zkSNARK prover delegation framework, a prover in Siniel needs not to engage in the MPC protocol after sending its shares of private witness. This means that a Siniel prover can outsource the entire computation to the workers. We compare Siniel with EOS and show significant performance advantages of the former. The experimental results show that, under low bandwidth conditions (10MBps), Siniel saves about 65% time for delegators than that of EOS, whereas under high bandwidth conditions (1000MBps), Siniel saves about 95% than EOS.

November 8, 2024 at 3:48 AM Everybody can reply

ePrint Updates

@eprint.ing.bot

Blind zkSNARKs for Private Proof Delegation and Verifiable Computation over Encrypted Data (Mariana Gama, Emad Heydari Beni, Jiayi Kang, Jannik Spiessens, Frederik Vercauteren) ia.cr/2024/1684

Abstract. In this paper, we show for the first time it is practical to privately delegate proof generation of zkSNARKs proving up to 2²⁰ R1CS constraints to a single server. We achieve this by homomorphically computing zkSNARK proof generation, an approach we call blind zkSNARKs. We formalize the concept of blind proofs, analyze their cryptographic properties and show that the resulting blind zkSNARKs remain sound when compiled using BCS compilation. Garg et al. gave a similar framework at CRYPTO 2024, but no practical instantiation for proving non-trivial computations was known. By delegating proof generation, we are able to reduce client computation time from 10 minutes to mere seconds, while server computation time remains limited to 20 minutes. We also propose a practical construction for vCOED supporting constraint sizes four orders of magnitude larger than the current state-of-the-art verifiable FHE-based approaches. These results are achieved by optimizing Fractal for the GBFV homomorphic encryption scheme, e.g. by designing specialized homomorphic circuits with two dimensional NTTs. Furthermore, we make the proofs publicly-verifiable by appending a zero-knowledge Proof of Decryption (PoD). We propose a new construction for PoDs, optimized for low proof generation time, exploiting modulus and ring switching in GBFV; these techniques might be of independent interest. Finally, we implement the latter protocol in C and report on execution time and proof sizes.

October 18, 2024 at 2:40 AM Everybody can reply

2 reposts 4 likes

2 4

ePrint Updates

@eprint.ing.bot

Sparrow: Space-Efficient zkSNARK for Data-Parallel Circuits and Applications to Zero-Knowledge Decision Trees (Christodoulos Pappas, Dimitrios Papadopoulos) ia.cr/2024/1631

Abstract. Space-efficient SNARKs aim to reduce the prover’s space overhead which is one the main obstacles for deploying SNARKs in practice, as it can be prohibitively large (e.g., orders of magnitude larger than natively performing the computation). In this work, we propose Sparrow, a novel space-efficient zero-knowledge SNARK for data-parallel arithmetic circuits with two attractive features: (i) it is the first space-efficient scheme where, for a given field, the prover overhead increases with a multiplicative sublogarithmic factor as the circuit size increases, and (ii) compared to prior space-efficient SNARKs that work for arbitrary arithmetic circuits, it achieves prover space asymptotically smaller than the circuit size itself. Our key building block is a novel space-efficient sumcheck argument with improved prover time which may be of independent interest. Our experimental results for three use cases (arbitrary data parallel circuits, multiplication trees, batch SHA256 hashing) indicate Sparrow outperforms the prior state-of-the-art space-efficient SNARK for arithmetic circuits Gemini (Bootle et al., EUROCRYPT’22) by 3.2-28.7× in total prover space and 3.1-11.3× in prover time. We then use Sparrow to build zero-knowledge proofs of tree training and prediction, relying on its space efficiency to scale to large datasets and forests of multiple trees. Compared to a (non-space-efficient) optimal-time SNARK based on the GKR protocol, we observe prover space reduction of 16-240× for tree training while maintaining essentially the same prover and verifier times and proof size. Even more interestingly, our prover requires comparable space to natively performing the underlying computation. E.g., for a 400MB dataset, our prover only needs 1.4× more space than the native computation.

October 14, 2024 at 2:09 AM Everybody can reply

1 likes

1

企業テックブログRSS

@tech-blog-rss-feed.bsky.social

zkSNARKのプロトコルではどのように公開入力をパラメータ化しているのか？ | HashPort技術ブログ

はじめに今回は小ネタです。zkSNARK（1など）の記事を読むと「回路を数式に落とし込んでいるんだな」ということは分かると思いますが、単純なアルゴリズムでは「予め決められた形式の回路に対して出力が1になる何らかの非公開入力（private

tech.hashport.io

October 4, 2024 at 8:08 PM Everybody can reply