Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
hash2x64.ts
hash4x128.ts
merkleProof.ts
utils.ts

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 are used to compute hash(p, v)
    • The other 4 registers are used to compute hash(v, p)
  • Hashing a value takes 31 steps - so, the computation is broken into 32-step rounds. The first 31 steps of each round are used to hash the values, and the last step is used to set the values for the next round of hashing.
  • There is 1 public input register that holds a binary representation of the index parameter such that the next binary digit of the index "appears" in the register every 32 steps.
    • This value is used to determine which of the hashes advances to the next round of computation.
  • There is 1 secret input register that holds values for proof nodes such that a new node value "appears" in the register every 32 steps.

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

transition 8 registers in 16*32 steps {
    when ($k0) {
        // constants for the hash function
        K1: [$k1, $k2, $k3, $k4];
        K2: [$k5, $k6, $k7, $k8];

        // compute hash(p, v)
        S1: [$r0, $r1, $r2, $r3];
        S1: MDS # S1^alpha + K1;
        S1: MDS # S1^(inv_alpha) + K2;

        // compute hash(v, p)
        S2: [$r4, $r5, $r6, $r7];
        S2: MDS # S2^alpha + K1;
        S2: MDS # S2^(inv_alpha) + K2;

        out: [...S1, ...S2];
    }
    else {
        // this happens every 32nd step

        // select the hash to move to the next step
        h: $p0 ? $r4 | $r0;

        // set values for p and v for the next step
        S1: [h, $s0, 0, 0];
        S2: [$s0, h, 0, 0];

        out: [...S1, ...S2];
    }
}
You can’t perform that action at this time.