In the current proof verification implementation, it is never asserted, that the tree was traversed all the way down to the leaf nodes.
The tree is fully traversed, if the entire key/path has been processed, so all 251 bits. Not traversing all the way until the end of the key, allows an attacker to verify arbitrary edge nodes that are in the original path of the key.

This behaviour can be prevented, by ensuring the remaining_key parameter is 0 after all proof nodes have been processed. Otherwise it is possible to truncate the proof path, verifying an incorrect value as a result.

I have added a PoC of this behaviour here: a935126

Bug Report

Bonsai-trie version: 322af3f

Current behavior:

Double insertion of the same key into a bonsai db without calling commit between insertions results in BonsaiStorageError::Trie("Couldn't fetch node in db").

According to @AurelienFT this could be due to the db trying to access the key to replace it while it hasn't yet been committed to storage.

Expected behavior:

Bonsai db should be able to handle double insertions without having to commit to storage.

Steps to reproduce:

Perform double insertion of the same key into a bonsai db in a single commit.

Related code:

The function currently crashing: preload_node_subtree

feat(storage): Implement a way to handle persisting <contract Trie<keys, values>>

Current behavior:

Currently the Starknet state root is computed using 3 persistent tries:

• Contract trie: A contract trie mapping contract addresses to a hashed representation of its storage containing it's storage root. (we store it in a contract_bonsai_db)
• Storage trie: A storage trie representing the root of a particular contract based on all it's key/value changes along the state (we store it in a storage_bonsai_db)
• Class trie: A class mapping class hashes to their compiled class hashes (we store it in a class_bonsai_db)

For the Contract and Class trie the bonsai lib works correctly.

The problem is regarding the storage trie. With the current lib there is no way to persist storage changes of a specific contract since the key/values associated to it are stored in the storage_bonsai_db without any contract identifier to retrieve them.

Provisory fix

The provisory fix we implemented is that for each Contract were storage changes were detected we retireve all the storage key values associated to store them along with the new changes and recompute the trie in memory. The problem is that it means we need to store the key/values duplicated in our codebase (to persist them with an associated contract) + it is really costly to do so

The goal would be to find an internal solution within the Bonsai-trie lib to this problem.

Bug Report

Bonsai-trie version: 83b2cab

Current behavior:

HashMapDB does not differentiate between leaf and branch nodes during insertion. This is in contrast to RocksDB which stores leaf and branch nodes in different columns (this is handled here using the get_cf method of DatabaseKey). This results in surprising behavior when retrieving keys from HashMapDB for example, since these will also include branch keys.

Expected behavior:

It would be more logical from the user perspective for a difference to be made between leaf and branch nodes in HashMapDB to allow to retrieve only the keys the user themselves inserted into the db.

Steps to reproduce:

1. Create a new BonsaiStorage with a HashMapDb and initialize a dummy tree.
2. Insert multiple nodes & commit.
3. Call get_keys, ignoring the first size byte. You will notice the resulting keys do not only contain those manually inserted.

Related code:

This is what a potential solution to this issue would look like.

fn insert(                                                     
    &mut self,                                                 
    key: &crate::bonsai_database::DatabaseKey,                 
    value: &[u8],                                              
    _batch: Option<&mut Self::Batch>,                          
) -> Result<Option<Vec<u8>>, Self::DatabaseError> {            
    Ok(self.db.insert(key.get_cf().to_vec().extend_from_slice(key.as_slice()), value.to_vec()))
}                                                              

Note that this would mean that any retrieval code would also have to be update accordingly