One month update/statement of work! Seeking commentary and feedback from the community. I’ve spent most of my days in the past month in #monero-dev on freenode, leading to many productive conversations. I didn’t want to post my FFS for Sept-Nov until after I had updated the community. About 2 weeks ago, I posted the first MRL research roadmap. I’ll address those points more or less in order… after I first address a few things that will be making it onto the next MRL research roadmap. If you’ll notice, an enormous amount of my job is just to keep reading. That… probably won’t change much at least until September.
New stuff not on the last list
- I am in recruitment talks with PhD students who are graduating soon, looking for employment, and are interested in applying cryptography. We may have a post on the FFS in a few days from a recruit. These individuals are still on the job market in other areas, so even if these folks are fully funded, they may be offered a job somewhere else and turn down the position at Monero… in which case, if I understand the rules of the FFS appropriately, all the raised funds will go to the Monero general fund, I think. I need verification on that. Due to this strange set-up, we may want to discuss different strategies for hiring future researchers*.
- This could fall under the heading of “Future Proofing Monero” but it is a little shorter-term than that. After many conversations with members in #monero-dev and a few conversations with Sarang on my own time, it’s become clear that there is a prevalent “bad practice” in the Monero codebase inherited from CryptoNote: appending information to a message before hashing (one of many examples: one-time addresses are computed using H(rA || n)G + B, for example, where || denotes concatenation). This is considered a bad practice, using HMAC methods is considered superior and is the international standard for generating one-time codes (see here) Firstly, HMAC is provably secure. Secondly, there is at least one known attack against hashing concatenated messages while using weak hash functions. You may think to yourself “Ah, but we use Keccak, which is resistant against length extension attacks,” to which I respond “So? HMAC is provably secure and hashing concatenated messages is known to have at least one known attack vector.” For these reasons, I am recommending that every computation in the Monero codebase that uses hashed concatenated messages be updated to HMAC schemes. On the other hand, we could simply go through the code and identify every instance in the codebase in which we hash concatenated messages, consider the security requirements for that instance, and then determine whether it is necessary to switch to HMAC, but I don’t think that is more conservative in either the terms of time-to-implement or security.
Onto the actual MRLRRM.
Zero-Knowledge Lit Review: Today I uploaded the first draft of the literature review of zk-SNARKs written by Jeffrey Quesnelle. I have already provided comments back to him to gear the document more toward MRL goals, requests for clarification of material I’ve personally found confusing in the past in crypto, and so on; I expect that we will trade it back and forth a handful of more times. I am torn on whether to publish it as an MRL Research Bulletin, which is not formally peer-reviewed, or a peer-reviewed journal (I’m leaning toward that process). If there are any particular zk cryptoschemes that YOU know of that have been overlooked, let us know and we will do some more reading. The plan for this is still to shoot for publication (or at least submission) by early August.
RingCT: I have read the RingCT paper, mostly understand what is going on, and I am checking proofs and approaches thoroughly, looking for flaws that have not already been pointed out here. If anyone knows of more exploits, please let me know immediately. I am on the #monero-dev channel most of the time during the day, and I don’t want to miss anything. Still reading about Borromean ring sigs, range proofs, etc. I have not gotten far enough into this yet to put an expected time of completion on publication.
Other criticisms: I have not yet gotten to the two papers mentioned in the road map, but don’t worry too much. One of these papers makes some not-very-well-supported claims about how much of the blockchain that could be potentially revealed and somewhat disregards the one-time addresses, and one of these papers makes no assumptions about malicious users attempting to implicate ostensibly innocent users of criminal transactions. Both are serious papers, to be sure, but I am de-prioritizing them a little bit.
Threshold multisignatures: Currently reading. A lot. I have some concerns about how this was pushed into the testing phase already; normally it would be fine to push something like this even if it only comes with a brief, clearly written explanation of what is going on (think the cryptonote standards), not necessarily with security proofs or peer-reviewed vetting… but we don’t even really have a short standard written up, afaik, just an old blog post by Shen and a half-written MRL Research Bulletin.
Churning, mandatory mix-ins: I’ve thought a lot about this problem presented by knaccc of an exchange, Eve, determining the purchase habits of Alice at Bob’s Burgers. No solutions yet except churning, but this has probably been what I’ve spent the most time thinking about.
Signature sizes, RingCT: Add to this list “range proof sizes.” No progress to report yet beyond reading.
The Distributional Problem: I think game-theory can allow us to get around this without too much difficulty, but I have nothing formally composed yet. I’m thinking about the game of bombers and fighters: an attacker gets to send a squadron of planes against a defender. The defender can either target fighters, which are lightly shielded, or bombers, which are heavily shielded; the attacker can place bombs on either the fighters or the bombers. If the bombs get through, the attacker wins and gets a point, otherwise the defender wins and gets a point. The game is repeatedly played for a number of rounds. What strategy on the part of each player optimizes their chance of success? It turns out the solution is usually “the most random strategy,” which is to say, the least predictable one.
Oh, on point 9 from the MRL-R001: Hardness of blockchain analysis: I have some ideas on how to prove the equivalence of this problem with certain NP or NP-Hard problems, but I haven’t put a lot of formal energy into it except I have a document in which I formally state a model problem with similar properties. I’m convinced that the hardness is astronomical, but I have not written anything up.
I have made no progress on points 8 or 10-13 beyond some thought. These are all rather low priority right now anyhow. I will make an update like this at the end of next month as well here on the forums, and at the end of August I will release the first Monero newsletter as my “final update” for the 3-month period of June-August. My first order of business in September will be to revise and update the research road map and release MRL-R002.
*What I’m thinking about is one- or two-year “appointment” or “visiting researcher” positions, one or two at a time, where these researchers are paid out of a common research fund. Given the volatility of cryptocurrency and given how the FFS typically funds projects over rather short spans of time, this is an interesting challenge; I’m inclined to just let folks who are interested apply on their own through the FFS the way I did, but that is a barrier toward recruitment. I have more urgent things on my mind right now, but this has been percolating. I will probably make a recommendation about this by the end of my first 3-month pay period, and I will probably just throw my hands up and discard the idea by the end of the year.