SMT: Ideds about SMT Implementation Optimization

[hsyodyssey]

Hi friends, I have a small question about the SMT codebase. 

Since the logic of mt.updateWord and mt.updateVarWord functions are basically the same, I will take mt.updateWord as an example.

To my understanding, in the tree update process, the function call chains when facing a new node are as follows:

1. First, we call mt.updateWord and then call mt.Update.
   proof, err := mt.Update(k, v, kPreimage, vPreimage[:])
2. In the mt.Update function, we first go through the MT by the mt.GetNode function. 
   n, err := mt.GetNode(nextKey)
3. If the key is not found, we return to the mt.updateWord function, then call MT. Add function to add a new node to the MT. 
4. In the mt.Add function, we call the mt.addLeaf function to add the lead node.
   newNodeLeaf := NewNodeLeaf(kHash, vHash, kPreimage, vPreimage)

However, we can see that there are two parts that should be duplicated in the current codebase.

1. There are three hash calls may be duplicated.
   We can observe that the mt.Update and mt.Add have the same agruments when we call MT.updateWord function.

        // mt.Update and mt.Add have the same agruments.
     	proof, err := mt.Update(k, v, kPreimage, vPreimage[:])
	if err == ErrKeyNotFound {
		err = mt.Add(k, v, kPreimage, vPreimage[:])
		return nil, err
	}

Hence, the values of kHash, vHash, and path should be the same both in Update and Add.

func (mt *MerkleTree) Update(k, v *big.Int, kPreimage *smt.Byte32, vPreimage []byte) (*CircomProcessorProof, error) {
        ...
	kHash := smt.NewHashFromBigInt(k)
	vHash := smt.NewHashFromBigInt(v)
	path := getPath(mt.maxLevels, kHash[:])
        ...
}

func (mt *MerkleTree) Add(k, v *big.Int, kPreimage *smt.Byte32, vPreimage []byte) error {
...
	kHash := smt.NewHashFromBigInt(k)
	vHash := smt.NewHashFromBigInt(v)
	newNodeLeaf := NewNodeLeaf(kHash, vHash, kPreimage, vPreimage)
	path := getPath(mt.maxLevels, kHash[:])
...
}

2. MT's duplicate visits. We already went through the MT in the mt.Update function, but we go through the MT in the mt.addLeaf again.

         // mt.Update function accesses the MT from the root node.
	nextKey := mt.rootKey
	siblings := []*smt.Hash{}
	for i := 0; i < mt.maxLevels; i++ {
		n, err := mt.GetNode(nextKey)
                 ...
        }

        // mt.addLeaf function also starts from the mt.rootKey
	newRootKey, err := mt.addLeaf(tx, newNodeLeaf, mt.rootKey, 0, path)

I think the mt.GetNodefunction called in both mt.Update and mt.addLeaf is costly, since it will call mt.db.Get (key [:]), which is currently called leveldb every time it is invoked.

I have some simple ideas:

1. We can reuse the kHash, vHash, and path computed in mt.Update function.
2. We could establish a memory database for MT, then we could go through the memory instead of the disk.

After finishing all the main workflow functions, we may need to think about how to reduce the potential number of levelDB calls, since the disk I/O is costly.

Please let me know if I have misunderstood anything.

[lispc]

agree. A lot of tech debt in tree codes. We should revisit these sub-optimal codes later.