# SHA Graph

SHA(x,y)=z
SHA[x1|x2|...|xn] = SHA(SHA[x1|...|x(n-1)], xn)

------------------------

parent = { SHA}

------------------------

Root = DAG'(X) from above
Proof computed using X
Instead of Normal: CID(DAG(X)), use CID(DAG(Y))

// ref_to_oneblock: SHA(SHA[x1|...|x(n-1)],xn) = SHA[x1|...|xn]
// ref_to_restblocks: SHA[x1|...|x(n-1)]

NODE={
left: {
CID(left)
H = SHA(0, F0 ... bottom_right_leaf_of_left_child)
}
right: {
CID(right)
SHA(H, bottom_left_leaf_of_right_child..Fn)
}
}

Z = SHA256(F0 || F1)

NODE={
left: {
// CID(F0)
H = SHA(0, F0)
}
right: {
// CID(F1)
G = SHA(H, F1)
}
}

For every k, SHA(F0..Fk):

SHA(H,G) = correct answer
H = SHA(0, F0)

digraph hierarchy {

                nodesep=1.0 // increases the separation between nodes

                node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
                edge [color=Blue, style=dashed] //All the lines look like this
                
                root [label = "h=SHA(0,F0|F1) \n SHA(h,F2|F3)"]
                i0 [label = "h0=SHA(0,F0) \n SHA(h0,F1) "]
                i1 [label = "h1=SHA(h,F2) \n SHA(h1,F3)"]
                
                root
                root -> i0
                root -> i1
                i0 -> f0
                i0 -> f1
                i1 -> f2
                i1 -> f3
}

For every k: verified and know SHA(f0..f(k-1), fk)

h, h0, h1, ?

? = f0

### StrawmanB Proposal (WIP)

Overview: Restructure the graph to store more copies of intermediate SHA256 hashes such that partial SHAs present in each node can be used to verify the ones underneath it.

Example: We have an 4MiB file `F` with `H_F=SHA256(F)` so we divide the file up into 4 chunks `F0...F3`. We then put them into a tree with non-leaf nodes `I0...I2` as below and a root node `Root`.

digraph hierarchy {

                nodesep=1.0 // increases the separation between nodes

                node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
                edge [color=Blue, style=dashed] //All the lines look like this
                
                root [label = "Root \n LeftHash : SHA(0,F0||F1) \n RightHash : SHA(LeftHash,F2||F3)"]
                i0 [label = "\I0 \n LeftHash : SHA(0,F0) \n RightHash: SHA(LeftHash,F1) "]
                i1 [label = "\I1 \n LeftHash : SHA(Root.LeftHash,F2) \n RightHash : SHA(LeftHash,F3)"]
                
                root
                root -> i0
                root -> i1
                i0 -> F0
                i0 -> F1
                i1 -> F2
                i1 -> F3
}

To download the graph we:

1) Get the Root block knowing that H=SHA256(F0||F1||F2||F3) should be the hash of the concatenated leaf blocks. The Root block points us at both I2 and F3.
2) Fetch F3 and check that SHA256-P(F0 || F1 || F2, F3) can give us H.
3) Fetch I2 and then F2 and check that SHA256-P(F0 || F1, F2) gives the SHA256-P(F0 || F1 || F2) that we found in Root.
4) Fetch I1 and then F1 and check that SHA256-P(F0, F1) gives the SHA256-P(F0 || F1) that we found in I2
5) Fetch I0 and then F0 and check that SHA256-P(nil, F1) gives the SHA256-P(nil || F0) that we found in I1

### DISCUSSION

Node X, represents Xi…..Xj
Contents node:
- A = HASH(0, Xi..Xj)
- (B) = HASH(left sibling's A) -> only for right nodes
- C = HASH(B or 0, X(i+j)/2...Xj)

H(A*B) = H(A)*H(B)

H(left)*H(right) -> known H(whole)

X

Verifier knows:
SHA(X)

Prover knows:
X

To prove: Y = SHA3(X)

C challenge by verifier

know: SHA3(X+challenge), SHA(X+challenge)
=> learn X