Computational work for OSPEAD parameterization
Computational Work for OSPEAD Parameterization
Abstract
The OSPEAD project led by Rucknium will substantially improve user privacy by reducing Monero's statistical attack surface. The project's goal is to overhaul the decoy selection algorithm (DSA) to remedy weaknesses in Monero's privacy model.
To achieve the best fit for OSPEAD parametrization, the analysis code developed by Rucknium needs to be computed over a much larger portion of recent Monero transactions. The number of rings that can be processed is the “sample size” for the statistical analysis, so we desire as many data points as possible to enable Monero's OSPEAD-informed DSA to match the true spend distribution as closely as possible.
The first step to achieving a large sample size is porting the current OSPEAD code written in R (a slow interpreted language) to a fast compiled language like C++ or Rust. However, even with faster code, analyzing the rings one at a time in series will limit the practical sample size. To unlock analysis of 10^5 - 10^7 rings, it is also necessary to parallelize the code and run the analysis on a cluster or high performance workstation which contains dozens of CPU cores. Without these changes, the current R code would take years to run. With these changes the analysis will be executable with several days to weeks of compute time. This unlocks a critical bottleneck for OSPEAD parametrization, which itself is critical for Monero user privacy and Monero's future as a whole.
In addition to efficiency improvements described above, we will increase precision in the final output by pre-filtering transactions with heuristics based on transaction uniformity defects. For Rucknium's analysis, the quality of the results is degraded if the analysis includes rings that were not generated by wallet2
software (the standard reference implementation). To avoid this, we will filter out non-wallet2
transactions by applying a number of fingerprinting techniques developed by Isthmus and Neptune over the last 4 years of Noncesense Research Lab R & D. These include features such as unlock times and fees that would not be produced by standard wallets.
Current Status
The OSPEAD project has made exciting progress toward its goal of securing the decoy selection algorithm (DSA) against statistical attack, as outlined in Rucknium's original proposal. Given the statistical nature of the work involved, all algorithms and analysis is written in one of the primary programming languages used for statistics work: R. The benefits of R for statistical analysis are many fold, and it is certainly the right language for the job given the statistical focus of this project.
However, the OSPEAD project is currently bottlenecked by computation as there are an enormous number of rings to process from the last 6 months alone. There are certain computationally-heavy components of the code base that, when executed in R, result in the overall analysis taking 3 months to compute 1 week of historical data. While R is a best-in-class language for statistical programming, it is a higher-level language and thus quite slow in execution. Furthermore, the current code is single threaded and only runs on one CPU core. All of this is leading to a prohibitively-expensive computational barrier, which would need years of computation to complete the months of transaction analysis that is now needed to complete the OSPEAD project.
Proposed Analysis Engine Optimization Work
This proposal is designed to solve the challenge posed by the computational barriers described above. Specifically it allows the much faster processing of more data, in order to achieve the most robust OSPEAD results possible. If this project is approved, the following will be delivered to the OSPEAD team and the Monero community.
- Identify which parts of the code need to be sped up: Benchmark which components of the current OSPEAD R code are causing the computational bottlenecks described in the above section.
- Translate from R to a fast compiled language: Translate the bottleneck components into a fast, compiled language like C/C++ or Rust and bundle the translated code into R packages for easy integration. It will be critical for all computation and functionality to be precisely preserved, and to interface with remaining R code seamlessly, which will require significant engineering as well as robust testing. We expect that this translation step will result in a roughly 10x speed up.
- Parallelize the sped-up code: Once the code has been ported, we will further reduce runtime by parallelizing the existing code across multiple CPU cores. Parallelization can be carried out in R or the compiled language components, as needed to get the desired speedup. Parallelizing code can be quite challenging and requires expertise to work through the various common issues that develop, but the effort will be well worth it, as this step is expected to speed up computation approximately linearly with the number of CPU cores.
- Run the optimized code on a scientific workstation with 64 cores: As part of this CCS proposal, a scientific workstation will be leveraged to complete analysis and computation of the results needed by OSPEAD on 64 CPU cores. This CCS commits up to 23,000 CPU hours, providing more than enough compute needed to complete the OSPEAD analysis on a large number of recent rings with the above improvements.
- Results delivered for use in OSPEAD parameterization: Deliver code and results only to Rucknium, with full documentation and scripts designed to help others run the above code in the future (e.g. enabling the code to be run on MRC). All deliverables from this CCS will become part of the OSPEAD project and disclosure process managed by Rucknium.
Timeline & Budget
The overall project to speed up OSPEAD computation will take 5+ full time engineering weeks and require significant investment in computational resources. The breakdown is as follows:
- Benchmarking bottlenecks: 0.5 weeks full time equivalent (FTE) engineering work
- Translating bottleneck code and ensuring continued interoperability with initial code: 1.5 weeks FTE
- Parallelizing code to run on multiple CPUs: 1.0 weeks FTE
- Analysis to filter out non-
wallet2
transactions: 1.0 weeks FTE - Running optimization on scientific work station: 0.5 weeks FTE and up to 23,000 CPU hours committed
- Final deliverables including documentation; 1.0 weeks FTE
Total time: 5.5 weeks FTE + 23,000 CPU hours. We expect the engineering work to be complete by Mar 30, 2023.
Total budget: 190 XMR, paid at the start of work to avoid exchange rate volatility risk.
Team
Mitchell Krawiec-Thayer (Isthmus) and the Geometry Labs engineering team
Dr. Mitchell Krawiec-Thayer is a privacy tech researcher whose Monero contributions have largely focused on empirical transaction tree analysis leveraging statistical heuristics and transaction uniformity defects. Other past Monero work includes fingerprinting the mid-2021 transaction volume anomaly, a statistical analysis of nonce value distribution, an opportunistic study of miner equipment types, and identification of the heuristics that will be used to filter non-wallet2
transactions in this project. Mitchell is the President and Chief Scientist at Geometry Labs and will coordinate this CCS process. The lead engineer on this project will be Cheyenne Atapour, a blockchain research engineer with experience in developing performant systems. He has the experience with compiled languages such as C++ and Rust necessary to optimize the OSPEAD code. Geometry Labs is a blockchain and cryptography research & development team, whose specializations include: blockchain infrastructure, scientific tooling, analytics and observatories, and development of novel cryptographic mechanisms.
Merge request reports
Activity
The proposal was developed with my input.
From the beginning, the plan was to get help from C++ developers. From the original proposal:
I will work with j-berman and mj to develop and implement OSPEAD, as they outlined in their own CSS proposals.
j-berman is working on Seraphis now. mj's proposal to help with OSPEAD failed to raise funds.
isthmus approached me after the January 18, 2022 Monero Research Lab meeting where I said
So like I have said before, OSPEAD will have some blind spots due to lack of C++ support. But the plan is mostly intact. Unless someone else wants to work on the C++ work or mj finds funding another way....With a slow implementation, the estimate will not be as precise. And we will probably not have a good measure of how precise it is.
Under certain regularity conditions, the estimator of the real spend age distribution is guaranteed to get the right answer when the sample size is infinite. (The estimator is consistent). Of course, the number of Monero transactions is not infinite. In situations such as this, it is recommended to use two related statistical procedures:
-
Monte Carlo simulation. You generate a sample with a random number generator. Then you apply your estimator to the sample. Then generate and estimate again many times. Usually 1000+, but 100 may be acceptable if the estimation takes a long time. Then you compare the estimation results to the true values of what you are trying to estimate. You know the true values since you chose them when you generated the random sample. If the estimates are close to the true value, that's good news. If not, you need to increase the sample size (in our case it would be increasing the time window of the sample from weekly to monthly) or adjust the estimator.
-
Bootstrapping. Here the real data is used. You randomly sample from the real data with replacement, run the estimator, and store the results. Like Monte Carlo simulation, you do this 1000+ times. The stored results can tell you the approximate variability of the estimator. It can be used to calculate confidence intervals. If the estimate is precise, great. If not, you need to take the low precision into account when making decisions based on the estimate.
If you have an estimation procedure that is already computationally intensive and then do it 1,000+ times for Monte Carlo simulation and bootstrapping, you are potentially colliding with the limits of feasibility. The estimator is now written in R. R can be fast, but it has known weaknesses in these circumstances:
Sometimes R code just isn’t fast enough....Typical bottlenecks that C++ can address include:
-
Loops that can’t be easily vectorised because subsequent iterations depend on previous ones.
-
Recursive functions, or problems which involve calling functions millions of times. The overhead of calling a function in C++ is much lower than in R.
-
Problems that require advanced data structures and algorithms that R doesn’t provide. Through the standard template library (STL), C++ has efficient implementations of many important data structures, from ordered maps to double-ended queues.
I believe that it will be possible to have one run of the R code for each week of data if this CCS proposal is not funded. Monte Carlo simulation and bootstrapping with the real spend age estimator are probably not possible with R. They are only possible with a compiled language like C++ or Rust.
Having little knowledge of the finite-sample performance of the estimator makes me nervous as a statistician. The phrases that come to mind are "blind spots" and "corner cutting". If isthmus is willing to manage the C++/Rust writing and the community is willing to fund it, then we should definitely do it.
My main concern with this proposal is that Cheyenne Atapour does not have much public C++ code to judge his capability to execute. I am writing a small "test" for Cheyenne to satisfy my concerns about this.
-
isthmus has an extensive body of work / contributions to the Monero project / active MRL member who is undertaking this proposal under the banner of their real company leaving no doubt of 'is this a great proposal' or not. But i must pose these questions with the bigger picture in mind.
A question I've seen asked elsewhere: Does the current existing infrastructure available to the MRL team have any effect on this proposal https://ccs.getmonero.org/proposals/gingeropolous_zenith_storage.html
And another from myself regarding the 100% upfront request. Can you specify the USD amount you require for this work and what buffer you are adding for the time frame you expect to complete the work (i see 5.5 weeks) and point to where your volatility analysis supports this buffer for the time frame. Perhaps an upfront amount less than 100% would make sense? https://github.com/Mitchellpkt/volatility_analysis
Edit* as per the latest transparency report if this proposal is considered fundamental to the Monero project by Core, it may benefit from receiving a contribution to make up for any volatility shortfalls. but before even considering this, you must be forthcoming with your USD rates to complete the work / buffer when you have completed you final investigations.
Edited by plowsoffCould you make a comment on how this could be applied to the input selection algorithm that Seraphis would be using? Maybe @j-berman can also give some comments here about his experience with it?
I can speak to this. The current decoy selection algorithm samples decoys independently, without replacement, from a Gamma(19.28, 1/1.61) distribution as suggested by Moser et al. (2018). The parameters are defined in wallet2 and did not change when ring size increased from 11 to 16 in the August 2022 hard fork. The decoy selection algorithm does not depend on the number of decoys. It just repeats the random sampling until it has enough decoys to satisfy Monero's consensus rules.
The decoy selection algorithm that OSPEAD will suggest also will not depend on the ring size. I believe that the Seraphis code is currently planning to do "binning" by selecting a set of blocks by an algorithm similar to today's algorithm and then including a set of outputs within each of those blocks. (Binning has not been rigorously analyzed for potential advantages and disadvantages for Monero user privacy.) For example, with ring size 128 the algorithm could select 16 blocks by the Moser or OSPEAD probability distribution and then select 8 of the outputs within that block as the actual ring members. The real spend would be one of those ring members, of course. If OSPEAD passes review, its probability distribution would be used in the first step of the binned ring member selection procedure.
Mimicking the real spend age distribution as closely as possible is important regardless of ring size (except if rings were to include all transaction outputs). In the original OSPEAD proposal I wrote:
Increasing the ring size is part of Monero's long-term development roadmap. However, I have produced evidence that the statistical vulnerability would still remain with larger ring sizes. Raising the ring size from 11 to, say, 16 would barely dent the potency of my attack. Raising the ring size to 256 would mitigate the attack to a substantial degree, but user privacy might still be at some risk. In other words, we cannot get ourselves out of this problem by simply raising the ring size.
Hi everybody, thanks so much for the thoughtful comments and questions. I’ve been sharing brief updates on IRC for MRL meetings, and wanted to drop an update here as well.
Rucknium provided a toy function in R with corresponding tests, and Geometry Labs produced (at no cost) a little demo of the workflow for using C++ in an R setting. You can check it out here: https://github.com/geometry-labs/workflow_demo#readme
This week we plan to study the most severe OSPEAD bottlenecks, to sketch out the optimization & parallelization plans with enough detail to (1) put an accurate time estimate on the final scope, and (2) confirm that we have enough engineering time and bandwidth blocked out to execute the project before moving the CCS forward for funding.
If the final plan looks good in terms of scope and timing, I’ll update the proposal accordingly and add another comment. (I’ll also circle back and answer the questions from above comments)
Hello everyone, just a brief update. I've decided to carry out much of this work on my own time, at no cost. To avoid confusion, I'll be closing this CCS for now, but I might reopen it or create a new one if circumstances change. Thank you all again for your valuable input and support :)
What made you make such a surprising decision?
I mean. To have 190 or not have them is quite a difference.
Edited by mjUnfortunately, Geometry just doesn’t have enough Q2 bandwidth to commit to completing the entire project at this time.
I just plan to turn my upcoming hobby time towards helping with data cleaning (by identifying and filtering non-
wallet2
transactions, as described above).Of course that is only a portion of the original planned scope. But I’m hoping that chipping away at my part on the weekends will allow me to make a small but meaningful personal contribution to the OSPEAD effort.
Any updates on Geometry's current workload? @Mitchellpkt