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

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


MPhil Thesis Defence


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

By

Mr. Zhuo CAI


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.


Date:                   Friday, 28 July 2023

Time:                   2:00pm - 4:00pm

Venue:                  Room 3494
                        lifts 25/26

Committee Members:      Dr. Amir Goharshady (Supervisor)
                        Prof. Cunsheng Ding (Chairperson)
                        Dr. Jiasi Shen


**** ALL are Welcome ****