Blockchain Papers

Naoya Shiratori, Mitsuru Tada

No abstract is available for this record.

Munindar P. Singh, Amit K. Chopra

We propose a sociotechnical, yet computational, approach to building decentralized applications that accommodates and exploits blockchain technology. Our architecture incorporates the notion of a declarative, violable contract and enables flexible governance based on formal organizational structures, correctness verification without obstructing autonomy, and a basis for trust.

Carla Ràfols, Javier Silva

No abstract is available for this record.

Alireza Parvizimosaed, Sepehr Sharifi, Daniel Amyot, Luigi Logrippo · 5 authors

No abstract is available for this record.

Fuyuki Kitagawa, Takahiro Matsuda, Takashi Yamakawa

We give a construction of a non-interactive zero-knowledge (NIZK) argument for all \(\mathsf {NP}\) languages based on a succinct non-interactive argument (SNARG) for all \(\mathsf {NP}\) languages and a one-way function. The succinctness requirement for the SNARG is rather mild: We only require that the proof size be \(|\pi |=\mathsf {poly}(\lambda )(|x|+|w|)^c\) for some constant \(c<1/2\), where |x| is the statement length, |w| is the witness length, and \(\lambda \) is the security parameter. Especially, we do not require anything about the efficiency of the verification.

Adriana Iuliana Stancu, Mihaita Dragan

No abstract is available for this record.

Inbar Kaslasi, Guy N. Rothblum, Ron D. Rothblum, Adam Sealfon · 5 authors

No abstract is available for this record.

Geoffroy Couteau, Dominik Hartmann

We put forth a new framework for building pairing-based non-interactive zero-knowledge (\(\mathsf {NIZK}\)) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a \(\varSigma \)-protocol into a \(\mathsf {NIZK}\). Our framework enjoys a number of interesting features: conceptual simplicity, parameters derive from the \(\varSigma \)-protocol; proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying \(\varSigma \)-protocol; fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS; yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments(ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions.

Hila Dahari, Yehuda Lindell

No abstract is available for this record.

Oded Goldreich, Liav Teichner

We initiate a study of super-perfect zero-knowledge proof systems. Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time. In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated by a strict probabilistic polynomial-time that is allowed to fail with probability at most one half. We show that two types of perfect zero-knowledge proof systems can be transformed into super-perfect ones. The first type includes the perfect zero-knowledge interactive proof system for Graph Isomorphism and other systems of the same form, including perfect zero-knowledge arguments for NP. The second type refers to perfect non-interactive zero-knowledge proof sys-tems. We also present a super-perfect non-interactive zero-knowledge proof system for the set

Amiya Behera

More details: https://shivarthu.reaudito.com/ Democracy is about fair and equal treatment of everyone in a country. But itbecomes unrealistic to achieve when political parties have their conflict of interest,and leaders don’t have the expertise to make evidence-based policies and neitherhave the skill and manpower for solving problems that surround our society andecosystem. The new fair democracy provides an elegant way of governance thatseparates the representative responsibility according to their specialization and cangrow into any complexity. The governance is divided into various departments, andeach department is supervised by representatives with expertise in the field. Votersneed to have enough knowledge about the departments and their problems, in orderto vote for the selecting representatives of a department. The selection process ofrepresentatives is difficult in and easy out, which allows only serious and utilitarianactors to hold the responsibility, weeding out frivolous ones.

Damiano Azzolini, Fabrizio Riguzzi, Evelina Lamma

In Bitcoin, if a miner is able to solve a computationally hard problem called proof of work, it will receive an amount of bitcoin as a reward which is the sum of the fees for the transactions included in a block plus an amount inversely proportional to the number of blocks discovered so far. At the moment of writing, the block reward is several orders of magnitude greater than the sum of transaction fees. Usually, miners try to collect the largest reward by including transactions associated with high fees. The main purpose of transaction fees is to prevent network spamming. However, they are also used to prioritize transactions. In order to use the minimum amount of fees, users usually have to find a compromise between fees and urgency of a transaction. In this paper, we develop a probabilistic logic model to experimentally analyze how fees affect confirmation time and miner’s revenue and to predict if an increase of average fees will generate a situation when the miner gets more reward by not following the protocol.

Daiki Miyahara, Tatsuya Sasaki, Takaaki Mizuki, Hideaki Sone

Kakuro is a popular logic puzzle, in which a player fills in all empty squares with digits from 1 to 9 so that the sum of digits in each (horizontal or vertical) line is equal to a given number, called a clue, and digits in each line are all different. In 2016, Bultel, Dreier, Dumas, and Lafourcade proposed a physical zero-knowledge proof protocol for Kakuro using a deck of cards; their proposed protocol enables a prover to convince a verifier that the prover knows the solution of a Kakuro puzzle without revealing any information about the solution. One possible drawback of their protocol would be that the protocol is not perfectly extractable, implying that a prover who does not know the solution can convince a verifier with a small probability; therefore, one has to repeat the protocol to make such an error become negligible. In this paper, to overcome this, we design zero-knowledge proof protocols for Kakuro having perfect extractability property. Our improvement relies on the ideas behind the copy protocols in the field of card-based cryptography. By executing our protocols with a real deck of physical playing cards, humans can practically perform an efficient zero-knowledge proof of knowledge for Kakuro.

Ron van der Meyden

This paper investigates the specification and verification of atomic swap multi-party transactions. It is argued that logics with the ability to express properties of strategies of players in a multi-agent setting are conceptually useful for this purpose, although ultimately, the less expressive setting of temporal logic suffices for verification of concrete implementations. This is illustrated through the use of a model checker to verify atomic swap smart contracts in on-chain and cross-chain settings.

Bojan Marinković, Paola Glavan, Zoran Ognjanović, Thomas Studer

Abstract In this paper we provide a strongly complete axiomatization of a temporal epistemic logic in which non-rigid sets of agents are allowed. Using this framework, we prove a number of properties of the blockchain protocol with respect to the given set of axioms and premises.

Preston Stovall

An adequate semantics for generic sentences must stake out positions across a range of contested territory in philosophy and linguistics. For this reason the study of generic sentences is a venue for investigating different frameworks for understanding human rationality as manifested in linguistic phenomena such as quantification, classification of individuals under kinds, defeasible reasoning, and intensionality. Despite the wide variety of semantic theories developed for generic sentences, to date these theories have been almost universally model-theoretic and representational. This essay outlines a range of proof-theoretic analyses for characterizing generics. Particular attention is given to an expressivist proof-theory that can be traced to 1) work on logical syntax that Carnap undertook prior to his turn toward truth-conditional model theory in the late 1930s, and 2) research on sequent calculi and natural deduction systems that originate in work from Gentzen and Prawitz.1

