provider-storage: turn StoredNode into a leaf/internal enum, validate children

[!NOTE]
This issue description is AI-generated (drafted and then re-validated against the code at 4ac8da65). File/line references and claims were checked at that commit, but please double-check and validate everything yourself before starting work — the code may have moved, and the design decisions below are proposals, not settled.

Motivation

StoredNode stores redundant bytes and accepts internally inconsistent data from clients. Its layout is about to be pinned as an on-disk format by the compatibility tests from #365, so reshaping it is cheap now — before any release ships provider data — and a #375-style migration afterwards.

Current state

• StoredNode { data: Vec<u8>, children: Option<Vec<H256>> } (crates/providers/storage/src/backend/mod.rs:57-64) is SCALE-encoded into RocksDB CF_NODES under key blake2_256(data) (backend/rocksdb.rs:270-277); children only tags leaf vs internal for traversal.
• An internal node's hash is hash_children(l, r) = blake2_256(l ‖ r) (crates/primitives/storage/src/lib.rs:501-506), so data must equal l ‖ r — children duplicates the same 64 bytes. A two-child internal node encodes to 132 B (2+64 for data, 1+1+64 for children) where 66 B (Internal(Vec<H256>)) would do.
• store_node (backend/rocksdb.rs:203-243) validates two things: blake2_256(data) == expected_hash, and that every non-zero child hash already exists in CF_NODES (Error::ChildrenMissing). What it does not check is that children is consistent with data. So a node whose children disagree with its preimage is stored silently — the hash check passes on data, the existence check passes on unrelated-but-present hashes — and traversal (collect_chunks, collect_chunk_hashes, calculate_tree_size) then follows the wrong children. Clients supply children over the wire: PUT /node (provider-node/src/api.rs:284-308) and replica_sync.rs:154-172.
• The design (docs/design/scalable-web3-storage.md:931-937, originally paritytech/polkadot-sdk#10731) models an internal node as just its child hashes.

Proposed solution

/// A node in a bucket's content-addressed chunk tree.
pub enum StoredNode {
    /// Leaf: hash = blake2_256(data)
    Chunk(Vec<u8>),
    /// Internal: hash = blake2_256(concat(children))
    Internal(Vec<H256>),
}

• The internal preimage is derived (concat(children)), and store_node verifies blake2_256(concat(children)) == hash — a data/children mismatch becomes unrepresentable and inconsistent uploads are rejected instead of silently stored.
• Upload wire API unchanged: the handler maps data + children | null into the enum. The download path is not free, see the TODO below.
• CF_NODES layout changes — update the compatibility tests from #365 in the same PR as a deliberate format break.

While at it, think about:

• a better name — e.g. ChunkTreeNode or Node.
• a better shape — e.g. Internal([H256; 2]) since the provider builds the tree from binary pairs. Note this is not currently an invariant on the wire (see the odd-level client bug below), so fixing the arity at 2 pulls that fix into this PR; Internal(Vec<H256>) keeps the two changes separable.

TODO

• Turn StoredNode into the enum; derive the internal preimage instead of storing it
• Decide name and final shape
• Validate internal nodes in store_node (hash over concatenated children)
• Map the wire request into the enum (api.rs, replica_sync.rs)
• Reconstruct data on the download path: DownloadNodeResponse.data is built from node.data (provider-node/src/api.rs:246-254, and :699). With a derived preimage it must be rebuilt as concat(children) for internal nodes, or replica_sync peers and storage_user::read_node receive an empty data.
• Decide quota accounting: store_node charges data.len() to bucket.used_bytes (backend/rocksdb.rs:271, 280), so every internal node currently costs 64 B of the agreement quota. Dropping the stored preimage silently changes quota semantics unless we deliberately keep charging 32 * children.len(). Make it an explicit choice, not a side effect.
• Simplify build_padded_merkle_tree (backend/mod.rs:265-276), which hand-builds node_data right next to the same children
• Update the compatibility tests (note the current stored_node golden fixture in backend/rocksdb.rs:797-820 uses a single-child children, which is unrepresentable under an [H256; 2] shape)
• Optional #375 seed: write + check a format-version byte in CF_METADATA on DB open

Adjacent bug found while validating (fix here or file separately)

StorageUser::build_merkle_tree_on_provider (clients/storage/src/storage_user.rs:552-579) promotes odd levels: for a trailing lone node it sets parent_hash = pair[0] but still uploads a node with data = pair[0].as_bytes() (32 B) and children = Some([pair[0]]). Since blake2_256(data) != pair[0], store_node already rejects this today with InvalidHash — meaning any upload whose chunk count makes a level odd (≥3 chunks with fixed chunking, storage_user.rs:490-499) fails.

It also means the client and the provider build different trees for the same leaves: the client promotes odd nodes, while build_padded_merkle_tree pads with H256::zero() to the next power of two. This must be resolved before fixing the internal-node arity at 2.

Related

• #365 — bincode → parity-scale-codec, compatibility tests
• #375 — provider storage format versioning/migrations
• Out of scope, separate design question: no leaf/internal domain separation in chunk-tree hashing (blake2_256 without a 0x00/0x01 prefix) — root-breaking, needs its own decision