Spec bug: get_ledger_root bit_length() off-by-one yields depth-31 root at power-of-two note-set sizes (consensus-split landmine)

[davidrusu]

get_ledger_root bit_length() off-by-one at power-of-two sizes → depth-31 root → consensus split vs. conforming reimplementations

Repo: spec defect in docs/blockchain/raw/cryptarchia-proof-of-leadership.md (§ "Ledger Root"). The reference Rust implementation and the PoL/PoQ Circom circuits are the correct side; the written pseudocode is wrong.

Summary

get_ledger_root decides how many empty-subtree extension levels to apply using
len(note_set).bit_length(). For any note-set whose size is an exact power of two, bit_length
overcounts the padded balanced-tree height by one, so the extension loop runs one iteration too few
and the function returns a depth-31 root instead of the depth-32 root the protocol uses
everywhere else. A node that computes the ledger root by following this pseudocode literally will
disagree with the deployed implementation (and the depth-32 PoL/PoQ membership circuits) whenever the
live note-set size is a power of two — a consensus split (its leader proofs and block roots will
be rejected by the rest of the network, and vice-versa).

Spec text (lines 113-123)

def get_ledger_root(note_set: list[NoteId]):
    assert(len(note_set) < 2**32)
    ledger_root = get_merkle_root(note_set)        # Merkle root padded to next power of 2
    ledger_root_height = len(note_set).bit_length()   # <-- BUG
    for height in range(ledger_root_height, 32):
        h = Hasher()
        h.update(ledger_root)
        h.update(empty_tree_root(height))
        ledger_root = h.digest()
    return ledger_root

Why it's wrong

get_merkle_root pads to the next power of two, so for a set of n > 0 notes the resulting balanced
tree has height ceil(log2(n)). The extension loop must start from that height. But:

• For n = 2^k: ceil(log2(n)) = k, whereas n.bit_length() = k + 1. The loop then runs
  range(k+1, 32) = 31 - k extensions, giving final depth k + (31 - k) = 31. One short.
• For n not a power of two: ceil(log2(n)) == n.bit_length(), so the loop is correct (depth 32).

Concretely (effective final depth):

n	correct (impl/circuit)	spec pseudocode
1	32	31
2	32	31
3	32	32
4	32	31
8	32	31

Correct side = implementation + circuits

• The note tree always produces a fixed depth-32 root: utxotree/src/merkle.rs
  (TREE_HEIGHT_EXCEPT_ROOT = 32, root is Node::Empty { height: 32 }), with empty_subtree_root
  matching the spec's empty_tree_root recurrence.
• The PoL/PoQ circuits verify a fixed depth-32 membership path
  (zk/proofs/pol/src/wallet_inputs.rs: AGED/LATEST_NOTE_MERKLE_TREE_HEIGHT = 32;
  mantle/pol_lib.circom uses proof_of_membership(32)).

A depth-31 (spec-conforming) root could not be verified by the depth-32 circuits, so the engineering
stack is necessarily depth-32 and the pseudocode is the defective side. Same bit_length shape should
be checked in any analogous root helper.

Suggested fix

Compute the padded balanced-tree height correctly, e.g.:

ledger_root_height = 0 if len(note_set) <= 1 else (len(note_set) - 1).bit_length()
# == ceil(log2(len)) for len >= 1
for height in range(ledger_root_height, 32):
    ...

This yields depth 32 for all sizes (including powers of two), matching the implementation and the
circuits. Recommend adding a worked vector / cross-check in the spec asserting the root for, e.g.,
1, 2, 3, 4, 8 notes equals the depth-32 implementation root.