Please login or register.

Hire PhD mathematician to look into post-quantum crypto, ZK[...]

XMR1,153.33

funded of XMR1,050.00 target

54 individual contributions
109.84%
109.84070046762% Funded
1 payouts
XMR803.33 balance available
30.346978115967% Paid Out

Milestones 1/3

  • June

    Payout for June, 2017

    Completion Date: Friday 30 June 2017

    Funds awarded: 33.33% (~XMR384.40)

  • July

    Payout for July, 2017

    Funds awarded: 33.33% (~XMR384.40)

  • August

    Payout for August, 2017

    Funds awarded: 33.33% (~XMR384.40)

Payouts 1

  • 350 XMR (Friday 30 June 2017)

WHAT: Hire me, a newly-minted Ph.D. Mathematician for research, mathematical modeling, statistical analysis, paper publication, grant writing, and educational/professional outreach. Goals include minimizing blockchain bloat, ensuring Monero is robust in a post-quantum world, and investigating ZK protocols. See below for details.

WHO: My name is Brandon Goodell. I worked under the pseudonym Surae Noether earlier in graduate school. I have a B.Sc. in math from Colorado State University, an M.Sc. in math from North Dakota State University and, in a few weeks, a Ph.D. from Clemson University in Mathematical Sciences. My research in academica, working chronologically backward, involved integral domains in commutative algebra, computationally efficient models of neurons, and modeling disease propagation deterministically and stochastically. I can make my CV available to anyone who wants a copy, and there is a bit more detail about my Ph.D. work at the end of this.

WHY: Crypto is an arms race, and Monero is in a rather fragile position. The way I see it, Monero is facing the following problems in the near future, in no particular order: (1) any system built without zero-knowledge protocols is leaking info with each broadcast transaction, (2) post-quantum cryptography is going to be a requirement, and (3) blockchain bloat: block size is proportional to key size and key size is proportional to privacy. I can't promise to fix each of these issue, but I can promise to devote my time and energy into new proposals towards their eventual solution.

PROPOSAL, EXPIRATION: Hire me for 1050 Monero for June, July, and August 2017. At the discretion of the community renew on a quarterly basis (adjusting for exchange rate to USD).

Primary job description: Discover and vet new ideas and community proposals, participate in community conversations on IRC, the forum, reddit, and disseminate any rigorous results I develop (proofs or counter-proofs of security, technical reports with formal plausibility and security analyses, white papers, peer reviewed publications, and speaking at conferences). Previous contributions to Monero along these lines included Shen's Ring CT and my previous work on chain reactions. The emphasis of the bulk of this work will be on points (1), (2), and (3) from the WHY section: zero knowledge protocols, post-quantum crypto, and blockchain bloat.

In addition to this, one of my long-term goals for MRL is for the lab to be self-sufficient to remove the burden from the community members. Finding external sources of funding (possibly through grants, possibly through other sources) will likely be an annual tradition with an eye toward that goal. Publication of white papers including plausibility and security analyses, together with submissions to peer-reviewed scientific journals, will make up the component of my work most visibile to the community; if I can manage to actually land a grant, that would be a completely different animal.

My tertiary job may include educational and professional outreach, depending on how the community feels. I have ideas for educational outreach programs ranging from high school to college to graduate school; I think this would be a fun way to get the next generation of coders interested in crypto and the future backbone of financial data structures. I also have ideas for professional outreach. This involves cultivating talent in the academic worlds of the math and computer science communities, as well as encouraging the talent already in our communities... I would like to organize an annual technical cryptocurrency conference to invite the active and thoughtful members of the Monero community, other cryptocurrency communities, the academic community to discuss the goldmine of thought experiments swirling around cryptocurrencies.

MILESTONES: Since this is not a finite project with a well-defined outcome, milestone assessment may be an impractical way to judge progress. We could judge my progress by number of papers published each quarter or each year, but that provides motivation for me to produce least-publishable-units (LPU): short papers that say just enough to get me paid. I won't have time to necessarily put out higher quality, in depth publications if I have a quota to meet. I do not think it is in the interest of quality research to work under an LPU incentive.

