Meta issue for potential improvements to SSZ parital proofs
- Dominant language
- Python
- Stars
- 19
- Forks
- 15
- PR merge metrics
- No merged PRs in 30d
Description
## What was wrong?
Partial SSZ proofs are being implemented in #142 (TODO, more PRs). There are a few areas that could benefit from potential optimizations. This issue tracks those.
## What can it be improved?
### Use `bitarray` library for tree paths
The [`bitarray`](https://pypi.org/project/bitarray/) library looks like a solid fast implementation of bit-arrays. The API might be cleaner, and we might get some performance benefits as well. A benchmarking suite should be in place to measure performance before tackling this.
### Better stream decoding of proofs
Currently the stream decoding can exit cleanly on a condition that should raise an exception. The `ProofElement.deserialize` should be adjusted to allow callers to differentiate between:
- stream is empty (exit without error)
- stream is not empty, but in trying to parse the element the stream becomes empty (should exit with error).
Initial idea for doing this relatively simply would be to wrap the `stream: IO[bytes]` in something that allows you to *peek* and see if the stream is empty or not.
### `Proof.hash_tree_root` is a foot gun :foot: :gun:
The `Proof.hash_tree_root` property doesn't necessarily reflect the actual merkle root. This API is currently a foot-gun since it'd be easy to forget to validate the proof object. We should address this.
### Generation of `ProofTree` cost
We should look into the actual cost of tree generation. The current algorithm is recursive which incurs a high cost of many call frames. First step is to benchmark this, after which we can optimize the algorithm.
### `Proof.serialize` doesn't need to generate the tree
We should adjust `Proof.serialize` to avoid genration of the `ProofTree` since it should be possible to serialize the proof without generating the tree.
### Optimizations for chunking and computation of the `hash_tree_root`
Our "chunking" approach could probably be optimized by splitting up two different use cases.
We could have a highly optimized `compute_hash_tree_root` function that operates on a stream and merklizes as it goes. The current approach of computing all chunks, and then merklizing has an O(N) memory footprint. This should be reducable to something like O(log(n)) if we are continually grouping and merklizing as we process the stream.
Similarly, we can optimize the creation of partial proofs. Currently, we compute a full proof and then trim it down to a partial proof. We should instead be able to use the above approach of streaming the chunks and merklizing them as we go to reduce the overall computation needed for partial proof computation. We avoid ever creating the full proof and instead directly create the partial proof from the raw data. This allows us to use the streaming approach to chunk and merklize the parts of the data that are not used by the partial proof.
### Compression
We aren't using any compression at this stage. We should try using `snappy` to compress serialized proofs and see if we can squeeze out some extra bytes.
### Better benchmarking
We should update the benchmarking test suite to also test using "real" data. This will be especially important if we implement compression because currently we're using a lot of random data which isn't going to compress well. Real data will have more parts that actually compress.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the partial SSZ proof work in #142 and the benchmarking suite mentioned in this issue. Investigate the listed areas separately, including ProofElement.deserialize, Proof.hash_tree_root, ProofTree generation, Proof.serialize, chunking, compression, and real-data benchmarks; this meta issue has no single completion target.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- backend, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 18/100