📅 Original date posted:2018-02-03
📝 Original message:
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: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180203/e0a57a15/attachment.html>;
Conner Fromknecht [ARCHIVE] /
npub1za…uua2a
2023-06-09 12:48:47
in reply to nevent1q…hed3
Author Public Key
npub1za0a9afyj7um5feva0d5xmhfsah3zxm252hna2duq0numa952frqvuua2aPublished at
2023-06-09 12:48:47Event JSON
{
"id": "4ca99756cc350991fd6c6312b759fff2791ca2dbaf586c934d472c912dec1cfc",
"pubkey": "175fd2f52497b9ba272cebdb436ee9876f111b6aa2af3ea9bc03e7cdf4b45246",
"created_at": 1686314927,
"kind": 1,
"tags": [
[
"e",
"f2035f92a6b919f36c1def56b3ceb0a166ddea2a82ae2d36c4fa4dde643ab243",
"",
"reply"
],
[
"p",
"9456f7acb763eaab2e02bd8e60cf17df74f352c2ae579dce1f1dd25c95dd611c"
]
],
"content": "📅 Original date posted:2018-02-03\n📝 Original message:\nHello everyone,\n\nWhile working on some upgrades to our lightning-onion repo [1],\nroasbeef pointed\nout that all of our implementations use a quadratic algorithm to\niteratively apply the intermediate blinding factors.\n\nI spent some time working on a linear algorithm that reduces the total\nnumber of scalar multiplications. Overall, our packet construction\nbenchmarks showed an 8x speedup, from 37ms to 4.5ms, and now uses ~70% less\nmemory. The diff is only ~15 LOC, and thought this would be a\nuseful optimization for our implementations to have. I can make a PR that\nupdates the example source in lightning-rfc if there is interest.\n\nA description, along with the modified source, can be found in my PR to\nlightning-onion [2]. The correctness of the output has been verified\nagainst the (updated) BOLT 4 test vector [3].\n\n[1] https://github.com/lightningnetwork/lightning-onion\n[2] https://github.com/lightningnetwork/lightning-onion/pull/18\n[3] https://github.com/lightningnetwork/lightning-rfc/pull/372\n\nCheers,\nConner\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180203/e0a57a15/attachment.html\u003e",
"sig": "43333d31ba0c9eb6dd2e6ac0847e8fc047a93c8c30cb3a8964ef1a8611f1805074145708ca59541d0b12d48fd31cc199f9ed8c3fb7a0fcabadad20db934536f2"
}