A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks

• URL: http://arxiv.org/abs/2309.11250v1
• Date: Wed, 20 Sep 2023 12:21:39 GMT
• Title: A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks
• Authors: Zhuo Cai,
• Abstract summary: We provide a protocol for distributed generation of randomness. It is trustless and generates unbiased random numbers. It is also tamper-proof and no party can change the output or affect its distribution.
• Score: 0.6216023343793144
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Many protocols in distributed computing rely on a source of randomness, usually called a random beacon, both for their applicability and security. This is especially true for proof-of-stake blockchain protocols in which the next miner or set of miners have to be chosen randomly and each party's likelihood to be selected is in proportion to their stake in the cryptocurrency. Current random beacons used in proof-of-stake protocols, such as Ouroboros and Algorand, have two fundamental limitations: Either (i)~they rely on pseudorandomness, e.g.~assuming that the output of a hash function is uniform, which is a widely-used but unproven assumption, or (ii)~they generate their randomness using a distributed protocol in which several participants are required to submit random numbers which are then used in the generation of a final random result. However, in this case, there is no guarantee that the numbers provided by the parties are uniformly random and there is no incentive for the parties to honestly generate uniform randomness. Most random beacons have both limitations. In this thesis, we provide a protocol for distributed generation of randomness. Our protocol does not rely on pseudorandomness at all. Similar to some of the previous approaches, it uses random inputs by different participants to generate a final random result. However, the crucial difference is that we provide a game-theoretic guarantee showing that it is in everyone's best interest to submit uniform random numbers. Hence, our approach is the first to incentivize honest behavior instead of just assuming it. Moreover, the approach is trustless and generates unbiased random numbers. It is also tamper-proof and no party can change the output or affect its distribution. Finally, it is designed with modularity in mind and can be easily plugged into existing distributed protocols such as proof-of-stake blockchains.

Related papers

• Local contextuality-based self-tests are sufficient for randomness expansion secure against quantum adversaries [0.0]
  We show that local contextuality-based self-tests are sufficient to construct a randomness expansion protocol that is secure against unbounded quantum adversaries. Our protocol is based on self-testing from non-contextuality inequalities and we prove that our schemeally produces secure random numbers which are $mathcalO(mstepsilon)$-close to uniformly distributed and private.
  arXiv  Detail & Related papers  (2024-09-30T08:31:46Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• The Rate-Distortion-Perception Trade-off: The Role of Private Randomness [53.81648040452621]
  We show that private randomness is not useful if the compression rate is lower than the entropy of the source. We characterize the corresponding rate-distortion trade-off and show that private randomness is not useful if the compression rate is lower than the entropy of the source.
  arXiv  Detail & Related papers  (2024-04-01T13:36:01Z)
• Improvements on Device Independent and Semi-Device Independent Protocols of Randomness Expansion [0.0]
  Device Independent (DI) and Semi-Device Independent (semi-DI) protocols of randomness expansion are discussed. We introduce enhanced DI and semi-DI protocols that surpass existing ones in terms of output randomness rate, security, or in some instances, both. A notable contribution is the introduction of randomness expansion protocols that recycle input randomness, significantly enhancing finite round randomness rates for DI protocols based on the CHSH inequality violation.
  arXiv  Detail & Related papers  (2023-11-22T17:03:04Z)
• Random Boxes Are Open-world Object Detectors [71.86454597677387]
  We show that classifiers trained with random region proposals achieve state-of-the-art Open-world Object Detection (OWOD) We propose RandBox, a Fast R-CNN based architecture trained on random proposals at each training. RandBox significantly outperforms the previous state-of-the-art in all metrics.
  arXiv  Detail & Related papers  (2023-07-17T05:08:32Z)
• A privacy-preserving publicly verifiable quantum random number generator [48.7576911714538]
  We report the implementation of an entanglement-based protocol that allows a third party to publicly perform statistical tests without compromising the privacy of the random bits. limitations on computing power can restrict an end-user's ability to perform such verification.
  arXiv  Detail & Related papers  (2023-05-18T12:13:48Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle. Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent. The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
  arXiv  Detail & Related papers  (2022-08-31T17:39:29Z)
• Certified Random Number Generation from Quantum Steering [1.0820909926464386]
  Certified randomness protocols have been developed which remove the need for trust in devices by taking advantage of nonlocality. Here, we use a photonic platform to implement our protocol, which operates in the quantum steering scenario. We demonstrate an approach for a steering-based generator of public or private randomness, and the first generation of certified random bits, with the detection loophole closed.
  arXiv  Detail & Related papers  (2021-11-18T03:49:43Z)
• A trustless decentralized protocol for distributed consensus of public quantum random numbers [0.0]
  Quantum random number (QRNG) beacons distinguish themselves from classical counterparts by providing intrinsic unpredictability. We introduce a proof-of-principle experiment of the first consensus protocol producing QRNs in a decentralized environment (dQRNG) Our method is thus suited for distribute systems that requires a bias-resistant, highly secure, and public-verifiable random beacon.
  arXiv  Detail & Related papers  (2021-08-26T21:17:58Z)
• Modeling Sequences as Distributions with Uncertainty for Sequential Recommendation [63.77513071533095]
  Most existing sequential methods assume users are deterministic. Item-item transitions might fluctuate significantly in several item aspects and exhibit randomness of user interests. We propose a Distribution-based Transformer Sequential Recommendation (DT4SR) which injects uncertainties into sequential modeling.
  arXiv  Detail & Related papers  (2021-06-11T04:35:21Z)
• Improved device-independent randomness expansion rates using two sided randomness [3.4376560669160394]
  A device-independent randomness expansion protocol aims to take an initial random string and generate a longer one. We investigate the possible improvement that could be gained using the two-sided randomness. We also consider a modified protocol in which the input randomness is recycled.
  arXiv  Detail & Related papers  (2021-03-12T19:49:17Z)

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.