However, I like the idea of writing an MRL newsletter each quarter that summarizes mine and other members' contributions to the Monero community and toward the MRL research efforts. This newsletter would, presumably, be an investor's reality check that their money is not being wasted. Certainly, investors will see the white and peer-reviewed papers put out by MRL in addition to this newsletter, and although the peer review process can be agonizingly slow, papers can be posted to ArXiV in the midst of review. For these reasons, I am not tremendously concerned that it will be difficult to convince the community of my worth in terms of reearch output, but it would be nice to produce a newsletter as both a brag for our educational outreach work and to satisfy the notion of a milestone for investors. Of course, I'm absolutely open to suggestions.

Lastly: I had a very good time working for MRL last time around and there is lots of room for improving my work (I was young... alas). You can find my graduate student page here. For more details about me: my PhD qualifying exams were in abstract algebra, real analysis, and mathematical statistics. My coursework has touched on a very wide range of mathematics... an incomplete list includes topology and graph theory, algebraic geometry and commutative algebra, cryptography and coding theory, real and complex analysis, harmonic/Fourier/functional analysis, mathematical statistics, variational calculus, and pattern recognition/machine learning. I starting programming computers in middle school, and over the years I have coded in C, C++, Java, Python (2), and (if you count them as programming languages rather than software packages) in R, Mathematica, Matlab, and Maple. You can find my github at https://www.github.com/b-g-goodell where I have a shitty automated Coinbase bitcoin trader, a shitty evolutionary algorithm for training recurrent neural networks, and a not-so-shitty "probabilistic neural network," which is a dead-simple pattern recognition device. I have been teaching throughout graduate school, courses ranging in difficulty from business calculus to differential equations for engineers and proof writing for undergraduate math majors.

Replies: 36
suraeNoether edited 3 weeks ago Replies: 2 | Weight: 450 | Link [ - ]

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. Signature sizes, RingCT: Add to this list “range proof sizes.” No progress to report yet beyond reading.

  7. 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.

Reply to: suraeNoether
rm edited 1 week ago Replies: 1 | Weight: 476 | Link [ - ]
  • what's the motivation for focusing on changing the stealth address/key derivation process? sha3/keccak anything works here, and would free up a lot of your time for more important things. I don't understand why you're mentioning provable security when (a) monero isn't provably secure anyway and (b) using a hash function that isn't vulnerable to these attacks addresses the attacks perfectly well.
  • the zk paper is focused on snarks, why? my snark criticisms are mostly in the comment below. also where would you be publishing this? it reads like a literature review of snarks?
  • are you a cryptographer? apparently (not naming names) the borromean ring signatures are blah
  • the ringCT proofs (signatures?) are huge atm. Why are they so large? how can you make them smaller? :)
  • do you have any info on the multisig stuff? It seems super interesting but everywhere I try and look for it there's just deleted posts and dead links :( is it broken?
  • why game theory over stats on the distribution problem? it seems like a simple stats problem? i don't think picking the most random inputs in this case would work well at all? they should be chosen with an extreme bias towards recent txos.
  • > 'As a matter of user privacy, the urgency of this problem is rather low, due to the one-time addresses in Monero' -- I totally disagree, this problem allows any curious onlooker to guess which of these one-time addresses is performing certain transactions, which over time can be used to build up profiles of monero users. Which goes completely in the face of everything monero is trying to do (unless I've misunderstood and monero is trying to just trick people into thinking that their actions are private, in which case carry on, i guess)
Reply to: rm suraeNoether
suraeNoether posted 1 week ago Weight: 478 | Link [ - ]

1) Replacing possibly insecure schemes with provably secure schemes at a low cost is the motivation. In this instance, we have a particular scheme that is known to be implementation-sensitive and lacks a security proof. There is a relatively cheap alternative with an implementation-agnostic security proof. Seems like a no-brainer to not rely on the strength of any particular component (like Keccak) if we don't need to.

