Bitcoin

My current research interest is: Bitcoin, smart contracts, cryptography, protocols. I have a lot to learn.

I'm particularly interested in techniques that enhance Bitcoin's smart contract capabilities without compromising on fundamental properties, like scalability, decentralization and censorship-resistance.

While a lot of useful and great ideas are first explored in altcoins, I'm convinced that most of them will eventually find their way into Bitcoin, without requiring substantial changes to the base layer.

Merkleize All The Things  -  github

This research explores a type of covenant (and some additional transaction introspection) that would enable very general classes of smart contracts in bitcoin.

Such covenants could be enabled as a soft-fork, with little to no additional workload for fully validating nodes.

The writeup argues that such covenants would enable chains of bitcoin transactions to perform arbitrary computations. Moreover, it would make a generic fraud proof protocol possible, allowing to create scalable layer-2.

Fast hash-based additive accumulators (draft)  -  code

In this work, I explore a class of cryptographic accumulators that I believe has the potential to allow for extensions of Bitcoin's scripting capabilities, without sacrificing on the fundamental properties that make it easy for anyone to run a full node. These accumulators only allow to add elements to a set, and are cheap to maintain (should they become part of the consensus rules), while moving the cost of proving set membership to the interested parties. Therefore, while the "state" grows arbitrarily, no validating nodes needs to hold more than a short "summary" of it.

While an append-only state is less flexible than a key-value store (as in Ethereum), I believe that many of the interesting protocols using smart contracts can be adapted to use an append-only state managed by an accumulator.

This will be the topic of further exploration (any comment or insight is greatly appreciated).

Algorithms

During my PhD at IDSIA, I focused on the field of Approximation Algorithms, advised by Fabrizio Grandoni.

Basically: take some hard optimization problems (usually NP-hard). How close can we get to the optimal solution with an efficient algorithm?

It is a branch of theoretical computer science that attempts to classify how hard problems are, from a rather theoretical point of view.

A common theme among the optimization problems I worked on during my PhD is that they are a little geometric in nature, as they often involve (or can be connected to) placing some rectangles inside some larger containers while trying to maximize or minimize something.

In my thesis I tried to put all the three works under the same common thread.

Approximating Geometric Knapsack via L-packings

with Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Arindam Khan and Andreas Wiese

FOCS, Berkeley, California, 15—17 October 2017.

Improved Pseudo-Polynomial-Time Approximation for Strip Packing

with Waldo Gálvez, Fabrizio Grandoni and Arindam Khan

FSTTCS, Chennai, India, 13—15 December 2016.

Improved Approximation Algorithms for Unsplittable Flow on a Path with Time Windows.

with Fabrizio Grandoni and Sumedha Uniyal

WAOA, Patras, Greece, 17—18 September 2015.