2 edited body edited Dec 16 '18 at 11:10 Dmitri Urbanowicz 60622 silver badges99 bronze badges One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm. Let the file be partitioned in $$n$$ blocks of fixed size, $$H$$ be a hash-function, and $$h_t$$ be a value stored in a node $$t$$. If $$t$$ is a leave, then $$h_t$$ is a hash of the corresponding block. If $$r$$ is a parent of $$a$$ and $$b$$, then $$h_r = H[(a,b)]$$$$h_r = H[(h_a,h_b)]$$. One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm. Let the file be partitioned in $$n$$ blocks of fixed size, $$H$$ be a hash-function, and $$h_t$$ be a value stored in a node $$t$$. If $$t$$ is a leave, then $$h_t$$ is a hash of the corresponding block. If $$r$$ is a parent of $$a$$ and $$b$$, then $$h_r = H[(a,b)]$$. One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm. Let the file be partitioned in blocks of fixed size, $$H$$ be a hash-function, and $$h_t$$ be a value stored in a node $$t$$. If $$t$$ is a leave, then $$h_t$$ is a hash of the corresponding block. If $$r$$ is a parent of $$a$$ and $$b$$, then $$h_r = H[(h_a,h_b)]$$. 1 answered Dec 15 '18 at 9:56 Dmitri Urbanowicz 60622 silver badges99 bronze badges One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm. Let the file be partitioned in $$n$$ blocks of fixed size, $$H$$ be a hash-function, and $$h_t$$ be a value stored in a node $$t$$. If $$t$$ is a leave, then $$h_t$$ is a hash of the corresponding block. If $$r$$ is a parent of $$a$$ and $$b$$, then $$h_r = H[(a,b)]$$.