From fc6655ed3c4840a5d4d669ad3c44e2ffe1019173 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 25 May 2015 13:49:41 +0930 Subject: [PATCH] crypto/shachain: new module Signed-off-by: Rusty Russell --- ccan/crypto/shachain/LICENSE | 1 + ccan/crypto/shachain/_info | 29 ++++++++++ ccan/crypto/shachain/shachain.c | 87 ++++++++++++++++++++++++++++ ccan/crypto/shachain/shachain.h | 32 ++++++++++ ccan/crypto/shachain/test/run-8bit.c | 52 +++++++++++++++++ ccan/crypto/shachain/test/run.c | 42 ++++++++++++++ 6 files changed, 243 insertions(+) create mode 120000 ccan/crypto/shachain/LICENSE create mode 100644 ccan/crypto/shachain/_info create mode 100644 ccan/crypto/shachain/shachain.c create mode 100644 ccan/crypto/shachain/shachain.h create mode 100644 ccan/crypto/shachain/test/run-8bit.c create mode 100644 ccan/crypto/shachain/test/run.c diff --git a/ccan/crypto/shachain/LICENSE b/ccan/crypto/shachain/LICENSE new file mode 120000 index 00000000..2b1feca5 --- /dev/null +++ b/ccan/crypto/shachain/LICENSE @@ -0,0 +1 @@ +../../../licenses/BSD-MIT \ No newline at end of file diff --git a/ccan/crypto/shachain/_info b/ccan/crypto/shachain/_info new file mode 100644 index 00000000..7cbf02da --- /dev/null +++ b/ccan/crypto/shachain/_info @@ -0,0 +1,29 @@ +#include "config.h" +#include +#include + +/** + * crypto/shachain - compactly-representable chain of 256-bit numbers. + * + * This code produces a practically infinite (2^64) chain of 256-bit numbers + * from a single number, such that you can't derive element N from any element + * less than N, but can efficiently derive element N from a limited number + * of elements >= N. + * + * License: BSD-MIT + * Author: Rusty Russell + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/ilog\n"); + printf("ccan/crypto/sha256\n"); + return 0; + } + + return 1; +} diff --git a/ccan/crypto/shachain/shachain.c b/ccan/crypto/shachain/shachain.c new file mode 100644 index 00000000..4b6a31db --- /dev/null +++ b/ccan/crypto/shachain/shachain.c @@ -0,0 +1,87 @@ +/* MIT (BSD) license - see LICENSE file for details */ +#include +#include +#include +#include +#include + +static void change_bit(unsigned char *arr, size_t index) +{ + arr[index / CHAR_BIT] ^= (1 << (index % CHAR_BIT)); +} + +static void derive(shachain_index_t index, size_t bits, struct sha256 *hash) +{ + int i; + + for (i = bits - 1; i >= 0; i--) { + if (!((index >> i) & 1)) { + change_bit(hash->u.u8, i); + sha256(hash, hash, 1); + } + } +} + +void shachain_from_seed(const struct sha256 *seed, shachain_index_t index, + struct sha256 *hash) +{ + *hash = *seed; + derive(index, sizeof(index) * CHAR_BIT, hash); +} + +void shachain_init(struct shachain *shachain) +{ + shachain->num_valid = 0; +} + +/* We can only ever *unset* bits, so to must only have bits in from. */ +static bool can_derive(shachain_index_t from, shachain_index_t to) +{ + return (~from & to) == 0; +} + +void shachain_add_hash(struct shachain *chain, + shachain_index_t index, const struct sha256 *hash) +{ + int i; + + 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)) + break; + } + + /* 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; +} + +bool shachain_get_hash(const struct shachain *chain, + shachain_index_t index, struct sha256 *hash) +{ + int i; + + for (i = 0; i < chain->num_valid; i++) { + shachain_index_t diff; + + /* If we can get from key to index only by resetting bits, + * we can derive from it => index has no bits key doesn't. */ + if (!can_derive(chain->known[i].index, index)) + continue; + + /* Start from this hash. */ + *hash = chain->known[i].hash; + + /* This indicates the bits which are in 'index' and + * not the key */ + diff = index ^ chain->known[i].index; + + /* Using ilog64 here is an optimization. */ + derive(~diff, ilog64(diff), hash); + return true; + } + return false; +} diff --git a/ccan/crypto/shachain/shachain.h b/ccan/crypto/shachain/shachain.h new file mode 100644 index 00000000..b0f947e9 --- /dev/null +++ b/ccan/crypto/shachain/shachain.h @@ -0,0 +1,32 @@ +/* MIT (BSD) license - see LICENSE file for details */ +#ifndef CCAN_CRYPTO_SHACHAIN_H +#define CCAN_CRYPTO_SHACHAIN_H +#include "config.h" +#include +#include +#include + +/* Useful for testing. */ +#ifndef shachain_index_t +#define shachain_index_t uint64_t +#endif + +void shachain_from_seed(const struct sha256 *seed, shachain_index_t index, + struct sha256 *hash); + +struct shachain { + unsigned int num_valid; + struct { + shachain_index_t index; + struct sha256 hash; + } known[sizeof(shachain_index_t) * 8]; +}; + +void shachain_init(struct shachain *shachain); + +void shachain_add_hash(struct shachain *shachain, + shachain_index_t index, const struct sha256 *hash); + +bool shachain_get_hash(const struct shachain *shachain, + shachain_index_t index, struct sha256 *hash); +#endif /* CCAN_CRYPTO_SHACHAIN_H */ diff --git a/ccan/crypto/shachain/test/run-8bit.c b/ccan/crypto/shachain/test/run-8bit.c new file mode 100644 index 00000000..10520bc3 --- /dev/null +++ b/ccan/crypto/shachain/test/run-8bit.c @@ -0,0 +1,52 @@ +#define shachain_index_t uint8_t + +#include +/* Include the C files directly. */ +#include +#include + +#include + +#define NUM_TESTS 255 + +int main(void) +{ + struct sha256 seed; + struct shachain chain; + struct sha256 expect[NUM_TESTS]; + size_t i, j; + + /* This is how many tests you plan to run */ + plan_tests(NUM_TESTS + NUM_TESTS * (NUM_TESTS + 1) + NUM_TESTS); + + 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]))); + } + + shachain_init(&chain); + + for (i = 0; i < NUM_TESTS; i++) { + struct sha256 hash; + + shachain_add_hash(&chain, i, &expect[i]); + for (j = 0; j <= i; 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); + } + } + + return exit_status(); +} diff --git a/ccan/crypto/shachain/test/run.c b/ccan/crypto/shachain/test/run.c new file mode 100644 index 00000000..39391685 --- /dev/null +++ b/ccan/crypto/shachain/test/run.c @@ -0,0 +1,42 @@ +#include +/* Include the C files directly. */ +#include +#include + +#define NUM_TESTS 50 + +int main(void) +{ + struct sha256 seed; + struct shachain chain; + struct sha256 expect[NUM_TESTS]; + size_t i, j; + + /* This is how many tests you plan to run */ + plan_tests(NUM_TESTS + NUM_TESTS * (NUM_TESTS + 1) + NUM_TESTS); + + 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]))); + } + + shachain_init(&chain); + + for (i = 0; i < NUM_TESTS; i++) { + struct sha256 hash; + + shachain_add_hash(&chain, i, &expect[i]); + for (j = 0; j <= i; j++) { + ok1(shachain_get_hash(&chain, j, &hash)); + ok1(memcmp(&hash, &expect[j], sizeof(hash)) == 0); + } + ok1(!shachain_get_hash(&chain, i+1, &hash)); + } + + return exit_status(); +} -- 2.39.2