Surae 2018 Q3 updates:
I am joining my June and July progress reports for convenience.
The following is a description of my work for June 2018. I have been working on: 1. Ongoing work on the security of multi-signature schemes, the Knowledge-of-secret-key (KOSK) setting, rewind/replay attacks, and tree-based signing. This has included communication with community members and members of the cryptography community. The multi-signature MRL bulletin is still in prep (see below). . Ongoing work on consensus systems, selfish mining, cryptocurreny network dynamics, and population ecology-inspired network simulations. . Ongoing work on a formal proposal on selecting a fixed consensus ring size and how to go about selecting that ring size. 4. Developed a statistical test for Moneromooo. The test is based on hashrate to warn a node that the hashrate may have experienced a sharp discontinuity. I have a blog post (in preparation) planned working through the creation of such a test from a formal hypothesis testing perspective from mathematical statistics. . Volunteered on the ZCash Foundation Grant-Making Committee, helping guide the foundation in distributing $250,000 for projects related to "internet payment privacy infrastructure." 5. Assisted serhack and UkoeHB with their writing projects: Mastering Monero and Zero to Monero. 6. Held research meetings (see here, here, here, and here).
Here are some progress notes.
My time on multisignatures has been productive, but frustrating. I brought the multisignature paper mostly to it's current state (you can see it here), which is still "under construction." The knowledge of secret key (KOSK) setting has some problems with it unless it satisfies from strict formal requirements (which I'm looking into); abandoning the KOSK setting seems to expose us to a commit-and-reveal stage which might allow a certain sort of replay attack (an especially egregious problem in the case that a sloppy implementation leads to users exposing their private keys). I am communicating with some authors in the space to see if I can gain some clarity on proof details and attack routes. So, more research needs to be done, but we are rounding the corner here. The primary "works cited" include: 1. Bellare, Mihir, and Gregory Neven. "Multi-signatures in the plain public-key model and a general forking lemma." Proceedings of the 13th ACM conference on Computer and communications security. ACM, 2006. PDF link here 2. Maxwell, Gregory, et al. "Simple Schnorr Multi-Signatures with Applications to Bitcoin." (2018). PDF link here 3. Drijvers, Manu, et al. Okamoto Beats Schnorr: On the Provable Security of Multi-Signatures. IACR Cryptology ePrint Archive, Report 2018/417, 2018. Available at http://eprint. iacr. org/2018/417, 2018. PDF link here 4. Bellare, Mihir, and Oded Goldreich. "On defining proofs of knowledge." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992. PDF link here
Consensus systems. I have been working on network simulations (see here) and I have started looking into some other interesting approaches (see here). Additionally, I've been reading up on the following papers. I have no particular thoughts yet. This sort of reading is an ongoing sort of task that will always take time at MRL, so we can stay on top of new research in the area. . Team Rocket. "Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies", 2018. . Fruit chains (Pass, Rafael, and Elaine Shi. "Fruitchains: A fair blockchain." Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 2017.
Blockchains as an abstract object, selfish mining, and Ethereum as an economic predator: Call this a flight of fancy. I've made several updates to my PoissonGraphs project here, which simulates a network live for testing the dynamic properties of things like difficulty algorithms and consensus algorithms. Any change to our protocols would require looking at questions like "how stable is the algorithm?" and "how rapidly does the algorithm return to an operational equilibrium after a perturbation?" Some of these are difficult to analyse without just straight-up Monte Carlo simulations, which is what PoissonGraphs is meant to do. It's almost ready. It spits out a human-readable transcript that could be animated by an ambitious person. I am interested in eventually coupling two such networks together (like Bitcoin coexisting next to Ethereum) with an econonomic model of trade between the two simulating some central exchange authority.
In addition to that, I have a colleague (formerly at University of New Mexico, and soon to be at the University of Exeter) who is interested in writing a paper using population ecology inspired model of a smart contract system like Ethereum and a more usual system like Bitcoin, to model how a clever smart contract system like Ethereum could "prey" upon the hashrate of an innocent unsuspecting Bitcoin. Papers I'm reading that are loosely falling into this pile include the following. 7. Ritz, Fabian and Zugenmaier, Alf. "The Impact of Uncle Rewards on Selfish Mining in Ethereum." Arxiv. 2018. 8. Pass, Rafael, Lior Seeman, and Abhi Shelat. "Analysis of the blockchain protocol in asynchronous networks." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2017.
July was mostly taken up by multisignatures, which are freaking done! Well, ready for submission anyway.
My time on multisignatures came to an end: no more writing before submitting to a journal and receiving comments from reviewers. You can see the current incarnation here. We are currently considering different journal options.
A new sublinear ring signature scheme was submitted to MRL by Lai, Ronge, Schröder, Thyagarajan (all at FAU), Ruffing (at Blockstream) and Wang (at CUHK). Sarang started coding it in Python, and I've been working through his code with him looking for various indexing stuff, and generally learning about polynomial commitment schemes.
DLSAG: I started to review dual-output LSAG signatures for use as return addresses, written by Sarang, formalizing an idea by Pedro Moreno-Sanchez.
I want to once again express my gratitude to the Monero community. I am excited to meet all y'all at DefCon in 120 degree heat. I hope that my work so far at MRL has been pleasing to you guys, and I hope my work on multisignature can bring confidence to the community about the security of their funds.