Table projections - Githubissues

sga001 commented 1 year ago

Table projections can be used whenever the verifier know which entries in the table the prover will access. For example, in DNA regex, the verifier will know the positions of the chunks of relevant characters.

In such cases, we need a few things from the front-end.

(1) It needs to identify what these "public chunks" are (not their content, just their indices). This is inferrable from the regex. For example "^.{100}abc.{40}def.*$", would have the public chunks at positions [100, 103] and [143, 146]. One restriction is that the positions of these chunks need to be at power-of-2 boundaries. For example, above we might have to pick "larger" chunks that strictly necessary in order to ensure that [100, 103] and [143, 146] fall into power-of-2 ranges when you keep slicing the table in two.

(2) It needs to notify the backend of this fact and the specific chunks through some API so that the backend knows that it can perform a table projection on the document.

The backend needs to do the following.

(3) It needs to perform the projection as per the description in "projection.txt" in the repo. Note that the description is for a single "chunk" but we will generalize it to any chunks.

(4) Perform the sumcheck in nlookup with respect to the projected table rather than the original.

(5) Use the "selector vector" s (in the projection.txt document) as if it were some of the random values the verifier provided to produce the IPA proof on the entire original table.

(6) Verfier checks IPA proof as before.

Front-end:

[x] Automatically infer public chunks boundaries
[x] Figure out the correct power-of-2 boundaries.
[x] API to communicate this information to backend
[ ] Extend to alts

Back-end

[x] Perform table projection given chunks
[x] Perform nlookup on table projection (whenever possible) instead of original
[x] Update the way IPA proof is produced
[x] Verify IPA proof for projection

sga001 commented 1 year ago

@elefthei : how are you communicating public chunks to the backend? For example, if the regex is "^.{100}abc.{40}def.*$", how are you telling the backend that these indices are "public" so it is safe to do additional optimizations like projections that reveal these indices.

In contrast, "^.*abc.*" also has skips, but in this case the indices are private so we cannot do projections.

elefthei commented 1 year ago

That’s precisely what an open set means, open bound corresponds to .* and closed to public indices

On Fri, Jun 16, 2023 at 7:22 PM Sebastian Angel @.***> wrote:

@elefthei https://github.com/elefthei : how are you communicating public chunks to the backend? For example, if the regex is "^.{100}abc.{40}def.*$", how are you telling the backend that these indices are "public" so it is safe to do additional optimizations like projections that reveal these indices.

In contrast, "^.abc.", also has skips, but in this case the indices are private so we cannot do projections.

— Reply to this email directly, view it on GitHub https://github.com/elefthei/rezk/issues/70#issuecomment-1595008965, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAF3HLCGCAXWKEAVAOKFLATXLSI63ANCNFSM6AAAAAAY4QP2LQ . You are receiving this because you were mentioned.Message ID: @.***>

-- Lefteris Ioannidis, MIT 2014

sga001 commented 1 year ago

No, that doesn't make sense. Here's an example:

"^.*abc.{100}hello"

Here, there are no public indices at all. Because if you reveal the position of where c ends and h begins, you are also leaking information about the private indices (.*) at the beginning.

Or are you suggesting that: any prefix of open sets that includes closed ranges is public? Only after there is a open set does it become private?

But even then, here's another example that contradicts this.

".{2, 100}abc". Here, if you reveal that it's actually 70, that's also leaking information. This has the closed range (2, 100). So this doesn't work either.

elefthei commented 1 year ago

The indices are not on absolute terms, they are additive and we call them skips. In your example, there is a private index w_i pointing to the first ‘a’ then a constraint w_i + 102 = w_j which specifies is the index of the first ‘h’ in hello.

On Fri, Jun 16, 2023 at 8:21 PM Sebastian Angel @.***> wrote:

No, that doesn't make sense. Here's an example:

"^.*abc.{100}hello"

Here, there are no public indices at all. Because if you reveal the position of where c ends and h begins, you are also leaking information about the private indices (.*) at the beginning.

— Reply to this email directly, view it on GitHub https://github.com/elefthei/rezk/issues/70#issuecomment-1595106371, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAF3HLECV2MPL5HUK2QCZULXLSP2VANCNFSM6AAAAAAY4QP2LQ . You are receiving this because you were mentioned.Message ID: @.***>

-- Lefteris Ioannidis, MIT 2014

sga001 commented 1 year ago

You are not understanding my question. A "public" index is an index that the verifier knows. They know the actual value of the index. It has to be an absolute value.

Remember the DNA example.

"^.{100}ATTAG.{40000}AAC.*$

There, it is all about absolute indexes. It is only when they are absolute and known in the regex, that they are public. Otherwise they cannot be public since they reveal information about the document.

This Issue is all about: how to figure out which indices are public so that the backend can perform optimizations for them. This needs to be done at the regex level / SAFA level, since the backend doesn't have this information.

elefthei commented 1 year ago

I understood the question, if everything is public then I perform the computation of absolute indices from additive. In any case I am traveling right now, Jess understands how skips work and can explain them to you.

On Fri, Jun 16, 2023 at 8:31 PM Sebastian Angel @.***> wrote:

You are not understanding my question. A "public" index is an index that the verifier knows. They know the actual value. It has to be an absolute value.

Remember the DNA example.

"^.{100}ATTAG.{40000}AAC.*$

There, it is all about absolute indexes. It is only when they are absolute and known in the regex, that they are public. Otherwise they cannot be public since they reveal information about the document.

This Issue is all about: how to figure out which indices are public so that the backend can perform optimizations for them. This needs to be done at the regex level.

— Reply to this email directly, view it on GitHub https://github.com/elefthei/rezk/issues/70#issuecomment-1595119287, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAF3HLE4VJK546YOUVLN2H3XLSQ6VANCNFSM6AAAAAAY4QP2LQ . You are receiving this because you were mentioned.Message ID: @.***>

-- Lefteris Ioannidis, MIT 2014

ecmargo commented 1 year ago

Front end is done assuming no changes to specifications

elefthei / rezk

Table projections #70