ipld / ipld/py-ipld-dag

DAG-PB encoder doesn't sort links by Name — violates DAG-PB spec

Open Beginner friendly
#23 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
13
Forks
9
PR merge metrics
No merged PRs in 30d

Description

The DAG-PB specification requires that links be sorted by Name (byte-wise), with named links before unnamed links. `_encode_pb_node()` writes links in the order they appear in the input list without sorting, producing non-canonical output that may not match other implementations.

### Problem

In `dag/codecs/dag_pb.py`:

```python
def _encode_pb_node(node: PBNode) -> bytes:
parts: list[bytes] = []

for link in node.links: # ← Links written in input order
link_bytes = _encode_pb_link(link)
parts.append(_encode_length_delimited(2, link_bytes))

if node.data is not None:
parts.append(_encode_length_delimited(1, node.data))

return b"".join(parts)
```

The [DAG-PB spec](https://ipld.io/specs/codecs/dag-pb/spec/) states:

> "Links MUST be sorted by Name (byte-wise). Links without a Name MUST come after all named links."

This means:

```python
# These two nodes should produce identical bytes, but don't:
node1 = PBNode(links=[
PBLink(hash=cid_b, name="beta"),
PBLink(hash=cid_a, name="alpha"),
])
node2 = PBNode(links=[
PBLink(hash=cid_a, name="alpha"),
PBLink(hash=cid_b, name="beta"),
])

encode(node1) != encode(node2) # BUG: should be equal
```

### Proposed Solution

Sort links before encoding:

```python
def _encode_pb_node(node: PBNode) -> bytes:
parts: list[bytes] = []

# Sort links: named links first (by name, byte-wise), then unnamed links
def link_sort_key(link: PBLink) -> tuple[int, bytes]:
if link.name is not None:
return (0, link.name.encode("utf-8"))
return (1, b"") # Unnamed links come after all named links

sorted_links = sorted(node.links, key=link_sort_key)

for link in sorted_links:
link_bytes = _encode_pb_link(link)
parts.append(_encode_length_delimited(2, link_bytes))

if node.data is not None:
parts.append(_encode_length_delimited(1, node.data))

return b"".join(parts)
```

Add tests verifying that differently-ordered links produce identical output.

### Related

- DAG-PB spec: https://ipld.io/specs/codecs/dag-pb/spec/
- File: `dag/codecs/dag_pb.py`

Contributor guide

Open the contributing guide

Research direction

Start in dag/codecs/dag_pb.py at _encode_pb_node() and review how node.links are emitted. Add coverage for differently ordered named links and unnamed links, then run the relevant DAG-PB codec tests. Done means link order is canonical and equivalent input nodes produce identical encoded bytes.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
88/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.