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
Name | Description |
---|---|
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
Name | Description |
---|---|
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
Name | Description |
---|---|
PrintMode
|
Describe print modes for toString
|
Aliases
Name | Description |
---|---|
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);
}
}