Blockchain Papers

Zhen Li, Qi Liao

No abstract is available for this record.

Manoj Tarambale

In the digital age, cryptographic systems are the most important part of safe communication. To protect data security, confidentiality, and validity, they need strong design frameworks. The math methods used in this paper are very important for designing and analyzing secure systems. As basic ideas, it looks at number theory, math, and complexity theory, with an emphasis on both old and new methods. Some important topics are the creation of prime numbers, modular arithmetic, elliptic curves, and finite fields, which are the basis for many encryption methods. The paper also talks about how complexity theory can be used to measure the strength of cryptography. It specifically talks about issues with discrete logarithms and integer factorization, which are at the heart of popular protocols like RSA and ECC. It also looks into lattice-based cryptography, which is seen as a strong option to quantum threats, and shows how hard it is to solve lattice issues. The study also looks at the design principles of symmetric cryptography, mainly block ciphers and stream ciphers, and how they use permutation groups and linear algebra to make sure that key plans and spread methods are safe. The paper also looks at secure hash functions, focusing on collision resistance, pre-image resistance, and how they are made using mathematics concepts such as Merkle-Damgård and sponge functions. Advanced topics like homomorphic encryption and zero-knowledge proofs show how mathematics and cryptography are increasingly coming together. They show how they can be used to make operations safe on protected data and privacy-preserving protocols. This paper gives a full picture of how mathematical theories and methods are used to build strong cryptographic systems by combining strict mathematical models with real-world cryptographic needs. The discussion stresses that the field is always changing because of new threats and improvements in computers. It also calls for constant scientific progress to make cryptography stronger against future problems.

Kaiyan Shi, Kaushik Chakraborty, Wen Yu Kon, Omar Amer · 6 authors

We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(η) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).

Tanish Aggarwal, Sudhakar Kumar, Sarjana Singh, Brij B. Gupta · 6 authors

Zero Knowledge Proofs (ZKPs), cryptographic protocols that allow a party to authenticate a transaction to another without disclosing additional information beyond the authenticity of the transaction, continue to have a significant impact on privacy, security, and integrity in applications. It addresses constraints such as computing costs, trust dimensions, and integration complexity, and proposes possible methods and techniques for future research. It emphasizes the importance of ZKP for improving privacy and security in digital systems highlights, the article emphasizes the importance of continuous innovation and further development of their standardization efforts. Proofs (ZKPs) have emerged as a powerful tool in cryptography, offering innovative solutions to privacy, security, and authentication challenges. This article provides an in-depth review of ZKPs, exploring their progress, challenges and future prospects in cryptography. It examines the basic concepts of ZKPs, their applications, and their impact on cryptographic protocols.

Junchao Chen, Alberto Sonnino, Lefteris Kokoris-Kogias, Mohammad Sadoghi

Sharding has emerged as a critical technique for enhancing blockchain system scalability. However, existing sharding approaches face unique challenges when applied to Directed Acyclic Graph (DAG)-based protocols that integrate expressive smart contract processing. Current solutions predominantly rely on coordination mechanisms like 2PC and require transaction read/write sets to optimize parallel execution. These requirements introduce two fundamental limitations: 1) additional coordination phases incur latency overhead, and 2) pre-declaration of read/write sets proves impractical for Turing-complete smart contracts with dynamic access patterns. This paper presents Thunderbolt, a novel sharding architecture for both single-shard transactions (Single-shard TXs) and cross-shard transactions (Cross-shard TXs) and enables nonblocking reconfiguration to ensure system liveness. Our design introduces 4 key innovations: 1) each replica serves dual roles as a full-shard representative and transaction proposer, employing the Execution-Order-Validation (EOV) model for Single-shard TXs and Order-Execution (OE) model for Cross-shard TXs. 2) we develop a DAG-based coordination protocol that establishes deterministic ordering between two transaction types while preserving concurrent execution capabilities. 3) we implement a dynamic concurrency controller that schedules Single-shard TXs without requiring prior knowledge of read/write sets, enabling runtime dependency resolution. 4) Thunderbolt introduces a nonblocking shard reconfiguration mechanism to address censorship attacks by featuring frequent shard re-assignment without impeding the construction of DAG nor blocking consensus. Thunderbolt achieves a 50x throughput improvement with 64 replicas compared to serial execution in the Tusk framework.

Peso Vilella, Antonio

Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2024, Director: Bruno Mazorra i Luis Victor Dieulefait

Kieran Mastel, William Slofstra

The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.

Paul Bilokon

No abstract is available for this record.

