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 />
## std::crypto::fri::frie2f4
| Procedure | Description |
| ----------- | ------------- |
| 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 2 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: [layer_ptr + 2, layer_ptr + 2, poe^4, f_pos, ne1, ne0, layer_ptr + 2, rem_ptr, x, x, x, x, x, x, x, x, ...]<br /><br />Cycles: 76<br /> |
| verify_query | Verifies one FRI query.<br /><br />Input:  [poe, p, e1, e0, layer_ptr, rem_ptr, ...]<br />Output: [x, x, x, x, x, x, x, x, x, x, ...]<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 codeword.<br /><br />Cycles: 40 + num_layers * 76<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 />Note that the check that the remainder codeword corresponds to the remainder polynomial received<br />by the verifier should now be performed by the calling procedure.<br /><br />Input:  [query_ptr, layer_ptr, rem_ptr, g, ...]<br />Output: [...]<br /><br />- query_ptr is a pointer to a list of tuples of the form (e0, e1, p, poe) where poe is equal<br />to g^p with g being the initial FRI domain generator. p is the query index at the first layer<br />and (e0, e1) is an extension field element corresponding to the value of the first layer at index p.<br />- layer_ptr is a pointer to the first layer commitment denoted throughout the code by C.<br />layer_ptr + 1 points to the first [alpha0, alpha1, t_depth, d_size] where d_size is the size<br />of initial domain divided by 4, t_depth is the depth of the Merkle tree commitment to the<br />first layer and (alpha0, alpha1) is the first challenge used in folding the first layer.<br />Both t_depth and d_size are expected to be smaller than 2^32. Otherwise, the result of<br />this procedure is undefined.<br />- rem_ptr is a pointer to the first tuple of two consecutive degree 2 extension field<br />elements making up the remainder codeword. This codeword can be of length either 32 or 64.<br /><br />The memory referenced above is used contiguously, as follows:<br /><br />[query_ptr ... layer_ptr ... rem_ptr ...]<br /><br />This means for example that:<br />1. rem_ptr - 1 points to the last (alpha0, alpha1, t_depth, d_size) tuple.<br />2. layer_ptr - 1 points to the last (e0, e1, p, poe) tuple.<br /><br />Cycles: 7 + 4 + num_queries * (40 + num_layers * 76 + 26)<br /> |