Srinath Setty, Sebastian Angel, Trinabh Gupta, Jonathan Lee
This paper introduces Spice, a system for building verifiable state machines (VSMs). A VSM is a request-processing service that produces proofs establishing that requests were executed correctly according to a specification. Such proofs are succinct (a verifier can check them efficiently without reexecution) and zero-knowledge (a verifier learns nothing about the content of the requests, responses, or the internal state of the service). Recent systems for proving the correct execution of stateful computations--Pantry [25], Geppetto [34], CTV [30], vSQL [83], etc.--implicitly implement VSMs, but they incur prohibitive costs. Spice reduces these costs significantly with a new storage primitive. More notably, Spice's storage primitive supports multiple writers, making Spice the first system that can succinctly prove the correct execution of concurrent services. We find that Spice running on a cluster of 16 servers achieves 488-1167 transactions/second for a variety of applications including inter-bank transactions [27], cloud-hosted ledgers [28], and dark pools [63]. This represents an 18,000-685,000× higher throughput than prior work.
Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible, for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message or a completely unrelated value. Although such codes do not exist if the family of “tampering functions” ${\mathcal F}$ is completely unrestricted, they are known to exist for many broad tampering families ${\mathcal F}$. One such natural family is the family of tampering functions in the so-called split-state model. Here the message $m$ is encoded into two shares $L$ and $R$, and the attacker is allowed to arbitrarily tamper with $L$ and $R$ individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature but either (1) were constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as noninteractive zero-knowledge proofs and leakage-resilient encryption), or (3) could only encode 1-bit messages. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model. The heart of our construction uses the following new property of the inner-product function $\langle{L,R\rangle}$ over the vector space ${{F}_p}^n$ (for a prime $p$ and large enough dimension $n$): if $L$ and $R$ are uniformly random over ${\mathbb{F}_p}^n$, and $f,g:{\mathbb{F}_p}^n\rightarrow {\mathbb{F}_p}^n$ are two arbitrary functions on $L$ and $R$, then the joint distribution $(\langle{L,R\rangle},\langle{f(L),g(R)\rangle})$ is “close” to the convex combination of “affine distributions” $\{(U,aU+b)\mid a,b\in \mathbb{F}_p\}$, where $U$ is uniformly random in ${\mathbb{F}_p}$. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so-called quasi-polynomial Freiman--Ruzsa theorem, which was recently established by Sanders [Anal. PDE, 5 (2012), pp. 627--655] as a step toward resolving the polynomial Freiman--Ruzsa conjecture [B. Green, in Surveys in Combinatorics, London Mathematical Society, London, 2005, pp. 1--29].
Dragos Strugar, Rasheed Hussain, Manuel Mazzara, Víctor Rivera
Electric Autonomous Vehicles (EAVs) promise to be an effective way to solve transportation issues such as accidents, emissions and congestion, and aim at establishing the foundation of Machine-to-Machine (M2M) economy. For this to be possible, the market should be able to offer appropriate charging services without involving humans. The state-of-the-art mechanisms of charging and billing do not meet this requirement, and often impose service fees for value transactions that may also endanger users and their location privacy. This paper aims at filling this gap and envisions a new charging architecture and a billing framework for EAV which would enable M2M transactions via the use of Distributed Ledger Technology (DLT).
The blockchain revolution upholds the decentralizing ideal of “control nothing.” It is natural that such a pursuit would face issues of governance that demand reasonable control; control that is both operational as well as adaptive in nature. Eliminating middlemen and handing over controls to a trusted system of trustless agents does not thereby bestow trust across time. This is especially true when relentless change is the order of the day. Issues of governance rise up when blockchain systems (especially those that have embedded smart contracts) are forced to operate increasingly away from their original intent. Smart contracts need governance when beset with the problem of the unknown-unknowns. Guided by the axiomatic approach, this paper looks at the paradoxical issue of blockchain governance from a Complex Adaptive Systems (CAS) perspective that helps frame the fundamental problem of decentralization. The objective is to solve the Blockchain Governance Kernel Design. Real-life examples are used to illustrate the findings.
This report examines how advances in data science and encoding could improve transport. It investigates three linked and rapidly changing areas: First, it discusses the deployment of blockchain and other distributed ledger-based approaches, that record transactions efficiently and in a verifiable and permanent way. Secondly, the study looks at open algorithms and other alternatives to traditional data-sharing. Finally, it reviews the development of a common data syntax for encoding mobility services.
David Mendes, Irene Pimenta Rodrigues, César Fonseca, Manuel José Lopes · 6 authors
We introduce our solution developed for data privacy, and specifically for cognitive security that can be enforced and guaranteed using blockchain technology in SAAL (Smart Ambient Assisted Living) environments. Personal clinical and demographic information segments to various levels that assures that it can only be rebuilt at the interested and authorized parties and no profiling can be extracted from the blockchain itself. Using our proposal the access to a patient's clinical process resists tampering and ransomware attacks that have recently plagued the HIS (Hospital Information Systems) in various countries. The core of the blockchain model assures non-repudiation possible by any of the involved information producers thus maintaining ledger fidelity of the enclosed historical process information. One important side effect of this data infrastructure is that it can be accessed in open form, for research purposes for instance, since no individual re-identification or group profiling is possible by any means.
Cryptocurrencies like Bitcoin have proven to be a phenomenal success. The underlying techniques hold huge promise to change the future of financial transactions, and eventually the way people and companies compute, collaborate, and interact. At the same time, the current Bitcoin-like proof-of-work based blockchain systems are facing many challenges. In more detail, a huge amount of energy/electricity is needed for maintaining the Bitcoin blockchain. In addition, their security holds if the majority of the computing power is under the control of honest players. However, this assumption has been seriously challenged recently and Bitcoin-like systems will fail when this assumption is broken. This research proposes novel blockchain designs to address the challenges. We first propose a novel blockchain protocol, called 2-hop blockchain, by combining proof-of-work and proof-of-stake mechanisms. That said, even if the adversary controls more than 50% computing power, the honest players still have the chance to defend the blockchain via honest stake. Then we revise and implement the design to obtain a practical cryptocurrency system called Twinscoin. In more detail, we introduce a new strategy for difficulty adjustment in the hybrid blockchain and provide an analysis of it. We also show how to construct a light client for proof-of-stake cryptocurrencies and evaluate the proposal practically. We implement our new design. Our implementation uses a recent modular development framework for blockchains, called Scorex. It allows us to change only certain parts of an application leaving other codebase intact.
Eli Ben‐Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner · 6 authors
We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size \(O(\log ^2 n)\); it can be produced with \(O(n \log n)\) field operations and verified with O(n). At 128 bits of security, proofs are less than \({250}\,\mathrm{kB}\) even for several million constraints, more than \(10{\times }\) shorter than prior SNARGs with similar features.
Distributed ledger technologies (DLTs) are currently dominating the field of distributed systems research and development. The Ethereum blockchain is emerging as a popular DLT platform for developing software and applications. Several challenges in Ethereum software development are the complex nature of working with DLTs, the lack of tools for developing on this DLT, and poor documentation of concepts for DLT developers. In this thesis, we provide building blocks that reduce the complexity of DLT operations and lower the barrier to entry into DLT development. We do this by providing a Node.js library, Ethereum-Easy, that simplifies operations on Ethereum. We implement this library into a sample application called Rock, Paper, Scissors (RPS) and built a continuous delivery, continuous integration pipeline for deploying Ethereum code (Jenk-Thereum). This thesis aims to make development on DLTs easier, quicker, and less expensive.
Mohammad Hossein Manshaei, Murtuza Jadliwala, Anindya Maiti, Mahdi Fooladgar
Low transaction throughput and poor scalability are significant issues in public blockchain consensus protocols such as Bitcoins. Recent research efforts in this direction have proposed shard-based consensus protocols where the key idea is to split the transactions among multiple committees (or shards), which then process these shards or set of transactions in parallel. Such a parallel processing of disjoint sets of transactions or shards by multiple committees significantly improves the overall scalability and transaction throughout of the system. However, one significant research gap is a lack of understanding of the strategic behavior of rational processors within committees in such shard-based consensus protocols. Such an understanding is critical for designing appropriate incentives that will foster cooperation within committees and prevent free-riding. In this paper, we address this research gap by analyzing the behavior of processors using a game-theoretic model, where each processor aims at maximizing its reward at a minimum cost of participating in the protocol. We first analyze the Nash equilibria in an N-player static game model of the sharding protocol. We show that depending on the reward sharing approach employed, processors can potentially increase their payoff by unilaterally behaving in a defective fashion, thus resulting in a social dilemma. In order to overcome this social dilemma, we propose a novel incentive-compatible reward sharing mechanism to promote cooperation among processors. Our numerical results show that achieving a majority of cooperating processors (required to ensure a healthy state of the blockchain network) is easier to achieve with the proposed incentive-compatible reward sharing mechanism than with other reward sharing mechanisms.
Thach Ngoc Nguyen, Christian Servín, Владик Крейнович
Nowadays, most financial transactions are based on a centralized system, when all the transaction records are stored in a central location. This centralization makes the financial system vulnerable to cyber-attacks. A natural way to make the financial system more robust and less vulnerable is to switch to decentralized currencies. Such a transition will also make financial system more transparent. Historically first currency of this type -- bitcoin -- use a large amount of electric energy to mine new coins and is, thus, not scalable to the level of financial system as a whole. A more realistic and less energy-consuming scheme is provided by proof-of-stake currencies, where the right to mint a new coin is assigned to a randomly selected user, with probability depending of the user's stake (e.g., his/her number of coins). What probabilities should we choose? In this paper, we find the probability selection that provides the optimal result -- optimal in the sense that it is the least inductive to cheating.
We introduce BitML, a domain-specific language for specifying contracts that regulate transfers of bitcoins among participants, without relying on trusted intermediaries. We define a symbolic and a computational model for reasoning about BitML security. In the symbolic model, participants act according to the semantics of BitML, while in the computational model they exchange bitstrings, and read/append transactions on the Bitcoin blockchain. A compiler is provided to translate contracts into standard Bitcoin transactions. Participants can execute a contract by appending these transactions on the Bitcoin blockchain, according to their strategies. We prove the correctness of our compiler, showing that computational attacks on compiled contracts are also observable in the symbolic model.
Konstantinos Chalkias, James Brown, Mike Hearn, Tommy Lillehagen · 6 authors
Inspired by the blockchain architecture and existing Merkle tree based signature schemes, we propose BPQS, an extensible post-quantum (PQ) resistant digital signature scheme best suited to blockchain and distributed ledger technologies (DLTs). One of the unique characteristics of the protocol is that it can take advantage of application-specific chain/graph structures in order to decrease key generation, signing and verification costs as well as signature size. Compared to recent improvements in the field, BPQS outperforms existing hash-based algorithms when a key is reused for reasonable numbers of signatures, while it supports a fallback mechanism to allow for a practically unlimited number of signatures if required. We provide an open source implementation of the scheme and benchmark it.