6 ms·

The firedancer team at one of the better HFT firms wrote an AVX512 optimized implementation of ed25519 and X25519 that’s significantly faster than OpenSSL. htt

by SEJeff 2y ago

The firedancer team at one of the better HFT firms wrote an AVX512 optimized implementation of ed25519 and X25519 that’s significantly faster than OpenSSL. https://github.com/firedancer-io/firedancer/pull/716 https://github.com/firedancer-io/firedancer/pull/716 Ditto for sha256: https://github.com/firedancer-io/firedancer/pull/778 https://github.com/firedancer-io/firedancer/pull/778 And sha512: https://github.com/firedancer-io/firedancer/pull/760 https://github.com/firedancer-io/firedancer/pull/760 If you’re an optimization nerd, this codebase is wild.

electricshampo1 2y ago
Completely agree re: firedancer codebase. There is a level of thought and discipline wrt performance that I have never seen anywhere else.
- SEJeff 2y ago
  That team is full of world experts in high performance computing.
- dhx 2y ago
  It's much more than just performance they've thought about. Here are some of the secure programming practices that have been implemented: /* All the functions in this file are considered "secure", specifically: - Constant time in the input, i.e. the input can be a secret[2] - Small and auditable code base, incl. simple types - Either, no local variables = no need to clear them before exit (most functions) - Or, only static allocation + clear local variable before exit (fd_ed25519_scalar_mul_base_const_time) - Clear registers via FD_FN_SENSITIVE[3] - C safety */ libsodium[4] implements similar mechanisms, and Linux kernel encryption code does too (example: use of kfree_sensitive)[5]. However, firedancer appears to better avoid moving secrets outside of CPU registers, and [3] explains that libraries such as libsodium have inadequate zeroisation, something which firedancer claims to improve upon. [1] https://github.com/firedancer-io/firedancer/blob/main/src/ballet/ed25519/fd_curve25519_secure.c https://github.com/firedancer-io/firedancer/blob/main/src/ba... [2] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Constant_time_Montgomery_ladder https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic... [3] https://eprint.iacr.org/2023/1713 https://eprint.iacr.org/2023/1713 [4] https://libsodium.gitbook.io/doc/internals#security-first https://libsodium.gitbook.io/doc/internals#security-first [5] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
  - tptacek 2y ago
    These are table stakes for core cryptographic code, and SOT crypto code --- like the Amazon implementation this story is about --- tend at this point all to be derived from formal methods.
    - dhx 2y ago
      As an example, the Amazon implementation doesn't refer to gcc's[1] and clang's[2] "zero_call_used_regs" to zeroise CPU registers upon return or exception of functions working on crypto secrets. OpenSSL doesn't either.[3] firedancer _does_ use "zero_call_used_regs" to allow gcc/clang to zeroise used CPU registers.[9] As another example, the Amazon implementation also doesn't refer to gcc's "strub" attribute which zeroises the function's stack upon return or exception of functions working on crypto secrets.[4][5] OpenSSL doesn't either.[3] firedancer _does_ use the "strub" attribute to allow gcc to zeroise the function's stack.[9] Is there a performance impact? [6] has the overhead at 0% for X25519 for implementing CPU register and stack zeroisation. Compiling the Linux kernel with "CONFIG_ZERO_CALL_USED_REGS=1" for x64_64 (impacting all kernel functions) was found to result in a 1-1.5% performance penalty.[7][8] [1] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-zero_005fcall_005fused_005fregs-function-attribute https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute... [2] https://clang.llvm.org/docs/AttributeReference.html#zero-call-used-regs https://clang.llvm.org/docs/AttributeReference.html#zero-cal... [3] https://github.com/openssl/openssl/discussions/24321 https://github.com/openssl/openssl/discussions/24321 [4] https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Type-Attributes.html#index-strub-type-attribute https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Type-At... [5] https://gcc.gnu.org/onlinedocs/gcc/Stack-Scrubbing.html https://gcc.gnu.org/onlinedocs/gcc/Stack-Scrubbing.html [6] https://eprint.iacr.org/2023/1713.pdf https://eprint.iacr.org/2023/1713.pdf [7] https://www.phoronix.com/review/zero-used-regs/5 https://www.phoronix.com/review/zero-used-regs/5 [8] https://lore.kernel.org/lkml/20210505191804.4015873-1-keescook@chromium.org/ https://lore.kernel.org/lkml/20210505191804.4015873-1-keesco... [9] FD_FN_UNSANITIZED: https://github.com/firedancer-io/firedancer/blob/master/src/util/fd_util_base.h https://github.com/firedancer-io/firedancer/blob/master/src/...
      - 2y ago
