DAG-PB encoder doesn't sort links by Name — violates DAG-PB spec
- 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
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