Circom is a popular programming language for writing arithmetic circuits that can be used to generate zero-knowledge proofs (ZKPs) like zk-SNARKS. ZKPs have received tremendous attention in protocols like zkRollups. The Circom circuits are compiled to Rank-1 Constraint Systems (R1CS) circuits, based on which zk-SNARK proofs are generated. However, one major challenge associated with R1CS circuits is the problem of under-constrained circuits, which are susceptible to allowing incorrect computations to pass verification due to insufficient constraints, potentially leading to security vulnerabilities. In this paper, we propose a novel framework CONSCS to automatically verify Circom circuits. Our contributions are threefold: 1) we propose novel circuit inference rules to help reduce the size of circuits and to extract more comprehensive information than existing works; 2) we introduce the novel Binary Property Graph (BPG) as a highly efficient reasoning engine, outperforming all existing tools in effectiveness and efficiency; 3) we leverage fine-grained domain-specific information to guide the SMT solving to address non-linear constraints, increasing the success rate of SMT queries of existing works from 2.68% to 48.84%. We conduct experiments to show that CONSCS enhances the solved rate of existing works from around 50-60% to above 80%.
Federated Learning (FL) is a widespread approach that allows training machine learning (ML) models with data distributed across multiple devices. In cross-silo FL, which often appears in domains like healthcare or finance, the number of participants is moderate, and each party typically represents a well-known organization. For instance, in medicine data owners are often hospitals or data hubs which are well-established entities. However, malicious parties may still attempt to disturb the training procedure in order to obtain certain benefits, for example, a biased result or a reduction in computational load. While one can easily detect a malicious agent when data used for training is public, the problem becomes much more acute when it is necessary to maintain the privacy of the training dataset. To address this issue, there is recently growing interest in developing verifiable protocols, where one can check that parties do not deviate from the training procedure and perform computations correctly. In this paper, we present a systematization of knowledge on verifiable cross-silo FL. We analyze various protocols, fit them in a taxonomy, and compare their efficiency and threat models. We also analyze Zero-Knowledge Proof (ZKP) schemes and discuss how their overall cost in a FL context can be minimized. Lastly, we identify research gaps and discuss potential directions for future scientific work.
Rug pulls pose a grave threat to the cryptocurrency ecosystem, leading to substantial financial loss and undermining trust in decentralized finance (DeFi) projects. With the emergence of new rug pull patterns, research on rug pull is out of state. To fill this gap, we first conducted an extensive analysis of the literature review, encompassing both scholarly and industry sources. By examining existing academic articles and industrial discussions on rug pull projects, we present a taxonomy inclusive of 34 root causes, introducing six new categories inspired by industry sources: burn, hidden owner, ownership transfer, unverified contract, external call, and fake LP lock. Based on the developed taxonomy, we evaluated current rug pull datasets and explored the effectiveness and limitations of existing detection mechanisms. Our evaluation indicates that the existing datasets, which document 2,448 instances, address only 7 of the 34 root causes, amounting to a mere 20% coverage. It indicates that existing open-source datasets need to be improved to study rug pulls. In response, we have constructed a more comprehensive dataset containing 2,360 instances, expanding the coverage to 54% with the best effort. In addition, the examination of 14 detection tools showed that they can identify 25 of the 34 root causes, achieving a coverage of 73.5%. There are nine root causes (Fake LP Lock, Hidden Fee, and Destroy Token, Fake Money Transfer, Ownership Transfer, Liquidity Pool Block, Freeze Account, Wash-Trading, Hedge) that the existing tools cannot cover. Our work indicates that there is a significant gap between current research and detection tools, and the actual situation of rug pulls.
As zero-knowledge proofs gain increasing adoption, the cryptography community has designed domain-specific languages (DSLs) that facilitate the construction of zero-knowledge proofs (ZKPs). Many of these DSLs, such as Circom, facilitate the construction of arithmetic circuits, which are essentially polynomial equations over a finite field. In particular, given a program in a zero-knowledge proof DSL, the compiler automatically produces the corresponding arithmetic circuit. However, a common and serious problem is that the generated circuit may be underconstrained, either due to a bug in the program or a bug in the compiler itself. Underconstrained circuits admit multiple witnesses for a given input, so a malicious party can generate bogus witnesses, thereby causing the verifier to accept a proof that it should not. Because of the increasing prevalence of such arithmetic circuits in blockchain applications, several million dollars worth of cryptocurrency have been stolen due to underconstrained arithmetic circuits. Motivated by this problem, we propose a new technique for finding ZKP bugs caused by underconstrained polynomial equations over finite fields. Our method performs semantic reasoning over the finite field equations generated by the compiler to prove whether or not each signal is uniquely determined by the input. Our proposed approach combines SMT solving with lightweight uniqueness inference to effectively reason about underconstrained circuits. We have implemented our proposed approach in a tool called QED 2 and evaluate it on 163 Circom circuits. Our evaluation shows that QED 2 can successfully solve 70% of these benchmarks, meaning that it either verifies the uniqueness of the output signals or finds a pair of witnesses that demonstrate non-uniqueness of the circuit. Furthermore, QED 2 has found 8 previously unknown vulnerabilities in widely-used circuits.
Les preuves vérifiables de manière probabiliste (PCP, de l'anglais "probabilistically checkable proofs), les preuves interactives (IP, pour "interactive proofs") ou encore les preuves à divulgation nulle de connaissance ("zero-knowledge proofs") ont la particularité d'admettre une vérification probabilististe. Ces systèmes de preuves probabilistes interviennent dans les constructions de schémas de calcul vérifiable, des protocoles cryptographiques permettant de vérifier très rapidement qu'un long calcul a été correctement effectué. En 2016, un nouveau modèle de preuve a été introduit par Ben-Sasson, Chiesa et Spooner : celui des preuves interactives par oracle (IOP, pour "interactive oracle proofs"). Ce modèle généralise à la fois les PCPs et les IPs et a suscité beaucoup d'intérêt depuis son introduction. Le modèle IOP a mené à d'intéressants résultats théoriques sur les arguments non-interactifs succincts et transparents ainsi qu'à des déploiements industriels.Un problème récurrent dans les constructions de systèmes de preuves probabilistes est celui de tester efficacement la proximité à un code correcteur d'erreurs. Le but est de déterminer si un certain mot appartient à un code linéaire donné, ou bien s'il est éloigné de tout mot de ce code. Les tests de proximité à des codes polynomiaux peuvent être interprétés comme des tests de bas degré. Par exemple, un important sous-protocole utilisé dans de nombreuses constructions pratiques est un "IOP of Proximity" pour les codes de Reed-Solomon (Ben-Sasson et al., ICALP 2018).Dans cette thèse, nous proposons dans le modèle IOP des protocoles permettant de vérifier la proximité à des codes correcteur d'erreurs.En nous inspirant du test de proximité pour les codes de Reed-Solomon de Ben-Sasson et al., nous commençons par formuler un cadre abstrait et générique pour construire des "IOPs of Proximity" pour des codes linéaires et en analysons formellement les propriétés. Nous appliquons ensuite cette méthodologie à différentes familles de codes généralisant les codes de Reed-Solomon. Il s'agit d'une part de codes définis à partir d'évaluations de polynômes multivariés et, d'autre part, de codes de géométrie algrébrique définis sur des courbes. Nos protocoles permettent de tester la proximité à des codes présentant des propriétés attrayantes par rapport aux codes de Reed-Solomon (telles que des alphabets de petite taille), tout en ayant une efficacité similaire à la construction de Ben-Sasson et al.
In this paper, we address Field Programmable Gate Array (FPGA) implementation of the Elliptic Curve Digital Signature Algorithm(ECDSA), which is suitable for cryptocurrencies in blockchain. Although the ECDSA requires high computational efforts, utilization of a specific logic circuit allows us quick and easy computation. In this paper, we give implementation results of the ECDSA on an FPGA, and mention the superiority of FPGA implementation by comparing its simulation result with that of software based computation using a CPU.
This paper proposes a new zero-knowledge proof protocol of identification which combines the characteristics of the ECC and zero-knowledge proof.The proposed protocol has more advantages in the aspect of the quantity of computing and traffic.
Physical Unclonable Functions (PUFs) and Hardware Security
Reuse of intellectual property (IP) of VLSI physical design facilitates integration of more components on a single chip in shrinking time-to-market. For intellectual property protection (IPP), various kinds of IP marks are embedded into the design for establishing the veracity of a legal owner. However, public verification of IP marks is not leakage-proof. Current techniques include a sufficiently large set of public marks containing a header and a message body in addition to private ones to facilitate only public verification at the cost of significant increase in design overhead. But these techniques are not effective, as attackers manage to obtain potential clues to tamper public marks rendering public verification invalid and may also suitably override the marks to include own signature resulting in wrong public identification of IP owner. Here we propose a zero-knowledge protocol to ensure robust and absolutely leakage proof convincing public verification with the help of private marks. We have tested our protocol for FPGA benchmarks. The results on overhead and robustness are encouraging.
Physical Unclonable Functions (PUFs) and Hardware Security