syzygyhack 2y ago
I laughed a little at calling Firedancer contributors "a team at a HFT firm". Not that you are technically wrong, not at all, that's where Jump came from. It's just that this is all completely blockchain-driven optimization, but the b-word is so dirty now that we've gotta go back to using TradFi for the rep.
- SEJeff 2y ago
  It’s an optimization in hashing algorithms that is around twice as fast as the ones Amazon is posting in thus article for the same eliptic curves. If the Amazon improvements are hacker news worthy (they are) this seems reasonable contextually. Also, I worked for Jump for almost 12 years :)
- webXL 2y ago
  What makes the “b-word” dirty?
  - ShroudedNight 2y ago
    The trough of disillusionment carved out by grifters burning the peat of enthusiasm unsustainably.
  - SEJeff 2y ago
    I didn’t use it because I didn’t find it relevant. They’re using hashing and EC algorithms and they’re improving them.
  - jandrese 2y ago
    It's hard to separate from the sea of grifters, con men, cranks, and scammers that infest the domain. Just using the word is a yellow flag that you might be some kind of whacko, even if all you really want to talk about is the math. People have to forever be on guard that you might at any point pivot to all taxation is theft or how you have formed your own micro nation that consists entirely of yourself and thus have diplomatic immunity from all prosecution. Because it happens. Or maybe you have a once in a lifetime deal to buy this receipt like object for some hideous art that is guaranteed to appreciate in value millions of percent. It's just the crowd that has aggregated around crypto currencies includes a lot of untrustworthy people.
4gotunameagain 2y ago
So many manhours spent on finding better ways to shovel around money and pocket what falls from the cracks. What a wasteful and unproductive enterprise, considering the vast majority of the devised improvements never see the public eye. Still, impressive work. Imagine if those brilliant minds behind this were focused somewhere else.
- posnet 2y ago
  The greatest minds of our generation spend their time thinking about how to: - make people click on ads - make trading algos faster - replace human artists - build more efficient killing machines - destroy any remaining concept of privacy
  - 4gotunameagain 2y ago
    Hey, at least we had one of them working on TempleOS.
  - vladms 2y ago
    This directly implies that all the people that did useful stuff (improving cancer survivability, new vaccines, renewable energy, and others) are all "below" the "greatest minds of our generation". Not to mention it also suggests there is a way to "compare" minds. I would not choose myself to do somethings, but that does not mean I despise automatically people choosing to.
    - geodel 2y ago
      I think they meant greatest minds have to be greatest money earners also. Else they are not greatest minds.
  - astrange 2y ago
    Aren't the greatest mind(s) of our generation writing Terry Tao's blog posts?
  - geodel 2y ago
    Greatest mind of previous generation made nuclear bombs and other deadly things.
pantalaimon 2y ago
That looks really neat, but I still don't understand what firedancer actually is - what is a validator client for Solana and why does it need it's own crypto library?
- SEJeff 2y ago
  It’s a new from scratch implementation of a validator for Solana the fastest blockchain by several orders of magnitude. The slowest part is signature verification so they sped up hashing to improve performance of the entire system. They follow a first principles approach (the lead has a few physics degrees) and opted to speed up the cryptography. The beauty of this, despite the bad views on blockchain, is that they freaking sped up the cryptography of commonly used algorithms more than anything open or closed source that I personally am aware of. It’s a win in cryptography, much like this Amazon post is, except it’s slower than the firedancer implementation.
  - scrlk 2y ago
    Off topic - is Firedancer going to survive Jump winding down its crypto arm? Kanav left, they liquidated a huge staked ETH position a few months ago (+ a bunch of other coins), and the SEC/CFTC is all over them for the Terra Luna fiasco.
    - SEJeff 2y ago
      Rumors of Jump’s demise are greatly exaggerated. Check the torrent of firedancer talks at Solana Breakpoint literally next week and decide yourself. Folks have said jump is gonna die for 20+ years. They’ve been around 30ish…
      - sangnoir 2y ago
        Parent asked a specific question about the survival of Firedancer and winding down of the crypto arm though. No demise of Jump mentioned.
        2y ago
nly 2y ago
A lot of slowness comes typically comes from wanting to avoid methods that enable side-channel timing attacks
inopinatus 2y ago
I see they learned clang’s dirty little secret over intrinsics viz. that in producing the IR it deviates (sometimes dramatically when AVX-512 is concerned) from the documented opcodes and the results are inevitably detrimental.
- astrange 2y ago
  This is why ffmpeg uses assembly, and people get extremely mad when you say it's done for a reason, because they always want to come up with a fancier abstraction (usually cross-platform) which then defeats the purpose because it doesn't actually work. nb those abstractions do make sense when you can only afford to write a single implementation of the algorithm; then you're just talking about a high level programming language. But they frequently fail to achieve their goal when you're writing a second implementation for the sole purpose of being faster.
