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.

MRL Announcements

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.

Educational Outreach

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.

Spectre

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.

Anti-ASIC Brigade

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

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!

Surae's End of November (2017!) Update

Hello, everyone! Sarang posted his update a few days ago to give the community time to review his work before the end of the month. I was hoping to finish multisig off before the end of this month... so I held off on writing this update until then... but it looks like I'm somewhere between 2 days and a week behind on that estimate.

MRL Announcements

Meetings. We are holding weekly meetings on Mondays at 17:00 UTC. Logs are to be posted on my github soon(tm). Usually we alternate between "office hours" and "research meetings." At office hours, we want members of the community to come in and be able to ask questions, so we are considering opening up a relay to the freenode channel during office hours times, unless things get out of hand.

POW-Difficulty Replacement Contest. Some time in December, I am going to formalize an FFS "idea" to open up a multiple-round contest for possible replacements for our proof of work game. The first round would have a 3- or 6-month deadline. Personally, I would love it if this FFS could have an unbounded reward amount. If the community is extremely generous, we could easily whip up a large enough reward to spur lots and lots of interest across the world.

The Bitcoin POW game uses SHA256 to find nonces that produce hashes with sufficiently small digests according to the Bitcoin difficulty metric. Our current POW game uses CryptoNight to find nonces that produce hashes with sufficiently small digests according to the CryptoNote difficulty metric. The winner need not be proof of work. My current thoughts are roughly this:

All submissions will be public. Submissions that minimize incentives for centralized mining (or maximize disincentives) will be preferred over submissions that do not. Submissions that are elegant will be preferred over submissions that are not. Submissions that have provable claims about desirable properties will be preferred over submissions that do not (e.g. for either the Bitcoin or the Monero POW games, the necessary and sufficient network conditions for these games to produce blocks in a Poisson process have not been identified, to my understanding). Submissions that have a smaller environmental impact will be preferred over submissions that have a larger impact. And so on. I would like as many ideas as possible about a judging rubric for the first round. Especially if a large amount of money will be put up as a prize.

The details of the next round would be announced along with the winners of the first round. The reward funds should be released when a set of judges agree on a winner. MRL and Monero Core should each have representation on the panel of judges, and there ought to be at least one independent judge not directly associated with the Monero Project, like Peter Todd, Tim Ruffing, or someone along those lines. But, again, this is just an idea. If the community doesn't like it, we can drop it.

Here is a rundown for November

Multisig. Almost done. I know, I know, it's been forever. We, as a community, have recently come to see how important it is to carefully and formally ensure the correctness of our schemes before proceeding. Multisig is a delicate thing because a naively implemented multisig can reveal information about the participants.

I'm finishing vetting key creation today, finishing signatures tomorrow and the next day. Then I'm passing the result off to moneromooo and luigi to ensure that my description of their code is accurate up to their understanding. Then onto Sarang for final reviews before submission, hopefully by the end of the month. I have my life until Sunday evening blocked off to finish this. A copy of the document will be made available to the community ASAP (an older version is on my github), after more checking and writing is completed.

This whitepaper on multisig will be broken into two papers: one will be intended for peer review describing multi-ring signatures, and one will be a Monero Standard. More about that later...

RTRS RingCT column-linkability and amortization. You may say "what? I thought we were putting RTRS RingCT on the back burner?" Well, I'm still think ing about amortization of signatures. I'm thinking it will be possible (although perhaps not feasible) for miners to include amortized signatures upon finding new blocks. This would allow users to cite an amortized signature for fast verification, but has some possible drawbacks. But more exciting, I'm also chatting with Tim Ruffing, one of the authors on the RTRS RingCT papers: he thinks he has a solution to our "linkability by columns" problem with MLSAG and RingCT. Currently we try to avoid using more than one ring signature per recipient. This avoids linking distinct outputs based on bundling of these ring signatures. Ruffing believes RTRS RingCT can be tweaked to prove several commitments in a vector of commitments; this would allow a single RTRS RingCT to be computed and checked for each output being spent.

Once all the details are checked, I'll write up a document and make a copy of it available to the community. If it works, of course.

