Issue #70
Paper of the Week:
Paper Title: SPARKs: Succinct Parallelizable Arguments of Knowledge.
TLDR:
If computing a proof takes much longer than the computation, this would cause a significant delay making the system useless in various realistic settings.
This work introduces succinct parallelizable arguments of knowledge (SPARKs) where the prover’s running time is “essentially” optimal.
More precisely, an interactive argument (P, V) is a SPARK if instances solvable in (non-deterministic) parallel time T using p processors can be proven with the following efficiency requirements (ignoring dependence on the security parameter or statement size):
The prover’s parallel time is T + polylog(T · p). (In other words, the prover’s running time is essentially T for large computations!)
The prover uses at most p · polylog(T · p) processors. In other words, the prover preserves the total work and parallelism of the underlying computation up to polylogarithmic factors.
The communication and verifier complexity are polylog(T · p).
The main results consider succinct arguments for arbitrary non-deterministic polynomial-time PRAM computation. Specifically, they consider machines M that run in parallel time T when using p processors.
Authors: Naomi Ephraim*, Cody Freitag* Ilan Komargodski†, and Rafael Pass*,
Affiliations: * Cornell Tech and † NTT Research.
Security:
1. Paper Title: Discouraging Pool Block Withholding Attacks in Bitcoins.
Summary: This work revisits the game-theoretic model for pool block withholding attacks and propose a revised approach to reallocate the reward to the miners.
Authors: Zhihuai Chen*, Bo Li†, Xiaohan Shan‡, Xiaoming Sun*, and Jialin Zhang*,
Affiliations: * University of Chinese Academy of Sciences, † University of Oxford, and ‡ Tsinghua University.
Privacy:
No papers.
Scalability:
1. Paper Title: Lightweight Virtual Payment Channels (Extended Version).
Summary: This work proposes a new variant of Virtual Channels that is based on UTXO and requires only multisignatures and timelocks, that is, it does not require smart-contracts.
Authors: Maxim Jourenko*, Mario Larangeira*†, and Keisuke Tanaka*,
Affiliations: * Tokyo Institute of Technology and † Input Output Hong Kong.
2. Paper Title: Aardvark: A Concurrent Authenticated Dictionary with Short Proofs.
Summary: A novel authenticated dictionary backed by vector commitments with short proofs, applied to the problem of decoupling storage from transaction verification in cryptocurrencies.
Authors: Derek Leung*, Yossi Gilad*, Sergey Gorbunov*, Leonid Reyzin*, Nickolai Zeldovich*,
Affiliations: * Algorand, Inc.
3. Paper Title: Zecale: Reconciling Privacy and Scalability on Ethereum.
Summary: A general purpose aggregator using recursive composition of SNARKs that allows to improve the scalability of SNARK-based applications on Ethereum via aggregation of transactions off-chain.
Authors: Antoine Rondelet*,
Affiliations: * Clearmatics.
Proofs:
1. Paper Title: SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE.
Summary: A succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential Learning With Errors (LWE) assumption.
Authors: Ruta Jawale*, Yael Tauman Kalai†‡, Dakshita Khurana*, and Rachel Zhang‡,
Affiliations: * UIUC, † Microsoft, and ‡ MIT.
Consensus:
1. Paper Title: SklCoin: Toward a Scalable Proof-of-Stake and Collective Signature Based Consensus Protocol for Strong Consistency in Blockchain.
Summary: A new Byzantine consensus protocol and its corresponding software architecture that leverages two ideas: 1) the proof-of-stake concept to dynamically form stake-proportionate consensus groups that represent block miners (stakeholders), and 2) scalable collective signing to efficiently commit transactions irreversibly.
Authors: Zakwan Jaroucheh*, Baraq Ghaleb*, and William J Buchanan*,
Affiliations: * Edinburgh Napier University.
Tokenomics:
1. Paper Title: Authenticating Deeds/Organizing Society Considerations for Blockchain-Based Land Registries.
Summary: The prospects of blockchain for land registries from different theoretically informed angles. Those theories do not aim at predicting future success. Rather, they provide distinct lenses to highlight different aspects and prospects of this technology in practice.
Authors: Gianluca Miscione*, Christine Richter†, and Rafael Ziolkowski‡,
Affiliations: * University College Dublin, † University of Twente, and ‡ University of Zurich.
2. Paper Title: New Models of ‘Intelligent Investing’ for the Post-Crisis Economy.
Summary: This work focuses on developing two models that might provide the basis for a different ‘post-crisis’ economy.
Authors: Mark Fenwick* and Erik P.M. Vermeulen†,
Affiliations: * Kyushu University and † Tilburg University.
3. Paper Title: Inhabiting Different Realities: Incrementalism, Paradigms and the New Prospect.
Summary: This paper queries whether the current vector of regulatory thinking about crypto-assets is capable of achieving the public policy objectives of regulation while not obstructing the exploration of the New Prospect and the possible benefits it might bring to society.
Authors: Syren Johnstone*,
Affiliations: * University of Hong Kong.
4. Paper Title: An Impossible Trinity in Blockchain-based Transactions: Decentralization, Privacy, and Lower Transaction Costs.
Summary: This paper shows that if there is a dilemma between decentralization and privacy protection, such that a more decentralized system increases the risks of data leakage, allowing additional privacy protection within the blockchain network at a cost, such as hiring mixers, does not resolve the initial dichotomy.
Authors: Soo Jin Kim*
Affiliations: * ShanghaiTech University.
Conferences, Journals, & CFPs:
September 17-18 - Cryptocurrencies and Blockchain Technology (CBT’2020) (United Kingdom)
October 21-23 - The second ACM conference on Advances in Financial Technologies (AFT’20) (New York City)
Conferences’ Videos:
Jobs:
RFPs:
This newsletter is for informational purposes only. This content does not in any way constitute an offer or solicitation of an offer to buy or sell any investment solution or recommendation to buy or sell a security; nor it is to be taken as legal, business, investment, or tax advice. In fact, none of the information in this or other content on zk Capital should be relied on in any manner as advice. None of the authors, contributors, or anyone else connected with zk Capital, in any way whatsoever, can be responsible for your use of the information contained in this newsletter.