slt2021 2y ago
wow amazing, nobody is gonna edit that code ever again...

by SEJeff 2y ago

electricshampo1 2y ago

Completely agree re: firedancer codebase. There is a level of thought and discipline wrt performance that I have never seen anywhere else.

SEJeff 2y ago
That team is full of world experts in high performance computing.
dhx 2y ago
It's much more than just performance they've thought about. Here are some of the secure programming practices that have been implemented: /* All the functions in this file are considered "secure", specifically: - Constant time in the input, i.e. the input can be a secret[2] - Small and auditable code base, incl. simple types - Either, no local variables = no need to clear them before exit (most functions) - Or, only static allocation + clear local variable before exit (fd_ed25519_scalar_mul_base_const_time) - Clear registers via FD_FN_SENSITIVE[3] - C safety */ libsodium[4] implements similar mechanisms, and Linux kernel encryption code does too (example: use of kfree_sensitive)[5]. However, firedancer appears to better avoid moving secrets outside of CPU registers, and [3] explains that libraries such as libsodium have inadequate zeroisation, something which firedancer claims to improve upon. [1] https://github.com/firedancer-io/firedancer/blob/main/src/ballet/ed25519/fd_curve25519_secure.c https://github.com/firedancer-io/firedancer/blob/main/src/ba... [2] https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Constant_time_Montgomery_ladder https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic... [3] https://eprint.iacr.org/2023/1713 https://eprint.iacr.org/2023/1713 [4] https://libsodium.gitbook.io/doc/internals#security-first https://libsodium.gitbook.io/doc/internals#security-first [5] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
- tptacek 2y ago
  These are table stakes for core cryptographic code, and SOT crypto code --- like the Amazon implementation this story is about --- tend at this point all to be derived from formal methods.
  - dhx 2y ago
    As an example, the Amazon implementation doesn't refer to gcc's[1] and clang's[2] "zero_call_used_regs" to zeroise CPU registers upon return or exception of functions working on crypto secrets. OpenSSL doesn't either.[3] firedancer _does_ use "zero_call_used_regs" to allow gcc/clang to zeroise used CPU registers.[9] As another example, the Amazon implementation also doesn't refer to gcc's "strub" attribute which zeroises the function's stack upon return or exception of functions working on crypto secrets.[4][5] OpenSSL doesn't either.[3] firedancer _does_ use the "strub" attribute to allow gcc to zeroise the function's stack.[9] Is there a performance impact? [6] has the overhead at 0% for X25519 for implementing CPU register and stack zeroisation. Compiling the Linux kernel with "CONFIG_ZERO_CALL_USED_REGS=1" for x64_64 (impacting all kernel functions) was found to result in a 1-1.5% performance penalty.[7][8] [1] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-zero_005fcall_005fused_005fregs-function-attribute https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute... [2] https://clang.llvm.org/docs/AttributeReference.html#zero-call-used-regs https://clang.llvm.org/docs/AttributeReference.html#zero-cal... [3] https://github.com/openssl/openssl/discussions/24321 https://github.com/openssl/openssl/discussions/24321 [4] https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Type-Attributes.html#index-strub-type-attribute https://gcc.gnu.org/onlinedocs/gcc-14.2.0/gcc/Common-Type-At... [5] https://gcc.gnu.org/onlinedocs/gcc/Stack-Scrubbing.html https://gcc.gnu.org/onlinedocs/gcc/Stack-Scrubbing.html [6] https://eprint.iacr.org/2023/1713.pdf https://eprint.iacr.org/2023/1713.pdf [7] https://www.phoronix.com/review/zero-used-regs/5 https://www.phoronix.com/review/zero-used-regs/5 [8] https://lore.kernel.org/lkml/20210505191804.4015873-1-keescook@chromium.org/ https://lore.kernel.org/lkml/20210505191804.4015873-1-keesco... [9] FD_FN_UNSANITIZED: https://github.com/firedancer-io/firedancer/blob/master/src/util/fd_util_base.h https://github.com/firedancer-io/firedancer/blob/master/src/...
    - 2y ago

syzygyhack 2y ago

I laughed a little at calling Firedancer contributors "a team at a HFT firm". Not that you are technically wrong, not at all, that's where Jump came from. It's just that this is all completely blockchain-driven optimization, but the b-word is so dirty now that we've gotta go back to using TradFi for the rep.

