I could some volunteer work for you Sir.! Just email me if you need anything beyond my capacity. [email protected]
Sarang: funding for July-September 2018
SarangNoether posted this 6 years ago
It's your old pal Dr. Sarang Noether again! I'm good to go for another three months of research and development work for the Monero Research Lab. If you've been tracking the updates from my previous monthly reports, you know that I've been busy with a lot of projects to keep Monero on the cutting edge.
This month has been unique, since I wasn't supported by the Forum Funding System as usual. Instead, I've been teaching a summer cryptography course for the Duke University Talent Identification Program, where gifted youngsters sign up to take challenging university-level courses in their areas of interest. It's a full-time job for the students and instructors; the course runs all day, every weekday, for three weeks (with a week of staff training before it begins, totaling one month). Students in high school don't normally get to see how unbelievably cool applied cryptography is, so programs like this are essential for inspiring the next generations of mathematicians, computer scientists, and cryptographers; projects like Monero need talent! Because the course is so dynamic, my notes and materials get updated constantly; but never fear! They'll all be posted to GitHub once the course ends, so anyone who's interested in the history and present-day use of cryptography can learn too. In the interest of disclosure, I was compensated (but by no means extravagantly!) for my time by Duke University, including room and board.
Please take a look at my previous monthly reports for full details on my research activity; I've contributed my efforts to many Monero endeavors. Bulletproofs are a monumental and important task, and certainly the most visible project I've led so far; we've been working on them since the last half of last year, but it's a huge undertaking. We were the first distributed asset project to attempt a full deployment of these awesome new range proofs, and that means we're blazing a kickass trail. Lots of math, prototyping, coding, analysis, testing, and optimizing has gone into them. Even now, at the final review stage, we're still finding ways to make transactions smaller and faster. Less visible and shiny projects have included new research into refunds, signatures, transaction security, and more.
Every day brings something new when it comes to research. There is always a flurry of new academic work to stay on top of, new threats to analyze, cutting-edge ideas to dive into, and more. My labmate and I put together a brief roadmap that highlights some of the directions we want to take our research. But don't look at that list as all-inclusive or even a guarantee of what you'll see in a future release. The nature of research and development is fluid and intellectually risky. Many (most?) wild ideas end up not working, or aren't right for the project for one reason or another. But some are! The point of the Lab is to take a bunch of crazy ideas, figure out what sticks, and make them happen. It's a grand plan that has been, in my humble opinion, a huge success for the project and one of many things that makes Monero stand out among other projects.
As before, I've set this funding request at my interpretation of fair market compensation of an independent Ph.D. researcher. I use a window average and my best judgment for the exchange rate, understanding that it may fluctuate during the funding period. The amount is set at 250 XMR (any changes to that amount will be noted here as needed; none so far). I work hard to return value to the community for the value you provide here.
I'm always available to answer questions or take suggestions, comments, or complaints. Feel free to respond to this funding post, the accompanying post in r/Monero, or on the freenode IRC channel #monero-research-lab where we talk research. And finally, a huge round of applause to the community for being the engine that drives the Lab and the Monero Project forward. Onwards!
Donated!
Hello once again; Dr. Sarang Noether here with my monthly report for July. As always, my thanks to the Monero community for supporting my work and that of the Monero Research Lab in general. We work to keep Monero on the cutting edge through quality research and analysis, and this month has been no exception.
Bulletproof audit results are coming in! Kudelski Security has completed their final report, which includes responses from our researchers and developers. The gist is that a few minor issues were found that have been patched; of course, these issues were only found in our non-production code, and were all considered to be of low risk with no exploits identified. QuarksLab has provided their initial draft report as well. They identified issues that have been patched, but were also unable to identify any direct exploits. A third independent review from Benedikt Bünz has finished, and he has provided an initial report as well, finding issues only affecting the prototype implementation that do not apply to production code. Additionally, the transaction fee model is being updated to reflect the space savings offered by Bulletproofs, and you should see at least an 80% reduction in fees. Kudos to the many people who have worked hard on the math, code, analysis, and testing leading up to this point.
I spoke at a blockchain event in Portland on the importance of privacy and fungibility in digital assets. While this wasn't formally representing the Lab, I did use Monero as an example of good technology. My travel and hotel were covered by the organizers (with a small stipend for food), with no community funding used. In August, I will be speaking at our DEF CON village on design principles and attacks across different asset projects; my hotel, travel, and food will be covered thanks to generous community donations. In September, I will be delivering two similar talks at a privacy-focused event in Houston, where my expenses will be covered by the organizers. I think there are great benefits to educating the public through talks and presentations, and I like being transparent about how they are funded. Relating to this, lecture material and exercises from my summer course (which took place last month in Atlanta) have been posted to my repository. There are undoubtedly the usual typos and other mistakes present, so any corrections and additions are welcome!
My latest work has focused on a new confidential transaction model in the works by a group of researchers affiliated with Tim Ruffing, with whom we've interacted before. You may remember that name from some earlier work on sublinear ring signatures. Their team provided us an internal draft of a new paper that describes a clever way to integrate several aspects of confidential transactions, like ring signatures and range proofs, into a single compact structure. The scheme could allow us to scale to large ring sizes without the associated cost in transaction size. I've been working on some prototype code to help me better understand the math and scaling of the proposal, which are complex. We have no immediate plans to transition to this, but it's exciting new research that deserves a close look as it's being developed. Incomplete (and ongoing) code has been posted to my repository. To my knowledge, this is the first test implementation of several of the underlying mathematical building blocks.
Ongoing work for the next month will include several projects. I will complete my study of the prototype sublinear transaction model with more concrete data on scaling and feasibility. I will assist lab partner Surae Noether with review of his newly-completed multisignature scheme security proofs, which have been a formidable and comprehensive effort. There is interesting analysis to be done on how a CoinJoin-type model for transaction merging might (or might not!) be a future option for users who want such a thing. And I want to continue some early work on generalizing the Bulletproofs math to arbitrary numbers of outputs, which could have applications for other zero-knowledge systems. There is always plenty to be done!
As always, my thanks to everyone for supporting my work and that of the Monero Research Lab. We work hard to keep Monero safely on the cutting edge, and it's all thanks to our excellent community. Comments, questions, and suggestions are always welcome.
And now to Sarang's Reading Corner, a short list of some papers that I've found interesting recently.
Multi-Hop Locks for Secure, Privacy-Preserving and Interoperable Payment-Channel Networks: An interesting cryptographic primitive for use in payment channel networks.
Flux: Revisiting Near Blocks for Proof-of-Work Blockchains: A method of using so-called "near blocks" (whose proof-of-work does not quite meet difficulty restrictions) to incentivize honest mining strategies.
Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials: A zero-knowledge framework for polynomial relations that has many applications. The techniques in this paper were adapted for use in the proposed sublinear confidential transaction scheme by Ruffing and collaborators.
Zerocoin: Anonymous Distributed E-Cash from Bitcoin: The original paper describing Zerocoin, a way to use zero-knowledge proofs for anonymity as a Bitcoin extension. This work was the basis for later papers that led to Zerocash and the Zcash project. I revisited this paper while writing a talk on design principles and attacks on asset projects. An interesting read for some of the simple techniques it uses.
Made my small contribution. Keep up the excellent work!
Hi, everybody! (Hi, Dr. Noether!) It's your pal Sarang here to deliver my monthly report for September. Even though it might get old, I never tire of offering sincere thanks to the entire community for your support of my research and the Monero Research Lab in general. We work to improve the project and provide value through research and development.
There are few big and flashy accomplishments to tout this month, but a number of small additions to our growing base of knowledge. My repository contains updated technical notes on dual-key ring signatures and an easy set-theoretic representation of spent outputs that you may find interesting. The goal of the first paper is to examine new fundamentals that could be useful in off-chain applications. The goal of the second is to provide a simple generalization of output blackballing.
As the clock ticks down on our network upgrade, optimizations and updates continue. Some of these will be included in later releases due to timing. An updated scalar inversion algorithm removes our reliance on OpenSSL libraries, and we now have a simple and efficient batching approach to these operations for use in Bulletproofs, for example.
I was interested to understand use cases for view keys, and ways in which a user could safely provide balance information without compromising knowledge of spent outputs. New approaches that were examined all had major issues with efficiency and knapsack-style information leakage, leading me to conclude that our current method of balance proof (providing an auditor with your view key and signed key images) provides approximately the same attack surface as potential alternatives. There are certainly valid arguments for wishing to provide outgoing transaction information for transparency if a user wishes, and I hope we can identify better solutions in the future.
My next funding round, which covers full-time research for the rest of this calendar year, has completed. Work for the next few months will be varied and includes several larger projects that I've been working on throughout this funding period as well. One is to complete a feasibility study for sublinear ring signatures with operational prototype code; this was delayed by other more pressing projects, but I am returning to it in order to solve some lingering computational problems. Another is to determine useful applications of Bulletproofs to Monero-specific zero-knowledge statements, which would require quite a bit of new code to handle this more general approach to the proving system. A third is some new work into graph-theoretical representations of ring signatures, which may provide us useful adversarial heuristic information and help us better understand what approaches an adversary might take to distinguish particular transactions. Each of these is a large and complex area of study, but this is the purpose of the Lab!
As always, I welcome comments and questions regarding this research. Monero continues to thrive because of community dedication and support. Onward!
Hello again! Dr. Sarang Noether here with my monthly report for August. I say it every month, but my sincere thanks go out to the entire Monero community for supporting my research for the Monero Research Lab. The goal is always to drive Monero forward through the finest research and development efforts.
As our next scheduled network upgrade approaches, I've completed further Bulletproofs optimizations to squeeze as much speed as possible out of transaction verification. As was our original goal, tests show that transaction size is crazy small and transaction times are crazy fast. Tests on a few different machines suggest that verifying one Bulletproof is over 4 times faster than our old method, and verifying a batch of 64 Bulletproofs is over 36 times faster than the old method! We also added some additional checks and safeguards to reflect suggestions from our audit process, taking a belt-and-suspenders approach. There is additional side work happening on some Bulletproofs generalizations that could be useful later. To help with this, I made a quick Python port of basic Bulletproofs functionality that is substantially simpler than the original; this port is for prototyping only, and is neither efficient nor asserted to be secure for production use.
I've assisted Lab partner Surae Noether with formalization of our multisignature scheme, which underwent major revision to reflect new academic research and more comprehensive analysis. The paper has been posted to the IACR preprint archive. Security proofs can get admittedly pretty ugly, but they are an important part of the development process that we hope will benefit other researchers and projects as well. We're completing similar formal analysis of dual-key outputs that was written up earlier.
The recent Monero village at DEF CON in Las Vegas was a smashing success, and I was glad to represent the Lab. I had the opportunity to share great information about the project with hundreds of people, both Monero enthusiasts and newcomers to the space. Our room was packed with attendees, and we even had to turn people away when we hit capacity! I delivered a talk on privacy research and attack vectors that was recorded and should be made available through more official DEF CON channels. I can also post the slides from this talk to my research repository if there's any interest; let me know. I'll be delivering similar talks on the importance of privacy research at upcoming events in Houston and Orlando (no community funding needed).
There's plenty of ongoing research happening. There has been good discussion on the practical functionality of view keys. Right now, proving the balance of an address involves giving an auditor both the view key and a list of signed key images, which leaks information about which outputs are spent. I'm interested to see if there are alternatives to this that don't have this kind of leak. To be clear, there is no plan to force users to give up any privacy. There are useful cases for wanting to demonstrate balance, and right now we don't have a good and safe way of doing so. Research continues on smaller ring signature schemes, on safe methods for refund transactions, and on heuristics involving ring size and churn behavior.
As always, on to Sarang's Reading Corner, a selection of just a few of the interesting papers I've come across recently. Being on this list doesn't mean I necessarily agree with the contents or conclusions, just that I found the paper interesting.
Coloured Ring Confidential Transactions: Initial work on how to include multiple assets on a single blockchain that's compatible with our ring confidential transaction model.
Mobius: Trustless Tumbling for Transaction Privacy: An idea on how to implement certain privacy features into Ethereum that applies ring signatures to mixing.
On the Instability of Bitcoin Without the Block Reward: An analysis of possible future implications to assets of finite supply, and a good reminder of why block rewards are important to mining incentives.
PHANTOM: A Scalable BlockDAG Protocol: An update to an earlier paper on a graph-based consensus model that has potentially good scaling.
Switch Commitments: A Safety Switch for Confidential Transactions: A simple and clever method for providing customizable security in commitments.