Optimize performance

[Stentonian]

The performance of the Bulletproofs generation and verification is not something we have full control over in this repo so that is not the topic of this issue.

What we do have full control over is tree construction and path generation / verification. There is likely a bunch of optimization that can be done here if by just using better Rust progamming technique.

Currently the store of the tree is a hashmap but maybe this is not the best data structure to use. Reading material:

• https://users.rust-lang.org/t/how-to-improve-the-performance-when-using-hashmap-with-huge-data-in-rust/44322
• https://users.rust-lang.org/t/hashmap-performance/6476
• https://users.rust-lang.org/t/hashmap-vs-vec-for-integer-lookups/28061
• https://www.reddit.com/r/rust/comments/7mqwjn/hashmapstringt_vs_vecstringt/

There may also be some ways to improve performance by minimizing the amount of data that is copied (rather passing pointers around). Reading material:

• https://www.reddit.com/r/rust/comments/11n32so/which_collections_use_heap_vs_stack/
• https://stackoverflow.com/questions/47179667/is-a-string-array-e-g-string-3-stored-on-the-stack-or-heap
• https://stackoverflow.com/questions/53691012/is-there-any-way-to-allocate-a-standard-rust-array-directly-on-the-heap-skippin

Another thing we can do to improve the tree constructor performance is try to find a pre-defined binary tree data structure that allows sparse trees and a custom merge function. This has been tried before (https://github.com/silversixpence-crypto/dapol/issues/12) and was not fruitful but it might be worth taking another look. It might be useful to read the BTree implementation code to get some inspiration on optimizations.

The thing with the tree is that we need to access it from the bottom up (for inclusion proof calculation), which seems to rule out linked nodes because of Rust's ownership model. But Rc<T> allows for multiple references to the same data. Rc doesn't work when doing concurrency but there seems to be an alternate to use there.

A lot of the structs defined in the code have an underlying 256 piece of data represented as a u8 array. Arrays of this type may be stored on the stack so we need to check that these are actually stored on the heap to prevent stack overflow. We could possibly wrap the values in a Box to make sure they are stored on the heap. Generally the data stored in these u8 arrays does not change, it only needs to change ownership. So the heap seems to be the best place for this data to be stored.

[Stentonian]

Depending on how large the serialized tree is we may want to store only part of the tree. All we need to store really are the bottom-layer leaf nodes, but this means we have to reconstruct the tree each time we want to generate an inclusion proof. We could store the top n layers as well as the bottom layer, which would save on some of the construction time.

[Stentonian]

Interesting to note that de-referencing a heap variable well copy it to the stack (at least for a box): https://doc.rust-lang.org/rust-by-example/std/box.html

If you do the same memory check with a vector you see that it takes 24 bytes on the stack no matter how many elements you push to it:

    use std::mem;
    let mut a = Vec::<Coordinate>::new();
    for i in 0..10000 {
        a.push(Coordinate {
            x: i,
            y: i as u8,
        });
    }
    println!("Vec occupies {} bytes on the stack",
             mem::size_of_val(&a));

[Stentonian]

A note from inside single_threaded::build_node

                // TODO may be able to further optimize by leaving out the padding leaf nodes
                // from the store.
                // Only insert nodes in the store if
                // a) node is a bottom layer leaf node (including padding nodes)
                // b) node is in one of the top X layers where X = store_depth
                // NOTE this includes the root node.

[Stentonian]

A note from multi_threaded::get_num_nodes_left_of

// TODO can be optimized using a binary search

[Stentonian]

Serialization/deserialization of the tree might be too slow at the input sizes we will be operating the code on, so it might be a good idea to try using a database as storage of the tree nodes as apposed to a hashmap. Some further details on other options here: https://github.com/silversixpence-crypto/dapol/issues/68

Also:

• https://users.rust-lang.org/t/fastest-way-to-save-and-load-a-hashmap/55091/4

[Stentonian]

https://github.com/silversixpence-crypto/dapol/issues/137

[Stentonian]

Ideally we should move the storage of nodes to a database. It will allow instant save & load of the tree, at the cost of being more expensive to build.