Surae 2018 Q1 final update:

Greetings all,

My update for the work month of December was posted in January (see below), my January update and my February updates were both posted in March (see below), and my update for March is being posted at the end of June. I was going back through my records and I realized I never filed this update, for some reason. I believe maybe I was holding off until after the road map was completed? Perhaps. Anyway, the road map can be seen here, and this was, in fact, completed during the work month of March. I also did the following:

1. Ongoing work on applying a variation of the Musig multi-signature scheme to our LSAG ring signature scheme. This included communication with community members and members of the cryptography community, and it included many changes and reductions to our multisignature MRL bulletin (in prep).
2. Ongoing work on churn, EAE attacks, and financial privacy for a future MRL bulletin (in prep). At the time this included research on the monerov airdrop issues.
3. Ongoing work on a future MRL bulletin on the trade-offs between blockchain efficiency and financial privacy, how we have tried to solve the problem, how zcash tries to solve the problem, and how masternode-style set-ups try to solve the problem. This includes the discussion on "why sublinear ring signatures won't be implemented soon without dramatic improvements to verification times."
4. First discussed with Moneromooo a statistical test based on block arrival rate to detect extreme changes in hashrate.
5. Helped Sarang and the community with the discussion on bulletproof audit choices, funding, etc.
6. Assisted koe/UkoeHB in his editing of Zero to Monero.
7. Worked on the Cartesian Signature paper (see here).
8. Learned about and discussed Matthew Green's "How to Mix a Crowd" protocol for describing large anonymity sets efficiently.
9. Held 4 research meetings (see minutes here, here, here, and here).
10. Did background reading and research in the following papers (not a complete list):
    • Narula, Neha, Willy Vasquez, and Madars Virza. "zkLedger: Privacy-Preserving Auditing for Distributed Ledgers." 15th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 18) . USENIX} Association, 2018. See here. Research into this as a possible auditable solution to second layer Monero transactions under very specific use-cases.
    • Maxwell, Gregory, et al. "Simple Schnorr Multi-Signatures with Applications to Bitcoin." (2018). See here.
    • Kiayias, Aggelos, Andrew Miller, and Dionysis Zindros. "Non-interactive proofs of proof-of-work." (2017). See here. This is part of the ongoing second-layer discussion.

Much of my work can be elaborated upon if folks have questions about what my month of March was like in more detail; if they want progress notes, I recommend that folks check my posting for May 2018 here and my upcoming post for June.

I want everyone to know I love them, and that I'm again incredibly grateful for the contributions the community has made towards MRL. This has made a bunch of really cool work possible, and I hope that everyone is happy with the direction we are moving!

I'll be happy to help fund the MRL team (Sarang & Surae) again.

+100

Donated.

Howdy, everyone! This is the last delayed update I plan on making (next update should be on the 2nd of March). This update spans early January to the first week of February. I'll just jump right in:

This month, you sent me all over the world to represent Monero. You, as a community, kick complete and total ass. Thanks to the generous donations of Monero community members, I was able to attend the RealWorldCrypto conference in Zurich with fluffypony and friends, and the BPASE18 conference at Stanford with Sarang (and also fluffypony and friends). Together, these ate up a huge portion of my time for January, but attending these conferences was extremely valuable. I met with several members of the international Monero and cryptocurrency community, hardware wallet developers, researchers and developers... these trips were fantastic. I learned a lot about the game theoretic implications of smart contracts, various flavors of selfish mining and block-withholding attacks, consensus mechanisms, hardware sidechannel attacks, and large scale key management systems.

Let me tell you how cool it is to be waiting for Buenz' talk on bulletproofs, sitting next to andytoshi coding up bulletproofs, while gmaxwell is across the room realizing SHA-256 can be bulletproofed... when andytoshi is simultaneously realizing how to implement (yet another) optimization of bulletproofs. Moments like that get me all philosophical. Funny story: Pietr Wuille and I both found ourselves in the same boat, in Zurich without tickets to attend RWC. Thanks to the very generous Zooko Wilcox, I was able to attend the conference nevertheless. I still have his nametag with his name scratched out and "Monero Research Lab" written in childish crayon underneath it. I don't know how Wuille got in, come to think of it...

