Federated Learning (FL) emerges as a viable solution to facilitate data collaboration, enabling multiple clients to collaboratively train a machine learning (ML) model under the supervision of a central server while ensuring the confidentiality of their raw data. However, existing studies have unveiled two main risks: (i) the potential for the server to infer sensitive information from the client's uploaded updates (i.e., model gradients), compromising client input privacy, and (ii) the risk of malicious clients uploading malformed updates to poison the FL model, compromising input integrity. Recent works utilize secure aggregation with zero-knowledge proofs (ZKP) to guarantee input privacy and integrity in FL. Nevertheless, they suffer from extremely low efficiency and, thus, are impractical for real deployment. In this paper, we propose a novel and highly efficient approach RiseFL for secure and verifiable data collaboration, ensuring input privacy and integrity simultaneously. Firstly, we devise a probabilistic integrity check method that transforms strict checks into a hypothesis test problem, offering great optimization opportunities. Secondly, we introduce a hybrid commitment scheme to satisfy Byzantine robustness with improved performance. Thirdly, we present an optimized ZKP generation and verification technique that significantly reduces the ZKP cost based on probabilistic integrity checks. Furthermore, we theoretically prove the security guarantee of RiseFL and provide a cost analysis compared to state-of-the-art baselines. Extensive experiments on synthetic and real-world datasets suggest that our approach is effective and highly efficient in both client computation and communication. For instance, RiseFL is up to 28x, 53x, and 164x faster than baselines ACORN, RoFL, and EIFFeL for the client computation.
Firas Hamila, Mohammad Hamad, Daniel Costa Salgado, Sebastian Steinhorst
Abstract With the rapid expansion of IoT devices and their applications, there is an increasing demand for efficient and secure authentication mechanisms to protect against unauthorized access. Traditional authentication mechanisms face limitations regarding computational speed, communication costs, and vulnerability to cyber-attacks. Zero-knowledge proof (ZKP) protocols have emerged as an effective solution for achieving secure and efficient authentication in such environments without revealing sensitive information. Among ZKP protocols, $$\Sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocols, a class of interactive ZKP protocols, have been employed for their efficiency and security. However, their interactive nature necessitates multiple rounds of communication, which can reduce efficiency and increase communication overhead for resource-constrained devices. Many works have aimed to eliminate the interaction of $$\Sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocols by utilizing a transformation called the Fiat–Shamir transformation (FST). However, there is still a concern regarding the soundness of the FST as it can sometimes convert a secure $$\Sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocol into an insecure non-interactive zero-knowledge (NIZK) authentication scheme. In this paper, we propose an approach for transforming $$\Sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocols into a NIZK protocol based on the FST, yielding significant enhancements in efficiency, communication overhead reduction, and elimination of interaction. Our proposed protocol enables the completion of the authentication process in a single request while also strengthening the soundness of $$\Sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocols in comparison with the traditional FST by requiring two authentication factors instead of one. To demonstrate our approach’s robustness, we conducted comprehensive informal and formal security analyses (using the Tamarin-Prover). Our protocol demonstrated completeness, soundness, zero-knowledge properties, and robustness against attacks, including eavesdropping, message modification, replay, and brute force attacks. Additionally, our performance analysis displayed a remarkable 50% improvement in computational cost compared to traditional $$\Sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Σ</mml:mi> </mml:math> -protocols, underscoring its efficiency for practical use.
Blockchain technology finds widespread application across various fields due to its key features such as immutability, reduced costs, decentralization, and transparency. The security of blockchain relies on elements like hashing, digital signatures, and cryptography. However, the emergence of quantum computers and supporting algorithms poses a threat to blockchain security. These quantum algorithms pose a significant threat to both public-key cryptography and hash functions, compelling the redesign of blockchain architectures. This paper investigates the status quo of the post-quantum, quantum-safe, or quantum-resistant cryptosystems within the framework of blockchain. This study starts with a fundamental overview of both blockchain and quantum computing, examining their reciprocal influence and evolution. Subsequently, a comprehensive literature review is conducted focusing on Post-Quantum Distributed Ledger Technology (PQDLT). This research emphasizes the practical implementation of these protocols and algorithms providing extensive comparisons of characteristics and performance. This work will help to foster further research at the intersection of post-quantum cryptography and blockchain systems and give prospective directions for future PQDLT researchers and developers.
Josep LluÃs Ferrer Gomila, M. Francisca Hinarejos
In this article, we present the first proposal for contract signing based on blockchain that meets the requirements of fairness, hard-timeliness, and bc-optimism. The proposal, thanks to the use of blockchain, does not require the use of trusted third parties (TTPs), thus avoiding a point of failure and the problem of signatories having to agree on a TTP that is trusted by both. The presented protocol is fair because it is designed such that no honest signatory can be placed at a disadvantage. It meets the hard-timeliness requirement because both signatories can end the execution of the protocol at any time they wish. Finally, the proposal is bc-optimistic because blockchain functions are only executed in case of exception (and not in each execution of the protocol), with consequent savings when working with public blockchains. No previous proposal simultaneously met these three requirements. In addition to the above, this article clarifies the concept of timeliness, which previously has been defined in a confusing way (starting with the authors who used the term for the first time). We conducted a security review that allowed us to verify that our proposal meets the desired requirements. Furthermore, we provide the specifications of a smart contract designed for the Ethereum blockchain family and verified the economic feasibility of the proposal, ensuring it can be aligned with the financial requirements of different scenarios.
A zeroknowledge proof is a game between a prover and a verifier, where the aim of the prover is to present the correctness of an assertion without giving the actual proof. This enables systems to achieve privacy with transparency and, if required, compliance. Zero knowledge proofs have been used in protection of data in healthcare and other systems, anonymous verifiable voting, financial systems like digital currencies, secure exchange of digital assets, secure remote biometric authentication, secure auction, and blockchain. The challenge of zero-knowledge proofs is that they are computationally hard to produce, some implementations need a trusted third party for setup and system initialization, some require efficiency optimization methods. Moreover, common algorithms cannot resist quantum computing attacks warranting research in the area.
In recent years, the increasing prevalence of digital transactions and data sharing has underscored the critical importance of privacy and security in the digital realm. Blockchain technology, initially designed to support cryptocurrencies like Bitcoin, has evolved into a versatile platform with the potential to provide trust, transparency, and data immutability in a wide range of applications. Concurrently, zero-knowledge proofs have emerged as a pioneering approach to safeguarding data privacy, allowing parties to validate information without disclosing the underlying data. This review paper thoroughly investigates the convergence of blockchain technology and zero-knowledge proofs, aiming to understand how their synergy can foster privacy-preserving transactions. We examine the foundational principles of zero-knowledge proofs, their theoretical underpinnings, and practical implementation within blockchain networks. Through a comprehensive analysis, we assess the effectiveness of this amalgamation in protecting sensitive data and consider its applicability to diverse use cases. This review provides a detailed exploration of the synergistic potential of blockchain and zero-knowledge proofs in reshaping the landscape of data privacy in an increasingly interconnected world.
The privacy concern in smart contract applications continues to grow, leading to the proposal of various schemes aimed at developing comprehensive and universally applicable privacy-preserving smart contract (PPSC) schemes. However, the existing research in this area is fragmented and lacks a comprehensive system overview. This paper aims to bridge the existing research gap on PPSC schemes by systematizing previous studies in this field. The primary focus is on two categories: PPSC schemes based on cryptographic tools like zero-knowledge proofs, as well as schemes based on trusted execution environments. In doing so, we aim to provide a condensed summary of the different approaches taken in constructing PPSC schemes. Additionally, we also offer a comparative analysis of these approaches, highlighting the similarities and differences between them. Furthermore, we shed light on the challenges that developers face when designing and implementing PPSC schemes. Finally, we delve into potential future directions for improving and advancing these schemes, discussing possible avenues for further research and development.
Traditional cloud-centric approaches to medical data sharing pose risks related to real-time performance, security, and stability. Medical and healthcare data encounter challenges like data silos, privacy breaches, and transmission latency. In response to these challenges, this paper introduces a blockchain-based framework for trustworthy medical data sharing in edge computing environments. Leveraging healthcare consortium edge blockchains, this framework enables fine-grained access control to medical data. Specifically, it addresses the real-time, multi-attribute authorization challenge in CP-ABE through a Distributed Attribute Authorization strategy (DAA) based on blockchain. Furthermore, it tackles the key security issues in CP-ABE through a Distributed Key Generation protocol (DKG) based on blockchain. To address computational resource constraints in CP-ABE, we enhance a Distributed Modular Exponentiation Outsourcing algorithm (DME) and elevate its verifiable probability to "1". Theoretical analysis establishes the IND-CPA security of this framework in the Random Oracle Model. Experimental results demonstrate the effectiveness of our solution for resource-constrained end-user devices in edge computing environments.
Haojia Sun, K. Ranjith Singh, Jan-Paul Ramos-Dávila, Jonathan Aldrich · 5 authors
Blockchains facilitate secure resource transactions through smart contracts, yet these digital agreements are prone to vulnerabilities, particularly when interacting with external contracts, leading to substantial monetary losses. Traditional verification techniques fall short in providing comprehensive security assurances, especially against re-entrancy attacks, due to the unavailable implementations of external contracts. This paper introduces an incremental approach: gradual verification. We combine static and dynamic verification techniques to enhance security, guarantee soundness and flexibility, and optimize resource usage in smart contract interactions. By implementing a prototype for gradually verifying Algorand smart contracts via the pyTEAL language, we demonstrate the effectiveness of our approach, contributing to the safe and efficient execution of smart contracts.
Abstract The application of healthcare systems has led to an explosive growth in personal electronic health records (EHRs). These EHRs are generated from different healthcare institutions and stored in cloud data centers, respectively. However, data owners lose the authority to control and track their private and sensitive EHRs. In fact, data owners cannot establish rules for EHRs exchanging and sharing, nor can they verify the integrity of EHRs stored in semi-trusted clouds. Hence, a individual-centric access control framework is required to realize data access control. In this study, we construct a data access control framework, which integrates the decentralized smart contracts and role-based access control (RBAC) to provide fine grained data access control services. Besides, this scheme allows data owners to define access control policies using JavaScript Object Notation (JSON) and further translate these policies into immutable blockchain transactions. Furthermore, we combine blockchain and bilinear mapping to design a data integrity verification system for users to check the integrity of their cloud stored EHRs. Finally, we analyze the security of this scheme and develop a prototype system to evaluate the performance. Both theoretical analysis and experiment results indicate that this scheme can realize fine-grained data access control and efficient data integrity verification
Md. Rahat Hasan, Ammar Alazab, Siddhartha Barman Joy, Mohammed Nasir Uddin · 9 authors
The Internet of Things (IoT) has recently attracted much interest from researchers due to its diverse IoT applications. However, IoT systems encounter additional security and privacy threats. Developing an efficient IoT system is challenging because of its sophisticated network topology. Effective access control is required to ensure user privacy in the Internet of Things. Traditional access control methods are inappropriate for IoT systems because most conventional access control approaches are designed for centralized systems. This paper proposes a decentralized access control framework based on smart contracts with three parts: initialization, an access control protocol, and an inspection. Smart contracts are used in the proposed framework to store access control policies safely on the blockchain. The framework also penalizes users for attempting unauthorized access to the IoT resources. The smart contract was developed using Remix and deployed on the Ropsten Ethereum testnet. We analyze the performance of the smart contract-based access policies based on the gas consumption of blockchain transactions. Further, we analyze the system’s security, usability, scalability, and interoperability performance.
Mohammed Mujeer Ulla, Preethi Preethi, Md. Sameeruddin Khan, Deepak S. Sakkari
Very recent attacks like ladder leaks demonstrated the feasibility of recovering private keys with side-channel attacks using just one bit of secret nonce. ECDSA nonce bias can be exploited in many ways. Some attacks on ECDSA involve complicated Fourier analysis and lattice mathematics. This paper will enable cryptographers to identify efficient ways in which ECDSA can be cracked on curves NIST256p, SECP256k1, NIST521p, and weak nonce, kind of attacks that can crack ECDSA and how to protect yourself. Initially, we begin with an ECDSA signature to sign a message using the private key and validate the generated signature using the shared public key. Then we use a nonce or a random value to randomize the generated signature. Every time we sign, a new verifiable random nonce value is created, and a way in which the intruder can discover the private key if the signer leaks any one of the nonce values. Then we use Lenstra–Lenstra–Lovasz (LLL) method as a black box, we will try to attack signatures generated from bad nonce or bad random number generator (RAG) on NIST256p, SECP256k1 curves. The combination of nonce generation, post-message signing, and validation in ECDSA helps achieve Uniqueness, Authentication, Integrity, and Non-Repudiation. The analysis is performed by considering all three curves for the implementation of the Elliptic Curve Digital Signature Algorithm (ECDSA). The comparative analysis for each of the selected curves in terms of computational time is done with the leak of nonce and with the Lenstra–Lenstra–Lovasz method to crack ECDSA. The average computational costs to break ECDSA with curves NIST256p, NIST521p, and SECP256k1 are 0.016, 0.34,0.46 respectively which is almost zero depicting the strength of the algorithm. The average computational costs to break ECDSA with curves SECP256K1 and NIST256p using LLL are 2.9 and 3.4 respectively
John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen
We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled to an equivalent $3$-message argument system, mirroring the transformation for quantum proof systems [KW00, KKMV07]. As immediate applications, we show how to derive hardness amplification theorems for quantum bit commitment schemes (answering a question of Yan [Yan22]), EFI pairs (answering a question of Brakerski, Canetti, and Qian [BCQ23]), public-key quantum money schemes (answering a question of Aaronson and Christiano [AC13]), and quantum zero-knowledge argument systems. We also derive an XOR lemma [Yao82] for quantum predicates as a corollary.
In the rapidly evolving landscape of decentralized systems, ensuring the integrity and trustworthiness of smart contracts is paramount for developers. This paper presents a comprehensive strategy for enhancing smart contract security by focusing on specific high-risk areas, including Integer Overflow, Dangerous Delegate Calls, Timestamp Dependency, Reentrancy Vulnerabilities, Race Conditions, and Sybil attacks. Despite the growing significance of smart contracts in blockchain ecosystems, a notable research gap exists in the development of specialized tools capable of providing real-time vulnerability detection and mitigation guidance. To bridge this gap, our research introduces the ‘GRIFFIN’ - Smart Contracts. Vulnerability Detector is a powerful tool that has been rigorously tested and validated. Our study has yielded significant results, demonstrating the efficacy of the GRIFFIN in proactively identifying and mitigating critical vulnerabilities within a diverse dataset of 12,000 real-world solidity smart contracts. The tool leverages state-of-the-art static analysis techniques and machine learning algorithms, achieving superior accuracy rates when compared to existing solutions. This heightened accuracy not only empowers developers but also boosts the overall robustness and dependability of smart contract ecosystems. The cornerstone of our research is the development and validation of a practical, user-centric solution. By providing actionable insights, code snippets, and real-time feedback to developers, GRIFFIN equips them with the knowledge and tools needed to address vulnerabilities swiftly and effectively. This innovative approach is not merely an academic endeavor but a significant stride towards cultivating resilient and dependable smart contract environments. It instills a culture of security-conscious development practices, ensuring that the smart contracts crucial to decentralized systems can operate with the highest level of trust and reliability. Index Terms— Smart Contracts; Integer overflow; DangerousDelegate call; Timestamp Dependence; Reentrancy Attack; RaceCondition; Sybil Attack; Static Analysis; Detection
Blockchains add transactions to a distributed shared ledger by arriving at consensus on sets of transactions contained in blocks. This provides a total ordering on a set of global transactions. However, total ordering is not enough to satisfy application semantics under the Byzantine fault model. This is due to the fact that malicious miners and clients can collaborate to add their own transactions ahead of correct clients' transactions in order to gain application level and financial advantages. These attacks fall under the umbrella of front-running attacks. Therefore, total ordering is not strong enough to preserve application semantics. In this paper, we propose causality preserving total order as a solution to this problem. The resulting Blockchains will be stronger than traditional consensus based blockchains and will provide enhanced security ensuring correct application semantics in a Byzantine setting.
The rapid development of the Internet of Things (IoT) has resulted in vast amounts of widely distributed data. Sharing these data can spur innovative advancements and enhance service quality. However, conventional data-sharing methods often involve third-party intermediaries, posing risks of single-point failures and privacy leaks. Moreover, these traditional sharing methods lack a secure transaction model to compensate for data sharing, which makes ensuring fair payment between data consumers and providers challenging. Blockchain, as a decentralized, secure, and trustworthy distributed ledger, offers a novel solution for data sharing. Nevertheless, since all nodes on the blockchain can access on-chain data, data privacy is inadequately protected, and traditional privacy-preserving methods like anonymization and generalization are ineffective against attackers with background knowledge. To address these issues, this paper proposes a decentralized, privacy-preserving, and fair data transaction model based on blockchain technology. We designed an adaptive local differential privacy algorithm, MDLDP, to protect the privacy of transaction data. Concurrently, verifiable encrypted signatures are employed to address the issue of fair payment during the data transaction process. This model proposes a committee structure to replace the individual arbitrator commonly seen in traditional verifiable encrypted signatures, thereby reducing potential collusion between dishonest traders and the arbitrator. The arbitration committee leverages threshold signature techniques to manage arbitration private keys. A full arbitration private key can only be collaboratively constructed by any arbitrary t members, ensuring the key’s security. Theoretical analyses and experimental results reveal that, in comparison to existing approaches, our model delivers enhanced transactional security. Moreover, while guaranteeing data availability, MDLDP affords elevated privacy protection.
Federated learning, as one of the three main technical routes for privacy computing, has been widely studied and applied in both academia and industry. However, malicious nodes may tamper with the algorithm execution process or submit false learning results, which directly affects the performance of federated learning. In addition, learning nodes can easily obtain the global model. In practical applications, we would like to obtain the federated learning results only by the demand side. Unfortunately, no discussion on protecting the privacy of the global model is found in the existing research. As emerging cryptographic tools, the zero-knowledge virtual machine (ZKVM) and homomorphic encryption provide new ideas for the design of federated learning frameworks. We have introduced ZKVM for the first time, creating learning nodes as local computing provers. This provides execution integrity proofs for multi-class machine learning algorithms. Meanwhile, we discuss how to generate verifiable proofs for large-scale machine learning tasks under resource constraints. In addition, we implement the fully homomorphic encryption (FHE) scheme in ZKVM. We encrypt the model weights so that the federated learning nodes always collaborate in the ciphertext space. The real results can be obtained only after the demand side decrypts them using the private key. The innovativeness of this paper is demonstrated in the following aspects: 1. We introduce the ZKVM for the first time, which achieves zero-knowledge proofs (ZKP) for machine learning tasks with multiple classes and arbitrary scales. 2. We encrypt the global model, which protects the model privacy during local computation and transmission. 3. We propose and implement a new federated learning framework. We measure the verification costs under different federated learning rounds on the IRIS dataset. Despite the impact of homomorphic encryption on computational accuracy, the framework proposed in this paper achieves a satisfactory 90% model accuracy. Our framework is highly secure and is expected to further improve the overall efficiency as cryptographic tools continue to evolve.
Erkan Tairi, Pedro Moreno-Sánchez, Clara Schneidewind
The scalability and interoperability challenges in current cryptocurrencies have motivated the design of cryptographic protocols that enable efficient applications on top and across widely used cryptocurrencies such as Bitcoin or Ethereum. Examples of such protocols include (virtual) payment channels, atomic swaps, oracle-based contracts, deterministic wallets, and coin mixing services. Many of these protocols are built upon minimal core functionalities supported by a wide range of cryptocurrencies. Most prominently, adaptor signatures (AS) have emerged as a powerful tool for constructing blockchain protocols that are (mostly) agnostic to the specific logic of the underlying cryptocurrency. Even though AS-based protocols are built upon the same cryptographic principles, there exists no modular and faithful way for reasoning about their security. Instead, all the works analyzing such protocols focus on reproving how adaptor signatures are used to cryptographically link transactions while considering highly simplified blockchain models that do not capture security-relevant aspects of transaction execution in blockchain-based consensus.
We introduce the first practical protocols for fully decentralized sealed-bid auctions using timed commitments. Timed commitments ensure that the auction is finalized fairly even if all participants drop out after posting bids or if n bidders collude to try to learn the nth bidder's bid value. Our protocols rely on a novel non-malleable timed commitment scheme which efficiently supports range proofs to establish that bidders have sufficient funds to cover a hidden bid value. This allows us to penalize users who abandon bids for exactly the bid value, while supporting simultaneous bidding in multiple auctions with a shared collateral pool. Our protocols are concretely efficient and we have implemented them in an Ethereum-compatible smart contract which automatically enforces payment and delivery of an auctioned digital asset.
Sylvain Chatel, Christian Mouchet, Ali Utkan Şahin, Apostolos Pyrgelis · 6 authors
Multiparty fully homomorphic encryption (MFHE) schemes enable multiple parties to efficiently compute functions on their sensitive data while retaining confidentiality. However, existing MFHE schemes guarantee data confidentiality and the correctness of the computation result only against honest-but-curious adversaries. In this work, we provide the first practical construction that enables the verification of MFHE operations in zero-knowledge, protecting MFHE from malicious adversaries. Our solution relies on a combination of lattice-based commitment schemes and proof systems which we adapt to support both modern FHE schemes and their implementation optimizations. We implement our construction in PELTA. Our experimental evaluation shows that PELTA is one to two orders of magnitude faster than existing techniques in the literature.
Yibin Yang, David Heath, Carmit Hazay, Vladimir Kolesnikov · 5 authors
Vector Oblivious Linear Evaluation (VOLE) supports fast and scalable interactive Zero-Knowledge (ZK) proofs. Despite recent improvements to VOLE-based ZK, compiling proof statements to a control-flow oblivious form (e.g., a circuit) continues to lead to expensive proofs. One useful setting where this inefficiency stands out is when the statement is a disjunction of clauses \mathcalL _1 Å‚or \cdots Å‚or \mathcalL _B. Typically, ZK requires paying the price to handle all B branches. Prior works have shown how to avoid this price in communication, but not in computation.
Despite the notable advances in the development of high-assurance, verified implementations of cryptographic protocols, such implementations typically face significant performance overheads, particularly due to the penalties induced by formal verification and automated extraction of executable code. In this paper, we address some core performance challenges facing computer-aided cryptography by presenting a formal treatment for accelerating such verified implementations based on multiple generic optimizations covering parallelism and memory access. We illustrate our techniques for addressing such performance bottlenecks using the Line-Point Zero-Knowledge (LPZK) protocol as a case study. Our starting point is a new verified implementation of LPZK that we formalize and synthesize using EasyCrypt; our first implementation is developed to reduce the proof effort and without considering the performance of the extracted executable code. We then show how such (automatically) extracted code can be optimized in three different ways to obtain a 3000x speedup and thus matching the performance of the manual implementation of LPZK of lpzkv2.[13] We obtain such performance gains by first modifying the algorithmic specifications, then by adopting a provably secure parallel execution model, and finally by optimizing the memory access structures. All optimizations are first formally verified inside EasyCrypt, and then executable code is automatically synthesized from each step of the formalization. For each optimization, we analyze performance gains resulting from it and also address challenges facing the computer-aided security proofs thereof, and challenges facing automated synthesis of executable code with such an optimization.
Yuyang Sang, Ning Luo, Samuel Judson, Ben Chaimberg · 8 authors
A zero-knowledge proof (ZKP) is a powerful cryptographic primitive used in many decentralized or privacy-focused applications. However, the high overhead of ZKPs can restrict their practical applicability. We design a programming language, Ou, aimed at easing the programmer's burden when writing efficient ZKPs, and a compiler framework, Lian, that automates the analysis and distribution of statements to a computing cluster. Ou uses programming language semantics, formal methods, and combinatorial optimization to automatically partition an Ou program into efficiently sized chunks for parallel ZK-proving and/or verification. We contribute: (1) A front-end language where users can write proof statements as imperative programs in a familiar syntax; (2) A compiler architecture and implementation that automatically analyzes the program and compiles it into an optimized IR that can be lifted to a variety of ZKP constructions; and (3) A cutting algorithm, based on Pseudo-Boolean optimization and Integer Linear Programming, that reorders instructions and then partitions the program into efficiently sized chunks for parallel evaluation and efficient state reconciliation.
Nils Fleischhacker, Gottfried Herold, Mark Simkin, Zhenfei Zhang
Multi-signatures allow for compressing many signatures for the same message that were generated under independent keys into one small aggregated signature. This primitive is particularly useful for proof-of-stake blockchains, like Ethereum, where the same block is signed by many signers, who vouch for the block's validity. Being able to compress all signatures for the same block into a short string significantly reduces the on-chain storage costs, which is an important efficiency metric for blockchains.