Please login or register.

Continue funding Surae for another quarter (June, July, Aug)

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 on-and-off 2014-2016, and I have worked at MRL full-time since June 2017.

WHAT I am requesting a continuation of funding for my next quarter, of June-August. The overall lab-wide goals for MRL in the 2018/2019 year are described here. Contributors can expect in the next quarter: the beginning of the expansion of the document "Zero to Monero" into the Monero Standards, the literature review component of the roadmap to make progress as Sarang and I continue to read and take notes on current literature, a technical report on churn and linkability heuristics, and the (still in preparation) technical report on multisignatures (see below).

WHY Monero Research Lab has thus communicated with researchers all over the cryptocurrency industry, cryptographers, computer scientists, and computer engineers. In the past year, we have traveled internationally to conferences to learn and participate in the dissemination of results, contributed to several published technical notes on the technology underlying Monero, helped read and review papers for other researchers, participated in the cryptocurrency community more broadly, and learned quite a bit about decentralized payment infrastructures.

Problematically, our work into multisig has revealed a lot of dangerous territory. Our research into multisig is taking place concurrently with several big cryptography researchers, and their results are impacting our own pursuits. The Musig paper, released earlier this year here, seemed like a promising method of key aggregation, but only a short time later, it was proven here that the Musig protocol as originally published can not be proven secure under the discrete logarithm or one-more discrete logarithm assumption. Pause for a moment and think about that: this is not a proof that the scheme is insecure, but a proof that the scheme is not provably secure! If we want to rely only on provably secure schemes, then we must abandon the original Musig protocol, even if we secretly suspect that the ground truth is that Musig is not breakable.

To give an idea of the speed at which this research is proceeding, the same paper proves the unprovability of security in this approach also (with some of the same authors!) and proposes a new provably secure signature scheme. To read more about some of the depth and complexity of proving multisignature schemes secure, this paper has some interesting explanations of the Knowledge-of-Secret-Key assumption; we are also collecting more papers on the matter.

HOW MUCH TOTAL 135 XMR. I am asking for 9000$ USD/month, and I am asking at 200 USD/XMR as my baseline exchange rate, which is a hair over the 30 day exponential moving average as of the moment I posted this. 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.

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.

Replies: 9
suraeNoether edited 8 months ago Weight: 0 | Link [ - ]

Surae 2018 August updates:

Greetings all,

In the month of August, I met a lot of you in person in Las Vegas at DefCon. This was fun, but I was sick most of the time, so I didn't get to spend as much time with you guys as I wanted.

I also posted the multisig paper on IACR, available here. I have posted it on my github here, and I have a meta-thread going to collect all review and copy-editing changes as they come up, see here. After we select a journal and send it out for peer review, I'll post any information from that process that I can in that issue, or in a similar issue.

I also continued my churn analysis; under a certain null hypothesis, it looks like ring sizes around 19 or 20 are unnecessarily large for transction histories to be concretely indistinguishable with only 3 churns. The write-up for this is in-progress (not quite ready for sharing). Under this hypothesis, using Chebyshev's inequality, we obtain a rough bound: for d churns and ring size r, with a probability of q of "de-fungible-izing" a transaction spending a tagged or poison output, with the attacker being the true spender or knowing the identity of the true spender of proportion p of the blockchain, transactions are (approximately) concretely indistinguishable up to this probability q if pqr^d > 1. The Chebyshev inequality is notoriously a very weak bound. For example, if the attacker controls half the blockchain and we want the probability of q to be smaller than 10^-6 (i.e.\ one in a million tagged transactions are identified) then Chebyshev's says we need r^d > 2*10^6. For a ring size of 20, this means d = 5 churns. However, as I mentioned above, the practical number for d is closer to 3 for a ring size of 20.

My churn analysis ended up extending to a game-theoretic formalization of the fungibility of a digital currency, which informally goes like this. Alice and Bob are two PPT algorithms with access to some non-empty wallets. Alice sends Bob a single transaction, whose outputs are "tagged." Bob selects a random bit b and is granted full access to the digital currency network for up to q blocks. Bob then sends Alice m new transactions, whose outputs are "deposits." Alice then outputs a bit b'. The bit b indicates whether Bob shall try to include at least one tagged output in at least one deposit, and the bit b' indicates Alice's guess at the value of b. Alice wins if b = b'. If for any ppt Alice, for any ppt Bob, Alice has a probability of success at most negligibly greater than 1/2, we say the protocol is (q, m)-fungible.

I also got horribly sick in the middle of the month, and I've been sort of inactive as a consequence. I hope that getting the IACR paper out the door and developing some concrete approaches to churn and fungibility is satisfactory for the community. I have been reviewing the DLSAG paper by Sarang and I have started writing up a paper whose title is already known: "Spender-ambiguous cross-chain atomic swaps of confidential assets." This involves formalizing threshold ring confidential transactions (thring confidential transactions?) using dual output ring signatures being described by Sarang.

I want to once again express my gratitude to the Monero community. My work so far at MRL has been extremely rewarding to me, both personally and professionally; I hope my work on multisignature can bring confidence to the community about the security of their funds, and I hope I can continue to contribute valuably to the Monero community.

Surae

nioc edited 8 months ago Weight: 0 | Link [ - ]

I have watched the activity at MRL these last months with a smile on my face as much fundamental work for Monero was being done. Foundational work has always been a strong point of Monero and I fell that it is important to continue that focus. I will support this funding.

erciccione edited 8 months ago Weight: 0 | Link [ - ]

<3 your work Surae. Will donate

