Honeybee: Decentralized Peer Sampling with Verifiable Random Walks for Blockchain Data Sharding

• URL: http://arxiv.org/abs/2402.16201v2
• Date: Mon, 22 Jul 2024 22:33:07 GMT
• Title: Honeybee: Decentralized Peer Sampling with Verifiable Random Walks for Blockchain Data Sharding
• Authors: Yunqi Zhang, Shaileshh Bojja Venkatakrishnan,
• Abstract summary: Key challenge toward implementing sharding is verifying whether the entirety of a block's data is available in the network. We present a primitive sampling algorithm for present nodes that uses random nodes. We show that the quality achieved by Honeybee is significantly better compared to the state-of-the-art sampling algorithm.
• Score: 6.120657470247715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Data sharding$\unicode{x2013}$in which block data is sharded without sharding compute$\unicode{x2013}$is at the present the favored approach for scaling Ethereum and other popular blockchains. A key challenge toward implementing data sharding is verifying whether the entirety of a block's data is available in the network (across its shards). A central technique proposed to conduct this verification uses erasure-coded blocks and is called data availability sampling (DAS). While the high-level protocol details of DAS have been well discussed in the community, discussions around how such a protocol will be implemented at the peer-to-peer layer are lacking. We identify random sampling of nodes as a fundamental primitive necessary to carry out DAS and present Honeybee, a decentralized algorithm for sampling nodes that uses verifiable random walks. Honeybee is secure against attacks even in the presence of a large number of Byzantine nodes (e.g., 50% of the network). We evaluate Honeybee through experiments and show that the quality of sampling achieved by Honeybee is significantly better compared to the state-of-the-art. Our proposed algorithm has implications for DAS functions in both full nodes and light nodes.

Related papers

• Performance Evaluation of Hashing Algorithms on Commodity Hardware [0.0]
  This report presents a performance evaluation of three popular hashing algorithms Blake3, SHA-256, and SHA-512. These hashing algorithms are widely used in various applications, such as digital signatures, message authentication, and password storage. The results of the evaluation show Blake3 generally outperforms both SHA-256 and SHA-512 in terms of throughput and latency.
  arXiv  Detail & Related papers  (2024-07-11T08:31:02Z)
• Scalable Zero-Knowledge Proofs for Verifying Cryptographic Hashing in Blockchain Applications [16.72979347045808]
  Zero-knowledge proofs (ZKPs) have emerged as a promising solution to address the scalability challenges in modern blockchain systems. This study proposes a methodology for generating and verifying ZKPs to ensure the computational integrity of cryptographic hashing.
  arXiv  Detail & Related papers  (2024-07-03T21:19:01Z)
• RecAGT: Shard Testable Codes with Adaptive Group Testing for Malicious Nodes Identification in Sharding Permissioned Blockchain [8.178194928962311]
  We propose RecAGT, a novel identification scheme aimed at reducing communication overhead and identifying potential malicious nodes. First, shard testable codes are designed to encode the original data in case of a leak of confidential data. Second, a new identity proof protocol is presented as evidence against malicious behavior. Third, adaptive group testing is chosen to identify malicious nodes.
  arXiv  Detail & Related papers  (2023-11-05T07:43:48Z)
• Trustless Privacy-Preserving Data Aggregation on Ethereum with Hypercube Network Topology [0.0]
  We have proposed a scalable privacy-preserving data aggregation protocol for summation on the blockchain. The protocol consists of four stages as contract deployment, user registration, private submission and proof verification.
  arXiv  Detail & Related papers  (2023-08-29T12:51:26Z)
• Proof-of-work consensus by quantum sampling [0.0]
  We propose to use a variant, called coarse-grained boson-sampling (CGBS), as a quantum Proof-of-Work (PoW) scheme for blockchain consensus. The users perform boson-sampling using input states that depend on the current block information, and commit their samples to the network. By combining rewards to miners committing honest samples together with penalties to miners committing dishonest samples, a Nash equilibrium is found that incentivizes honest nodes.
  arXiv  Detail & Related papers  (2023-05-31T13:58:40Z)
• QuTE: decentralized multiple testing on sensor networks with false discovery rate control [130.7122910646076]
  This paper designs methods for decentralized multiple hypothesis testing on graphs equipped with provable guarantees on the false discovery rate (FDR) We consider the setting where distinct agents reside on the nodes of an undirected graph, and each agent possesses p-values corresponding to one or more hypotheses local to its node. Each agent must individually decide whether to reject one or more of its local hypotheses by only communicating with its neighbors, with the joint aim that the global FDR over the entire graph must be controlled at a predefined level.
  arXiv  Detail & Related papers  (2022-10-09T19:48:39Z)
• Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
  We propose a non-additive and deterministic smoothing method, Deterministic Smoothing with Splitting Noise (DSSN) In contrast to uniform additive smoothing, the SSN certification does not require the random noise components used to be independent. This is the first work to provide deterministic "randomized smoothing" for a norm-based adversarial threat model.
  arXiv  Detail & Related papers  (2021-03-17T21:49:53Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41:59Z)
• Deep Momentum Uncertainty Hashing [65.27971340060687]
  We propose a novel Deep Momentum Uncertainty Hashing (DMUH) It explicitly estimates the uncertainty during training and leverages the uncertainty information to guide the approximation process. Our method achieves the best performance on all of the datasets and surpasses existing state-of-the-art methods by a large margin.
  arXiv  Detail & Related papers  (2020-09-17T01:57:45Z)
• Improving Face Recognition by Clustering Unlabeled Faces in the Wild [77.48677160252198]
  We propose a novel identity separation method based on extreme value theory. It greatly reduces the problems caused by overlapping-identity label noise. Experiments on both controlled and real settings demonstrate our method's consistent improvements.
  arXiv  Detail & Related papers  (2020-07-14T12:26:50Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  Homomorphic Encryption (HE) is receiving more and more attention recently for its capability to do computations over the encrypted field. We propose a novel general distributed HE-based data mining framework towards one step of solving the scaling problem. We verify the efficiency and effectiveness of our new framework by testing over various data mining algorithms and benchmark data-sets.
  arXiv  Detail & Related papers  (2020-06-17T18:14:30Z)

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.