Enhancing Key Rotation Security in Mostro with Pedersen Commitments and Zero-Knowledge Proofs (ZKP)

[fabohax]

Statements to Argue the Importance of This Proposal

1. Addressing the Security Flaw

   • The Mostro protocol currently lacks a mechanism to ensure continuity of reputation across key rotations without exposing sensitive information like identity keys (index 0). While offering a "full privacy mode" where the identity key is not sent to Mostro is good, users opting for privacy lose reputation entirely. This dichotomy may discourage privacy-conscious users.
   • This creates a security risk, as stated in the protocol's documentation: "users who want to maintain reputation simply send the identity key to Mostro." This practice compromises anonymity and exposes users to correlation attacks: an attempt to link multiple actions, identities, or data points to the same entity by analyzing patterns or shared attributes, compromising anonymity and privacy.

2. Current JSON Flaw Example

   • From the protocol JSON, the pubkey field in the "seal" is directly tied to the identity key:

     "pubkey": "<index 0 pubkey (identity key)>"

     • Exposing the identity key in this way makes it linkable across multiple orders, violating the principle of unlinkability essential for privacy.

3. Proposal Importance

   • By introducing Pedersen commitments and Zero-Knowledge Proofs (ZKPs), users can prove their reputation continuity without disclosing the identity key. This aligns with privacy-preserving practices, ensuring users maintain their anonymity while proving trustworthiness.

---

Raw Blueprint for the Proposed Solution

Commitment Scheme with Pedersen Commitments

The commitment is defined as:

$$ C = g^{K} \cdot h^{\text{reputation}} \cdot h^{\text{salt}} $$

Where:

• ( g ) and ( h ) are group generators.
• ( K ) is the identity key.
• ( reputation ) is the user's reputation score.
• ( salt ) ensures commitment uniqueness.

Key Rotation with Continuity

When the user rotates their key, the new commitment is:

$$ C' = g^{K_{\text{new}}} \cdot h^{\text{reputation}} \cdot h^{\text{salt}} $$

To prove continuity of reputation, a ZKP must show that:

1. ( C ) and ( C' ) are valid commitments.
2. ( reputation ) and ( salt ) are consistent across both.
3. ( K{new} ) is derived correctly from the user's mnemonic or seed.

Zero-Knowledge Proof Objective

The ZKP verifies:

$$ g^{K} \cdot h^{\text{reputation}} \cdot h^{\text{salt}} = C $$

and:

$$ g^{K_{\text{new}}} \cdot h^{\text{reputation}} \cdot h^{\text{salt}} = C' $$

without revealing ( K ), ( K{new} ), ( reputation ), or ( salt ).

4. Integration into Mostro Protocol

   • Modify the JSON structure to replace direct identity key exposure with a Pedersen commitment and ZKP:

     {
       "id": "<id>",
       "kind": 1059,
       "pubkey": "<Buyer's ephemeral pubkey>",
       "content": {
         "commitment": "<C>",
         "proof": "<zkp_proof>",
         "content": {
           "order": {
             "version": 1,
             "trade_index": 1,
             "action": "take-sell",
             "payload": null
           }
         },
         "tags": []
       },
       "tags": [["p", "<Mostro's pubkey>"]],
       "created_at": 1234567890,
       "sig": "<Buyer's ephemeral pubkey signature>"
     }

5. Benefits of This Approach

   • Privacy: Identity keys are never exposed in raw form.
   • Reputation Continuity: Users can prove their reputation without revealing sensitive details.
   • Unlinkability: Orders cannot be correlated to the same identity key by Mostro or third parties.

Final Argument

This proposal closes a critical security gap by replacing the direct exposure of identity keys with privacy-preserving cryptographic mechanisms. It also aligns with the broader principles of decentralized privacy and trust. Adopting Pedersen commitments and ZKPs ensures a future-proof protocol that protects users while maintaining reputation continuity.

[fabohax]

Do you think it's worth trying to dig deeper into this? Please let me know. Thanks !

[grunch]

Hi @fabohax this is great proposal, I have some doubts, why the reputation is inside the formula? the reputation need to be public because we need to have show it to the counterpart.

Can you explain how can we integrate this proposal with the current gift wrap event, please use a non encrypted gift wrap example like we did here.

I also have other questions:

• Will it be possible to migrate reputation from one identity to another?
• Will it be possible to change from a client to another client on an active order? let's say you created an order on your mobile app, but you have to go out, you are in home now and want to keep using your computer, how can we allow to users do that?
• Produce this commitment is expensive in terms of CPU resources?

Probably the more I understand this the more questions I will have, my first proposal was a chain of signatures, this reminds me a bit my proposal but ZK makes it more elegant.

[fabohax]

Reputation is inside the formula as a tamper-proof binding to the Identity Key and previous Reputation - to expose reputation publicly is also a critical point to discuss if that reputation would be linked to pubkey - that would be traceable and a potential target for correlation attacks. There must be a way to obscure the reputation and just reveal it for specific-purpose. Something like a ZKP to prove that the reputation is the highest between all open trades so it can get listed on a public stack of orders. (Anyways, that requires further thinking)

1. Will it be possible to migrate reputation from one identity to another?
This might be done with a linking ZKP from trader that commits:

$$ C = g^{K} \cdot h^{\text{reputation}} \cdot h^{\text{salt}} $$

$$ C _i= g^{K_i} \cdot h^{\text{reputation}} \cdot h^{\text{salt}} $$

The reputation value and salt must be identical for both commitments and previous reputation will be set to zero.

2. Will it be possible to change from a client to another client on an active order? let's say you created an order on your mobile app, but you have to go out, you are in home now and want to keep using your computer, how can we allow to users do that?

In that case, the mnemonic seed should serve as the root for all derived keys so the user can regenerate their identity key and trade keys on any device by importing the mnemonic. Commitments and ZKPs can be reproduced on a new device without breaking the session.

3. Produce this commitment is expensive in terms of CPU resources?
No much. On circuits using zk-snarks, computation can be done in 500ms easily and verification in a fraction as 10ms. Proof sizes might also round 500 bytes. It would require predefined trusted setup that might weight less than 50MB, because is not so intensive. Anyways, Binius implementation is also under research.

[fabohax]

a gift wrap event might be seen like this:

{
  "id": "<id>",
  "kind": 1059,
  "pubkey": "<Buyer's ephemeral pubkey>",
  "content": {
    // Seal
    "id": "<seal's id>",
    "pubkey": "<identity pubkey>",
    "reputation_proof": {
      "commitment": "<g^K * h^reputation * h^salt>",
      "proof": "<ZKP proving Reputation = 42>"
    },
    "content": {
      // Rumor
      "id": "<rumor's id>",
      "pubkey": "<trade pubkey>",
      "kind": 1,
      "content": [
        {
          "order": {
            "version": 1,
            "id": "abc123",
            "trade_index": 1,
            "action": "take-sell",
            "payload": null
          }
        },
        "<index 1 signature of the sha256 hash of the serialized first element of content>"
      ],
      "created_at": 1691518405,
      "tags": []
    },
    "kind": 13,
    "created_at": 1686840217,
    "tags": [],
    "sig": "<index 0 pubkey (identity key) signature>"
  },
  "tags": [["p", "<Mostro's pubkey>"]],
  "created_at": 1234567890,
  "sig": "<Buyer's ephemeral pubkey signature>"
}

the reputation_proof includes the Commitment and Proof (e.g. =42 )

[fabohax]

ZKP-Based Selective Disclosure for Reputation in Mostro

To balance privacy and verifiability, a Zero-Knowledge Proof (ZKP) can be used to implement selective disclosure of a user's reputation in Mostro. Here's how it works:

---

How It Solves the Problem

1. Reputation Binding:
   • The user's reputation is committed using a Pedersen commitment:

$$ C = g^K \cdot h^{\text{reputation}} \cdot h^{\text{salt}} $$

 - ( K ): Identity key.
 - ( reputation ): The user's score.
 - ( salt ): A PIN value set by user ensuring uniqueness.

2. Selective Disclosure:

   • Instead of revealing the reputation directly, the user provides a ZKP to prove:
     • ( reputation ) matches a specific claimed value (e.g., ( reputation = 42 )).
     • Or, ( reputation ) falls within a specific range or is higher than a stacked group.
   • The ZKP ensures this without exposing ( K ), ( reputation ), or ( salt ).

3. Verification:

   • The verifier (e.g., Mostro or a counterparty) checks the ZKP and commitment ( C ) to confirm the reputation's validity.
   • No sensitive information is disclosed during this process.

---

Benefits of ZKP-Based Selective Disclosure

1. Privacy: The user's reputation score is not publicly revealed unless the user chooses to disclose it.
2. Verifiability: Anyone can verify the claim against the commitment and ZKP without needing additional trust.
3. Security: Reputation integrity is preserved, and sensitive data (like keys or salts) remains private.
4. Flexibility: Users can prove exact values or ranges, enabling nuanced interactions (e.g., reputation comparison).

[arkanoider]

Really really interesting @fabohax ! I am on code refactoring travel with mostrod, but I will take some time to understand better how this magic works!

Can you show ( if you yet have in mind ) a basic example of the messages involved in a voting session? Now we simply let users vote at the end of the trade with a vote between 1 and 5. Let's say Alice and Bob have now a reputation of 4.1 for Alice and 3.8 for Bob they happily trade and the mostro ask them to vote for each other. What comes next? Can you show me a basic example?

Really curious to know more about ZKP, but time is scarce! ;)

