Disclaimer: most of the procedures in this file assume that the input pointers are word-aligned.<br />
## std::crypto::stark::random_coin
| Procedure | Description |
| ----------- | ------------- |
| get_rate_1 | Return the first half of the rate portion of the random coin state<br /><br />The random coin uses RPO to generate data. The RPO state is composed of 3<br />words, 2 words for the rate, and 1 word for the capacity. This procedure<br />returns the first word of the RPO state.<br /><br />Input: [...]<br />Output: [R1, ...]<br />Cycles: 6<br /> |
| set_rate_1 | Store the first half of the rate portion of the random coin state.<br /><br />Input: [R1, ...]<br />Output: [...]<br />Cycles: 6<br /> |
| get_rate_2 | Return the second half of the rate portion of the random coin state<br /><br />The random coin uses RPO to generate data. The RPO state is composed of 3<br />words, 2 words for the rate, and 1 word for the capacity. This procedure<br />returns the first word of the RPO state.<br /><br />Input: [...]<br />Output: [R2, ...]<br />Cycles: 6<br /> |
| set_rate_2 | Store the second half of the rate portion of the random coin state.<br /><br />Input: [R2, ...]<br />Output: [...]<br />Cycles: 6<br /> |
| get_capacity | Return the capacity portion of the random coin state<br /><br />The random coin uses RPO to generate data. The RPO state is composed of 3<br />words, 2 words for the rate, and 1 word for the capacity. This procedure<br />returns the first word of the RPO state.<br /><br />Input: [...]<br />Output: [C, ...]<br />Cycles: 6<br /> |
| set_capacity | Set the capacity portion of the random coin state.<br /><br />Input: [C, ...]<br />Output: [...]<br />Cycles: 6<br /> |
| load_random_coin_state | Load the random coin state on the stack.<br /><br />Input: [...]<br />Output: [R2, R1, C, ...]<br />Cycles: 18<br /> |
| store_random_coin_state | Store the random coin state to memory.<br /><br />Input: [R2, R1, C, ...]<br />Output: [...]<br />Cycles: 18<br /> |
| init_seed | Initializes the seed for randomness generation by computing the hash of the proof context using<br />the trace length, number of queries, the number of bits of grinding.<br />Currently, this part, as well as the rest of the STARK verifier assumes a blowup factor<br />equal to 8.<br />The ouput of this procedure is the capacity portion of the state after applying `hperm`.<br /><br />Input: [log(trace_length), num_queries, grinding, num_constraints, trace_info, num_fixed_len_pi, ...]<br />Output: [C, ...]<br />Cycles: 210<br /> |
| reseed | Reseed the random coin with `DATA`<br /><br />Input: [DATA, ...]<br />Ouput: [...]<br />Cycles: 54<br /> |
| generate_aux_randomness | Draw a list of random extension field elements related to the auxiliary segment of the execution<br />trace and store them.<br /><br />More specifically, we draw two challenges, alpha and beta. This means that our multi-set hash function<br />has the form `h(m) = alpha + \sum_{i=0}^{\|m\| - 1} m_i * beta^i` for a message `m`.<br /><br />As these random challenges have already been used non-deterministically in prior computations, we<br />also check that the generated challenges matche the non-deterministically provided one.<br /><br />Input: [...]<br />Output: [...]<br />Cycles: 20<br /> |
| generate_constraint_composition_coefficients | Draw constraint composition random coefficient and save it at `compos_coef_ptr`.<br /><br />Input: [...]<br />Output: [...]<br />Cycles: 13<br /> |
| generate_deep_composition_random_coefficients | Draw deep composition polynomial random coefficient and save it at `deep_rand_coef_ptr`.<br /><br />As this random challenge has already been used non-deterministically in prior computations, we<br />also check that the generated challenge matches the non-deterministically provided one.<br /><br />Input: [...]<br />Output: [...]<br />Cycles: 22<br /> |
| generate_z_zN | Generate the OOD challenge point `z = (z0, z1)` and compute `z^N` where N is<br />the trace length. The resulting word `[(z_1, z_0)^N, z1, z0]` is stored in the<br />global memory address `exec.z_ptr` reserved for it.<br /><br />Input: [X, ...]<br />Output: [...]<br />Note: The top word on the stack is consumed by this procedure.<br />Cycles: 21 + 10 * log(N)<br /> |
| generate_list_indices | Generate a list of `num_queries` number of random indices in the range<br />[0, lde_size] and store it in memory starting from `query_ptr`.<br />The list is stored as `(r, depth, y, y)` where `depth` is `log(lde_domain_size)`.<br />`depth` is needed when computing the deep queries.<br /><br />Input: [query_ptr, num_queries, ...]<br />Output: [...]<br /><br />Cycles: 267 + q * 236 + r * 29 where q = num_queries / 8 and r = num_queries % 8<br /><br />NOTE: This procedure is called first, and right after the PoW check, thus the first element<br />in the rate portion of the state is discarded.<br />NOTE: The cycles count can be estimated, using the fact that r < 8, via the more compact formula<br />470 + 236 * (num_queries / 8)<br /> |
| check_pow | Check that the Proof-of-Work contained in the nonce is equal to the required number<br />of bits prescribed by grinding bits. The grinding factor is assumed to be less than 32.<br /><br />Input: [...]<br />Output: [...]<br />Cycles: 73<br /> |