OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA

• URL: http://arxiv.org/abs/2501.00214v1
• Date: Tue, 31 Dec 2024 01:30:24 GMT
• Title: OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA
• Authors: Jinyuan Chen,
• Abstract summary: We propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr.
• Score: 15.464948077412021
• License:
• Abstract: In this work, we propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. This protocol achieves MVBA consensus on a message $\boldsymbol{w}$ with expected $O(n |\boldsymbol{w}|\log n + n^2 \log q)$ communication bits, expected $O(n^2)$ messages, expected $O(\log n)$ rounds, and expected $O(\log n)$ common coins, under optimal resilience $n \geq 3t + 1$ in an $n$-node network, where up to $t$ nodes may be dishonest. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. When error correction codes with a constant alphabet size (e.g., Expander Codes) are used, $q$ becomes a constant. An MVBA protocol that guarantees all required properties without relying on any cryptographic assumptions, such as signatures or hashing, except for the common coin assumption, is said to be information-theoretically secure (IT secure). Under the common coin assumption, an MVBA protocol that guarantees all required properties in all executions is said to be error-free. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^2 \log n)$ communication bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under a relaxed resilience (RR) of $n \geq 5t + 1$. Additionally, we propose a hash-based asynchronous MVBA protocol, called OciorMVBAh. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^3)$ bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under optimal resilience $n \geq 3t + 1$.

Related papers

• Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement [23.27199615640474]
  We present a novel reduction from multivalued BA to binary BA. As our reduction uses multivalued WA, we design two new efficient WA protocols for $ell$-bit inputs. Our WA protocols extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and near-optimal security.
  arXiv  Detail & Related papers  (2025-02-04T13:44:41Z)
• OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement [15.464948077412021]
  We propose an error-free, information-theoretically secure multi-valued asynchronous Byzantine agreement protocol, called OciorABA. In our protocol design, we introduce a new primitive: asynchronous partial vector agreement (APVA)
  arXiv  Detail & Related papers  (2025-01-20T23:36:11Z)
• Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
  We consider an asynchronous network of $n$ message-sending parties, up to $t$ of which are byzantine. We study approximate agreement, where the parties obtain approximately equal outputs in the convex hull of their inputs. This takes $Theta(n2)$ messages per reliable broadcast, or $Theta(n3)$ messages per iteration.
  arXiv  Detail & Related papers  (2024-08-10T09:03:06Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
  arXiv  Detail & Related papers  (2024-04-16T00:56:36Z)
• Compression for Qubit Clocks [55.38708484314286]
  We propose a compression protocol for $n$ identically prepared states of qubit clocks. The protocol faithfully encodes the states into $(1/2)log n$ qubits and $(1/2)log n$ classical bits.
  arXiv  Detail & Related papers  (2022-09-14T09:45:53Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
  arXiv  Detail & Related papers  (2022-07-07T06:16:19Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.