KeyPack grin-wallet enhancement, please take a look

[ebkme]

KeyPack: A Transaction Protocol for Grin

Wallet-Layer Enhancement for MimbleWimble Transactions with Advanced Privacy Through Transaction Unlinking

Abstract

This paper presents KeyPack, a wallet-layer protocol that enhances Grin’s transaction model without modifying the underlying MimbleWimble protocol. The proposed method splits transactions into two atomic parts while maintaining security through encrypted keys, creating unlinked transactions that improve privacy by breaking transaction graph analysis. The protocol reduces the standard three-step interactive process to a single step, enables offline receiving, and enhances MimbleWimble privacy properties through transaction unlinking. The approach creates distinct, temporally separated transactions that appear unrelated on the blockchain, making transaction graph analysis substantially more difficult. The paper provides comprehensive mathematical proofs of security, enhanced privacy preservation through unlinking, and proper fee handling.

Table of Contents

1. [Introduction]
2. [Background]
3. [The KeyPack Protocol]
4. [Security Analysis]
5. [Privacy Considerations]
6. [Fee Handling]
7. [Compression Techniques]
8. [Edge Cases and Mitigations]
9. [Conclusions]

1. Introduction

1.1 Problem Statement

Grin’s current transaction model presents several significant challenges:

1. Complex Transaction Flow: The current three-step interactive process requires:

   Sender (slate_v1) → Receiver (slate_v2) → Sender (slate_v3)
   

   This necessitates simultaneous online presence and creates high coordination complexity.

2. Payment Proof Limitations: While supported, current payment proofs suffer from:

   • Complex exchange processes
   • Non-standardized implementation
   • Integration difficulties

3. User Experience Barriers: Current implementation creates friction through:

   • Unfamiliar transaction models
   • High cognitive load
   • Poor mobile experience

1.2 Key Innovations

KeyPack protocol provides:

• Enhanced privacy through transaction unlinking, making transaction graph analysis more difficult
• Temporally separated, seemingly unrelated transactions that mask transaction flow
• Reduced transaction steps with maintained security
• Integrated robust payment proofs
• Enhanced MimbleWimble privacy properties
• No consensus changes required

The protocol’s primary innovation lies in creating two distinct, apparently unrelated transactions on the blockchain. This unlinking property improves privacy by:

1. Breaking direct transaction graph connections
2. Creating temporal separation between transaction components
3. Increasing difficulty of correlation attacks
4. Preventing formation of clear transaction patterns
5. Masking sender-receiver relationships

2. Background

2.1 MimbleWimble Fundamentals

MimbleWimble transactions use Pedersen Commitments:

• C(r, v) = r·H + v·G
  where:
  • r is the blinding factor
  • v is the value
  • H, G are generator points
  • · denotes scalar multiplication

2.2 Standard Grin Transaction Structure

A typical Grin transaction consists of:

1. Inputs: C(r_in, v) = r_in·H + v·G
2. Outputs: C(r_out, v) = r_out·H + v·G
3. Kernel: K = (r_in - r_out)·H
4. Kernel Signature: s = k + e*r where:
   • k is the nonce
   • e is the challenge
   • r is the kernel excess (r_in - r_out)

3. The KeyPack Protocol

3.1 Core Concept

KeyPack decomposes a standard Grin transaction into two cryptographically linked but temporally separated transactions. This decomposition maintains atomic operation through encrypted key management while breaking transaction graph linkability.

3.1.1 Transaction Decomposition

Standard Grin transaction A → B is decomposed into:

TX1: A → T (Temporary output with encrypted key for B)
TX2: T → B (Automatic execution when B receives key)

3.1.2 Detailed Transaction Structure

First Transaction (A → T):

Components:
1. Input:
   - C(r_a, v) = r_a·H + v·G
   - Commitment from A's UTXO set
   - Standard Pedersen commitment

2. Temporary Output:
   - C(r_t, v) = r_t·H + v·G
   - r_t is encrypted for B
   - Uses temporary blinding factor

