brc-20 Index State Hash Verification Scheme v2 (MuHash Version)

1. Background and Design Evolution

1.1 Limitations of the v1 Scheme

The v1 scheme uses a dual Merkle Tree plus chained structure. Although it can locate differences precisely, it has the following issues:

• Chained dependency: prev_commitment_hash causes any difference in an intermediate block to propagate to all subsequent blocks.

• Version incompatibility: after indexer code upgrades or rule changes, hashes of intermediate blocks may differ even when the final state is the same.

• Incremental calculation: only changed addresses are committed, requiring additional delta calculation logic.

• Poor fault tolerance: differences in intermediate processing cannot be tolerated; every block must match exactly.

1.2 Core Idea of the v2 Scheme

Inspired by the MuHash mechanism used for the Bitcoin UTXO set, this scheme uses a full-state commitment:

• Full state: each block commits to the complete BRC-20 balance state, not only the changed addresses.

• Independent calculation: each block hash is calculated independently and does not depend on the previous block.

• Final consistency: as long as the final balance state is the same, the hash is the same, tolerating differences in intermediate processing.

• Version compatibility: different versions of indexer code can produce the same hash as long as they eventually converge to the same state.

This design is especially suitable for index mining scenarios: indexers with different implementations and different versions are allowed, as long as their final states are consistent.

2. Introduction to the MuHash Mechanism

2.1 What Is MuHash

MuHash (Multiplicative Hash) is a commutative hash function with the following properties:

• Commutativity: the order in which elements are added does not affect the final result.

• Incremental updates: elements can be added or removed efficiently.

• Determinism: the same set always produces the same hash.

2.2 Mathematical Principle of MuHash

MuHash is based on a multiplicative group over a finite field:

1. Serialize each element into a byte string.

2. Hash the byte string and map it to an element in a large prime field.

3. Multiply all elements in the field.

4. Hash the final result once more to obtain a fixed-length output.

Key properties:

• Multiplication is commutative: a x b = b x a.

• Therefore, element order does not affect the result.

• Incremental updates are possible: to add element c, multiply by c; to remove element d, divide by d.

2.3 Bitcoin Implementation Reference

Bitcoin uses MuHash3072 to calculate the hash of the UTXO set:

• It uses a 3072-bit prime field.

• Each UTXO is serialized and mapped to a field element through ChaCha20.

• The field elements of all UTXOs are multiplied together.

• The final result is output as a 32-byte hash through SHA-256.

3. v2 Scheme Design

3.1 Data Input

Use the full balance state after merging the overlay:

TokenUsersBalanceData: map[string]map[string]*BRC20TokenBalance

• [ticker][pkscript] -> balance

• Contains all addresses with non-zero balances, not only addresses changed in the current block.

• This is the final state after processing the current block.

BRC20TokenBalance structure:

type BRC20TokenBalance struct {
    Ticker               string
    PkScript             string            // Raw bytes, not hex
    AvailableBalance     uint128.Decimal
    TransferableBalance  uint128.Decimal
}

3.2 Balance Entry Serialization

Each balance entry (ticker + pkscript + balance) is serialized into a byte string and used as an input element to MuHash.

Serialization format:

balance_entry = (
    len(ticker)                      [4 bytes, little-endian]
    ticker                           [variable length, UTF-8 bytes]
    len(pkscript)                    [4 bytes, little-endian]
    pkscript                         [variable length, raw bytes]
    len(available_balance_str)       [4 bytes, little-endian]
    available_balance_str            [variable length, UTF-8 bytes, generated by AvailableBalance.String()]
    len(transferable_balance_str)    [4 bytes, little-endian]
    transferable_balance_str         [variable length, UTF-8 bytes, generated by TransferableBalance.String()]
)

Key points:

• All integers use little-endian encoding.

• Variable-length fields use a 4-byte length prefix.

• Balances use the Decimal.String() method to ensure determinism.

• The ticker uses lowercase form (BRC-20 is case-insensitive).

• Only entries with non-zero balances are serialized (a zero balance is treated as nonexistent).

3.3 MuHash Calculation

Steps:

1. Collect all balance entries

   • Iterate through TokenUsersBalanceData.

   • Skip zero-balance entries (both AvailableBalance and TransferableBalance are zero).

2. Serialize each entry

   • Serialize it into a byte string according to the format above.

3. Map to field elements

   • For each serialized byte string, use ChaCha20 or SHA-256 to map it to a MuHash3072 field element.

   • Specific mapping method: domain_element = Hash(balance_entry) mod prime.

4. Field multiplication

   • The initial value is 1 (the multiplicative identity of the field).

   • Multiply each field element: result = result x element mod prime.

   • Because multiplication is commutative, order does not matter.

5. Final hash

   • Serialize the field element into a byte string (3072 bits = 384 bytes).

   • Apply SHA-256 to obtain the 32-byte brc20_state_hash.

3.4 Block Commitment Structure

