starkware-libs / ethSTARK

Glossary

1. Introduction
2. Disclaimers
3. Dockerfile Usage
4. Run Example
5. Prover Inputs
6. Running Tests
7. Measuring Security

1. Introduction

STARKs (Scalable Transparent ARguments of Knowledge) are a family of proof-systems characterized by scalability and transparency. Scalability - via quasilinear proving time and poly-logarithmic verification time, and transparency - meaning all verifier-side messages are public random coins (requiring no trusted setup).

This project implements a STARK protocol as a non-interactive protocol between a prover and a verifier. The prover sends a proof in order to convince the verifier that a certain statement is true. Usually the proven statement indicates that a desired computation on some input was executed correctly. The verifier reads the given proof in order to test the integrity of the proven statement. To that end, the Fiat-Shamir heuristic is employed in order to turn what can be described as an interactive communication to a non-interactive protocol.

For an honest prover and a valid computation the verifier is guaranteed to accept the proof. Otherwise, if the prover is dishonest or the computation is compromised, it would require an infeasible amount of computation on the prover's part in order to produce a proof that the verifier will not reject.

The Rescue-Hash statement proven by the prover given in this code is:

"I know a sequence of n + 1 inputs {w_i} such that H(...H(H(w_0, w_1), w_2) ..., w_n) = p"

where:

• H is the Rescue hash function.
• Each w_i is a 4-tuple of field elements. These are private inputs, known only to the prover.
• p is the public output of the hash (which also consists of 4 field elements).

For more details, see our external documentation.

The following sections explain how to compile and run the tests and benchmarks in this project, as well as explaining the meaning and usage of the prover inputs.

2. Disclaimers

1. The code presented in this project has been audited by PeckShield Inc., to view their report, click here.

2. The system is designed to guarantee up to 80 bits of security, depending on hardcoded values and on several parameters given as input. Refer to the [Measuring Security] section for more details.

3. The proofs generated by the prover in this project are not zero-knowledge, even though zero-knowledge proofs are an optional feature of STARKs.

4. The chain-length (representing the number of Rescue hash invocations) must be divisible by 3. This is done for simplicity, since batches of 3 hashes are fit into 32 rows in the Rescue hash trace.

5. This project only supports compilation on a Linux (Ubuntu 18.04) environment. For other operating systems, a Dockerfile is included in order to simulate such an environment (Refer to the [Dockerfile Usage] section).

3. Dockerfile Usage

For operating systems which are not compatible with this project, the source directory holds a dedicated Dockerfile, which automatically runs the unit tests and end-to-end tests on a simulated Ubuntu 18.04 environment.

To use this, simply navigate to the cloned source directory and run:

> docker build --tag ethstark .

Once the docker image is built, a terminal may be accessed in the simulated Ubuntu environment using:

> docker run -it ethstark

From there the project's code can be compiled and run as detailed in the following sections.

4. Run Example

In order to run the example, first make sure to install dependencies, this can be done by running the following script:

> ./install_deps.sh