Back to business.

MRL Announcements: We are continuing with our weekly research meetings on Mondays at 17:00 UTC until someone starts to complain loudly about it.

Summary of Work: This month saw a lot of travel, so my actionable work was a little less varied this month. In the remainder of January and the start of February, I primarily have spent my time on:

• Multisig: I was concerned for awhile that our multisig scheme allowed for key cancellation attacks. Luigi has since proven me wrong (we have an authentication phase that cannot be passed by someone attempting a key cancellation attack). As such, multisig is back to "almost done" status. I spent a lot of time looking into the key aggregation set-up from the Musig paper, which elegantly handles key cancellation attacks. As a consequence, the multisig paper will be a little bit more well-rounded. This is one of the reasons I've put off posting this statement of work, I was hoping to get it completed and available for the community to read. Next update will be at the end of this month, and I anticipate a completed multisig paper for everyone to read through by that point.

• SPECTRE and Blockchain simulations: Since Sarang and I are constantly looking into consensus mechanisms like SPECTRE and PHANTOM, and I have been interested in difficulty for a long time, I've coded a sandbox simulation of a cryptocurrency network. Nodes arrive and leave in two independent Poisson processes, blocks are discovered at local nodes according to an independent Poisson process with intensities dependent upon difficulty, and blocks are deterministically transmitted accross the network. This is available on my github here although there are some issues with the code. My code implementing constant-time SPECTRE will eventually be used within these simulations.

• A new cryptographic scheme: I have some details written down on a new implementation of proxy ring signatures, under the random oracle model and discrete log assumption, and without bilinear pairings. The application of this scheme in cryptocurrencies is not totally clear to me (there are repudiability issues and issues with re-use of signatures), but I am not aware of any other proxy ring signature schemes without bilinear pairings, so I think it is worthwhile to describe this scheme and submit it for peer review.

• Reading: I am reading a lot on merge-mined sidechains and security models, lightning network, arithmetic circuits, and decentralized asset issuance. In fact, the latter is what led me to my proxy ring signature scheme. I am particularly interested in learning all I can about AC circuits and satisfiability. It seems like the next decade is going to use them a lot.

• Churn and EABE: I know, what is this, 2017? Someone recently reached out to me about a possible attack that, upon further consideration, appeared to be an EABE attack. After a back and forth with this concerned party, we discussed some alternatives to churn. Some ideas are being kicked around still. In the meantime, I want to remind the community: the sender-ambiguity property of Monero is improved in chains of transactions, so if you are wild about your personal privacy, we recommend that you construct one or more self-to-self transactions before spending Monero.

• Writing the "Q1" Research Roadmap: This has been briefly delayed. We will be posting this as soon as possible; the delay is partly my fault, and partly due to the fact that this document has some more comprehensive implications for 2018.

In addition to this, I've been having discussions with Sarang about educational outreach. News on this soon! Seriously, some cool stuff is happening behind the scenes here and we hope to make an announcement about it soon.

Donated!

Happy Thanksgiving!! One of the many things I am thankful for is the excellent work being done at the MRL

Donation sent :)

donated

Hello again, everyone. Thank you all for your patience in my delayed end-of-2017 update for MRL: my family and I had some emergency health issues (so December was less productive than I had hoped) and then I had to bounce out to Zurich for a week to go to the Real World Crypto conference with Fluffypony and friends (so I was again delayed in January).

MRL Announcements We are still having weekly Monday meetings at 17:00 UTC. These are one-part research meetings, where we update the community on our work, and one-part "office hours" where we answer questions, help new people in Monero, etc. I've missed the past several meetings (see my excuses above) which I feel a bit terrible about. I am happy to entertain format suggestions regarding these meetings. They can always be improved, and sometimes I feel like I'm just describing all my recent shower thoughts to a mostly empty room.

POW Difficulty Replacement Contest: After discussing with several community members, we are putting this on hold for a few months. I still think this is a good idea, but I believe we have higher priorities right now. Right now I am shooting for such a contest to be funded by 1st June 2018, for submissions to be accepted in July, August, and Septebmer 2018, and for a winner to be announced (or all submissions announced as losers lulz) by 1st December 2018. My initial plan is to match up 10% of donations up to around $2000-4000 USD (worth of Monero) so that the prize could be quite substantial. If all submissions are losers, we can either run a second round of the contest, or send the funds to the monero general fund, or donate it all to the Pineapple fund or something. However, given how things seem to be going, maybe we should be expecting to begin in September or something like that.

