Skip to content
This repository has been archived by the owner on Oct 23, 2022. It is now read-only.

DAG-CBOR-encoded Ipld::Map does not strictly order keys #492

Open
cdata opened this issue Jan 26, 2022 · 2 comments
Open

DAG-CBOR-encoded Ipld::Map does not strictly order keys #492

cdata opened this issue Jan 26, 2022 · 2 comments
Labels
bug Something isn't working

Comments

@cdata
Copy link
Contributor

cdata commented Jan 26, 2022

Describe the bug
TL;DR Ipld::Map does not strictly order keys, leading to inconsistency in content hashing between this implementation and go-ipfs (and probably others).

Strictness errata for DAG-CBOR, including explicit key order, is detailed here: https://github.com/ipld/ipld/blob/master/specs/codecs/dag-cbor/spec.md#:~:text=The%20keys%20in,order%20sorts%20earlier.

To Reproduce

use ipfs::{ipld::dag_cbor::DagCborCodec, Ipld};
use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::<String, Ipld>::new();
    map.insert("foo".into(), Ipld::Null);
    map.insert("calcium".into(), Ipld::Null);
    map.insert("zesty".into(), Ipld::Null);

    let ipld_map = Ipld::Map(map);
    let bytes = DagCborCodec::encode(&ipld_map);

    println!("Bytes: {:?}", bytes);
}

Output with current (incorrect) implementation:

Ok([163, 103, 99, 97, 108, 99, 105, 117, 109, 246, 99, 102, 111, 111, 246, 101, 122, 101, 115, 116, 121, 246])

Expected behavior

Expected output (created with patched implementation):

Ok([163, 99, 102, 111, 111, 246, 101, 122, 101, 115, 116, 121, 246, 103, 99, 97, 108, 99, 105, 117, 109, 246])

Environment (please complete the following information)

  • Operating system, kernel version where applicable: Pop!_OS 21.10 / 5.15.11-76051511-generic
  • Rust version:

stable-x86_64-unknown-linux-gnu (default)
rustc 1.57.0 (f1edd0429 2021-11-29)

@cdata cdata added the bug Something isn't working label Jan 26, 2022
@vmx
Copy link
Contributor

vmx commented Jan 26, 2022

FYI: there are also test vectors for DAG-CBOR at https://github.com/ipld/codec-fixtures. I'm currently adding a test runner to run them against another IPLD implementation: https://github.com/ipld/codec-fixtures/tree/add-rust

bors bot added a commit that referenced this issue Feb 1, 2022
493: Strict ordering for DAG-CBOR-encoded map keys r=koivunej a=cdata

This change proposes a fix for #492 . `Ipld::Map` keys are sorted according to [the strictness guidelines in the DAG-CBOR spec](https://github.com/ipld/ipld/blob/master/specs/codecs/dag-cbor/spec.md#:~:text=The%20keys%20in,order%20sorts%20earlier.) when encoding them as DAG-CBOR.


Co-authored-by: Chris Joel <[email protected]>
Co-authored-by: Christopher Joel <[email protected]>
@koivunej
Copy link
Collaborator

koivunej commented Apr 1, 2022

Keeping this issue open for a less wasteful implementation which would use a btreemap with correctly sorting keys newtype.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

3 participants