Nir Bitansky, Nathan Geier

No abstract is available for this record.

Yogev Bar-On, Yishay Mansour

A growing number of products use layer 2 solutions to expand the capabilities of primary blockchains like Ethereum, where computation is off-loaded from the root chain, and the results are published to it in bulk. Those include optimistic and zero-knowledge rollups, information oracles, and app-specific chains. This work presents an analysis of layer 2 blockchain strategies determining the optimal times for publishing transactions on the root chain. There is a trade-off between waiting for a better layer 1 gas price and the urgency to finalize layer 2 transactions. We present a model for the problem that captures this trade-off, generalizing previous works, and we analyze the properties of optimal publishing strategies. We show that such optimal strategies hold a computable simple form for a large class of cost functions.

Erica Blum, Derek Leung, Julian Loss, Jonathan Katz · 5 authors

The Algorand consensus protocol is interesting both in theory and in practice. On the theoretical side, to achieve adaptive security, it introduces the novel idea of player replaceability, where each step of the protocol is executed by a different randomly selected committee whose members remain secret until they send their first and only message. The protocol provides consistency under arbitrary network conditions and liveness under intermittent network partitions. On the practical side, the protocol is used to secure the Algorand cryptocurrency, whose total value is approximately 850M at the time of writing.

С. С. Гончаров, Andrey Nechesov

The increasing use of artificial intelligence algorithms, smart contracts, the internet of things, cryptocurrencies, and digital money highlights the need for secure and sustainable decentralized solutions. Currently, the blockchain technology serves as the backbone for most decentralized systems. However, the question of axiomatization of the blockchain theory in the first-order logic has been open until today, despite the efficient computational implementations of these systems. This did not allow one to formalize the blockchain structure, as well as to model and verify it using logical methods. This work introduces a finitely axiomatizable blockchain theory T that defines a class of blockchain structures K using the axioms of the first-order logic. The models of the theory T are well-known blockchain implementations with the proof of work consensus algorithm, including Bitcoin, Ethereum (PoW version), Ethereum Classic, and some others. By utilizing mathematical logic, we can study these models and derive new theorems of the theory T through automatic proofs. Also, the axiomatization of blockchain opens up new opportunities to develop blockchain-based systems that can help solve some of the open problems in the fields of artificial intelligence, robotics, cryptocurrencies, etc.

Fatma Hachicha, Yosra Ghabri, Khaled Guesmi, Ramzi Benkraiem

Cet article analyse la volatilité des cryptomonnaies à l’aide de la méthode de Monte-Carlo par chaînes de Markov (MCMC). L’objectif de cette étude est de trouver une technique plus efficace pour prévoir et estimer la volatilité, afin de fournir des informations cruciales aux gestionnaires de portefeuille et aux décideurs. Deux modèles ont été examinés : le modèle de volatilité stochastique autorégressive avec distribution t de Student (ARSV-t) et le modèle SVOL, en utilisant l’algorithme de Metropolis Hasting. Les résultats montrent que le modèle ARSV-t est plus performant que le modèle SVOL, surtout lorsqu’on traite des données financières hautement volatiles, telles que celles des cryptomonnaies. De plus, les prévisions obtenues avec le modèle ARSV-t sont plus précises que celles du modèle SVOL. Nous avons également constaté que la signification statistique des variables contrôlant la volatilité stochastique varie en fonction de la période d’estimation (COVID-19, guerre Russie-Ukraine). Ces résultats contribuent à améliorer notre compréhension des prévisions de la volatilité sur le marché des cryptomonnaies.

John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba · 6 authors

State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.

Suthee Ruangwises

In this paper, we propose a physical protocol to verify the first nonzero term of a sequence using a deck of cards. The protocol lets a prover show the value of the first nonzero term of a given sequence to a verifier without revealing which term it is. Our protocol uses $Θ(1)$ shuffles, which is asymptotically lower than that of an existing protocol of Fukusawa and Manabe which uses $Θ(n)$ shuffles, where $n$ is the length of the sequence. We also apply our protocol to construct zero-knowledge proof protocols for three well-known logic puzzles: ABC End View, Goishi Hiroi, and Toichika. These protocols enables a prover to physically show that he/she know solutions of the puzzles without revealing them.

Scott Aaronson, Shih‐Han Hung

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain $Ω(n)$ min-entropy, where $n$ is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits -- thereby "bootstrapping" from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol's output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most $n\sim 60$ qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.

Suthee Ruangwises, Mitsugu Iwamoto