2) It is a literature review of snarks. It is about snarks because I was curious about how snarks worked and Jeffrey offered to do some work for me. Moreover, transaction validation, in an abstract sense, is "like" an argument of knowledge, and cryptographic primitives revolving around that idea are therefore of great interest to my research in cryptocurrencies. I don't know where it's going to be published yet, we haven't gotten that far into editing.

3) I am an algebraist but I have taken several graduate-level courses on cryptography and algebraic geometry underlying elliptic curve crypto. I'm currently working through the borromean ring signature stuff and the RingCT stuff.

4) RingCT proofs are big because of the range proofs; zk-proving that the amount of a transaction output is within a certain range. I have been first focusing on the signature changes in RingCT with an eye toward multisigs, so I haven't had the pleasure of figuring out the range proofs yet.

5) The only current description of the current multisig scheme, is here. The scheme requires vetting and a security proof before I'm going to be comfortable with it, although it's close to being implemented.

6) Let's say you work in law enforcement and you decide on a set of rules along the lines of "If we are more than 99% confident that so-and-so is implicated in a transaction, then we will consider this to be 'beyond a reasonable doubt.'" Then all anyone needs to do is hand-fashion their ring signatures to be in the 99.9th percentile. They will be excluded as an outlier at 99% confidence and be totally missed by law enforcement. On the other hand, if someone wants to frame you, they can hand-fashion their own ring signatures so that your outputs lie dead-smack-in-the-center of Mr. Law Enforcement's "best guess" window, although their outputs are in law enforcement's outlier regions.

Lying with statistics is super easy. Statistics all boils down to getting a "random" or a fair sample. In the real world, human behavior corrupts that immediately. Consequence of evolution/ecology/economics.

7) Forgive me, where are you quoting from? Which problem are you referring to here?

Reply to: suraeNoether
scoobybejesus posted 2 weeks ago Replies: 2 | Weight: 460 | Link [ - ]

First of all, this is very exciting. To have the MRL officially back in action, at least for now, is outstanding. It's obvious that you are driven/motivated, intelligent, etc; and work done and related updates so far are very much appreciated. At the same time, I think it's important to play my role as a community member and also provide some [what is hopefully] constructive criticism.

-From what I read, I didn't see anything about zk-research as it would apply to Monero. In that respect, I'm a little disappointed. If something comes of it in the future, that could be exciting; but it actually doesn't seem pressing now.