Consequences of bulletproofs. In my last end-of-month update I hinted at issues with an exponential space-time trade-off in RTRS RingCT. Due to the speed and space savings with bulletproofs, it may now be feasible to implement RTRS RingCT. With improved verification time savings with bulletproofs we can relax our requirements for verification times for signatures. This will allow the slightly longer verification times of RTRS RingCT to be counter-acted. Solving the problem "what ring sizes can we really get away with?" involves some modeling and solving some linear programming problems (linear programming, or linear optimization, is an anachronistically named area of applied mathematics involved with optimizing logistic problems... see here for more information).

Hence, we will be inserting bulletproofs into Monero with low friction, and then we will look into the logistics of moving to RTRS RingCT.

Monero Standards. Right now, we don't have a comprehensive list of how Monero works, all the various primitives and how they all fit together. Sarang and I have begun working on some Monero Standards that are similar to the original Cryptonote Standards (see here for more information). For each standard, from our hash function on upward, we will describe the standard, provide a justification for Monero's choices in those standards (complete with references), as well as a list of possible replacement standards. For example, our Monero RingCT Standard should describe the RingCT scheme described by shen, which is essentially a ring signature with linear combinations of signing keys + amount commitments. Under the "possible replacements" section, we would describe both the RTRS RingCT scheme and the doubly efficient zk-snark technology as two separate options.

These standards may take awhile to complete, and will be living documents as we change the protocol over the years. In the meantime, it will make it dramatically easier for future researchers to step into MRL and pick up where previous researchers have left off.

Hierarchical view keys. Exploiting the algebra we currently use for computing one-time keys, the sub-address scheme plays with view keys in a certain way, allowing a user to have one single view key for many wallets. Similarly, we may split a view key into several shares, where each subset of shares can be used to grant partial view access to the wallet. A receiver can request that a sender use a particular basepoint in their transaction key where different subsets of shares of the view key grant access to transactions with different basepoints in their transaction keys. None of these are protocol-level observations, they are wallet-level observations. Moreover, these require only that a receiver optionally specify a basepoint.

In other words: hierarchical view keys are a latent feature of our one-time address scheme that has not seen specific development yet. It's a rather low priority compared to the other projects under development; it grants users fine-grained control over their legal compliance, but Monero Standards will have great long-term impact on development and research at Monero.

Criticisms. Monero has suffered some recent criticisms about our hash function. I want to briefly address them.

First, I believe part of the criticism came from a confusion between Keccak3, SHA-3, and Keccak: we have never claimed to use SHA-3 as our hash function, we have only used the Keccak3 hash function, which is a legacy choice inherited from the original CryptoNote reference code. Many developers confuse the two, but Keccak3 was the hash function on which SHA-3 is based. In particular, the Keccak sponge construction can be used to fashion lots and lots of primitives, all of which could fairly be called "Keccak:" both Keccak3 and SHA-3 are Keccak constructions. This may be a subtle nomenclature issue, but it's important because a good portion of our criticisms say "Hey, they aren't using SHA-3!"

Second, I believe part of the criticism also comes from our choice of library, which in my opinion isn't a big deal as long as the library does what it says on the tin. In this case, our hash function is a valid implementation of Keccak3 according to the Keccak3 documentation. The most important criticism, from my point of view, is our choice of pre-SHA-3 Keccak3 as our hash function. Keccak3 underwent lots of analysis during the SHA contest, and Keccak3 is a well-vetted hash funtion. However, it has not been chosen as an international standard. There is a sentiment in the cryptocurrency community to distrust standards, which is probably a healthy sentiment. In this case, however, it means that our choice of hash function is not likely to be supported in common, well-vetted libraries in the future. Moreover, since SHA-3 is an international standard, it shall be undergoing heavy stress testing over the coming decades, a benefit Keccak3 shall not enjoy.

Last month, after some discussions, we made changes to our choice of PRNG in Monero to match the PRNG for Bitcoin. There has since been some discussions instantiated by anonimal about this choice of PRNG. We at MRL are doing our best to assist the core team in weighing the relative costs and benefits of switching to a library like crypto++, and so we believe these criticisms fall into the same category. We intend to address these issues and make formal recommendations in the aforementioned Monero Standards. Sorry for using the word aforementioned.

