Documentation - Prehashed #87
Conversation
There was a problem hiding this comment.
As you wrote quite formally, it is not very easy to read. I would cut sentences and try to write more naturally for readability.
I am not sure it is clear that instead of making "checks live" we precompute the hashes in advance and link sequences to bins. As such, in "live" we only have to check memory to see which elements are the next in a sequence. This is cheaper than the naive scheme because we perform many more checks than the cardinality of Sp (in average). Also the bin have in average only one element (of course this is when the prover only has np elements).
Co-authored-by: Raphael <[email protected]>
docs/prehashing.md
Outdated
|
|
||
| **Construction with Prehashing** optimizes the basic Telescope ALBA protocol by reducing the computational cost of checking sequences. | ||
| Here, a sequence means an ordered set of elements or tuples that meet certain hash conditions in the protocol. | ||
| In the basic approach, we would attempt to extend a given sequence "blindly" with all elements of $S_p$. |
There was a problem hiding this comment.
what do you mean by blindly?
There was a problem hiding this comment.
I think @rrtoledo means without implementing the prehash oracle, by blindly.
There was a problem hiding this comment.
By "blindy" I meant searching having no information and using all elements.
Co-authored-by: Raphael <[email protected]>
| > - $\mathsf{bin_3}$: $\emptyset$ | ||
| > - No valid $s_2$ can be selected. | ||
| > - Backtracking for $t = 1$: | ||
| > - After exhausting all possible sequences for $t = 1$, no valid proof is found. |
There was a problem hiding this comment.
Are you implying here that C doesn't work?
| - When constructing sequences, the prover selects elements directly from the current bin to extend the sequence, continuing this process until the sequence reaches the required length $u$. | ||
| - After constructing a sequence of length $u$, the prover validates it with $H_2$. The sequence is a valid proof if $H_2(t, s_1, \dots, s_u) = 1$. | ||
|
|
||
| The precomputed $H_0$ values enable quick checks to see if a new element can extend a sequence, based on whether $H_1(t, s_1, \dots, s_k)$ matches $H_0(s_{k+1})$. |
There was a problem hiding this comment.
"The values precomputed with
"based on whether
| > - Compute $H_1(2, s_1, s_2)$ to determine the next bin to explore. | ||
| > - Assume $H_1(2, D, B) = 1$, so the prover looks in bin 1. | ||
| > - $\mathsf{bin_1}$: $\[A, C\]$ | ||
| > - Extend the sequence with $s_3 = C$. |
There was a problem hiding this comment.
Why do we extend with C, not A?
| > - $\pi:~~$ `proof`, a valid proof $(t, s_1, \ldots, s_u)$ or $\bot$. | ||
| > --- | ||
| > - $bins \leftarrow$ { } | ||
| > - **for** each $~~ i \in \[1,~ n_p\]:$ |
There was a problem hiding this comment.
This is a bit confusing. Here [ ] denotes an interval, but above for bins it denoted a list or a set. Suggest to use for bins either ( ) if it's a list or { } if it's a set.
| > - Output: | ||
| > - $0/1$. | ||
| > --- | ||
| > - **if** $~~ t ~∉ \[d\]:$ |
There was a problem hiding this comment.
If we are using notation [d] here, we can also use it everywhere else instead of [1, x].
Content
This PR includes documentation of Telescope construction with prehashing.
Pre-submit checklist
Comments
Issue(s)
Closes #85