-Yes, it would be great to see multisig formalized (if the fact that it isn't formalized is an issue). Certainly, an MRL paper describing Cryptonote design and implementation of N/N and (N-1)/N multisig would be awesome.

But here's the meat, IMO:

-Regarding the papers criticizing Monero, it would be nice to see this knocked out. If their arguments are flawed/slanted/etc, let's set the record straight. The papers are at least partially correct, so an MRL response may go a long way. I imagine that this response would be completed in connection with the churning/mandatory mixin issue and the distribution issue, which would be a huge, huge, huge accomplishment to have dealt with. In my view, these should be a primary focus. They all tie together, are all potentially critical to Monero's privacy claims.

Anyway, those are my two cents. Keep up the great work. I very much look forward to the next update.

Reply to: scoobybejesus suraeNoether
suraeNoether posted 1 week ago Weight: 478 | Link [ - ]

"From what I read, I didn't see anything about zk-research as it would apply to Monero." A few points. First, and most importantly, this is a first draft, and Jeffrey and I are working on a second draft as we speak that elaborates on usages of these constructions in cryptocurrency. Second, I didn't provide Jeffrey with any direction on this paper... leading me to... third, I got from him exactly what I had hoped: a broad-spectrum, shotgun-style look at the schemes as they are currently described and used. I wanted a broad-spectrum lit review of snarks to understand them in the abstract, to know how and when to use them in the future when I design cryptoschemes. Lastly, this was a lit review I was going to do for myself anyway, so it seemed wasteful to not document the process and give Jeffrey some more experience in technical writing.

I understand your concern about the papers criticizing Monero. These papers will be addressed directly with a research bulletin, hopefully by the end of my first three months with Monero. Right now I have literally only two MRL research bulletin drafts going: one of them is the EABE attack and one of them is a pair of responses to the recent criticisms. However in my estimation, although the criticisms are worth responding to, they do not present an immediate security risk. I have been devoting most of my time most recently to looking into the EABE attack and the churning approach to solving the problem, because this is a very serious route for an observer to de-anonymize folk's financial behavior that represents a security threat right now.

It's an interesting challenge to balance research into immediate issues that need resolving with long-term benefit to the currency.

Reply to: scoobybejesus suraeNoether
rm posted 1 week ago Replies: 1 | Weight: 476 | Link [ - ]

obviously I'm not OP, but one of the criticisms in the papers, that small 'mixin' sizes can affect the mixin sizes of others', without these people knowing that their anonymity set size has been reduced, actually isn't a problem for Monero anymore, even now. So was it just an announcement to this end that you were asking for? The problem was of the type 'if you send a transaction with two parties, and one of those is me, and then i send a transaction with that TXO, then obviously that one is me, and eliminating me from your anonymity set leaves just you. Now the minimum mixin size is 4, this just isn't an issue at all anymore.

Regarding the distribution issue, I completely agree -- OP this should absolutely be your focus for now. zk-snarks aren't at all relevant as they exist today, and I don't think anyone wants monero to turn into a zcash clone anyway. there are nice properties of monero (like total supply of coins being a publicly verifiable number) that would be lost if you were to implement zk-snarks. You should absolutely be looking at sublinear linkable ring signatures. They can be as small, or even smaller than snarks, and prover and verifier time are fast. But in the research roadmap you say that the distribution problem isn't a problem because monero has one time keys? This is a silly argument. the privacy of monero with the distribution problem and one time keys is ~the privacy of bitcoin with one time keys. that's not exactly what we're aiming for here, is it?

Reply to: rm scoobybejesus suraeNoether
suraeNoether posted 1 week ago Weight: 478 | Link [ - ]

Bitcoin with one time keys?

suraeNoether posted 1 month ago Weight: 419 | Link [ - ]

Hey everyone! I wanted to write a quick post to thank everyone again for funding me, and to provide a quick update on my progress.

Everyone seemed rather keen on the idea of a newsletter/research roadmap, so at the end of each 3-month period, I'm going to write up a little newsletter with a picture of where we've been, where we are, and where we are going. But since I just began, I figured that I should write up a brief initial description of the topics that will be under investigation in the first 3 months. This way, the community doesn't need to wait 3 full months to see what I'm getting up to. Here is the first MRL Research Roadmap. Expect another at the end of August.

In this case, it's little more than a to-do list ranked roughly by urgency and timeline: urgent or short projects come first on the list, non-urgent or longer-term projects occur later in the list. Future research roadmaps will include details on the progress of each of these items, will have new items added to it, old items removed, and so on. I'm seeking feedback for this roadmap. If someone has a pet project, or a suspected security flaw, we should reshuffle the list around as appropriate.

The first item on the list is not really a to-do but a brag, as it is a rather exciting development. A graduate student in computer science named Jeffrey Quesnelle at the University of Michigan-Dearborne has contacted MRL and is interested in dabbling with cryptocurrencies for his thesis! He has already written a literature review for me on the history of ZK-SNARKs, related constructions, and how they relate to cryptocurrencies. We will be whipping this into shape for a peer review publication by the end of my first 3-month period with MRL at the latest (first round of copy-editing is almost complete, just waiting on me to finish up a few pages of notes). Jeffrey is willing to do work on behalf of MRL like prototyping new cryptosystems. His experience includes cryptography in vehicles for the automotive industry and has interests regarding the internet-of-things, so if anyone has any other tasks for Jeffrey, we can always put him through the ringer :D

You will notice this roadmap covers a lot of ground, from immediate small projects to pie-in-the-sky future-proofing. None of this is guaranteed, and some of these projects could take years, even with many many contributors, so do not consider this a list of things that will be coming to Monero soon (although some high-urgency, short-term projects will be seeing something rather soon by necessity). These are essentially the big buckets I'm currently putting my efforts into. Again, I'm seeking feedback, please do not hesitate to contact me.

rm edited 2 months ago Replies: 2 | Weight: 338 | Link [ + ]

Hey! First, a disclaimer on my behalf -- I came here through a link that Zooko shared, and I'm not really active at all in the monero community, but as we have fairly similar backgrounds (yours is cooler, congrats on becoming a dr!!!!) I thought I'd hand over all the low hanging fruit I know about, so you can crack on with them! It might also act as a good jumping off point for me/anyone else who wants to swing by and make some researchies.

Education(?)-wise:

  • Ring signatures actually are zero-knowledge proofs. I think, technically, they're something like witness indistinguishable (non-interactive) zero-knowledge proofs of membership?
  • I don't hugely understand what you meant by > any system built without zero-knowledge protocols is leaking info,
    but I guess you're concerned about metadata? This is actually a topic I've wanted to do a big collection of info on for a while:
    • What is even revealing about Monero transactions at this point?
    • Timing analysis?
    • 'Intersection sets' (where a given sender and recipient appear together more often than expected) are an often cited issue with 'mixing' schemes, but actually don't affect monero (as address/public key reuse is impossss) so you can emphasize that somewhere.
    • Are the attacks outlined in AM's monerolink inherent to passive mixing schemes?
    • Is the distribution that transactions get picked from fixed now?
    • Are these sort of 'what people do in the future can directly influence the anonymity that I, following the protocol exactly, can get' problems inherent in passive mixing protocols? How do we define them? How do we minimise the damage? How do we parametrise the leakage?
  • Quantum proofing: what do you actually want to do here? This might be trivial from both a stealth address and pedersen commitment PoV; less so from a ring signature perspective. But that would be a really cool research avenue (is it possible??? Do you have any quantum crypto friends??? I would super work on this :D).

Scaling-wise:

  • You can easily make addresses much shorter.
  • There are ways that you won't even have to communicate a new 'public viewing key' alongside every transaction. This reduces address size even more! (but only works for parties who have transacted with one another before
  • Sublinear ring signatures!
    • A lot of these (actually, all that I can find!?) depend on a CRS (I've been told off for this, but i'm using CRS here to mean common reference string. This is the reason for ZCash's trusted setup -- pretty much there are some very_necessary_parameters that can only be constructed with knowledge of very_dangerous_information). There's a result that NIZKs are impossible in the standard model, so choices are the above, or use the random oracle model (as monero does now!)
    • Someone better at cryptography could jump in here, or you could become this person! (If you're looking into building a new ring signature scheme I'd absolutely go bombard some nearby crypto researchers if I were you :))
  • > block size is proportional to key size and key size is proportional to privacy. What does this mean? Do you mean signature size is proportional to ring size? Or do you mean security is proportional to key size? If it's the former, absolutely - sublinear ring signatures !! If it's the latter, I don't recommend making the system less secure as a way to reduce bloat!!!!
Reply to: rm
suraeNoether edited 3 weeks ago Weight: 429 | Link [ - ]

In regards to your comment about ring signatures: the ring sig implementation in the cryptonote reference was, indeed, a non-interactive zk proof.

Reply to: rm
suraeNoether posted 1 month ago Replies: 1 | Weight: 418 | Link [ - ]

> Ring signatures actually are zero-knowledge proofs. I think, technically, they're something like witness indistinguishable (non-interactive) zero-knowledge proofs of membership?

My understanding is that there exists zero-knowledge implementations of ring signatures but not every implementation of ring signatures are zero-knowledge. AFAIK anyway. If you have a link, I'd read it.

> I don't hugely understand what you meant by > any system built without zero-knowledge protocols is leaking info, but I guess you're concerned about metadata? This is actually a topic I've wanted to do a big collection of info on for a while: What is even revealing about Monero transactions at this point? Timing analysis?

Fact of the matter is unless a protocol is provably zero knowledge (either perfectly zero knowledge or statistically zero knowledge) then a non-trivial amount of information is made available by definition (otherwise you could have proven your protocol was zk in the first place). You or I may not be clever enough to figure out how to piece that information together, but someone might be clever enough, or an advanced machine learning algorithm crawling the Monero blockchain may be clever enough in a few years.

Timing is included in this. It may seem like a trivial issue, but if you can pin a transaction down to within +/- 2 minutes using block height, you have quite a bit of knowledge of that transaction. It makes the knacccattack (churning) particularly effective: not only can an exchange determine the purchasing habits of its customers, it can determine what time of night they prefer to buy their hentai pillows with monero.

> 'Intersection sets' (where a given sender and recipient appear together more often than expected) are an often cited issue with 'mixing' schemes, but actually don't affect monero (as address/public key reuse is impossss) so you can emphasize that somewhere.

Intersection sets are interesting. So are techniques for solving nonograms and sudoku. I fear the day that Grobner bases can be brought to bear against a blockchain, even one that uses one-time addresses.

>Are the attacks outlined in AM's monerolink inherent to passive mixing schemes? Is the distribution that transactions get picked from fixed now?

I don't know yet, but that paper is on the top of my todo. AFAIK the distribution is still triangular, but "fixed" implies there is something wrong with our current method. FWIW, there is a game-theoretic thing happening, where if an eavesdropper assumes that transactions follow some "true" distribution, a malicious user could use that assumption to convince the eavesdropper that another ring member was responsible for a transaction: simply select an innocent and unaware ring member that is an outlier with respect to the assumed distribution.

> Are these sort of 'what people do in the future can directly influence the anonymity that I, following the protocol exactly, can get' problems inherent in passive mixing protocols?

This is not something I have considered, and the answer would be highly dependent on the definition of the passive mixing protocol and the specific implementation.

Keep in mind, though, Cryptonote/monero isn't really a mixing protocol, passive or otherwise, because there is a probabilistic thing happening. In a mixing protocol (say an old school vanilla bitcoin tumbler, not a shapeshift) you are playing a big pea-and-cup game, but an observer can watch every move carefully and, after a sufficiently long (possibly very long) period of time of computation, the observer can determine where each little pea ended up. Mixing protocols are deterministic in that sense. In Cryptonote, implication of ownership is shared across multiple addresses (all of which are one-time addresses, no less).

Even knowing deterministically where the vast majority of the money is going is not enough to pin down the probabilistic ownership thing. If I work for the NSA and I have already revealed a million transactions in the mempool, and one of the owners of one of those transactions signs a ring with even only ONE other member, I will not be able to do better than a coin flip in guessing the signer without extra information. This is distinctly different from deterministic mixing: if I have a bunch of bitcoin UTXOs and I send them through a mixer, no matter how large, I will be able to eventually determine exactly which addresses ended up with those UTXOs. In fact, for each and every little transaction I create to mix them all up, I can see the sender and receiver addresses clearly.

One question might be "can traditional mixers outpace blockchain forensics," but that's a completely different topic (and one I haven't thought about.

>How do we define them? How do we minimise the damage? How do we parametrise the leakage?

Good question. I think, short of perfectly zero knowledge constructions, there will always be a trade-off making your security dependent upon future (possibly malicious) user behavior.

>Quantum proofing: what do you actually want to do here? This might be trivial from both a stealth address and pedersen commitment PoV; less so from a ring signature perspective. But that would be a really cool research avenue (is it possible??? Do you have any quantum crypto friends??? I would super work on this :D).

Secretly I want Monero to be the first quantum-proof cyptocurrency: signatures, hashing algorithm, proof of work. Publicly, I have sincere doubts if PQC will ever be lightweight enough to build a decentralized blockchain that is remotely reasonably sized. All my crypto friends, quantum or otherwise, with a few exceptions, work at NSA or have zero interest in currency, unfortunately.

> You can easily make addresses much shorter.

Do tell.

> There are ways that you won't even have to communicate a new 'public viewing key' alongside every transaction. This reduces address size even more! (but only works for parties who have transacted with one another before

I will try to look into this, the notion of view keys has interested me a lot. I would love the ability to generate view keys with scaled viewing rights (viewing receipt of transactions, viewing sent transactions, viewing both, viewing transactions sent to or received from certain parties who consent somehow,

> Sublinear ring signatures! A lot of these (actually, all that I can find!?) depend on a CRS (I've been told off for this, but i'm using CRS here to mean common reference string. This is the reason for ZCash's trusted setup -- pretty much there are some very_necessary_parameters that can only be constructed with knowledge of very_dangerous_information). There's a result that NIZKs are impossible in the standard model, so choices are the above, or use the random oracle model (as monero does now!)

That is mostly my understanding also, and trusted setups need to be avoided in Monero, which is why I'm looking deeply into ring sigs, their history, their variations.

> block size is proportional to key size and key size is proportional to privacy. What does this mean? Do you mean signature size is proportional to ring size? Or do you mean security is proportional to key size? If it's the former, absolutely - sublinear ring signatures !! If it's the latter, I don't recommend making the system less secure as a way to reduce bloat!!!!

1) Block size is proportional to key size: I mean if you double the size of keys, you will double the average block size.

2) Key size is proportional to privacy: To encrypt any amount of information with perfect secrecy requires a key with the same "size" as that information. I mean this quite literally and abstractly: the more information you wish to encrypt, the larger the keys necessary to keep that information perfectly secret. I'm not saying we should reduce security to improve bloat, I am merely recognizing the trade-off between the two.

Reply to: suraeNoether rm
rm posted 3 weeks ago Weight: 454 | Link [ - ]

Hopefully you've clarified the zero-knowledge points sufficiently enough for yourself that I don't have to address them, but I don't know what churning attack is.

> Intersection sets are interesting.

Intersection attacks aren't a thing with one-time use addresses.

> Keep in mind, though, Cryptonote/monero isn't really a mixing protocol, passive or otherwise, because there is a probabilistic thing happening.

Monero is a mixing protocol. The fact you view it as more probabilistic than a specific type of bitcoin mixer doesn't prevent it from being a mixing protocol. Stop and go mixes are mixing protocols that rely on randomness too. Your comparison with bitcoin mixers is flawed too imo -- the situation is exactly the same. You need one honest party other than yourself to have the plausible deniability that you desire.

> which is why I'm looking deeply into ring sigs, their history, their variations.

Just get a sublinear ring signature that depends on ROM/DDH/whatever, and then make it linkable (by combining zero knowledge proof of private key that corresponds to one of the public keys with zero knowledge proof of private key which corresponds to one of the public keys and produces the given key image. The only sublinear ring sig depending on ROM/DDH rather than CRS is accountable ring sigs as found here, but you can hack at them til something useful appears :)

> 2) Key size is proportional to privacy: To encrypt any amount of information with perfect secrecy requires a key with the same "size" as that information. I mean this quite literally and abstractly: the more information you wish to encrypt, the larger the keys necessary to keep that information perfectly secret. I'm not saying we should reduce security to improve bloat, I am merely recognizing the trade-off between the two.