SEJeff 2y ago
It’s an optimization in hashing algorithms that is around twice as fast as the ones Amazon is posting in thus article for the same eliptic curves. If the Amazon improvements are hacker news worthy (they are) this seems reasonable contextually. Also, I worked for Jump for almost 12 years :)
webXL 2y ago
What makes the “b-word” dirty?
- ShroudedNight 2y ago
  The trough of disillusionment carved out by grifters burning the peat of enthusiasm unsustainably.
- SEJeff 2y ago
  I didn’t use it because I didn’t find it relevant. They’re using hashing and EC algorithms and they’re improving them.
- jandrese 2y ago
  It's hard to separate from the sea of grifters, con men, cranks, and scammers that infest the domain. Just using the word is a yellow flag that you might be some kind of whacko, even if all you really want to talk about is the math. People have to forever be on guard that you might at any point pivot to all taxation is theft or how you have formed your own micro nation that consists entirely of yourself and thus have diplomatic immunity from all prosecution. Because it happens. Or maybe you have a once in a lifetime deal to buy this receipt like object for some hideous art that is guaranteed to appreciate in value millions of percent. It's just the crowd that has aggregated around crypto currencies includes a lot of untrustworthy people.

4gotunameagain 2y ago

So many manhours spent on finding better ways to shovel around money and pocket what falls from the cracks. What a wasteful and unproductive enterprise, considering the vast majority of the devised improvements never see the public eye. Still, impressive work. Imagine if those brilliant minds behind this were focused somewhere else.

posnet 2y ago
The greatest minds of our generation spend their time thinking about how to: - make people click on ads - make trading algos faster - replace human artists - build more efficient killing machines - destroy any remaining concept of privacy
- 4gotunameagain 2y ago
  Hey, at least we had one of them working on TempleOS.
- vladms 2y ago
  This directly implies that all the people that did useful stuff (improving cancer survivability, new vaccines, renewable energy, and others) are all "below" the "greatest minds of our generation". Not to mention it also suggests there is a way to "compare" minds. I would not choose myself to do somethings, but that does not mean I despise automatically people choosing to.
  - geodel 2y ago
    I think they meant greatest minds have to be greatest money earners also. Else they are not greatest minds.
- astrange 2y ago
  Aren't the greatest mind(s) of our generation writing Terry Tao's blog posts?
- geodel 2y ago
  Greatest mind of previous generation made nuclear bombs and other deadly things.

pantalaimon 2y ago

That looks really neat, but I still don't understand what firedancer actually is - what is a validator client for Solana and why does it need it's own crypto library?

SEJeff 2y ago
It’s a new from scratch implementation of a validator for Solana the fastest blockchain by several orders of magnitude. The slowest part is signature verification so they sped up hashing to improve performance of the entire system. They follow a first principles approach (the lead has a few physics degrees) and opted to speed up the cryptography. The beauty of this, despite the bad views on blockchain, is that they freaking sped up the cryptography of commonly used algorithms more than anything open or closed source that I personally am aware of. It’s a win in cryptography, much like this Amazon post is, except it’s slower than the firedancer implementation.
- scrlk 2y ago
  Off topic - is Firedancer going to survive Jump winding down its crypto arm? Kanav left, they liquidated a huge staked ETH position a few months ago (+ a bunch of other coins), and the SEC/CFTC is all over them for the Terra Luna fiasco.
  - SEJeff 2y ago
    Rumors of Jump’s demise are greatly exaggerated. Check the torrent of firedancer talks at Solana Breakpoint literally next week and decide yourself. Folks have said jump is gonna die for 20+ years. They’ve been around 30ish…
    - sangnoir 2y ago
      Parent asked a specific question about the survival of Firedancer and winding down of the crypto arm though. No demise of Jump mentioned.
      - 2y ago

nly 2y ago

A lot of slowness comes typically comes from wanting to avoid methods that enable side-channel timing attacks

inopinatus 2y ago

I see they learned clang’s dirty little secret over intrinsics viz. that in producing the IR it deviates (sometimes dramatically when AVX-512 is concerned) from the documented opcodes and the results are inevitably detrimental.

astrange 2y ago
This is why ffmpeg uses assembly, and people get extremely mad when you say it's done for a reason, because they always want to come up with a fancier abstraction (usually cross-platform) which then defeats the purpose because it doesn't actually work. nb those abstractions do make sense when you can only afford to write a single implementation of the algorithm; then you're just talking about a high level programming language. But they frequently fail to achieve their goal when you're writing a second implementation for the sole purpose of being faster.

slt2021 2y ago

wow amazing, nobody is gonna edit that code ever again...