FCMP++ Research
layout: fr
title: Full-Chain Membership Proofs + Spend Authorization + Linkability Research CCS
author: kayabaNerve
date: April 13, 2024
amount: 2000 XMR
milestones:
- name: Provide a soundness proof for the proof using Elliptic Curve Divisors
funds: ?
done:
status: unfinished
- name: Formally verify the gadgets
funds: ?
done:
status: unfinished
- name: Prove the composition to be unlinkable, unforgeable, and non-malleable
funds: ?
done:
status: unfinished
- name: Audit the Implementation of GBPs
funds: ?
done:
status: unfinished
- name: Audit the Elliptic Curve Divisors Library
funds: ?
done:
status: unfinished
- name: Audit the implementation of the gadgets
funds: ?
done:
status: unfinished
- name: Audit the implementation of the circuit
funds: ?
done:
status: unfinished
- name: Audit the implementation of the Towering Curve Cycle
funds: ?
done:
status: unfinished
- name: Audit the implementation of the Generalized Schnorr Protocol
funds: ?
done:
status: unfinished
payouts:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:
- date:
amount:This CCS is to prove, review, and audit Full-Chain Membership Proofs (a trustless solution based on Generalized Bulletproofs) 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). The review and audits here would also lay the ground work for FCMPs with Seraphis as well.
All of these milestones have "?" for their required funds. The goal of this CCS is to raise the funds necessary to contract various external parties. All XMR will be held per the usual CCS policy, by core, until the necessary agreements are made for each milestone. The intention of this is to prevent needing to file several CCSs (addng delays) and to minimize the amount of confusion re: funding efforts. I do not want to have to justify to the community, after 5 CCSs for audits, why a 6th one is still justified and FCMPs aren't a black hole of endless fundraises for audits.
Unfortunately, that last note cannot be completely unavoided. Since there are not auditors ready for each and every milestone, this CCS may run out of funds prior to completion of all milestones (requiring another CCS). The amount chosen (2000 XMR, roughly 230k USD) was chosen on the belief it's reasonable for the scope described. Due to the subject matter (ZK proofs and circuits) currently being one of the hottest fields in the cryptocurrency space at large, with both startups and VCs, I'm unable to provide any such guarantee.
With that note, it may sound optimal to do individualized CCSs. That'd not only add weeks/months to the process (as some of these audits are serialized, so a delay in one adds to the delay in the next), it'd risk being unable to contract certain auditors. In my experience, auditors schedule as long as months out from time of agreement. In the time it takes to discuss the proposal and raise the funds, auditors' availability schedules may shift dramatically, including in rates (shifting the amount necessary/adding a deadline for the discussion and fundraising). Hence this proposal.
kayabaNerve and jberman are the people primarily expected to find such parties, with the actual agreement on parties and amount to be by their endorsement, and a general agreement within MRL that the proposed expenditure is reasonable. The word choice of reasonable means that the proposed parties are reasonably trusted to be able to adequately perform the work proposed, the amount to be paid is understandable and amenable, and if there are other potential parties, none are clearly, completely, and definitively better choices.
If the work within this CCS for any reason fails, or completes with a remaining balance, 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 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
mentioned in merge request !448 (merged)
changed title from Migrate Research{- CCS from !448 (merged)-} to FCMP++ Research
What I would like to see with this proposal either in the same timeframe or around the same timeframe as "Prove the composition to be unlinkable, unforgeable, and non-malleable", is to do the same for the forward secret variant proposed in this comment: https://gist.github.com/kayabaNerve/0e1f7719e5797c826b87249f21ab6f86?permalink_comment_id=5016745#gistcomment-5016745. This version of FCMP-RCT is the version to give us feature parity with Seraphis, so if we plan on doing FCMP-RCT, we should know if this version is also secure. Also (maybe not possible), but it would be interesting to see if during your research, you were able to find a scheme with the same first layer for the membership proof, such that in the event of an upgrade, we would only have to switch out the composition proof.
The agreement seems to be to move forward with the forward-secret variant. Accordingly, I'm so fine moving the CCS to the F-S variant. I don't believe any explicit text changes are necessary?
Edited by Luke ParkerAt the risk of stating the obvious, The MRL meetings (including the latest one) combined with feedback received and the swiftness of just and correct modifications from Kayabanerve point to this projects acceptance and the impact it shall have on Moneros timeline. Basically we have the right persons involved and they are acting with good intentions whilst being guided by feedback.
tiny nitpick: Should the author of this be "Monero Research Lab" as this fund is 'theirs' and consensus for things come from them, whereas the development part is yours?
mentioned in commit 22c239a2
This was discussed at the MRL meeting on the 15th, but I would like to post here for visibility and posterity's sake.
Full-chain membership proof review
Cypher Stack
Cypher Stack proposes to conduct a review of a set of proofs for use in a proposed Monero protocol update.
Recent work culminating in a technical note by Luke Parker proposes a Monero protocol update that uses a combination of techniques to enable full-chain membership proofs in a manner compatible with existing outputs. This requires several proofs to show useful properties:
- Membership proofs assert that outputs consumed in a transaction exist from being generated in previous transactions, but without revealing which outputs are consumed
- Spend authorization and linkability proofs assert that consumed outputs have not already been consumed, and that the prover is authorized to do so
- Balance proofs assert that consumed and generated outputs (accounting for any fees) balance in value.
- Range proofs assert that generated output commitments bind to valid values that cannot overflow.
Because the structure of balance and range proofs is well understood, the technical note proposes relations that establish the goals of membership and authorization proofs. It also directly proposes an instantiation for authorization proofs.
Cypher Stack proposes to review membership and authorization proofs as discussed in the technical note. The technical note offloads the structure of membership proofs (for example, to a construction like curve trees). Because of this, we will examine possible requirements for these proofs, with an eye toward properties available from expected instantiations. We will also review the provided instantiation of authorization proofs, and examine the properties of these proofs. Additionally, we will endeavor to examine the extent to which, if any, modifications to the proposed authorization proof may be more efficient. Finally, we will examine the implications of the design on forward secrecy. This encompasses Sections 2, 3, and 5.5 of the technical note.
The engagement will conclude with a report outlining the review and its findings.
The price for this work was agreed on at 198 XMR. This was approved at the meeting, but I would like both @kayabaNerve and jberman to approve via either comment or positive emoji here so relevant payouts can be conducted.
The meeting included my ack and jberman's ack, along with general consensus as necessary to satisfy the oversight detailed in this CCS.
kayabaNerve and jberman are the people primarily expected to find such parties, with the actual agreement on parties and amount to be by their endorsement, and a general agreement within MRL that the proposed expenditure is reasonable. The word choice of reasonable means that the proposed parties are reasonably trusted to be able to adequately perform the work proposed, the amount to be paid is understandable and amenable, and if there are other potential parties, none are clearly, completely, and definitively better choices.
@luigi1111 @binaryFate to donate to MAGIC Grants for the Veridise audit that covers the milestone "Provide a soundness proof for the proof using Elliptic Curve Divisors" (as discussed during the last MRL meeting), please send the equivalent of $10,000 USD (ideally with a small ~0.5-1% buffer please) to:
8BpuwCquJGwDm93kxjeknCRmaQXEW332tQZHCdFgJEmMjj5YneYeqNkj3ibnCvyc4TEhKGthkLt92cUnM9Sgohf3MrdTZJ2On behalf of kayabaNerve I am posting "Soundness Proof for Eagen’s Proof of Sums of Points" by Alp Bassa of Veridise: PDF. It will be discussed at the July 3, 2024 Monero Research Lab meeting.
The prior MRL meeting came to consensus on extending Veridise's hours as needed and contracting Cypher Stack to do review of the above proofs.
Brandon Goodell has submitted a quote for doing review of the GBP security proofs: monero-gbp.pdf
Their estimate is less than Cypher Stack's quote for the Bulletproofs++ review (my closest comparable, though they're not really the same). Since the hours should be budgeting for the worst case, I personally endorse it and want to discuss it at the upcoming MRL meeting.
-
Divisors report:
Cypher Stack put in a bid to review the recent divisors report that the MRL commissioned. We've since delivered our review here: https://github.com/cypherstack/divisor-report/releases/tag/final
The price for this work was approved at 38 XMR.
https://github.com/monero-project/meta/issues/1034 was the meeting deciding that payment. I can confirm the above deliverable.
As a summary of all tasks thus far:
2000 XMR was raised.
Veridise was contracted to write proofs for the divisor technique, producing this. That was initially billed at 10k USD, for which MAGIC received 70 XMR to facilitate.
Veridise also had a brief extension on hours to review the R1CS gadget. That took an additional four hours, billed at an additional 1k USD ($250 an hour). MAGIC has yet to request/receive the XMR to facilitate that.
Cypher Stack was contracted to review the composition producing this. This was billed at 198 XMR.
Cypher Stack was contracted to review the proofs for the divisor technique and produced this. This was billed at 38 XMR.
Within a distinct CCS, Cypher Stack proved Generalized Bulletproofs. Goodell submitted a quote to review these which was agreed to. They did produce a positive review which they apparently have yet to add to this issue and state their final hour tally for (yet I believe it was fairly estimated), placing it ~22k +- 3k.
That places the total amount expended at 306 XMR + 1k + ~25k USD, which I'd consider as 480 XMR in total expenditure.
This still leaves some commentary regarding the divisors (which I'll speak on at today's meeting), review/verification of the rest of the gadgets, and audits.
-
Veridise has completed their second report on negative coefficients and an extended review of the use of logarithmic derivatives, available here: VAR_Monero_Logarithmic_Derivatives_Final.pdf
MAGIC Grants is requesting reimbursement the costs of the prior R1CS gadget extension (the four hours) and this second report. The requested amount is $6,000.
MAGIC Grants currently has a reserved project balance of $151.73. MAGIC Grants will use this balance toward these expenses.
MAGIC Grants will reserve any leftover amount after exchange fees for future expenses.
@luigi1111 @binaryFate the funds can be donated by clicking "Donate to MAGIC Grants" here: https://donate.magicgrants.org/general
Edited by Justin Ehrenhofer Confirming the above request by sgp, which I believe was already paid out, follows due process.
My prior message discussed $1000. The remaining $5000 can be traced as authorized by MRL here: https://libera.monerologs.net/monero-research-lab/20241002#c438657
Apologies for my delay in providing this confirmation.
My GBP security review several weeks late: GBP_Security_Review.pdf Thank you all for your patience, this delay was unacceptable and unintended.
My general results: Overall, GBPs are suitable for use, I think they are secure.
GBPs have a few problems, but the problems are not "new," in the sense that similar problems are considered acceptable elsewhere in Monero's design in particular, and in the cryptocurrency design space more broadly. Also, the problems do not come equipped with known attack vectors. Moreover, doing further research into these possible problems is a general open problem in applied cryptography, so there is not a good reason to delay putting GBPs into prod code.
Most of the problems are strictly superficial problems, like neglecting runtimes and success probabilities, which are useful for assessing practical security levels. Some of the problems are possible theoretical issues related to unwinding which may impact GBPs in the future. However, these would impact usual bulletproofs similarly, which (literature suggests) are thought to be secure. For these reasons, I phrase it this way in the review: if BPs are up to industry standards, then so are GBPs.
Hours: 130 hours (Initial review took 37 hours, detailed analysis took 61 hours, documentation took 32 hours).
Payment rate: 185 USD hourly, totaling 24050 USD.
Payment XMR address: 89hdFGoW4tdTMbreB5mzSN5spUVqhM7SkGyRmbRRNVy9igyfGDjSnX3Sie2exYemy6DEmiDaN9HyP6vdaqddmfCpRhyri8o
Thank you all again for your patience.
Edited by Brandon GoodellThe report provides a solid case demonstrating "if BP is safe, then GBP is safe." It systematically goes through the relation of GBP's to BP's, and the relevant security properties and arguments of knowledge in GBP's (and BP's) to do so. Thus the report gives confidence in GBP's used in FCMP++.
It also provides solid reasoning why long term, Monero research should look to prioritize 1) assessing practical attacks on BP's/GBP's taking tightness gaps into account, and 2) post quantum. Note the latter echoes @kayabaNerve's gist calling for research to prioritize post quantum cryptography (link).
The hours to complete the task were within estimates and the requested amount is what was agreed to prior.
+1 on the deliverable from me.
Thank you @b-g-goodell for your work on this! Glad you're doing work on Monero again :)
This invoice was paid today @b-g-goodell (at time of sending the exchange rate XMR/USD was taken from Kraken)
