Struct PreImageCache

Helper struct to manage a range of pre-images

struct PreImageCache ;

When dealing with pre-images, the only unrecoverable data is the seed. Everything else is, by definition, derived from the seed. As a result, we can compress the data as much as we want, to reduce memory usage. However, this comes at the cost of more computation.

For example, if we have cycles of 10 pre-images, we can first compute the seed (H0), then reveal our initial commitment (H9). This will cost us 9 hash operations. Then on the next reveal, in order to get H8, we need to perform 8 hash operations, then 7 for H7, etc...

If we want to improve this, we can store intermediate results: when generating H9, we do perform 9 hash operations, but store H5. Hence, when generating H8 and H7, we only need to perform 3 and 2 hash operations, respectively, and will never need to perform more than 4 operations (save the initial commitment).

This structure is a mean to generalize this approach, with arbitrary count and arbitrary sample size (interval, or distance, between saved pre-images).

Constructors

NameDescription
this () Default-initialized PreImageCache is not valid, make sure it can't be accidentally constructed (e.g. by embbeding it in another aggregate)
this (data_, sample_size) Construct an instance using already existing data
this (count, sample_size) Construct an instance and allocate memory

Methods

NameDescription
byStride () Alias to the underlying data, useful when dealing with multiple levels
length ()
opIndex (index) Get the hash at index idx in the cycle
reset (seed, length) Populate this cache from the seed
toString (sink, mode) Print the content of a cache

Enums

NameDescription
PrintMode Describe print modes for toString

Aliases

NameDescription
opDollar

Example

Hash[32] data;
data[0] = hashFull("Hello World");
foreach (idx, ref entry; data[1 .. $])
    entry = hashFull(data[idx]);

// First case and last two are degenerate
immutable intervals = [1, 2, 4, 8, 16];
foreach (interval; intervals)
{
    auto cache = PreImageCache(data.length / interval, interval);
    cache.reset(data[0]);
    foreach (idx, const ref value; data)
        assert(value == cache[idx]);

    // Test `length` and `$` properties
    assert(cache[$-1] == data[$-1]);
    assert(cache[cache.length - 1] == data[$-1]);

    switch (interval)
    {
    case 32:
    case 16:
    case 8:
    case 4:
    case 2:
    case 1:
        assert(cache.data.length == (32 / interval));
        size_t data_idx;
        foreach (idx, const ref entry; cache.data)
        {
            assert(entry == data[data_idx]);
            data_idx += interval;
        }
        break;

    case 64:
        assert(cache.data.length == 1);
        assert(cache.data[0] == data[0]);
        break;

    default:
        assert(0);
    }
}