Trie.get()/Trie.find() does not return data, but the data is present.

[iclighthouse]

We had this issue during a stress test. orders used the Trie module and had a total of 798 records.

Only this data was encountered unreadable, most of the other data can be read normally.

canister-id: ynbvm-hiaaa-aaaak-adbqa-cai

1. Can get the data using Trie.filter().
   code:

private func keyb(t: Blob) : Trie.Key<Blob> { return { key = t; hash = Blob.hash(t) }; };

public query func testTrieFilter() : async TrieList<Txid, TradingOrder>{
        let _txid : Text = "000000c28ca1e305eeaeaccdd069e91a45f9668d6a3407e31a5c0db7c9372b28"; // blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+("
        var txid : Blob = Blob.fromArray([]);
        switch(Hex.decode(_txid)){
            case(#ok(r)){ txid := Blob.fromArray(r); };
            case(_){};
        };
        var trie = icdex_orders;
        let page = 1;
        let size = 10;
        trie := Trie.filter<Txid, TradingOrder>(trie, func (k:Txid, v:TradingOrder): Bool{ 
            k == txid; 
        });
        return trieItems<Txid, TradingOrder>(trie, page, size);
    };

execute:
dfx canister --network ic call ynbvm-hiaaa-aaaak-adbqa-cai testTrieFilter
returns:

(
  record {
    total = 1 : nat;
    data = vec {
      record {
        blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+(";
        record {
          fee = record { fee0 = 0 : nat; fee1 = 0 : nat };
          gas = record { gas0 = 0 : nat; gas1 = 0 : nat };
          status = variant { Pending };
          toids = vec {};
          data = null;
          time = 1_668_476_725_633_900_968 : int;
          txid = blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+(";
          icrc1Account = opt record {
            owner = principal "vlpmr-zi3rn-n6nwy-qx6jf-snrkm-nwoje-jghma-7j3lv-irskf-yojl3-eqe";
            subaccount = null;
          };
          orderType = variant { LMT };
          filled = vec {};
          expiration = 1_676_252_725_633_900_968 : int;
          nonce = 194 : nat;
          account = blob "\c1\e9\a9\c94\8f\ef\c3\e04\c9\08L\cd\0b\b0\0f\c4\9a\8e\c2\0a\0f\89\14\b2\a5R\f3\c3P\bc";
          remaining = record {
            quantity = variant { Sell = 100_000_000 : nat };
            price = 300 : nat;
          };
          index = 940 : nat;
          orderPrice = record {
            quantity = variant { Sell = 100_000_000 : nat };
            price = 300 : nat;
          };
          refund = record { 0 : nat; 0 : nat; 0 : nat };
        };
      };
    };
    totalPage = 1 : nat;
  },
)

2. Can get the data using Trie.mapFilter().
   code:

public query func testTrieMapFilter() : async TrieList<Txid, TradingOrder>{
        let _txid : Text = "000000c28ca1e305eeaeaccdd069e91a45f9668d6a3407e31a5c0db7c9372b28"; // blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+("
        var txid : Blob = Blob.fromArray([]);
        switch(Hex.decode(_txid)){
            case(#ok(r)){ txid := Blob.fromArray(r); };
            case(_){};
        };
        var trie = icdex_orders;
        let page = 1;
        let size = 10;
        trie := Trie.mapFilter<Txid, TradingOrder, TradingOrder>(trie, func (k:Txid, v:TradingOrder): ?TradingOrder{ 
            if (k == txid){
                return ?v;
            }else { return null; }; 
        });
        return trieItems<Txid, TradingOrder>(trie, page, size);
    };

execute:
dfx canister --network ic call ynbvm-hiaaa-aaaak-adbqa-cai testTrieMapFilter
returns:

(
  record {
    total = 1 : nat;
    data = vec {
      record {
        blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+(";
        record {
          fee = record { fee0 = 0 : nat; fee1 = 0 : nat };
          gas = record { gas0 = 0 : nat; gas1 = 0 : nat };
          status = variant { Pending };
          toids = vec {};
          data = null;
          time = 1_668_476_725_633_900_968 : int;
          txid = blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+(";
          icrc1Account = opt record {
            owner = principal "vlpmr-zi3rn-n6nwy-qx6jf-snrkm-nwoje-jghma-7j3lv-irskf-yojl3-eqe";
            subaccount = null;
          };
          orderType = variant { LMT };
          filled = vec {};
          expiration = 1_676_252_725_633_900_968 : int;
          nonce = 194 : nat;
          account = blob "\c1\e9\a9\c94\8f\ef\c3\e04\c9\08L\cd\0b\b0\0f\c4\9a\8e\c2\0a\0f\89\14\b2\a5R\f3\c3P\bc";
          remaining = record {
            quantity = variant { Sell = 100_000_000 : nat };
            price = 300 : nat;
          };
          index = 940 : nat;
          orderPrice = record {
            quantity = variant { Sell = 100_000_000 : nat };
            price = 300 : nat;
          };
          refund = record { 0 : nat; 0 : nat; 0 : nat };
        };
      };
    };
    totalPage = 1 : nat;
  },
)

3. Cannot query the data using Trie.get()
   code:

public query func testTrieGet() : async OrderStatusResponse{
        let _txid : Text = "000000c28ca1e305eeaeaccdd069e91a45f9668d6a3407e31a5c0db7c9372b28"; // blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+("
        var txid : Blob = Blob.fromArray([]);
        switch(Hex.decode(_txid)){
            case(#ok(r)){ txid := Blob.fromArray(r); };
            case(_){};
        };
        switch(Trie.get(icdex_orders, keyb(txid), Blob.equal)){
            case(?(order)){ return #Pending(order); };
            case(_){ return #None; };
        };
    };

execute:
dfx canister --network ic call ynbvm-hiaaa-aaaak-adbqa-cai testTrieGet
returns:

(variant { None })

It is also

(variant { 870_530_776 })

4. Cannot query the data using Trie.find()
   code:

public query func testTrieFind() : async OrderStatusResponse{
        let _txid : Text = "000000c28ca1e305eeaeaccdd069e91a45f9668d6a3407e31a5c0db7c9372b28"; // blob "\00\00\00\c2\8c\a1\e3\05\ee\ae\ac\cd\d0i\e9\1aE\f9f\8dj4\07\e3\1a\5c\0d\b7\c97+("
        var txid : Blob = Blob.fromArray([]);
        switch(Hex.decode(_txid)){
            case(#ok(r)){ txid := Blob.fromArray(r); };
            case(_){};
        };
        switch(Trie.find(icdex_orders, keyb(txid), Blob.equal)){
            case(?(order)){ return #Pending(order)};
            case(_){ return #None; };
        };
    };

execute:
dfx canister --network ic call ynbvm-hiaaa-aaaak-adbqa-cai testTrieFind
returns:

(variant { None })

It is also

(variant { 870_530_776 })

[iclighthouse]

Environment:
MacBook
dfx 0.11.2

[matthewhammer]

Thanks for reporting.

Could you try testing to see if the Trie invariants are being broken somehow?

If the find algorithm (which is dead simple) cannot find the item, but it's actually there (via filter, etc) then it seems likely that something is breaking the structural invariants of the trie itself, so it no longer represents the right thing.

There's a public function called isValid that was written long ago. It should be used in the unit tests, but is not. (Here's a small step towards correcting that.)

Could you experiment with that test within your tests (ideally after after change)? If it's violated at some point, then we know what change to the Trie corrupted the structural invariants, making items impossible to find.

Alternatively, if you post your entire test script, I could try to insert the uses of isValid myself.

[matthewhammer]

As I consider the possible causes, I have an additional check I'd make of the code, if I could:

Namely, that there are no mutations to the objects in the Trie. (The objects in the trie are immutable).

Or, if they are mutated, then the mutated fields do not affect their hash or equality relationships. (If this is violated, it would explain the behavior you have now).

[crusso]

As I consider the possible causes, I have an additional check I'd make of the code, if I could:

Namely, that there are no mutations to the objects in the Trie. (The objects in the trie are immutable).

Or, if they are mutated, then the mutated fields do not affect their hash or equality relationships. (If this is violated, it would explain the behavior you have now).

@matthewhammer do you mean the keys, or the values? The keys here appear to be Blobs, thus immutable.

[matthewhammer]

I mean the keys. The values are not relevant for any of the structural invariants of the Trie.

It is the hash of the keys that matters, where the bits of the hash determine the Trie's shape. (The trie uses these bits as needed, depending on its total size; so for n items, log_2(n) bits are used.)

If the key were to mutate, the placement in the tree would be "wrong" and would not help when locating it based on its (new) hash value.

It's also important (but not relevant for this issue) that the hash be "mostly injective", sending different keys to different hashes, almost always. There is a little tolerance for collisions, but it's "small" (like eight per hash value).

The keys here appear to be Blobs, thus immutable.

Why are they using the var keyword in these snippets?

[iclighthouse]

public query func testTrieValid() : async Bool{
        return Trie.isValid(icdex_orders, true);
    };

returns :

(false)

[iclighthouse]

If a Canister (e.g. a token) with a lot of data encounters this problem, how do I fix it?

[iclighthouse]

Possible causes.
Cycles are heavily pre-charged during stress tests, and then Cycles are mostly returned as the executions continue to complete.
Trie's should be broken when there were not enough Cycles are pre-charged and the system did not report an error. This situation is not really a lack of available Cycles.

[chenyan-dfinity]

Trie's should be broken when there were not enough Cycles are pre-charged and the system did not report an error.

I think in this case, the system will still report an error as not enough cycle.

[nomeata]

There is a little tolerance for collisions, but it's "small" (like eight per hash value).

What happens when you have more than 8 keys with the same hash value?

[iclighthouse]

A hash value has 4 bytes? (I think that's a little small)

So, what is the safe capacity that a Trie can store?
Errors in smart contracts due to hidden restrictions can be very costly. If such restrictions are not explicitly pointed out and the dapps that encounter such limitations should have a large number of users and assets, then the damage to the ecosystem will be significant.

[nomeata]

Yes, especially as the Hash functions used are rather … naive, so it is likely that collisions can be actively provoked by an attacker. It’s already bad enough if performance degrades in that case (and that alone might be reason enough not to use a hash-based data structure in code under threat), but silent functional breakage is of course intolerable, and would be very embarrassing, to put it mildly…