Reachable unwrap panic in ics23_prove
Description
The ics23_prove function attempts to generate an ICS-23 proof↗ of membership or nonmembership of a given key in Grug's state based on whether or not the key is present or absent.
It checks if there is a corresponding value for the key in the state_storage RocksDB table, and if there is, it returns a proof of membership. However, if there is no corresponding value, it will attempt to generate a nonmembership proof, which consists of membership proofs for neighboring keys that would be adjacent to the given key if it were present.
To find these neighboring keys, it attempts to query the preimages RocksDB table (which contains mappings from hashes of keys to keys) to find the next and previous keys to the queried key ordered by hash value. It then obtains the value of those keys in the state_storage table, assuming they exist, and generates membership proofs for them.
...
let proof = match state_storage.read(&key) {
// Value is found. Generate an ICS-23 existence proof.
Some(value) => CommitmentProofInner::Exist(generate_existence_proof(key, value)?),
// Value is not found.
//
// Here, unlike Diem or Penumbra's implementation, which walks the
// tree to find the left and right neighbors, we use an approach
// similar to SeiDB's:
// https://github.com/sei-protocol/sei-db/blob/v0.0.43/sc/memiavl/proof.go#L41-L76
//
// We simply look up the state storage to find the left and right
// neighbors, and generate existence proof of them.
None => {
let cf = cf_preimages(&self.inner.db);
let key_hash = key.hash256();
let opts = new_read_options(Some(version), None, Some(&key_hash));
let left = self
.inner
.db
.iterator_cf_opt(&cf, opts, IteratorMode::End)
.next()
.map(|res| {
let (_, key) = res?;
let value = state_storage.read(&key).unwrap();
generate_existence_proof(key.to_vec(), value)
})
.transpose()?;
let opts = new_read_options(Some(version), Some(&key_hash), None);
let right = self
.inner
.db
.iterator_cf_opt(&cf, opts, IteratorMode::Start)
.next()
.map(|res| {
let (_, key) = res?;
let value = state_storage.read(&key).unwrap();
generate_existence_proof(key.to_vec(), value)
})
.transpose()?;
CommitmentProofInner::Nonexist(NonExistenceProof { key, left, right })
},
};
...However, the commit function can delete the keys and values inserted in the state_storage and state_commitment tables without deleting their corresponding key hashes in the preimages table.
...
// Writes in state commitment
let cf = cf_state_commitment(&self.inner.db);
for (key, op) in pending.state_commitment {
if let Op::Insert(value) = op {
batch.put_cf(&cf, key, value);
} else {
batch.delete_cf(&cf, key);
}
}
// Writes in state storage (note: don't forget timestamping)
let cf = cf_state_storage(&self.inner.db);
for (key, op) in pending.state_storage {
if let Op::Insert(value) = op {
batch.put_cf_with_ts(&cf, key, ts, value);
} else {
batch.delete_cf_with_ts(&cf, key, ts);
}
}
...Because of this, the keys can be absent from the state_storage table despite the preimages remaining present, causing the unwraps to panic in the process of finding the neighboring nodes.
This is demonstrated by the following test:
#[test]
fn ics23_prove_delete() {
let path = TempDataDir::new("_grug_disk_db_ics23_delete");
let db = DiskDb::open(&path).unwrap();
let (_, maybe_root) = db.flush_and_commit(Batch::from([
(b"m".to_vec(), Op::Insert(b"m".to_vec())), (b"a".to_vec(), Op::Insert(b"a".to_vec()))
])).unwrap();
let root = maybe_root.unwrap().to_vec();
let to_prove = b"L";
let (_, maybe_root) = db.flush_and_commit(Batch::from([(b"a".to_vec(), Op::Delete)])).unwrap();
let root = maybe_root.unwrap().to_vec();
let proof = db.ics23_prove(to_prove.to_vec(), None).unwrap();
println!("{:?}", proof);
assert!(ics23::verify_non_membership::<HostFunctionsManager>(&proof, &ICS23_PROOF_SPEC, &root, to_prove));
}Impact
As nonmembership proofs are requested in the process of handling ICS-4 packet time-outs, this will result in periodic crashes / denial of service whenever the hash of a packet-receipt path is adjacent to a deleted key.
Additionally, the use of SeekToLast with an upper bound smaller than the last key is undefined by RocksDB↗, and this is the current behavior with set_iterator_upper_bound (in new_read_options) and IteratorMode::End.
Recommendations
We recommend addressing the panic by using .find_map in place of .next().map, with error handling changed to skip over preimages that are no longer present in the state, and addressing the RocksDB undefined behavior by using IteratorMode::From and not using lower and upper bounds.
The following patch applies the above suggestions to ics23_prove:
let cf = cf_preimages(&self.inner.db);
let key_hash = key.hash256();
-let opts = new_read_options(Some(version), None, Some(&key_hash));
+let opts = new_read_options(Some(version), None, None);
let left = self
.inner
.db
- .iterator_cf_opt(&cf, opts, IteratorMode::End)
- .next()
- .map(|res| {
- let (_, key) = res?;
- let value = state_storage.read(&key).unwrap();
- generate_existence_proof(key.to_vec(), value)
+ .iterator_cf_opt(&cf, opts, IteratorMode::From(&key_hash, rocksdb::Direction::Reverse))
+ .find_map(|res| {
+ let key = match res {
+ Ok((_, key)) => key,
+ Err(e) => return Some(Err(DbError::from(e))),
+ };
+ let value = state_storage.read(&key)?;
+ Some(generate_existence_proof(key.to_vec(), value))
})
.transpose()?;
-let opts = new_read_options(Some(version), Some(&key_hash), None);
+let opts = new_read_options(Some(version), None, None);
let right = self
.inner
.db
- .iterator_cf_opt(&cf, opts, IteratorMode::Start)
- .next()
- .map(|res| {
- let (_, key) = res?;
- let value = state_storage.read(&key).unwrap();
- generate_existence_proof(key.to_vec(), value)
+ .iterator_cf_opt(&cf, opts, IteratorMode::From(&key_hash, rocksdb::Direction::Forward))
+ .find_map(|res| {
+ let key = match res {
+ Ok((_, key)) => key,
+ Err(e) => return Some(Err(DbError::from(e))),
+ };
+ let value = state_storage.read(&key)?;
+ Some(generate_existence_proof(key.to_vec(), value))
})
.transpose()?;Additionally, we recommend removing keys from the preimages table when they are removed from the state_storage table to conserve space and improve the efficiency of iterating to find neighboring nodes.
Remediation
This issue has been acknowledged by Left Curve Software Ltd., and fixes were implemented in the following commits: