Promise to harass Sarang with that dollar and you got a deal
Funding for Surae at MRL Q2 2018
suraeNoether posted this 6 years ago
WHO My name is Brandon Goodell. I am Monero Research Lab’s first postdoctoral researcher into cryptocurrency. I have a Ph.D. in Mathematical Sciences from Clemson University, a M.Sc. in Mathematics from North Dakota State University, and a B.S. in Mathematics from Colorado State University. I taught as a graduate student for 9 years at the university level, and I have participated in the Monero community under the pseudonym Surae Noether since 2014.
WHAT I am requesting a continuation of funding for our next "quarter" of April and May. Our last quarter was four months, and this quarter will only be 2 months (getting MRL back on a usual fiscal quarter shape). This will conclude my first full time year at MRL for me! Note that we at MRL have not put out a quarterly research road map yet this year. For reasons related to Monero Core's recent change to PoW, we have been ... re-arranging our expectations for the upcoming year. Expect a "first research road map of 2018" before the end of May. In addition to this, I plan on keeping a "crypto paper" diary of journal papers I've read, what they are about, etc, which I will make publicly available so folks can track my progress in reading. I'm hoping Sarang is willing to contribute to this as well. I wish I had done this from the start.
WHY FUND IT: Monero Research Lab has thus far been in communication with researchers all over the cryptocurrency industry, cryptographers, computer scientists, and computer engineers. These communications have led us to testing (and rejecting) one sublinear ring signature scheme, testing (and accepting) the bulletproofed range proof scheme, implementing various elliptic curve speed-ups that will overall make Monero much faster, and implementing a cryptocurrency network simulator. In addition to this:
MRL has arranged for an audit of our Bulletproofs code (which got funded absurdly quickly). This is proceeding under Sarang's helpful guiding hand. I should amend this to say: bulletproofed range proofs. Because bulletproofs ... can do a lot. A lot, not just range proofs.
The multisig MRL Research Bulletin here is close to ready for submission to peer review. This is only the current version, which has not undergone the following changes: the body of "main.tex" will be merged with the extraneous sections from "thresh.tex" and the appendix on C++ code will be a standalone paper. Sarang and I are going over the proofs very carefully and will be put on arXiv in a few days here. We are splitting the description of the scheme and the C++ code review into two papers. The delay is on two fronts. First, due to our reading of some recent work published by the folks at Blockstream, we have been able to formalize several of our security definitions in different, more compact ways. Second, splitting the paper into two plus a moderate rewrite of the first section has allowed a significant reduction in length of the paper without sacrificing readability, which improves our odds of getting it published. In addition to this, there is yet another reduction of our scheme that may lead to a second publishable paper. So in total the multisig paper has blossomed into 3 documents: (i) describing threshold LSAG signatures and their use in RingCT as threshold MLSAGs, (ii) scoping out our C++ in comparison to threshold MLSAGs, and (iii) a paper describing a rather general threshold scheme.
There has recently been some work on difficulty (see for example here and here). We are currently constructing a sandbox simulation of cryptocurrency networks. The simulation can model any POW coin, using any difficulty computation regime, and any consensus algorithm. It evolves dynamically according to some underlying population model, and we can use this to simulate various attacks on consensus algorithms, difficulty computations, etc. You can see the current code here, but an update is coming soon.
I am working on a document detailing one way that an EAE attack can go down, and looking into mitigating methods. I am not making this document public yet.
I am working on a document detailing the time-space trade-off induced by transitioning to a sublinear ring signature scheme, and why such a transition isn't always a net gain. Again, this is not yet being made public. The idea is to map this measurable trade-off to a trade-off between security against linkability and speed/efficiency of the network. Anyone familiar with security should be well aware of the trade-off between speed and security, but this particular relationship is nicely quantifiable. Thing is: a lot of cryptography papers talk about the efficiency of their schemes but they only discuss signature computation time. In our application, signature verification time is our bottleneck. It would be nice to put explain how an ostensibly "efficient" scheme described in the literature can be wildly inefficient in our set-up. I've described this in my end-of-February write-up.
Monero Standards: Still in the phase of compiling descriptions. Expect movement on this by the end of May.
So, in total, we have 5 or 7 "documents" brewing, half of which we hope to be peer-reviewed. Expect at least one MRL Bulletin or MRL Research Note by the end of May. We are still being productive: We have some work on some theoretical fronts that may be interesting.
We are still working on the question of long-term ASIC resistance. A strong argument is to be made that asserting ASIC resistance is equivalent to willfully engaging in an inevitably losing arms race, but a strong argument is to be made that ASIC resistance is critical to egalitarian mining; we think we can use game theoretic analyses of incentives to suss out the difference.
We are also looking into adding a layer of oblivious transaction processing on top of the current Monero blockchain to allow for improved privacy, but this is rather new territory and is slow going. Depending on our results from the EAE analysis, this may elevate in priority.
These are longer-term projects. A brief update/result from my last funding round: Last funding round, I wanted to look into proofs of space and proofs of retrieval. Most schemes end up requiring too much time to verify, so these are (as of now) not useful replacements for proof of work, which is quickly verifiable in constant time. This coupled with the ability of an attacker to execute very cheap attacks without the sunk cost of mining hardware leads us back to the Nakamoto Proof of Work-based model.
HOW MUCH TOTAL: 63 XMR. In line with Sarang, I am asking for 9001$ USD/month. I am going to use 285 USD/XMR as my baseline exchange rate, which is a hair over the 30 day exponential moving average. Just like Sarang, this is in line with market rates for a Ph.D. scientist and mathematician (accounting for the tax implications of working outside a traditional employer), and represents my assessment of fair compensation. Similar to Sarang, once discussion about my request is over, I will use a thirty day simple average to determine the XMR amount. Sarang and I agree this is the most fair and transparent way to set the desired funding level due to price volatility.
LET'S DISCUSS We at MRL strongly value community input into the funding process, and welcome discussions regarding this proposal. I want to thank the community once again for their continued faith in me and Monero Research Lab. I wish everyone had a job they found as satisfying as this.
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.
Thanks everyone! I hope I can break the discrete logarithm hardness assumption for both fun and profit on behalf of MRL!
Surae's End of April 2018
MRL Announcements
Meetings. We are holding weekly meetings on Mondays at 17:00 UTC. Logs are to be posted on my github soon(tm).
Conferences, etc. The most valuable contribution I've made to the Monero community this month actually came from (1) reporting someone else's results after (2) flying across the planet to speak with a researcher face-to-face at a conference, all (3) on the Monero Community's dime, I may add. Every donor helped make this happen: a colleague of Tim Ruffing at Saarlang, Pedro Moreno-Sanchez, and his student Rodrigo brought to MRL's attention their model of dual-output key Monero transactions. These are optional transaction formats that allow for refund addresses, are backwards compatible, and soft-fork capable; we are working on the privacy implications, but this is the first step toward a lightning network for Monero. Flumo? Sarang's first draft of a technical note describing the advancement can be seen here. We seem to be drifting closer to Harry Potter spells with the names of these things... To be perfectly clear, one of my goals for the first year of my time at Monero included refund addresses! I am absolutely delighted and honored to report Pedro and Rodrigo's results to our community.
Work Update
Multisig. The majority of my work this month has been on multisig. I plan on submitting this for publication at the end of May. Multisig in this paper is a little different than the description in our implementation. There are two major development fronts here.
First, after much deliberation and consultation with Sarang and others outside of MRL, the superiority of the musig key aggregation technique over our simple sums verified with sginatures has become clear. This approach was published this past February and the technique is provably secure against key cancellation (rogue key) attacks, and requires only one round of communication for key aggregation. In addition to this, it was brought to MRL's attention a few purely technical problems with the construction of security proofs in settings where (i) signatures are used to prevent rogue key attacks and (ii) no certificate authority is responsible for handing out keys. You can read about musig here, or you can read about some of the pitfalsl of the knowledge-of-secret-key assumption here and here. We generally want to avoid all but the bare minimum number of assumptions for security purposes, so since musig does not depend on the KOSK assumption, we favor that approach to key aggregation.
Second, we are following a similar tactic as described in the musig paper to prove the security of our multisignature scheme. This is relevant because we are lifting a security result from a normal/usual setting up to a ring-signature setting. The proof does not carry over directly and suffers several of the same roadblocks that the musig paper faced. Our road blocks are non-negligibly more annoying in the ring setting than they were in the usual Schnorr setting; we must apply a general forking lemma three times instead of twice to account for the ring signatures in Monero, for example. I will post a link to the current version before Saturday evening, and I want to submit for publication before the end of the Month, if possible.
This is now a two-paper project: the "theoretical security paper" and "the practical code review paper," the latter of which will end up in the Monero Standards.
Algebraic Geometry and generating elliptic curves. I've recently started reading papers on how to construct elliptic curves of a prescribed order and preferably with a prescribed embedding number. The papers I'm reading begin with this one and marching forward in time citation by citation based on ostensible relevance to Monero.
Bulletproof auditing is proceeding. Ask Sarang about this one.
Monero Standards and the Zero To Monero publication here. Right now, we don't have a comprehensive list of how Monero works, all the various primitives and how they all fit together. A month or three ago, a few Monero contributors started working on Zero To Monero, a technical document that begins with cryptonote constructions and ends with our latest developments in ring confidential transactions. It's about 45-50 pages long and part of this month I have spent reading this document and making notes/suggestions before the authors publish it. This document is the first step toward the Monero Standards.
Want to hear a joke? We funded 4 months over xmas to get back onto the usual fiscal quarter and then bunged it all up by only getting funded for 2 months in the subsequent quarter, putting us back where we started.
Never confuse a mathematician for an arithmetician. Oy.
Community, education, outreach. We've had the first board meeting of Multidisciplinary Academic Grants in Cryptocurrencies, a non-profit independent of The Monero Project. Our goal is simple: close the loop between the cryptocurrency and education. Money is flowing into the cryptocurrency space thanks to a lot of educated people, but in the meantime undergraduates have the honor of graduating without any knowledge of next-generation security systems. Since this is an independent project, I don't plan on mentioning it very much during these updates, but MAGIC will be hosting a privacy-enhancing-technology conference in the summer of 2019 with an emphasis on financial privacy. Since the Monero Project in general and Monero Research Lab in particular will be involved with both organization and content, some overlap in these updates will be a little inevitable.
SPECTRE, Poisson-Graph Simulations, Cartesian Square Signatures. These are ongoing back-burners, and I have not made any changes to these recently.
Plans for next month? I'm not going to pretend to know yet. It could be flumo work, it could be elliptic curve group construction, it could be SPECTRE/PHANTOM or other consensus methods...
Thank you again! This is a dream life. I can't explain to you guys how absolutely bizarre it is to go from working for 10 years as an academic grunt to ... having an opinion that the market deems valuable. It's humbling and awesome and I'm doing my best to learn as much as possible. I'm hoping that my work ends up making Monero better.