https://github.com/starkware-libs/ethSTARK
06/13/2022
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:
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.
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.
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.
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.
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 }
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 }
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" ] ] }
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`
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:
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.
STARK（可扩展的透明知识论证）是一系列以可扩展性和透明性为特征的证明系统。可扩展性——通过准线性证明时间和多对数验证时间，以及透明度——意味着所有验证方消息都是公共随机硬币（不需要可信设置）。
该项目将 STARK 协议实现为证明者和验证者之间的非交互协议。证明者发送证明是为了让验证者相信某个陈述是真实的。通常，经过验证的语句表明对某些输入的期望计算已正确执行。验证者读取给定的证明以测试证明声明的完整性。为此，采用了 Fiat-Shamir 启发式算法，以便将可以被描述为交互式通信的内容转变为非交互式协议。
对于诚实的证明者和有效的计算，验证者保证接受证明。否则，如果证明者不诚实或计算受到损害，则证明者将需要不可行的计算量才能产生验证者不会拒绝的证明。
这段代码给出的prover证明的Rescue-Hash语句为：
“我知道一个 n + 1 个输入序列 {w_i} 使得 H(...H(H(w_0, w_1), w_2) ..., w_n) = p”
在哪里：
有关更多详细信息，请参阅我们的外部文档。
以下部分解释了如何编译和运行该项目中的测试和基准，以及解释证明者输入的含义和用法。