Things that didn't move much include a) educational outreach, b) SPECTRE, c) anti-ASIC roadmap, d) refund transactions. Most of which was on hold to complete multisig.

As far as educational outreach, I contacted a few members of a few math/cs depts at universities around me, but I haven't gotten anything hopeful yet. I wanted to go local (with respect to me) to make it easier to organize, but that's looking less likely. No matter how enthusiastic of a department we find, garnering participation from faculty members, beginning an application process for new students, squirelling up funding, working out logistics of getting teachers or lecturers/speakers from point A to point B, where to stash students, etc would be a challenge to finish before, say, July. And some schools start their fall semesters in mid-August. So I'm thinking that Summer 2019 is reasonable as the first Monero Summer School... and would be a real fun way to finish off a two-year post-doc!

December plan. I am going to finish multisig, and then finish the zk-lit review with Jeffrey Quesnelle, since these are both slam dunks. Any other time in December I have will be devoted to a) looking into the logistics of using the bulletproofs + RTRS RingCT set-up, b) reading the new zk-stark paper and assessing its importance for Monero, c) beginning work on Monero Standards, which includes addressing our hash function criticisms, our PRNG, etc.

Thank you again! This is an incredible opportunity, and this community is filled with some smart cookies. Every day is a challenge, and I couldn't ask for a more fun thing to be doing with my life right now. I'm hoping that my work ends up making Monero better for you.

We are all another month older, and a little wiser for it. In the past month, most of my work went into writing the MRL Roadmap MRL-R002 (which may be found here), working on the ring threshold multisig paper (RTM), and RTRS RingCT prototyping. I’m going to describe my work on these and make some announcements. In addition to all of the above, I try to vet at least two papers for further investigation each day; recently I have done some reading on forward-secure key exchanges. I am looking for possible applications towards view key security in light wallets.

**MRL Announcements: **

Meetings: At the suggestion of fluffypony, MRL is going to host weekly meetings on Mondays at 17:00 UTC on freenode. Our first meeting will be Monday 9 October 2017. The first week will be a research meeting, where contributors will describe their current work and progress, discuss technical details and obstacles they are working out, and solicit opinions from each other. The second week will be an “office hours” where any member of the community is welcome to come in and pester us with questions for a few hours. Thereafter we will simply alternate, until a newer better schedule is decided upon.

Personel: After hiring Sarang Noether full time at MRL thanks to the generous efforts of the community, we have been able to divide and conquer between RTM and Kenshi-Knaccc subaddresses, so MRL as a Lab has moved forward more rapidly already with his hiring. I have been reading through the subaddress scheme with Sarang and assisting him in copy-editing his draft on that topic while he has been assisting me with the multisig topic. We again welcome him.

Educational Outreach: I am currently testing the waters about writing a grant to the Monero FFS to fund a summer undergraduate program in cryptocurrencies hosted at a university for summer 2018. Testing the waters means finding a friendly department and asking friends in the Monero community about their feelings on donating to such a fund. Several colleagues suggest that hosting programs like this at schools is easy if they have been funded already, and the difficulty is rather in finding a department willing to participate in running a workshop (as opposed to simply renting out dorm rooms at a university and hosting classes in their classrooms). I would prefer to do this at a smaller school with a vibrant CS or math program, rather than shooting for something big and flashy, but finding a friendly department is the challenge.

For Multisig: The current draft of the RTM paper may be found here. Proofs are currently somewhere between “sketches of proofs” and “nonexistent” yet. Take this document as a pre-first draft until I’m confident in the proofs. Security definitions have changed non-trivially since I last made a posting, but I am fairly confident in my description of CIK(S) schemes, which is a novel description. I anticipate to be completely finished with a draft ready for review (by as many folks as possible!) by the middle of the first week of October. At this point, I’m seeking a balance between a theoretical description of the scheme and the proposed implementation (moreover, I am laboring over the correctness of the proposed implementation, because my description in that document is based on slightly out of date information).