3. Kernel K1:
   - K1 = (r_a - r_t)·H
   - Standard kernel excess
   - Includes encrypted payload

4. Transaction Data:
   - Encrypted r_t for B
   - Payment proof components
   - Version information
   - Metadata (timestamp, network)

Second Transaction (T → B):

Components:
1. Input:
   - C(r_t, v) = r_t·H + v·G
   - Uses decrypted r_t
   - Spends temporary output

2. Final Output:
   - C(r_b, v-f) = r_b·H + (v-f)·G
   - B's receiving address
   - Includes fee deduction

3. Kernel K2:
   - K2 = (r_t - r_b)·H + f·G
   - Commits to transaction fee
   - Links to payment proof

4. Transaction Data:
   - Complete payment proof
   - Fee commitment
   - Standard metadata

3.1.10 Non-repudiation and Dispute Prevention

KeyPack’s encrypted mode provides cryptographic proof of transaction intent and execution, preventing disputes about coin transmission.

Cryptographic Evidence Chain:

1. Sender Proof Generation:
   - Transaction kernel K1 signed by sender
   - Encrypted r_t bound to recipient's key
   - Payment proof σ₁ with amount commitment
   - Timestamped blockchain record

2. Recipient Validation Chain:
   recipient_access = ECDH(recipient_priv, sender_pub)
   if decrypt(r_t, recipient_access) succeeds:
     - Proves sender intended recipient
     - Proves correct amount
     - Proves sender authorization
     - Provides temporal proof

Dispute Resolution Properties:

1. Sender Cannot Deny:
   - Kernel signature proves sending intent
   - Encrypted key proves intended recipient
   - Blockchain timestamp proves timing
   - Amount commitment proves value

2. Recipient Cannot Deny:
   - Key decryption proves receipt ability
   - Second transaction proves access
   - Blockchain records prove timing
   - Kernel linkage proves completeness

3. Third Party Verification:
   - All proofs publicly verifiable
   - Temporal sequence confirmed
   - Amount commitments validated
   - Cryptographic linkage verified

Protocol Evidence Trail:

Evidence Components:
1. First Transaction:
   - Kernel commitment K1
   - Sender signature σ₁
   - Encrypted key data
   - Amount commitment
   
2. Recipient Access:
   - Successful key decryption
   - Second transaction K2
   - Linked payment proof
   - Blockchain inclusion

Dispute Prevention Mechanisms:

1. Transaction Intent:
   if (verify_kernel_signature(K1, sender_pub) &&
       verify_key_encryption(r_t, recipient_pub)) {
     // Proves sender intended this recipient
     // Proves specific amount
     UNDENIABLE_INTENT = true
   }

2. Receipt Capability:
   if (decrypt_temp_key(r_t, recipient_priv) &&
       verify_second_tx(K2, r_t)) {
     // Proves recipient could access funds
     // Proves transaction completion
     UNDENIABLE_RECEIPT = true
   }

Comparison with Unencrypted Mode:

Encrypted Mode:
1. Proof Properties:
   - Recipient-specific intent provable
   - Access capability provable
   - Temporal sequence verifiable
   - Complete evidence chain

2. Dispute Resolution:
   - Clear responsibility assignment
   - Cryptographic evidence
   - Third-party verifiable
   - Temporal proof available

Unencrypted Mode:
1. Proof Properties:
   - General sending intent only
   - No specific recipient binding
   - Temporal sequence only
   - Incomplete evidence chain

2. Dispute Scenarios:
   - Recipient uncertainty
   - Intent ambiguity
   - Claim race conditions
   - Limited evidence

Forensic Analysis Capabilities:

1. Transaction Validation:
   verify_complete_transaction(tx_data):
     kernel1 = verify_first_transaction()
     key_encryption = verify_recipient_binding()
     kernel2 = verify_second_transaction()
     return {
       sender_intent: kernel1.valid,
       recipient_bound: key_encryption.valid,
       completion_proof: kernel2.valid,
       temporal_proof: blockchain_timestamps
     }

