# Distributing blocks with validation and non-dependant list generation

Problem
Suppose I have a system of nodes that can communicate with a parent node, but not among each other. Suppose then a file on the parent node is split up into blocks and divided among the children. The file is then deleted from the parent node.

If the parent were to then request the blocks back from the children, how can the original order be reconstructed without retaining a list of all the files on the parent. Additionally, to prevent one of the nodes from maliciously modifying a block, the parent would also have to validate the blocks coming back.

Optimal Solution
A system of naming the blocks of a file, where the list of files can be generated on any node given a seed. Given the list, a parent should be able to use the list somehow to validate the blocks coming back from children.

Attempt #1
So what I have got so far is the ability to minimally store a list of the blocks. I do so by naming the blocks as such:

block_0 = hash(file_contents)
block_n = hash(block_n-1) [hashing the name of the previous file]


This enables the order of the files to be retained by just keeping the seed (name of block_0), and the number of blocks (e.g. 5d41402abc4b2a76b9719d911017c592,5 --> seed,files). However this will not allow the files to be validated independently.

Attempt #2
Simply take the hash of each block and store that in a list. However this is not efficient and will result in a large amount of memory allocated to this task alone if a large number of blocks need to be tracked. This will not do.

-
If you're concerned about nodes maliciously modifying the data, are you also wanting confidentiality (e.g. encryption)? Something to think about, anyway. –  Reid Jun 5 '13 at 4:06
How about embedding each block's MAC to the next? So that $b'_0=b_0||MAC(b_1)$, with the last block having the MAC of $b_0$. To make it even easier to identify a corrupt block, $$b'_n=b_n||MAC(b_{n-1})||MAC(b_{n+1})$$
where $||$ denotes concatenation. To identify the order of the blocks, simply try to fit them together as they come, or embed each block's $n$ to it.
The scheme I would use is $$b_n = n || c || \operatorname{MAC}_k(n||c)$$ where $b_n$ is the block in question, $n$ is the index of the block, $c$ is the contents of the block, and $k$ is a symmetric key for the MAC. Embedding $n$ lets you quickly order messages, which is nice, since missing blocks don't screw everything up (necessarily). I can't think of any real advantage in using the MAC for a different block in the current block. But I may be missing something. –  Reid Jun 5 '13 at 4:04