Anne Broadbent, Alex B. Grilo, Nagisa Hara, Arthur Mehta
In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs play an important role in security protocols such as in digital signatures and authentication schemes, as they enable a prover to demonstrate possession of certain information (such as a private key or a credential), without revealing it. A PoK is formally defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to any accepting prover. We extend this concept to the setting of a single classical verifier and multiple quantum provers and present the first statistical zero-knowledge (ZK) PoK proof system for problems in QMA. To achieve this, we establish the PoK property for the ZK protocol of Broadbent, Mehta, and Zhao (TQC 2024), which applies to the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers' strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state, the verifier also certifies that a prover has access to a quantum system, in particular, a ground state; this indicates a new level of verification for a proof of quantumness.
A decentralized oracle network is a good solution for blockchain interoperability, and a multisignature is a proper cryptographic primitive for off-chain aggregation where each participating signer’s public key can be identified during verification. An important requirement for the decentralized oracle network is that some important data requests may require high-reputation nodes to validate the external data, while some common data requests may need only low-cost nodes to execute the validation. Thus, we present a weighted Schnorr multisignature to meet this requirement, which is proven to be unforgeable. However, purely relying on the cryptographic scheme cannot fully identify each participating node’s reputation; thus, we design three on-chain contracts for recording and identifying the oracle nodes’ reputation and realizing the reword mechanism. The on-chain components (e.g., smart contracts) and the off-chain components (e.g., oracle nodes) constitute a whole blockchain interoperability system. We implement our system over the Ethereum platform and analyze its on-chain and off-chain costs.
We analyze developer activity across 10 major Ethereum repositories (totaling 129884 commits, 40550 issues) spanning 10 years to examine how events such as technical upgrades, market events, and community decisions impact development. Through statistical, survival, and network analyses, we find that technical events prompt increased activity before the event, followed by reduced commit rates afterwards, whereas market events lead to more reactive development. Core infrastructure repositories like Go-Ethereum exhibit faster issue resolution compared to developer tools, and technical events enhance core team collaboration. Our findings show how different types of events shape development dynamics, offering insights for project managers and developers in maintaining development momentum through major transitions. This work contributes to understanding the resilience of development communities and their adaptation to ecosystem changes.
Haotian Wu, Yuzhe Tang, Zhaoyan Shen, Jun Tao · 6 authors
Blockchain has become a popular paradigm for secure and immutable data storage. Despite its numerous applications across various fields, concerns regarding the user privacy and result integrity during data queries persist. Additionally, the need for rich query functionalities to harness the full potential of blockchain data remains an area ripe for exploration. In order to address these challenges, our paper first utilizes a framework based on the Trusted Execution Environment (TEE) and oblivious RAM technique to achieve both privacy and data integrity. To enhance the query efficiency over the entire blockchain, we then devise a two-level learned indexing methodology named TELEX within the TEE for both integer and string keys. We also propose different query processing algorithms for versatile query types, including exact queries, aggregate queries, Boolean queries, and range queries. By implementing the prototype and conducting extensive evaluation, we demonstrate the feasibility and remarkable improvement in efficiency compared to existing solutions.
This paper addresses the problem of the relationship between the correctness of the event diagram of distributed computing from the standpoint of communication between local processes of this computing and the existence of a logical clock for that diagram. The problem is analyzed using The Coq Proof Assistant software without assuming the fairness of the principle of excluded middle. That is, the obtained results are correct from the point of view of constructive logic, which is essential for computer science. It has been formally proved that the existence of a logical clock for distributed computing ensures the irreflexivity of the causal relation related to that computing. The conjecture about the fairness of the converse statement has been claimed. Keywords: distributed computing, cloud platform, blockchain, digital distributed ledgers, global time, logical clock, event ordering.
In today's increasingly interconnected world, the demand for efficient, resilient and fault tolerance distributed data communication systems is paramount. This research explores a novel alternative approach to address the challenges of traditional distributed systems. The study investigates the integration of cutting-edge technologies, such as decentralized networks, blockchain, and Software-Defined Wide Area Network (SD-WAN), to revolutionize data communication. This alternative approach aims to enhance system efficiency, scalability and reliability while reducing vulnerabilities associated with centralized systems. By leveraging decentralization principles, networking automation approaches and distributed ledger technology, it prioritizes data efficiency, integrity, security, presenting a transformative vision for network infrastructure. This research contributes to the ongoing discussions about distributed data transmission systems. It opens up a new perspective and paves the way for future achievements in this field.
Abstract The aim of this study is to design and implement a system that allows centralized blockchain institutions to prove their solvency. This system ensures that institutions do not misappropriate user assets and enhances trust between users and institutions. The article introduces the Groth‐16 zero‐knowledge proof algorithm from ZK‐SNARK (zero‐knowledge succinct non‐interactive argument of knowledge). The R1CS arithmetic circuit in the Groth‐16 algorithm effectively guarantees the authenticity and tamper‐resistance of the system's raw data sources. Additionally, it combines the use of Merkle Sum Trees and Sparse Merkle trees. The former enables users to perform distributed verification of solvency proofs, while the latter effectively hides the overall number of users. Finally, users verify the balances and the private key signatures of addresses in the institution's bulletin board. Together, these components form a comprehensive and distributed solvency proof solution. This solution is a pioneering solution in the field of blockchain solvency proofs and provides a secure, efficient, and privacy‐preserving method for centralized cryptocurrency service providers or Web3 enterprise custodians. It effectively addresses the challenge of proving an institution's possession of sufficient reserves to cover user assets without compromising user privacy or disclosing the institution's scale.
Modern database systems are expected to handle dynamic data whose characteristics may evolve over time. Many popular database benchmarks are limited in their ability to evaluate this dynamic aspect of the database systems. Those that use synthetic data generators often fail to capture the complexity and unpredictable nature of real data, while most real-world datasets are static and difficult to create high-volume, realistic updates for. This paper introduces CrypQ, a database benchmark leveraging dynamic, public Ethereum blockchain data. CrypQ offers a high-volume, ever-evolving dataset reflecting the unpredictable nature of a real and active cryptocurrency market. We detail CrypQ's schema, procedures for creating data snapshots and update sequences, and a suite of relevant SQL queries. As an example, we demonstrate CrypQ's utility in evaluating cost-based query optimizers on complex, evolving data distributions with real-world skewness and dependencies.
In database applications involving sensitive data, the dual imperatives of data confidentiality and provable (verifiable) query processing are important. This paper introduces PoneglyphDB, a database system that leverages non-interactive zero-knowledge proofs (ZKP) to support both confidentiality and provability. Unlike traditional databases, PoneglyphDB enhances confidentiality by ensuring that raw data remains exclusively with the host, while also enabling verifying the correctness of query responses by providing proofs to clients. The main innovation in this paper is proposing efficient ZKP designs (called circuits) for basic operations in SQL query processing. These basic operation circuits are then combined to form ZKP circuits for larger, more complex queries. PoneglyphDB's circuits are carefully designed to be efficient by utilizing advances in cryptography such as PLONKish-based circuits, recursive proof composition techniques, and designing with low-order polynomial constraints. We demonstrate the performance of PoneglyphDB with the standard TPC-H benchmark. Our experimental results show that PoneglyphDB can efficiently achieve both confidentiality and provability, outperforming existing state-of-the-art ZKP methods.
A group signature scheme in which signers are able to designate openers by specifying access structures over openers' attributes was introduced at CANDAR 2021, which is called GSdT. In this paper, we present a construction of GSdT from only symmetric-key primitives; pseudorandom functions, hash functions and commitments. Due to the features, our GSdT is expected to be secure against computational power of quantum computers. We first introduce syntax and security definitions in the static group model. Then, in our construction, the key ingredient is a non-interactive zero-knowledge proof of knowledge system that is constructed from the primitives in the “MPC-in-the-head” paradigm, owing the technique that was developed by Katz, Kolesnikov and Wang (ACM-CCS 2018). Our approach starts with their group signature scheme, but non-trivially extends the Merkle tree so that signers can treat (all-AND) boolean formulas as the access structures. According to our estimation, the signing time is less than 3.0 sec and the signature size is less than 0.5 MB in a scenario that the numbers of group members and attributes are 27and 23, respectively, and security to be attained is 128 bit quantum security.
Cardano is a Proof-of-Stake cryptocurrency with a market capitalisation in the tens of billions of USD and a daily volume of hundreds of millions of USD. In this paper we reflect on applying formal methods, functional architecture and Haskell to building Cardano. We describe our strategy, projects, lessons learned, the challenges we face, and how we propose to meet them.
In this paper, we study steady flows in data streams, which refers to the flows whose arrival rate is always non-zero and around a fixed value for several consecutive time windows. To find steady flows in real time, we propose a novel sketch-based algorithm, SteadySketch, aiming to accurately report steady flows with limited memory. To the best of our knowledge, this is the first work to define and find steady flows in data streams. The key novelty of SteadySketch is our proposed reborn technique, which reduces the memory requirement by 75%. Our theoretical proofs show that the negative impact of the reborn technique is small. Experimental results show that, compared with the two comparison schemes, SteadySketch improves the Precision Rate (PR) by around 79.5% and 82.8%, and reduces the Average Relative Error (ARE) by around$905.9\times $and$657.9\times $, respectively. Finally, we provide three concrete cases: cache prefetch, Redis and P4 implementation. As we will demonstrate, SteadySketch can effectively improve the cache hit ratio while achieving satisfying performance on both Redis and Tofino switches. All related codes of SteadySketch are available at GitHub.
Michał Król, Onur Ascigil, Sergi Reñé, Alberto Sonnino · 8 authors
The Ethereum Global Network (EGN) hosts a complete ecosystem of decentralized services, including blockchains such as Ethereum mainnet but also exchange markets, content delivery networks, and many more. Service discovery is a fundamental mechanism in the EGN, allowing new nodes to look up and connect to other nodes already participating in one of these services. The current service discovery of the EGN, DISCv5, is not scalable and efficient enough to support the current and future needs of the ecosystem. We present DISC-NG, a novel service discovery protocol for the EGN that is scalable, efficient, and secure. DISC-NG leverages the EGN-wide DHT to allow service participation advertisements to meet service discovery requests. DISC-NG compensates the unbalance in service popularity and minimizes the potential for abuse by malicious nodes. We implement DISC-NG in devp2p, the network stack used by the majority of clients connecting to the EGN, as well as in a large-scale simulator. DISC-NG can discover services in the EGN faster than DISCv5 while being more robust to malicious nodes. DISC-NG is now in a staging phase and scheduled for deployment as an improvement to DISCv5.
Elvira Albert, María García de la Banda, Alejandro Hernández-Cerezo, Alexey Ignatiev · 6 authors
Given a loop-free sequence of instructions, superoptimization techniques use a constraint solver to search for an equivalent sequence that is optimal for a desired objective. The complexity of the search grows exponentially with the length of the solution being constructed and the problem becomes intractable for large sequences of instructions. This paper presents a new approach to superoptimizing stack-bytecode via three novel components: (1) a greedy algorithm to refine the bound on the length of the optimal solution; (2) a new representation of the optimization problem as a set of weighted soft clauses in MaxSAT; (3) a series of domain-specific dominance and redundant constraints to reduce the search space for optimal solutions. We have developed a tool, named S uper S tack , which can be used to find optimal code translations of modern stack-based bytecode, namely WebAssembly or Ethereum bytecode. Experimental evaluation on more than 500,000 sequences shows the proposed greedy, constraint-based and SAT combination is able to greatly increase optimization gains achieved by existing superoptimizers and reduce to at least a fourth the optimization time.
Indika Kumara, Stefan Driessen, Tom van Eijk, Dario Di Nucci · 6 authors
Data mesh is an emerging decentralized approach to managing and generating value from analytical enterprise data at scale. It shifts the ownership of the data to the business domains closest to the data, promotes sharing and managing data as autonomous products, and uses a federated and auto-mated data governance model. This short tutorial introduces data mesh architecture to practitioners and researchers in the software architecture community. First, we present the key components of a data mesh architecture and discuss critical design decisions that should be made when designing and implementing data meshes in organizations. Then, we present the findings from the data mesh case studies we conducted at the three organizations in the Netherlands and Germany.
Amir M. Ebrahimi, Bram Adams, Gustavo A. Oliva, Ahmed E. Hassan
The proxy pattern is a well-known design pattern with numerous use cases in several sectors of the software industry. As such, the use of the proxy pattern is also a common approach in the development of complex decentralized applications (DApps) on the Ethereum blockchain. Despite the importance of proxy contracts, little is known about (i) how their prevalence changed over time, (ii) the ways in which developers integrate proxies in the design of DApps, and (iii) what proxy types are being most commonly leveraged by developers. This study bridges these gaps through a comprehensive analysis of Ethereum smart contracts, utilizing a dataset of 50 million contracts and 1.6 billion transactions as of September 2022. Our findings reveal that 14.2% of all deployed smart contracts are proxy contracts. We show that proxy contracts are being more actively used than non-proxy contracts. Also, the usage of proxy contracts in various contexts, transactions involving proxy contracts, and adoption of proxy contracts by users have shown an upward trend over time, peaking at the end of our study period. They are either deployed through off-chain scripts or on-chain factory contracts, with the former and latter being employed in 39.1% and 60.9% of identified usage contexts in turn. We found that while the majority (67.8%) of proxies act as an interceptor, 32.2% enables upgradeability. Proxy contracts are typically (79%) implemented based on known reference implementations with 29.4% being of type ERC-1167, a class of proxies that aims to cheaply reuse and clone contracts' functionality. Our evaluation shows that our proposed behavioral proxy detection method has a precision and recall of 100% in detecting active proxies. Finally, we derive a set of practical recommendations for developers and introduce open research questions to guide future research on the topic.
Alexandr Kuznetsov, Alex Rusnak, Anton Yezhov, Dzianis Kanonik · 6 authors
Zero-knowledge proofs have emerged as a powerful tool for enhancing privacy and security in blockchain applications. However, the efficiency and scalability of proof systems remain a significant challenge, particularly in the context of Merkle tree inclusion proofs. Traditional proof aggregation techniques based on AND logic suffer from a high verification complexity and data communication overhead, limiting their practicality for large-scale applications. In this paper, we propose a novel proof aggregation approach based on OR logic, which enables the generation of compact and universally verifiable proofs for Merkle tree inclusion. By adapting and extending the concept of OR composition from Sigma protocols, we achieve a proof size that is independent of the number of leaves in the tree, and verification can be performed using any single valid leaf hash. This represents a significant improvement over AND aggregation, which requires the verifier to process all leaf hashes. We formally define the OR aggregation logic; describe the process of generating universal proofs; and provide a comparative analysis that demonstrates the advantages of our approach in terms of proof size, verification data, and universality. Furthermore, we discuss the potential of combining OR and AND aggregation logics to create complex acceptance functions, enabling the development of expressive and efficient proof systems for various blockchain applications. The proposed techniques have the potential to significantly enhance the scalability, efficiency, and flexibility of zero-knowledge proof systems, paving the way for more practical and adaptive solutions in large-scale blockchain ecosystems.
Ethereum 2.0 is the second-largest cryptocurrency by market capitalization and a widely used smart contract platform. Therefore, examining the reliability of Ethereum 2.0's incentive mechanism is crucial, particularly its effectiveness in encouraging validators to adhere to the Ethereum 2.0's protocol. This paper studies the incentive mechanism of Ethereum 2.0 and evaluates its robustness by analyzing the interaction between block proposers and attesters in a single slot. To this end, we use Bayesian games to model the strategies of block proposers and attesters and calculate their expected utilities. Our results demonstrate that the Ethereum 2.0 incentive mechanism is incentive-compatible and promotes cooperation among validators. We prove that a Bayesian Nash equilibrium and an ex ante dominant strategy exist between the block proposer and attesters in a single slot. Our research provides a solid foundation for further analysis of Ethereum 2.0's incentive mechanism and insights for individuals considering participation as a validator in Ethereum 2.0.
Multiple sequence alignment (MSA) is a fundamental algorithm in bioinformatics. In a situation when the alignment might need to be protected while revealing the other information such the input sequences and the alignment score, zero knowledge proof can be used. In this paper, a validator checks the consistency between the input sequence and the alignment, and between the alignment and the alignment score. The validator is written in Circom language which will be compile into a circuit. Using a zero knowledge prove system called zkSNARK, a cryptographic proof is generates for the circuit and its input. This proof demonstrates that all inputs are consistent without revealing the actual alignment.
This article examines the significant challenges encountered in implementing sharding within distributed replication systems. It identifies the impediments of achieving consensus among large participant sets, leading to scalability, throughput, and performance limitations. These issues primarily arise due to the message complexity inherent in consensus mechanisms. In response, we investigate the potential of sharding to mitigate these challenges, analyzing current implementations within distributed replication systems. Additionally, we offer a comprehensive review of replication systems, encompassing both classical distributed databases as well as Distributed Ledger Technologies (DLTs) employing sharding techniques. Through this analysis, the article aims to provide insights into addressing the scalability and performance concerns in distributed replication systems.
The widespread availability of tools to collect and share spatial data enables us to produce a large amount of geographic information on a daily basis. This enormous production of spatial data requires scalable data management systems. Geospatial architectures have changed from clusters to cloud architectures and more parallel and distributed processing platforms to be able to tackle these challenges. Peer-to-peer (P2P) systems as a backbone of distributed systems have been established in several application areas such as web3, blockchains, and crypto-currencies. Unlike centralized systems, data storage in P2P networks is distributed across network nodes, providing scalability and no single point of failure. However, managing and processing queries on these networks has always been challenging. In this work, we propose a spatio-temporal indexing data structure, DSTree. DSTree does not require additional Distributed Hash Trees (DHTs) to perform multi-dimensional range queries. Inserting a piece of new geographic information updates only a portion of the tree structure and does not impact the entire graph of the data. For example, for time-series data, such as storing sensor data, the DSTree performs around 40% faster in spatio-temporal queries for small and medium datasets. Despite the advantages of our proposed framework, challenges such as 20% slower insertion speed or semantic query capabilities remain. We conclude that more significant research effort from GIScience and related fields in developing decentralized applications is needed. The need for the standardization of different geographic information when sharing data on the IPFS network is one of the requirements.
Principal Engineer, Discover Financial Services, Houston, TX, USA, AdisheshuReddy Kommera
The Event-Driven Data Mesh Integration pattern revolutionizes modern data sharing by blending eventdriven architecture and the data mesh paradigm. This innovative approach decentralizes data ownership, enabling organizational domains to manage their data autonomously while ensuring real-time responsiveness and seamless scalability. Central to the pattern are event broker layers, domain-oriented data producers, event enrichment nodes, and a self-serve data product catalog. Key features include schema validation, policy-based governance, and real-time enrichment, fostering efficiency, compliance, and agility. Integrating AI-powered self-healing mechanisms further enhances resilience, automates recovery processes, and optimizes resource allocation. Applications span various sectors, from operational systems to analytics pipelines, enabling real-time decision-making and continuous improvement. This approach empowers organizations to innovate faster while maintaining robust data governance, scalability, and interoperability across autonomous domains, paving the way for intelligent and dynamic data ecosystems.
Today’s organizations are seeking to develop new solutions to enhance the security, transparency, and accessibility of their cloud-based infrastructure. Integrating distributed ledger technology with cloud-based infrastructure can bring significant advantages to organizations but involves a complex process that requires meticulous planning, design, and execution. The process commences with choosing the suitable DLT platform, and one must possess a thorough understanding of distributed ledger technology and cloud computing technologies, including their unique features, capabilities, and compromises.