WTF Happened in the past 45-ish days?: Rundown for December and January.

Multisig: Because of this paper, I've decided to just start tripling my expected time-to-completion for everything. Because apparently I am not super great at estimating time of completion. This took up the majority of my time becuase I constantly felt "almost done," so I didn't want to work on anything else.

The vast majority of January I spent working on the multisig paper, correcting mistakes, going through code review. I believe I spent around 120 or 135 hours working on this in December and January together. The current version can be seen here... there are two major remaining components for this paper: first, the attack section of the paper has been temporarily commented out, and second, the code review needs to be re-reviewed (all explanations of the code need to be fleshed out and triple checked). I expect each of these (the attack section and the code appendix) to take between 25 and 30 hours of work, totalling 50 to 60 hours before completion of the multisig paper (translation: I really think I'll be done with this before the end of the week, but I'm afraid it will take the rest of the month).

RTRS RingCT, column linkability, amortization: Still chatting with soon-to-be-Dr. Ruffing about these. Expect more information about this by the end of January.

Bulletproofs: We are currently discussing how to go about auditing/vetting bulletproofs. Sarang and I both agree that the math looks good, Sarang and Moneromooo both believe the code is rather tight, and we have had some optimizations suggested by various folks. As I mentioned on Reddit just the other day, we are sort of faced with a dilemma here: either we implement bulletproofs for the Spring hard fork or not, and each decision has a cost. The cost of not implementing bulletproofs will, over six months, amount to around six hours of additional download+sync time for new nodes. This cost is in adoption rate, and is certain to occur. On the other hand, the cost of implementing bulletproofs too soon, is Monero's double spend protection, and is not certain to occur. Since one of these is catastrophic but may not occur, and the other is kinda terrible but is certain to occur, we have a tradeoff to consider here. We are being cautious. Expect a statement from us about this in the coming days.

Monero Standards: No progress has yet been made on these, although much of the documentation in the multisig paper will make it into the RingCT component of the Monero Standards, so there is a nice overlap there.

Remainder of January and leading into February: I am attending BPASE18 with Sarang, Fluffypony, and all you other crazy bastards. In addition to this, I am merely finishing the multisig paper by the end of January. For those of you keeping track of hours, I plan on working 50 hour weeks for the remainder of January and for all of February so that my delayed payment for December does not bleed into the end of the "quarter."

Any time I have leftover in January above and beyond multisig will go into one of the following: 1) the ZK literature review by Jeffrey Quesnelle (author of the recent Zcash linkability paper), 2) working on my SPECTRE code (the blockchain concensus algorithm, not the recent exploit), or 3) network simulations for independent verification of the difficulty assessment computations of zavvy12 from here (if you are curious, I have some not-yet-functional code gluing Poisson processes together here).

What about the rest of the year?:

First Quarter Roadmap: This is being delayed until the end of January if not a bit longer. This is partly becuase this first quarter roadmap is really an "2018 whole-year roadmap," and partly because all of the delays I have personally recently experienced. In addition to this, after speaking with fluffypony in Zurich, I am going to look into:

Fee structures: Using time series analysis, I believe it will be a fairly straightforward task to develop a long-term plan for our fee structures based on empirical connections between fees and network activity. These connections are, of course, correlative not causative and, moreover, would be computed assuming absence of attacks. However, this would provide us some sort of long-term empirical plan for our fee structures (compared, for example, to eyeballing/arbitrarily setting base fees each hard fork). This would provide us an easy target to point at when we hear fee complaints in the future... a statement like "our fee model disagrees with you, so unless you have a better forecasting model than ours, or a specific attack model in mind, your criticism is empirically unjustifiable" would be absolutely invaluable against feeFUD.