Next, compile the project code by running the following commands into the terminal (from the project's source directory):

> mkdir -p build/Release
> cd build/Release
> cmake ../.. -DCMAKE_BUILD_TYPE=Release
> make -j
> cd ../..

The prover requires a private input file (representing the witness for the proven statement). In order to randomize the prover's private input used by this example code, use:

> PYTHONPATH=src example/random_private_input.py --chain_length=3

NOTE: Other chain length values will require appropriate changes to the example/rescue_params.json file (see [Prover Inputs] section).

Once the code is compiled, the dependencies installed, and the random private input is generated, use the following command to run the STARK prover:

> build/Release/src/starkware/main/rescue/rescue_prover \
    --parameter_file example/rescue_params.json \
    --prover_config_file example/rescue_prover_config.json \
    --public_input_file example/rescue_public_input.json \
    --private_input_file example/rescue_private_input.json \
    --out_file example/proof.json \
    --logtostderr

The flags used in the above command define paths to example files containing the various prover inputs. For a more detailed description of these inputs, refer to the [Prover Inputs] section of this guide.

Finally, run the STARK verifier using:

> build/Release/src/starkware/main/rescue/rescue_verifier \
    --in_file example/proof.json \
    --logtostderr

The file example/proof.json is generated after running the prover as described above, and contains the proof along with the public input, given to the verifier for verification.

If all goes well the end result should be a successful validation of the proof by the verifier.

5. Prover Inputs

Parameter file

Contains parameters that configure the STARK protocol. This affects the way the proof is generated by the prover and interpreted by the verifier.

NOTE: Some of the values in this file affect the security level of the system. Consult the [Measuring Security] section for more details.

{
    "stark": {
        "fri": {
            "fri_step_list": [
                1,
                2,
                2
            ],
            "last_layer_degree_bound": 1,
            "n_queries": 30,
            "proof_of_work_bits": 20
        },
        "log_n_cosets": 2
    }
}

NOTE: The values given in "fri_step_list" and "last_layer_degree_bound" should satisfy:
sum(fri_step_list) + log2(last_layer_degree_bound) = log2(trace_length)
where trace_length is equal to 32 * chain_length / 3, rounded up to the nearest power of 2.

Prover config file

Contains a configuration governing the way the prover operates internally in order to tweak performance. This has no affect on the produced proof or the way the verifier reads it.

{
    "constraint_polynomial_task_size": 256
}

Public input file

Contains the public input, which represents data known to both the prover and the verifier. In the case of the Rescue hash statement, the public input is the output of the Rescue hash function, for which the prover claims to know the inputs which produce it (In the Rescue hash statement in the [Introduction] section this is represented by p). Furthermore, chain_length represents the number of Rescue hash invocations in the proven statement (represented by n in the statement).

{
    "output": [
        "0xb87ffc3341ef328",
        "0x1825dd4dfceaa726",
        "0x1e869731f5a4318",
        "0x1239e1d4648b2716"
    ],
    "chain_length": 3
}

Private input file

Contains private data known only by the prover, and used to generate the proof. In the case of the Rescue hash statement, the private input is a series of inputs whose hash (as defined above) is given in the public input file, and representing the points {w_i} whose combined hash results in the desired output.

{
    "witness": [
        [
            "0x12e4f2bfa4bedb74",
            "0x1bbb965e8fd3d6e",
            "0x4992d0f548d72d2",
            "0x1704eaf08d47dab5"
        ],
        [
            "0x3f3eeb71ad8960e",
            "0x172a32b0942db2b7",
            "0xf7cefd948bf82b6",
            "0x1e096a30ec5a1c8"
        ],
        [
            "0x65f0bf6258e54e",
            "0x1c1f0fcd9420f4b8",
            "0xa7213eb3fe40af3",
            "0x15e178d3990c036"
        ],
        [
            "0x3eae9a8c9777c40",
            "0x1b09401086b5282b",
            "0xdeee4f5fa8573e2",
            "0x36f3a7c772e42f"
        ]
    ]
}

6. Running Tests

Refer to the [Run Example] section for the commands to build the project code.

To run all the unit tests available in this project, use:

> (cd build/Release; ctest -v)
> pytest

The project has two benchmarks, one for the prover and one for the verifier. They can be executed using:

> build/Release/src/starkware/benchmarks/rescue_prover_benchmark
> build/Release/src/starkware/benchmarks/rescue_verifier_benchmark

7. Measuring Security

As mentioned in the [Disclaimers] section, this system is designed to support up to 80-bits of security.

The conjectured security in this system is the minimum of three values:

1. log_n_cosets * n_queries + proof_of_work_bits (these are the parameters that appear in the parameter_file. Refer to the [Prover Inputs] section for details).
2. The collision resistance of the hash used by the protocol. This system employs Blake2s160 for the protocol, which is considered to provide 80 bits of security at the time of writing this project.
3. log(extension_field_size) - log(trace_length) (where the extension field is hardcoded to be of size 122 bits, and trace_length = (chain_length / 3) * 32 rounded up to nearest power of 2).

Additionally, there is a proven security bound on the soundness of the FRI protocol (used as the LDT component of the STARK protocol), for more information refer to section [7.2] in this paper: https://eprint.iacr.org/2020/654.