git.ozlabs.org Git - ccan/blob - ccan/crypto/shachain/design.txt

   1 Efficient Chains Of Unpredictable Numbers
   2 =========================================
   3
   4 The Problem
   5 -----------
   6
   7 The Lightning Network wants a chain of (say 1 million) unguessable 256
   8 bit values; we generate them and send them one at a time to a remote
   9 node.  We don't want the remote node to have to store all the values,
  10 so it's better if they can derive them once they see them.
  11
  12 A Simple Solution
  13 -----------------
  14
  15 A simple system is a hash chain: we select a random seed value, the
  16 hash it 1,000,000 times.  This gives the first "random" number.
  17 Hashed 999,999 times gives the second number, etc. ie:
  18
  19     R(0) = seed
  20     R(N+1) = SHA256(R(N))
  21
  22 This way the remote node needs only to remember the last R(N) it was
  23 given, and it can calculate any R for N+1 or above.
  24
  25 However, this means we need to generate 1 million hashes up front, and
  26 then do almost as many hashes to derive the next number.  That's slow.
  27
  28 A Tree Solution
  29 ---------------
  30
  31 A better solution is to use a binary tree, with the seed at the root.
  32 The left child is the same as the parent, the right child is the
  33 SHA256() of the parent with one bit flipped (corresponding to the
  34 height).
  35
  36 This gives a tree like so:
  37
  38                       seed
  39                     /      \
  40                   /          \
  41                 /              \
  42               /                  \
  43             seed                   SHA256(seed^1)
  44            /    \                  /             \
  45        seed    SHA256(seed^2)  SHA256(seed^1)  SHA256(SHA256(seed^1)^2)
  46 Index:  0         1                2                  3
  47
  48 Clearly, giving R(2) allows you to derive R(3), giving R(1) allows you
  49 to derive nothing new (you still have to remember R(2)), and giving
  50 R(0) allows you to derive everything.
  51
  52 In pseudocode, this looks like the following for a 64 bit tree:
  53
  54 generate_from_seed(index):
  55     value = seed
  56     for bit in 0 to 63:
  57         if bit set in index:
  58             flip(bit) in value
  59             value = SHA256(value)
  60     return value
  61
  62
  63 The Receiver's Tree
  64 -------------------
  65
  66 To derive the value for a index N, you need to have the root of a tree
  67 which contains it.  That is the same as needing an index I which is N
  68 rounded down in binary: eg. if N is 0b001100001, you need 0b001100000,
  69 0b001000000 or 0b000000000.
  70
  71 Pseudocode:
  72
  73 # Can we derive the value for to_index from from_index?
  74 can_derive(from_index, to_index):
  75     # to_index must be a subtree under from_index; this is the same as
  76     # saying that to_index must be the same as from_index up to the
  77     # trailing zeros in from_index.
  78     for bit in count_trailing_zeroes(from_index)..63:
  79         if bit set in from_index != bit set in to_index:
  80             return false
  81     return true
  82
  83 # Derive a value from a lesser index: generalization of generate_from_seed()
  84 derive(from_index, to_index, from_value):
  85     assert(can_derive(from_index, to_index))
  86     value = from_value
  87     for bit in 0..63:
  88         if bit set in to_index and not bit set in from_index:
  89             flip bit in value
  90             value = SHA256(value)
  91     return value
  92
  93 If you are receiving values (in reverse order), you need to remember
  94 up to 64 of them to derive all previous values.  The simplest method
  95 is to keep an array, indexed by the number of trailing zeroes in the
  96 received index:
  97
  98 # Receive a new value (assumes we receive them in order)
  99 receive_value(index, value):
 100     pos = count_trailing_zeroes(index)
 101     # We should be able to generate every lesser value, otherwise invalid
 102     for i in 0..pos-1:
 103        if derive(index, value, known[i].index) != known[i].value:
 104             return false
 105     known[pos].index = index
 106     known[pos].value = value
 107     return true
 108
 109 To derive a previous value, find an element in that array from which
 110 you can derive the value you want, eg:
 111
 112 # Find an old value
 113 regenerate_value(index):
 114     for i in known:
 115         if can_derive(i.index, index):
 116             return derive(i.index, i.value, index)
 117     fail
 118
 119 You can see the implementation for more optimized variants of the
 120 above code.
 121
 122 Rusty Russell <rusty@rustcorp.com.au>