Side note on this: Anyone willing to get me as much historical Monero network and pricing data as possible in this regard will be doing me a huge favor in saving me time. I can analyze data quickly, I can curate a data set slowly. Due to this, I do not plan on spending any of my time actually gathering any of this data before February: if someone hands me a data set, I will analyze it happily. When I say "as much data as possible," I'm not kidding around. Average number of transactions per block, average fee paid per transaction, average kb per transaction, number of inputs per transaction, number of outputs per transaction, average time between blocks, USD/XMR and EUR/XMR and CNY/XMR and BTC/XMR exchange rates and exchange volumes at the time of each block for many exchanges... these are all obvious, but even silly stuff like "number of cryptocurrencies listed on each exchange at each block time" is nontrivially helpful information.

Educational outreach: I have something semi-secret brewing that I hope can be included in my end-of-Februrary announcement. It's probably a badly kept secret (many many folks in Zurich have given me their thoughts), but putting it in writing here seems to be perhaps unwise until I speak with a few more folks about how to handle all of it. My initial plans for Sarang were to organize a 2018 summer school at some willing university, but it appears that was too ambitious (we are shooting for summer 2019 now for this), so we have pivoted a little bit to this new idea... anyway, details will be forthcoming over the coming weeks.

THANK YOU ALL. This is the best opportunity anyone like me could possibly hope for. I am pretty sure Sarang feels the same way. The Monero community has so far proved to be extremely generous. I really do my best to avoid concluding that a decision was good just because the outcome was good, you know? But kicking the traditional economy to the curb in favor of this opportunity has been absolutely the best outcome of my life so far, and I fear I couldn't possibly explain to everyone, even face to face, how much all of this means to me.

At the risk of mimicking the first season of Silicon Valley... thanks for giving me the opportunity to make the world a better place.

donated

I want to thank everyone who donated, and anyone who even CONSIDERED donating! This is, again, a real honor to be working on this project for this community, and to have the support of the members. I'll be posting my end of November (2017!) update soon.

testing testing

Surae's End of February Report!

Howdy everyone! Another month gone. More results. Some news. This report was late because I had to speak to some lawyer types about our surprise announcement...

Research Stuff

Multisig RingCT: In the past month, the multisig paper has undergone a drastic revision read here, main.tex for clarity purposes. As of last Monday's research meeting, I thought the final big changes would take about a day, but they took about a week and a half. The result is above: a more compact paper with a moderately more compact presentation. Some details in some proofs still need to be fleshed out, references and citations need to be verified, the appendix describing the C++ code needs to be modified heavily, and a few more decisions need to be made before submission. Excluding the appendix describing the C++ code, I am hoping that some community members start reading through the current proofs looking for gaps, incomplete parts, logical problems, etc. The primary body of the thing is down to around 14 pages or so. In total, this was around 75% of my month.

Bulletproof Audits: We have made available here the statements of work from the various audit groups we've been discussing at research meetings, bulletproof meetings, and developer meetings, and we have started our discussion on BP audits on the FFS here. Please drop by and give us your thoughts. In particular, there have been rumblings that perhaps we could pay for an independent formal audit for the multisig code to go with my review. I support this, FWIW.

Where my sublinear ring sigs at? I am writing up a brief research note with Sarang. The idea is this: (i) small anonymity sets are worse than large anonymity sets, (ii) authentication still requires touching all keys in the anonymity set at least once, leading to linear verification times, and (iii) improving the space-efficiency of a blockchain therefore interacts with this linear verification time in a way that produces a space-time trade-off, leading to (iv) a trade-off between traceability and the space-time efficiency of the blockchain, (v) several ways that several different currencies have handled this trade-off, and (vi) implications from cost of running an untraceable cryptocurrency network at scale on this time-space trade-off. Our interests are now turning toward bulletproofs: in implementing bulletproofs, we learned many optimizations for elliptic curve arithmetic that will make our current ring signature schemes faster, but also since SHA-256 is bulletproof-compatible, we are idly toying with the idea of bulletproofing the SHA-256 versions of, say, LSAG or MLSAG signatures.

Sublinear TLDR: Monero is using ring signatures that are practically optimal in the sense that every other scheme we've looked at has either been too big or too slow. So we are trying to make elliptic curve arithmetic faster and trying the black magic of bulletproofs.

