FCMP+SA+L

.md

Full-Chain Membership Proofs + Spend Authorization + Linkability

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.

Terminology

• 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

  [
      [A, B, C],
      [D, E, F]
  ]`
  

  And a n-length row

  [x, y, z]
  

  The m-length output column:

  [
    T,
    U,
  ]
  

  is

  [
    xA + yB + zC,
    xD + yE + zF,
  ]
  

  This is useful to prove knowledge of the opening of a vector commitment and consistency between vector commitments.
• 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.

Recap

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:

1. Unblind the Pedersen Commitment input.
2. Verify the unblinded variable is present in the layer being hashed.
3. 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 ).

Difficulty

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.

Solution

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.

Originally Proposed Modifications for Deployment During RingCT

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.

Proposed Modifications

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.

Integrity

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).

Privacy

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).

Features

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.

Relation to Seraphis

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.

Performance

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:

1. Proving for a tri-set membership.
2. Doing multiple unblinds.
3. Proving consistency of bH, bG or r, 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.

Steps and Timeline

There are several different tracks along which we can move, and we should move along in parallel.

Implementation

1. Implement GBPs.

This has already been done and solely needs optimizations performed.

2. Implement an amenable framework for building arithmetic circuits.

This has technically been done, yet needs some love.

3. Implement a library for elliptic curve divisors.

Technically done, yet with an edge case that should be fixed.

4. 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).

5. Implement the FCMP+SA+L circuit.

This was done for FCMPs yet not FCMP+SA+L.

6. 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.

7. Implement the necessary towering curves.

This is trivial to do over a generic integer library, yet performance effectively requires a dedicated implementation be done.

8. Integrate into Monero.

Formal Security

1. 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.

2. Have the divisor-technique reviewed, having been prior published by Eagen.

This is possible now.

3. 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.

4. 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.

Practical Secrity

1. Audit the implementation of GBPs.

This is possible once the further optimizations are done, and the formal proofs exist.

2. Audit the circuit framework.

This is possible once the framework is cleaned to a point we're happy with.

3. Audit the EC divisor library.

This is possible as soon as the standing edge case is resolved.

4. Audit the implementation of the gadgets.

This should be trivial and possible as soon as the gadgets are formally proven.

5. 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.

6. Audit the circuit.

7. Audit the secondary proof.

This could be audited as soon as it's implemented, which again, should be trivial to implement.

8. Audit the integration.

Contribution to Seraphis

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).

Steps Forward

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:

1. Having Monero build the tree.
2. Having wallet2 call prove via the Rust library.
3. 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).
4. 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).

I personally expected Seraphis to be ready much sooner. If the 3-5 year estimate is correct, then I fully support going this route of implementing a RingCT-compatible version of FCMP if it turns out to be feasible.

What is the transaction size estimate compared to current CLSAG-16? How does the verification time compare to current CLSAG-16?

which is presumably reducible to the Decisional Diffie-Hellman

Here is a proof.

Definitions

Let a "DDH oracle" be an algorithm that takes a quadruple of group elements [G,X,Y,Z] and returns:

1. True if the quadruple has the form of [G,x*G,y*G,x*y*G] for some scalars x, y.
2. False if the quadruple has the form of [G,x*G,y*G,z*G] for some scalars x, y, z.

Let a "FCMP oracle" be an algorithm that takes two tuples of group elements [K,J] and [K',J'] and returns

1. True if K' = r*K and J' = (1/r)*J for some scalar r.
2. False otherwise.

Proof part A: Constructing a FCMP oracle from a DDH oracle

By submitting the quadruple [K,K',J',J] to the DDH oracle, we get a FCMP oracle.

Let j be the scalar such that: J = j*K.

We can easily see that the DDH oracle will return True iif the FCMP oracle would return True because we can define:

G:=K
x:=r
y:=j/r

Then x*y*G = j*K = J.

Proof part B: Constructing a DDH oracle from a FCMP oracle

By submitting the tuples [G,Z] and [X,Y] to the FCMP oracle, we get a DDH oracle.

Let

X = x*G
Y = y*G
Z = z*G

The FCMP oracle will return True iif there is a scalar r such that

X = r*G
Y = (1/r)*Z

We can clearly see that this is the case when z = x*y, we have r = x.

This proposal will be discussed at the Monero Research Lab meeting on Wed 03 April 2024, 17:00 UTC: monero-project/meta#986

I'd estimate ~2.2kB per input at this time, @tevador, and I'd love to have you at the meeting in an hour to further discuss this.

towering curves having already been found by tevador

Here is my latest and probably final tower-cycle proposal:

p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
q = 0x7fffffffffffffffffffffffffffffffbf7f782cb7656b586eb6d2727927c79f
Ep: y^2 = x^3 - 3*x + 15789920373731020205926570676277057129217619222203920395806844808978996083412 
Eq: y^2 = x^3 - 3*x + 50691664119640283727448954162351551669994268339720539671652090628799494505816

This is the first cycle I found that has 2^256 - 2*q < 2^128 (this allows for faster field arithmetic mod q on some architectures) and both curves have a curve constant of a = -3 (this allows for more efficient group law formulas).

As for the actual implementation, I can't promise to help since it reportedly needs to be written in rust, but it should not take a lot of work:

1. Efficient arithmetic in GF(p) can be taken from any Curve25519 open source library.
2. Efficient arithmetic in GF(q) needs to be implemented since this specific prime is unlikely to be used by anyone else.
3. Efficient group law for both Ep and Eq can be taken from any P-256 (secp256r1, NIST curve) open source library because it has the same curve form of y^2 = x^3 - 3*x + b (the three curves differ in the b constant, which is usually not used in group law formulas).

I'm planning to publish a commented script that produces this cycle to show that these are NUMS curves.

To be quite honest, I simply don't have familiarity with implementing big ints and modular arithmetic 😅 I'd be fine implementing the point aspects over the various fields. I'd also be happy to advise on Rust/port some C code (which should be trivial) :)

Looking forward to the script, and thank you, tevador.

This may allow outgoing view keys. Output keys are currently xG where the key image is x hash_to_point(xG). We don't actually check output keys are over G at time of creation though (we do inherently at time of spend right now).

This proposal, under the alternative modifications which make sense to move forward with, outputs a key xG + rZ, for some generator Z, requiring the signer know x and r to create the GSP we use as a signature. The intent was for r to be the randomness used within the circuit. If the re-randomized key was already xG + aZ, it'd be re-blinded by r to xG + (a+r)Z. Then, the GSP would be able to open it with x, (a+r), before proving the key image as x hash_to_point(K) (where K is xG + aZ).

This means that one cannot spend such output keys without knowing the a component, which should allow publishing the x component, which should allow anyone with x to calculate the key images for outputs.

The modified public spend key would be usable in the existing address format, without others being able to distinguish. This means all new addresses could opt into OVKs without segmenting the privacy pool/mandating a new format.

The primary concern I have is the redefinition of key images from dlog_G(K) hash_to_point(K) to term_G(K) hash_to_point(K). That needs to be proven secure under the current proposal regardless, as it does that naturally. If that's insecure, we can make the GSP prove the key is over G by outputting not just K + rZ, yet also K + rY, requiring opening both over G, Z and G, Y with consistent scalars.

My biggest concern with Monero after this is the lack of forward secrecy. With the current Monero, output keys are K = xG, and key images are I = x hash_to_point(K). A quantum computer will be able to solve for the discrete logarithm of K over G, then calculate the would-be key image to detect when its spent.

If output keys are rewritten as xG + rZ after FCMPs are deployed (I am not calling for with), xG cannot be determined to calculate the key image ahead of time (as described above). When given a key image x hash_to_point(K), every single output key would have some r causing it to match.

Accordingly, the key image model can be made forward secret with the above key image re-definition (a side effect of my proposal which I now believe should be made a feature) and wallets eventually re-defining their output keys. The proof would still need to be forward secret though.

The current proposal isn't (again, for the alternate modifications). Providing bG, the hint, enables calculating bH enables calculating the key image generator from the blinded key image generator.

This does force some degree of modification to the above proposal, which I don't want to immediately endorse in the name of scope creep, despite how big of an accomplishment I'd believe this'd be. The circuit changes would be as simple as (for new generators W, X, Y, Z):

K' = K + aW
H' = hash_to_point(K) + bX
D = bY + dZ
C' = C + cG

which I believe there's space for within my current estimates (due to padding causing us to have leftover space).

The issue would be the opening proof. We'd need to remove a x bX term (where x is the private key), and I don't see a way to do that without providing a hint (xX) which isn't forward secret. I believe a more powerful, and more complex, proof would be needed which I don't want to immediately posit nor propose at this time.

This would be a worthwhile future evolution however.

Looking forward to the script, and thank you, tevador.

https://gist.github.com/tevador/4524c2092178df08996487d4e272b096

I updated the b constants of the curves to match the minimality criteria (i.e. the presented curves are the first curves that match the criteria in natural search order).

Note: the script can run for up to a few hours before it outputs our curves (depends on the number of CPU threads).

The modified public spend key would be usable in the existing address format, without others being able to distinguish. This means all new addresses could opt into OVKs without segmenting the privacy pool/mandating a new format.

While the public address format would stay the same, there would have to be significant wallet-side changes. The only feasible way would be to opt in for OVKs at wallet creation time when using the Polyseed mnemonic phrase, which can encode a bit flag "enable_ovk".

Why do we have to opt in at wallet creation time? Because enabling OVKs at any later time could cause the following issues:

1. Inconsistent list of generated addresses. Existing addresses would suddenly change if the wallet was restored with OVKs enabled, if it was previously being used witout OVKs. This could cause major confusion to users.
2. Wallets could miss outputs that were sent to legacy addresses. This could be mitigated by wallets scanning for both versions of each address (with and without the a*Z component).

1. Wallets without OVKs

Legacy wallets and Polyseed wallets with "enable_ovk" set to false would only have two private keys k_v (the private view key) and k_s (the private spend key). Subaddress generation would be unchanged:

m = Hs("SubAddr" || k_v || account_index || subaddress_index_within_account)
Y = k_s*G + m*G
X = k_v*Y
Address = (X,Y)

2. Wallets with OVKs

New wallets with "enable_ovk" set to true would consist of four private keys:

1. k_s, the private spend key
2. k_vs = H(k_s), the private view-spent key
3. k_vr = H(k_vs), the private view-received key
4. s_ga = H(k_vr), the generate-address secret

The fourth key is not related to OVKs, but since we are already changing the private keys, we might as well separate the ability to generate addresses from the ability to view incoming payments, which merchants have been complaining about.

Subaddress generation would work as follows:

m_z = Hs("SubAddr-Z" || s_ga || account_index || subaddress_index_within_account)
m_g = Hs("SubAddr-G" || s_ga || account_index || subaddress_index_within_account)
Y = k_s*Z + m_z*Z + k_vs*G + m_g*G
X = k_vr*Y
Address = (X,Y)

We would get 4 distinct wallet tiers:

Tier	Secret	Public keys	Off-chain capabilities	On-chain capabilities
AddrGen	s_ga	k_s*Z, k_vs*G, k_vr*G, k_vr*Z, k_vr*k_s*Z, k_vr*k_vs*G	generate public addresses	none
ViewReceived	k_vr	k_s*Z, k_vs*G	all	view received
ViewAll	k_vs	k_s*Z	all	view received, view spent
Master	k_s	-	all	all

I guess this would be a "mini-Jamtis".

This does force some degree of modification to the above proposal, which I don't want to immediately endorse in the name of scope creep

I agree. Forward secrecy is already present in Seraphis and this is meant to be an interim solution. I think providing forward secrecy is out of scope of this proposal, especially if it requires a more complex proof or has slower verification time.

As for OVKs, I'm currently in favor of implementing them as a separate wallet type described above (possibly being enabled by default for newly generated wallets). The main reason is that it's only a wallet-side change that's invisible on the outside, so we can't prevent 3rd party wallets from implementing it. In that case, it's better to have official support for compatibility reasons.

Scope creeping (I played with it when I had some spare time, it's an interesting problem), this is amenable to forward secrecy. I'm defining forward secrecy as an adversary being unable to link outputs to the inputs spending them, nor to each other, even when there is a QC available. The QC is assumed to only have the information on-chain.

For new generators T, U, V (redoing notation yet again), with the key image generator labelled I, we'd output:

K' = xG + aT
I' = I + bU
B = bV + cT

This does extend the circuit (we have a new c variable), yet doesn't impact proof size/time due to current padding rules from my initial estimates.

BP+ is inherently a zkPoK for the relationship P = a G_bold + b H_bold + ayb G + r H, where a, G_bold, b, H_bold are vectors and their multiplications are actually inner products (the sum of each pair multiplied). ayb is the inner-product of three vectors, where y is a vector of powers of y. If y[0] = 1, this is not the weighted inner-product yet the standard inner-product relationship.

If we set a = [x], G_bold = [G], b = [b], H_bold = [V], G = U, H = T, y = 1, we'd obtain a proof for P = xG + bV + xbU + rT for some prover-specified x, b, r in two points and three scalars (it's quite close to the existing Schnorr proof as it's not doing a permutation argument over 64 rows in the vectors, and it's not converting the range proof statement to a WIP statement).

In order to ensure the P has the same x, b as K', B, we could open P in a GSP. Instead, we do P - K' - B. For an honest provider, this is (xG + bV + xbU + rT) - (xG - aT) - (bV + cT), or xbU + (r - a - c)T. For a dishonest prover who uses a distinct x/b, they will be left with a remaining G or V term. Accordingly, a prover can prove honesty by opening over U, T alone (without G, V terms).

That would be this following matrix/output column/row of scalars.

[
  [G, T, 0, 0]
  [0, 0, U, T],
  [I', 0, -U, 0],
]
[
  K',
  P',
  L
]
[x, a, xb, r-a-c]

---

This is forward secret per https://gist.github.com/kayabaNerve/e09ba62d4a6165ced006b037f1068d95. That script defines a prime field (insecure to malicious adversaries, of course, but that's not what we're modelling) in order to give us a discrete log oracle (modular inverse by whatever number we define the 'points' as). It creates an honest instance of the proof, then picks a random output J (specifically, a random number acting as the distinct key image generator for a distinct output).

The Python proceeds to use the discrete log oracle to extract various scalar solutions and nonces, before rebuilding all of the nonce commitments. Since it is able to extract all scalars necessary for the proof to be valid, and since the commitments are identical, one with a discrete log oracle cannot differentiate I from J as both yield valid solutions.

This causes the BP+ + GSP composition to output 6 points and 7 scalars (416 bytes), with the FCMP proof outputting 3 points itself (ignoring the linking tag, which is not considered part of the proof). Only the BP+ + GSP composition would have to be done on a hardware wallet, and a more efficient version is presumably possible if one inlines the BP+ and the GSP. This commentary doesn't as it means we'd solely need to argue a composition, not a new proof (however building on prior theory).

---

I'm fine immediately continuing on the non-F-S variant, in order to minimize contention. Despite that, I'm obligated to note:

• The F-S variant achieves parity with Seraphis re: functionality (the non-F-S variant is only lacking in F-S)
• It doesn't require a new anonymity pool
• It doesn't require changing the address format (solely generating new addresses to gain the benefits described)
• It doesn't invalidate old addresses
• It can be rolled out incrementally (initially FCMPs, then F-S FCMPs with the same address protocol yet new generation methods, then a new address scheme if still believed worth it, then new TX versions removing TX extra... all over several HFs, instead of at once)
• The F-S variant would also minimally increase development time

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

1. 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.
2. Replacing ring signatures with FCMP-RCT will significantly increase technical debt for future protocol handling code and make future Seraphis integration harder.
3. In practice, moving forward with FCMP-RCT will split development time away from Seraphis integration today.
4. If FCMP-RCT is enacted, this will increase the dev community's reliance upon wallet2.
5. 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.
6. 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.
7. 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.
8. If FCMPs are implemented before Jamtis is implemented, then background syncing will necessarily consume more storage/RAM.

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.

1. The goal for F-S is for a QC to not be able to learn more. I showed that by demonstrating a DLog solver (a feature available to a QC) can find a solution for any output, therefore the actually spent output isn't differentiable.

2. The benefit of Seraphis is in the design simplicity, which my afford notable performance benefits to the membership proof under the squashed enote model (though that adds additional elements to the aggregate range proofs).

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

I don't agree with the presentation of this. A tree needs to be added to the database, agreed. "cryptonote core" doesn't notably change. It passes the tree root, calls accumulate on the tree, and calls pop on reorg. We would edit the RCT section of the TX, sure. Validation logic only changes in calling FCMP::verify with the tree root instead of CLSAG::verify with the decoy information. We would need new RPC routes and the wallet would have to move from requesting decoy information to path information. Accordingly, all of the above sounds like three notable changes claimed notable across six sections.

The crypto libraries are necessary now and with Seraphis, so I find that note largely irrelevant personally. The only libs which wouldn't be reused are the Helios/Selene if Seraphis adopts a curve cycle.

4. I disagree on the impact of that technical debt, and will take it for the year of privacy discussed at which users would otherwise be vulnerable.

5. Only jberman would split off under current proposals.

6. seraphis-migration/strategy#3 discusses replacing wallet2 and I'm fine leaving all conversations about wallet2 being bad to it.

7. I disagree FCMPs are overkill to anything. We need to evolve past rings. This is the fastest proposal to do so while meeting a trustless setup and performance requirements.

8. Seraphis is welcome to make its own CCS. This CCS does not outlaw Seraphis CCSs. I do not believe Seraphis, even with resources, can accomplish the integration, formal proving, formal review, and auditing necessary before this can as this has a much smaller scope than Seraphis on a fundamental level.

9. FCMPs over RingCT only have larger attack surface than FCMPs with Seraphis because Seraphis takes a giant attack surface, and part of its giant attack surface is the FCMPs + RingCT attack surface. It just shifts the burden. I also don't believe the attack surface is an issue as both this and Seraphis are proposed with extensive review and audits.

10. The proposed increase in storage requirements are minimal. It's just the need for view-only wallets to keep all key images until the spend key filters them, instead of only key images which used a known output as a decoy. That, combined with how the outgoing view key extension would enable view-only wallets to immediately filter...

11. I'd argue this proposal has less, or at worst equal, remaining work than Seraphis does, not just less work in total. This also accomplishes notable milestones several months to year(s) faster.

this route of implementing a RingCT-compatible version of FCMP if it turns out to be feasible.

Do we know when the "if" in this statement can get resolved? From my perspective, this would introduce a key deciding factor. If its known that FCMP-RCT is sound within a matter of weeks, and the deployment (including audits) can occur <1 year, to me it makes sense to push this forward.

From where I sit, seraphis was first introduced primarily to permit an increase in ringsize, with the hopeful development of some non-ring based system that could be dropped in. Concurrently, the seraphis upgrade would usher in a new transaction system that is ultimately better than the one we have from cryptonote.

It turns out that non-ring based system was discovered prior to seraphis implementation. I think this was unexpected.

I know this is a technical thread, but i'll drop some analogies. I feel like monero is currently a plug in hybrid car. It's using the best of the technology that was available at the time to achieve the goals of the manufacturers, which is lower emissions (or something. don't take the analogy all the way). The ideal car in this analogy would be a fully electric car built from the ground up. This is seraphis. However, in this hypothetical scenario, there's a crisis and there's no more gas and people still need cars. Thus, we can produce an electric car thats usable now by dropping in an electric motor, because an engineer just figured out how to do it. Thats FCMP-RCT.

In real life, car manufacturers that attempted this drop in weren't successful, but I'd argue that's because there wasn't a gas supply crisis. Whereas car manufacturers that created pure electric cars from the ground up have done... relatively well.

Which I think brings us to the pertinent question. Is there a crisis that would warrant postponing the ideal product in lieu of something that could work now?

I would argue yes. It's been known that rings are the weakest link in monero's function. before the spam attacks it was known. It was known well before then.

Due to the ongoing debate if FCMPs should be implemented before Seraphis, I reread the Seraphis paper. The main premise of the new key image format that comes with Seraphis was to enable outgoing view keys (OVKs) and to separate the membership proof from the ownership proof.

Since both of these features can be achieved with RingCT-compatible key images, is there a good reason to go forward with the imcompatible key image format?

Most, if not all, new features of Seraphis could be implemented with a RingCT-compatible key format:

1. Membership/ownership proof separation can be done as described in this gist.
2. Jamtis address format also works (with minor changes to the key derivation formulas), including all wallet tiers, encrypted address tags and Janus attack protections.
3. Transaction structure changes are also applicable as they are independent of the key format.

If Seraphis was adapted to use the key formats mentioned here, the pre-Seraphis FCMP implementation would 100% roll over to Seraphis, which would address the concerns some people might have with this endeavor. Additional advantages would be:

1. We could optionally support both old and new address formats at the same time if that was something deemed useful.
2. There would be no need for migration-type transactions that spend old RingCT e-notes and create new Seraphis e-notes. All old e-notes would be part of the anonymity set of all future transactions, which would arguably be better for privacy.
3. We would only have a single pool of spent key images instead of two.

Do we know when the "if" in this statement can get resolved?

If you ignore performance enough, I'd say it's resolved. I initially posited 35ms at Monerokon, which was actually a 100ms variant that did several additional proofs GBPs supersede. If GBPs fall through, we'd fall back to that 100ms metric (with a new item to formally prove). That ignores the several performance benefits we're looking at. BPs, instead of BP+s, inherently should be ~2x faster (35ms -> 17.5ms), and I've come up with more efficient ways of architecting the circuit internally.

I also have high faith in the ability to prove GBPs. I'm expecting a soundness proof for the divisors to be more difficult, yet that'd 'only' double our cost for performing the elliptic curve cryptography in circuit (back to 35ms, if we use BPs and not BP+s).

Ideally, we should have an upper bound on time in around a month, when the current CS work completes.

It turns out that non-ring based system was discovered prior to seraphis implementation.

To be fair, FCMPs with Seraphis was discovered before FCMPs without Seraphis.

postponing the ideal product

necessitates discussion on how far from ideal this is.

---

Most, if not all,

I believe all features of Seraphis are accomplished when the above idea is fully executed (the F-S variant and supporting wallet code).

If Seraphis was adapted to use the key formats mentioned here

If we are to keep the Seraphis code (which I would support), I'd probably endorse deploying this over the existing codebase (with extensions), then deploying the Seraphis code as a new wallet library + new transaction version. I'm obligated to note that makes Seraphis more of a codebase than a protocol, as it is now, yet that also isn't necessarily an issue.

We could optionally support both old and new address formats at the same time

This does cause metadata leakage (wallet age revealed), yet doesn't invalidate old addresses which is great.

---

Distinctly, why wasn't non-RCT outputs migrated into RCT? Can't we set the randomness in a Pedersen Commitment to 0 and make RCT outs out of non-RCT outs? I ask as that'd allow making all historical TX validation code technically still active (due to CN-RCT migration TXs still being allowed, as they should be) solely historical (as new spends of original CN outputs would be treated as RCT outputs which would be a subset of the new global pool). When thinking about removing the Seraphis migration, I had that thought about the old migration.

Distinctly, why wasn't non-RCT outputs migrated into RCT?

Currently, outputs are grouped by their value for the purposes of decoy selection. Ring-CT outputs are counted as having a value of 0. Old denominated outputs and unmixable outputs have transparent amounts, so presumably the real output (and the amount spent) would be leaked with a high probability if such an old output appeared in the ring.

I think that with FCMPs, we could easily treat all outputs from the genesis block as a single group by creating amount commitments for them with a known mask (AFAIK coinbase outputs use a mask value of 1, i.e. C = v*H + G).

I'd be quite interested if it really wasn't done historically due to side-channel attack commentary, I'll note this as yet another idea which can take FCMPs to their 'ultimate' form.

cc @jeffro256 on tech debt (it doesn't remove the verification code, yet would make it explicitly historical) and also @jeffro256 for their own comment on migrating RCT outputs to Seraphis (which I wouldn't see possible without an overtly complicated circuit/having every Seraphis TX also have a RCT input/etc).

necessitates discussion on how far from ideal this is.

from my understanding, a large benefit of seraphis was the modularization of all of the components. (e.g., FCMP could just be dropped into the membership proof component). So I guess one question regarding this FCMP-RCT effort is how upgradable is it? e.g., in 5 years, if something faster and smaller comes out for component x, y, or z, how easy is it to slip into cryptonote-fcmp-rct, vs how easy would it be to slip into seraphis-fcmp?

Or maybe "future-proof" would be the right term.

If Seraphis was adapted to use the key formats mentioned here, the pre-Seraphis FCMP implementation would 100% roll over to Seraphis, which would address the concerns some people might have with this endeavor.

This seems like an ideal option imo.

from my understanding, a large benefit of seraphis was the modularization of all of the components.

This also modularizes the membership and spend-auth/linkability proof. The statements are distinct, as needed to safely satisfy the RingCT design preserved, yet it is modularized. Membership, spend-auth/linkability, balance (currently sum of commitments is zero), and output range could also be independently upgraded.

This seems like an ideal option imo.

I believe that proposal is effectively to move forward with this now, then scrap Seraphis the cryptographic protocol. Seraphis the codebase would then be adapted to satisfy the system created here, argued only fundamentally distinct in the linking tag structure. That is equivalent to the general idea of FCMP+SA+L now + JAMTIS later + new TX formats which are saner later (incrementally upgrading without a hard migration), except the new TX formats would be the already written Seraphis formats re-intented. I just want to be clear about my understanding there.

@tevador When you have a moment, mind chiming in on https://repo.getmonero.org/monero-project/ccs-proposals/-/merge_requests/448?

https://github.com/kayabaNerve/fcmp-/blob/develop/fcmp%2B%2B.pdf is my work in progress formalization of this, with background. The circuit is detailed yet I wouldn't claim specified yet. It also covers how integration would be handled.

cc @tevador especially (who I don't believe I can reach on Matrix 😅 ), when you have the time.

https://github.com/kayabaNerve/fcmp-ringct/blob/develop/fcmp%2B%2B.pdf should now be at the feedback phase, where the only expected changes are for clarity/detail where not enough detail was provided (such as on the integration side of things). Barring evolution with research (see DLog PoK which I played safe here, yet do posit a more efficient candidate for), only minor tweaks should occur.

I reviewed the PDF, version d946868.

• 4.3 First bullet point should probably say "Hadamard product" instead of "vector multiplication" to avoid ambiguity.
• 4.3.8 The section is missing a sentence explaining that permissible points are those where U(y) is a square and U(-y) is non-square. I'd also add that 1/4 of points are permissible.
• 5.4, 6.8.1 You could add a reference to Jamtis-RCT, which is a compatible addressing scheme supporting outgoing view keys.
• 6.8.2 Outgoing view keys are not a requirement for forward secrecy. It's sufficient to add a T-component to the one-time address when constructing an e-note.

Regarding section 6.4, where you propose to require output keys and commitments to be permissible, I've been thinking about it and it should be possible by adding two encrypted 1-byte fields to every e-note, which will contain the number of times the constructed value needs to be incremented to be equal to the published key, i.e. K_o = K_o' + i_1 T and C = C' + i_2 G, where K_o' and C' are the values derived from the sender-recipient shared secret. The integers i_1 and i_2 are in the range of 0-255, which gives a negligible chance of failure to find a permissible point (less than 1.4x10^-32).

1. ACK.
2. I don't spell out the square commentary, yet did comment permissible(Y) && !pemissible(Y). I'll elaborate.
3. ACK as a cite under future expansion :) Thanks for putting that together. I have yet to review it, unfortunately.
4. Agreed they're not technically required, yet the addition of the T term is what simultaneously creates the outgoing view key and offers forward secrecy. I'll rewrite it so its clearer than outgoing view keys, which is a bunch of wallet protocol changes, isn't implied as required.
5. I don't require outputs be permissible. I require they be made permissible before being added to the tree. It's a few additions by the node (1.5 on average?), so it shouldn't notably impact performance, and prevents requiring changes to the scanning process. We can also publish such values, yet I believe post-incrementing is the simpler solution. The only argument against the node doing it is if one posits a pit of non-permissible values (say, thousands of them in a row) which forms an effective DoS.

Distinctly, even without an extra item, could we not force wallets to resample randomness until permissibility happens to be achieved? That'd not increase bandwidth (negligible) nor change the scanning protocol (which is a bit annoying, and likely requires a table or 1-byte double-and-add to be properly performant?).

the addition of the T term is what simultaneously creates the outgoing view key and offers forward secrecy

Not necessarily. If the T term is derived from the shared secret, it's not safe to use the G term as the OVK. However, the resulting ouput key is forward-secret nonetheless.

It's a few additions by the node (1.5 on average?)

Actually, it's on average 4 point additions and 8 Legendre symbol calculations.

The only argument against the node doing it is if one posits a pit of non-permissible values (say, thousands of them in a row) which forms an effective DoS.

Not thousands, but it's quite easy to find keys that will take 80+ point additions, so it can be considered to be a DoS vector. We can go with it for the initial FCMP rollout, but I'd like to add permissible keys and commitments to the Jamtis-RCT specs. That would reduce the verifier workload to just 2 Legendre symbol calculations per key.

could we not force wallets to resample randomness until permissibility happens to be achieved

The chance that a random key is permissible is 1/4. Two-output transactions only have one public key and a total of 4 keys derived from it. That means you would need, on average, 256 attempts (=4⁴) to make a valid 2-output transaction. Impractical.

likely requires a table or 1-byte double-and-add to be properly performant

You can have a precomputed table of 256 multiples of T and G, which would only take 32 KB. Then you'd only need one table lookup and one point addition to recompute the permissible key. In any case, thanks to view tags, this would only happen for a small fraction of e-notes, so the precomputed tables are probably not even worth it.

Fair. I always presumed deployment via the public spend key as that's indistinguishable, with no changes to scanning/sending. Apologies for being so imprecise.

If 1/4 points are permissible, I would've assumed we'd reach a permissible point in 1.5 additions (as the current one can be checked without any additions). The average distance to an permissible point being 4, not 2, when they're presumably even spaced by 4 sounds off. I haven't wrote the code to literally show however. Agreed there's overhead for the check itself.

80+ point additions definitely isn't great. It's still less work than a scalar multiplication though. In that case, I'd go back to recommending resampling randomness yet that only can be discussed when each output has an independent randomness which isn't currently the case. If we're shifting send/scan changes to a future fork, would not that future fork presumably use independent randomness per outputs? I'd have to re-read on how Seraphis + JAMTIS proposed handling change outputs. If the extra byte is the best solution, along with a table or one-byte double-and-add in the scan code (which I never meant to suggest impractical, solely an annoyance like all three of these paths have), ACK.

Re: torsion (6.2.1 and 6.4): What can happen if we allow keys with a torsion component to be added to the tree? I can't think of any exploit as long as the SA+L proof is handled correctly.

I can't think of any. I just no longer care to ask the question and argue security despite the question. It's not worth the mental effort and the potentially surprising results. I'm still frustrated I still have to consider some aspects re: torsion which are fundamentally not removable. This just really isn't the place to fuck around, find out.

The requirement of torsion clearing historical points is adding a non-negligible amount of work however, which I will concede. To go in depth, the divisor-based DLog proof shouldn't pass for torsioned elements. No sum of elements without torsion will add with a torsioned element to the identity element, which is what the divisor is supposed to check. That means the worst you get is torsion in, torsion out, on the output key and commitment.

We already argue spending torsioned input commitments is fine. You can torsion them on-chain, and we verify them as prime order elements (emphasis on as prime order elements, not that they are prime order elements), but at time of spend they'll be torsioned. For a torsioned binomial output key x'G + aT, where ' denotes torsion, we'd have to argue it's fine.

I'm not sure that is? I proposed a Bulletproof+ for the F-S SA+L. While we can argue if it's actually a BP+ or not (as it's solely the one-round protocol), that doesn't change we currently ensure all elements passed to a BP+ are without torsion via torsion clears. This would not have its torsion cleared and would be explicitly torsioned. We'd have to inv eight, eight (currently proposed for outputs, now done for inputs) or so increase the tolerances of our policy re: BP+.

I'd rather be done with it, and if we're concerned about performance (just over one additional scalar multiplication), implement Pornin's halving method which I believe is just 30% the cost.