README.md

Rescue STARKs

Examples in this directory use a modified version of Rescue hash function to define various STARKs. As compared to the original construct, the modifications are as follows:

• The second step of the last round is omitted from the computation;
• The first step of the first round is pre-computed;
• The function is restricted to accepting a single value..

All constants used in computations were generated by using code from here: https://github.com/KULeuven-COSIC/Marvellous.

Hash preimage

THere are two examples that generate STARKs to prove knowledge of hash preimage. Both are essentially the same, but use different parameters for Rescue hash function:

Hash 2x64

In this example, the following parameters are uses:

• p (field modulus): 2^64 - 21 * 2^30 + 1
• m (number of registers): 2
• N (rounds): 32

Hash 4x128

In this example, the following parameters are uses:

• p (field modulus): 2^128 - 9 * 2^32 + 1
• m (number of registers): 4
• N (rounds): 32

Merkle Proof

This example generates STARKs for computations that verify Merkle proofs. Basically, it can be used to prove that you know a proof for some value in a Merkle tree at the specified index without revealing that value or the proof.

Just as a reminder the code (in JavaScript) for verifying Merkle proof looks like this:

function verify(root, index, proof) {
    index += 2**proof.length;

   let v = proof[0];
   for (let i = 1; i < proof.length; i++) {
       p = proof[i];
       if (index & 1) {
           v = hash(p, v);
       }
       else {
           v = hash(v, p);
       }
       index = index >> 1;
   }

   return root === v;
}

The way this is translated into a STARK is:

• There are 8 state registers:
  • The first 4 registers ($r0 - $r3) are used to compute hash(p, v).
  • The other 4 registers ($r4 - $r7) are used to compute hash(v, p).
• Each register is 128-bits, and values in the merkle tree are assumed to be 128-bits as well. For example, hash(p, v) works like so:
  • Value p goes into registers $r0. Value v goes into registers $r1. The other 2 registers ($r2 and $r3) are used internally by the hash function algorithm and are initialized to 0.
  • After 31 steps, the hash of two values is in registers $r0.
• Since, hashing takes 31 steps, the computation consists of a 32-step loop repeated for each node of a Merkle branch. The code works as follows:
  • The computation requires 3 inputs:
    • leaf - this is the node for which the Merkle proof is generated. It requires 2 field elements to represent.
    • nodes - this is the Merkle path to the leaf. It also requires 2 field elements to represent, but unlike leaf the rank of this input is 1. This means, that for every leaf value, there can be many node values provided.
    • indexBit - this holds a binary representation of the leaf's position. It is represented by a single element which is restricted to binary values. This input also has a rank 1. So, for every node, a single index bit should be provided.
  • The first init clause is executed once for each branch (you can generate proofs for multiple branches). All it does is initialize the execution state ($r registers) to hold values passed in via leaf and node inputs (see this for more explanation of how input loops work).
  • The second init clause is executed once for each node in a branch. It uses value in bitIndex to figure out which of the hashed values (hash(p, v) or hash(v, p)) advances to the next cycle of hashing.
  • The for steps loop executes the actual hash function logic. It computes both, hash(p, v) and hash(v, p) at the same, with result of hash(p, v) going to register $r0 and result of hash(v, p) going to register $r4.

This all results into a transition function that looks like this:

transition 8 registers {
    for each (leaf, node, indexBit) {

        // initialize state with first 2 node values
        init {
            yield [leaf, node, 0, 0, node, leaf, 0, 0];
        }

        for each (node, indexBit) {

            // for each node, figure out which value advances to the next cycle
            init {
                h <- indexBit ? $r4 : $r0;
                yield [h, node, 0, 0, node, h, 0, 0];
            }

            // execute Rescue hash function computation for 31 steps
            for steps [1..31] {
                // compute hash(p, v)
                S1 <- mds # $r[0..3]^alpha + roundConstants[0..3];
                S1 <- mds # (/S1)^(inv_alpha) + roundConstants[4..7];

                // compute hash(v, p)
                S2 <- mds # $r[4..7]^alpha + roundConstants[0..3];
                S2 <- mds # (/S2)^(inv_alpha) + roundConstants[4..7];

                yield [...S1, ...S2];
            }
        }
    }
}