Topic: Bitcoin Computer Science research topics (Read 1529 times)

Thanks for the advice. I'm also talking to a CS research group with PhD candidates and people doing dual-degree in Econ/CS & Econ/Math so I think there can be a good fit with lots of real-world experimental opportunity.

Wow! Many thanks for this. Looks like lots to choose from.


He's doing 5-year CS program which a combination of 3 years bachelor general CS degree + 2 years graduate CS specialized topic programme.

A bit of advice: Bitcoin and PoW crypto-currencies like it are unique because to understand them you can't just understand crypto, you also need to understand a bit of economics, game theory, and even politics. Equally, it's very common that ideas that seem technically sound fall flat when analyzed from an economic/social/political point of view; it's easy to make ideas that only work if all the participants are "honest" in some way, which just isn't good enough here.

The key problem is that in a PoW consensus system the defenders only have a linear advantage over the attackers, where in basically all other cryptography they have an exponential advantage. It's why the latter can say things like:

- https://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

while with Bitcoin we're worried that economics incentives won't be enough to ward off attacks.

I guess you mean he's studying CS at the undergraduate level.

Here is a quick brain dump of some interesting CS-y bitcoin stuff:

There are a bunch of network-simulation problems that might be fun to do. For example Aviv Zohar's paper http://eprint.iacr.org/2013/881 still has not been simulated to the best of my knowledge. It would also be neat to study the network consequences of selfish mining, block size changes, propagation of invalid blocks or transactions, etc. These are not really open problems, just things that people have not studied in great depth, so your friend would have some support here.

There is also some cool data structure work to do with blockchain pruning and utxo management. Peter Todd has an idea for using Merkle Mountain Ranges to store the utxo set, then requiring transactions to provide cryptographic proof of the MMR updates. This has a practical problem in that the proofs are huge compared to ordinary transactions, but it's still something neat to study. I'm sure others will jump in with data structures problems; this is not really my thing.

Then on the crypto side there are much cooler problems, but perhaps not so accessible on the undergraduate level. For some bitcoin side projects it would be neat to have ed25519 blind signatures. Learning the background then implementing this is probably roughly the right amount of work for an undergrad honours thesis. Check out ed25519 signatures and Matt Green's note on blind signatures. You might also want to track down David Chaum's untraceable cash paper for a cool application of blind signatures. (If it's behind a paywall I can get it for you.) In the same category would be one-way aggregatable signatures, which are cool in their own right. According to that paper, which I still haven't read, they have some sort of applicability to bitcoin.

There are tons of neat proposals for using bitcoin's secure global timestamping mechanism to solve cryptographic problems. Tons of these are posted here (though I don't have any links offhand). Another exciting example is secure multiparty computation in Bitcoin.

Another cool idea would be to use pairing-based crypto to implement Identity-Based encryption. That paper has a quick overview of pairing-based crypto, which essentially means you have a magic bilinear mapping between groups. This is "moon math" in the sense that the security assumptions are much less studied than, say, discrete log for elliptic curve groups. There are some neat applications for IBE, eg Adam Back's non-interactive forward secrecy scheme. If bilinear mappings are not weird or theoretical enough, there are extensions of this which give you multilinear mappings. (I haven't bumped into one, but gmaxwell says papers exist.) Pairing crypto uses bilinear maps, which can be used for a noninteractive 3-party shared secret, similarly to how EC-Diffie-Hellman gives you a 2-party shared secret -- an (n-1)-linear mapping would give you an n-party shared secret. Peter Todd had some use for such things recently, hence the interest in multilinear mappings.

Veering further into moon math, and probably also past the undergraduate level, there has been a lot of interest in the bitcoin community in efficiently verifiable zero-knowledge computations. In particular, a recent paper on SNARKs (succinct noninteractive arguments for knowledge) has drawn some excitement. Again there are practical problems with the computational time required, but not abhorrent. A more serious problem is that the security proof is in the CRS common reference string model. When a cryptosystem requires all parties to have access to a common reference string, in Real Life this reference string is generated by one party who has access to some secret key -- and with this key, forged proofs can be constructed. Imagine if bitcoin depended on SNARKs and nobody could prove that satoshi was not using (or did not have) such a key. Solving this efficiently is a big open problem. This is cool to investigate (and the linked paper has a -ton- of references) but probably even doing a book report on that paper would be beyond an undergraduate thesis.

A list of alt ideas (some of which I've mentioned above) is here: https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas . Your friend may also want to idle on #bitcoin-wizards and see what floats by.

I've got a friend studying Computer Science and looking for a research topic around bitcoin.
What are the hard-core CS challenges in the bitcoin tech space both in software and hardware?
Any links/pointers would be appreciated.