From conner at lightning.engineering Sat Feb 3 02:20:01 2018 From: conner at lightning.engineering (Conner Fromknecht) Date: Sat, 03 Feb 2018 02:20:01 +0000 Subject: [Lightning-dev] QuickMaths for Onions: Linear Construction of Sphinx Shared-Secrets Message-ID: 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: