Surae 2018 Q2 final update:
Greetings all,
The following is a description of my work for May; part of this month, I was on vacation. I worked more than 120 hours, including running three research lab meetings.
- Finished constructing MRL Roadmap for second half 2018/first half 2019. See here. 2.Ongoing work on adapting the Musig multi-signature scheme to our LSAG ring signature scheme. This included literature review on multisignatures, the Knowledge-of-secret-key (KOSK) setting, rewind/replay attacks, and tree-based signing. This also included investigating a recent problem with the Musig security proof. See below for more details.
- Ongoing work re: fee structures on bulletproofs. ArticMine is writing up a technical document on the matter.
- Ongoing general work on consensus systems, selfish mining, cryptocurreny network dynamics, simulations, and population ecology approaches to network hashrate modeling (see below).
- Ongoing work for a description of a zk-ledger-based sidechain for off-chain transactions.
- Finished developing a statistical test for Moneromooo based on block arrival rate to detect extreme changes in hash rate; a technical note is probably overkill on this one, so I'm considering writing up a blog post on this.
- Assisted Sarang in his investigation into dual-output ring signatures and the security of trigger heights (see here).
- Discussed temporally prunable transactions with needmoney90 and some general blockchain statistical modeling with IsthmusCrypto.
- Began studying the work being done on generative adversarial networks (see here).
- Began a search into some algebraic geometry concepts for constructing elliptic curves, including: Atkin, A. Oliver L., and François Morain. "Elliptic curves and primality proving." Mathematics of computation 61.203 (1993): 29-68. (See here).
- Assisted serhack and UkoeHB with their writing projects: Mastering Monero and Zero to Monero.
- Four research meetings were held in May, although I missed the second one (see here, here, here, and here).
Here are some progress notes.
Fee structures on bulletproofs can be summarized thusly: we are replacing block size with a "block weight" that is essentially a measure of how many transaction outputs, N, are included in a block. Why? Total time it takes to verify transactions is roughly proportional to aN, the space that transactions will take up are approximately bN + clog(N) for some a, b, and c. Total verification time is something like (a+b)N + clog(N). If we charge fees proportional to just N, then what happens? Well, we sort of ignore the log(N) term. For transactions with many many outputs, N is large, we are under-compensating miners by a factor of clog(N), so miners favor transactions with fewer outputs. This incentivizes efficient output management, but note that this is a rather weak incentivization: most transactions are 2-in, 2-out already, so this extra term is generally only worth considering for a very (very VERY) out-of-the-ordinary Monero transaction. Further optimizing incentivization structure gets down into finer details than we think are necessary.
My time on multisignatures in May was extremely frustrating. The knowledge-of-secret-key (KOSK) setting has been under interrogation and the Musig multi-signature scheme as originally published was demonstrated to have a problem with its security proof. Our current scheme uses Schnorr signature-based authentication in key generation and signing in order to emulate the KOSK setting to prevent rogue key attacks. The 2006 Bellare and Neven paper elaborates on this. Schemes that attempt to abandon the KOSK setting tend to do so with a commit-and-reveal stage, and our original scheme used both signature authentication to emulate the KOSK setting and a commit-and-reveal stage. I began looking at a version of the Musig scheme without signature authentication, outside of the KOSK setting, with a commit-and-reveal stage. I brought the multisignature paper mostly to it's current state (you can see it here), although this link includes changes from June. This paper is still in preparation. My primary "works cited" from this time include:
- 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
- Maxwell, Gregory, et al. "Simple Schnorr Multi-Signatures with Applications to Bitcoin." (2018). PDF link here
- 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
I want to once again express my gratitude to the Monero community. This is THE ONLY community that is totally funding independent research into cryptocurrencies and privacy technology with no real strings attached. Every day I wake up thinking how I need to make this community proud, and my primary motivation to get out of bed in the morning is to make Monero. Just. A. Little. Better. I hope that my work so far at MRL has been pleasing to you guys. I hope everyone hangs tight for multisig: this scheme is going through fire and flame. Good for character.