From rusty at rustcorp.com.au  Tue Mar  8 05:55:56 2016
From: rusty at rustcorp.com.au (Rusty Russell)
Date: Tue, 08 Mar 2016 16:25:56 +1030
Subject: [Lightning-dev] Laundry list of inter-peer wire protocol changes
In-Reply-To: <20160127142229.GA17540@sapphire.erisian.com.au>
References: <87d1snvhyf.fsf@rustcorp.com.au>
	<20160127142229.GA17540@sapphire.erisian.com.au>
Message-ID: <878u1tms2b.fsf@rustcorp.com.au>

Anthony Towns <aj at erisian.com.au> writes:
> On Wed, Jan 27, 2016 at 01:37:04PM +1030, Rusty Russell wrote:
>> Misc
>> ----
>> - shachain vs elkrem
>>   - We use this to generate the revocation secrets, to minimize storage
>>     and computation for a huge number of old commitment txs.
>>   - They're actually very similar, but elkrem is much easier to grok.[6]
>
> Hmm, I was going to say I like it, but I'm not sure I do...

OK, I revisited shachain; it's nicer to describe in terms of a binary
tree.  The derivation is still a little complex, but people should find
this far less brainbendy.

And yes, I reversed the indices, so we start with 0xFFFFFFFFFFFFFFFF and
work back towards the seed at 0.

>From https://github.com/rustyrussell/ccan/blob/master/ccan/crypto/shachain/design.txt:

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 at rustcorp.com.au>