Blockchain Papers

Shai Levin, Robi Pedersen

No abstract is available for this record.

Yibin Yang

No abstract is available for this record.

Helger Lipmaa

No abstract is available for this record.

Geoffroy Couteau, Srinivas Devadas, Alexander Koch, Sacha Servan-Schreiber

No abstract is available for this record.

Yunqing Sun, Hanlin Liu, Kang Yang, Yu Yu · 6 authors

We introduce the notion of committed vector oblivious linear evaluation (C-VOLE), which allows a party holding a pre-committed vector to generate VOLE correlations with multiple parties on the committed value. It is a unifying tool that can be found useful in zero-knowledge proofs (ZKPs) of committed values, actively secure multi-party computation, private set intersection (PSI), etc.

Khoshakhlagh, Sajjad

No abstract is available for this record.

Xia, Yu

Secure Multi-party Computation (MPC) considers the problem where a set of mutually distrusting parties want to jointly compute a function over their private inputs, without revealing any extra information about these inputs other than what it can be inferred from the output of the function. This setting is well-motivated, and it has many real-world applications such as auction, voting, etc. MPC can be also seen as a generalization of many natural cryptographic primitives. For example, zero-knowledge (ZK) can be viewed as a special case of two-party secure computation. In ZK, a party, called prover aims to convince a second party, called verifier, that the prover’s private input witness w and a public input statement x belong to a relation R. An important research direction in secure computation is to find the trade-off between the required setup (e.g., the use of the broadcast channel, the use of common reference string (CRS) / public key infrastructure (PKI), the upper bound of the parties that can be corrupted, etc.), and the security guarantees that can be achieved. The setups can be viewed as some general assumptions that the protocol needs to satisfy, and they influence the usability of the protocol in real-world scenarios. In principle, having simpler (or no) setups mean that the protocol is more general and can be more useful in real-world scenarios. At the same time, having simpler setups may lead to weaker security guarantees. Therefore, finding the trade-off between setup and security guarantees is important and meaningful. In this thesis, we target MPC and ZK, and we focus on how to minimize the setup for MPC and ZK while still providing meaningful levels of security. More specifically: Regarding MPC, we focus on the dishonest majority (i.e., the adversary can corrupt all but one party), and we aim at 1) minimizing the use of broadcast channels. 2) studying the MPC with pre-processing when no setup is available. • Informally, a broadcast channel guarantees that when a message is sent, this reaches all the parties, without ambiguity. It also guarantees that if an honest party receives a message from a corrupted party, then it is guaranteed that all the honest parties have received the message. To realize broadcast, parties in the protocol could run the broadcast protocol, which may require many rounds of peer-to-peer communications. An alternative way is to rely on physical or external infrastructure such as blockchain. In both cases, broadcast is expensive, as such, we want to minimize its use. In particular, this thesis presents the following results: – When assuming no setup, we give a complete characterization with respect to the use of broadcast channels, and we obtain the optimal results. – We consider the same problem for the case that we only want to allow the black-box use (i.e., do not have access to the code of the algorithm) of the oblivious transfer protocol. We also give a characterization. • In the standard definition of MPC, the parties’ private inputs are fixed before the start of the protocol. However, there is another type of MPC named MPC with pre-processing, where the protocol can pre-compute some messages without using parties’ inputs, and these messages can accelerate computations in the online phase (i.e., other computations that require parties’ inputs). Since some expensive computations can be pre-computed, the online phase could be more lightweight. Therefore, we want to remove the dependency of the input from as many rounds as possible, so that we can do some pre-processing. In this direction, we explore the protocol with no setup. We provide a compiler that can turn a big class of MPC protocol that may require the inputs already to compute the first round, into a new protocol that needs the inputs only in the last two rounds. We also propose new MPC definitions that capture this delayed-input features. Regarding ZK, we do the following: • In standard single-theorem ZK definition, the security of the ZK protocol is guaranteed to hold only when one proof is issued. In the case where multiple zero-knowledge proofs need to be issued (i.e., to prove multiple NP statements), each new zero-knowledge proof requires a freshly generated setup. In the multi-theorem ZK definition, instead, one setup is sufficient for generating multiple zero-knowledge proofs for multiple instances. We propose a multi-theorem protocol (in the format of a compiler) that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Prior works could achieve this adaptive security only inefficiently via NP reductions. • ZK protocols are secure only when all setups are correctly generated, but in real-world scenarios, some of the setups may not be correctly generated. For instance, to run a non-interactive zero-knowledge (NIZK) protocol, the setup CRS could be chosen with bias. In this case, the security of the NIZK protocol does not hold anymore. Instead of finding a secure ZK candidate, one alternative solution is to have multiple instantiations of ZK candidates and assume that only for a subset of them the setup is generated correctly. More formally, we consider the case where only a subset of the instances are secure. In more detail, given access to n candidate instantiations of a NIZK for some language, we want to have a construction that itself implements a NIZK for the same language without relying on any additional computational assumptions. We refer to this type of construction as combiner, and the combiner is secure assuming at least t of the given candidates are secure. In this work, we provide three different constructions of robust NIZK combiners and show that combiners are impossible to realize unless the majority of the input candidates are secure.

Sabine Oechsner, Vítor Pereira, Peter Schöll

Computer-aided cryptography, with particular emphasis on formal verification, promises an interesting avenue to establish strong guarantees about cryptographic primitives. The appeal of formal verification is to replace the error-prone pen-and-paper proofs with a proof that was checked by a computer and, therefore, does not need to be checked by a human. In this paper, we ask the question of how reliable are these machine-checked proofs by analyzing a formally verified implementation of the Line-Point Zero-Knowledge (LPZK) protocol (Dittmer, Eldefrawy, Graham-Lengrand, Lu, Ostrovsky and Pereira, CCS 2023). The implementation was developed in EasyCrypt and compiled into OCaml code that was claimed to be high-assurance, i.e., that offers the formal guarantees of guarantees of completeness, soundness, and zero knowledge. We show that despite these formal claims, the EasyCrypt model was flawed, and the implementation (supposed to be high-assurance) had critical security vulnerabilities. Concretely, we demonstrate that: 1) the EasyCrypt soundness proof was incorrectly done, allowing an attack on the scheme that leads honest verifiers into accepting false statements; and 2) the EasyCrypt formalization inherited a deficient model of zero knowledge for a class of non-interactive zero knowledge protocols that also allows the verifier to recover the witness. In addition, we demonstrate 3) a gap in the proof of the perfect zero knowledge property of the LPZK variant of Dittmer, Ishai, Lu and Ostrovsky (CCS 2022) that the EasyCrypt proof is based, which, depending on the interpretation of the protocol and security claim, could allow a malicious verifier to learn the witness. Our findings highlight the importance of scrutinizing machine-checked proofs, including their models and assumptions. We offer lessons learned for both users and reviewers of tools like EasyCrypt, aimed at improving the transparency, rigor, and accessibility of machine-checked proofs. By sharing our methodology and challenges, we hope to foster a culture of deeper engagement with formal verification in the cryptographic community.

Biniyam Deressa, M.A. Hasan

We introduce zkMaP (Zero-Knowledge Succinct Non-Interactive Matrix Multiplication Proofs), a novel non-interactive zero-knowledge proof system for verifying matrix multiplication with significant improvements in efficiency and scalability. Our protocol leverages KZG polynomial commitments and an innovative inner-product reduction technique to reduce the verification of n x n matrix multiplication to a single pairing equation, thereby enabling constant-time verification independent of the matrix size. In particular, zkMaP requires only two pairing operations and produces proofs as small as 320 bytes, yielding a 96 percent reduction in proof size compared to prior schemes. Furthermore, the prover's computational complexity follows the state-of-the-art at O(n^2), with experimental results demonstrating that proofs for 1024 x 1024 matrices can be generated in approximately 12.21 seconds, offering a 16.14x speedup over previous methods. Our implementation also exhibits better memory efficiency, using only 24.58 MB of prover-side RAM for 1024 x 1024 matrices, and supports scalable batch processing, achieving per-proof generation times of 46.79 milliseconds for 1024 instances while maintaining a constant verification time of 3.6 ms.

Kwan Yin Chan, Tsz Hon Yuen, Siu Ming Yiu

Traceable ring signatures (TRSs) allow a signer to create a signature that maintains anonymity while enabling traceability if needed. It merges the characteristics of traditional ring signatures with the ability to trace signers, making it ideal for applications that demand both confidentiality and accountability. In a TRS scheme, a ring of potential signers generates a signature on a message without disclosing the actual signer’s identity. However, the identity can be traced if the signer uses the same tag for multiple signatures. This paper introduces a novel formal construction of TRS under universally composable (UC) security. We integrate verifiable random functions (VRFs) and zero-knowledge proofs for membership, employing Pedersen commitments. Our signature schemes maintain a logarithmic size while preserving the UC security guarantees. Additionally, we explore the potential to extend the property of one-time anonymity in TRS to K-time anonymity.

Dong Fang, Guifang Huang, Shuai Chang, Haonan Yang · 6 authors

Abstract Verifiable encryption enables the decryption to be taken on properly generated ciphertexts, by making the encryptor provide a zero-knowledge proof. To meet the quantum-safe application requirements, such as key escrow, Lyubashevsky et al. proposed a one-shot verifiable encryption (LN17 scheme) based on the hardness of lattice problems. In their scheme, the FSwA-type zero-knowledge proof was obtained using rejection sampling on a discrete Gaussian distribution. In this paper, we present a construction of verifiable encryption that utilizes rejection sampling on bimodal Gaussian to get the associated zero-knowledge proof. Our new construction, while exhibiting a weaker soundness property than LN17 scheme, benefits from a smaller proof size, leading to a reduced size of the verifiable ciphertext. As for the weaker soundness property, it supports some applications such as key escrow where honestly generated verifiable ciphertexts are more useful to be decrypted out in the hope of doing some further computation tasks. We provide the efficiency comparison of the new construction by instantiating it with several sets of concrete parameters.

L. Domven, Aliyu Danladi Hina, A. M. Kwami, C. M. Miri · 5 authors

This study proposes a secure mobile voting system that integrates elliptic curve cryptography (ECC) with secure multiparty computation (SMPC) to guarantee vote confidentiality, integrity, and verifiability. Designed to enable scalable, privacy-preserving elections via mobile devices, the system authenticates voters using registered numbers and records ballots as encrypted points on an elliptic curve. Encrypted votes are published on a public bulletin board alongside zero-knowledge proofs to ensure their validity. To safeguard decryption, Shamir’s secret sharing distributes keys among trusted authorities, enabling collective tallying without exposing individual votes. The system incorporates ECC-based secret sharing, homomorphic encryption, and zero-knowledge proofs, leveraging the hardness of the elliptic curve discrete logarithm problem (ECDLP) for robust security. Both experimental and theoretical evaluations demonstrate that ECC significantly improves computational efficiency and scalability, making the system well-suited for resource-constrained environments. Overall, the integration of ECC and SMPC offers a practical, efficient, and secure framework for mobile elections, effectively balancing privacy, security, and performance.

Maria Nuțu, Giorgi Akhalaia, Răzvan Bocu, Maksim Iavich

Commitment schemes represent foundational cryptographic primitives enabling secure verification protocols across diverse applications, from blockchain systems to zero-knowledge proofs. This paper presents a systematic survey of vector, polynomial, and functional commitment schemes, analyzing their evolution from classical constructions to post-quantum secure alternatives. We examine the strengths and limitations of RSA-based, Diffie–Hellman, and lattice-based approaches, highlighting the critical shift toward quantum-resistant designs necessitated by emerging computational threats. The survey reveals that while lattice-based schemes (particularly those using the Short Integer Solution problem) offer promising security guarantees, they face practical challenges in proof size and verification efficiency. Functional commitments emerge as a powerful generalization, though their adoption is constrained by computational overhead and setup requirements. Key findings identify persistent gaps in adaptive security, composability, and real-world deployment, while proposed solutions emphasize optimization techniques and hybrid approaches. By synthesizing over 90 research works, this paper provides both a comprehensive reference for cryptographic researchers and a roadmap for future developments in commitment schemes, particularly in addressing the urgent demands of post-quantum cryptography and decentralized systems.

Yuki Sawai, Kyoichi Asano, Yohei Watanabe, Mitsugu Iwamoto

Range arguments are a type of zero-knowledge proofs that aim to prove that a prover's committed value falls within a specified range for a verifier. Previously, most range arguments were constructed based on the DLOG assumption, and hence, exponentiation operation is required for proof generation and verification. In addition, it is generally known that splitting a zero-knowledge proof protocol into a preprocessing phase and an online phase makes computation after fixing the input efficient. Still, such protocol has yet to be known for range arguments. This paper proposes an efficient range arguments protocol with a preprocessing phase. Our proposal takes a new approach by using arithmetic circuits to express the constraints that the prover must prove. The prover (resp. verifier) can generate (resp. verify) a part of proof based on multiplication and addition operations instead of exponentiation operations. Our range argument is a generic construction that does not rely on any particular mathematical assumptions, which enables us to construct a post-quantum range argument. The implementation evaluation shows that the total computation time for the prover and verifier in the online phase is efficient compared to Bulletproofs, one of the state-of-the-art range proofs. Especially, the prover computation is efficient.

Qiuyue Liu, Zhanyuan Cai

This paper studies the \emph{unimodular isomorphism problem} (UIP) of convex lattice polytopes: given two convex lattice polytopes $P$ and $P'$, decide whether there exists a unimodular affine transformation mapping $P$ to $P'$. We show that UIP is graph isomorphism hard, while the polytope congruence problem and the combinatorial polytope isomorphism problem (Akutsu, 1998; Kaibel, Schwartz, 2003) were shown to be graph isomorphism complete, and both the lattice isomorphism problem ( $\mathrm{Sikiri\acute{c}}$, $\mathrm{Sch\ddot{u}rmann}$, Vallentin, 2009) and the projective/affine polytope isomorphism problem (Kaibel, Schwartz, 2003) were shown to be graph isomorphism hard. Furthermore, inspired by protocols for lattice (non-) isomorphism (Ducas, van Woerden, 2022; Haviv, Regev, 2014), we present a statistical zero-knowledge proof system for unimodular isomorphism of lattice polytopes. Finally, we propose an algorithm that given two lattice polytopes computes all unimodular affine transformations mapping one polytope to another and, in particular, decides UIP.

Ngoc Khanh Nguyen, George O'Rourke

In this work, we present a concretely efficient lattice-based zero-knowledge proof system that satisfies straight-line extractability. At the heart of our construction is a novel, non-generic application of the Katsumata transform (CRYPTO 2021) to the widely adopted zero-knowledge framework of Lyubashevsky, Nguyen and Plançon (CRYPTO 2022). Our approach significantly optimizes the proof size, achieving a 2X reduction compared to prior generic techniques. This makes our scheme particularly well-suited for anonymous credential systems, secure multi-party computation, and proving quantum security, where straight-line extractability is essential.

Julio López Fenner, Carlos Castillo-Muñoz, Francisco Escobar, Ana Bustamante-Mora · 5 authors

Privacy-preserving secure multi-party computation protocols are known to face scalability and efficiency challenges in environments where participants hold distinct attributes of the same records (vertical partitioning) or controls a subset of complete records (horizontal partitioning), as in cross-institutional health data analysis or federated IoT analytics, mostly because of communication overhead and the need to address adaptability to large scale or heterogeneous settings. This work introduces a novel MPC protocol based on the Damgård–Jurik cryptosystem and Schnorr zero-knowledge proofs (ZKP), designed to securely aggregate private data distributed across a number of parties. By combining homomorphic encryption with non-interactive ZKP’s, the protocol ensures privacy, correctness, and scalability, aligning with the principles of privacy-enhancing technologies (PETs). Our approach minimizes data exposure, allowing participants to audit results, and achieves linear O(N) communication complexity, thus making it suitable for large-scale applications in secure data analytics and collaborative computing.

Yancheng Zhang, Mengxin Zheng, Xun Chen, Jingtong Hu · 8 authors

In the context of cloud computing, services are held on cloud servers, where the clients send their data to the server and obtain the results returned by server. However, the computation, data and results are prone to tampering due to the vulnerabilities on the server side. Thus, verifying the integrity of computation is important in the client-server setting. The cryptographic method known as Zero-Knowledge Proof (ZKP) is renowned for facilitating private and verifiable computing. ZKP allows the client to validate that the results from the server are computed correctly without violating the privacy of the server’s intellectual property. Zero-Knowledge Succinct NonInteractive Argument of Knowledge (zkSNARKs), in particular, has been widely applied in various applications like blockchain and verifiable machine learning. Despite their popularity, existing zkSNARKs approaches remain highly computationally intensive. For instance, even basic operations like matrix multiplication require an extensive number of constraints, resulting in significant overhead. In addressing this challenge, we introduce $z k V C$, which optimizes the ZKP computation for matrix multiplication, enabling rapid proof generation on the server side and efficient verification on the client side. zkVC integrates optimized ZKP modules, such as Constraint-reduced Polynomial Circuit (CRPC) and Prefix-Sum Query (PSQ), collectively yielding a more than $\mathbf{1 2}$-fold increase in proof speed over prior methods. The code is available at https://github.com/UCF-Lou-Lab-PET/zkformer.

Lior Rotem

The seminal work of Goldreich and Krawczyk (SIAM Journal on Computing) shows that any constant-round public-coin interactive proof for languages not in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi mathvariant="sans-serif">B</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> </mml:mrow> </mml:mrow> </mml:math> cannot be black-box zero knowledge. Their result says nothing, however, about proofs (or arguments) of knowledge for languages in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi mathvariant="sans-serif">B</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> </mml:mrow> </mml:mrow> </mml:math>. As a special case, their work leaves open the question of whether Schnorr's protocol for proving knowledge of discrete logarithms in cyclic groups is black-box zero knowledge. In this work we focus on the zero knowledge of proofs of knowledge, centering on Schnorr's protocol as a prominent example. We prove two lower bounds, ruling out two different classes of simulators through which Schnorr's protocol can be proven zero knowledge: We prove that if a relation <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℛ</mml:mi> </mml:mrow> </mml:math> has a public-coin interactive proof of knowledge that is black-box zero knowledge and this protocol is compatible with the Fiat-Shamir transform in the random oracle model, then <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℛ</mml:mi> </mml:mrow> </mml:math> must be efficiently searchable. As an immediate corollary, we deduce that Schnorr's protocol cannot be black-box zero knowledge in groups in which discrete log is hard. We define a new class of simulators for Schnorr's protocol, which we call generic simulators. A generic simulator is one that works in any cyclic group, and does not use the representation of the specific group in which Schnorr's protocol is instantiated. We prove that Schnorr's protocol cannot have generic simulators. As an additional contribution, we generalize the original lower bound of Goldreich and Krawczyk, to prove that a language not in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi mathvariant="sans-serif">B</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> <mml:mi mathvariant="sans-serif">P</mml:mi> </mml:mrow> </mml:mrow> </mml:math> cannot have an interactive proof (not necessarily of knowledge) that is both black-box zero knowledge and compatible with the Fiat-Shamir transform in the random oracle model. In conjunction with recent works, this extends the Goldreich-Krawczyk lower bound to public-coin protocols that are not constant-round but have round-by-round soundness, including the parallel repetition of any public-coin interactive proof.

Agon Kokaj, Elissa Mollakuqe

This work presents a mathematical solution to data privacy and integrity issues in Split Learning which uses Homomorphic Encryption (HE) and Zero-Knowledge Proofs (ZKP). It allows calculations to be conducted on encrypted data, keeping the data private, while ZKP ensures the correctness of these calculations without revealing the underlying data. Our proposed system, HavenSL, combines HE and ZKP to provide strong protection against attacks. It uses Discrete Cosine Transform (DCT) to analyze model updates in the frequency domain to detect unusual changes in parameters. HavenSL also has a rollback feature that brings the system back to a verified state if harmful changes are detected. Experiments on CIFAR-10, MNIST, and Fashion-MNIST datasets show that using Homomorphic Encryption and Zero-Knowledge Proofs during training is feasible and accuracy is maintained. This mathematical-based approach shows how crypto-graphic can protect decentralized learning systems. It also proves the practical use of HE and ZKP in secure, privacy-aware collaborative AI.

H. Y. Fu, Kieran Mastel, Xingjian Zhang

