Home

tl;dr: We give on overview of bilinear accumulators, a more communication-efficient alternative to Merkle Hash Trees (MHTs) that comes at an increase in computation. Put simply, bilinear accumulators are commitments to sets with constant-sized (non)membership proofs. For more details, see this full post on Decentralized Thoughts.

These are some notes on how to efficiently multiply a Toeplitz matrix by a vector. I was writing these for myself while implementing the new amortized KZG proofs by Feist and Khovratovich, but I thought they might be useful for you too.

A polynomial $\phi$ of degree $d$ is a vector of $d+1$ coefficients: \begin{align} \phi &= [\phi_0, \phi_1, \phi_2, \dots, \phi_d] \end{align} For example, $\phi = [1, 10, 9]$ is a degree 2 polynomial. Also, $\phi’ = [1, 10, 9, 0, 0, 0]$ is also a degree 2 polynomial, since the zero coefficients at the end do not count. But $\phi’’ = [...

tl;dr: We “authenticate” a polynomial multipoint evaluation using Kate-Zaverucha-Goldberg (KZG) commitments. This gives a new way to precompute $n$ proofs on a degree $t$ polynomial in $\Theta(n\log{t})$ time, rather than $\Theta(nt)$. The key trade-off is that our proofs are logarithmic-sized, rather than constant-sized. Nonetheless, we use ou...

tl;dr: Most people implement threshold BLS naively, using a $O(t^2)$ algorithm to compute Lagrange coefficients. We show how to use a faster $O(t\log^2{t})$-time algorithm for this. This makes aggregating $(t,n)$ BLS threshold signatures much faster, both at small and large scales. The question of scaling threshold signatures came to us at VMw...

This is a re-exposition of a post by Dan Boneh, Ben Fisch, Ariel Gabizon on how to obtain a constant-sized range proof from constant-sized polynomial commitments. This post was moved to Decentralized Thoughts.

This is Ryan Holiday’s “Ego is the enemy” in bullet-point form. These are the ideas I found interesting from the book, without the excellent stories used to back them. For those, you’ll have to buy the book. I changed some of the excerpts from 2nd person to 1st person, so they resonate more. I kept the same table of contents as in the book, exc...

These are my notes from a quick workshop at Stony Brook University given by Professor Michael Bender and Professor Rob Johnson in May 2012. How to make the presentation Prefix competitive If you had one slide, make your presentation. If you had two slides, extend your 1 slide presentation. 1 slide -> 2 slides -> 3 slides. Quick...