We translate the expand-and-extract framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting. While they use it to obtain a synchronous BA with \(2^{-\lambda }\) error probability in \(\lambda +1\) rounds, we achieve asynchronous BA in \(\lambda +3\) rounds. At the heart of their solution is a proxcensus primitive, which is used to reach graded agreement with \(2^r+1\) grades in r rounds by reducing proxcensus with \(2s-1\) grades to proxcensus with s grades in one round. The expand-and-extract paradigm relies on proxcensus to expand binary inputs to \(2^\lambda +1\) grades in \(\lambda \) rounds before extracting a binary output by partitioning the grades using a \(\lambda \) bit common coin. However, this proxcensus protocol does not translate to the asynchronous setting without lowering the corruption threshold or using more rounds in each recursive step. Instead, we define validated proxcensus and show that it can be instantiated in asynchrony with the same recursive structure and round complexity as synchronous proxcensus. The main technique is to attach justifiers to all messages which forces the adversary to choose between only sending useful messages or being ignored.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Short Paper: A New Way to Achieve Round-Efficient Asynchronous Byzantine Agreement

  • Simon Holmgaard Kamp

摘要

We translate the expand-and-extract framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting. While they use it to obtain a synchronous BA with \(2^{-\lambda }\) error probability in \(\lambda +1\) rounds, we achieve asynchronous BA in \(\lambda +3\) rounds. At the heart of their solution is a proxcensus primitive, which is used to reach graded agreement with \(2^r+1\) grades in r rounds by reducing proxcensus with \(2s-1\) grades to proxcensus with s grades in one round. The expand-and-extract paradigm relies on proxcensus to expand binary inputs to \(2^\lambda +1\) grades in \(\lambda \) rounds before extracting a binary output by partitioning the grades using a \(\lambda \) bit common coin. However, this proxcensus protocol does not translate to the asynchronous setting without lowering the corruption threshold or using more rounds in each recursive step. Instead, we define validated proxcensus and show that it can be instantiated in asynchrony with the same recursive structure and round complexity as synchronous proxcensus. The main technique is to attach justifiers to all messages which forces the adversary to choose between only sending useful messages or being ignored.