Blockchain Papers

Irina Strelkovskaya, Oleksiy Onatskiy, Larysa Yona

No abstract is available for this record.

Agathe Beaugrand, Guilhem Castagnos, Fabien Laguillaumie

No abstract is available for this record.

Shi Wang

With the rapid development of the digital economy and the Internet of Things, identity authentication in resource-constrained environments faces challenges such as low efficiency and inadequate privacy protection. Addressing the high computational and communication overhead of traditional RSA and ECC authentication mechanisms, this study proposes an efficient identity authentication mechanism (AC-ZKP) based on algebraic curves and non-interactive zero-knowledge proofs (NIZK). This mechanism leverages algebraic curve group operations to achieve lightweight key management and employs zero-knowledge proofs to ensure information concealment and anti-forgery during identity verification. The paper conducts a systematic study across four dimensions: system modeling, algorithm design, security analysis, and performance evaluation. Experimental results demonstrate that while maintaining 128-bit security strength, the AC-ZKP mechanism reduces authentication latency by approximately 44% and communication overhead by about 40%. It also exhibits strong scalability and resistance to attacks, significantly outperforming traditional ECC schemes. These findings provide a viable solution for lightweight, high-security identity authentication in IoT, edge computing, and cross-border data exchange environments.

Cyprian Omukhwaya Sakwa, Andrew Omala Anyembe, Fagen Li

No abstract is available for this record.

Eshan Sud, Shirish Agarwal, Lav Upadhyay

Zero-Knowledge Proofs (ZKPs) are public key cryptosystem that enables to demonstrate that a statement which is known by them is correct without revealing the same to the verifier. ZKPs have moved in modern cryptographic systems, blockchain applications, decentralized finance (DeFi) and identity authentication systems. This paper explores the evolution of ZKPs and their significance as in secure and privacy preserving. We classify ZKPs into two groups namely interactive and non-interactive, discussing prominent protocols such as zk-SNARKs, zk-STARKs, Bulletproofs, PLONK, and Halo2. Each approach has advantages as efficiency, proof size, and computational overhead. The study further examines the multitude of applications of ZKPs, as privacy-enhanced blockchain transactions, zero-knowledge rollups for scalability, decentralized identity management, secure voting mechanisms, and regulatorycompliant financial systems. With advantages, possible limitations in scalability, lack of standardization, and vulnerabilities to emerging quantum computing threats. Due to the restrictions, hardware acceleration through GPUs and others, presents promising solutions, while new protocols such as PLONK and Halo2 seek to optimize performance to earlier developed solutions. Finally, we discuss the future trajectory of ZKPs. This review aims to provide an understanding of the current state of ZKP research, its applications, and the key challenges that need to be addressed to facilitate broader adoption.

Katharina Koschatko, Reinhard Lüftenegger, Christian Rechberger

Gröbner basis cryptanalysis of hash functions and ciphers, and their underlying permutations, has seen renewed interest recently. Anemoi (Crypto’23) is a permutation-based hash function that is efficient for a variety of arithmetizations used in zero-knowledge proofs. In this paper, exploring both theoretical bounds as well as experimental validation, we present new complexity estimates for Gröbner basis attacks on the Anemoi permutation over prime fields.We cast our findings in what we call the six worlds of Gröbner basis cryptanalysis. As an example, keeping the same security arguments of the design, we conclude that at least 41 instead of 37 rounds would need to be used for 256-bit security, whereby our suggestion does not yet include a security margin.

Shahzad Ahmad Butt, Benjamin Reynolds, V. Ramamurthy, Xiao Xiao · 8 authors

