hash it 1,000,000 times. This gives the first "random" number.
Hashed 999,999 times gives the second number, etc. ie:
- R(1,000,000) = seed
- R(N-1) = SHA256(R(N))
+ R(0) = seed
+ R(N+1) = SHA256(R(N))
This way the remote node needs only to remember the last R(N) it was
-given, and it can calculate any R for N-1 or below.
+given, and it can calculate any R for N+1 or above.
However, this means we need to generate 1 million hashes up front, and
then do almost as many hashes to derive the next number. That's slow.
-A More Complex Solution
------------------------
-
-Instead of a one-dimensional chain, we can use two dimensions: 1000
-chains of 1000 values each. Indeed, we can set generate the "top" of
-each chain much like we generated a single chain:
-
- Chain 1000 Chain 999 Chain 998 ...........Chain 1
- seed SHA256(C1000) SHA256(C999) ....... SHA256(C2)
-
-Now, deriving chain 1000 from seed doesn't quite work, because it'll
-look like this chain, so we flip the lower bit to generate the chain:
-
- Chain 1000 Chain 999 Chain 998 ...........Chain 1
-1000 seed^1 SHA256(C1000)^1 SHA256(C999)^1...... SHA256(C2)^1
- 999 SHA256(above) SHA256(above) SHA256(above) ..... SHA256(above)
- 998 SHA256(above) SHA256(above) SHA256(above) ..... SHA256(above)
- ...
-
-Now, we can get the first value to give out (chain 1, position 1) with
-999 hashes to get to chain 1, and 999 hashes to get to the end of the
-chain. 2000 hashes is much better than the 999,999 hashes it would
-have taken previously.
-
-Why Stop at 2 Dimensions?
--------------------------
-
-Indeed, the implementation uses 64 dimensions rather than 2, and a
-chain length of 2 rather than 1000, giving a worst-case of 63 hashes
-to derive any of 2^64 values. Each dimension flips a different bit of
-the hash, to ensure the chains are distinct.
-
-For simplicity, I'll explain what this looks like using 8 dimensions,
-ie. 8 bits. The seed value always sits the maximum possible index, in
-this case index 0xFF (b11111111).
-
-To generate the hash for 0xFE (b11111110), we need to move down
-dimension 0, so we flip bit 0 of the seed value, then hash it. To
-generate the hash for 0xFD (b11111101) we need to move down dimension
-1, so we flip bit 1 of the seed value, then hash it.
-
-To reach 0xFC (b11111100) we need to move down dimension 1 then
-dimension 0, in that order.
-
-Spotting the pattern, it becomes easy to derive how to reach any value:
-
- hash = seed
- for bit in 7 6 5 4 3 2 1 0:
- if bit not set in index:
- flip(bit) in hash
- hash = SHA256(hash)
-
-Handling Partial Knowledge
---------------------------
-
-How does the remote node, which doesn't know the seed value, derive
-subvalues?
-
-Once it knows the value for index 1, it can derive the value for index
-0 by flipping bit 0 of the value and hashing it. In effect, it can
-always derive a value for any index where it only needs to clear bits.
-
-So, index 1 gives index 0, but index 2 doesn't yield index 1. When
-index 3 comes along, it yields 2, 1, and 0.
-
-How many hash values will we have to remember at once? The answer is
-equal to the number of dimensions. It turns out that the worst case
-for 8 dimensions is 254 (0b11111110), for which we will have to
-remember the following indices:
-
- 127 0b01111111
- 191 0b10111111
- 223 0b11011111
- 239 0b11101111
- 247 0b11110111
- 251 0b11111011
- 253 0b11111101
- 254 0b11111110
-
-127 lets us derive any hash value for index <= 127. Similarly, 191
-lets us derive anything > 127 but <= 191. 254 lets us derive only
-itself.
-
-When we get index 255 this collapses, and we only need to remember
-that one index to derive everything.
+A Tree Solution
+---------------
+
+A better solution is to use a binary tree, with the seed at the root.
+The left child is the same as the parent, the right child is the
+SHA256() of the parent with one bit flipped (corresponding to the
+height).
+
+This gives a tree like so:
+
+ seed
+ / \
+ / \
+ / \
+ / \
+ seed SHA256(seed^1)
+ / \ / \
+ seed SHA256(seed^2) SHA256(seed^1) SHA256(SHA256(seed^1)^2)
+Index: 0 1 2 3
+
+Clearly, giving R(2) allows you to derive R(3), giving R(1) allows you
+to derive nothing new (you still have to remember R(2)), and giving
+R(0) allows you to derive everything.
+
+In pseudocode, this looks like the following for a 64 bit tree:
+
+generate_from_seed(index):
+ value = seed
+ for bit in 0 to 63:
+ if bit set in index:
+ flip(bit) in value
+ value = SHA256(value)
+ return value
+
+
+The Receiver's Tree
+-------------------
+
+To derive the value for a index N, you need to have the root of a tree
+which contains it. That is the same as needing an index I which is N
+rounded down in binary: eg. if N is 0b001100001, you need 0b001100000,
+0b001000000 or 0b000000000.
+
+Pseudocode:
+
+# Can we derive the value for to_index from from_index?
+can_derive(from_index, to_index):
+ # to_index must be a subtree under from_index; this is the same as
+ # saying that to_index must be the same as from_index up to the
+ # trailing zeros in from_index.
+ for bit in count_trailing_zeroes(from_index)..63:
+ if bit set in from_index != bit set in to_index:
+ return false
+ return true
+
+# Derive a value from a lesser index: generalization of generate_from_seed()
+derive(from_index, to_index, from_value):
+ assert(can_derive(from_index, to_index))
+ value = from_value
+ for bit in 0..63:
+ if bit set in to_index and not bit set in from_index:
+ flip bit in value
+ value = SHA256(value)
+ return value
+
+If you are receiving values (in reverse order), you need to remember
+up to 64 of them to derive all previous values. The simplest method
+is to keep an array, indexed by the number of trailing zeroes in the
+received index:
+
+# Receive a new value (assumes we receive them in order)
+receive_value(index, value):
+ pos = count_trailing_zeroes(index)
+ # We should be able to generate every lesser value, otherwise invalid
+ for i in 0..pos-1:
+ if derive(index, value, known[i].index) != known[i].value:
+ return false
+ known[pos].index = index
+ known[pos].value = value
+ return true
+
+To derive a previous value, find an element in that array from which
+you can derive the value you want, eg:
+
+# Find an old value
+regenerate_value(index):
+ for i in known:
+ if can_derive(i.index, index):
+ return derive(i.index, i.value, index)
+ fail
+
+You can see the implementation for more optimized variants of the
+above code.
Rusty Russell <rusty@rustcorp.com.au>
#include <string.h>
#include <assert.h>
+#define INDEX_BITS ((sizeof(shachain_index_t)) * CHAR_BIT)
+
static void change_bit(unsigned char *arr, size_t index)
{
arr[index / CHAR_BIT] ^= (1 << (index % CHAR_BIT));
}
-/* We can only ever *unset* bits, so to must only have bits in from. */
+static int count_trailing_zeroes(shachain_index_t index)
+{
+#if HAVE_BUILTIN_CTZLL
+ return index ? __builtin_ctzll(index) : INDEX_BITS;
+#else
+ int i;
+
+ for (i = 0; i < INDEX_BITS; i++) {
+ if (index & (1ULL << i))
+ break;
+ }
+ return i;
+#endif
+}
+
static bool can_derive(shachain_index_t from, shachain_index_t to)
{
- return (~from & to) == 0;
+ shachain_index_t mask;
+
+ /* Corner case: can always derive from seed. */
+ if (from == 0)
+ return true;
+
+ /* Leading bits must be the same */
+ mask = ~((1ULL << count_trailing_zeroes(from))-1);
+ return ((from ^ to) & mask) == 0;
}
static void derive(shachain_index_t from, shachain_index_t to,
/* We start with the first hash. */
*hash = *from_hash;
- /* This represents the bits set in from, and not to. */
+ /* This represents the bits set in to, and not from. */
branches = from ^ to;
for (i = ilog64(branches) - 1; i >= 0; i--) {
if (((branches >> i) & 1)) {
void shachain_from_seed(const struct sha256 *seed, shachain_index_t index,
struct sha256 *hash)
{
- derive((shachain_index_t)-1ULL, index, seed, hash);
+ derive(0, index, seed, hash);
}
void shachain_init(struct shachain *chain)
{
chain->num_valid = 0;
- chain->max_index = 0;
+ chain->min_index = 0;
}
bool shachain_add_hash(struct shachain *chain,
shachain_index_t index, const struct sha256 *hash)
{
- int i;
+ int i, pos;
/* You have to insert them in order! */
- assert(index == chain->max_index + 1 ||
- (index == 0 && chain->num_valid == 0));
-
- for (i = 0; i < chain->num_valid; i++) {
- /* If we could derive this value, we don't need it,
- * not any others (since they're in order). */
- if (can_derive(index, chain->known[i].index)) {
- struct sha256 expect;
-
- /* Make sure the others derive as expected! */
- derive(index, chain->known[i].index, hash, &expect);
- if (memcmp(&expect, &chain->known[i].hash,
- sizeof(expect)) != 0)
- return false;
- break;
- }
+ assert(index == chain->min_index - 1 ||
+ (index == (shachain_index_t)(-1ULL) && chain->num_valid == 0));
+
+ pos = count_trailing_zeroes(index);
+
+ /* All derivable answers must be valid. */
+ /* FIXME: Is it sufficient to check just the next answer? */
+ for (i = 0; i < pos; i++) {
+ struct sha256 expect;
+
+ /* Make sure the others derive as expected! */
+ derive(index, chain->known[i].index, hash, &expect);
+ if (memcmp(&expect, &chain->known[i].hash, sizeof(expect)))
+ return false;
}
- /* This can happen if you skip indices! */
- assert(i < sizeof(chain->known) / sizeof(chain->known[0]));
- chain->known[i].index = index;
- chain->known[i].hash = *hash;
- chain->num_valid = i+1;
- chain->max_index = index;
+ chain->known[pos].index = index;
+ chain->known[pos].hash = *hash;
+ if (pos + 1 > chain->num_valid)
+ chain->num_valid = pos + 1;
+ chain->min_index = index;
return true;
}
/**
* shachain_from_seed - Generate an unpredictable SHA from a seed value.
* @seed: (secret) seed value to use
- * @index: index of value to generate.
+ * @index: index of value to generate (0 == seed)
* @hash: value generated
*
* There will be no way to derive the result from that generated for
- * any *lesser* index.
+ * any *greater* index.
*
* Example:
* #include <time.h>
*
* static void next_hash(struct sha256 *hash)
* {
- * static uint64_t index = 0;
+ * static uint64_t index = 0xFFFFFFFFFFFFFFFFULL;
* static struct sha256 seed;
*
* // First time, initialize seed.
- * if (index == 0) {
+ * if (index == 0xFFFFFFFFFFFFFFFFULL) {
* // DO NOT DO THIS! Very predictable!
* time_t now = time(NULL);
* memcpy(&seed, &now, sizeof(now));
* }
*
- * shachain_from_seed(&seed, index++, hash);
+ * shachain_from_seed(&seed, index--, hash);
* }
*/
void shachain_from_seed(const struct sha256 *seed, shachain_index_t index,
struct sha256 *hash);
/**
- * shachain - structure for recording/deriving incrementing chain members
- * @max_index: maximum index value successfully shachain_add_hash()ed.
- * @num_valid: number of known[] array valid. If non-zero, @max_index valid.
- * @known: known values to allow us to derive those <= @max_index.
+ * shachain - structure for recording/deriving decrementing chain members
+ * @min_index: minimum index value successfully shachain_add_hash()ed.
+ * @num_valid: number of known[] array valid. If non-zero, @min_index valid.
+ * @known: known values to allow us to derive those >= @min_index.
*
* This is sufficient storage to derive any shachain hash value previously
* added.
*/
struct shachain {
- shachain_index_t max_index;
+ shachain_index_t min_index;
unsigned int num_valid;
struct {
shachain_index_t index;
struct sha256 hash;
- } known[sizeof(shachain_index_t) * 8];
+ } known[sizeof(shachain_index_t) * 8 + 1];
};
/**
* @index: the index of the hash
* @hash: the hash value.
*
- * You can only add index 0 (for a freshly initialized chain), or one more
- * than the previously successfully added value.
+ * You can only add index 0xFFFFFFFFFFFFFFFF (for a freshly
+ * initialized chain), or one less than the previously successfully
+ * added value.
*
* This can fail (return false without altering @chain) if the hash
* for this index isn't consistent with previous hashes (ie. wasn't
* Example:
* static void next_hash(const struct sha256 *hash)
* {
- * static uint64_t index = 0;
+ * static uint64_t index = 0xFFFFFFFFFFFFFFFFULL;
* static struct shachain chain;
*
- * if (!shachain_add_hash(&chain, index++, hash))
+ * if (!shachain_add_hash(&chain, index--, hash))
* errx(1, "Corrupted hash value?");
* }
*/
*
* static void next_hash(const struct sha256 *hash)
* {
- * static uint64_t index = 0;
+ * static uint64_t index = 0xFFFFFFFFFFFFFFFFULL;
* static struct shachain chain;
*
- * if (!shachain_add_hash(&chain, index++, hash))
+ * if (!shachain_add_hash(&chain, index--, hash))
* errx(1, "Corrupted hash value?");
* else {
* struct sha256 check;
- * assert(shachain_get_hash(&chain, index-1, &check));
+ * assert(shachain_get_hash(&chain, index+1, &check));
* assert(structeq(&check, hash));
* }
* }
{
struct sha256 seed;
struct shachain chain;
- struct sha256 expect[NUM_TESTS];
- size_t i, j;
+ struct sha256 expect[NUM_TESTS+1];
+ int i, j;
/* This is how many tests you plan to run */
- plan_tests(NUM_TESTS * 3 + NUM_TESTS * (NUM_TESTS + 1));
+ plan_tests(66559);
memset(&seed, 0, sizeof(seed));
- /* Generate a whole heap. */
- for (i = 0; i < NUM_TESTS; i++) {
+ /* Generate a whole heap; each should be different */
+ for (i = 0; i <= NUM_TESTS; i++) {
shachain_from_seed(&seed, i, &expect[i]);
if (i == 0)
- ok1(memcmp(&expect[i], &seed, sizeof(expect[i])));
+ ok1(memcmp(&expect[i], &seed, sizeof(expect[i])) == 0);
else
ok1(memcmp(&expect[i], &expect[i-1], sizeof(expect[i])));
}
shachain_init(&chain);
- for (i = 0; i < NUM_TESTS; i++) {
+ for (i = NUM_TESTS; i > 0; i--) {
struct sha256 hash;
ok1(shachain_add_hash(&chain, i, &expect[i]));
- for (j = 0; j <= i; j++) {
+ for (j = i; j <= NUM_TESTS; j++) {
ok1(shachain_get_hash(&chain, j, &hash));
ok1(memcmp(&hash, &expect[j], sizeof(hash)) == 0);
}
- ok1(!shachain_get_hash(&chain, i+1, &hash));
- if (chain.num_valid == 8) {
- printf("%zu: num_valid %u\n", i, chain.num_valid);
- for (j = 0; j < 8; j++)
- printf("chain.known[%zu] = 0x%02x\n",
- j, chain.known[j].index);
- }
+ ok1(!shachain_get_hash(&chain, i-1, &hash));
+ }
+
+ /* Now add seed. */
+ ok1(shachain_add_hash(&chain, 0, &expect[0]));
+ for (j = 0; j <= NUM_TESTS; j++) {
+ struct sha256 hash;
+ ok1(shachain_get_hash(&chain, j, &hash));
+ ok1(memcmp(&hash, &expect[j], sizeof(hash)) == 0);
}
return exit_status();
{
struct sha256 seed;
struct shachain chain;
- size_t i;
+ uint64_t i;
plan_tests(NUM_TESTS);
memset(&seed, 0xFF, sizeof(seed));
shachain_init(&chain);
- for (i = 0; i < NUM_TESTS; i++) {
+ for (i = 0xFFFFFFFFFFFFFFFFULL;
+ i > 0xFFFFFFFFFFFFFFFFULL - NUM_TESTS;
+ i--) {
struct sha256 expect;
- unsigned int num_known = chain.num_valid;
shachain_from_seed(&seed, i, &expect);
/* Screw it up. */
expect.u.u8[0]++;
- /* Either it should fail, or it couldn't derive any others. */
+ /* Either it should fail, or it couldn't derive any others (ie. pos 0). */
if (shachain_add_hash(&chain, i, &expect)) {
- ok1(chain.num_valid == num_known + 1);
+ ok1(chain.known[0].index == i);
/* Fix it up in-place */
- chain.known[num_known].hash.u.u8[0]--;
+ chain.known[0].hash.u.u8[0]--;
} else {
expect.u.u8[0]--;
ok1(shachain_add_hash(&chain, i, &expect));
--- /dev/null
+#define shachain_index_t uint8_t
+
+#include <ccan/crypto/shachain/shachain.h>
+/* Include the C files directly. */
+#include <ccan/crypto/shachain/shachain.c>
+#include <ccan/tap/tap.h>
+
+#include <stdio.h>
+
+static bool bit_set(shachain_index_t index, int bit)
+{
+ return index & (1ULL << bit);
+}
+
+/* As per design.txt */
+static bool naive_can_derive(shachain_index_t from, shachain_index_t to)
+{
+ int i;
+
+ for (i = count_trailing_zeroes(from); i < 8; i++) {
+ if (bit_set(from, i) != bit_set(to, i))
+ return false;
+ }
+ return true;
+}
+
+int main(void)
+{
+ int i, j;
+
+ /* This is how many tests you plan to run */
+ plan_tests(65536);
+
+ for (i = 0; i < 256; i++) {
+ for (j = 0; j < 256; j++) {
+ ok1(can_derive(i, j) == naive_can_derive(i, j));
+ }
+ }
+
+ return exit_status();
+}
struct sha256 seed;
struct shachain chain;
struct sha256 expect[NUM_TESTS];
- size_t i, j;
+ uint64_t i, j;
/* This is how many tests you plan to run */
- plan_tests(NUM_TESTS * 3 + NUM_TESTS * (NUM_TESTS + 1));
+ plan_tests(NUM_TESTS * 3 + NUM_TESTS * (NUM_TESTS + 1) - 1);
memset(&seed, 0, sizeof(seed));
/* Generate a whole heap. */
- for (i = 0; i < NUM_TESTS; i++) {
- shachain_from_seed(&seed, i, &expect[i]);
- if (i == 0)
- ok1(memcmp(&expect[i], &seed, sizeof(expect[i])));
- else
- ok1(memcmp(&expect[i], &expect[i-1], sizeof(expect[i])));
+ for (i = 0xFFFFFFFFFFFFFFFFULL;
+ i > 0xFFFFFFFFFFFFFFFFULL - NUM_TESTS;
+ i--) {
+ int expidx = 0xFFFFFFFFFFFFFFFFULL - i;
+ shachain_from_seed(&seed, i, &expect[expidx]);
+ if (i != 0xFFFFFFFFFFFFFFFFULL)
+ ok1(memcmp(&expect[expidx], &expect[expidx-1],
+ sizeof(expect[expidx])));
}
shachain_init(&chain);
- for (i = 0; i < NUM_TESTS; i++) {
+ for (i = 0xFFFFFFFFFFFFFFFFULL;
+ i > 0xFFFFFFFFFFFFFFFFULL - NUM_TESTS;
+ i--) {
struct sha256 hash;
-
- ok1(shachain_add_hash(&chain, i, &expect[i]));
- for (j = 0; j <= i; j++) {
+ int expidx = 0xFFFFFFFFFFFFFFFFULL - i;
+ ok1(shachain_add_hash(&chain, i, &expect[expidx]));
+ for (j = i; j != 0; j++) {
ok1(shachain_get_hash(&chain, j, &hash));
- ok1(memcmp(&hash, &expect[j], sizeof(hash)) == 0);
+ expidx = 0xFFFFFFFFFFFFFFFFULL - j;
+ ok1(memcmp(&hash, &expect[expidx], sizeof(hash)) == 0);
}
- ok1(!shachain_get_hash(&chain, i+1, &hash));
+ ok1(!shachain_get_hash(&chain, i-1, &hash));
}
return exit_status();
projects / ccan / commitdiff