This is true for one-time pads... we don't use information theoretically secure encryption in real life. I'm not certain why you're even mentioning encryption? you're using keys to SIGN rather than ENCRYPT, meaning that the privacy absolutely doesn't depend on the length of keys, and rather absolutely depends on the number of other people in the ring.

anonimal edited 2 months ago Replies: 1 | Weight: 324 | Link [ + ]

Hi, Brandon, welcome back.

In addition to this, one of my long-term goals for MRL is for the lab to be self-sufficient to remove the burden from the community members. Finding external sources of funding (possibly through grants, possibly through other sources) will likely be an annual tradition with an eye toward that goal.

With those actions come a shifting of power and influence. I think such actions should not be taken lightly.

Reply to: anonimal
suraeNoether posted 2 months ago Weight: 325 | Link [ + ]

You are not wrong... there are a few points here, though, that I think are important. First and most simply, MRL is not the core team. If I make terrible recommendations, the core team can (AND SHOULD) ignore me. Examples of everyone ignoring me at will: (1) if the core team and community thinks I shouldn't seek external grants, then that should be removed from my job description, (2) even if we get MRL funded externally, MRL is not obligated to take the money (i.e. I'd rather apply and turn it down than not apply and never have the chance to turn it down) and (3) even if we accept external funding for MRL, the core team is under no obligation to listen to my results.

Secondly, and long-windedly, let me explain why I even inserted the idea into my first post. There's this problem I have with grant-based systems. A lot of STEM disciplines out there are grant-based; engineering, chemistry, etc. You publish or you perish, and you get grants or you perish. It's just the way of the research world in certain corners, especially education. This isn't entirely for bad reasons; offloading the cost of research away from the students and toward external sources makes paying for professors easier, and therefore makes education cheaper (imagine how much universities would charge if they were footing the bill for big physics projects instead of the Department of Energy...)

Until relatively recently, the math world hasn't exactly been considered a grant-based discipline. Computational mathematics has always required lots of funding for resources, but an algebraist or a topologist, historically, could do their work in a field of posies with a pen and paper. But recent trends in education has put pressure on math departments in many US universities to start seeking grants and funding (and so you start seeing a lot fewer pure mathematicians and a lot more computational mathematicians filling up departments, because provosts and deans put pressure on departments to hire professors who get grants... and because we need more computational research in a world where computers are increasingly dominating our lives). Consequently, almost every project pitches and applications in academia need to come equipped with four parts: (i) how will this help research? (ii) how will this help students? (iii) how will this serve the department/school/committee administratively? (iv) how will this help you get a grant?

Areas in math that are computational, or algorithmic, or related to simulations, or related to solving real-world logistic problems and optimization, these are areas that get grants because the ideas can be applied immediately and we see benefit immediately. An area like cryptocurrency has an astonishingly higher chance of getting grants than an area like commutative algebra, topology, or category theory. These areas are significantly less likely to get a grant because the applications of those extremely "pure" areas of math can take hundreds of years to crystallize. Sometimes that's not the case. Topology swept the Nobel prizes last year in physics. But my general point remains, which is the problem I have with grant-based systems, which is this.

