This proposes an extension to FCMPs to make them a drop-in replacement for the exsting CLSAG. In order to be such a replacement, the proof must handle membership (inherent to FCMPs), spend authorization, and linkability.
- FCMP: Full Chain Membership Proof
- GBP: Generalized Bulletproof, a modified Bulletproof supporting Pedersen Vector Commitments in its arithmetic circuit proof. Security proofs are currently being worked on by Cypher Stack.
- GSP: Generalized Schnorr Protocol, a proven protocol for 2009 for proving:
For a m*n matrix
And a n-length row[ [A, B, C], [D, E, F] ]`
The m-length output column:[x, y, z]
is[ T, U, ]
This is useful to prove knowledge of the opening of a vector commitment and consistency between vector commitments.[ xA + yB + zC, xD + yE + zF, ]
- BP+: Bulletproof+. A weighted-inner-product proof currently in use in Monero.
- F-S: Forward secret. An adversary who can solve for the elliptic curve discrete log problem cannot find the spent output.
FCMPs, when instantiated with GBPs, are a O(n)
proof of an O(log m)
program (where m
is the amount of members in the set). The program is a Merkle tree proof, where the same layer program is executed multiple times. The layer program is summarizable as follows:
- Unblind the Pedersen Commitment input.
- Verify the unblinded variable is present in the layer being hashed.
- Hash the layer, outputting a new Pedersen Vector Commitment (blinding the hash for the layer).
For the first layer, under Seraphis, the input would be the re-randomized squashed-enote (effectively a Pedersen Vector Commitment). The "unblinding" would remove the re-randomization and continue.
The final layer would use randomness = 0 such that the output Pedersen Vector Commitment is the tree root (or the protocol would take the difference and require a discrete log PoK, forcing the user ).
The naive solution would be to open K
, the output key, inside the proof, then prove for the key-image inside the proof. This would require hardware wallets perform the FCMP proof, which is extremely undesirable/entirely unacceptable. Accordingly, the goal is for the membership proof to perform re-randomization without knowledge of x
, letting a second proof prove for spend authorization and the key image.
Instead of building a Merkle tree of squashed enotes, we build a Merkle tree with elements (K, hash_to_point(K), C)
where C
is the amount commitment. We output re-randomized versions of all three and then prove the key image correctly formed.
EDIT: These should not be moved forward with. The alternative modifications in the next section achieve much better properties and are the basis of the forward-secret variant posted below. This is only present as it was discussed below and therefore would be confusing to remove entirely.
For the first layer, we don't take in the re-randomized squashed-enote (as this is pre-Seraphis), yet (r K, r**-1 H(K), C + a G)
. We denote this (K', H', C')
.
The first layer does not perform the traditional unblinding (addition of a G
for a known a
) for K', H'
. Instead, it multiplies K
by r
(checking it's equal to K'
) and H'
by r
(checking it's equal to H(K)
). We then perform the traditional unblinding of C'
and check membership of (K, H(K), C)
.
This does not prove the spend is authorized nor that any claimed linking tag is correctly formed. It solely shows that the K', H'
are derived as expected from a member of the tree.
We then extend this with a Discrete Log Equality proof for K', I
over G, H'
. The discrete logarithm of K'
is r x
, which we notate x'
. x' H'
expands to r x r**-1 H(K)
, with the r
terms cancelling out for x H(K)
, the expected key image. This introduces linkability into the proof. By having the DLEq proof's transcript be over the message signed, spend authorization as well.
With newly introduced generators T, U, V
, and ignoring the amount commitment for now:
K' = K + aT
I' = hash_to_point(K) + bU
B = bV
The FCMP would only perform three standard unblinds (the third being C'
, ignored here), and show consistency between the bU
term in I'
with B
. Instead of performing a DLEq proof after, we'd provide a proof of the following.
For matrix:
[
[G, T, 0], // Open K'
[0, 0, V], // Open B
[U, 0, 0], // Create xU as a hint, Z, to prove for bxU without revealing bU
[I', 0, -Z] // x (H(k) + bU) + -bxU = x H(k)
]
The multi-scalar-multiplication by the consistent row of scalars:
[x, a, b]
The output is:
[
K',
B,
Z,
I
]
where Z
is part of the proof data (formed as x U
) and I
is the key image.
This proves linkability, and again performs spend-authorization so long as the message is part of the proof's transcript.
Obviously, implementation must be done correctly, and the proving system (GBPs) must be proven secure. Forging a member requires breaking the Merkle tree OR r, r**-1
consistency (for the original proposal) or bU, bV
consistency (for the current proposal). The original proposal also assumes the trivial r = 0
case is banned, which it already should be by the rule against key images of identity (though we'd still explicitly prevent it).
The privacy of the originally proposed scheme relies on it being infeasible to link K', H'
to K, H(K)
. The most trivial way to solve this is by checking if DH(K, H(K)) == DH(K', H')
, which is presumably reducible to the Decisional Diffie-Hellman. The Decisional Diffie-Hellman game asks if DH(A, B) == C
. One who can check if two Diffie-Hellmans would be equivalent can check if a single Diffie-Hellman is equivalent via DH(A, B) == DH(C, G)
.
The second scheme's privacy is much more clear-cut. Given the commitment bV
, one must calculate bU
, which is the Computational Diffie-Hellman (with the caveat Monero key images are currently considered private under the weaker Decisional Diffie-Hellman problem, so this being stronger is irrelevant).
Not only would this introduce FCMPs to Monero, it would also enable transaction chaining and post-proved membership if we don't bind the membership proof into the secondary proof's (whether DLEq or GSP) transcript.
Seraphis offers more efficient FCMPs, should provide forward privacy, and moves from hacked-together formal properties inherent to RingCT to formalized-from-the-start properties.
Unfortunately, Seraphis has been estimated as 2 to 5 years out by UkoeHB, with inclusion of FCMPs making it closer to 5 years. I disagree with that estimate, yet jberman estimated 3 years themselves. The goal of this is to solve the privacy issues solvable under RingCT, buying time to do better regarding design, performance/scalability, and the unsolvable issues (forward privacy). This may also be of indepedent merit.
I prior estimated Full-Chain Membership Proofs to be 35ms in a batch of 10. This was evaluated over the "pasta curves" with Bulletproofs+. The arithmetic-circuit argument for Bulletproofs, which we are currently using (or rather, Generalized Bulletproofs, a derivative of), should be twice as fast due to the relation to the underlying proof. This would mean ~18ms within a batch of 10.
Generalized Bulletproofs also notably reduces the amount of gates we use in circuit. Prior, we spent several gates entering the divisor into the circuit (a bunch of numbers which had to be entered somehow). Now, with Generalized Bulletproofs, we can simply provide an additional Pedersen Vector Commitment (32 bytes) to enter the divisor. This slashes the size of the circuit.
By adding SA+L, we'll have the additional performance costs within the first layer of:
- Proving for a tri-set membership.
- Doing multiple unblinds.
- Proving consistency of
bH, bG
orr, r**-1
.
I'm expecting this makes the first layer ~3x more expensive.
So from for 1+1+1+1 at 35ms, to 1+1+1+1 at 18ms, to 3+1+1+1 (~31ms). That's ignoring the reduction in gates offered by GBPs.
There are several different tracks along which we can move, and we should move along in parallel.
- Implement GBPs.
This has already been done and solely needs optimizations performed.
- Implement an amenable framework for building arithmetic circuits.
This has technically been done, yet needs some love.
- Implement a library for elliptic curve divisors.
Technically done, yet with an edge case that should be fixed.
- Implement the various gadgets (set membership, index within set, PoK of DLog, proof of DLog).
This was done as needed for FCMPs, not as needed for FCMP+SA+L which has some distinctions (multi-set membership, which is done via getting the index of each item within each set and checking equality, and proof of DLog).
- Implement the FCMP+SA+L circuit.
This was done for FCMPs yet not FCMP+SA+L.
- Implement the secondary proof.
This isn't too notable, with a polished implementation hopefully being within a few days of work for the second case. The first case is prior implemented.
- Implement the necessary towering curves.
This is trivial to do over a generic integer library, yet performance effectively requires a dedicated implementation be done.
- Integrate into Monero.
- Formally prove the soundness, completeness, and zero-knowledge properties of GBPs.
We can do this now. Diego claimed a deliverable, or lack thereof if a failure occurs, could happen in one month.
- Have the divisor-technique reviewed, having been prior published by Eagen.
This is possible now.
- Formally prove the correctness of the "gadgets", as logical.
This is possible with just a formal description of the circuit, and the gadgets contained within. The Curve Trees paper did specify their gadgets, yet we have a notably different construction due to the usage of divisors and the extensions proposed here.
- Formally prove the correctness of the secondary proof.
The first proposal uses a DLEq which has existed since Chaum-Pedersen's 1993 work. The second uses a proof I frequently see referred to as a "Generalized Schnorr Protocol", despite my personal dislike for the ascription. I wouldn't be surprised if it was already proven.
- Audit the implementation of GBPs.
This is possible once the further optimizations are done, and the formal proofs exist.
- Audit the circuit framework.
This is possible once the framework is cleaned to a point we're happy with.
- Audit the EC divisor library.
This is possible as soon as the standing edge case is resolved.
- Audit the implementation of the gadgets.
This should be trivial and possible as soon as the gadgets are formally proven.
- Audit the implementations of the towering curves.
This is possible as soon as the curves are implemented. If we implement them with a constant-time integer library, we'd solely audit that.
-
Audit the circuit.
-
Audit the secondary proof.
This could be audited as soon as it's implemented, which again, should be trivial to implement.
- Audit the integration.
Creation of FCMP+SA+L effectively does all the work necessary for FCMPs with Seraphis with regards to FCMPs themselves. It'd provide the proving system, gadgets, review/audits, and most of the composition work. The only additions would be the curve cycle libraries (if we switched curves), the cross-group DLEq we'd move commitments with, and the new integration (into Seraphis instead of into RingCT).
We'd have to agree on which proposal to move forward with, if we were to move forward.
While the first proposal was the one originally posited, it remains here solely for historic reasons. It appears to perform one less PoK of DLog, making it faster, yet it requires using two private points as generators within Proof of (Knowledge of) DLog statements. Such proofs are much more performant when the generator being used is public.
The second proposal also has the benefit of a much stronger argument for privacy, and uses additive randomness (instead of multiplicative).
We'd then need various implementation work done. I can personally implement the curve libraries using crypto-bigint, yet I cannot implement tailored implementations as likely needed to maintain the performance target. Someone else would need to step up.
I believe I can have all the implementation done, besides integration into Monero, within a few months. The actual integration into Monero would be:
- Having Monero build the tree.
- Having wallet2 call prove via the Rust library.
- Adding RPC routes to get the current tree root and the path of a member of the tree (where the DSA would be used to request multiple paths as to not reveal the output being spent).
- Having monerod call verify via the Rust library.
There'd be no wallet/address/privacy set migration. All of the additional curves would be contained within the proof.
I cannot estimate/guarantee the timeline for the formal analysis side of things. I'd hope by clearly defining components, the rate at which review occurs is not bottlenecked by the rate at which development occurs. That doesn't change we'd have to efficiently manage the timeline and definition of components. I'd hope for, in the best case, development + review/audits of the building blocks in 3-6 months, targeting deployment in ~12 months. Beyond myself, the only development necessary is of dedicated curve implementations (towering curves having already been found by tevador) and the integration into Monero (which jberman already started for FCMPs into Seraphis).
Introduction
FCMP = Full-chain Membership Proofs (efficient signatures that let each input have the anonymity set of the entire chain)
FCMP-RCT = Full-chain Membership + Spend Authorization + Linking proofs on RingCT as described in this proposal.
F-S = Forward Secrecy, usually in reference to DLP solvers not being able to glean any tx information only from on-chain data.
OVK = Outgoing View Keys
To begin, I want to express how impressive @kayabaNerve's work is here that 1) FCMPs on RingCT is possible in the first place, 2) it can be modified to be made forward secret against a quantum adversary, and 3) it can be made to be so efficient. I'm certainly glad that this is an excellent option that exists for Monero development to take. However, this post is mainly against going forward with FCMP-RCT under the following large underlying assumption: For efficiency, security, cryptographic clarity, elliptic curve changes, perfect forward secrecy, or other inherent protocol properties, the network WILL want to migrate to Seraphis at SOME point. If this assumption is NOT true (which could possibly be the case since FCMP-RCT achieves feature parity with Seraphis with F-S added), then you can ignore this entire post altogether.
Quick Summary of Concerns with FCMP-RCT
Seraphis Integration Progress
TODO
Expanding on FCMP-RCT concern points
"Though described as such, FCMP-RCT is NOT a drop-in replacement for CLSAGs from an engineering standpoint, as many non-trivial changes to the database, cryptonote core, tx format, tx construction code, tx validation logic, RPC interface, and wallet logic will have to be made, as well as additional crypto libs, that wouldn't have to be made with a more "typical" ring-like proof."
This can be contrasted to the upgrade from MLSAGs to CLSAGs, which is a true "drop-in" replacement. The upgrade to CLSAGs had all of the exact engineering properties of MLSAGs, we just needed to add in a field to the RingCT signatures, and call a different function for verification if that field was present. This is not the case with FCMPs (in any form, Seraphis or FCMP-RCT), since we must interact with the curve tree when constructing txs, proving txs, or modifying the chainstate. The same can be said about Seraphis if we choose to go for FCMPs on the first iteration, however, Seraphis lets us achieve basically all the features (membership proof delegation, better multisig, OVKs, tx chaining, F-S) without having to integrate FCMPs on the first go. In other words, Seraphis lets us integrate more gradually on the point of FCMPs. FCMP-RCT lets us integrate gradually in respect to F-S.
"Replacing ring signatures with FCMP-RCT will significantly increase technical debt for future protocol handling code and make future Seraphis integration harder."
This point is related to the first point. If we plan to do Seraphis in the future, we will effectively have 4 tx eras instead of a 3, when it comes time to write code that can verify all cases. We would have: Pre-RingCT, RingCT, FCMP-RCT, and Seraphis, with the FCMP-RCT era being the shortest. Since we have to make changes to the tx format, even outside the RingCT signatures, and must keep additional database information, from a codebase standpoint, this makes the entire ruleset for full nodes much more complicated.
""In practice, moving forward with FCMP-RCT will split development time away from Seraphis integration today."
There are not a great number of people who can correctly integrate extensive changes into critical parts of Monero core infrastructure. Some of those people are working on Seraphis integration currently or Seraphis review. In order for FCMP-RCT to get the review work in deserves, this will necessarily slow down Seraphis integration in the current dev environment.
"If FCMP-RCT is enacted, this will increase the dev community's reliance upon wallet2."
The "No Wallet Left Behind" project, in addition to being the place to discuss/iterate Seraphis developments, has also become the room for discussing replacing wallet2, since large swathes of legacy wallet code have been re-written for Seraphis anyways. Only as I've delved deeper into looking at other Monero wallets' design, and wallet libs in other cryptocurrency projects, have I truely began to appreciate how bad wallet2's design is, and how significantly is it likely holding back Monero's adoption on many fronts. There are numerous, numerous efforts by developers in all different languages to create wrappers, or sometimes band new libs, around avoiding having to deal with wallet2. There is a wrapper around wallet2 in the core codebase (which completely changes the API). There are wrappers in different languages which change the API completely. There are ecosystem wrappers in the same language which help you avoid using wallet2. Yet wallet2, and Cryptonote scanning in general, is so complicated that almost all services use wallet2 underneath. Yet wallet2 is not modular, not light-weight, has no real way to meaningfully change transport methods without a re-write of the abstract http client, has few re-usable free functions, has no decent debugging tools, no documentation outside of a few scattered comments, etc, etc. This results in worse Monero services, and less Monero integration into the broader cryptocurrency ecosystem. Certainly, government regulation and blockchain surveillance companies have a large role to play in suppresing Monero adoption, but it's also hard to overstate how annoying it is to develop on Monero as an outsider compared to other currencies. The sooner we move away from wallet2, the faster we can remove technical barriers to adoption. The Seraphis integration project has already began significant work on this (see UkoeHB/monero#23), has a plan to phase out the internals of wallet2, and as such, would destroy an incredible amount of technical debt in the future at the cost of some dev time in the present.
"FCMPs in general are likely overkill for dealing with decoy flooding attacks (FCMPs really shine against EAE, EABE, poisioned dust attacks, etc), so the recent sharp increase in tx count should not cause us to rashly jump to a FCMP solution."
This discussion will need much more space and research than can be covered in this short post, but as I largely understand it, increasing the reference set past a certain point has very quickly diminishing returns when performing a decoy flood attack against the entire network. Let's say that tha attacker can create 50% of the decoys on-chain, the difference between the effective ring size being 64 (128 under Seraphis * 50%) and half of the chain for privacy against non-counterparties is not that much. FCMPs would really change the game in regards to privacy when dealing with malicious counterparties (EAE, EABE, etc). I won't expand on this point much further, since the details could be discussed for days, but we shouldn't let the recent spam attacks push us to FCMPs too quickly at the expense of the future health of the protocol. We shoul move to FCMPs careful and for the right reasons.
This CCS proposal related to this work asks for ~$375,000 worth of funding. AFAIK, that amount of resources has not been allocated towards Seraphis integration. If the stated reason for doing FCMP-RCT is to get FCMPs in before Seraphis, since seraphis integration is taking too long, it makes more sense to instead to allocate those resources directly to make FCMPs on Seraphis happen faster.
Fact: People want FCMPs
Fact: People want Seraphis
Fact: Seraphis integration is taking too long in some people's eyes
Fact: People have the capital and desire to push extensive protcol and infrastructure changes (FCMP-RCT) to happen soon
Conclusion: it would make sense if those resources were allocated to Seraphis integration
"FCMP-RCT has a much larger attack surface than FCMPs on Seraphis, since FCMP-RCT has to additionally prove spend authorization and linking, and as such, it should be noted that there is a greater security concern of a buggy implementation in FCMP-RCT than FCMPs on Seraphis."
FCMPs under Seraphis only have to prove membership, which is the property that the input enote the proof is talking about simply exists on-chain. This proof system must do all the things that a ring signature under RingCT must do: it must prove that one of the pubkeys in the reference set authorized this input, that this input has an amount commitment that corresponds to that input, that this pubkey has not been spend from before by proving it corresponds to a key image, and that the same key image corresponds to the same amount commitment. Seraphis replaces all of these proofs, as well as changing how key images are defined, but we get the nice cryptographic property that the proofs are compartamentalized into proving specific properties. Thus, if we are able to prove the security of the abstract Seraphis protocol, any new changes to the implementation of the Seraphis protocol (FCMPs, new iterations of FCMPs, new composition proofs, etc) don't have to satisfy all of the RingCT security properties at once, and are thus much less likely to have breaking bugs.
"If FCMPs are implemented before Jamtis is implemented, then background syncing will necessarily consume more storage/RAM."
This one is a smaller technical issue, but cryptonote background view-key syncers would have to store every single on-chain key image of every single tx until their spend key is brought back online. Versus today, the background process only has to store the key images of rings whose reference sets contain the index of an owned enote (which today with a ring size of 16 is about ~8x as many enotes as the user owns). This is because current output selection of cryptonote addressing can't tell if a user is involved in a transaction solely based on its enotes. In Jamtis, output selection guarantees at least one view tag must match if the tx constructor is sending funds. That way, we could narrow down the key images needed to store to only those whose in transactions where at least one view tag matches (likely ~1%).
Conclusion
So there's a quick and dirty explanation of why I don't think we should move forwards with FCMP-RCT if we are going to move forwards with Seraphis eventually. However, @kayabaNerve has given us a path to F-S, which would basically give us all the same properties of Seraphis, if less efficiently. FCMP-RCT would give us a quicker path to FCMPs, but would likely take longer to do F-S, if we chose to do it after the first upgrade. Seraphis integration has a head start, but there is likely less total work to do to get to a first FCMP-RCT hard fork. Also, this post is not necessarily a hard "no" for @kayabaNerve's CCS proposal, since apparently ~80% of the R&D work translates nicely to Seraphis FCMPs.