Documentation - Centralized Telescope: Main #101
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
curiecrypt
force-pushed
the
curiecrypt/doc-centralized-main
branch
from
cdee2bf to
22a9c73
Compare
rrtoledo
requested changes
Dec 16, 2024
rrtoledo
approved these changes
Dec 24, 2024
| - The prover retries the proof generation process up to $r$ times. | ||
| - Each retry uses a different retry counter $v$, where $v \in \[1, r\]$, to diversify the search process. | ||
| - Hash-based binning: | ||
| - Elements in $S_p$ are prehashed into bins using $H_0(v, \cdot) where v \in \[1,r\]$, grouping elements based on their hash values. We prehashed using the retry counter to get different bins for each repetition, reducing the risk of badly distributed bins. |
There was a problem hiding this comment.
Suggested change
| - Elements in $S_p$ are prehashed into bins using $H_0(v, \cdot) where v \in \[1,r\]$, grouping elements based on their hash values. We prehashed using the retry counter to get different bins for each repetition, reducing the risk of badly distributed bins. | |
| - Elements in $S_p$ are prehashed into bins using $H_0(v, \cdot)\ where\ v \in \[1,r\]$, grouping elements based on their hash values. We prehashed using the retry counter to get different bins for each repetition, reducing the risk of badly distributed bins. |
| - Retries with index $v$: | ||
| - The prover retries the proof generation process up to $r$ times. | ||
| - Each retry uses a different retry counter $v$, where $v \in \[1, r\]$, to diversify the search process. | ||
| - Hash-based binning: |
There was a problem hiding this comment.
Suggested change
| - Hash-based binning: | |
| - Seeded binning: |
|
|
||
| ## Overview | ||
| - When $n_p$ is large, the rapid growth in potential proof tuples increases the chances of finding a valid proof, making construction easier. | ||
| - For small $n_p$, limited elements reduce the probability of finding a valid proof in a single attempt. |
There was a problem hiding this comment.
The real reason is that when n_p is small, the arrangement of balls into bins is far from uniform. On average each bin still gets exactly one ball, but it's likely that many bins will be empty and some will have many elements. Turns out it's better to have many bins with one ball than one bin with many balls.
There was a problem hiding this comment.
When n_p is small, we still can use the scheme with prehashing, but the completeness error is moderate instead of tiny. By introducing retries, the completeness error is decreased.
| - The prover retries the proof generation process up to $r$ times. | ||
| - Each retry uses a different retry counter $v$, where $v \in \[1, r\]$, to diversify the search process. | ||
| - Hash-based binning: | ||
| - Elements in $S_p$ are prehashed into bins using $H_0(v, \cdot) where v \in \[1,r\]$, grouping elements based on their hash values. We prehashed using the retry counter to get different bins for each repetition, reducing the risk of badly distributed bins. |
There was a problem hiding this comment.
Suggested change
| - Elements in $S_p$ are prehashed into bins using $H_0(v, \cdot) where v \in \[1,r\]$, grouping elements based on their hash values. We prehashed using the retry counter to get different bins for each repetition, reducing the risk of badly distributed bins. | |
| - Elements in $S_p$ are prehashed into bins using $H_0(v, \cdot)$ where $v \in \[1,r\]$, grouping elements based on their hash values. We prehashed using the retry counter to get different bins for each repetition, reducing the risk of badly distributed bins. |
| 4. **Bounded DFS**: | ||
| - A bounded DFS search is used to construct the sequence $(t, s_1, ..., s_u)$, with a shared step limit $B$ applied across all starting points $t$. | ||
| - At each step of DFS: | ||
| - The algorithm search a new element for the current sequence $(t, s_1, ..., s_k)$ in bin numbered $H_1(v, t, s_1, ..., s_k)$. |
There was a problem hiding this comment.
Suggested change
| - The algorithm search a new element for the current sequence $(t, s_1, ..., s_k)$ in bin numbered $H_1(v, t, s_1, ..., s_k)$. | |
| - The algorithm searches a new element for the current sequence $(t, s_1, ..., s_k)$ in bin numbered $H_1(v, t, s_1, ..., s_k)$. |
| - With the new $v$, the hash function $H_0(v, s)$ is applied to organize elements of $S_p$ into bins, and the process resumes from step 3. | ||
| 7. **Completion**: | ||
| - If a valid proof is found in any retry, the prover outputs the proof immediately. | ||
| - If all $r$ retries are exhausted without finding a valid proof, the process terminates, and the prover outputs $\bot$. |
There was a problem hiding this comment.
Will there be pseudocode like in previous docs?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Content
This PR includes general information about the Section 3.2.2. Generalization to small$n_p$ ,
centralized_telescope.The further details such as parameter setup, algorithms will be handled in individual PRs.
Pre-submit checklist
Issue(s)
Closes #100