Monero Standards: I have an ASCII adaptation and compression of the multisig paper for ready for the Standards. We are starting to compile everything together for a deep theoretical documentation of Monero. That brings me to....

Mostly Complete Description of RingCT: A Monero contributor Kurt Alonso at Universitat Autonoma de Barcelona has written a rather comprehensive report on the crypto underlying Monero. His report can be found here. I am trying to decide if I want to switch all my notation for the multisig paper around to be consistent with the notation in this paper. Kurt's contribution is a valuable resource to the Monero community, and we thank him! I'll be spending a day or two looking through this.

Blockchain compression: Matthew Green of John Hopkins contacted me about a paper he and his student Alishah Chator are writing here. They describe a recoverable sampling scheme, RSS, which can efficiently describe how to retrieve outputs for use in verifying a signature. These RSS approaches scale with the number of outputs, and the result is extreme reduction in the space complexity required to describe a subset of a ledger for a given transaction. Currently, this does not provide us much gain, but as Monero scales upward, techniques such as this will become really easy wins. So we put this in the category of "futurizing Monero," or rather: we shall describe methods such as these in Monero Standards, each of which will have sections describing long-term improvements to our protocol.

Bulletproofs in general: Sarang recently made available a brief technical note on the Monero-specific implementation of BP range proofs... and then within about a day of being completed, Blockstream came out with an amended version of the BP paper that included all of our implementation variations, making this publication somewhat redundant. Check out where a brief technical note goes to die. This is how research goes, unfortunately: about six months before my MS thesis was completed, for example, another grad student elsewhere did exactly the same thesis and I had to start over from scratch.

Plans: Before the end of the month, the next MRL roadmap, which are sub-quarterly apparently, will be announced. At this point, we have enough options on the table to start laying out a vision of what future versions of Monero will probably look like (primarily, we have a few options on the table for better anonymity, and we need to start discussing the practicality of implementing these various options).

Announcement? A portion of my month was spent speaking with lawyers about incorporating an educational non-profit. How would you feel about funding a few elementary school teacher salaries in South Africa or Chile for a year or two? What about providing a handful of one-year no-strings free-ride scholarships to some qualified undergraduates at a university? How would you feel about providing a research grant to someone who figures out an environmentally-friendly version of proof-of-work? These things are all similar in three ways: each are in pursuit of improved educational and research-based outreach, all of these are purely philanthropic, and none of these are reasonable to fund with the FFS on a per-project basis.

This morning, I finished filing articles of incorporation for an educational non-profit Multidisciplinary Academic Grants in Cryptocurrencies (MAGIC) with the Secretary of State of Colorado. We would like Monero to be an active player in improving the educational environment across the world. We want the Monero community to help build a pipeline between education and workers capable of contributing to cryptocurrencies and related industries, providing scholarships to students in the US, providing research grants to principal investigators looking into research areas adjacent to cryptocurrencies, and providing infrastructure grants to disadvantaged schools across the world. An additional convenient component of registering as a non-profit is this: now we have a legal vehicle through which we can fund Monero conferences.

How will it be funded? To start, I am going to match up to 5% of donations, up to 50 XMR, in a soon-to-be posted FFS. Any funding we get above will go directly to the non-profit. Hopefully we get enough money to do a lot of cool stuff the first year plus have XMR carry over to the following year. We will also be soliciting funds from donors in more traditional ways in future years.

Who will run it? Sarang and I will be running MAGIC. We have a partner at Clemson University and a partner in South Africa. My wife, who was also in higher education for nearly a decade, will be helping me run it as a board member. None of the board members will be paid for their work as board members.

Why not call it Monero Academic Grants in Cryptocurrency? For Monero to be in the title, The Monero Project has a requirement that the organization must be a work-group at The Monero Project, which is an open-source software project. Open-source software projects cannot be granted non-profit status in the US. So we cannot be an official work group at The Monero Project without losing tax exemption status, and we cannot use the Monero name without being a work group at the Monero Project.

Why should we fund this? Well, if the feel-good warm-fuzzy feeling of helping folks go to university to study cryptocurrency, or building libraries for disadvantaged third graders in ZA, isn't enough for you, then you may be a bit of a nihilist. But even nihilists care about their bottom line, and I hope that everyone can see what sort of good this can do for Monero's image. Not to mention, programs like this help bring a new generation of students into cryptocurrencies in general and Monero in particular!

