October 2018 - Surae's End of Month Upate
Howdy! This is the second of my three "Q2" end-of-month updates. See my next proposal for funding here to see an explanation for how quarters got all messed up and how we are correcting it for our next pay period.
Subaddress paper completed (see here). Sarang and I had an in-person meeting at the beginning of this month to get that finished.
Meetings. Although we accidentally missed one, we are holding weekly meetings on Mondays at 17:00 UTC on freenode. We are trying to alternate between research meetings and "office hours" where folks can come in and ask any sorts of questions they like. Depending on the success of Monero Coffee Chats, we may abandon the idea of office hours and just make these meetings about research only.
PRNG made less weird. We have had ongoing conversations on freenode about the PRNG used in Monero. Certain choices inherited from the original BitMonero fork remain which are ostensibly innocent, but not standard and somewhat weird. In particular, our pseudo-random number generator (PRNG) was... odd. This was originally pointed out by Matthew Green, an we want to thank him for bringing it to our attention. We have made some changes.
I am beginning an e-mail chain with the chair of a math and CS department at a local university (details to come in the next week hopefully, depending on our conversation) about a 3-4 week Monero Summer School Program for 2018. This would be for talented undergraduates to spend a few weeks learning about cryptocurrencies and possibly build one of their own. I strongly feel that a program like this has the potential to literally pay for itself, but it would require a first-year bootstrap. I am looking into the possibilities of grants to match funding, and so on. The first summer of this will necessarily be a small program, I think, as a test bed, but we can scale this up from year to year by inviting out experts to give lectures, etc, creating a pipeline of students into the cryptocurrency industry.
Works in progress
Multisig paper Soon(TM)
Currently in the midst of code review. This project has experienced consistent incremental progress, but none of it is flashy. About one third of this month I spent modifying the complete description of the multisig scheme to take into account multiple outputs, corrected errors in my paper, and beginning the code review. I made some recommendations to change how keys are computed. Through helpful discussions with moneromooo and luigi, we actually identified an unstated assumption in the paper that has ramifications for the security model: the public multisig keys need to be communicated over a secure side channel before beginning to avoid MITM to determine whether a key is a shared multisig key or not. Without this assumption, an eavesdropper has a non-negligible advantage in guessing whether a given pubkey is a multisig key or not.
All that really remains for multisig is to go through the code with a fine-toothed comb. Since I've been really bad at predicting a deadline on this one, I'm going to hold my tongue here, but I don't see any reason to expect a change from consistent incremental progress. We intend to complete this well before the next hard fork.
About one third of this month, I studied how the Spectre algorithm works, wrote up some python code that implements a naive caching that brings the algorithm in the Spectre paper from cubic to quadratic time (read: makes the Spectre algorithm go a bit faster). We were first alerted to the properties of Spectre by Zooko of ZCash, coincidentally. I verified with one of the authors of the Spectre paper how to bring the algorithm into constant-time (with a trade-off of a possible route of CPU-wasting attack). After we get that implemented, the next step is running a simulation of a Monero network as a spatio-temporal Poisson process (block arrival) on a graph (nodes on the network with a certain propagation speed) to compare the Spectre algorithm with the Nakamoto consensus in the presence of attack models like selfish mining. The basic idea at this point is to stress-test something like Spectre to see whether switching would really do us any favors. This is not intended for the next hard fork.
This section should be more properly entitled the pro-network security brigade. Another third of this month I have spent studying "the ASIC problem." To be clear: Monero is currently still ASIC resistant, but rumor mills are always claiming ASICs are right around the corner. I am developing two documents about this.
First, a longer-term roadmap (which will be versioned and updated every few months) on how to handle appearances of ASICs if or when they appear. It takes time and lots of capital to tape out ASICs, whereas making modifications to our PoW algorithm takes an attention to detail and a hard fork. In this sense, we always have the advantage in the ASIC arms race.
Second, I am analyzing how economic incentives in PoW games work. Namely, the question of CPU vs. GPU vs. ASICs is very much a question of the commoditization of the mining hardware, block rewards, fee structures, network security, and decentralization. Decentralization is costly, but brings some benefits to network security. The common wisdom claims that commoditization brings decentralization, which brings network security. In reality, the relationships are highly context-dependent.
For example, for user anonymity reasons, we favor a flat per-kB transaction fee rather than dynamic transaction fees. Yet making such a change influences network security because in a fee-less currency, the network is vulnerable to spam and in a high-fee environment, there is improved economic incentive to mine. Making rational decisions here requires modeling: it is not difficult to construct a model of a similar situation in which network security (or rather blockchain integrity) and user anonymity are in a trade-off by way of dynamic fees.
Conversations at The Lab
Andytoshi swung by to start talking about atomic swaps and refund transactions in Monero, which has prompted me to start to lazily look into a certain key image problem and forward-secure key exchanges more generally. Also, silur has begun chatting with us about quantum-hard shuffles as PRNG choices.
Next month is the final month of my second pay period at MRL. We plan on bringing multisig to a safe conclusion as rapidly as is wise, make progress toward a decision on whether to move forward long-term with SPECTRE or something like it, and make progress on our aforementioned brigade against centralization (or at least: brigade against network insecurity?). Critically important is to complete multisig for implementation toward LN and atomic swaps, and to inform the community on the progress we have made on the roadmap for this quarter by the end of November. Any other progress made on any other progress in November is icing on the cake.
Thank you all!
I have to say, I'm absolutely stunned at the level of community support, and I'm delighted to have these opportunities. The idea of teaching a summer school to get excited kids into cryptocurrency and prepare them for actual jobs absolutely thrills me!