[fabohax]

Thank you for the support! Regarding the voting session, I propose you to consider a Binary Rating Scheme. This approach simplifies computations, enhances efficiency, and is straightforward user-friendly. The binary scheme uses a pair ([0, 1]):

• 0: Negative rating.
• 1: Positive rating.

How the Binary Scheme Works

1. Order Rating Flow

1. Trade Completion:

   • Once the trade is completed, both participants (e.g., Alice and Bob) are prompted to rate each other.

2. Rating Submission:

   • Each trader submits a rating commitment ( C ) alongside a Zero-Knowledge Proof (ZKP) verifying the validity of their rating.
   • Example JSON:

     {
       "action": "SubmitRating",
       "order_id": "abc123",
       "from": "<Alice's public key>",
       "to": "<Bob's public key>",
       "rating": 1,
       "commitment": "64108439878827100336420054642254933189834238606611862623819540493761014449685",
       "proof": "<ZKP proving valid rating>",
       "timestamp": "2025-01-16T21:34:00Z"
     }

3. Verification:

   • Mostro verifies the ZKP and commitment to ensure the rating is:
     • Valid ( r in {0, 1} )
     • Correctly tied to the trade and participants.

4. Reputation Update:

   • If the proof and commitment are valid, Mostro updates the reputation score of the rated user.

---

2. JSON Structure for Orders and Ratings

Order Object:

{
  "order_id": "abc123",
  "buyer": "<Alice's public key>",
  "seller": "<Bob's public key>",
  "status": "Completed",
  "buyer_rating": {
    "commitment": "64108439878827100336420054642254933189834238606611862623819540493761014449685",
    "proof": "<ZKP proving valid rating>"
  },
  "seller_rating": {
    "commitment": "32848523890384583924582093845203984520394520348520398452039485039845039485398",
    "proof": "<ZKP proving valid rating>"
  },
  "timestamp": "2025-01-16T21:30:00Z"
}

---

3. Commitment and ZKP for Ratings

Rating Commitment:

Each trader submits a Pedersen commitment for their rating:

$$ C = g^k \cdot h^r \cdot h^s \mod p $$

Where:

• ( k ): Private Key.
• ( r ): Binary rating (0 for negative, 1 for positive).
• ( s ): Salt (a random number to ensure uniqueness).
• ( g, h ): Public group generators.
• ( p ): A large prime modulus.

Zero-Knowledge Proof:

The ZKP ensures:

1. ( r in {0, 1} ): The rating is valid.
2. ( C ) is correctly formed:

$$ C = g^k \cdot h^r \cdot h^s \mod p $$

---

4. Verification and Reputation Update

Verification of Ratings:

1. Mostro verifies the ZKP to ensure:

   • The rating ( r ) is valid.
   • The commitment ( C ) matches the rating.

2. If the ZKP is valid, the rating is accepted.

Reputation Update:

• Each user’s reputation is tracked as:

$$ \text{Reputation} = \frac{\text{Total Positive Votes}}{\text{Total Votes}} $$

Additionally, to prevent attackers from tracking reputation, it is crucial that Rating Submits may be temporary.

[fabohax]

Gonna test a prototype using zk-SNARKs in Rust, for proving, publishing, and verifying. Any details I should take note?