Thanks everyone! I want to, once again, thank the Monero community. I have been granted (heh) the most amazing opportunity to work on this project, and I am incredibly thankful. I hope that all of you appreciate the work that Sarang and I have put into Monero, and I hope that you guys think your funds are being well-spent.

Surae's End of March Report.

Hi everyone! Surae here, describing my work from March 2018. Thanks for your patience in the delay.

Papers in preparation

Multisig RingCT: If you recall, in February, multisig had undergone a big revision, getting it closer to the point of submission for publication. After seeking feedback from several folks, the paper is undergoing yet more revisions, making this creation much more compact and clearly written. So far, we've identified a few non-security-critical issues with our description and with the code implementation, and we have identified a few conceptual ways to make the presentation more clear. Some simplifications suggested in the musig paper, are going to be suggested. The month of March was filled with discussions with several contributors about these issues.

Analyzing churn: Sarang and I are jointly working on a churn paper. The contents may end up being too sensitive for this report to be made available outside of the core team. This is very high priority and very high urgency; we wish to make a statement on best practices as soon as possible.

Technical note on network efficiency: MRL is currently writing a technical note on the general efficiency requirements for a PoW-based cryptocurrency to scale. Specifically, this paper will explore sublinear one-time ring signatures for use in a cryptocurrency as used in Monero, bounds on the speed and efficiency of these schemes required for either reasonable low-level use like what we see today or high volume use like what we might see in the coming years. This has been lowered in priority until multisig is out the door.

Difficulty adjustment algorithm: I have a draft of a document that has some handwritten notes of mine from a few weeks ago I just got typed up. Essentially, this is going to boil down to "estimating hashrate as a statistical inference problem" paper. I'll be using my (currently working?) Poisson-process Graph cryptocurrency network simulator to show how various statistical techniques perform at estimating hashrate. This is the same set of simulations we'll be using to investigate SPECTRE, the consensus paper. I didn't want my handwritten notes on this to stay un-recorded for much longer (high urgency but low priority)

Monero Standards: I no longer have an ASCII adaptation and compression of the multisig paper for ready for the Standards, because we are undergoing some changes to that paper. Stay tuned. This is high priority but not high urgency.

A new signature scheme: I think I developed a novel signature scheme based on a structure that I know for certain exists... I "just" haven't come up with a way to implement with cryptographic levels of security. But I'm going to seek publication on this in a peer reviewed journal soon, in case someone else comes up with an implementation. See here. This is very low priority.

What happened to the roadmap? Sarang kicked a draft of the roadmap to me more than a month ago and I am working on it presently, but multisig and analyzing churn are two high priority items.

Educational outreach

MAGIC is an educational non-profit dedicated to improving the pipeline between the education world and the cryptocurrency world and to improving education worldwide in general. We'll be providing scholarships to help students attend university in disciplines related to cryptocurrencies, providing research grants to help graduate students and principal investigators look into questions related to e-cash and cryptocurrencies, hosting educational events like research conferences and educational workshops, and providing general infrastructure grants to under-privileged schools in the US and abroad. We don't really know exactly what sort of neighborhood of budget we'll be aiming for, and the donations from the community will entirely determine how effective this organization will be.

I've spent a portion of my time this month organizing the upcoming "FIRST BOARD MEETING" of the MAGIC board of directors in Denver on April 27. We'll be outlining our expectations from this non-profit and making our statements about our mission shortly after. We've gotten verbal confirmation from Globee about setting up an account for receiving donations. So far, the board members include myself, my wife, Sarang, rehrar, sgp, the operations manager from Globee; we may also have a board member from Clemson University join us, but we are holding off on making formal announcements.

Conference organization

The first MAGIC board meeting is at one of a handful of locations we are thinking of using for the first Monero conference. While some folks are in town for that, we may go scope out some locations and post some photos and estimates.

Thanks everyone! Y'all have enabled the most amazing opportunity to work on this project, and I am very thankful. I hope everyone is satisfied with the work that Sarang and I have put into Monero, and I hope that you guys think your funds are being well-spent.