nervosnetwork / sparse-merkle-tree

46 stars 37 forks source link

feat: extract compiled proof for sub leaves #27

Closed TheWaWaR closed 2 years ago

quake commented 2 years ago

this replay with callback solution looks good to me, but I think current implementation can still be optimized for non-existent proofs, and with an is_last_op_merge_zero flag, we can make the proof generated by extract_proof fn the same size as the directly generated one by merkle_proof.

Here is the pseudo code (in real code, we should also check the overflow of += 1 and += n)

OpCodeContext::H => {
MergeValue::Value(hash) => {
  if hash.is_zero() {
    if is_last_op_merge_zero {
      *sub_proof.last_mut() += 1;
    }
  }
}

OpCodeContext::O => {
  if is_last_op_merge_zero {
    *sub_proof.last_mut() += n;
  }
}

We may add a checking to the fn test_sub_proof to verify this optimization:

        let sub_keys: Vec<_> = data.iter().filter_map(|(k, _v)| ...);
        let sub_merkle_proof = smt.merkle_proof(sub_keys).unwrap();
        assert_eq!(sub_merkle_proof.compile(sub_keys).0, sub_proof.0);