Zero-Knowledge Proofs (ZKPs) have emerged as an important cryptographic technique allowing one party (prover) to prove the correctness of a statement to some other party (verifier) and nothing else. ZKPs give rise to user's privacy in many applications such as blockchains, digital voting, and machine learning. Traditionally, ZKPs suffered from poor scalability but recently, a sub-class of ZKPs known as Zero-knowledge Succinct Non-interactive ARgument of Knowledges (zk-SNARKs) have addressed this challenge. They are getting significant attention and are being implemented by many public libraries. In this paper, we present a novel scalable architecture that is suitable for accelerating the zk-SNARK prover compute on FPGAs. We focus on the multi-scalar multiplication (MSM) that accounts for the majority of computation time spent in zk-SNARK systems. The MSM calculations extensive rely on modular arithmetic so highly optimized Intel IP Libraries for modular arithmetic are used. The proposed architecture exploits the parallelism inherent to MSM and is implemented using the Intel OneAPI framework for FPGAs. Our implementation runs 110x-150x faster compared to reference software library, uses a generic curve form in Jacobian coordinates and is the first to report FPGA hardware acceleration results for BLS12-381 and BN128 family of elliptic curves.

Carsten Baum, Ward Beullens, Shibam Mukherjee, Emmanuela Orsini · 8 authors

No abstract is available for this record.

Xiangren Chen, Bohan Yang, Wenping Zhu, Hanning Wang · 9 authors

Zero-knowledge proof (ZKP) is an attractive cryptographic paradigm that allows a party to prove the correctness of a given statement without revealing any additional information. It offers both computation integrity and privacy, witnessing many celebrated deployments, such as computation outsourcing and cryptocurrencies. Recent general-purpose ZKP schemes, e.g., zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK), suffer from time-consuming proof generation, which is mainly bottlenecked by the large-scale number theoretic transformation (NTT) and multi-scalar point multiplication (MSM). To boost its wide application, great interest has been shown in expediting the proof generation on various platforms like GPU, FPGA and ASIC.So far as we know, current works on the hardware designs for ZKP employ two separated data-paths for NTT and MSM, overlooking the potential of resource reusage. In this work, we particularly explore the feasibility and profit of implementing both NTT and MSM with a unified and high-performance hardware architecture. For the crucial operator design, we propose a dual-precision, load-balanced and fully-pipelined Montgomery multiplier (LBFP MM) by introducing the new mixed-radix technique and improving the prior quotient-decoupled strategy. Collectively, we also integrate orthogonal ideas to further enhance the performance of LBFP MM, including the customized constant multiplication, truncated LSB/MSB multiplication/addition and Karatsuba technique. On top of that, we present the unified, scalable and highperformance hardware architecture that conducts both NTT and MSM in a versatile pipelined execution mechanism, intensively sharing the common computation and memory resource. The proposed accelerator manages to overlap the on-chip memory computation with off-chip memory access, considerably reducing the overall cycle counts for NTT and MSM.We showcase the implementation of modular multiplier and overall architecture on the BLS12-381 elliptic curve for zk-SNARK. Extensive experiments are carried out under TSMC 28nm synthesis and similar simulation set, which demonstrate impressive improvements: (1) the proposed LBFP MM obtains 1.8x speed-up and 1.3x less area cost versus the state-of-the-art design; (2) the unified accelerator achieves 12.1x and 5.8x acceleration for NTT and MSM while also consumes 4.3x lower overall on-chip area overhead, when compared to the most related and advanced work PipeZK.

Marat Salikhov

Abstract With the development of Web3 technologies, the third generation of the Internet has become one of the most promising areas. It involves the use of decentralized, transparent, and user-oriented applications. However, many Web3 projects do not pay sufficient attention to security, which can lead to serious consequences. Even a small error in the code can make the system vulnerable, opening access to attackers. As a result, the industry faces frequent security breaches that threaten users and undermine trust in new technologies. One of the main problems with Web3 is private key management. This is a critical security aspect that is directly related to the protection of digital assets and users' personal information. The risk of losing or theft of a private key can lead to irreparable consequences, since in the case of loss there is no way to restore or reset the key. Various ways of storing the private key of a crypto wallet to ensure security are discussed. For example, the key can be split into parts and stored encrypted on hardware media, or the entire encrypted key can be stored on secure media. Quantitative data are calculated using Shamir’s scheme.

Pedro García-Cereijo, Gabriel Fernández-Blanco, Paula Fraga‐Lamas, Tiago M. Fernández‐Caramés

