Multiple databus reads from same index #937
Comments
AztecBot
pushed a commit
that referenced
this issue
Jul 15, 2024
TLDR: Up until now we were limited to only 1 read per entry of a databus
column (see explanation of why below). This PR removes this limitation
so that we can read from any row arbitrarily many times at the cost of
adding one polynomial/commitment per databus column.
Note: this PR also cleans up some of the handling of ecc op wires and
databus polys in various places by making better use of Flavor style
getters.
Explanation: The log derivative lookup relation involves a polynomial
that contains inverses, i.e. I_i = (read_term_i*write_term_i)^{-1}.
These inverses only need to be computed when the relation is "active",
i.e. when the row in question either contains a databus read gate or
data that is being read. At all other rows, we simply set the value of
the inverse polynomial to 0. This allows a subrelation of the form:
`read_term * write_term * inverses - inverse_exists`
Where `inverse_exists` is a polynomial that takes 1 if the relation is
active (or equivalently, if the inverse has been computed) and 0
otherwise. Therefore, if the inverse has been computed, we check that it
is indeed equal to the inverse of `read_term * write_term`, otherwise,
the subrelation contribution is trivially 0. If we only allow a single
read from each row of a bus column, the term `inverse_exists` can be
computed as an algebraic OR of the form:
`is_read_gate + read_counts - (is_read_gate * read_counts)`
since both `is_read_gate` and `read_counts` are both boolean. If
`read_counts` is no longer boolean, no such algebraic expression exists.
The solution is to introduce a dedicated boolean polynomial `read_tag`
whose values are given by `min(1, read_counts)`, i.e. 1 if one or more
reads have been performed at that row, and 0 otherwise.
Closes #937
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Currently the databus does not allow multiple reads from the same index. (This is plausibly OK for the long term, see note at bottom). This is to ensure that
read_countscan be treated as boolean which allows it to be used in a boolean expression of the forminverse_exists = is_read_gate + read_counts - (is_read_gate * read_counts);This expression is in turn used in the first subrelation in the DataBus relation which checks the correctness of the inverse polynomial via an expression like:[(read_term * write_term * inverses - inverse_exists) * scaling_factor](std::get<subrel_idx_1>(accumulator) += (read_term * write_term * inverses - inverse_exists) * scaling_factor;)At rows where the relation is "inactive" (i.e. no read and no write), inverses is equal to 0 (as is inverse_exists). If the relation is active, the term
read_term * write_term * inverseswill be equal to 1 (if the inverse was computed correctly) and so willinverse_exists, so the two will cancel.If we want to allow multiple reads, we need to come up with an efficient means for doing so. A naive approach would be to simply have an additional polynomial that takes the value 1 if one or more reads have been performed at a given index. But this adds another polynomial and another commitment for each databus column.
Note: It is plausibly acceptable to only allow single reads from databus columns which is why I'm leaving it in this state. Once a value has been read once, it's more efficient to connect it to another value via a copy constraint anyway. For
return_dataits almost certainly sufficient since a "read" is actually a "write" in the sense that the intent of performing a read is to establish a connection between some value value in the circuit and its counterpart in the return data. The values in return_data are known at the start of the circuit; only one read/write is required to establish those values were formed correctly. The single-read restriction is protected by an ASSERT.The text was updated successfully, but these errors were encountered: