Difference between r2 and drg-attacks and CCS paper

# Difference between r2 and drg-attacks and CCS paper Difference between r2 and drg-attacks (and paper) are two folds: 1. different way to compute the bucket index 2. different way to compute the final value ## Bucket Index of the parent + In the paper algorithm (DRSample, Algorithm 1 in CCS [paper](https://acmccs.github.io/papers/p1001-alwenA.pdf), we have: ```rust g' <-- [1,floor(log2(v))+1] ``` + In r2, we have the following [code](https://github.com/nicola/r2/blob/master/src/graph.rs#L49): ```rust let logi = ((node * m) as f32).log2().floor() as usize; let j = rng.gen::<usize>() % logi; ``` => r2 uses the floor of the logarithm without doing a +1 when selecting the value and using modulo (which creates an exclusive upper bound). It gives rises to high differences in bucket index, as show below: ```rust v = 18, log2(v) = 4.16... // --- DRSample --- g' <-- [1, 5] // floor(log2(v)) = 4 // --- R2 --- g' <-- [1, 4[ <=> [1, 3] // upper bound is 4[ because of the modulo ``` + In drg-attacks, we have the following [code](https://github.com/nicola/r2/blob/master/src/graph.rs#L49) which follows the paper algorithm: ```rust let meta_idx = node * m; // ceil instead of floor() + 1 let max_bucket = (meta_idx as f32).log2().ceil() as usize; // [1, ceil(log2(v))] <=> [1, floor(log2(v)) + 1] let i: usize = rng.gen_range(1, max_bucket + 1); ``` **Note**: I believe that is the main issue that causes Valiant's attack to give back different results - ignoring a few buckets change the graph structure. ## Final Index of the parent + In the paper [Algorithm 1](https://acmccs.github.io/papers/p1001-alwenA.pdf), we have: ```rust g <-- min(v, 2^g') r <-- [max(g/2, 2) , g] return v - r ``` + In r2 we have ```rust // min(v, 2^g') let jj = cmp::min(node * m + k, 1 << (j + 1)); // r <-- [ max(jj/2, 2), jj ] let back_dist = rng.gen_range(cmp::max(jj >> 1, 2), jj + 1); // v - r let out = (node * m + k - back_dist) / m; ``` + In drg-attacks we have: ```rust // g = min(v, 2^g') let max = std::cmp::min(meta_idx, 1 << i); // max(2, g / 2) let min = std::cmp::max(2, max >> 1); // return v - [ max(2, g/2), g ] let meta_parent = node * m - rng.gen_range(min, max); // no "+ k" here let real_parent = meta_parent / degree; ``` The reason for drg-attacks to NOT include the "+k" is because it prevents falling on the same "real" node when we divide by the degree. Basically, drg-attacks always choose the minimum index for the "bucket of meta nodes". For example, with $d = 3$, node 2 gets mapped to $\{6,7,8\}$. * To find a parent for node 2, drg-attacks's code takes 3 times the meta index 6 as an upper bound so that it always find a number $v - r < 6$. * In r2, for the third iteration, the "meta index" would be 8 so I may end up selecting the meta-node $8 - 2 = 6$, which corresponds to the same index in the basic graph ($6/d = 2$) ! From what I understand of the paper algorithm, this should not be possible and is not desirable: for a given child $u$, we always select a parent node $v$ such that $2^(i-1) <= dist(v,u) <= 2^i$ , so $dist(u,v) > 1$. In the code they even go further since the minimum to choose r from is 2, so $v = u - r <= u - 2 \neq v$.