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).
Abstract: This work presents an adaptive profitable discriminatory pricing mechanism for cloud computing based on secure function decomposition, cryptographic commitments and zero knowledge proof. Cloud computing is an emerging trend of enterprise resource planning where a selling agent or service provider (S) wants to allocate a set of computational resources and related IT services optimally and fairly among many buying agents or service consumers (B) within its capacity constraint. Each service consumer discloses its demand plan for an IT portfolio within its budget constraint and rank of preference. An IT portfolio may include SaaS, PaaS, IaaS, CaaS, DaaS and dSaaS. The basic objective of the service provider is to optimize its expected revenue within target profit margin. It is basically a problem of secure function evaluation where the concept of decomposition of a function is considered. It is a constrained nonlinear optimization problem; the search is governed by a set of intelligent moves. The communication complexity of the pricing mechanism depends on the time constraint of the negotiating agents, their information state and the number of negotiation issues; it also depends on number of negotiation rounds and the complexity of IT portfolio. The computational cost depends on the complexity of function decomposition. The security and privacy of strategic data of the trading agents provides business intelligence to the pricing mechanism. The ultimate objective of the mechanism is to predict a profitable discriminatory pricing plan for each consumer.
We present a new definition of computationally binding commitment schemes in the quantum setting, which we call “collapse-binding”. The definition applies to string commitments, composes in parallel, and works well with rewindingbased proofs. We give simple constructions of collapse-binding commitments in the random oracle model, giving evidence that they can be realized from hash functions like SHA-3. We evidence the usefulness of our definition by constructing three-round statistical zero-knowledge quantum arguments of knowledge for all NP languages.
Six assertions concerning the status of Bitcoin are formulated and defended: (i) Bitcoin is not and will not become a currency-like informational commodity, (ii) currency-like informational commodities that aren’t currencies must be frauds, (ii) specific BTC amounts may become monetized and thus may be turned into financial assets, (iii) currently no BTC amounts are monetized in any currency area and therefore none are financial assets, (iv) by means of burocratic steps only some BTC volumes can be turned in to an informational currency within a given currency area, modified client software is not required for that step, (v) if a specific amount of BTC qualifies as currency, it also qualifies as money, (vi) moneyness of Bitcoin, or rather of a specific occurrence of an amount of BTC, should be questioned only after one has agreed positively on its status as a financial asset, and negatively on its status as an amount of currency. Factions in the Bitcoin promoting movement are viewed from a perspective of organizational multi-threading. Different factions of the Bitcoin movement may wish to see status issues about Bitcoin settled in different ways. Overall consistency in these matters should not be expected from the union of factions in the Bitcoin movement.
We show that the behaviour of Bitcoin has interesting similarities to stock\nand precious metal markets, such as gold and silver. We report that whilst\nLitecoin, the second largest cryptocurrency, closely follows Bitcoin's\nbehaviour, it does not show all the reported properties of Bitcoin. Agreements\nbetween apparently disparate complexity measures have been found, and it is\nshown that statistical, information-theoretic, algorithmic and fractal measures\nhave different but interesting capabilities of clustering families of markets\nby type. The report is particularly interesting because of the range and novel\nuse of some measures of complexity to characterize price behaviour, because of\nthe IRS designation of Bitcoin as an investment property and not a currency,\nand the announcement of the Canadian government's own electronic currency\nMintChip.\n
We give an explicit definition of decentralization and show you that\ndecentralization is almost impossible for the current stage and Bitcoin is the\nfirst truly noncentralized currency in the currency history. We propose a new\nframework of noncentralized cryptocurrency system with an assumption of the\nexistence of a weak adversary for a bank alliance. It abandons the mining\nprocess and blockchain, and removes history transactions from data\nsynchronization. We propose a consensus algorithm named Converged Consensus for\na noncentralized cryptocurrency system.\n
Los motivos históricos y económicos que han llevado a programar el protocolo Bitcoin se encuentran en la actualidad con una interesante fase evolutiva de los algoritmos de encriptación para la identificación de datos y la transmisión de derechos, tratándose de un sistema que presenta aspectos jurídicos dignos de mención.
In recent years there has been a fantastic boom of increasingly sophisticated “cryptographic objects ” — identity-based encryption, fully-homomorphic encryption, functional encryption, and most recently, various forms of obfuscation. These objects often come in various flavors of security, and as these constructions have grown in number, complexity and inter-connectedness, the relationships between them have become increasingly confusing. We provide a new framework of cryptographic agents that unifies various cryptographic objects and security definitions, similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. Our contributions can be summarized as follows. • Our main contribution is a new model of cryptographic computation, that unifies and extends cryptographic primitives such as Obfuscation, Functional Encryption, Fully Homomorphic En-cryption, Witness encryption, Property Preserving Encryption and the like, all of which can be cleanly modeled as “schemata ” in our framework. We provide a new indistinguishability preserving (IND-PRE) definition of security that interpolates indistinguishability and simulation
Samuel Ranellucci, Alain Tapp, Rasmus Winther Zakarias
Abstract. Even though Zero-knowledge has existed for more than 30 years, few generic constructions for Zero-knowledge exist. In this paper we present a new kind of commitment scheme on which we build a novel and efficient Zero-knowledge protocol for circuit satisfiability. 1
Our research is concerned with the processes of collaboration that are required by organizations as they increasingly adopt more network-like organization structures (Drucker, 1988; Huber, 1984; Malone, Yates, & Benjamin, 1987). We want to understand the kinds of communication that are needed and design information technologies to support them (Boland & Tenkasi, 1995; Boland, Tenkasi, & Te&s;eni, 1994). By network-like organizations we mean those that resemble open systems as described by Hewitt (1985, 1986).Open systems are composed of decentralized, autonomous units, each with different and inconsistent knowledge bases. Open systems are characterized by distributed cognition (Hutchins, 1996; Norman, 1993) in which the task of the organization is achieved by individuals and technologies acting independently within their own domains on parts of the overall problem, but taking each other and their interdependencies into account in their actions. In a network-like, open system organization, coordination emerges within this process of distributed cognition.
The famous new money Bitcoin is classified as a technical informational money (TIM). Besides introducing the idea of a TIM, a more extreme notion of informational money will be developed: exclusively informational money (EXIM). The informational coins (INCOs) of an EXIM can be in control of an agent but are not owned by any agent. INCOs of an EXIM cannot be stolen, but they can be lost, or thrown away. The difference between an EXIM and a TIM shows up when considering a user perspective on security matters. Security for an EXIM user is discussed in substantial detail, with the remarkable conclusion that computer security (security models, access control, user names, passwords, firewalls etc.) is not always essential for an EXIM, while the application of cryptography based information security is unavoidable for the use of an EXIM. Bitcoin seems to meet the criteria of an EXIM, but the assertion that "Bitcoin is an EXIM", might also be considered problematic. As a thought experiment we will contemplate Bitguilder, a hypothetical copy of Bitcoin that qualifies as an EXIM. A business ethics assessment of Bitcoin is made which reveals a number of worries. By combining Bitguilder with a so-called technical informational near-money (TINM) a dual money system, having two units with a fluctuating rate, may be obtained. It seems that a dual money can remedy some, but not all, of the ethical worries that arise when contemplating Bitcoin after hypothetically having become a dominant form of money. The contributions that Bitcoin's designers can potentially make to the evolution of EXIMs and TIMs is analyzed in terms of the update of the portfolio of money related natural kinds that comes with Bitcoin.
Given an instance of a hard decision problem, a limited goal is to compress that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $\mathrm{OR}$-compression scheme for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some “target” language $L'$ if and only if $\bigvee_j [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is strong if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$. Strong compression for SAT seems unlikely. Work of Harnik and Naor [SIAM J. Comput., 39 (2010), pp. 1667--1713] and Bodlaender, Downey, Fellows, and Hermelin [J. Comput. System Sci., 75 (2009), pp. 423--434] showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam [J. Comput. System Sci., 77 (2011), pp. 91--106] showed that if SAT is strongly OR-compressible, then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Finding similar evidence against AND-compression was left as an open question. We provide such evidence: we show that strong AND- or OR-compression for SAT would imply nonuniform, statistical zero-knowledge proofs for SAT---an even stronger and more unlikely consequence than $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Our method applies against probabilistic compression schemes of sufficient “quality” with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of quantum instance compression, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, “preserves the answer” to the input instance. The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to “disguise” information being fed into a compressive mapping; we believe this method may find other applications.
Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, Salil Vadhan
Abstract: We investigate the complexity of the following computational problem: Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping p: Fn → Fm, where F is a finite field, approximate the output entropy H(p(Un)), where Un is the uniform distribution on Fn and H may be any of several entropy measures. We show: • Approximating the Shannon entropy of degree 3 polynomials p: Fn 2 → Fm 2 over F2 to within an additive constant (or even n.9) is complete for SZKPL, the class of problems having statistical zero-knowledge proofs where the honest verifier and its simulator are computable in logarithmic space. (SZKPL contains most of the natural problems known to be in the full class SZKP.) • For prime fields F = F2 and homogeneous quadratic polynomials p: Fn → Fm, there is a probabilistic polynomial-time algorithm that distinguishes the case that p(Un) has entropy smaller than k from the case that p(Un) has min-entropy (or even Renyi entropy) greater than (2 + o(1))k. • For degree d polynomials p: Fn 2 → Fm 2, there is a polynomial-time algorithm that distinguishes the case that p(Un) has max-entropy smaller than k (where the max-entropy of a random variable is the logarithm of its support size) from the case that p(Un) has max-entropy at least (1 + o(1)) · kd (for fixed d and large k).
Imad Fakhri Taha Alshaikhli, Rusydi Hasan Makarin, Siti Khairunnisa Mohd Bakri, Nur Dalilah More Yusoff · 5 authors
Much of the current innovation in advanced materials is occurring at the nanoscale, specifically in manufactured nanomaterials (MNs). MNs display unique attributes and behaviors, and may be biologically and physically unique, making them valuable across a wide range of applications. However, as the number, diversity and complexity of MNs coming to market continue to grow, assessing their health and environmental risks with traditional animal testing approaches is too time- and cost-intensive to be practical, and is undesirable for ethical reasons. New approaches are needed that meet current requirements for regulatory risk assessment while reducing reliance on animal testing and enabling safer-by-design product development strategies to be implemented. The adverse outcome pathway (AOP) framework presents a sound model for the advancement of MN decision making. Yet, there are currently gaps in technical and policy aspects of AOPs that hinder the adoption and use for MN risk assessment and regulatory decision making. This review outlines the current status and next steps for the development and use of the AOP framework in decision making regarding the safety of MNs. Opportunities and challenges are identified concerning the advancement and adoption of AOPs as part of an integrated approach to testing and assessing (IATA) MNs, as are specific actions proposed to advance the development, use and acceptance of the AOP framework and associated testing strategies for MN risk assessment and decision making. The intention of this review is to reflect the views of a diversity of stakeholders including experts, researchers, policymakers, regulators, risk assessors and industry representatives on the current status, needs and requirements to facilitate the future use of AOPs in MN risk assessment. It incorporates the views and feedback of experts that participated in two workshops hosted as part of an Organization for Economic Cooperation and Development (OECD) Working Party on Manufactured Nanomaterials (WPMN) project titled, "Advancing AOP Development for Nanomaterial Risk Assessment and Categorization", as well as input from several EU-funded nanosafety research consortia.
Traditionally, the definition of zero-knowledge states that an interactive proof of x ∈ L provides zero (additional) knowledge if the view of any polynomial-time verifier can be reconstructed by a polynomial-time simulator. Since this definition only requires that the worst-case running-time of the verifier and simulator are polynomials, zero-knowledge becomes a worst-case notion. In STOC’06, Micali and Pass proposed a new notion of precise zero-knowledge, which captures the idea that the view of any verifier in every interaction can be reconstructed in (almost) the same time (i.e., the view can be “indistinguishably reconstructed”). This is the strongest notion among the known works towards precislization of the definition of zero-knowledge. However, as we know, there are two kinds of computational resources (i.e. time and space) that every algorithm consumes in computation. Although the view of a verifier in the interaction of a precise zero-knowledge protocol can be reconstructed in almost the same time, the simulator may run in very large space while at the same time the verifier only runs in very small space. In this case it is still doubtful to take indifference for the verifier to take part in the interaction or