[Lightning-dev] QuickMaths for Onions: Linear Construction of Sphinx Shared-Secrets

Jim Posen jim.posen at gmail.com
Sun Feb 4 09:02:47 UTC 2018


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: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180204/3fcc68ad/attachment-0001.html>


More information about the Lightning-dev mailing list