ae5f1d2fd7
* added upload status * added changes for progress bar with more logs and bug fixes, Documentation yet to be added * huge changes that need more doucmenting * added possibility to get profile using NodeID * added fix profile listing user profile information * removed profile image from the explore reult struct * saving current changes * added filter to search based on NodeID * Monday bug fixing * updates to the profile * changes for tracing the blockchain profile image not shown * added condition to ensure TAG is not sent and removed debug prints * updated webapi docs
Fragment
This package implements file fragmentation. Files are split into smaller fragments of equal size (except the last one) to make it more convenient to share a file between multiple peers. This approach is similar to how Torrents are dividing files into chunks called "pieces".
All fragments are hashed and organized in a merkle tree. The root hash of this merkle tree is stored together with the fragment size on the blockchain for each file.
Merkle Tree
A good explanation on how merkle trees work is published in the BitTorrent BEP 30. The advantage of using a merkle tree is that each fragment can be verified against the root hash by only providing its sibling and uncle hashes. Receivers can independently verify the validity of the content by using the provided sibling and uncle hashes to generate the root hash and compare it against the known root hash.
This means that only the sender needs to keep the hashes "in the middle" and a pre-data hash list exchange is not needed.
A hash in the tree is generated by concatenating the 2 hashes of its children in binary representation and hashing that aggregate. Blake3 is used as hashing algorithm.
Fragment Size
Files that are stored should be accompanied by a separate file that stores the entire merkle tree (including all leafs and the middle hash). This allows to serve the file and the proof without any computation.
The total number of hashes (including the root hash) is 2*Fragments -1.
Example: If a 4 GB file is split into 1 MB sized fragments, there are 4096 fragments. This means 8191 hashes, requiring at least 256 KB for the accompanying merkle tree file.
Considerations
- Security: Larger fragment sizes increase the size of data to download before detecting an invalid fragment.
- Deduplication: Smaller chunks may result in higher deduplication.
- Streaming: For streaming videos a smaller size would be preferred, otherwise expensive buffering might be required. Larger fragments may result in noticable waiting times for the end user.
- Overhead: The smaller the fragment size, the more fragments, thus more individual pieces to compute. The time when generating the merkle tree initially can be usually neglected (since it only happens once), but too small fragments may result in unnecessary computations when exchanging fragments.
Current Algorithm
The current algorithm identifies static fragment sizes based on the file size per below table.
| File Size (max) | Fragment Size | Max Fragment Count | Merkle Tree File |
|---|---|---|---|
| 256 MB | 256 KB | 1024 | 64 KB |
| 1 GB | 512 KB | 2048 | 128 KB |
| 2 GB | 1 MB | 2048 | 128 KB |
| 4 GB | 2 MB | 2048 | 128 KB |
| 8 GB | 8 MB | 1024 | 64 KB |
| 16 GB | 16 MB | 1024 | 64 KB |
| 32 GB | 32 MB | 1024 | 64 KB |
| 64 GB | 64 MB | 1024 | 64 KB |
| 1 TB | 64 MB | 16384 | 1 MB |
| 2 TB | 128 MB | 16384 | 1 MB |
| 1 PB | 512 MB | 2097152 | 128 MB |
| 1 PB + | 1 GB | 1048576 + | 64 MB + |
Other Algorithms
Video Streaming
According to the Netflix documentation, SD quality requires 384 KB/s, HD 640 KB/s, and 4k 3.2 MB/s.
An example movie "Home Alone (1990) 1080p" (which would obviously require a license from 20th Century Studios Inc for distribution) is about 1.6 GB. This classic has an input bitrate of about 2 MB/s. The proposed fragment size of 1 MB seems appropriate for videos that size and codec.
Torrent Piece Size
The target piece size in torrents is a well-discussed topic. The lower limit appears to be 256KB and upper limit 64MB (at least formerly).
- Vuze Wiki from 2005 suggests "a torrent should have around 1000-1500 pieces, to get a reasonably small torrent file and an efficient client and swarm download".
- TorrentFreak in 2008 suggests "the optimum number of pieces seems to be between 1200 and 2200".
- A random Reddit post from 2019 suggests a max of 64 MB.
- This Reddit comment from 2021 lists information about unusually large torrent files which may be useful for considering real life edge cases.
IPFS Block Size
In IPFS "a block refers to a single unit of data, identified by its key (hash)" according to the IPFS documentation.
In an issue from 2016 IPFS is described to have a block size of 1 MB (and libp2p enforcing a 2 MB limit). The reason is stated for security (against DoS), deduplication, latency, bandwidth, and performance.