2. Evidence Collection:
   collect_dispute_evidence(tx_id):
     return {
       sender_proofs: {
         kernel_signature: K1.signature,
         encrypted_key: r_t_encrypted,
         payment_proof: σ₁,
         blockchain_record: block_data
       },
       recipient_proofs: {
         key_decryption: decrypt_proof,
         second_tx: K2,
         temporal_data: timestamps
       }
     }

This cryptographic evidence chain makes encrypted mode particularly suitable for:

• Commercial transactions requiring proof
• Exchange integrations needing audit
• Regulated environments
• Dispute-prone scenarios
• High-value transfers

The undeniable cryptographic proof of sending intent to a specific recipient, combined with proof of recipient access capability, creates a complete evidence chain that prevents disputes about whether coins were actually sent and to whom.

In contrast, unencrypted mode lacks these dispute resolution properties as it cannot prove specific recipient intent, making it unsuitable for scenarios where transaction non-repudiation is required.

Implementation Differences:

Encrypted Mode:
1. Key Distribution:
   encrypted_r_t = ChaCha20Poly1305(
     encryption_key,
     r_t,
     associated_data
   )
   
2. Access Control:
   - Only intended recipient can decrypt
   - Transaction bound to recipient
   - Failed attempts traceable

Unencrypted Mode:
1. Key Distribution:
   clear_r_t = r_t  // Direct publication
   
2. Access Control:
   - Any party can use r_t
   - First-to-claim model
   - Racing condition possible

Use Case Analysis:

Encrypted Mode Optimal For:
1. Direct payments
2. Exchange transactions
3. Guaranteed delivery
4. Privacy-critical transfers
5. Known recipient scenarios

Unencrypted Mode Enables:
1. Atomic swaps
2. Payment channels
3. Lightning-style networks
4. Prize/reward distributions
5. First-to-claim games

Security Implications:

Encrypted Mode:
1. Privacy Properties:
   - Recipient privacy preserved
   - Transaction graph obscured
   - Full unlinkability maintained

2. Security Guarantees:
   - Guaranteed recipient
   - No front-running possible
   - Replay protection built-in

Unencrypted Mode:
1. Privacy Properties:
   - Recipient privacy optional
   - Transaction graph partially visible
   - Conditional unlinkability

2. Security Considerations:
   - Front-running possible
   - Race conditions exist
   - Requires additional protections

Protocol Modifications:

Transaction Header:
struct KeyPackHeader {
    version: u8,
    flags: u8,
    encryption_mode: EncryptionMode,
    ...
}

enum EncryptionMode {
    Encrypted {
        recipient_pubkey: PublicKey,
        encrypted_key: Vec<u8>
    },
    Unencrypted {
        clear_key: Vec<u8>
    }
}

Mode Selection Logic:

fn determine_encryption_mode(
    transaction_type: TransactionType,
    recipient_known: bool,
    privacy_level: PrivacyLevel
) -> EncryptionMode {
    match (transaction_type, recipient_known, privacy_level) {
        // Standard payment to known recipient
        (TransactionType::Direct, true, _) => 
            EncryptionMode::Encrypted,
            
        // Atomic swap or similar
        (TransactionType::Swap, _, _) => 
            EncryptionMode::Unencrypted,
            
        // High privacy requirement
        (_, _, PrivacyLevel::Maximum) => 
            EncryptionMode::Encrypted,
            
        // Default to encrypted for safety
        _ => EncryptionMode::Encrypted
    }
}

Usage Considerations:

1. Default Behavior:

   - Encrypted mode default
   - Explicit opt-out required
   - Warning for unencrypted use
   

2. Security Recommendations:

   - Use encrypted mode for direct payments
   - Unencrypted only with additional protections
   - Consider privacy implications
   

3. Implementation Requirements:

   Encrypted Mode:
   - Full KeyPack implementation
   - Key management system
   - Recipient public key
   
   Unencrypted Mode:
   - Simplified KeyPack
   - Additional safety checks
   - Race condition handling
   