Abstract Decomposition puzzles are pencil-and-paper logic puzzles that involve partitioning a rectangular grid into several regions to satisfy certain rules. In this paper, we construct a generic card-based protocol called printing protocol , which can be used to physically verify solutions of decompositon puzzles. We apply the printing protocol to develop card-based zero-knowledge proof protocols for two such puzzles: Five Cells and Meadows. These protocols allow a prover to physically show that he/she knows solutions of the puzzles without revealing them.

David Pointcheval

Electronic voting is one of the most interesting application of modern cryptography, as it involves many innovative tools (such as homomorphic public-key encryption, non-interactive zero-knowledge proofs, and distributed cryptography) to guarantee several a priori contradictory security properties: the integrity of the tally and the privacy of the individual votes. While many efficient solutions exist for honest-but-curious voters, that follow the official procedure but try to learn more than just the public result, preventing attacks from malicious voters is much more complex: when voters may have incentive to send biased ballots, the privacy of the ballots is much harder to satisfy, whereas this is the crucial security property for electronic voting. We present a new technique to prove that an ElGamal ciphertext contains a message from a specific subset (quasi-adaptive NIZK of subset membership), using linearly-homomorphic signatures. The proofs are both quite efficient to generate, allowing the use of low-power devices to vote, and randomizable, which is important for the strong receipt-freeness property. They are well-suited to prevent vote-selling and replay attacks, which are the main threats against the privacy in electronic voting, with security proofs in the generic group model and the random oracle model.

Xinxuan Zhang, Yi Deng

No abstract is available for this record.

Ben Charoenwong, Robert M. Kirby, Jonathan Reiter

We examine which decentralized finance architectures enable meaningful regulation by combining financial and computational theory. We show via deduction that a decentralized and permissionless Turing-complete system cannot provably comply with regulations concerning anti-money laundering, know-your-client obligations, some securities restrictions and forms of exchange control. Any system that claims to follow regulations must choose either a form of permission or a less-than-Turing-complete update facility. Compliant decentralized systems can be constructed only by compromising on the richness of permissible changes. Regulatory authorities must accept new tradeoffs that limit their enforcement powers if they want to approve permissionless platforms formally. Our analysis demonstrates that the fundamental constraints of computation theory have direct implications for financial regulation. By mapping regulatory requirements onto computational models, we characterize which types of automated compliance are achievable and which are provably impossible. This framework allows us to move beyond traditional debates about regulatory effectiveness to establish concrete boundaries for automated enforcement.

Suthee Ruangwises

Ball sort puzzle is a popular logic puzzle consisting of several bins containing balls of multiple colors. Each bin works like a stack; a ball has to follow the last-in first-out order. The player has to sort the balls by color such that each bin contains only balls of a single color. In this paper, we propose a physical zero-knowledge proof protocol for the ball sort puzzle using a deck of playing cards, which enables a prover to physically show that he/she knows a solution with $t$ moves of the ball sort puzzle without revealing it. Our protocol is the first zero-knowledge proof protocol for an interactive puzzle involving moving objects.

Brian Wu, Bridget Wu

Alan Turing, a mathematician, logician, and computer scientist, is widely considered to be the father of computer science. In the 1930s, he invented the Universal Turing Machine. Assuming enough memory is available, the Turing Machine could calculate anything using only two symbols (0 or 1) arranged in a potentially infinite one-dimensional sequence. This is the basis for the first computer. Turing-completeness, therefore, refers to any computation problem that can be solved and implemented in a Turing-complete environment, no matter how complex.

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

No abstract is available for this record.

Zhenrui Zhang

People are getting familiar with cryptocurrencies because of the rapid development of cryptography, and bitcoin, a traditional decentralized digital currency, becomes famous. Thus, it is necessary to establish a digital currency allocation framework. Two existing methods both share the same goal of reaching blockchain consensus; however, the processes are different: The proof of Work system is completely related to tasks, but the Proof of Stake system is related to tokens. Hence, service providers are more than glad to apply the Proof of Work theory after distinguishing the difference between these two systems; this system which does not have high limitations is more fair and balanced. To enhance the traditional Proof of Work system, Artificial Intelligence can properly help and make the new framework works more efficiently. AI model can pre-assign a trustworthy score via the IP address, and then it can take the responsibility to generate the puzzle for the qualification. After the model verifies the output, the trustworthy score can increase or decrease based on the performance. Finally, it can establish a loop from the trustworthy score to puzzle difficulty, and then back to the trustworthy score. Therefore, an AI assistant can accurately monitor the entire transaction process and ensure validation to be environmentally friendly.