The deterministic nature of blockchains presents a significant challenge to pseudo-random number generation. Conventional seed-based random number generation methods may not be suitable for deterministic environments as they may be predictable and susceptible to attacks. To address this challenge, this paper proposes the integration of a pseudo-random number generation oracle for the nodes of an Ethereum network. Such an oracle acts as an external provider of pseudo-random numbers, generating random data by using the Fortuna algorithm, which can be used by smart contracts and decentralized applications on the blockchain. However, the integration of an oracle raises additional security and reliability concerns as it relies on a central node that impairs the decentralization of the blockchain and depends on the ability of the oracle to provide unpredictable and non-tampered pseudo-random numbers. The presented implementation can be used in different sectors, such as games of chance, random selection and other scenarios where randomness is essential to guarantee fairness and security. Thus, the integration of a pseudo-random number generation oracle into a Ethereum network can significantly improve the functionality and security of such decentralized applications. In order to show the performance of the proposed system, a comparison is presented that evaluates the security improvements with respect to traditional randomization methods within smart contracts.

O. Yu. Averkov, Alexandr Kuznetsov, I.V. Lysytska

Relevance: Starting with the invention of the Internet, the world began to change rapidly, and the pace of change is increasing, so the problem of data storage and processing is becoming more and more relevant. The ZK-STARK protocol is a new cryptographic zero-knowledge proof protocol that is not yet widely used in practice and allows you to check a message or a transaction on the blockchain network for authenticity without reproducing it completely. At the moment, gaps and problems related to this protocol are identified: computational complexity, possible poor compatibility with other protocols, and resistance to attacks from quantum computers. Therefore, the paper aims to supplement the coverage of the problem associated with computational complexity and to propose solutions to this problem. Purpose: on the basis of the theoretical implementation of the first stage named Arithmetization of the ZK-STARK protocol, to test its software implementation in order to provide recommendations on its most computationally efficient version. Research methods: mathematical statements on interpolation theory, group theory, number theory; information on Fibonacci numbers; information on the Euler function; generating element of a group; cyclic groups; Lagrange interpolation polynomial and the sequence of calculations of Arithmetization; Visual Studio 2022 programming environment, C++ programming language, NTL library, Microsoft Excel. Results of work: The result of the work is the theoretical implementation of the first stage of the ZK-STARK protocol and the effectiveness testing of the first stage, and providing recommendations for its most effective version. Conclusion: Testing has shown that the practical implementation of the Arithmetization based on the inverse fast Fourier transform has a time complexity , that is in times less than the time complexity of the Arithmetization based on inverse matrices method and Gaussian method for interpolation, that speeds up the work of Arithmetization of the ZK-STARK protocol.

Anees Ahmed, Nojan Sheybani, Davi Moreno, Nges Brian Njungle · 7 authors

Collision-resistant, cryptographic hash (CRH) functions have long been an integral part of providing security and privacy in modern systems. Certain constructions of zero-knowledge proof (ZKP) protocols aim to utilize CRH functions to perform cryptographic hashing. Standard CRH functions, such as SHA2, are inefficient when employed in the ZKP domain, thus calling for ZK-friendly hashes, which are CRH functions built with ZKP efficiency in mind. The most mature ZK-friendly hash, MiMC, presents a block cipher and hash function with a simple algebraic structure that is well-suited, due to its achieved security and low complexity, for ZKP applications. Although ZK-friendly hashes have improved the performance of ZKP generation in software, the underlying computation of ZKPs, including CRH functions, must be optimized on hardware to enable practical applications. The challenge we address in this work is determining how to efficiently incorporate ZK-friendly hash functions, such as MiMC, into hardware accelerators, thus enabling more practical applications. In this work, we introduce AMAZE, a highly hardware-optimized open-source framework for computing the MiMC block cipher and hash function. Our solution has been primarily directed at resource-constrained edge devices; consequently, we provide several implementations of MiMC with varying power, resource, and latency profiles. Our extensive evaluations show that the AMAZE-powered implementation of MiMC outperforms standard CPU implementations by more than 13$\times$. In all settings, AMAZE enables efficient ZK-friendly hashing on resource-constrained devices. Finally, we highlight AMAZE's underlying open-source arithmetic backend as part of our end-to-end design, thus allowing developers to utilize the AMAZE framework for custom ZKP applications.

