barretenberg icon indicating copy to clipboard operation
barretenberg copied to clipboard

Multiple databus reads from same index

Open ledwards2225 opened this issue 10 months ago • 0 comments

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_counts can be treated as boolean which allows it to be used in a boolean expression of the form inverse_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 * inverses will be equal to 1 (if the inverse was computed correctly) and so will inverse_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_data its 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.

ledwards2225 avatar Apr 03 '24 20:04 ledwards2225