• Stars
    star
    223
  • Rank 178,458 (Top 4 %)
  • Language
    C++
  • License
    Apache License 2.0
  • Created over 4 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

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.

More Repositories

1

cairo

Cairo is the first Turing-complete language for creating provable programs for general computation.
Rust
1,586
star
2

cairo-lang

Python
1,342
star
3

papyrus

Papyrus is a StarkNet full node written in Rust.
Rust
309
star
4

starkex-contracts

Solidity
276
star
5

stone-prover

C++
255
star
6

stwo

Rust
237
star
7

blockifier

Blockifier is a Rust implementation for the transaction-executing component in the StarkNet sequencer, in charge of creating state diffs and blocks.
Rust
170
star
8

starknet-specs

JavaScript
92
star
9

starkex-resources

Python
82
star
10

veedo

Solidity
77
star
11

starknet-staking

starknet-staking
Cairo
72
star
12

starkgate-frontend

Bridge interface allows users to transfer ERC20 tokens from Ethereum to StarkNet and vice versa.
JavaScript
63
star
13

starknet-api

Rust
59
star
14

starkware-crypto-utils

Signatures, keys and Pedersen hash on STARK friendly elliptic curve
TypeScript
54
star
15

formal-proofs

Lean
52
star
16

stark-perpetual

Cairo
49
star
17

starkgate-contracts

Python
35
star
18

crypto-cpp

C++
32
star
19

starkex-js

JavaScript SDK for StarkEx
TypeScript
28
star
20

starkex-for-spot-trading

Cairo
24
star
21

cairo-examples

Shell
24
star
22

stwo-cairo

Cairo
23
star
23

sequencer

Rust
23
star
24

starkex-core

21
star
25

mempool

Rust
14
star
26

starkex-data-availability-committee

Python
9
star
27

tree-sitter-cairo

JavaScript
7
star
28

starknet-snap

HTML
7
star
29

StarkNet-AllCoreDevs-Meetings

6
star
30

starkex-apps-api

6
star
31

starkex-playground

Python
6
star
32

okx-config

6
star
33

cairo-playground

Playground environment for those who want to learn and get to know Cairo language better.
JavaScript
5
star
34

davion-config

DavionLabs Perpetual StarkEx Configuration
4
star
35

starkex-resources-wip

Python
4
star
36

starknet-tutorials-erc20

3
star
37

starknet-addresses

3
star
38

starknet-tutorials-global

2
star
39

committer

Rust
2
star
40

stwo-air-schema

Shell
2
star
41

starknet-tutorials-erc721

2
star
42

dydx-config

2
star
43

starknet-tutorials-cairo-syntax

2
star
44

gammax-config

GammaX Perpetual StarkEx Configuration
2
star
45

starknet-tutorials-utils

1
star
46

x10-config

1
star
47

karpenter

1
star