Rares Ifrim, Dumitrel Loghin, Decebal Popescu

Blockchain technology entered the enterprise domain under the name of permissioned blockchains and hybrid or verifiable database systems, as they provide a distributed solution that allows multiple distrusting parties to share common information. One drawback of these systems is the overhead added by the cryptographic functions which impacts the throughput in terms of transactions per second and increases the latency of transaction processing. Many of the cryptographic functions and protocols used in blockchains are based on Elliptic Curve Cryptography (ECC). Unfortunately, ECC operations such as modulo inverse or scalar point multiplication have considerable latency which causes the slowdown of the entire system. In such situations, reconfigurable computing architectures, such as FPGAs, can be used to offload these tasks to overcome the performance loss. This survey analyzes the current state-of-the-art designs and implementations of ECC from a hardware perspective. We use a PRISMA-based approach to filter recent publications and to reduce their number from over 16,000 to only 43 highly relevant designs. In the end, we show that very few designs are able to fulfill all three properties of high performance, scalability, and efficiency.

Xudong Zhu, Haoqi He, Zhengbang Yang, Yi Deng · 6 authors

Zero-knowledge proof (ZKP) is a cryptographic primitive that enables a prover to convince a verifier that a statement is true, without revealing any other information beyond the correctness of the statement itself. Due to its powerful capabilities, its most practical type, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK), has been widely deployed in various privacypreserving applications such as cryptocurrencies and verifiable computation. Although state-of-the-art zkSNARKs are highly efficient for the verifier, the computational overhead for the prover is still orders of magnitude too high to warrant use in many applications. This overhead arises from several time-consuming operations, including large-scale matrix-vector multiplication (MUL), number-theoretic transform (NTT), and especially the multi-scalar multiplication (MSM) which constitutes the largest proportion. Therefore, further efficiency improvements are needed.In this paper, we focus on comprehensive optimization of running time and storage space required by the MSM algorithm on GPUs. Specifically, we propose a novel, modular and adaptive parameter configuration technique—elastic MSM to enable us to adjust the scale of MSM according to our own wishes by performing a corresponding amount of preprocessing. This technique enables us to fully unleash the potential of various efficient parallel MSM algorithms. We have implemented and tested elastic MSM over three prevailing parallel Pippenger algorithms on GPUs. Across various preprocessing space limitations (across various MSM scales), our constructions achieve up to about 1.90×, 1.08× and 1.36× (2.58×, 1.39× and 1.91×) speedup versus three state-of-the-art parallel Pippenger algorithms on GPUs, respectively.From another perspective, elastic MSM could also be regarded as a preprocessing technique over the well-known Pippenger algorithm, which is modular and could be used to accelerate almost all the most advanced parallel Pippenger algorithms on GPUs. Meanwhile, elastic MSM provides an adaptive trade-off between the running time and the extra storage space needed by parallel Pippenger algorithms on GPUs. This is the first preprocessing technique to retain the improved MSM computation brought by preprocessing under varying storage space limitations. Specifically, across various preprocessing space limitations (across various MSM scales), our constructions achieve up to about 192× and 223× (159× and 174×) speedup versus two state-ofthe- art preprocessing parallel Pippenger algorithms on GPUs, respectively.

Simon Masson, Antonio Sanso, Zhenfei Zhang

No abstract is available for this record.

Esra Günsay, Cansu Betin Onur, Murat Cenk

No abstract is available for this record.

Yongkui Yang, Zhenyan Lu, Jingwei Zeng, Xingguo Liu · 6 authors

In this paper, we propose Falic, a novel FPGA-based accelerator to accelerate multi-scalar multiplication (MSM), the most time-consuming phase of zk-SNARK proof generation. Falic innovates three techniques. First, it leverages globally asynchronous locally synchronous (GALS) strategy to build multiple small and lightweight MSM cores to parallelize the independent inner product computation on different portions of the scalar vector and point vector. Second, each MSM core contains just one large-integer modular multiplier (LIMM) that is multiplexed to perform the point additions (PADDs) generated during MSM. We strike a balance between the throughput and hardware cost by batching the appropriate number of PADDs and selecting the computation graph of PADD with proper parallelism degree. Finally, the performance is further improved by a simple cache structure that enables the computation reuse. We implement Falic on two different FPGAs with different hardware resources, i.e., the Xilinx U200 and Xilinx U250. Compared to the prior FPGA-based accelerator, Falic improves the MSM throughput by$3.9\boldsymbol{\times}$. Experimental results also show that Falic achieves a throughput speedup of up to$1.62\boldsymbol{\times}$and saves as much as$8.5\boldsymbol{\times}$energy compared to an RTX 2080Ti GPU.

Alhad Daftardar, Brandon Reagen, Siddharth Garg

Zero-Knowledge Proofs (ZKPs) are an emergent paradigm in verifiable computing. In the context of applications like cloud computing, ZKPs can be used by a client (called the verifier) to verify the service provider (called the prover) is in fact performing the correct computation based on a public input. A recently prominent variant of ZKPs is zkSNARKs, generating succinct proofs that can be rapidly verified by the end user. However, proof generation itself is very time consuming per transaction. Two key primitives in proof generation are the Number Theoretic Transform (NTT) and Multi-scalar Multiplication (MSM). These primitives are prime candidates for hardware acceleration, and prior works have looked at GPU implementations and custom RTL. However, both algorithms involve complex dataflow patterns -- standard NTTs have irregular memory accesses for butterfly computations from stage to stage, and MSMs using Pippenger's algorithm have data-dependent memory accesses for partial sum calculations. We present SZKP, a scalable accelerator framework that is the first ASIC to accelerate an entire proof on-chip by leveraging structured dataflows for both NTTs and MSMs. SZKP achieves conservative full-proof speedups of over 400$\times$, 3$\times$, and 12$\times$ over CPU, ASIC, and GPU implementations.

Annu

Modern cryptography relies heavily on the principles of algebraic structures to ensure the security and integrity of data. This paper explores the fundamental algebraic structures that underpin contemporary cryptographic systems, including groups, rings, fields, and lattices. We provide a detailed examination of how these structures are employed in various cryptographic algorithms and protocols, such as public-key cryptography, digital signatures, and hash functions. an overview of basic algebraic concepts and their properties, followed by an in-depth analysis of their applications in cryptographic schemes. For instance, the use of elliptic curve groups in Elliptic Curve Cryptography (ECC) offers enhanced security with smaller key sizes compared to traditional systems like RSA. Similarly, lattice-based cryptography presents promising solutions for post-quantum security, leveraging the hardness of lattice problems to resist attacks by quantum computers. the role of algebraic structures in the development of advanced cryptographic techniques, such as homomorphic encryption, which allows computations on encrypted data without decryption, and zero-knowledge proofs, which enable the verification of information without revealing the information itself. Through these examples, we illustrate the critical importance of algebraic structures in achieving robust and efficient cryptographic systems.

Alexander Kudzin, Kentaroh Toyoda, Mitsuru Kawazoe, Satoshi Takayama · 5 authors

