From jim.posen at gmail.com Sun Feb 4 09:02:47 2018 From: jim.posen at gmail.com (Jim Posen) Date: Sun, 4 Feb 2018 01:02:47 -0800 Subject: [Lightning-dev] QuickMaths for Onions: Linear Construction of Sphinx Shared-Secrets In-Reply-To: References: Message-ID: Nice work! I reread the relevant section in BOLT 4 and it is written in a way to suggest the quadratic time algorithm. I have opened a PR to update the recommendation and reference code: https://github.com/lightningnetwork/lightning-rfc/pull/374. On Fri, Feb 2, 2018 at 6:20 PM, Conner Fromknecht < conner at lightning.engineering> wrote: > Hello everyone, > > While working on some upgrades to our lightning-onion repo [1], roasbeef pointed > out that all of our implementations use a quadratic algorithm to > iteratively apply the intermediate blinding factors. > > I spent some time working on a linear algorithm that reduces the total > number of scalar multiplications. Overall, our packet construction > benchmarks showed an 8x speedup, from 37ms to 4.5ms, and now uses ~70% less > memory. The diff is only ~15 LOC, and thought this would be a > useful optimization for our implementations to have. I can make a PR that > updates the example source in lightning-rfc if there is interest. > > A description, along with the modified source, can be found in my PR to > lightning-onion [2]. The correctness of the output has been verified > against the (updated) BOLT 4 test vector [3]. > > [1] https://github.com/lightningnetwork/lightning-onion > [2] https://github.com/lightningnetwork/lightning-onion/pull/18 > [3] https://github.com/lightningnetwork/lightning-rfc/pull/372 > > Cheers, > Conner > > _______________________________________________ > Lightning-dev mailing list > Lightning-dev at lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > > -------------- next part -------------- An HTML attachment was scrubbed... URL: