Inversion-style key images and aggregation (multisig)

[UkoeHB]

Triptych, a next-generation transaction protocol under consideration for Monero, uses a style of key images different from Monero's current key images (also RingCT3.0 and one version of Omniring). This poses some challenges for multisig-based transactions, where key images must be constructed by collaboration between cosigners. Other details related to multisig are not discussed here.

Note: To transition from current bLSAG-style key images to inversion-style key images, the question of verifying double spends comes up, since double spends are identified when the same key image appears. The simple solution is that post-hardfork all new outputs can only be spent with TriptychType1 transactions (that use Triptych to sign them), while all old (pre-Triptych) outputs can only be spent with RingCT transactions (signing with MLSAG, or CLSAG). This way key images are clearly related to subsets of outputs, with no risk of cross-over. Note that in practice it means ring membership is constrained.

Key images; before and after

Using the hash-to-point function H_p(), and one-time address K^o (with private key k^o), our current key images are made like this
KI = k^o*H_p(K^o)

In Triptych (and others), key images are made like this, where U is an elliptic curve generator (not the normal one G), e.g. U = H_p("U") (or something similar)
KI^{inv} = (1/k^o)*U

Current multisig, where multiple participants, indexed e, own components of the group's private key (e.g. k^{o,grp} = k^o_1 + k^o_2 + ...) reconstruct the key image as a simple sum
KI = \sum k^o_e*H_p(K^{o,grp})

Clearly that won't work with Triptych key images, which contain an inversion of the private key. Thankfully, Paillier encryption, which I won't pretend to understand, provides a route to constructing aggregate inversions without compromising any participant's share of the full private key (see Gennaro and Goldfeder's original paper, especially Section 3).

Inversion-style aggregate key images for multisig

The method explained here was first explored for Monero by @SarangNoether. My objective is to document the process (also documented by sarang here), and also recommend some optimizations regarding message rounds.

An aside: Paillier encryption

First it will be helpful to lay out Paillier encryption, which is very RSA-esque.

1. A person has a public key N = p*q, where p and q are prime numbers. The private key is phi = (p-1)*(q-1) mod N^2.
2. Encrypt a message m using a randomly generated scalar r with E(m) = [(1+N)^m * r^N] mod N^2.
3. Decrypt with m = [[E(m)^(phi) mod N^2 - 1]/N * (1/phi mod N)] mod N. Note that r 'disappears' during decryption, and so only the encrypter needs to know it.

The process

There are many participants, indexed e, with components k_e of a group key k^{grp}, where the aggregate public key is K^{grp} = (\sum k_e)*G, who wish to construct the inversion-style key image KI^{inv} = (1/k^{grp})*U. In each round participants will perform some computations then send information to other participants, and the next round doesn't begin until the previous round is done.

0. Each participant must learn the other participants' Paillier public keys N_e.
1. Each participant e
   a) privately generates a random scalar gamma_e, computes gamma_e*U, and generates a Schnorr signature sigma_e proving knowledge of gamma_e in gamma_e*U
   b) privately generates a commitment mask x_e, and computes the commitment C_e = H_p("MPC gamma commit", gamma_e*U, x_e)
   c) privately, for each other participant i, generate a random scalar beta_e_i
   d) privately encrypts their private key with their Paillier public key N_e,E_e = E_e(k_e)
   e) sends C_e and E_e to the other participants
2. Each participant e
   a) privately computes, for each other participant i (using the value beta_e_i generated for them earlier),
   c_e_i = [E_i(x)^gamma_e mod N_i^2]*E_i(-beta_e_i) mod N_i^2
   b) sends c_e_i to participant i
3. Each participant e
   a. privately computes, using the values c_e_i received from other participants, alpha_e_i = decrypt(c_e_i, N_e) for each of those participants; this is where the Paillier encryption magic shows its face (although exactly how, I couldn't say)
   b. privately computes local_delta_e = k_e*gamma_e + \sum_i alpha_e_i + \sum_i beta_e_i
   c. sends gamma_e*U (the value committed to in C_e) and x_e, sigma_e, and local_delta_e to the other participants
4. Each participant e
   a. privately verifies for each other participant i, that C_i ?= H_p("MPC gamma commit", gamma_i*U, x_i)
   b. privately computes the full key image
   KI^{inv} = (\sum_e local_delta_e)^(-1)*(\sum gamma_e*U)

Seamless escrowed multisig

For a 2-of-3 escrowed marketplace, with buyer, vendor, and moderator, it is important to minimize the number of communication rounds. Escrowed markets with the current Monero transaction protocol can do collaborative transaction signing in the following steps (A is the buyer, B is the vendor). Please see Zero to Monero: Second Edition, chapter 10. There is a controversial optimization, namely single-commitment signing, which I won't get into here, but is a big part of the system I designed (and also part of this key image process).

0. Buyer (A) encounters vendor's (B's) shop. A collects some information found at the shop, which may be useful for an escrowed purchase.
1. A: initiates transaction (message sent to B)
2. B: creates partial transaction (message sent to A)
3. A: partially signs transaction (message sent to B)
4. B: finishes signing transaction (submits tx to nextwork)

Thankfully, making inversion-style key images can fit into that framework without disrupting the existing pattern.

0. A: collects N_B, and E_B, which were pre-computed/prepared by B. B's private key component is the shared secret between buyer-moderator, while A's private key component will be the sum of buyer-vendor and buyer-moderator key components and the part related to the sender-receiver shared secret based on the view key for a given one-time address owned by the multisig group (for efficiency, even though the buyer will also know the buyer-vendor key component and view key component).
1. A: [privately] generates gamma_A, computes gamma_A*U, generates x_A, generates beta_A_B; [stuff to send] computes E_A, c_B_A, C_A, and prepares Paillier key N_A
2. B: [privately] computes alpha_B_A, generates beta_B_A; [stuff to send] computes c_A_B, local_delta_B, gamma_B*U, sigma_B. He does not create a commitment for gamma_B*U (I don't know if this is a legitimate simplification).
3. A: [privately] computes alpha_A_B, KI^{inv}; [stuff to send] gamma_A*U, x_A, creates sigma_A, computes local_delta_A
4. B: [privately] verifies C_A, and computes KI^{inv}

Crucially, A learns K^{inv} in step 3 when she needs to make her partial signature, and likewise B learns it in step 4 when he finishes the signature.

[UkoeHB]

After a multisig group key image has been created, it is useful to also prove it is a legitimate key so other cosigners can learn it without needing to go through the whole process again. The most straightforward way, which any M cosigners (for M-of-N multisig) can do together, is a multibase Schnorr signature on base keys (G, KI^{inv}), and public keys (K^(grp), U) (see zero to monero 2 chapter 8 and section 9.5).