Problems

1. How to store multiple files remotely and know that those files haven’t been changed?

2. Given a starting 𝑥, compute 𝑥↦𝑥^3+5, and repeat that 1 million times. How to prove to someone I computed this, and did so correctly - without he having to re-run the whole thing.

   Suppose our starting number is 𝑥=2.
   - x^2 = 4
   - x^3 = x^2 * x = 4 * 2 = 8
   - X^3 + 5 = 13
   So our trace is {2, 4, 8, 13, ...}
   we will produce 3,000,001 numbers in computing the circuit.
   

→ How can we verify integrity of a vector of elements?

Solution 1: Single file hashing

For single file, we can use secure hash functions:

So a simple scheme for verifying file integrity: hash each file and save the store the hash locally.

Problem: has to store n hashes → we need constant-sized digest

Solution 2: Merkle Trees

Merkle tree

• the root is the digest, it is constant sized

  

• use merkle proof to verify if the files have been changed.