# Merkle Challenges

## Overview

Merkle challenges provide cryptographic proof-based approval mechanisms using SHA256 Merkle trees. They enable secure, gas-efficient whitelisting and claim code systems without storing large address lists on-chain.

**Key Benefits**:

* **Gas Efficiency**: Distribute gas costs among users instead of collection creators
* **Security**: Cryptographic proof verification prevents unauthorized access
* **Flexibility**: Support both whitelist trees and claim code systems
* **Scalability**: Handle large user bases without on-chain storage

## Interface Definition

```typescript
export interface MerkleChallenge<T extends NumberType> {
    root: string; // SHA256 Merkle tree root hash
    expectedProofLength: T; // Required proof length (security)
    useCreatorAddressAsLeaf: boolean; // Use initiator address as leaf?
    maxUsesPerLeaf: T; // Maximum uses per leaf
    uri: string; // Metadata URI
    customData: string; // Custom data field
    challengeTrackerId: string; // Unique tracker identifier
    leafSigner: string; // Optional leaf signature authority
}
```

## Basic Example

```json
{
    "merkleChallenges": [
        {
            "root": "758691e922381c4327646a86e44dddf8a2e060f9f5559022638cc7fa94c55b77",
            "expectedProofLength": "1",
            "useCreatorAddressAsLeaf": false,
            "maxUsesPerLeaf": "1",
            "uri": "ipfs://Qmbbe75FaJyTHn7W5q8EaePEZ9M3J5Rj3KGNfApSfJtYyD",
            "customData": "",
            "challengeTrackerId": "uniqueId",
            "leafSigner": "0x"
        }
    ]
}
```

## Challenge Types

### 1. Claim Code Challenges

Create a Merkle tree of secret claim codes that users must provide to claim tokens.

**Use Case**: Private claim codes, invitation systems, promotional campaigns

**Process**:

1. Generate secret claim codes
2. Build Merkle tree from hashed codes
3. Distribute codes privately to users with leaf signatures
4. Users provide code + Merkle proof in transfer

### 2. Whitelist Challenges

Create a Merkle tree of user addresses for gas-efficient whitelisting.

**Use Case**: Large whitelists, community access, gas cost distribution

**Process**:

1. Collect user addresses
2. Build Merkle tree from hashed addresses
3. Users provide their address + Merkle proof
4. System verifies address is in whitelist / valid proof

**Gas Cost Distribution**: Instead of the collection creator paying gas to store N addresses on-chain, each user pays their own gas for proof verification.

## Understanding useCreatorAddressAsLeaf

The `useCreatorAddressAsLeaf` field determines how the system handles the leaf value in Merkle proofs:

### Whitelist Trees (`useCreatorAddressAsLeaf: true`)

**Purpose**: Verify that the transaction initiator is in the whitelist.

**How It Works**:

1. **Automatic Override**: The system expects the provided leaf to be the initiator's BitBadges address ("bb1...")
2. **Address Verification**: Checks if the initiator's address exists in the Merkle tree
3. **No Manual Leaf**: Users don't need to provide their address as the leaf - the system handles it

**Recommended Configuration**:

* Set `initiatedByList` to "All" (whitelist tree handles the restriction)
* Set `useCreatorAddressAsLeaf: true`
* Build Merkle tree from BitBadges addresses as leaves \["bb1...", "bb2...", "bb3..."]

### Claim Code Trees (`useCreatorAddressAsLeaf: false`)

**Purpose**: Verify that the user possesses a valid claim code.

**How It Works**:

1. **Manual Leaf**: User must provide the actual claim code as the leaf
2. **Code Verification**: System verifies the provided code exists in the Merkle tree
3. **User Responsibility**: Users must know and provide their claim code

**Recommended Configuration**:

* Set `useCreatorAddressAsLeaf: false`
* Build Merkle tree from claim codes as leaves \["secret1", "secret2", "secret3"]
* Post root hash on-chain as challenge
* Distribute codes privately to users with leaf signatures

## Security Features

### Expected Proof Length

**Critical Security Feature**: All proofs must have the same length to prevent preimage and second preimage attacks.

```typescript
// All proofs must match this length
expectedProofLength: '2'; // 2-level proof required
```

**Design Requirement**: Your Merkle tree must be constructed so all leaves are at the same depth.

### Max Uses Per Leaf

Control how many times each leaf can be used:

| Setting         | Behavior          | Use Case             |
| --------------- | ----------------- | -------------------- |
| `"0"` or `null` | Unlimited uses    | Public claim codes   |
| `"1"`           | One-time use      | Single-use codes     |
| `"5"`           | Five uses maximum | Limited distribution |

**Critical Security Requirement**: For claim code challenges (`useCreatorAddressAsLeaf: false`), `maxUsesPerLeaf` must be `"1"` to prevent replay attacks.

### Replay Attack Protection

**⚠️ CRITICAL SECURITY RISK**: Non-address trees (claim codes) are vulnerable to front-running attacks.

**The Problem**:

1. User submits transaction with valid Merkle proof
2. Proof becomes visible in mempool (public blockchain)
3. Malicious actor sees the proof and front-runs the transaction
4. Original user's transaction fails, attacker gets the token

**Why This Happens**:

* Merkle proofs for claim codes are reusable until consumed
* Once in mempool, proofs are publicly visible
* No built-in protection against proof reuse

**The Solution**: Leaf signatures provide cryptographic protection against this attack.

## Challenge Tracking

### Tracker System

Uses increment-only, immutable trackers to prevent double-spending:

```typescript
{
    collectionId: T;
    approvalId: string;
    approvalLevel: 'collection' | 'incoming' | 'outgoing';
    approverAddress: string; // blank if collection-level
    challengeTrackerId: string;
    leafIndex: T; // Leftmost base layer leaf index = 0, rightmost = numLeaves - 1
}
```

Note the fact we use leaf indices to track usage and not leaf values.

### Tracker Examples

```
1-collection- -approvalId-uniqueID-0  → USED 1 TIME
1-collection- -approvalId-uniqueID-1  → UNUSED
1-collection- -approvalId-uniqueID-2  → USED 3 TIMES
```

**Important**: Trackers are scoped to specific approvals and cannot be shared between different approval configurations.

### Tracker Management

* **Increment-Only**: Once used, the number of uses cannot be decremented
* **Immutable**: Tracker state cannot be modified
* **Best Practice**: Use unique `challengeTrackerId` for fresh tracking of new approvals

## Leaf Signatures

### Protection Against Front-Running

Leaf signatures provide cryptographic protection against front-running attacks on claim code challenges.

**How It Works**:

```typescript
// Signature scheme
signature = ETHSign(leaf + '-' + bitbadgesAddressOfInitiator);
```

**Security Mechanism**:

1. **Address Binding**: Each proof is cryptographically tied to a specific BitBadges address
2. **Replay Prevention**: Even if proof is intercepted, it cannot be used by other addresses
3. **Mempool Safety**: Intercepted proofs in mempool are useless to attackers

### Implementation

```typescript
// Only Ethereum addresses supported currently
leafSigner: '0x742d35Cc6634C0532925a3b8D4C9db96C4b4d8b6';
```

**Critical Benefits**:

* **Front-Running Protection**: Prevents attackers from stealing tokens via mempool interception
* **Address-Specific**: Each proof is cryptographically bound to the intended recipient
* **Mempool Safety**: Makes intercepted proofs useless to malicious actors
* **Required for Claim Codes**: Strongly recommended for all non-address tree challenges

**⚠️ IMPORTANT**: For claim code challenges, leaf signatures are not just recommended—they are essential for security against front-running attacks.

## Merkle Tree Construction

### Standard Configuration

```typescript
import { SHA256 } from 'crypto-js';
import MerkleTree from 'merkletreejs';

// For claim codes
const codes = ['secret1', 'secret2', 'secret3'];
const hashedCodes = codes.map((x) => SHA256(x).toString());

// For whitelists
const addresses = ['bb1...', 'bb1...', 'bb1...'];
const hashedAddresses = addresses.map((x) => SHA256(x));

// Tree options (tested configuration)
const treeOptions = {
    fillDefaultHash:
        '0000000000000000000000000000000000000000000000000000000000000000',
};

// Build tree
const tree = new MerkleTree(hashedCodes, SHA256, treeOptions);
const root = tree.getRoot().toString('hex');
const expectedProofLength = tree.getLayerCount() - 1;
```

### Critical Requirements

1. **Same Layer**: All leaves must be at the same depth
2. **Consistent Proof Length**: All proofs must have identical length
3. **Test Thoroughly**: Verify all paths work before deployment
4. **Use Tested Options**: Stick to the `fillDefaultHash` configuration

## Transfer Integration

### Providing Proofs

Include Merkle proofs in [MsgTransferTokens](https://github.com/trevormil/bitbadges-docs/blob/master/bitbadges-blockchain/cosmos-sdk-msgs/x-tokenization/msgtransferbadges.md):

```typescript
const txCosmosMsg: MsgTransferTokens<bigint> = {
    creator: chain.bitbadgesAddress,
    collectionId: collectionId,
    transfers: [
        {
            // ... other fields
            merkleProofs: [
                {
                    aunts: proofObj.map((proof) => ({
                        aunt: proof.data.toString('hex'),
                        onRight: proof.position === 'right',
                    })),
                    leaf: isWhitelist ? '' : passwordCodeToSubmit,
                    leafSignature: leafSignature, // if applicable
                },
            ],
        },
    ],
};
```

### Proof Generation

```typescript
// Generate proof for user submission
const passwordCodeToSubmit = 'secretCode123';
const leaf = isWhitelist
    ? SHA256(chain.bitbadgesAddress).toString()
    : SHA256(passwordCodeToSubmit).toString();

const proofObj = tree.getProof(leaf, whitelistIndex);
const isValidProof = proofObj && proofObj.length === tree.getLayerCount() - 1;

// Create signature if needed
const leafSignature = signLeaf(leaf + '-' + chain.bitbadgesAddress);
```

## Comparison with ETH Signature Challenges

Merkle challenges and ETH signature challenges are very similar. The main difference is that Merkle challenges must also check that the signed message was pre-committed to in the tree, whereas ETH signature challenges only need to check that the signature is valid and not used before.

For more information, see [ETH Signature Challenges](/token-standard/learn/approval-criteria/eth-signature-challenges.md).

## Best Practices

### Design Considerations

1. **Tree Structure**: Ensure all leaves at same depth
2. **Proof Length**: Test all proof lengths are identical
3. **Tracker Management**: Use unique IDs for fresh tracking
4. **Security**: **MANDATORY** - Enable leaf signatures for claim codes to prevent front-running
5. **Testing**: Verify all paths work before mainnet

### Performance Optimization

1. **Small Lists**: For <100 users, consider regular address lists
2. **Gas Distribution**: Merkle trees excel with large user bases
3. **Proof Verification**: On-chain verification is gas-efficient
4. **Storage**: No on-chain storage of large lists required


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.bitbadges.io/token-standard/learn/approval-criteria/merkle-challenges.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.