BIP Draft: Optimal Batch Proofs for Utreexo

EntropyMaBoyy commented at 8:37 pm on January 9, 2026: none

This draft proposes a deterministic, canonical, and bandwidth-optimal batch proof format for Utreexo accumulator forests.

The proposal defines a canonical ordering of proof elements and a bitmap-guided verification stream that eliminates redundant hashes while preserving full verifiability and non-malleability.

The specification includes normative pseudocode, explicit failure modes, and reference test vectors. A Python reference implementation was used to validate all vectors.

This proposal does not modify consensus rules and is intended for use by wallets, light clients, and Utreexo-based systems.

Feedback is welcome, particularly regarding serialization choices and deployment considerations.

Create bip-xxxx.md dfd4e1b779

murchandamus commented at 8:53 pm on January 9, 2026: contributor

Hello Lucas,

I don’t think I have seen this idea discussed on the Bitcoin mailing list. Could you please provide the link to the thread where your idea was previously discussed? The document has various formatting issues, and at first glance, the text doesn’t seem to align well with the Utreexo proposals that are being discussed in #1923. Could you please tell us a little more about your process and how your proposal fits into the bigger picture regarding Utreexo?

murchandamus added the label New BIP on Jan 9, 2026

EntropyMaBoyy commented at 9:41 pm on January 9, 2026: none

Hi Murch,

Thanks for the quick feedback. You’re absolutely right to flag the disconnect with PR #1923. I’ve reviewed Calvin Kim’s proposal and can now articulate the technical friction clearly:

Core Difference: Implicit vs. Explicit Path Encoding

#1923 (Utreexo Standard): Uses implicit path derivation. The verifier calculates traversal order from leaf indices and num_leaves, saving bandwidth by deducing structure mathematically. This is optimal for full Utreexo nodes that maintain the accumulator state (Stump).
My Proposal (BIP-XXXX): Uses an explicit bitmap. The verifier follows a simple FIFO stack algorithm with no index calculations. This costs 1 bit per internal node but eliminates the need for num_leaves or tree topology awareness.

The “Stateless Verifier” Use Case

My target is ultra-light clients that want to verify a single proof without syncing the accumulator. For example:

Hardware wallets receiving a one-off payment proof.
Cross-protocol bridges where the verifier doesn’t track Bitcoin’s UTXO set state.
Environments where even small indexing logic is a security/complexity risk (e.g., firmware).

In these cases, transmitting a small bitmap is a deliberate trade-off: bandwidth for verifier simplicity and zero state.

Process Question

I now realize I may have jumped the gun. I haven’t posted to the Bitcoin mailing list yet—should I initiate discussion there first, even if this is positioned as a complementary (not competing) format? Or would it be more productive to propose this as an optional “stateless mode” extension within #1923’s framework?

Cleaned Pseudocode for Reference

Below is the final, tested implementation that aligns with the BIP’s security model (SHA256, exact consumption, no malleability):

  0import hashlib
  1from collections import deque
  2from typing import List, Deque
  3
  4#
  5-----------------------------------------------------------------------------
  6# Constants & Hash Function
  7#
  8-----------------------------------------------------------------------------
  9
 10BIT_LEFT = 0 # Bitmap 0: H(a || b)
 11BIT_RIGHT = 1 # Bitmap 1: H(b || a)
 12
 13def sha256(data: bytes) -> bytes:
 14    """Cryptographic hash function as specified by BIP."""
 15    return hashlib.sha256(data).digest()
 16
 17#
 18-----------------------------------------------------------------------------
 19# Single Tree Proof Verification
 20#
 21-----------------------------------------------------------------------------
 22
 23def verify_single_tree_proof(
 24    leaves: List[bytes],
 25    hashes: List[bytes],
 26    bitmap: List[int],
 27    expected_root: bytes
 28) -> bool:
 29    """
 30    Verifies a deterministic batch proof for one Merkle tree.
 31
 32    Args:
 33        leaves: Leaf hashes to prove (target nodes).
 34        hashes: Canonical sibling hashes (deduplicated, height-sorted).
 35        bitmap: Explicit L/R composition instructions (0=Left, 1=Right).
 36        expected_root: Known tree root for validation.
 37
 38    Returns:
 39        True iff proof is valid and consumes all elements exactly.
 40    """
 41    if not leaves:
 42        return False
 43
 44    # Initialize FIFO queue (not a stack) for sequential composition
 45    queue: Deque[bytes] = deque(leaves)
 46    hash_idx = 0
 47    bit_idx = 0
 48
 49    # Reconstruct root until one element remains
 50    while len(queue) > 1:
 51        # Exhaustion check: must have exactly enough elements
 52        if hash_idx >= len(hashes) or bit_idx >= len(bitmap):
 53            return False
 54
 55        a = queue.popleft() # Current accumulated hash
 56        b = hashes[hash_idx] # Next sibling hash
 57
 58        # Compose based on explicit bitmap direction
 59        if bitmap[bit_idx] == BIT_LEFT:
 60            c = sha256(a + b)
 61        else: # BIT_RIGHT
 62            c = sha256(b + a)
 63
 64        queue.append(c)
 65        hash_idx += 1
 66        bit_idx += 1
 67
 68    # Exact consumption is mandatory for non-malleability
 69    if hash_idx != len(hashes) or bit_idx != len(bitmap):
 70        return False
 71
 72    # Final root equality check
 73    return queue[0] == expected_root
 74
 75#
 76-----------------------------------------------------------------------------
 77# Forest Batch Proof Verification
 78#
 79-----------------------------------------------------------------------------
 80
 81class TreeProof:
 82    """Container for per-tree proof elements."""
 83    def __init__(self, leaves, hashes, bitmap, expected_root):
 84        self.leaves = leaves
 85        self.hashes = hashes
 86        self.bitmap = bitmap
 87        self.expected_root = expected_root
 88
 89def verify_forest_batch_proof(forest_proofs: List[TreeProof]) -> bool:
 90    """
 91    Verifies independence of proofs across a Utreexo forest.
 92    Each tree is validated in isolation; no cross-tree replay allowed.
 93    """
 94    for tree_proof in forest_proofs:
 95        if not verify_single_tree_proof(
 96            tree_proof.leaves,
 97            tree_proof.hashes,
 98            tree_proof.bitmap,
 99            tree_proof.expected_root
100        ):
101            return False
102    return True

El vie, 9 de ene de 2026, 5:54 p. m., murchandamus @.***> escribió:

@.**** commented on this pull request.

Hello Lucas,

I don’t think I have seen this idea discussed on the Bitcoin mailing list. Could you please provide the link to the thread where your idea was previously discussed? The document has various formatting issues, and at first glance, the text doesn’t seem to align well with the Utreexo proposals that are being discussed in #1923 https://github.com/bitcoin/bips/pull/1923. Could you please tell us a little more about your process and how your proposal fits into the bigger picture regarding Utreexo?

— Reply to this email directly, view it on GitHub https://github.com/bitcoin/bips/pull/2079#pullrequestreview-3645542856, or unsubscribe https://github.com/notifications/unsubscribe-auth/BUSRMZC2XA3O3C3XR7ZE2HT4GAIPLAVCNFSM6AAAAACRHFG7NOVHI2DSMVQWIX3LMV43YUDVNRWFEZLROVSXG5CSMV3GSZLXHMZTMNBVGU2DEOBVGY . You are receiving this because you authored the thread.Message ID: @.***>

murchandamus commented at 10:52 pm on January 9, 2026: contributor

Yes, BIP ideas should be discussed on the mailing list first.

Also, whatever process may be used to compile a document, it is upon the author to ensure that their proposal is clear and comprehensive, an obvious net improvement, and of high quality. This document has severe quality issues, and leaves me with the impression that it was LLM generated. Please don’t waste our time.

murchandamus closed this on Jan 9, 2026

murchandamus removed the label New BIP on Jan 9, 2026

BIP Draft: Optimal Batch Proofs for Utreexo #2079