(This is just an abstract. I have a more detailed proposal in pdf form with
charts, which is also too long to be pasted here. I have sent it to AST and up
loaded it to an online storage :
site http://www.mediamax.com/
username wubingzheng
password summercode
)

1. Goal

I think it's impossible to correct intentional damage. The simplest example,
attacker overwrite all the disk by 0. So the goal is to detect all modification
and correct just accidental modification.

2. Ideas

Some abbreviations:
    A-block : authentication block
    C-block : checksum block
    D-block : data block

(1) Detection

If there is only one checksum set for each D-block, it's not able to correct
the modification. Because when the checksum checking fails, we donot know
where the error occurs, the requested D-block, or other D-blocks in this
checksum group, or the A-block itself. In order to correct modification, more
than 1 checksum for each block is needed for correction.

So the first checksum, named authentication and AUTH for short, can be
generated just for detection but not correction, which means it takes just
128 bits or 256 bits, but not 1KB or 1 block. So one A-block can contain n
AUTHs(n = SIZE_BLOCK / SIZE_CHECKSUM). But we just use (n-1), and keep the
remained one for the AUTH of this A-block itself, which can avoid multipul
level checking.

According to the principle of locality in space, it's useful to read numbers
of blocks around the requested one for each request. Regard these blocks as
a group and generate AUTH from them.

(2) Correction

A real checksum(CHS for short) is needed for correction. Since the blocks
neighboring likely belong to the same file, they are likely to be modified
accidentally at the same time. In order to correct one block, which requires
the correctness of other blocks in the same group, it's better to distribute
the blocks over the disk. Although this will lose efficiency, it dose not
lose much, since they are just read when the AUTH checking fails.