FCMP++ Development
layout: fr
title: Full-Chain Membership Proofs + Spend Authorization + Linkability Development CCS
author: kayabaNerve
date: April 13, 2024
amount: 920 XMR
milestones:
- name: Provide a specification of the circuit and high-level protocol
funds: 80 XMR
done:
status: unfinished
- name: Productionize the crate for the arithmetic circuit proof
funds: 160 XMR
done:
status: unfinished
- name: Productionize the crate for the Elliptic Curve Divisor Library
funds: 80 XMR
done:
status: unfinished
- name: Implement the gadgets
funds: 320 XMR
done:
status: unfinished
- name: Implement the circuit
funds: 200 XMR
done:
status: unfinished
- name: Implement the Generalized Schnorr Protocol
funds: 40 XMR
done:
status: unfinished
- name: Implement multisig for the Generalized Schnorr Protocol
funds: 40 XMR
done:
status: unfinished
payouts:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:This CCS is to develop Full-Chain Membership Proofs (a trustless solution) into Monero under RingCT, replacing the existing CLSAG. This is distinct from prior intents to integrate FCMPs into Monero with Seraphis, and was prior discussed in a MRL meeting with well reception. That same meeting organized the funding of security proofs for Generalized Bulletproofs, a critical component for FCMPs (under both this proposal and Seraphis). This builds upon the work prior done on FCMPs, and does most of the ground work for FCMPs with Seraphis as well.
The exact deliverables will be:
- A document detailing the arithmetic circuit (a 'ZK program') and necessary integration work
- A ready-for-auditing Rust implementation of an amenable (trustless, formally proven, sufficiently performant) arithmetic circuit proof (currently expected to be Generalized Bulletproofs)
- A Rust library for calculating elliptic curve divisors
- The FCMP proof, as necessary for usage with RingCT
- The GSP (Generalized Schnorr Protocol) proof acting as the signature, with multisignature functionality
Milestones
The milestones are unordered, barring the first to provide a specification. The gadgets will be specified as a series of constraints in a non-machine-interpretable manner intended to allow human understanding and review of the flow and composition. With the definition of the proofs (largely modelled as black boxes to the protocol), all of the supporting infrastructure will also be defined as necessary to comprehend the integration into Monero and new privacy protocol created.
"Productionize the crate for the arithmetic circuit proving system" means to develop the arithmetic circuit proof implementation to the point I endorse auditing it. With those audits, the crate would be eligible for usage in production. Any audits of the implementation would only be sane after the proof implemented is formalized, with security proofs. Currently, the proposed proof is GBPs, and security proofs for it are actively being worked on. If they fail to be proven, this milestone is worded in such a way an alternative proof (with acceptable properties, from being trustless to sufficiently performant to building upon sufficiently accepted academia) may also be accepted. If there are no alternative proofs acceptable, this milestone will be considered not possible at this time, and for the purposes of this CCS, 'failed'.
"Productionize the crate for the Elliptic Curve Divisor Library" means to develop the crate for calculation of divisors into a point it can be audited.
"Implement the gadgets" means to implement the prior-specified gadgets, and all supporting code for them, such that they are ready for soundness proofs, formal verification, auditing, and etc.
"Implement the circuit" means to implement the prior-specified circuit, and supporting high-level functions, to the degree described for the gadgets. This will also include an implementation of the towering curve cycle, Helios and Selene, though not one expected to be performant enough for deployment.
"Implement the Generalized Schnorr Protocol" means to implement the Generalized Schnorr Protocol as needed for Monero's usage.
"Implement multisig for the Generalized Schnorr Protocol" means to implement a 2-round multisignature protocol, inspired by FROST, for the aforementioned Generalized Schnorr Protocol. This would have O(n) signing complexity and identifiable aborts.
All of these milestones will be done myself, kayabaNerve. Integration into Monero will be handled externally to this CCS, with jberman stating their intent to submit their own CCS. The steps for integration (regarding new protocol structures and how data such as the tree root will be specified/used when verifying transactions) will be part of the specification from the first milestone.
Audits
!449 (merged) establishes an earmarked fund for paying for audits, as necessary for all of the work produced by this CCS. The justification for this structure is mainly provided within that CCS, and is considered out of scope to this CCS.
Relation to Seraphis
GBPs, the Elliptic Curve Divisor library, the circuit specification (except the first layer), and the gadgets apply to a deployment of FCMPs with Seraphis (making this work largely reusable even if we don't move forward with FCMPs before Seraphis). The only part which wouldn't explicitly is the first layer of the circuit (which is currently expected to be composed of two distinct layers) and potentially the Generalized Schnorr Protocol work (as they are not currently used by Seraphis, yet I have proposed their use within Seraphis).
This work, if extended with the forward-secrecy discussions held and all associated wallet code necessary, would also be feature-complete with Seraphis. This would leave Seraphis, the protocol, a simpler/potentially more performant protocol, not an upgrade to privacy. This CCS, as currently specified, does not intend to detail all of the wallet upgrades which would be necessary (leaving that to future hard forks, keeping the scope of this concise and minimizing the timeline till deployment).
Other Necessary Development
As aforementioned, integration must also be done, and development of a performant implementation of the towering curve cycle. While jberman has spoken up for the former, another party will need to be found for the latter (such as tevador, who found the cycle and has expressed domain expertise). Barring finding another party for the latter, I would have to personally learn how to implement efficient modulo arithmetic and step up (a problem left to the future).
Failure
If the work within this CCS for any reason fails, the funds raised and remaining (held by core, per the rules of the CCS) will roll over into a general MRL research fund to sponsor further research and development, such as proofs for and review of Seraphis. The direction of and process for this new fund will be decided and agreed upon such a roll over occurring by core and discussions within MRL. The idea for this was premised on the idea of hiring researchers, Cypher Stack specifically, on retainer with the MRL having discretion over how those hours were spent. That was discussed at the same meeting as this proposal (proposal as in cryptographic idea, not proposal as in CCS proposal) with sufficiently well reception for me to propose it as the fallback here.
Merge request reports
Activity
All the currently specified milestones are for myself. jberman is also planning a CCS for the integration. The only remaining code milestone is the tower cycle, which I can do a non-performant implementation of. For the optimized one, I will either need to learn how to, or we'd another party to do so (such as tevador, who has shown expertise in this area).
For the left open milestones, the raised fund would be used to complete those milestones once the relevant parties are found. jberman and I have prior reached out to a few auditing companies and would be primarily at the helm of this role.
Per request, what was an R&D CCS is now an R CCS and a D CCS. I have left them on the same PR as they should be merged together. To merge Research without Development leaves nothing to actually audit, and to merge Development without Research creates a large code base to audit without any funds for audits. While we could fallback to individualized audits, it'd face the difficulties described in the Research CCS.
I have also removed the Tower Cycle development milestone so the Research CCS truly is just that. Research.
I'm in favor of holding off on this until jeffro256's feedback is considered.
My main concern was that this entire process seems rushed for such an important (and big peice) of monero's code, and would like to make sure all POVs are taken into account before any execution takes place.
Note that I'm not against FCMP in general.
This CCS is far too vague and unpolished for the amount of money requested, and it is not appropriate to muddy the waters with multiple proposals.
To demonstrate my point, I edited the 'first proposal' down to its actual content and highlighted points of ambiguity:
Introduction
This CCS is to develop Full-Chain Membership Proofs (a trustless solution based on Generalized Bulletproofs) into Monero under RingCT, replacing the existing CLSAG [WHAT A LOFTY AND ABSTRACT GOAL, I HOPE THERE IS A LOT OF BACKGROUND AND DISCUSSION FORTHCOMING...]. This builds upon the work prior done on FCMPs [WHERE? WHAT WORK?], and does most of the ground work for FCMPs with Seraphis as well [WHAT IS 'GROUND WORK'?].
Proposed Work
Development of the proofs and protocols are itemized in the milestones [THESE SHOULD BE IN THE PROPOSAL WITH MORE DETAILS].
[WHERE IS THE DISCUSSION ABOUT A NON-PERFORMANT TOWERING CURVE CYCLE IMPLEMENTATION MENTIONED LATER ON?]
Future Work
- Integration into Monero needs to be handled by Monero devs [WHAT DOES INTEGRATION ENTAIL? THERE IS NO INDICATION OF SCALE, SCOPE, OR STRUCTURE]. jberman has expressed interest in opening a CCS for this.
- Review and audit of [WHAT EXACTLY?] is required, which will require additional funding.
- A production-grade implementation of the Towering Curve Cycle will be necessary, as noted above. tevador may be a good candidate, since he found the cycle and has expressed domain expertise. If necessary I may be able to attempt this.
Funding
[NEEDS COMMENT JUSTIFYING/DETAILING FUNDING]
If this CCS encounters a problem and can't continue, non-dispersed funds will roll over into a general MRL research fund to sponsor further research and development, such as proofs for and review of Seraphis. [WHERE IS THE LINK TO THE MRL MEETING THAT DISCUSSED THIS?]
Edited by koeit is not appropriate to muddy the waters with multiple proposals
I was explicitly asked by Luigi and plowsof to split this proposal into two, as noted in this PR and in a comment on this PR. If your feedback is it should be merged back into one proposal, I'll note that at the next CCS meeting (though please clarify, as I'm not sure that is your current feedback and won't so represent your feedback as such at this time).
For prior work, I can point to both https:/github.com/kayabaNerve/full-chain-membership-proofs/ and https://ccs.getmonero.org/proposals/kayabaNerve-fcmp-retroactive.html. While I hear you on including them in the CCS directly (and would be happy make such edits), I don't believe that context has been missing in the various meetings.
"ground work" is a term for work that is the basis of other work. In this case, the ground work is the implementation of GBPs, the circuit (other than the first layer), and the gadgets (including the work with divisors). I'd be happy to clarify that too.
[WHERE IS THE DISCUSSION ABOUT A NON-PERFORMANT TOWERING CURVE CYCLE IMPLEMENTATION MENTIONED LATER ON?]
I'm unsure what you mean here. I said I would provide one. Since I wasn't billing for it, it wasn't included in any milestone. If you're asking for it to be explicitly associated with a milestone, I'm fine attaching it to "Implement the circuit" (as that's when it'd come up).
On integration, I am not handling that and would not be optimal to detail it. That's why I explicitly delegated it out. At a high-level, it's management of the tree, the relevant FFI bindings, and inputs which use FCMPs.
Review and audit of [WHAT EXACTLY?] is required,
Literally everything produced by this CCS. The second CCS present in this PR, which was originally part of the same PR before I was requested to split it, covers it in a line-item fashion.
[NEEDS COMMENT JUSTIFYING/DETAILING FUNDING]
I would've said the milestones detail what's being funded with line items. The justification for the amount is as simple as it's the amount I requested. I believe it's ~120k USD for ~6 months of work. That's presumably high to prior CCSs, yet it's the amount I requested. If that's amenable to everyone, it is. If it isn't, that can be commented and discussions can be had if it's a sufficiently shared sentiment.
[WHERE IS THE LINK TO THE MRL MEETING THAT DISCUSSED THIS?]
Referring to a MRL fund. That apparently was a slight misquote of mine, sorry, as that's actually a non-trivial issue. The part considered a great idea was CS on retainer by MRL, not MRL outright having a purse to so contract researchers. Rucknium brought it up on April 3rd, https://github.com/monero-project/meta/issues/986, and prior on the first https://libera.monerologs.net/monero-research-lab/20240401 without objections and some commentary in that direction. I'll edit this to more accurately represent this.
I believe most of this is about if this CCS should be a singular near-full-reference point for context, or if it should be a request for funds building upon the general knowledge. I leaned towards the latter, personally believing it was clear the details this was referring to since this PR was opened after a meeting (the one prior linked) explicitly discussing the gist (with far more details) this effectively builds upon. I do see how making it less of the latter and more of the former would be beneficial though and will work on updating this.
@kayabaNerve I'm not really looking for a discussion about it, I'm hoping you'll update the proposal itself with all this missing clarity.
If you want to do two separate proposals, put them in separate merge requests.
Edited by koe
I read through https://gist.github.com/kayabaNerve/0e1f7719e5797c826b87249f21ab6f86, which is kayabanerve's proposal for replacing CLSAG with a FCMP. The membership proof design is at least plausible on the surface (it follows a similar pattern to what we're doing in Seraphis and Lelantus Spark), although I don't know if it can actually be implemented securely with these 'generalized bulletproofs'. The proposed timeline of 1 year to deployment is very optimistic, I'd put it more like 2 years based on the current pace of Monero development and review. Writing proofs is much faster than all the other tasks to bring a new (very complicated and advanced) proof structure onto mainnet. I'm also skeptical about bringing in a Rust dependency, which would be a major shift in the Monero core repo (not to mention bloating binary sizes).
IMO this CCS should not be merged without endorsement from someone qualified to judge its feasibility (e.g. tevador).
for the most endorsing of tevador's comments, though I'll ask them to explicitly comment here. I also still want to add more detail to the CCS proper.
Based on my understanding of the Curve Trees paper, the proposed membership proof should work, with the theoretical soundness depending on the result of the recently funded CCS proposal.
Another possible reason for failure would be if the verification performance turned out to be inadequate for production deployment. Based on kayabaNerve's preliminary results, the performance should be sufficient and there should even be space for improvement with an optimized tower cycle implementation, which I'm hoping to submit my own CCS proposal for.
Overall, I'm in support of merging this proposal, but I have the following comments which should be addressed before merging:
- The "Research" part (proofs and audits) should be submitted as a separate merge request.
- The "Development" part (current merge request) should better specify the final deliverable. I think the output of this CCS should be a formal specification of the protocol and a Rust library with a C-compatible FFI that provides functions to:
- Generate the ownership proof (GSP)
- Generate the membership proof
- Verify the ownership proof
- Verify the membership proof
- Calculate a hash of a group of Merkle tree siblings (needs to be included here because it will call the tower cycle curves, which will not be accessible from Monero)
- The first milestone should be a formal specification of the whole protocol, so we can avoid having the situation of "the code is the specification".
- The proposal does not mention multisig for the GSP. Is this planned for another CCS proposal? I think multisig should be included here because the protocol cannot be deployed without it.
ACK to the two requests for distinct PRs. I disagree but there's enough push back I'll concede.
I'm fine making the circuit specification, and with it the overall protocol design, the first milestone (they're currently unordered, or I at least thought of them as unordered).
I'm also fine adding a milestone for multisig. It should be trivial re: theory for a GSP, and I already have a full Rust multisig library which can do some heavy parts of the role (audited prior by Cypher Stack). The more annoying part will be the FFI around it.
I'll try to update this later tonight or tomorrow. I'm currently bogged down by a distinct issue. Appreciate the feedback :)
Edited by Luke Parkermentioned in commit kayabaNerve/ccs-proposals@351cf4c7
mentioned in merge request !449 (merged)
