Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
This assignment is worth 20% of your final assessment
Assignment 3 - ByteTide - 20%
You are tasked with constructing a P2P File-Transfer program that will allow sending, receiving and detection of anomalous data chunks. The activity that your program will participate in will handle the following activities:
? Loading a configuration
? Loading package files and parsing their format
? Checking the integrity of the file matching to the configuration file’s path
? Managing many files that are completed and incomplete
? Complies with a network protocol to communicate with peers
? Informing a client program of the latest information of your peer and the files it manages
? Finalise and check that downloaded files match expected outcome
? Elegantly handle shutdown and disconnections from peers.
To reiterate, the program’s aim is to manage files, check integrity of chunks and files, share files and chunks, handle peer connections and requests. Unlike other file-transfer programs, there are no tracker or relay systems in place. A Peer is another program complying with this specification. It will need to implement the configuration, integrity checking, network protocol and object management.
It is advisable that while reading this document that you also refer to the glossary if you do not understand certain terms outlined in this document.
We strongly recommend reading this entire document at least twice. You are encouraged to ask questions on Ed after you have first searched, and checked for updates of this document. If the question has not been asked before, make sure your question post is of "Question" post type and is under "Assignment" category → "A3" subcategory. Please follow the staff directions for using the question template. As with any assignment, make sure that your work is your own, and that you do not share your code or solutions with other students.
It is important that you continually back up your assignment files onto your own machine, flash drives, external hard drives and cloud storage providers (as private). You are encouraged to submit your assignment regularly while you are in the process of completing it.
1 Part 1 - ByteTide Package Loader & Merkle Tree
To get started, you will need to be able to parse a .bpkg file and load it. To assist you with writing your code and complying with the test program, you are advised to complete the pkgchk.c file in the src directory.
1.1 The Package and its File Format (.bpkg)
In this program, a file is composed of several anomalous data chunks. The chunks are organised in a specific way such that when they are combined, the entire contents of the file can be constructed and presented to the user. A package defines the necessary information and resources required to construct the contents of a file. Packages represent a unique file given by an identifier string ident.
The package file format is a text format that will need to be parsed by your program. The package file format has the following fields. Please refer to the hashand chunk parts of the glossary. To also clarify, the package file, can be modelled as a binary tree, the term h, refers to the height of the tree in this instance.
? ident, hexadecimal string (1024 characters max), the identifier is used within the network to identify the same packages.
? filename, string (256 characters max), This is used to help save and locate the file to update when data is sent to it.
? size, uint32_t, specifies the size in bytes
? nhashes, uint32_t, specifies the number of hashes that are pre-computed from the original file. There must be only 2?(h-1)-1 hashes which will correspond to the hashes of all non-leaf node
? hashes, string[2?(h-1) - 1] (64 characters for each string), these correspond to the number hashes in the previous nhashes field.
? nchunks, uint32_t, specifies the number of chunks. The number of chunks must be a 2?(h-1) value.
? chunks, struct[2?(h-1)], each chunk have the fields: hash, offset and size.
– hash refers to a string (64 characters), corresponding to the datablock hash value
– offset, uint32_t, is the offset within the file
– size, uint32_t, is the size of the chunk in bytes
The format below gives an outline to the structure of a .bpkg file. Refer to the resources folder in the scaffold for a real example.
ident: <identifier>
filename: <filename>
size: <size in bytes>
nhashes: <number of hashes that are non-leaf nodes>
hashes:
"hash value"
...
nchunks: <number of chunks, these are all leaf nodes>
chunks:
"hash value",offset,size
...
1.2 Package Loading
The focus of this task is to load the .bpkg file and also store the details into a merkle tree. Please refer to Section 1.3 for information on a merkle tree.
? Read and load .bpkg files that comply with the format outlined in Section 1.1
? Once the .bpkg has been loaded successfully, it is advisable that your program also knows if the file exists or not and has functionality to construct a file of the size outlined in the file. Refer to pkgchk.c:bpkg_file_check function.
? Implement a merkle tree. Use the data from a .bpkg to construct a merkle-tree Refer to pkgchk .c :bpkg_get_all_hashes and
pkgchk .c :bpkg_get_all_chunk_hashes_from_hash functions, as you should be able to satisfy these operations after implementing a merkle tree without any IO on the data file.
? Computing the merkle tree hashes, ensuring that combined hashes match the parents hashes
when computed and finding minimum completed hashes. Refer to
pkgchk .c :bpkg_get_completed_chunks and
pkgchk .c :bpkg_get_min_completed_hashes functions. You will need to perform vali- dation on the chunks and discover portions of the file.
The above verifies chunks against package files and the data’s integrity.
1.3 What is a merkle tree?
Binary Tree A merkle tree is a variation on a binary tree. A binary tree is tree data structure, where a node is compose of the following.
? It holds a value/data
? Usually implemented to hold a key as well (Key-Value/Map Data Structure)
? Connected to two other nodes that are referred to as children. These are referred to as left and right nodes.
A common structure within C for a binary tree node is as follows
struct bt_node {
void* key;
void* value;
struct bt_node * left;
struct bt_node * right;
};
The above node, holds a key that will allow it to be searchable with the rule that it must be unique. It also holds a value, which can be assigned to arbitrary data.
Please Note: When building a tree with a key field that allows you to perform a search an efficient tree search, you will need to ensure that your tree is using an appropriate function for the job. Hint, if your tree is going to be multi-purpose, consider giving your tree a function pointer to compare the key.
To navigate and/or traverse a tree, you’dbe advised to traverse it in in-order traversal. Please make sure refer to your tree traversals. Please refer to the following documents to revise on tree-traversals:
? Tree-Traversal - Wikipedia
? Visualgo - BST
Qualities of a merkle tree Amerkle tree must is typically a perfect or full and complete binary tree but it can also be represented as a just a complete binary tree (Refer to Errata, Variations and Notes).
? Given a depth of d, the total number of nodes in your tree will be 2?d - 1
? All levels are full (necessary for a perfect binary tree).
? A merkle tree will have 2?(d-1) nodes at depth d, these will refer to your chunks.
? A merkle tree will have 2?(d-1) -1 non-leaf-nodes.
? All leaves have the same depth (no skewing)
All nodes in a merkle tree have a hash value. Hashes of a leaf node corresponds to a hash value of a data chunk. This value is derived from computing hash value of the data chunk itself.
All other non-leaf nodes derive their hash value by hashing their children’s hash values together.
Lets break down the above diagram.
? L1-L4 are data blocks, these refer to chunks in a file.
? Your leaf nodes 0-0 to 1-1 use a hash function to compute the hash of those data blocks. Given this part already, we have enough information to validate individual blocks.
Pseudocode Example: self.hash = Hash(DataBlock[i])
? Your non-leaf nodes 0, 1 and root, compute their hashes by combining the hash of their chil- dren into a long string and compute the hash of that (Refer: Errata, Variations and Notes)
Pseudocode Example: self.hash = Hash(left.hash + right.hash)
Figure 1: Merkle Tree - Wikipedia
The following is in relation to the .bpkg file and your merkle tree’s construction. You will have an expected hash value stored by your nodes and a computed hash value that you can use to 1) compute the hash on datablocks if it is a leaf node, or 2) compute the hash from the concatenation of left and right node hashes if it is a non-leaf node.
The following is an expansion of the operations. We are going through an example of computing the hash of root node of a tree with 7 nodes (similar to the diagram):
Expansion Pseudocode, with steps:
We need to compute the hash of the left and right child
1 . Hash(root) = Hash(
Hash(root.left) + Hash(root.right)
)
Since left and right child are not leaf nodes, we need to do it again 2 . Hash(root) = Hash(
Hash(
Hash(root.left.left) + Hash(root.left.right) )
+
Hash(
Hash(root.right.left) + Hash(root.right.right) )
)
We have found the leaf nodes
Compute the hash of the data blocks, the size is the chunk size as outlined in the .bpkg
3 . Hash(root) = Hash(
Hash(
Hash(DataBlock[0]) + Hash(DataBlock[1])
)
+
Hash(
Hash(DataBlock[2]) + Hash(DataBlock[3])
)
)
We concatenate the leaf children hashes that is assigned to their `computed` field
4 . Hash(root) = Hash(
Hash(
root.left.left.computed + root.left.right.computed )
+
Hash(
root.right.left.computed + root.right.right.computed )
)
Once again, concatenate the children hashes and compute the hash of that
5 . Hash(root) = Hash(
root.left.computed + root.right.computed
)
To help you get started, you can use the following struct as well as some helpful scaffold data.
struct merkle_tree_node {
void* key;
void* value;
struct merkle_tree_node * left;
struct merkle_tree_node * right;
int is_leaf;
char expected_hash[ 64 ]; //Refer to SHA256 Hexadecimal size char computed_hash[ 64 ];
};
struct merkle_tree {
struct merkle_tree_node * root;
size_t n_nodes;
};
Feel free to add and modify the struct above.
Do note You can construct a merkle tree that isn’t a perfect binary tree. However, this may make management of your data more difficult. Refer to Errata, Variations and Notes.
Do note Please make sure when you compute the hash, you use the hexadecimal representation. This is very important for non-leaf nodes that are computing the hash from an ordered concatenation of their children (left + right) hashes.
1.4 Errata, Variations and Notes
? Implementations: It isn’t necessary for a merkle tree to be a full or complete binary tree. You could potentially have a merkle tree with more than 2 children Or not all leaf nodes are on the same level
However, we have made this assumption to help simplify the data structure.
? Same-chunks, different positions: As through experimenting, you may have found that if you have chunks that contain the same data, in this case. Your implementation will need to either assume this will not happen or contain necessary data to differentiate it.
– Please refer to REQ packet, specifically offset part to help resolve searches.
– You can have a bit-field key alongside this similar to the diagram in the previous sections.
? More data than needed: For the most part, the file has been provided with more data than required to help with implementing this data structure but also ensure that other parts aren’t restricted if it is in an incomplete state.
? Using hexadecimal hash or byte-hash: The staff implementation uses the hexadecimal hashand while computing with the byte-hashis not-incorrect, it will yield different results to the test cases. Please make sure you comply with this.
1.5 Checklist
? Parse valid .bpkg files, ensure you can read each field of them.
? Construct a merkle tree from the bpkg files after parsing.
? Implement all the functions pkgchk.c.
? Run and compile make pkgchk.o and that will be able to compile pkgchk.c (Required for test cases)
? You are free to modify the Makefile to refer to your c files you will use in your build targets.
? Run and compile make pkgchecker, and compile against pkgmain.c to test your pro- gram locally.
2 Part 2 - Configuration, Networking and Program
You are now tasked with writing a program that will facilitate P2P file-transfer. Your program will need to complete the following tasks:
? Load a basic configuration file, your program will need to maintain the directory path it will store
? Implement and comply with the protocol to communicate with other peers within the network itself.
? Implement the commands for your program, these will include connecting. Your program will need to connect, disconnect and retrieve peer information. Handle package loading and remov-ing, retrieval of chunks from other peers.
This part deviates a little from part 1 as it is not completely necessary to build a merkle tree to get started on this part, let alone complete it. However It is necessary to be able to load a .bpkg file, retrieve the ident, filename, size, nchunks and chunks themselves for this part.
- 经济Economics
- 金融Finance
- 会计Accounting
- 工商管理Business Management
- 计算机computer science
- 商业分析business analysis
- 法律Law
- 管理Management
- 市场营销Marketing
- 哲学Philosophy
- 心理学Psychology
- 物理Physical
- 统计学statistics
- 电气工程electric engineering
- 化学chemistry
- 生物biology
- 数学mathematics
- 语言学linguistics
- 土木工程civil engineering
- 工程力学engineering mechanics
- 艺术art
PROFESSIONAL HELP!
在线咨询
立即下单
Wechat：THEend8_ 
Email：