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 (, 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.
The 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 be constant, . If the walk reaches either or , it stops. Define the two quantities below.
It just so happens that given enough time, the walk either ruins or escapes. 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?
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.
In this post, I am going to review two erasure codes: the Blaum-Bruck-Vardy code and the BASIC code (also here). These are erasure codes, which means, their purpose is to encode a number of data disks into a number of coding disks so that when one or more data/coding disks fail, the failed disk can be reconstructed using the existing data and coding disks.
A strength of these codes is that although the algebra is described on extension fields/rings over , the encoding/decoding process uses only Boolean addition/rotation operation and no finite field operation. These codes are also MDS (Maximum Distance Separable), which means they have the largest possible (minimum) distance for a fixed message-length and codeword-length.
(Recall that if a code has data components and parity components in its generator matrix in standard form, its distance is at most by the Singleton bound. Hence the code is MDS if and only if it can tolerate arbitrary disk failures.)
The BASIC code does the following things in relations to the BBV code:
Adds a virtual parity bit after each disk, giving each disk an even parity
Does polynomial arithmetic modulo instead of as in the case of BBV code
Shows equivalence to the BBV code by making a nice observation via Chinese Remainder Theorem
Proves MDS property for any number of coding disks when is “large enough” and has a certain structure
Open Question: What is the least disk size for which these codes are MDS with arbitrary distance?
Let . Let with distinc s. Let be a set of distinct nonnegative row-powers. Consider the Generalized Vandermonde matrix . When , this matrix becomes the ordinary Vandermonde matrix, .
An equivalent description of is the largest row-power and the set of missing rows from : that is, the items that are in but not in . Let be this set. Define the punctured Generalized Vandermonde matrix . Let be the th elementary symmetric polynomial.
[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]
Currently, we are asking whether all submatrices of the order- Vandermonde matrix over a finite extension of are invertible where is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.
We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.
Let denote an arithmetic progression of length $latek k$. Let for .
The Szemerédi theorem says, any “sufficiently dense” subset contains infinitely many for all . A finitary version says: Fix your favourite . Then, there exists a natural such that if you look any subset of size at least , you will find an . Yet another version says:
Szemerédi’s Theorem. The size of the largest subset without an cannot be too large; in particular, it is .
Recall that a function is if it grows too slow compared to , so that .
I am studying a coding theory problem. The question is this:
Open Question: Is there a prime and a positive integer such that all submatrices of the Discrete Fourier Transform matrix over the field are nonsingular?
Currently, I have only counterexamples: Let be the degree of the smallest extension over which contains a nontrivial th root of unity. Then, I know a lot of primes for which the matrix has a singular submatrix.
Every time I think “Now I understand the Fourier Transform,” I am wrong.
Doing the Fourier Transform of a function is just seeing it from “another” point of view. The “usual” view of a function is in the standard basis . For example, can be seen as a vector (in the basis given by the elements in the domain) whose coordinates are the evaluations of on the elements in the domain. It can also be seen as a polynomial (in the monomial basis) whose coefficients are these evaluations. Let us call this vector .
The same function can also be seen from the “Fourier basis”, which is just another orthogonal basis, formed by the basis vectors . The th coordinate in the new basis will be given by inner product between and the th basis vector . We call these inner products the Fourier coefficients. The Discrete Fourier Transform matrix (the DFT matrix) “projects” a function from the standard basis to the Fourier basis in the usual sense of projection: taking the inner product along a given direction.
In this post, I am going to use elementary group theoretic notions, polynomials, matrices, and vectors. The ideas in this post will be similar to this Wikipedia article on Discrete Fourier Transform.
Let be a prime number. We know that . Let be the ring the polynomials with indeterminate and coefficients in . The polynomial factors over as follows for various :
None of the factors above can be factored anymore, hence they are irreducible over . Let us call the trivial factor since the root already belongs to . But why do we have two nontrivial irreducible factors of , each of degree 3, whereas has only one non-trivial irreducible factor of degree 12? It appears that either there is only one nontrivial factor, or the degree of all nontrivial factors is the same. Why?
Let for a prime . We are interested in the structure of the ring . Via the Chinese Remainder Theorem, this question is equivalent to finding a factorization of over . Suppose factors in as
where each is an irreducible polynomial. What are the degrees of ? What is ?
We claim that where is the multiplicative order of mod .
This structure has been used in a beautifully instructive paper by Evra, Kowalski, and Lubotzky. (Yes, the one in Lubotzky-Philip-Sarnak.) In this paper, they have established connections among the Fourier transform, uncertainty principle, and dimension of ideals generated by polynomials in the ring above. We’ll talk about these connections in another post. The content of this post is Proposition 2.6(3) from their paper.