or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
![image alt](https:// "title") | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | Emoji list | ||
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Sin7Y Tech Review (25): STARK - An Indepth Technical Analysis
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →Step1 - Build trace (fib2-example)
The numbers marked in red are public info
Step2 - Prover for Trace
Selection of the protocol parameter:
1. AIR Instantiation
2. Verify the consistency of AIR and Trace (Debug module)
2.1 Verify basic parameters
2.2 Verify the validity of assertion (boundary cs)
2.3 Verify if Trace holds transition cs(Debug module)
Transcript
3. Commit for trace
Domain parameter selection:
3.1 Interpolate -> LDE -> evaluate over LDE-domain
3.2 Commitment
Transcript
4.Evaluate CS
4.1 Obtain Linear Composition Coefficients
The number of coefficients is consistent with that of constraints
In this example (fib2-example), there are 2 transition cs and 3 boundary cs.
4.2 Establish the evaluator for t-cs and b-cs
4.2.1 t-cs
4.2.2 b-cs
4.3 Evaluate t/s-cs over ce_domain
4.3.1 Define evaluator table
5. Commitment to Evaluate CS
5.1 Establish constraints composition polynomial
5.2 commitment to composition poly
Example:
Compose_poly = a * x^3 + b * x^2 + c * x + d = (a * x^2 + c) * x^ + (b * x^2 + d)
(a * x^2 + c) and (b *x^2 +d) correspond to two columns, respectively.
6. Establish DEEP composition polynomial
The general formal: f(x) = q(x)* t(x)
Need check at random z
6.1 Select z which out of domain(ood)
Draw an out-of-domain point z. Depending on the type of E, the point is drawn either from the base field or from an extension field defined by E.
The purpose of sampling from the extension field here (instead of the base field) is to increase security
6.2 evaluate trace and constraint polynomials at the OOD point z
6.2.1 trace_poly at z & z * g
6.2.2 composition poly at z
6.3 Establish Deep composition polynomial
6.3.1 Generate random numbers
6.3.2 cal quotient poly
6.4 Evaluate Deep over LDE
7. Calculate the FRI Layer num of Deep
8. Determine positions of the query
Select multiple positions of the query from lde_domain.
9. Establish proof objects
9.1 Generate FRI proof
9.2 Query trace poly at above positions
Similar to the above
9.3 Query constraint poly at above positions
Similar to the above
9.4 Establish the STARK Proof
Step3 - Verify the proof
Read pub-info from the transcript to obtain relevant data, and then to execute the verification process.
1.Ood consistency check
Verify the consistency of the mathematical relationship described in Chapter 5.2
2. Instantiate the FRI-verifier object
3. Calculate Deep poly on query positions
The calculating method is the same as that in Chapter 6.4
4. Execute the FRI VERIFY process