Date: Mon, 27 Jan 2014 16:54:27 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Combining sliding window and bit-reversal

I did more testing of different DAG architectures while enhancing my
pebbling algorithm.  These benchmarks change as the code changes, but
here's an interesting data point.

I was comparing Catena-3 graphs to Alexander's power-of-two graphs,
and both did well in different areas.  Then I though, how about
combining them?  So, instead of picking random locations within the
sliding window, I pick bit-reversal based locations.  This results in
the hardest to pebble DAGs so far for my pebbling algorithm.

I'm thinking of using this without password dependent memory location
reads for the first 50%, and then for the last 50%, I'll use the
existing NoelKDF DAG, which will have a ton of edges back into the
sliding bit-reversal DAG.  Just to be specific about how this DAG is
generated, here is the function I wrote that creates edges from a
position in the graph to a prior position:

// Find the previous position using Alexander's sliding power-of-two
window, with Catena
// bit-reversal.
static uint32 findSlidingReversePos(uint32 pos) {
    // This is a sliding window which is the largest power of 2 < i.
    if(pos < 2) {
        return UINT32_MAX;
    }
    uint32 mask = 1;
    while(mask <= pos) {
        mask <<= 1;
    }
    mask = mask >> 1; // Mask is greatest power of 2 <= pos
    uint32 reversePos = bitReverse((pos) & (mask-1), mask);
    if(reversePos + 1 >= pos - mask) {
        return reversePos;
    }
    return reversePos + mask;
}

Bill

Powered by blists - more mailing lists