BlockCommitment {
    version:            uint8           // Protocol version number, v2 = 0x02
    height:             uint64          // Block height
    block_hash:         [32]byte        // Block hash
    brc20_state_hash:   [32]byte        // Balance state hash calculated by MuHash
}

Final commitment hash:

commitment_hash = SHA256(
    version +
    height +
    block_hash +
    brc20_state_hash
)

Notes:

• prev_commitment_hash is not included; each block is independent.

• brc20_state_hash depends only on the final balance state of the current block.

• The same balance state always produces the same brc20_state_hash.

4. Verification Protocol

4.1 Fast Verification

Two nodes exchange commitment_hash (32 bytes) to determine whether their BRC-20 states at the given height are consistent.

If commitment_hash matches, it means:

• The block height is the same.

• The block hash is the same.

• The full BRC-20 balance state is exactly the same.

4.2 Divergence Localization

Because MuHash does not support hierarchical localization like a Merkle Tree, divergence localization requires other strategies:

Option 1: Ticker-level MuHash

Calculate a separate MuHash for each ticker:

ticker_state_hash[ticker] = MuHash(all balance entries of this ticker)

When the global brc20_state_hash does not match:

1. Exchange the lists of all tickers.

2. Compare the ticker_state_hash of each ticker.

3. Locate the specific ticker that is inconsistent.

4. Exchange all balance entries of that ticker and compare them entry by entry.

Option 2: Direct comparison

If brc20_state_hash does not match:

1. Exchange the lists of all tickers and the address count for each ticker.

2. For tickers with different counts, exchange the complete address lists.

3. For tickers with the same counts but possible differences, exchange all balance entries and compare them.

Recommendation:

• Use Option 1 (ticker-level MuHash) in production environments to support efficient localization.

• Simpler implementations can use Option 2 for direct comparison.

4.3 Checkpoint Mechanism

It is recommended to publish a checkpoint every 1000 blocks:

Checkpoint {
    height:             uint64
    block_hash:         [32]byte
    commitment_hash:    [32]byte
    brc20_state_hash:   [32]byte      // Optional, for fast localization
    version:            uint8
    timestamp:          int64
    signature:          []byte         // Optional
}

New nodes can start synchronization from a checkpoint and verify the commitments of subsequent blocks.

5. Performance Analysis

5.1 Computational Overhead

Assume the full state contains:

• 1000 tickers

• An average of 1000 addresses with balances per ticker

• 1 million balance entries in total

MuHash calculation:

• Serialization: 1 million operations (about 100 bytes each)

• Field mapping: 1 million ChaCha20 or SHA-256 operations

• Field multiplication: 1 million 3072-bit big integer multiplications

• Final hash: 1 SHA-256 operation

Estimated time:

• Serialization: ~100 ms

• Field mapping: ~500 ms (SHA-256) or ~200 ms (ChaCha20)

• Field multiplication: ~2000 ms (3072-bit big integer operations)

• Total: ~2-3 seconds

Compared with the time required for block indexing itself (usually 1-10 seconds), this overhead is acceptable.

Optimization strategies:

• Use incremental updates: perform add/remove operations only for changed addresses.

• Cache the MuHash state of the previous block and calculate the current block incrementally.

• Use a more efficient big integer arithmetic library (GMP).

5.2 Storage Overhead

Store one BlockCommitment per block:

version:              1 byte
height:               8 bytes
block_hash:          32 bytes
brc20_state_hash:    32 bytes
commitment_hash:     32 bytes
Total:              105 bytes/block

1 million blocks are approximately 105 MB, which is fully acceptable.

If ticker-level localization needs to be supported, additionally store the hash of each ticker:

Each ticker: ticker_name (variable length, 4 bytes on average) + ticker_state_hash (32 bytes) ~= 40 bytes
1000 tickers x 40 bytes = 40 KB/block
1 million blocks ~= 40 GB

This can be stored on demand, with detailed data retained only for the most recent 10000 blocks.

6. Advantages of the Scheme

6.1 Final Consistency

• As long as the final balance state is the same, the hash is the same.

• Differences in intermediate processing are tolerated (different event parsing orders, temporary states, etc.).

• Suitable for coexistence of multi-version indexers.

6.2 Version Compatibility

• After indexer code upgrades, the hash remains consistent as long as the final state converges.

• Differences in intermediate blocks will not cause all subsequent blocks to become inconsistent.

• Supports progressive upgrades and rollbacks.

6.3 Independent Calculation

• The hash of each block is calculated independently and does not depend on the previous block.

• Hashes of multiple blocks can be calculated in parallel.

• Verification can start from any checkpoint.

6.4 Full-State Commitment

• Commits to the complete balance state, not only changed addresses.

• More intuitive and easier to understand and verify.

• Can be used directly for state synchronization and snapshots.

6.5 Incremental Updates

• MuHash supports incremental updates (add/remove).

• The MuHash state of the previous block can be cached, updating only changed parts.

• Actual computational overhead is much lower than a full recalculation.

7. Limitations of the Scheme

7.1 Weaker Localization Capability

• MuHash itself does not support hierarchical localization.

• Additional ticker-level MuHash or direct comparison is required.

• Localization efficiency is lower than with a Merkle Tree.

7.2 Higher Computational Overhead

• Full-state MuHash calculation involves big integer operations.

• It is more time-consuming than Merkle Tree SHA-256 calculation.

• Optimization is required (incremental updates, efficient libraries).

7.3 Does Not Verify Correctness

• Same as v1, it only proves that "the results are consistent"; it does not prove that "the results are correct".

• Other mechanisms, such as majority consensus, are needed to ensure correctness.

7.4 Zero-Balance Handling

• Zero-balance entries do not participate in MuHash calculation (they are treated as nonexistent).

• The semantics of "zero balance" must be clearly defined (both AvailableBalance and TransferableBalance are zero).

8. Edge Case Handling

Scenario	Handling
Block has no BRC-20 activity	The balance state is the same as the previous block, and brc20_state_hash is the same.
All balances are zero	The MuHash result is 1 (the multiplicative identity), and the final brc20_state_hash is a specific value.
Ticker is an empty string	This should not occur. If it does, process it normally (length prefix is 0).
pkscript is empty	This should not occur. If it does, process it normally (length prefix is 0).
Balance is zero	It does not participate in MuHash calculation (skip this entry).
Block reorg	Recalculate brc20_state_hash for blocks after the reorg. Calculation is independent; no chained state rollback is needed.

9. Comparison with the v1 Scheme

Feature	v1 (Merkle Tree)	v2 (MuHash)
State commitment	Incremental (commits only changed addresses)	Full (commits all non-zero balances)
Chained dependency	Yes (prev_commitment_hash)	No (each block is independent)
Final consistency	No (intermediate differences propagate)	Yes (only the final state needs to match)
Version compatibility	Poor (intermediate block differences cause all subsequent blocks to differ)	Good (tolerates intermediate differences and only checks the final state)
Localization capability	Strong (hierarchical localization to a specific address)	Weak (requires an additional mechanism or direct comparison)
Computational overhead	Low (SHA-256)	High (big integer operations)
Incremental updates	Not supported (Merkle Tree must be rebuilt)	Supported (MuHash naturally supports add/remove)
Implementation complexity	Medium (Merkle Tree construction)	High (MuHash big integer operations)
Applicable scenarios	Strict consistency requirements, precise localization needed	Final consistency, intermediate differences tolerated

10. Implementation Recommendations

10.1 MuHash Library Selection

• Use Bitcoin Core's MuHash3072 implementation (C++).

• Or use Go's big.Int to implement a custom MuHash.

• GMP (GNU Multiple Precision Arithmetic Library) is recommended for better performance.

10.2 Incremental Update Strategy

Pseudocode:
1. Cache the MuHash state of the previous block.
2. For addresses changed in the current block:
   - If the previous balance is non-zero: remove the old entry.
   - If the current balance is non-zero: add the new entry.
3. Obtain the MuHash state of the current block.
4. Cache it for use by the next block.

10.3 Ticker-level MuHash (Optional)

To support efficient localization, a separate MuHash can be maintained for each ticker:

ticker_muhash[ticker] = MuHash(all balance entries of this ticker)

The global MuHash can be obtained by combining the MuHash values of all tickers (this requires special design).

Alternatively, the global MuHash and ticker-level MuHash can simply be calculated independently.

10.4 Zero-Balance Cleanup

Clean up zero-balance entries periodically to prevent TokenUsersBalanceData from growing without bound:

• When both AvailableBalance and TransferableBalance are zero, delete the entry from the map.

• This does not affect the MuHash result (zero balances do not participate in the calculation anyway).

11. Migration Path

11.1 Migrating from v1 to v2

• v1 and v2 can run in parallel without affecting each other.

• New blocks calculate both v1 and v2 commitments at the same time.

• Gradually transition to using only v2.

11.2 Version Identifiers

• v1: version = 0x01

• v2: version = 0x02

• Commitment hashes of different versions will not be confused.

12. Summary

Through the MuHash mechanism, the v2 scheme provides a more flexible and more fault-tolerant state commitment scheme for the BRC-20 index of Fractal Bitcoin.

Core advantages:

• Final consistency: intermediate differences are tolerated as long as the final state is the same.

• Version compatibility: supports coexistence of multi-version indexers and progressive upgrades.

• Independent calculation: each block is independent and does not rely on a chained structure.

• Full-state commitment: more intuitive and easier to understand and verify.

Applicable scenarios:

• Index mining: allows indexers with different implementations and different versions to participate.

• Multi-version coexistence: transition periods during indexer code upgrades.

• Final consistency verification: cares only about the final state, not the intermediate process.

Trade-offs:

• Higher computational overhead (but it can be optimized through incremental updates).

• Weaker localization capability (but it can be supplemented by ticker-level MuHash).

The v2 scheme is more suitable for Fractal's index mining ecosystem. It allows a more diverse set of participants while ensuring consistency of the final state.