## std::crypto::fri::frie2f4
| Procedure | Description |
| ----------- | ------------- |
| preprocess | Stores the layer commitments C followed by [d_size, t_depth, a1, a0] and [poe, p, e1, e0] where:<br />1) d_size is the domain size divided by 4 of the domain corresponding to C.<br />2) t_depth is the tree depth of the Merkle tree with commitment C.<br />3) (a0, a1) is the folding challenge to create the next layer.<br />4) p is the query index and (e0, e1) is the evaluation at the first layer and poe is g^p with<br />g being the initial domain generator.<br />TODO: This pre-processing function should in fact compute d_size and t_depth for each C<br />starting from the original domain size.<br /> |
| verify_query_layer | Checks that, for a query with index p at layer i, the folding procedure to create layer (i + 1)<br />was performed correctly. This also advances layer_ptr by 8 to point to the next query layer.<br /><br />Input: [layer_ptr, layer_ptr, poe, p, e1, e0, layer_ptr, rem_ptr, x, x, x, x, x, x, x, x, ...]<br />Output: [is_not_last_layer, layer_ptr+8, layer_ptr+8, poe^4, f_pos, ne1, ne0, layer_ptr+8, rem_ptr, x, x, x, x, x, x, x, x, ...]<br /><br />Cycles: 83<br /> |
| verify_query_64 | Verifies one FRI query.<br /><br />This procedure is specialized to the case when the remainder polynomial, used in the final check,<br />is expected to have degree at most 64.<br />This procedure is exactly the same as `verify_query_128` except for the remainder polynomial check,<br />thus any change to one procedure will imply an equivalent change to the other one.<br /><br />Input: [poe, p, e1, e0, layer_ptr, rem_ptr, ...]<br />Output: [x, x, x, x, x, x, x, x, x, x, x, x, ...] (12 "garbage" elements)<br /><br />- poe is g^p.<br />- p is a query index at the first layer.<br />- (e0, e1) is an extension field element corresponding to the value of the first layer at index p.<br />- layer_ptr is the memory address of the layer data (Merkle tree root, alpha etc.) for the next<br />layer.<br />- rem_ptr is the memory address of the remainder polynomial.<br /><br />Cycles: 107 + num_layers * 83<br /> |
| verify_query_128 | Verifies one FRI query.<br /><br />This procedure is specialized to the case when the remainder polynomial, used in the final check,<br />is expected to have degree at most 128.<br />This procedure is exactly the same as `verify_query_64` except for the remainder polynomial check,<br />thus any change to one procedure will imply an equivalent change to the other one.<br /><br />Input: [poe, p, e1, e0, layer_ptr, rem_ptr, ...]<br />Output: [x, x, x, x, x, x, x, x, x, x, x, x, ...] (12 "garbage" elements)<br /><br />- poe is g^p.<br />- p is a query index at the first layer.<br />- (e0, e1) is an extension field element corresponding to the value of the first layer at index p.<br />- layer_ptr is the memory address of the layer data (Merkle tree root, alpha etc.) for the next<br />layer.<br />- rem_ptr is the memory address of the remainder polynomial.<br /><br />Cycles: 140 + num_layers * 83<br /> |
| verify | Verifies a FRI proof where the proof was generated over the quadratic extension of the base<br />field and layer folding was performed using folding factor 4.<br /><br />Input: [...]<br />Output: [...]<br /><br />Cycles:<br /><br />Polynomial degree less than 64: 24 + num_queries * (107 + num_layers * 83)<br />Polynomial degree less than 128: 24 + num_queries * (140 + num_layers * 83)<br /> |