ethereum / ethereum/ddht

Meta issue for potential improvements to SSZ parital proofs

Open
#143 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.