This Week in Blockchain Research Issue #78

Issue #78

Issue #78

Paper of the Week:

Paper Title: Round-Efficient Byzantine Broadcast under Strongly Adaptive and Majority Corruptions.


  1. Are there (randomized) BB protocols with sublinear round complexity, and secure in the presence of a strongly adaptive adversary that is allowed to corrupt a majority of the nodes?

  2. This work presents the first affirmative answer to the above question, significantly improving our understanding of the round complexity of BB.

  3. To achieve this, this work relies on the existence of a trusted setup, the decisional linear assumption in suitable bilinear groups, as well as the existence of time-lock puzzles with suitable hardness parameters.

  4. The authors state that they do not know if the trusted setup is necessary, but some form of setup is necessary: without any setup, Byzantine Broadcast is impossible under 1/3 or more corruptions.

  5. They also assume the existence of time-lock puzzles; therefore, another open question is to understand whether time-lock puzzles are necessary. In fact, without time-lock puzzles, even sublinear-round BB under 51% strongly adaptive corruption remains open.

  6. Another natural question is whether we can improve the round complexity to expected constant.

AuthorsJun Wan*, Hanshen Xiao*, Srinivas Devadas*, and Elaine Shi†,

Affiliations: * MIT and † Cornell.


1. Paper Title: Taming the many EdDSAs.

Summary: This paper analyses security of concrete instantiations of EdDSA by identifying exploitable inconsistencies between standardization recommendations and Ed25519 implementations.

Authors: Konstantinos Chalkias*†, François Garillot*†, and Valeria Nikolaenko*†,

Affiliations* Novi and † Facebook.

2. Paper Title: Two-round trip Schnorr multi-signatures via delinearized witnesses.

Summary: A new m-entwined ROS problem that tweaks a random inhomogeneities in an overdetermined solvable system of linear equations (ROS) problem in a scalar field using an associated group.

Authors: Handan Kilinc Alper* and Jeffrey Burdges*,

Affiliations* Web 3.0 Foundation.

3. Paper Title: Random-index PIR with Applications to Large-Scale Secure MPC.

Summary: Combined with recent techniques for secure-MPC with stateless parties, the results yield a new secrets-on-blockchain construction.

Authors: Craig Gentry*, Shai Halevi*, Bernardo Magri†, Jesper Buus Nielsen†, and Sophia Yakoubov‡,

Affiliations* Algorand Foundation, † Concordium Blockchain Research Center, and ‡ Aarhus University.

4. Paper Title: Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation.

Summary: A new notion of cross-incremental proof (dis)aggregation for authenticated dictionaries, which enables aggregating multiple proofs with respect to different dictionaries into a single, succinct proof.

Authors: Alin Tomescu*, Yu Xia†, and Zachary Newman†,

Affiliations* VMware Research and † MIT CSAIL.

5. Paper Title: Game-theoretic Approach to Decision-making Problem for Blockchain Mining.

Summary: Model the decision-making problem for the participation in the mining as a non-cooperative game and show that hysteresis phenomena due to the coexistence of two pure Nash equilibria and jump phenomena of the choice of strategy profiles can be observed depending on the change of the mining reward.

AuthorsKosuke Toda*, Naomi Kuze*, and Toshimitsu Ushio*,

Affiliations: * University, Toyonaka.


No papers.


1. Paper Title: Using Homomorphic hashes in coded blockchains.

Summary: Introducing homomorphic hashes in coded blockchains.

Authors: Doriane Perard*, Xavier Goffin*, and Jerome Lacan*,

Affiliations* Universite de Toulouse.


No papers.


No papers.


1. Paper Title: The Blockchain Evolution and Revolution of Accounting.

Summary: This chapter explores applications of blockchain technology in finance, auditing, financial reporting and supply chain.

AuthorsKimberlyn George* and Panos N. Patatoukas*,

Affiliations: * University of California, Berkeley.

2. Paper Title: Digital Governance: Theory, Policy and Practice.

Summary: This paper aims to discuss key points of blockchain based decentralized governance and its role in sustainable economic growth of a nation.

AuthorsDivyan Sethuramalingam*,

Affiliations: * Harvard Business School.

3. Paper Title: Reverse Information Sharing: Reducing Costs in Supply Chains with Yield Uncertainty.

Summary: This paper studies a supply chain for a perishable good consisting of N retailers who compete for supply and practice dual sourcing, but do not have transparency to the inventory distributions of their suppliers a priori. The paper develops an analytical model to capture the retailers’ ordering dynamics over repeated iterations.

AuthorsPavithra Harsha*, Ashish Jagmohan*, Retsef Levi†, Elisabeth Paulson†, and Georgia Perakis†,

Affiliations: * IBM and † MIT.

Conferences, Journals, & CFPs:

Conferences’ Videos:



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.