In their recent breakthrough result, Slofstra and the second author show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE (STOC'24). We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE against dishonest verifiers with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we study the three central compression techniques underlying the MIP*=RE proof (Ji et al. '20): question reduction, oracularization, and answer reduction. We show that question reduction preserves the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against dishonest verifiers, and oracularization and answer reduction preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against honest verifiers. Secondly, we show that every constraint-constraint binary constraint system (BCS) nonlocal game, which provides a quantum information characterization of MIP*, can be converted to a synchronous constraint-variable BCS game to preserve perfect completeness for our compression. Lastly, we present a parametrized perfect-zero-knowledge transformation of MIP* protocols, which generalizes the transformation in (Slofstra and Kieran STOC'24) . This transformation allows us to preserve the zero-knowledge property against dishonest verifiers in the recursively oracularized protocols in our compression.

Jules Maire, Damien Vergnaud

We present a communication-efficient zero-knowledge proof of knowledge for the factorization of Blum integers, a special class of integers of the form n = p q , where p and q are distinct prime numbers satisfying p ≡ q ≡ 3 mod 4 and p ≃ q ≃ n . Existing protocols for proving such statements often incur significant communication costs, especially when demonstrating that p and q are of nearly equal size. We leverage the MPC-in-the-head paradigm, a cryptographic technique that transforms secure multi-party computation protocols into efficient zero-knowledge proof systems. In our protocol, the prover uses additive sharing of p and q over the integers. This approach simplifies proving the size relationship p ≃ q ≃ n and the congruence p ≡ q ≡ 3 mod 4 without requiring costly range proofs. To verify the primality of p and q , we employ the Boneh-Franklin biprimality test. Our protocol achieves a significant reduction in communication complexity. For a 2048-bit integer n and 128-bit security, we construct a proof as small as 12.3 KB, with prover and verifier computational costs comparable to existing protocols that require over 131 KB.

Noga Ron‐Zewi, Ron D. Rothblum

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language \(L \in \mathsf {NP}\) , with communication that is much shorter than the \(\mathsf {NP}\) witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness. In this work, we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a strictly linear size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a quasi- linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields. In more detail, for every Boolean circuit \(C=C(x,w)\) , we construct an \(O(\log |C|)\) -round argument-system in which the prover can be implemented by a size \(O(|C|)\) Boolean circuit (given as input both the instance x and the witness w ), with arbitrarily small constant soundness error and using \(\mathrm{poly}(\lambda ,\log |C|)\) communication, where \(\lambda\) denotes the security parameter. The verifier can be implemented by a size \(O(|x|) + \mathrm{poly}(\lambda , \log |C|)\) circuit following a size \(O(|C|)\) private pre-processing step, or, alternatively, by using a purely public-coin protocol (with no pre-processing) with a size \(O(|C|)\) verifier. The protocol can be made zero-knowledge using standard techniques (and with similar parameters). The soundness of our protocol is computational and relies on the existence of collision resistant hash functions that can be computed by linear-size circuits, such as those proposed by Applebaum et al. (ITCS, 2017). At the heart of our construction is a new information-theoretic interactive oracle proof ( \(\mathsf {IOP}\) ), an interactive analog of a \(\mathsf {PCP}\) , for circuit satisfiability, with constant prover overhead. The improved efficiency of our \(\mathsf {IOP}\) is obtained by bypassing a barrier faced by prior \(\mathsf {IOP}\) constructions, which needed to (either explicitly or implicitly) encode the entire computation using a multiplication code.

Calvin Josenhans, Andrey Kuehlkamp, Jarek Nabrzyski

Ethereum is currently the second largest blockchain by market capitalization and a popular platform for cryptocurrencies. As it has grown, the high value present and the anonymity afforded by the technology have led Ethereum to become a hotbed for various cybercrimes. This paper seeks to understand how these fraudulent schemes may be characterized and develop methods for detecting them. One key feature introduced by Ethereum is the ability to use programmable smart contracts to execute code on the blockchain. A common use of smart contracts is implementing fungible tokens with the ERC-20 interface. Such tokens can be used to impersonate legitimate tokens and defraud users. By parsing the event logs emitted by these ERC-20 contracts over 20 different periods of 100K blocks, we construct token transfer graphs for each of the available ERC-20 tokens on the blockchain. By analyzing these graphs, we find a set of characteristics by which suspicious contracts are distinguished from legitimate ones. These observations result in a simple model that can identify scam contracts with an average of 88.7% accuracy. This suggests that the mechanism by which fraudulent schemes function strongly correlates with their transfer graphs and that these graphs may be used to improve scam-detection mechanisms, contributing to making Ethereum safer.