<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small">Traditionally, a digest converts a sequence of bits to a fixed length output</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">M(d) -> 256 bits</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">We can now detect a single bit of corruption in the data file. Great! But that doesn't give us any information if the data is corrupted. We don't know where the corruption occurred. That is fine for little files but what about when we are dealing with 1TB archives?</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">A better approach would be to split the data up into chunks and construct a digest (Merkle tree??) over the chunks. But how big should the chunks actually be? There is clearly a tradeoff here which we traditionally just skate over entirely because we have this 'any fault will destroy our crypto' approach.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Another problem with the traditional approach is that it lacks parallelism. I have 64 cores on my CPU, I would like to be able to use all of them for hashing. So that points to dividing up the file at the block level, so if I have 16 chunks and want to use 4 threads, instead of calculating </div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 </div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">I would instead do</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 </div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">In either case, the result is D0 = H(H(0) +  H(1) +  H(2) +  H(3) + I)</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Where I is an index descriptor giving the index of the chunk in the document, hash mode, etc.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">I would then build a 'fat hash' which would consist of D0 + D1 + D2 + ... Dn</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">OK so at this point we can detect corruption but not recover from it. To do that, we need redundancy in the data. So a RAID like construct would be required within the data package:</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">0 1 2 3 P </div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">p = 0 xor 1 xor 2 xor 3</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div></div></div></div></div></div></div></div>