The hardness of highly-structured computational problems gives rise to a variety of public-key primitives. On one hand, the structure exhibited by such problems underlies the basic functionality of public-key primitives, but on the other hand it may endanger public-key cryptography in its entirety via potential algorithmic advances. This subtle interplay initiated a fundamental line of research on whether structure is inherently necessary for cryptography, starting with Rudich’s early work (PhD Thesis '88) and recently leading to that of Bitansky, Degwekar and Vaikuntanathan (CRYPTO '17). Identifying the structure of computational problems with their corresponding complexity classes, Bitansky et al. proved that a variety of public-key primitives (e.g., public-key encryption, oblivious transfer and even functional encryption) cannot be used in a black-box manner to construct either any hard language that has NP-verifiers both for the language itself and for its complement, or any hard language (and even promise problem) that has a statistical zero-knowledge proof system - corresponding to hardness in the structured classes NP ∩ coNP or SZK, respectively, from a black-box perspective. In this work we prove that the same variety of public-key primitives do not inherently require even very little structure in a black-box manner: We prove that they do not imply any hard language that has multi-prover interactive proof systems both for the language and for its complement - corresponding to hardness in the class MIP ∩ coMIP from a black-box perspective. Conceptually, given that MIP = NEXP, our result rules out languages with very little structure. Already the cases of languages that have IP or AM proof systems both for the language itself and for its complement, which we rule out as immediate corollaries, lead to intriguing insights. For the case of IP, where our result can be circumvented using non-black-box techniques, we reveal a gap between black-box and non-black-box techniques. For the case of AM, where circumventing our result via non-black-box techniques would be a major development, we both strengthen and unify the proofs of Bitansky et al. for languages that have NP-verifiers both for the language itself and for its complement and for languages that have a statistical zero-knowledge proof system.
This paper applies biomimetic engineering to the problem of permissionless Byzantine consensus and achieves results that surpass the prior state of the art by four orders of magnitude. It introduces a biologically inspired asymmetric Sybil-resistance mechanism, Proof-of-Balance, which can replace symmetric Proof-of-Work and Proof-of-Stake weighting schemes.
The biomimetic mechanism is incorporated into a permissionless blockchain protocol, Key Retroactivity Network Consensus (KRNC), which delivers ~40,000 times the security and speed of today's decentralized ledgers. KRNC allows the fiat money that the public already owns to be upgraded with cryptographic inflation protection, eliminating the problems inherent in bootstrapping new currencies like Bitcoin and Ethereum.
The paper includes two independently significant contributions to the literature. First, it replaces the non-structural axioms invoked in prior work with a new formal method for reasoning about trust, liveness, and safety from first principles. Second, it demonstrates how two previously overlooked exploits, book-prize attacks and pseudo-transfer attacks, collectively undermine the security guarantees of all prior permissionless ledgers.
Inspired by the work of Ghadafi and Groth (ASIACRYPT 2017) on a certain type of computational hardness assumptions in cyclic groups (which they call ``target assumptions''), we initiate an analogous work on another type of hardness assumptions, namely the ``knowledge-of-exponent'' assumptions (KEAs). Originally introduced by Damgard to construct practical encryption schemes secure against chosen ciphertext attacks, KEAs have subsequently been used primarily to construct succinct non-interactive arguments of knowledge (SNARKs), and proved to be inherent to such constructions. Since SNARKs (and their zero-knowledge variant, zk-SNARKs) are already used in practice in such systems as the Zcash digital currency, it can be expected that the use of KEAs will increase in the future, which makes it important to have a good understanding of those assumptions. Using a proof technique first introduced by Bellare and Palacio (but acknowledged by them as being due to Halevi), we first investigate the internal structure of the q-power knowledge-of-exponent (q-PKE) family of assumptions introduced by Groth, which is thus far the most general variant of KEAs. We then introduce a generalisation of the q-PKE family, and show that it can be simplified.
Ayushi Sharma, Shashwat Tiwari, Nitin Arora, S. C. Sharma
Blockchain is an emerging technology that can radically improve transactions security at banking, supply chain, and other transaction networks. It's estimated that Blockchain will generate $3.1 trillion in new business value by 2030. Essentially, it provides the basis for a dynamic distributed ledger that can be applied to save time when recording transactions between parties, remove costs associated with intermediaries, and reduce risks of fraud and tampering. This book explores the fundamentals and applications of Blockchain technology. Readers will learn about the decentralized peer-to-peer network, distributed ledger, and the trust model that defines Blockchain technology. They will also be introduced to the basic components of Blockchain (transaction, block, block header, and the chain), its operations (hashing, verification, validation, and consensus model), underlying algorithms, and essentials of trust (hard fork and soft fork). Private and public Blockchain networks similar to Bitcoin and Ethereum will be introduced, as will concepts of Smart Contracts, Proof of Work and Proof of Stack, and cryptocurrency including Facebook's Libra will be elucidated. Also, the book will address the relationship between Blockchain technology, Internet of Things (IoT), Artificial Intelligence (AI), Cybersecurity, Digital Transformation and Quantum Computing. Readers will understand the inner workings and applications of this disruptive technology and its potential impact on all aspects of the business world and society. A look at the future trends of Blockchain Technology will be presented in the book.
Miha E. Habič, Joel David Hamkins, Lukas Daniel Klausner, Jonathan L. Verner · 5 authors
Given a countable model of set theory, we study the structure of its generic multiverse, the collection of its forcing extensions and ground models, ordered by inclusion. Mostowski showed that any finite poset embeds into the generic multiverse while preserving the nonexistence of upper bounds. We obtain several improvements of his result, using what we call the blockchain construction to build generic objects with varying degrees of mutual genericity. The method accommodates certain infinite posets, and we can realize these embeddings via a wide variety of forcing notions, while providing control over lower bounds as well. We also give a generalization to class forcing in the context of second-order set theory, and exhibit some further structure in the generic multiverse, such as the existence of exact pairs.
In this vision paper, we present an approach that makes it possible to protect developed ideas and early concepts even during their systematical development. We take the Design Thinking process as an example, in which interfaces are used for individual stages (understand, observe, define, ideate, prototype, test) to digitally record verbal, written or sketched, and even modeled or constructed outcome. This outcome is recorded and linked to the originating person. To guarantee both proof-of-existence and proof-of-origin, a unique hash is generated from each digital artifact stored and embedded into the Bitcoin Blockchain by the OriginStamp decentralized trusted timestamping service. Once this unique fingerprint is embedded in a transaction in the underlying Blockchain network, it can be proven where particular contributions originated due to the characteristics of Blockchain architecture. By setting up a decentralized tamper-proof means of record keeping, the entire innovation chain from the first ideation to the beginning of production is verifiably stored. By providing a clear proof-of-origin, all innovators (even competitors) could continue to work on existing problem-solving process and add their contribution proportionately, depending on the state of innovation development. This concept enables an Open Innovation ecosystem, which has the potential to increase the innovation potential of companies immensely. Additionally, inventions that are not patentable because they do not comply with the strict regulations of patent law can still be published and protected because the information about the origin of the respective contribution is guaranteed.
Open access
Computability, Logic, AI Algorithms
Physical Unclonable Functions (PUFs) and Hardware Security
We present two models of the block chain of Bitcoin in the interactive theorem prover Agda. The first one is based on a simple model of bank accounts, while having transactions with multiple inputs and outputs. The second model models transactions, which refer directly to unspent transaction outputs, rather than user accounts. The resulting blockchain gives rise to a transaction tree. That model is formalised using an extended form of induction-recursion, one of the unique features of Agda. The set of transaction trees and transactions is defined inductively, while simultaneously recursively defining the list of unspent transaction outputs. Both structures model standard transactions, coinbase transactions, transaction fees, the exact message to be signed by those spending money in a transaction, block rewards, blocks, and the blockchain, and the second structure models as well maturation time for coinbase transactions and Merkle trees. Hashing and cryptographic operations and their correctness are dealt with abstractly by postulating corresponding operations. An indication is given how the correctness of this model could be specified and proven in Agda.
Authentication over insecure public networks or with untrusted servers raises more concerns in privacy and security.Modern algebra is one of the significantfields of mathematics. It is a combination of techniques used for a variety of applications including the process of the manipulation of the mathematical categories. In addition,modern algebra deals in depth with the study of abstractions such as groups, rings and fields,the main objective of this article is to provide a novel algebraic verification protocol using ring theory. The protocol is blind, meaning that it detects only the identity, and no additional information will be known anything about the prover (the biometric) to the authenticating server or vice-versa. More officially a blind authentication scheme is a cryptographic protocol that comprises of two parties, a user (the prover) that wants to achieve having signs on her messages, and a signer (the verifier) that is in ownership of his secret signing key. In this paper, we employ the algebraic structure called central Armendariz rings to design a neoteric algorithm for zero knowledge proof. The proposed protocol is established and illustrated through numerical example, and its soundness and completeness are proved.This method gave two important properties for the central Armendariz zero knowledge protocol compared with other known protocols.
We present a formalization of blockchain as a state machine, focusing upon permissionless blockchains due to general audience awareness of its most popular implementation, Bitcoin (permissioned blockchains are treated similarly without loss of generality). After presenting a typical Bitcoin transaction workflow, a general blockchain state representation is derived. It is demonstrated that the proper mathematical object defining the state of a blockchain is a topological fiber bundle, because it is not possible to globally `parametrize' blocks (or ledgers of blocks) by time due to their dependence upon cryptographic hash functions. In addition, we specify a general transition function between blockchain states that is agnostic to the consensus mechanism used to write blocks into the ledger, and which is probabilistic in nature, so that blockchain may be regarded as a probabilistic state machine. We then interpret agents (both human and code-based, such as `chaincode', `smart contracts', or other artificial intelligence) as automata interacting with blockchain technology, drawing upon the theory of non-cooperative repeated interaction games. Finally, blockchain as a hierarchy of state machines is defined, and future research directions are presented using this hierarchy as a point of departure for modeling blockchain dynamics.
We study the problem of argument systems, where a computationally weak verifier outsources the execution of a computation to a powerful but untrusted prover, while being able to validate that the result was computed correctly through a proof generated by the prover. In addition, the zero-knowledge property guarantees that proof leaks no information about the potential secret input from the prover. Existing efficient zero-knowledge arguments with sublinear verification time require an expensive preprocessing phase that depends on a particular computation, and incur big overhead on the prover time and prover memory consumption. This thesis proposes new constructions for zero-knowledge arguments that overcome the above problems. The new constructions require only a one time preprocessing and can be used to validate any computations later. They also reduce the overhead on the prover time and memory by orders of magnitude. We apply our new constructions to build a verifiable database system and verifiable RAM programs, leading to significant improvements over prior work.
Abstract This paper argues that many so‐called digital technologies can be construed as notational technologies, explored through the example of Monegraph, an art and digital asset management platform built on top of the blockchain system originally developed for the cryptocurrency bitcoin. As the paper characterizes it, a notational technology is the performance of syntactic notation within a field of reference, a technologized version of what Nelson Goodman called a “notational system.” Notational technologies produce abstracted entities through positive and reliable, or constitutive, tests of socially acceptable meaning. Accordingly, this account deviates from typical narratives of blockchains (usually characterized as Turing or state machines), instead demonstrating that blockchain technologies are effective at managing digital assets because they produce abstracted identities through the performance of notation. Since notational technologies rely on configurations of socially acceptable meaning, this paper also provides a philosophical account of how blockchain technologies are socially embedded.
Open access
Blockchain Technology Applications and Security
Neuroethics, Human Enhancement, Biomedical Innovations
We consider a problem we call StateIsomorphism: given two quantum states of n qubits, can one be obtained from the other by rearranging the qubit subsystems? Our main goal is to study the complexity of this problem, which is a natural quantum generalisation of the problem StringIsomorphism. We show that StateIsomorphism is at least as hard as GraphIsomorphism, and show that these problems have a similar structure by presenting evidence to suggest that StateIsomorphism is an intermediate problem for QCMA. In particular, we show that the complement of the problem, StateNonIsomorphism, has a two message quantum interactive proof system, and that this proof system can be made statistical zero-knowledge. We consider also StabilizerStateIsomorphism (SSI) and MixedStateIsomorphism (MSI), showing that the complement of SSI has a quantum interactive proof system that uses classical communication only, and that MSI is QSZK-hard.
Multi-agents systems communication is a technology, which provides a way for multiple interacting intelligent agents to communicate with each other and with environment. Multiple-agent systems are used to solve problems that are difficult for solving by individual agent. Multiple-agent communication technologies can be used for management and organization of computing fog and act as a global, distributed operating system. In present publication we suggest technology, which combines decentralized P2P BOINC general-purpose computing tasks distribution, multiple-agents communication protocol and smart-contract based rewards, powered by Ethereum blockchain. Such system can be used as distributed P2P computing power market, protected from any central authority. Such decentralized market can further be updated to system, which learns the most efficient way for software-hardware combinations usage and optimization. Once system learns to optimize software-hardware efficiency it can be updated to general-purpose distributed intelligence, which acts as combination of single-purpose AI.
We demonstrate that the Bitcoin Script language allows not only for primitive recursion, but in the deployment of an Ackerman function and hence the ability to simply recurse in Bitcoin script, we show that the script system is Turing complete. From this, we introduce a new class of Turing Machine, the PTTM or probabilistic Total Turing machine and note that Bitcoin acts as a decider or Total Turing Machine which allows us to find a NIZKPoK that can act as a TM based verifier to a Non-Interactive Proof that is run on an external and non-associated TM as a proof system. Bitcoin can extend to securely offer contracts such as best fit solutions to common logistic systems and optimisation problems including the Travelling Salesman class of problems and to the optimisation of systems. This can be offered as an open or time bound contract that guarantees payment and can be solved which allowing Pseudonymity of the bidder.
The concept of a Turing machine has been well defined. It would be sufficient to show that Bitcoin uses a dual stack architecture that acts as a dual counter machine. Such systems have already been demonstrated as being Turing complete. We demonstrate that Bitcoin script is a minimal family of which λ and R are members. Further using the compositional product rule and the iteration rule we demonstrate that Bitcoin scripting is Turing complete with the limitations imposed on any realworld computer. This limitation is that there cannot be an infinite tape. Iterations can be simulated using an “unrolled” loop function with allocation to the “Alt” stack. As the product rule states that if A, B are machines, then A.B is also a machine. The iteration rule shows that if A is a machine then (A) is also a machine. Further the minimum power of A under which the observed square of the final configuration is blank. The consequence of these rules is that for every partial recursive function of in variables we can show that it can be evaluated by machine of the proposed family.
Since Bitcoin was launched in 2009, several new cryptocurrencies have been initiated with variations to Bitcoin's original design. Although Bitcoin still remains the most prominent actor in the market, some technical problems have been raised to the design of the protocol. The objective of this thesis is to determine whether the newer cryptocurrencies handle the technical problems of Bitcoin, or if they also suffer from the same issues. Instead of evaluating several cryptocurrencies for this comparison, the cryptocurrency Ethereum has been chosen as a proxy for the others. Ethereum was started in 2014, is widely backed in the community and is second in line to Bitcoin when it comes to market capitalization. \n\nAs a basis for the comparative analysis a rigorous study of the Bitcoin and Ethereum protocols have been performed, and parallel descriptions of the systems have been devised. Three technical problem have shaped the focus of the analysis: computational waste, concentration of power and ambiguity of transactions. Real world statistical data has been gathered and synthesized to enlighten the findings in the comparison. The main result of the comparison is that both systems suffer from the same problems to a certain degree, due to the fact that they utilize the same consensus mechanism. However, Ethereum utilizes several newer techniques to try and reduce the severity of these problems compared to Bitcoin, with varying degrees of success.
Bitcoin is a digital currency and payment system based on classical cryptographic technologies which works without a central administrator such as in traditional currencies. It has long been questioned what the impact of quantum computing would be on Bitcoin, and cryptocurrencies in general. Here, we analyse three primary directions that quantum computers might have an impact in: mining, security, and forks. We find that in the near-term the impact of quantum computers appear to be rather small for all three directions. The impact of quantum computers would require considerably larger number of qubits and breakthroughs in quantum algorithms to reverse existing hash functions.
The paper deals with cryptocurrencies and trading. Main goal of this article is to introduce strategy for automated trading on cryptocurrency exchange market. For this purpose we will use algorithm based of Floyd-Warshall algorithm. Article is introductory and can this method can be developed in the future. First, a general introduction to cryptocurrencies is given from the programmer's point of view, some statistics data and figure representing volatility of exchange. Then the article describes some basic strategies for automated trading. Also explained is the algorithm Floyd-Warshall and its modifications for automation arbitrage. An illustrative example is given and a trading algorithm is listed.
Kriptovalute su digitalni novac utemeljen na kriptografiji i decentraliziranom sustavu. Postoje samo u elektroničkom obliku kao jedinstveni digitalni novčići ("tokeni"). Iza njih ne stoji autoritet države niti ih je moguće svojevoljno proizvesti. Rad se fokusira na značajkama, postavkama, razvoju i svim međuodnosima važnih ekonomskih faktora koji utječu na kriptovalute. U prvom poglavlju navedena su obilježja kriptovaluta. Drugo poglavlje daje primjere i govori o primjeni kriptovaluta u svakodnevnom životu. U trećem poglavlju je raspravljano o trenutnim i budućim regulacijama najmoćnijih zemalja svijeta (G20) , kao i njihovoj zajedničkoj suradnji u želji za jedinstvenim i standardiziranim pravilima, a sve u svrhu što kvalitetnijeg nadzora nad kriptovalutama kako bi se spriječile malverzacije i zaštitili potrošači. Četvrto poglavlje govori o inicijalnoj ponudi kovanica, a peto poglavlje je namijenjeno sigurnosti kriptovaluta. Cilj istraživanja je utvrditi koliko je studentska populacija upoznata i usmjerena prema novim oblicima digitalnog novca, koje značajke kriptovaluta smatraju pozitivnima, a koje negativnima i u kojoj su mjeri investirali ili su spremni investirati dio svojih ulaganja u kriptovalute i sl. Metode istraživanja korištene u radu su kompilacija na temelju proučavanja postojeće literature o temi rada, prikupljanje i analiza podataka vezanih uz kriptovalute, ponajprije podataka vezanih uz cijene i tržišnu kapitalizaciju, anketiranje studenata Ekonomskog fakulteta u Rijeci i metoda dedukcije putem koje su pokazane sve važne karakteristike i obilježja kriptovaluta. Na temelju provedene ankete u kojoj je sudjelovalo 90 studenata Ekonomskog fakulteta u Rijeci zaključak toga dijela istraživanja je da je mlada populacija dobro upoznata s kriptovalutama i njenim glavnim značajkama, ali i određenim nedostatkom informiranosti o tehnologiji (trećina studenata nije čula za pojam "blockchain") i nedovoljnoj odlučnosti oko investiranja i trgovanja u kriptovalute. Povrh toga, dokazan je i negativan utjecaj hakerskih napada i određenih kriminalnih radnji, kao i nestabilnost tržišne cijene na povjerenje studenata, ali i ukupne populacije vezane uz globalni financijski sustav u kriptovalute. Ishod istraživanja omogućio je da zaključimo kako su kriptovalute trenutno u ranoj fazi razvoja i nisu se dovoljno implementirale za široku primjenu u trgovini roba i usluga ili općenito kao sredstvo razmjene. Faktor koji je uključen u istraživanje kako bi opisao veličinu, odnosno obujam neke kriptovalute je tržišna kapitalizacija u dolarima. Temeljna ideja ovog rada je informirati čitatelja o pozitivnim i negativnim značajkama koje se se vežu uz kriptovalute. Na taj način čitatelji će biti bolje informirani i educirani o potencijalnom riziku ulaganja u kriptovalute, kao i većoj razini zaštite prilikom posjedovanja neke digitalne valute.
We survey recent results on the mathematical stability of Bitcoin protocol. Profitability and probability of a double spend are estimated in closed form with classical special functions. The stability of Bitcoin mining rules is analyzed and several theorems are proved using martingale and combinatorics techniques. In particular, the empirical observation of the stability of the Bitcoin protocol is proved. This survey article on the mathematics of Bitcoin is published by the Newsletter of the European Mathematical Society, vol.115, 2020, p.31-37. Continuation of arXiv:1601.05254 (EMS Newsletter, 100, 2016 p.32).