Proposals for Ultra-Large-Scale-System (ULSS), particularly the grid’s energy management systems (EMSs), to adopt the Ethereum blockchain are increasing as its support for privacy-preserving, encrypted, decentralized computing via sharding, rollups, Smart-Contracts (SC), and Zero-Knowledge-proofs (ZK) address the increasing topological, behavioral, and data-processing challenges. In this context, the aggregation and verification of aggregated, ZK Kate-Zaverucha-Goldberg constant-sized polynomials commitments (KZG) are a bottleneck limiting deployment to Internet-of-Things (IoT) nodes used by the EMS due to high O(b G+blog2b F) computationincurred when aggregating or verifying by recreation. The alternative, expensive pairing checks involve two pairings, three exponentiations (Exp), three multiplications (Mul), and one addition (Add), a security factor S times for the n aggregated KZG. The proposed pairing checks significantly reduce costs for both: 1) Verifiers: two pairings, no Exp, one Mul, and one Add, and 2) Provers: one pairing check, no Exp, four Mul, and one Add. The aggregation method, based on multidimensional differential addition chains, costs only O(ℓ) computation, where ℓ is the bit length of the scalars. This approach demonstrates the feasibility of operating a KZG-centric blockchain with KZG rollups on IoT networks, marking a significant advancement in ULSS.

Changxu Liu, Hao Zhou, Patrick Dai, Li Shang · 5 authors

Multi-Scalar Multiplication (MSM) is a computationally intensive task that operates on elliptic curves based on GF(P) . It is commonly used in zero-knowledge proof (ZKP), where it accounts for a significant portion of the computation time required for proof generation. In this article, we present PriorMSM, an efficient acceleration architecture for MSM. We propose a Priority-Based Scheduling Mechanism (PBSM) based on a multi-FIFO and multi-bank architecture to accelerate the implementation of MSM. By increasing the pairing success rate of internal points, PBSM reduces the number of bubbles in the pipeline of point addition (PADD), consequently improving the data throughput of the pipeline. We also introduce an advanced parallel bucket aggregation algorithm, leveraging PADD’s fully pipelined characteristics to significantly accelerate the implementation of bucket aggregation. We perform a sensitivity analysis on the crucial parameter of window size in MSM. The results indicate that the window size of the MSM significantly impacts its latency. Area-Time Product (ATP) metric is introduced to guide the selection of the optimal window size, balancing the performance and cost for practical applications of subsequent MSM implementations. PriorMSM is evaluated using the TSMC 28 nm process. It achieves a maximum speedup of 10.9× compared to the previous custom hardware implementations and a maximum speedup of 3.9× compared to the GPU implementations.

Mitjans Llorach, Àlex

As cryptographic technologies evolve, the need for specialized hash functions to operate efficiently over different computational environments becomes necessary. Traditional symmetric algorithms like AES and SHA-3 have been optimized for traditional hardware and software implementations, which are designed over binary fields. However, protocols like zero-knowledge proofs require hash functions that are optimised over large prime fields. This thesis addresses the growing demand for Arithmetization-Oriented (AO) cryptographic hash functions for zero-knowledge applications. The performance and efficiency of many zero-knowledge applications often depends on the efficiency of the hash function used. In response to this need, this work explores a selection of these hash functions and implements them within two zero-knowledge proving systems: Dusk Network?s Plonk and Polygon?s Plonky2, with a focus on assessing the different performance tradeoffs that these hash functions offer within these sytems.

Changxu Liu, Hao Zhou, Lan Yang, Jiamin Xu · 6 authors

Multi-Scalar Multiplication (MSM) is a fundamental cryptographic primitive, which plays a crucial role in Zero-knowledge proof systems. In this paper, we optimize the single MSM Process Element (PE) utilizing buckets with fewer conflicts, enhanced by Greedy-based scheduling, to achieve higher efficiency. The evaluation results show our optimized single MSM PE achieving a speedup of over two times on average, peaking at 3.63 times compared to previous works. Furthermore, we introduce Gypsophila, a scalable and bandwidth-optimized architecture for implementing multiple MSM PEs. Leveraging the characteristics of the bucket method, we optimize the data flow by balancing the throughput of bucket classification, bucket aggregation, and result aggregation in MSM. Simultaneously, multiple PEs with different data access patterns share a universal point input channel and post-processing unit, which improves the module utilization and mitigates the bandwidth pressure. Gypsophila with 16 PEs, accomplishes 16 MSM tasks in a mere 1.01% additional time, showcasing an approximate 7.8% reduction in area, with only about 116 of the bandwidth requirement, compared with 16 PEs without input channel and post-process unit sharing.