|
Post by kratiry on Mar 3, 2023 3:21:39 GMT -5
We could implement our system using a STARK for the relation R induced by the statement PreImageh,X1,…,Xn+1 described above. There are two problems with this approach, one theoretical and one practical. The first problem is that, even if there is only a single and short deletion of few bytes, the time complexity of verifying the proof will depend on the length of the overall transaction and this is a wasteful overkill. The second problem is that for larger transactions, the length of the corresponding rank-1 constraint system (R1CS), that is the constraint system used to represent a circuit, becomes huge. The storage needed to store the R1CS for transactions of size greater than 1KB, would consist of hundreds of gigabytes.
Instead of proving and verifying the previous statements directly in ZK (i.e., using a STARK for those statements), we prove and verify such statements in a more efficient way. The idea is to consider all intermediate outputs of each round of SHA256. Recall that SHA256 essentially works as follows: given an input X , it extends X to an input X′ of a length multiple of 64 bytes, breaks X′ into chunks of 64 bytes and for each of such chunks it executes a round function SHARound that takes as input a chunk and the output of the previous round. The first round takes as input the first chunk and a fixed value h0 that is the concatenation of values g0,…,g7 described in the SHA256 specifications [24, Sec. 6].6
|
|
|
Post by akira on Mar 3, 2023 3:22:08 GMT -5
Let X be a string obtained redacting a string Y and let h = H (Y ). Recall that X and h are public information as well as the points in which the redaction has been done. The witness is the original string Y before the redaction. Our goal is to design an efficient proof system to convince anyone that the public inputs are consistent with the redaction.
|
|