The Blockchain Technology Lab has outdone itself this year having had 7 papers accepted by Financial Cryptography and Data Security 2021. The major international conference covers all aspects of securing transactions and systems.

To view the complete FC21 program, click here

For information about each of the accepted papers, please see below.

Somewhere Statistically Binding Commitment Schemes with Applications

Authors: Prastudy Fauzi, Helger Lipmaa, Zaira Pindado, Janno Siim

Comments by Janno Siim:

A commitment scheme is a cryptographic tool that binds a message to a commitment value while also hiding it.  In this work, we defined a new notion called somewhere statistically binding commitment that perfectly binds specific elements of the committed vector message and perfectly hides the rest of the positions in the vector. This can be seen as a generalization of the Groth-Sahai commitments, which can be used to obtain very efficient zero-knowledge protocols that are one of the main tools for achieving privacy-preserving blockchains.  We show how to use this primitive for two applications. Firstly, we construct a protocol where a client can make queries on a database while both the query and the data unrelated to the query stay private.  Secondly, we show how to use this commitment to obtain very efficient zero-knowledge proofs under weak cryptographic assumptions.

Another Look at Extraction and Randomization of Groth’s zk-SNARK

Authors: Karim Baghery, Markulf Kohlweiss, Janno Siim, Mikhail Volkhov

Comments by Mikhail Volkhov:

The work investigates the properties of one of the most commonly used zk-SNARKs — Groth16, and by analysing its randomizability, shows that it can be used in protocols that were only known before to be realizable by stronger, and less efficient primitives. Furthermore, we suggest two such practical (transformed) instantiations of Groth16, showing their superior efficiency over previous solutions, and compare their relative performance. The work is mostly relevant to the practical SNARK-related applications, for example anonymous cryptocurrencies and privacy-preserving smart contracts.

Mining for Privacy:  How to Bootstrap a Snarky Blockchain

Authors: Thomas Kerber,  Aggelos Kiayias, Markulf Kohlweiss

Comments by Thomas Kerber:

In Mining for Privacy, we improve on the process of securely initialising zk-SNARKs — a process creating “toxic waste” which can break their security. It is necessary to trust that one of the participants in the initialisation securely deleted their part of the toxic waste. We remove the possibility of maliciously selecting these participants, by relying on proof-of-work to perform the selection.

SOK: Communication Accross Distributed Ledgers

Authors: Alexei Zamyatin, Mustafa Al-Bassam, Dionysis Zindros, Lefteris Kokoris-Kogias, Pedro Moreno-Sanchez,  Aggelos Kiayias, William J. Knottenbelt

Comments by Dionysis Zindros:

Recent developments in blockchain protocols have allowed different chains, typically isolated from one another, to communicate with each other. The space has quickly evolved to include a variety of such technologies with different trust and network assumptions. However, the question of transferring data in a “fair” manner between systems is an old problem in the field of database systems. This work places these new developments into historical context and organizes them into a taxonomy so that they can be compared and contrasted.

Efficient State Management in Distributed Ledgers

Authors: Nikos Karayannidis, Dimitris Karakostas, Aggelos Kiayias

Comments by Dimitris Karakostas:

Motivated by the inefficiencies of existing systems, which often lead to Denial-of-Service attacks, our work explores how to minimize the computation  requirements for maintaining a distributed ledger’s state. We treat this question as an optimization problem and devise a framework to evaluate the cost and identify the most efficient way of transacting, while also exploring the properties that transaction fees should possess, in order to incentivize users to adopt the proposed best practices.

Fast Isomorphic State Channels

Authors: Manuel Chakravarty, Sandro Coretti, Matthias Fitzi, Peter Gazi, Philipp Kant, Aggelos Kiayias, Alexander Russell

Comments by Sandro Coretti:

One approach to scaling blockchains are so-called state channels, which can process transactions away from the mainchain and only fall back to the mainchain when there are disputes. The Hydra Head Protocol provides isomorphic, multi-party state channels for fast and high-throughput offchain transaction processing. The term “isomorphic” refers to the ability to use the same smart-contract system in the state channels as on the mainchain. This allows smart contracts to be transferred seamlessly from the mainchain to the state channels (so-called heads) and back.

In our paper we establish strong security properties for the Hydra protocol, and we present and evaluate extensive simulation results that demonstrate that Hydra approaches the physical limits of the network in terms of transaction confirmation time and throughput while keeping storage requirements at the lowest possible.

Multi-instance Publicly Verifiable Time-lock Puzzle and its Applications

Authors:  Aydin Abadi, Aggelos Kiayias

Comments by Aydin Abadi:

Time-lock puzzles are elegant protocols that enable a party to lock a message such that no one else can unlock it, until a certain time elapses. Nevertheless, existing schemes are not suitable for the case where a server is given multiple instances of a puzzle scheme at once and it must unlock them at different points in time.  In this paper, we put forth and formally define a primitive called “multi-instance time-lock puzzle” which allows composing a puzzle’s instances. We propose a candidate construction: “chained time-lock puzzle” (C-TLP). It allows the server, given instances’ composition, to solve puzzles sequentially and efficiently. We present concrete applications of the primitive and demonstrate its use case in a blockchain-based solution. Specifically, we combine C-TLP with a smart contract and apply the combination to “outsourced proofs of retrievability” research line, and propose “smarter outsourced proofs of retrievability” (SO-PoR) scheme which offers a combination of real-time detection and fair payment while imposing very low overhead, that makes it particularly suitable for mission-critical data.