James Chapman, Roman Kireev, Chad Nester, Philip Wadler

No abstract is available for this record.

Matthew Coudron, William Slofstra

We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is $\mathrm{NP}$-complete to decide whether the classical value of a non-local game is 1 or $1- ε$. Furthermore, as long as $ε$ is small enough, this result does not depend on the gap $ε$. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap $ε$ decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of $\mathrm{MIP}^{co}(2,1,1,s)$ (proofs with two provers, one round, completeness probability $1$, soundness probability $s$, and commuting-operator strategies) can increase without bound as the gap $1-s$ gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class $\mathrm{PZK}$-$\mathrm{MIP}^{co}_δ(2,1,1,s)$ of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap $1-s$ gets arbitrarily small. While we do not know any computable time upper bound on the class $\mathrm{MIP}^{co}$, a result of the first author and Vidick shows that for $s = 1-1/\text{poly}(f(n))$ and $δ= 1/\text{poly}(f(n))$, the class $\mathrm{MIP}^{co}_δ(2,1,1,s)$, with constant communication from the provers, is contained in $\mathrm{TIME}(\exp(\text{poly}(f(n))))$. We give a lower bound of $\mathrm{coNTIME}(f(n))$ (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.

Paolo Bottoni, Daniele Gorla, Stefano Kasangian, Anna Labella

No abstract is available for this record.

Edward A. Lee

No abstract is available for this record.

Srinath Setty

This paper introduces Spartan, a new family of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for the rank-1 constraint satisfiability (R1CS), an NP-complete language that generalizes arithmetic circuit satisfiability. A distinctive feature of Spartan is that it offers the first zkSNARKs without trusted setup (i.e., transparent zkSNARKs) for NP where verifying a proof incurs sub-linear costs—without requiring uniformity in the NP statement’s structure. Furthermore, Spartan offers zkSNARKs with a time-optimal prover, a property that has remained elusive for nearly all zkSNARKs in the literature.

Stefano Tempesta

No abstract is available for this record.

Matteo Campanelli, Dario Fiore, Anaïs Querol

We study the problem of building non-interactive proof systems modularly by linking small specialized SNARKs in a lightweight manner. Our motivation is both theoretical and practical. On the theoretical side, modular SNARK designs would be flexible and reusable. Also, previous works (e.g., Geppetto) consider They have been successfully employed in previous works.(cite prev papers ). These approaches, however, tend to be ad-hoc and to reinventing the wheel. We propose to fill this gap. In practice, specialized SNARKs have the potential to be more efficient than general-purpose schemes, on which most existing works have focused. If a computation naturally presents different components (e.g. one arithmetic circuit and one boolean circuit), a general-purpose scheme would homogenize them to a single representation with a subsequent cost in performance. Through a modular approach one could instead exploit the nuances of a computation and choose the best gadget for each component. Our contribution is LegoSNARK, a toolbox (or framework) for commit-and-prove zkSNARKs (CP-SNARKs) that includes: 1) General composition tools: build new CP-SNARKs from proof gadgets for basic relationssimply. Formalize notion of cc-SNARK. 2) A lifting tool: a compiler to add commit-and-prove capabilities to a broad class of existing zkSNARKsefficiently. This makes them interoperable (linkable) within the same computation. For example, one QAP-based scheme can be used prove one component; another GKR-based scheme can be used to prove another. 3) A collection of succinct proof gadgets for a variety of relations. Additionally, through our framework and gadgets, we are able to obtain new succinct proof systems. Notably: -- LegoGro16, a commit-and-prove version of Groth16 zkSNARK, that operates over data committed with a classical Pedersen vector commitment, and that achieves a 5000× speedup in proving time. -- LegoUAC, a pairing-based SNARK for arithmetic circuits that has a universal, circuit-independent, CRS, and proving time linear in the number of circuit gates (vs. the recent scheme of Groth et al. (CRYPTO'18) with quadratic CRS and quasilinear proving time). -- LegoMM, a CP-SNARK for matrix multiplication that achieves optimal proving complexity.

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

No abstract is available for this record.