From aj at erisian.com.au  Wed Jan 27 14:22:29 2016
From: aj at erisian.com.au (Anthony Towns)
Date: Thu, 28 Jan 2016 00:22:29 +1000
Subject: [Lightning-dev] Laundry list of inter-peer wire protocol changes
In-Reply-To: <87d1snvhyf.fsf@rustcorp.com.au>
References: <87d1snvhyf.fsf@rustcorp.com.au>
Message-ID: <20160127142229.GA17540@sapphire.erisian.com.au>

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...

The comments in the code don't quite make sense to me, for instance,
the given examples:

 0b0000: L(L(L(L(seed))))
 0b0001: R(L(L(L(seed))))
 0b1000:   L(L(L(seed)))

should be 0, 1 and 2, I think, not 0, 1 and 8; and with four hash
operations, you've got 31 nodes not 15, and 16 leaves, not 8?

I think the pattern is:

 0b0000:  LLL (ie L(L(L(seed)))
 0b0001:  RLL (ie R(L(L(seed)))
 0b0010:  LL -> (0, 1)
 0b0011:  LRL
 0b0100:  RRL
 0b0101:  RL -> (3, 4)
 0b0110:  L -> (0, 1, 2, 3, 4, 5)
 0b0111:  LLR
 0b1000:  RLR
 0b1001:  LR -> (7, 8)
 0b1010:  LRR
 0b1011:  RRR
 0b1100:  RR -> (10, 11)
 0b1101:  R -> (7, 8, 9, 10, 11, 12)
 0b1110:  seed -> (0,..,13)

(Running the code translated into python gives those results too)

I don't the code is quite right either (though I may have translated
something wrong); eg if I try calling:

  descend(6, 13, 2, R(seed))

I get

  L(L(R(seed)))

instead of an error (since the right answer would be L(seed), which
can't be derived from R(seed)).

Personally, I think both this and shachain have the indexing backwards;
I think i=0 should match the seed, and the first hash transmitted across
the wire should be i=2^64-1, then counting down from there. This matches
the numbering used in https://en.wikipedia.org/wiki/Hash_chain fwiw.

With shachain, that gives the nice property that the only parameter
you need is the seed, you can work out the hash for any given index
directly from that, up to any arbitrary index, until you run out of
integer precision, or bits of security in your hash function.

With elkrem you can build an arbitrarily deep tree given a seed at the
conceptual level without any further parameters, but when you start
mapping that to indexes you need to know the desired height first.
This is, in essence, because L(seed) (eg) gets sent at different places
depending on the "height"; with a height of 1 it's the first value (or
third from last), with a height of 2 it's the third value (or fifth
from last), with a height of 3 it's the seventh value (or ninth from
last), etc.

Probably doesn't really matter, but I think it leads me to prefer Rusty's
construction. Might be good to have an explanation with it diagrammed
as an n-way tree structure though, in a similar way to how you visualise
the elkrem tree...

> - R value vs keypair
>   - Using a simple secret "redeemhash" allows easy tracing of
>     transactions through the network.
>   - Mats Jeratsch proposed a keypair scheme which decorrelates them[3],
>     Greg Maxwell optimized it slightly, and Anthony Towns[4] and Andrew
>     Poelstra independently came up with a way to do it without any
>     bitcoin mods.

FWIW I think this should still be considered an R&D idea rather than
trying to release it in v1.0.

> - Multi-sig txs
>   - Joseph pointed out that by simply allowing more than one signature on
>     commit txs[5], we can enable escrow-style services (including things
>     like GreenAddress.it which does this for normal wallets).

It's "more than one hash" not more than one /signature/, isn't it? (The
proposal was also to support 2-of-3 hashes, slightly more complicated
than just multiple hashes)

Cheers,
aj