Blockchain Papers

Rajrupa Singh, R. Selvakumar

No abstract is available for this record.

Matthew Cushman

A novel data structure that enables the storage and retrieval of linear array numeric data with logarithmic time complexity updates, range sums, and rescaling is introduced and studied. Computing sums of ranges of arrays of numbers is a common computational problem encountered in data compression, coding, machine learning, computational vision, and finance, among other fields. Efficient data structures enabling log n updates of the underlying data (including range updates), queries of sums over ranges, and searches for ranges with a given sum have been extensively studied (n being the length of the array). Two solutions to this problem are well-known: Fenwick trees (also known as Binary Indexed Trees) and Segment Trees. The new data structure extends the capabilities for the first time to further enable multiplying (rescaling) ranges of the underlying data by a scalar as well in log n. Scaling by 0 can be enabled, with the effect that subsequent updates may take (log n)2time. The new data structure introduced here consists of a pair of interacting Fenwick tree-like structures, one of which holds the unscaled values and the other of which holds the scalars. Experimental results demonstrating performance improvements for the multiplication operation on arrays from a few dozen to over 30 million data points are discussed. This research was done as part of Ajna Labs in the course of developing a decentralized finance protocol. It enables an efficient on-chain encoding and processing of an order book-like data structure used to manage lending, interest, and collateral.

Yuichi Komano, Takaaki Mizuki

No abstract is available for this record.

Robert Susik, Robert Nowotniak

Blockchain received a vast amount of attention in recent years and is still growing. The second generation of blockchain, such as Ethereum, allows execution of almost any program in Ethereum Virtual Machine (EVM), making it a global protocol for distributed applications. The code deployment and each operation performed in EVM cost the network fee called gas, which price varies and can be significant. That is why code optimization and well-chosen algorithms are crucial in programming on the blockchain. This paper evaluates the gas usage of several exact pattern matching algorithms on the Ethereum Virtual Machine. We also propose an efficient implementation of the algorithms in the Solidity/YUL language. We evaluate the gas fees of all the algorithms for different parameters (such as pattern length, alphabet size, and text size). We show a significant gas fee and execution time reduction with up to 22-fold lower gas usage and 55-fold speed-up comparing to StringUtils (a popular Solidity string library).

Eammon Hart, Joshua A. McGinnis

In this paper we describe protocols which use a standard deck of cards to provide a perfectly sound zero-knowledge proof for Hamiltonian cycles and Flow Free puzzles. The latter can easily be extended to provide a protocol for a zero-knowledge proof of many-to-many k-disjoint path coverings.

Faiza Suleymanovna Kurbalieva, Mutayeva Ibragimovna Sayeda

No abstract is available for this record.

Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Titouan Tanguy

This work introduces a new interactive oracle proof system based on the MPC-in-the-Head paradigm. To improve concrete efficiency and offer flexibility between computation time and communication size, a generic proof construction based on multi-round MPC protocols is proposed, instantiated with a specific protocol and implemented and compared to similar proof systems.

Muhammad Saad, Afsah Anwar, Srivatsan Ravi, Aziz Mohaisen

No abstract is available for this record.

Suthee Ruangwises, Toshiya Itoh

No abstract is available for this record.

Aleksei Udovenko

In this note, we report several solutions to the STARK-Friendly Hash Challenge: a competition with the goal of finding collisions for several hash functions designed specifically for zero-knowledge proofs (ZKP) and multiparty computations (MPC). We managed to find collisions for 3 instances of 91-bit hash functions. The method used is the classic parallel collision search with distinguished points from van Oorshot and Wiener (1994). As this is a general attack on hash functions, it does not exhibit any particular weakness of the chosen hash functions. The crucial part is to optimize the implementations to make the attack cost realistic, and we describe several arithmetic tricks.

Jérémy Charlier, Radu Statem, Jean Hilger

Smart contracts are autonomous software executing predefined conditions. Two of the biggest advantages of the smart contracts are secured protocols and transaction costs reduction. On the Ethereum platform, an open-source blockchain-based platform, smart contracts implement a distributed virtual machine on the distributed ledger. To avoid denial of service attacks and monetize the services, payment transactions are executed whenever code is being executed between contracts. It is thus natural to investigate if predictive analysis is capable to forecast these interactions. We have addressed this issue and propose an innovative application of the tensor decomposition CANDECOMP/PARAFAC to the temporal link prediction of smart contracts. We introduce a new approach leveraging stochastic processes for series predictions based on the tensor decomposition that can be used for smart contracts predictive analytics.

Xiaoyong Zhang, Ruizhen Wu, Mingming Wang, Lin Wang

The SHA-256 is playing an important role in various applications, such as e-transactions and bitcoins. To achieve more profits, the SHA-256 computation capacity is a main research direction of Hashing Algorithm. In this paper, a high-performance hardware architecture of SHA-256 hash is proposed. The computation of SHA-256 is rescheduled based on hardware characterises. Three pipelines are used to replace the critical path in the round functions which can shorten the long critical path, and divide the computation chain into independent parts. Multi-computation of SHA-256 is working in parallel pipelines, indicating that the computation capacity can be 3 times of standard SHA-256 implementation. The proposed SHA-256 hardware architecture has been implemented and synthesized with Intel 14nm technology. Simulation and synthesis results show the proposed SHA-256 hashing throughput can be improved by 3 times with 50.7% power reduction, at an area cost of 2.9 times compared to the standard implementation.

Mary Maller, Sean Bowe, Markulf Kohlweiss, Sarah Meiklejohn

Ever since their introduction, zero-knowledge proofs have become an important tool for addressing privacy and scalability concerns in a variety of applications. In many systems each client downloads and verifies every new proof, and so proofs must be small and cheap to verify. The most practical schemes require either a trusted setup, as in (pre-processing) zk-SNARKs, or verification complexity that scales linearly with the complexity of the relation, as in Bulletproofs. The structured reference strings required by most zkSNARK schemes can be constructed with multi-party computation protocols, but the resulting parameters are specific to an individual relation. Groth et al. discovered a zk-SNARK protocol with a universal structured reference string that is also updatable, but the string scales quadratically in the size of the supported relations.<br/> <br/>Here we describe a zero-knowledge SNARK, Sonic, which supports a universal and continually updatable structured reference string that scales linearly in size. We also describe a generally useful technique in which untrusted “helpers” can compute advice that allows batches of proofs to be verified more efficiently. Sonic proofs are constant size, and in the “helped” batch verification context the marginal cost of verification is comparable with the most efficient SNARKs in the literature<br/>

Jean‐Guillaume Dumas, Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki · 6 authors

No abstract is available for this record.

Francisca Adoma

The importance of big data in machine learning cannot be overemphasized in recent times. Through the evolution of big data, most scientific technologies that relied heavily on enormous data in solving complex issues in human lives gained grounds; machine learning is an instance of these technologies. Various machine learning models that yield groundbreaking throughputs with high efficiency rates in predicting, detecting, classifying, discovering and acquiring in-depth knowledge about events that would otherwise be very difficult to ascertain have been made possible due to big data. Although big data has undoubtedly helped in the field of machine learning research ,over the years, its mode of acquisition has posed great challenge in industries,education and other agencies that obtained them for various purposes. This is because these large quantities of data cannot be stored on personal computers with limited storage capabicity but required the use of high storage capacity servers for effective storage. These servers may be owned by a group of companies or individuals who had the singular priviledge to modify the data in their possession as and when deemed relevant thus the creation of a centralized data storage environment. These were mostly refered to as the Third Parties (TP) in the data acquisition process. For the services they rendered, these trusted parties priced data in their possession expensively. The adverse effect is a limitation on various researches that could help solve a number of problems in human lives. It is worth mentioning that the security of these data being purchased expensively cannot be even assured limiting various researches that thrive on secured data. In order to curb these occurrences and have better machine learning models, the incorporation of Blockchain Technology databases into machine learning. This paper discusses the concept of big data, Machine Learning and Blockchains. It further discusses how Big data has impacted the Machine learning Community, the significance of Machine Learning and how the BlockChain Technology could be used similarly impact the Machine Learning Community. The aim of this paper is to encourge further research in incoporating the BlockChain Technology into Machine Learning.

Beltrán Borja Fiz Pontiveros, Robert Norvill, Radu State

In this work we propose a compression method for smart contracts deployed in the Ethereum blockchain. By taking advantage of the repetition of sections of bytecode among multiple smart contracts previously deployed in the Ethereum blockchain we propose a new pseudo opcode that acts as a pointer that will allow smart contracts to reuse previously deployed code. We show that our proposed algorithm achieves space savings of up to 75% in a dataset of deployed Ethereum smart contracts bytecode, on par with other state of the art compression algorithms while remaining compatible with other methods currently in use for space reduction.

Jérémy Charlier, Radu State, Jean Hilger

Background: Past few months have seen the rise of blockchain and cryptocurrencies. In this context, the Ethereum platform, an open-source blockchain-based platform using Ether cryptocurrency, has been designed to use smart contracts programs. These are self-executing blockchain contracts. Due to their high volume of transactions, analyzing their behavior is very challenging. We address this challenge in our paper. Methods: We develop for this purpose an innovative approach based on the non-negative tensor decomposition Paratuck2 combined with long short-term memory. The objective is to assess if predictive analysis can forecast smart contracts activities over time. Three statistical tests are performed on the predictive analytics, the mean absolute percentage error, the mean directional accuracy and the Jaccard distance. Results: Among dozens of GB of transactions, the Paratuck2 tensor decomposition allows asymmetric modeling of the smart contracts. Furthermore, it highlights time dependent latent groups. The latent activities are modeled by the long short term memory network for predictive analytics. The highly accurate predictions underline the accuracy of the method and show that blockchain activities are not pure randomness. Conclusion: Herein, we are able to detect the most active contracts, and predict their behavior. In the context of future regulations, our approach opens new perspective for monitoring blockchain activities.

T. S Brinda

Wireless sensor network (WSN) have become a prominent solution for various interesting applications like security surveillance and monitoring of geographical areas. Various types of sensors are used and deployed in the network to collect useful physical parameters and some highly sensitive information is then been transmitted between the nodes and to the base station, without any human intervention. Hence, message authenticity and security are major requirements in WSN. Since the cryptographic schemes used for wired networks tend to exhaust wireless sensor network resources, they cannot be directly used in sensor networks. In this, the zero knowledge protocol (ZKP) is investigated that it is an under applied authentication mechanism used to identify compromised nodes from genuine ones. Here the Zero Knowledge Protocol (ZKP) is implemented in the network for the authentication and verification of sender sensor nodes before transmitting any sensitive information. The proposed scheme addresses the improvement in the security while maintaining the message confidentiality. In proposed scheme an optimal number of challenge questions are also used to maintain a balance between the added security and the increase in cost. Increase in the number of challenge question makes up to the reduced key size thus providing an improved security. The proposed scheme was assessed based on the mat lab simulation and an analysis was performed.

Ran Canetti, Amit Lichtenberg

The modeling of trapdoor permutations has evolved over the years. Indeed, finding an appropriate abstraction that bridges between the existing candidate constructions and the needs of applications has proved to be challenging. In particular, the notions of certifying permutations (Bellare and Yung, 96), enhanced and doubly enhanced trapdoor permutations (Goldreich, 04, 08, 11, Goldreich and Rothblum, 13) were added to bridge the gap between the modeling of trapdoor permutations and needs of applications. We identify an additional gap in the current abstraction of trapdoor permutations: Previous works implicitly assumed that it is easy to recognize elements in the domain, as well as uniformly sample from it, even for illegitimate function indices. We demonstrate this gap by using the (Bitansky-Paneth-Wichs, 16) doubly-enhanced trapdoor permutation family to instantiate the Feige-Lapidot-Shamir (FLS) paradigm for constructing non-interactive zero-knowledge (NIZK) protocols, and show that the resulting proof system is unsound. To close the gap, we propose a general notion of certifiably injective doubly enhanced trapdoor functions (DECITDFs), which provides a way of certifying that a given key defines an injective function over the domain defined by it, even when that domain is not efficiently recognizable and sampleable. We show that DECITDFs suffice for instantiating the FLS paradigm; more generally, we argue that certifiable injectivity is needed whenever the generation process of the function is not trusted. We then show two very different ways to construct DECITDFs: One is via the traditional method of RSA/Rabin with the Bellare-Yung certification mechanism, and the other using indistinguishability obfuscation and injective pseudorandom generators. In particular the latter is the first candidate injective trapdoor function, from assumptions other than factoring, that suffices for the FLS paradigm. Finally we observe that a similar gap appears also in other paths proposed in the literature for instantiating the FLS paradigm, specifically via verifiable pseudorandom generators and verifiable pseudorandom functions. Closing the gap there can be done in similar ways to the ones proposed here.

Craig Wright

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.

Xavier Bultel, Jannik Dreier, Jean‐Guillaume Dumas, Pascal Lafourcade

Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given value. We give physical algorithms to realize zero-knowledge proofs for these games which allow a player to show that he knows a solution without revealing it. These interactive proofs can be realized with simple office material as they only rely on cards and envelopes. Moreover, we formalize our algorithms and prove their security.

Maryam Rajabzadeh Asaar, Mahmoud Salmasizadeh

Abstract. In this study, a novel pairing based strong designated verifier signature scheme based on non-interactive zero knowledge proofs is proposed. The security of the proposal is presented by sequences of games without random oracles; furthermore, this scheme has a security proof for the property of privacy of the signer’s identity in comparison with the scheme proposed by Zhang et al. in 2007. In addition, this proposal compared to the scheme presented by Huang et al. in 2011 supports non-delegatability. The non-delegatability of our proposal is achieved since we do not use the common secret key shared between the signer and the designated verifier in our construction. Furthermore, if a signer delegates her signing capability which is derived from her secret key on a specific message to a third party, then, the third party cannot generate a valid designated verifier signature due to the relaxed special soundness of the non-interactive zero knowledge proof. To the best of our knowledge, this construction is the first attempt to generate a designated verifier signature scheme with non-delegatability in the standard model, while satisfying of non-delegatability property is loose.

Oded Goldreich

No abstract is available for this record.

Kristian Gjøsteen, Lillian Kråkmo

No abstract is available for this record.