USI - Email

Archive / INF Seminars / INF_2025_05_09_MauriceHerlihy

USI - Email

	Cross-Chain Consensus

Host: Prof. Marc Langheinrich

Friday

09.05

USI Campus EST, Room C1.03

14:30 - 15:30


	Maurice Herlihy Brown University

Abstract: As decentralized ledgers and blockchains become more common, cross-chain interoperability becomes essential to making those ledgers useful. In a cross-chain task, $m$ active, Byzantine parties undertake to trade assets using n passive but trustworthy smart contracts. Each party seeks an outcome that maximizes its own utility in the presence of Byzantine counterparties. This talk introduces a novel task called "cross-chain consensus''. We show that cross-chain consensus is \emph{universal}, meaning that any cross-chain consensus protocol can be transformed into a protocol for any other well-formed cross-chain task. We show that cross-chain consensus is impossible using unsigned messages, even if communication channels are authenticated. If each party can generate signed messages verifiable on all the blockchains, then there is a tight bound of $\Theta(m)$ communication rounds, where $m$ is the number of participating parties. Moreover, there is a communication-round optimal protocol that uses a finite number of precomputed signed messages.

Joint work with Sucharita Jayanti.

Biography: Maurice Herlihy has an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University and the staff of DEC Cambridge Research Lab. He is the recipient of the 2003 Dijkstra Prize in Distributed Computing, the 2004 Gödel Prize in theoretical computer science, the 2008 ISCA influential paper award, the 2012 Edsger W. Dijkstra Prize, and the 2013 Wallace McDowell award. He received a 2012 Fulbright Distinguished Chair in the Natural Sciences and Engineering Lecturing Fellowship, and he is fellow of the ACM, a fellow of the National Academy of Inventors, the National Academy of Engineering, and the National Academy of Arts and Sciences. In 2022, he won his third Dijkstra Prize.

Prof. Maurice Herliyi will be receving the USI Honorary doctorate at the Dies Academicus on 10 May 2025.