Our paper, titled How to Realize a Graph on Random Points, has gone up in the Arxiv. I’ll write more about it in future posts.

**Abstract:**

Continue reading “Our Paper on Realizing a Graph on Random Points”

Skip to content
The magic of mathematics and theoretical computer science is all the unexpected connections. You start looking for general principles and then mysterious connections emerge. Nobody can say why this is. — Robert Endre Tarjan

# Category: Mathematics

# Our Paper on Realizing a Graph on Random Points

# Things I Want to Remember

# Notes On Unbiased Random Walks

# Characterizing the Adversarial Grinding Power in a Proof-of-Stake Blockchain Protocol

# Forkable Strings are Rare

# Some Facts about the Gambler’s Ruin Problem

# A Publicly Verifiable Secret Sharing Scheme

Our paper, titled How to Realize a Graph on Random Points, has gone up in the Arxiv. I’ll write more about it in future posts.

**Abstract:**

Continue reading “Our Paper on Realizing a Graph on Random Points”

Advertisements

Imagine that a particle is walking in a two-dimensional space, starting at the origin . At every time-step (or “epoch”) it takes a vertical step. At every step, the particle either moves up by , or down by $altex -1$. This walk is “unbiased” in the sense that the up/down steps are equiprobable.

In this post, we will discuss some natural questions about this “unbiased random walk.” For example, how long will it take for the particle to return to zero? What is the probability that it will ever reach +1? When will it touch for the first time? Contents of this post are a summary of the Chapter “Random Walks” from the awesome “Introduction to Probability” (Volume I) by William Feller.

*[Contents of this post are based on an ongoing discussion with Alex Russell and Aggelos Kiayias. It contains potentially unpublished material.]*

In a proof-of-stake blockchain protocol such as Ouroboros, at most half of the users are dishonest. While an honest user always extends the longest available blockchain, the dishonest users try to fool him into extending a manipulated blockchain. Here, the user who is allowed to issue a block at any time-slot is called the “slot leader.” As it happens, a number of future slot leaders are computed in advance using the random values present in the blocks. Although counterintuitive, such a scheme ensures that if the adversary does not control more than half the users now, it is very unlikely that he cannot control more than half the slot leaders. The time-slots are divided into “epochs” of length .

In a blockchain protocol such as Bitcoin, the users see the world as a sequence of states. A simple yet functional view of this world, for the purpose of analysis, is a Boolean string of zeros and ones, where each bit is independently biased towards favoring the “bad guys.”

A bad guy is activated when for some . He may try to present the good guys with a conflicting view of the world, such as presenting multiple candidate blockchains of equal length. This view is called a “fork”. A string that allows the bad guy to fork (with nonnegligible probability) is called a “forkable string”. Naturally, we would like to show that forkable strings are rare: that the manipulative power of the bad guys over the good guys is negligible.

**Claim **([1], Bound 2)**.** Suppose is a Boolean string, with every bit independently set to with probability for some . The probability that is forkable is at most .

In this post, we present a commentary on the proof that forkable strings are rare. I like the proof because it uses simple facts about random walks, generating functions, and stochastic domination to bound an apparently difficult random process.

Consider a random walk in the two-dimensional discrete space, where the horizontal direction is indexed by nonnegative time steps and the vertical direction is indexed by integers.

A particle is at its initial position at time . At every time step, it independently takes a step up or down: up with probability and down with probability . If the walk is called *symmetric*. Let and be the probabilities that the particle ever reaches some level or , respectively. When it does, the walk stops. The quantity is the *ruin probability*. We set the initial conditions as .

The Gambler’s Ruin Problem:What is the probability that a walk, starting at some , eventually reaches the origin?

Continue reading “Some Facts about the Gambler’s Ruin Problem”

We all know Shamir’s -Secret Sharing Scheme: A dealer fixes a group and selects a random polynomial of degree at most over this group. He sets the constant coefficient equal to your secret , then distributes arbitrary evaluations of this polynomial as shares to the parties. Any subset of parties can pool their shares and reconstruct the polynomial via Lagrange interpolation.

What if we don’t want to trust the dealer nor the parties? Feldman’s Verifiable Secret Sharing Scheme allows the dealer to publish, in addition to the regular Shamir-shares, a generator of the group along with *proofs* or *commitments* for each coefficient of the polynomial . Each party can verify that his share is correct by testing whether

.

However, the shares are still private. What if we want *everyone* to be able to verify the correctness of all shares without knowing what the shares are? This is achieved by a Publicly Verifiable Secret Sharing Scheme, such as the one developed by Berry Schoenmaker, assuming the discrete log problem is hard.

Continue reading “A Publicly Verifiable Secret Sharing Scheme”