Comment
Author: Admin | 2025-04-28
Since each uses a blue move. If \(b+m , then \(\mathbf {P}_j\) must use at least \(n/m'\) red moves for each immediate predecessor in the third category. Under the conditions in the theorem, the cost of \(n/m'\) red moves is greater than a blue move since \(c_rn/m' > c_b\). Thus, the best strategy is to use blue moves over red moves for vertices on the input path whenever possible. Therefore,$$\begin{aligned} \mathsf {ec}(\mathbf {P}_j)&\ge c_rm' + c_b(m'-m-1)> (c_b+c_r)(m'-m-1) \\ \mathsf {ec}(\mathbf {P})&= \varSigma _{j\,=\,1}^{n/m'} \mathsf {ec}(\mathbf {P}_j) > (c_b+c_r)n(1-\frac{2(m+1)c_b}{nc_r}). \end{aligned}$$ \(\square \) When n is sufficiently large, a bit-reversal graph is bandwidth hard. Its red-blue pebbling complexity has a lower bound close to \((c_b+c_r)n\). An ASIC’s energy advantage is similar to that of scrypt, \(A_\mathsf {ec}\approx \frac{2c_{b,\mathsf {cpu}}+3c_{r,\mathsf {cpu}}}{c_{b,\mathsf {asic}}+c_{r,\mathsf {asic}}}\) and \(A_\mathsf {ec}\approx 18\) with parameters in Table 1. The capacity requirement on bit-reversal graphs to remain bandwidth hard is also similar to the requirement for scrypt.5.3 Stacked ExpandersAn \((n, \alpha , \beta )\) bipartite expander \((0 is a directed bipartite graph with n sources and n sinks such that any subset of \(\alpha n\) sinks are connected to at least \(\beta n\) sources. Prior work has shown that bipartite expanders for any \(0 exist given sufficiently many edges. For example, Pinsker’s construction [48] simply connects each sink to d independent sources. It yields an \((n, \alpha ,\beta )\) bipartite expander for sufficiently large n with overwhelming probability [25] if$${d > \frac{\mathrm {H_b}(\alpha ) + \mathrm {H_b}(\beta )}{-\alpha \log _2\beta }}$$where \({\mathrm {H_b}(\alpha )=-\alpha \log _2\alpha -(1-\alpha )\log _2(1-\alpha )}\).An \((n,k,\alpha ,\beta )\) stacked expander graph is constructed by stacking k bipartite expanders back to back. It has \({n(k+1)}\) vertices, partitioned into \(k+1\) sets each of size n, \({V=\{V_0, V_1, V_2, \cdots , V_k\}}\) with all edges are directed from \(V_{i\,-\,1}\) to \(V_{i}\) \((i \in [1..k])\). \(V_{i\,-\,1}\) and \(V_{i}\) plus all edges between them form an \((n, \alpha ,\beta )\) bipartite expander \(\forall i \in [1..k]\). The bipartite expanders at different layers can but do not have to be the same. Its maximum in-degree is the same as the underlying \((n, \alpha ,\beta )\) bipartite expanders.In the Balloon hashing algorithm, the vertices are furthered chained sequentially, i.e., there exist edges \((v_{i,j}, v_{i,j\,+\,1})\) for each \(0 \le i \le k, 0 \le j \le n-2\) as well as an edge \((v_{i,n\,-\,1},v_{i\,+\,1,0})\) for each \(0 \le i \le k\). In other words, Balloon hashing uses a stacked random sandwich graph in which each vertex has \(d>1\) predecessors from the previous layer. Figure 3 is a stacked random sandwich graph with \(n=4\), \(k=2\) and \(d=2\). In the figure, two consecutive layers form a \((4,4,\frac{1}{4},\frac{1}{2})\) expander.Fig. 3.A stacked random sandwich graph with \(n=4\), \(k=2\)
Add Comment