antw081 edited 8 months ago Weight: 0 | Link [ - ]

Donated.

suraeNoether edited 8 months ago Weight: 0 | Link [ - ]

Surae 2018 Q3 updates:

Greetings all,

I am joining my June and July progress reports for convenience.

June

The following is a description of my work for June 2018. I have been working on: 1. Ongoing work on the security of multi-signature schemes, the Knowledge-of-secret-key (KOSK) setting, rewind/replay attacks, and tree-based signing. This has included communication with community members and members of the cryptography community. The multi-signature MRL bulletin is still in prep (see below). . Ongoing work on consensus systems, selfish mining, cryptocurreny network dynamics, and population ecology-inspired network simulations. . Ongoing work on a formal proposal on selecting a fixed consensus ring size and how to go about selecting that ring size. 4. Developed a statistical test for Moneromooo. The test is based on hashrate to warn a node that the hashrate may have experienced a sharp discontinuity. I have a blog post (in preparation) planned working through the creation of such a test from a formal hypothesis testing perspective from mathematical statistics. . Volunteered on the ZCash Foundation Grant-Making Committee, helping guide the foundation in distributing $250,000 for projects related to "internet payment privacy infrastructure." 5. Assisted serhack and UkoeHB with their writing projects: Mastering Monero and Zero to Monero. 6. Held research meetings (see here, here, here, and here).

Here are some progress notes.

My time on multisignatures has been productive, but frustrating. I brought the multisignature paper mostly to it's current state (you can see it here), which is still "under construction." The knowledge of secret key (KOSK) setting has some problems with it unless it satisfies from strict formal requirements (which I'm looking into); abandoning the KOSK setting seems to expose us to a commit-and-reveal stage which might allow a certain sort of replay attack (an especially egregious problem in the case that a sloppy implementation leads to users exposing their private keys). I am communicating with some authors in the space to see if I can gain some clarity on proof details and attack routes. So, more research needs to be done, but we are rounding the corner here. The primary "works cited" include: 1. 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 2. Maxwell, Gregory, et al. "Simple Schnorr Multi-Signatures with Applications to Bitcoin." (2018). PDF link here 3. 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 4. Bellare, Mihir, and Oded Goldreich. "On defining proofs of knowledge." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992. PDF link here

Consensus systems. I have been working on network simulations (see here) and I have started looking into some other interesting approaches (see here). Additionally, I've been reading up on the following papers. I have no particular thoughts yet. This sort of reading is an ongoing sort of task that will always take time at MRL, so we can stay on top of new research in the area. . Team Rocket. "Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies", 2018. . Fruit chains (Pass, Rafael, and Elaine Shi. "Fruitchains: A fair blockchain." Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, 2017.

Blockchains as an abstract object, selfish mining, and Ethereum as an economic predator: Call this a flight of fancy. I've made several updates to my PoissonGraphs project here, which simulates a network live for testing the dynamic properties of things like difficulty algorithms and consensus algorithms. Any change to our protocols would require looking at questions like "how stable is the algorithm?" and "how rapidly does the algorithm return to an operational equilibrium after a perturbation?" Some of these are difficult to analyse without just straight-up Monte Carlo simulations, which is what PoissonGraphs is meant to do. It's almost ready. It spits out a human-readable transcript that could be animated by an ambitious person. I am interested in eventually coupling two such networks together (like Bitcoin coexisting next to Ethereum) with an econonomic model of trade between the two simulating some central exchange authority.

In addition to that, I have a colleague (formerly at University of New Mexico, and soon to be at the University of Exeter) who is interested in writing a paper using population ecology inspired model of a smart contract system like Ethereum and a more usual system like Bitcoin, to model how a clever smart contract system like Ethereum could "prey" upon the hashrate of an innocent unsuspecting Bitcoin. Papers I'm reading that are loosely falling into this pile include the following. 7. Ritz, Fabian and Zugenmaier, Alf. "The Impact of Uncle Rewards on Selfish Mining in Ethereum." Arxiv. 2018. 8. Pass, Rafael, Lior Seeman, and Abhi Shelat. "Analysis of the blockchain protocol in asynchronous networks." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2017.

July was mostly taken up by multisignatures, which are freaking done! Well, ready for submission anyway.

My time on multisignatures came to an end: no more writing before submitting to a journal and receiving comments from reviewers. You can see the current incarnation here. We are currently considering different journal options.

A new sublinear ring signature scheme was submitted to MRL by Lai, Ronge, Schröder, Thyagarajan (all at FAU), Ruffing (at Blockstream) and Wang (at CUHK). Sarang started coding it in Python, and I've been working through his code with him looking for various indexing stuff, and generally learning about polynomial commitment schemes.

DLSAG: I started to review dual-output LSAG signatures for use as return addresses, written by Sarang, formalizing an idea by Pedro Moreno-Sanchez.

I want to once again express my gratitude to the Monero community. I am excited to meet all y'all at DefCon in 120 degree heat. I hope that my work so far at MRL has been pleasing to you guys, and I hope my work on multisignature can bring confidence to the community about the security of their funds.

suraeNoether edited 8 months ago Weight: 0 | Link [ - ]

If anyone is curious, here is the current multisig paper: https://v2.overleaf.com/read/bfjfkdgnhgvh

Alex058 edited 8 months ago Weight: 0 | Link [ - ]

Donated

binaryFate edited 8 months ago Weight: 0 | Link [ - ]

3 XMR donated from XMR.TO

pa edited 8 months ago Weight: 0 | Link [ - ]

donated