vacp2p / zerokit

A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments.
Apache License 2.0
130 stars 7 forks source link

Incorrect behaviour of trees in override_range function #248

Closed seemenkina closed 3 months ago

seemenkina commented 3 months ago

1. Full Merkle Tree and Optimal Merkle Tree

This condition will not work correctly if the number of items to insert is less than the number of items to delete

https://github.com/vacp2p/zerokit/blob/4931b252378623bcc6f005164950710d152ee600/utils/src/merkle_tree/full_merkle_tree.rs#L181

At the same time the same behaviour is implemented correctly in PmTree:

https://github.com/vacp2p/zerokit/blob/4931b252378623bcc6f005164950710d152ee600/rln/src/pm_tree_adapter.rs#L287-L288

let leaves_new: Vec<TestFr> = (0..2).map(TestFr::from).collect();
tree.override_range(0, leaves_new.clone(), [0, 1, 2, 3]).unwrap();

2. PmTree

Doesn't work correctly behaviour when we need to put leaves further away than deleted items because of this line:

https://github.com/vacp2p/zerokit/blob/4931b252378623bcc6f005164950710d152ee600/rln/src/pm_tree_adapter.rs#L303-L304

and here should be start instead of min_index

For example: if we want to write data in indices [4..8] and delete data in indices [0..4], the data will be written from index 0 instead of 4.

Example for testing:

let leaves: Vec<Fr> = (0..4).map(|s| Fr::from(s as i32)).collect();
tree.override_range(4, leaves.clone(), [0, 1, 2, 3]).unwrap();
rymnc commented 3 months ago

addressed in https://github.com/vacp2p/zerokit/pull/250