1
$\begingroup$

Balloon's theorem says:

enter image description here

Questions:

  1. Am I understanding the variables correctly?

    • $n$ is number of blocks the user chooses.
    • $r$ is number of rounds the user chooses.
    • $\delta$ is number of pseudorandom dependencies the user chooses per-round per-deterministic block.
    • $S$ is number of memory blocks the adversary has, which is usually $S<n$ as the adversary tries to lower her costs.
    • $T$ is the number of blocks the adversary has to hash by using her $S$ many blocks memory.

  2. Since the theorem doesn't specify the margin by which $S$ is smaller than $n$, does this mean that it does not matter how smaller $S$ is than $n$ in terms of the equations?

  3. What if the adversary has as much space as the normal user? Would it be the case where $S=n$? Would the run-time become $$ S\cdot T = r\cdot n $$?

  4. What if $n=8$ blocks, $r=3$ rounds and $\delta=3$ random dependencies? Is the theorem implying that the adversary would guarantee solving it faster?

    Because if we plug the numbers in, we get: $$ \frac{3 \cdot 8^2}{32} = 4 $$ , which is less than the total number of hashes that an honest user would do, which (from my understanding of the Balloon algorithm) is: $$ r \cdot n = 3 \cdot 8 = 24 $$

  5. For the 2nd and stronger bound, the theorem says when $\delta=7$ and $S < n/64$—does this mean that if the adversary has $64$-fold less than user's $n$ blocks?

    For example, is it saying that, if the user has $1000$ many blocks space, then the stronger proof works if the adversary has $1024/64=16$ blocks?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Note also Theorem 33 from the paper and the accompanying proof, as that is the formal version of Theorem 1. $\endgroup$ Commented Jan 22 at 18:46

1 Answer 1

Reset to default
1
$\begingroup$

So here are my answers to your questions:

  1. Am I understanding the variables correctly?

Yes, basically, but $T$ has a few different meanings thoughout the paper. It mostly means time spent.

  1. Since the theorem doesn't specify the margin by which $S$ is smaller than $n$, does this mean that it does not matter how smaller $S$ is than $n$ in terms of the equations?

They specify in the paper that the weaker bound applies when $delta=3$ and $S < n/6$ and that the stronger bound applies when $delta=7$ and $S<n/64$.

  1. What if the adversary has as much space as the normal user? Would it be the case where $S=n$? Would the run-time become $S\cdot T = r\cdot n$?

No it should be more should $T=r\cdot n$, as far as I know.

  1. What if $n=8$ blocks, $r=3$ rounds and $\delta=3$ random dependencies? Is the theorem implying that the adversary would guarantee solving it faster? Because if we plug the numbers in, we get: $\frac{3 \cdot 8^2}{32} = 4$ , which is less than the total number of hashes that an honest user would do, which (from my understanding of the Balloon algorithm) is: $r \cdot n = 3 \cdot 8 = 24$

No, they specify in the paper that $n\geq 16$ and it should always be way way bigger than that.

  1. For the 2nd and stronger bound, the theorem says when $\delta=7$ and $S < n/64$—does this mean that if the adversary has $64$-fold less than user's $n$ blocks? For example, is it saying that, if the user has $1000$ many blocks space, then the stronger proof works if the adversary has $1024/64=16$ blocks?

Yes.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.