My honest-to-god opinion? If this was a completely ideal world, I would completely agree with you. Personally, I think that expecting a mathematically-driven research group to become self-funded, while an admirable goal for any research group, is bad for a bunch of reasons. It's unlikely to be fruitful because grants in math are rare in the first place, it monetizes research, it takes away time from research, and overall, I didn't get into math research because I like writing grants. I don't like that our society has pushed math research in that direction. Your wariness is important. If some US government intelligence agency gives us a grant and MRL subsequently makes a proposal for a new signature scheme (or something), it would be reasonable for the community to be concerned about a repeat of the dual elliptic curve controversy involving the NSA from years ago.

Having said all that... the basic idea of alleviating the burden of funding research from the community, I think, is still a good one. And even though I'm not a fan of writing grants, and even though I don't think anyone here would be totally comfortable (if AT ALL comfortable) accepting an NSA grant... what if the granting agency is the National Science Foundation? Or some program through MIT's various cryptocurrency projects? I'm not convinced the idea of external funding is a good idea... but neither am I convinced it is a bad idea. And...

As I said earlier... I would rather apply and turn the money down than not apply. Then again... I may be the sort of guy who asked two girls out to prom in school so I'd have the option...

mrowwy posted 2 months ago Weight: 321 | Link [ + ]

+10

suraeNoether edited 2 months ago Weight: 320 | Link [ + ]

Thanks again, everyone! I'm pretty astounded and impressed by the amount of support everyone is giving me, it's a very nice welcome!

snakes posted 3 months ago Weight: 318 | Link [ + ]

Delighted to support this!

pwrz posted 3 months ago Weight: 317 | Link [ + ]

Donated.

monerodinero posted 3 months ago Weight: 317 | Link [ + ]

Donated +20

smooth posted 3 months ago Weight: 317 | Link [ + ]

donated 100

useujp posted 3 months ago Weight: 316 | Link [ + ]

+10.10

fluffypony posted 3 months ago Weight: 316 | Link [ + ]

200 XMR sent from the general donation fund.

AJIekceu4 posted 3 months ago Weight: 316 | Link [ + ]

Donated!

antw081 posted 3 months ago Weight: 316 | Link [ + ]

Donated.

gym7rjm posted 3 months ago Weight: 316 | Link [ + ]

Donated +6