The choice between encrypted and unencrypted modes represents a trade-off between security guarantees and protocol flexibility. While encrypted mode provides the strongest security and privacy properties, unencrypted mode enables advanced features and novel use cases.

For typical transactions, encrypted mode remains the recommended default. Unencrypted mode should be used only in specific scenarios where its unique properties are required, and additional security measures can be implemented.

3.1.4 Transaction Flow Detail

Sending Process:

1. Wallet Preparation:
   - Select inputs
   - Calculate change
   - Generate r_t
   - Create payment proof

2. First Transaction Creation:
   - Build A → T transaction
   - Encrypt r_t for B
   - Sign transaction
   - Include metadata

3. First Transaction Broadcast:
   - Submit to network
   - Wait for confirmation
   - Monitor temporary output

Receiving Process:

1. Key Recovery:
   - Detect transaction
   - Derive shared secret
   - Decrypt r_t
   - Verify payment proof

2. Second Transaction Creation:
   - Build T → B transaction
   - Calculate fees
   - Sign transaction
   - Link payment proof

3. Second Transaction Broadcast:
   - Submit to network
   - Monitor confirmation
   - Update wallet state

3.1.5 Cut-Through and Blockchain State

Final Blockchain State:

1. Visible Components:
   - Input: C(r_a, v)
   - Output: C(r_b, v-f)
   - Kernels: K1, K2

2. Removed by Cut-Through:
   - Temporary output C(r_t, v)
   - All intermediate states

3. Net Effect:
   ((r_a - r_b)·H) + f·G  // Final kernel with fee

3.1.6 Payment Proof Integration

Proof Structure:

1. First Transaction Proof:
   E1 = r_excess1·H
   σ1 = k1 + e1·r_excess1
   msg1 = hash(
     amount ||
     kernel_features ||
     metadata
   )

2. Second Transaction Proof:
   E2 = r_excess2·H
   σ2 = k2 + e2·r_excess2
   msg2 = hash(
     amount ||
     kernel_features ||
     metadata
   )

3. Combined Proof:
   P = {
     E1, σ1, msg1,  // First transaction
     E2, σ2, msg2,  // Second transaction
     linking_data   // Cross-transaction validation
   }

3.1.7 Timelock Mechanism

1. Temporary Output Timelock:
   - Minimum lock: current_height + min_conf
   - Maximum lock: current_height + max_lock
   - Default: current_height + 1440 (≈24 hours)

2. Recovery Conditions:
   - Automatic return if not spent
   - Sender can reclaim after timeout
   - Configurable timeouts

3.1.8 Fee Handling Detail

1. First Transaction:
   - No fee required
   - Standard weight calculation
   - Zero fee commitment

2. Second Transaction:
   fee = weight * fee_base_rate
   weight = kernel_weight +    // Two kernels
           input_weight +      // Single input
           output_weight       // Final output

3. Fee Commitment in Kernel:
   K2 = (r_t - r_b)·H + f·G   // Explicit fee term

This expanded core concept provides a comprehensive technical foundation for understanding the complete KeyPack protocol implementation.

3.2 Temporary Key Encryption

The temporary key (r_t) is encrypted using:

1. Shared Secret Generation:

   s = ECDH(Alice_priv, Bob_pub)
   

2. Key Derivation:

   k = KDF(s || transaction_data)
   

3. Encryption:

   c = ChaCha20(k, r_t)
   

4. Security Analysis

4.1 Value Conservation Proof

Theorem 1: KeyPack preserves value conservation.

Proof:

1. Initial state before cut-through:

   (r_a·H + v·G) +      // Input from Alice
   (r_t·H + v·G) -      // Output to Temp
   (r_t·H + v·G) +      // Input from Temp
   (r_b·H + v·G)        // Output to Bob
   

2. After combining terms:

   (r_a - r_b)·H + 0·G
   

3. This proves:

   • Value is conserved (0·G term)
   • No coins created/destroyed
   • Blinding factors balance

4.2 Enhanced Transaction Privacy Through Unlinking

Theorem 2: KeyPack enhances transaction privacy through temporal and structural unlinking.

Proof:

1. For any outputs A, B in a standard transaction:

   P(link(A,B)) = 1/N
   

   where N is the total number of outputs

2. For KeyPack’s split transactions A₁, A₂:

   P(link(A₁,A₂)) = 1/N²
   

   This quadratic improvement occurs because:

   • Transactions appear at different times
   • No structural links exist between A₁ and A₂
   • Independent kernel commitments

3. The unlinking property holds because:

   • Cut-through removes C(r_t, v)
   • Kernels K1, K2 are temporally separated
   • Kernels are independently random and unlinkable
   • Each transaction appears as a standard Grin transaction
   • No observable correlation between parts exists

4. Transaction Graph Analysis Resistance:
   For an adversary attempting to link transactions:

   P(identify_true_flow) = P(link(A₁,A₂)) * P(temporal_correlation)
   

   where:

   • P(temporal_correlation) ≤ 1/T for time window T
   • Total linkability probability becomes 1/(N²T)

This demonstrates that KeyPack provides substantially stronger privacy than standard transactions by:

• Creating temporal separation
• Breaking structural links
• Generating independent kernels
• Masking transaction flow
• Preventing graph analysis

5. Privacy Considerations

5.1 Cryptographic Assumptions

Security relies on:

1. Discrete Logarithm Problem:

   Given P = x·G, finding x is hard
   

2. ECDH Security:

   s = ECDH(a, B) = ECDH(b, A)
   where:
   A = a·G, B = b·G
   

3. ChaCha20-Poly1305 Security:

   • IND-CCA2 secure
   • Authenticated encryption

5.2 Privacy Guarantees

1. Transaction Unlinkability:

   ∀ tx1, tx2: P(linked(tx1, tx2)) = P(random_guess)
   

2. Amount Confidentiality:

   • Hidden by Pedersen commitments
   • No leakage in proofs

6. Fee Handling

6.1 Mathematical Structure

Transaction 1 (Alice → Temp):

Inputs:   C(r_a, v) = r_a·H + v·G
Outputs:  C(r_t, v) = r_t·H + v·G
Kernel1:  K1 = (r_a - r_t)·H
Fee1:     0

Transaction 2 (Temp → Bob):

Inputs:   C(r_t, v) = r_t·H + v·G
Outputs:  C(r_b, v-f) = r_b·H + (v-f)·G
Kernel2:  K2 = (r_t - r_b)·H + f·G
Fee2:     f

6.2 Fee Conservation Proof

Theorem 3: KeyPack preserves proper fee handling.

Proof:

1. Initial state (all components):

   (r_a·H + v·G) +       // Input from Alice
   (r_t·H + v·G) -       // Output to Temp
   (r_t·H + v·G) +       // Input from Temp
   (r_b·H + (v-f)·G) -   // Output to Bob
   (r_a - r_t)·H +       // Kernel1
   (r_t - r_b)·H + f·G   // Kernel2 with fee
   

2. After combining terms:

   ((r_a - r_b)·H) + f·G
   

This proves:

• Value conservation including fee
• Single fee payment for entire operation
• Proper fee commitment in kernel

7. Compression Techniques

7.1 Key Compression

For public key P(x,y):

compressed = sign_bit(y) || x_coordinate

Compression ratio: ~50%

7.2 Nonce Derivation

nonce = blake2b(
    kernel_commitment ||
    amount ||
    height_delta
)[0..8]

7.3 Size Analysis

Final compressed format:

struct CompressedKeyPack {
    enc_key: [u8; 33],    // Compressed key
    nonce_data: [u8; 8],  // Derived nonce
    amount: u64,          // Amount
    height_delta: u16,    // Block height difference
    proof: [u8; 32],      // Compact proof
}

Total size: ~83 bytes (39% reduction)

8. Edge Cases and Mitigations

8.1 Network Partitions

Protected by:

1. Timelock prevents hanging
2. Funds return to sender after timeout
3. No permanent state changes

8.2 Front-running Protection

Secured through:

1. Recipient-specific encryption
2. Unique transaction data
3. Timelock enforcement

9. Conclusions

KeyPack implements:

1. Mathematically proven security
2. Full MimbleWimble compatibility
3. Strong payment proofs
4. Enhanced privacy preservation

Requirements:

1. No consensus changes
2. No protocol modifications
3. Wallet-layer updates only

All proofs rely on standard cryptographic assumptions and protocol design principles.

References

[1] MimbleWimble Protocol Specification
[2] Pedersen Commitments in Cryptography
[3] ChaCha20-Poly1305 AEAD Specification
[4] Schnorr Signature Scheme
[5] ECDH Key Exchange Protocol

[tromp]

This looks like the old familiar 1-of-2 output. Alice creates an output that both she and Bob can spend once she shares its blinding key with Bob. Which fails when that output gets spent, but both Alice and Bob deny spending it, claiming the other party must have spent it. With 1-of-2 outputs, there’s no way to determine who spent it…

@ebkme

• This necessitates simultaneous online presence and creates high coordination complexity.

No simultaneity required. Just 2 messages, one in each direction.

@ebkme

C(r, v) = r·H + v·G

Actually, it’s r·G + v·H.

Btw, Grin has a graph obfuscation protocol [1].

@ebkme

• Maximum lock: current_height + max_lock

Grin has no maximum-time locks.

[1] https://forum.grin.mw/t/mimblewimble-coinswap-proposal

[Anynomous]

For convenience, a link to the original 1-of-2 output proposal by David B to eliminate the finalize step.

Eliminating finalize step

Currently, grin transactions are created using the following 3 (simplified) steps: Send - Sender commits to amount, fee, and a public nonce, public excess. It could also commit to tx offset, inputs, change output, and probably others. Receive - The receiver adds their output & rangeproof, and commits to their public nonce and excess. It then updates the total kernel commitment, and signs for their half of the kernel. Finalize - The sender adds their half of the signature, aggregates the 2 part…

It is stated in this new KeyPack proposal that there are

Strong payment proofs

That is something that David had not solved in his proposal. Whats new in this proposal to my understanding is the use of a

1. A time-lock
2. Claimed strong payment proofs.
3. Use of cut-through to eliminate a temporary output (nifty, I also used this in my fun but poor transaction buddy proposal)

The payment proofs is something to really pay attention to, also if the proof works to avoid dispute in case a transaction expires (can the sender not falsely claim the funds were send)? I really wonder how the peoof can work, is the proof included in the transaction output that is dropped “C(r_t, v)”, or no probabbly the kernel.

Another part I do not understand is the “Single fee payment for entire operation”. Even if cut-through is used the transaction does create two kernels, and to my understanding the fees for the eliminated temporary output would still have to be paid for for the first kernel to be valid.

[Anynomous]

I think I see a first major problem. The proposed solutions wants to let Alice add a first transaction with a temporary output to the mempool that does not include a fee. Then Bob comes in to claim funds from that temporary output and he pays all the fee, or he does not… This would allow Alice to spam the mempool without limits with fake transactions since there is no fee as spam protection, rather surprising @ebkme would have missed this rather obvious problem. At the moment the mempool would reject the first transaction since it does not include a fee making the transaction invalid. In theory this could simply be fixed in the proposal by adding a fee to the first transaction with the only downside of increasing link-ability of the two transaction.

I leave it to others to check if payment proofs can theoretically work with this proposed solution.
Intuitively I would expect that after the timelock transpires there will be a race condition where you cannot prove who claimed the funds.

[Anynomous]

Just for fun I threw the first part of this proposal in an AI writing checker and the result is:
AI-generated 87%
Human written 13%

[tromp]

That would explain the lack of follow-ups?!

[CircusDad]

@ebkme thanks for taking the time to put this together and post. Sounds like the concept was already considered under another name but the the effort is appreciated.

@tromp @Anynomous thanks for being knowledgeable community members with the history to prevent repeat effort.