For RTRS RingCT: Sarang immediately began assisting knaccc and I in our implementation of a RTRS RingCT prototype. Together, we three were able to finish our implementation. Unfortunately, between MLSAG RingCT and non-amortized RTRS RingCT, we experience a nonlinear trade-off between blockchain space and transaction verification time (see more below). This makes RTRS RingCT without amortization unsuitable for transaction verification. Work on this front has therefore turned toward the theoretical application toward blockchains (the nonlinearity in the trade-off between blockchain space and transaction verification time qualifies a game in which a RTRS RingCT blockchain is verified as a memory-hard problem) and toward the possibility of amortization in the application towards signatures (both in the MLSAG and the RTRS cases).

The nonlinear tradeoff: This is an interesting part, I think, which should have been obvious earlier on. If ring signature verification is always asymptotically linear, then introducing logarithmic sized signatures also introduces an exponential trade-off between verification time-complexity and storage space-complexity.

To see what I mean by this, assume that currently it takes T hours to download a copy of a blockchain v1.1 and it takes S hours to verify. A new modification to the protocol, blockchain v1.2, comes out. This modification claims to provide a 100p% improved space complexity but a 100q% increased verification time. A new miner will take 100p% less time to download the blockchain (now taking (1-p)T hours) but will take 100q% more time per transaction in the blockchain for verification (now taking (1+q)S hours). The gain in download time is pT hours, the loss in verification time is qS hours. Hence, for blockchain v1.2, we require pT - qS > 0 for the implementation to be called “more time efficient for nodes” (and the larger, the better). Although we have a strong desire for S to be small in general so that nodes can validate transactions rapidly, this provides a strict “worthwhile”-ness cut-off: violate this cut-off and it will take miners more time with v1.2 than with v1.1 to sync to the current block height. In RTRS RingCT, T grows linearly in block height and logarithmically in ring size: T is O(h log(R)). Tim Ruffing recently presented a proof that in all ring signature schemes, verification time (without amortization) is linear in ring size. Hence, in all ring signature schemes, S grows linearly in both block height and ring size: S is O(h R). Thus, satisfying pT - qS > 0 is impossible for all ring sizes for a fixed value of p and q. In fact, we roughly need q < p log(R)/R to see a benefit. This is freaking awful.

For example, in order for a p=0.1 (10%) improvement in blockchain space complexity to be worth implementing, we require q < 0.1 log(R)/R. For a ring size like R=10, this means we cannot sacrifice more than 1% of verification time. For a ring size like R=10^k, this means we cannot sacrifice more than a proportion q=k/10^(k+1) of our verification time. This is very small (check k=2, gives us a 0.2% wiggle room on verification time, k=3 gives us 0.03% room, and so on). On the other end of the extreme, in order for a p = 0.9 improvement in blockchain space complexity to be worth implementing, we require q < 0.9 log(R)/R. For a ring size like R=10, we can now sacrifice 9% of our verification time! But for a ring size like R=10^k, we can’t sacrifice more than a proportion of 9k/10^(k+1) of our verification time. For a ring size like R=10^3, this means even a 90% improvement in blockchain space is unjustifiable if it means more than a 0.27% increase in verification time (not to be confused with 27%). You may ask yourself whether we can weight the formula linearly and use cpT - dqS > 0 where c/d reflects how much more we value download time than sync time. However, this leads to the same asymptotic trap as before.

Two final points about this: 1) none of the takes security into account and 2) range proofs don’t work this way. For 1), we may value large ring sizes more highly for security reasons, set R=10^k for some value of k, and use the above sorts of arguments to draw conclusions about tolerable changes to our protocols. For example, for a modest ring size of R=10^2, we require q < p/50, which is to say that no improvement of blockchain size by a factor of p is worth worsening verification time by more than a factor of p/50. For 2) range proofs are independent of ring size. In fact, T and S are both O(h) for range proofs, and so we merely require that p > q: we can justify a 10% decrease in range proof size if we increase verification time by at most 10%.

Anyways, back to work!

150 XMR sent from the general donation fund

Thanks again everyone who chose to fund me. I appreciate your support, and I am glad my contributions so far are speaking for themselves.