8 ms·

Homomorphically Encrypting CRDTs

277 points by jakelazaroff 1y ago

scyclow 1y ago
Encrypt the diffs for the server and write the hash to a blockchain to manage the ordering. Boom, problem solved without HME.
- ergl 1y ago
  You don't need ordering guarantees for diffs: apply them out of order and the final result should be the same (that's one of the key properties of CRDTs).
  - scyclow 1y ago
    So why do you need timestamps? Or, why do you even need a third party server to run HME to begin with? Why not just encrypt the data and let the client figure it out?
chrisweekly 1y ago
For the uninitiated: "In the context of encryption, 'homomorphic' describes methods that enable computations on encrypted data without needing to decrypt it first.
qualeed 1y ago
It doesn't actually say it anywhere, so: CRDT = Conflict-free replicated data type. https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
- Xeoncross 1y ago
  e.g. commonly used by applications that need to deal with multiple people editing a document.
  - MangoToupe 1y ago
    ...or, really, any kind of conflict-free syncing.
Joker_vD 1y ago
> Now, however, the server can no longer understand the changes you send. If you want to see your friend’s latest changes, you’ll need to both be online at the same time. What? No, the server sends you the changes you've not seen yet, you decrypt and merge them, and so you get the latest version of the document. Right? The homomorphic encryption is a fascinating topic, but it's almost never an answer if you need anything resembling reasonable performance and/or reasonable bandwidth. I've seen a paper that ingeniuously uses homomorphic encryption to implement arbitrary algorithmic computations, totally secret, by encoding a (custom-crafted) CPU together with RAM and then running "tick a clock" algorithm on them. And it works, so you can borrow some AWS huge instance and run you super-important calculations there — at 1 Hz. I am not kidding, it's literally 1 virtual CPU instruction per second. Well, if you are okay with such speed and costs, you either have very small data — at which point just run your computation locally, or you're really, really rich — at which point just buy your own goddamn hardware and, again, run it locally.
- zawaideh 1y ago
  If the server can't operate on the content, it can't merge it into the CRDT documents. Which means it would need to sending and receiving the entire state of the CRDT with each change. If the friend is online then sending operations is possible, because they can be decrypted and merged.
  - Joker_vD 1y ago
    I... still can't make heads or tails out of this description. Let me restate how I understand the scheme in TFA: there are two people, editing on the same document using CRDTs. When one person makes an edit, they push an encrypted CRDT to the sync server. Periodically, each of them pulls edits made by the other from the sync server, apply them to their own copy, and push the (encrypted) result back. Because of CRDT's properties, they both end up with the same document. This scheme doesn't require them two people to be on-line simultaneously — all updates are mediated via the sync server, after all. So, where am I wrong?
    - 1y ago
teleforce 1y ago
>Runtime performance is also — to put it lightly — lacking. I benchmarked the unencrypted and encrypted versions of the last write wins register on an M4 MacBook Pro. The unencrypted one averaged a merge time of 0.52 nanoseconds.The encrypted one? 1.06 seconds. That’s not a typo: the homomorphically encrypted merge is two billion times slower. Ouch!
- sieabahlpark 1y ago
  [dead]
thrance 1y ago
Another cool use of FHE, allowing to browse wikipedia privately while still online: https://news.ycombinator.com/item?id=31668814 https://news.ycombinator.com/item?id=31668814
plopilop 1y ago
As the article mentions, fully homomorphic encryption is insanely slow and inefficient. But I have to say that it is a relatively new field (the first FHE scheme was discovered in 2009), and that the field has immensely progressed over the last decade and a half. The first FHE scheme required keys of several TB/PB, bootstrapping (an operation that is pivotal in FHE schemes, when too many multiplications are computed) would take thousands of hours. We are now down to keys of "only" 30 MB, and bootstrapping in less than 0.1 second. Hopefully progress will continue and FHE will become more practical.
- 6r17 1y ago
  CRDTs are also crazy slow due to their architecture ; even the best alg out there are costly by design ; so adding homomorphic encryption is even more of a challenge ; tough it really is impressing I'm curious if this can be usable at all; edit so i bring some "proof" of my claim: from this very page : `To calculate the new map, the server must go through and merge every single key. After that, it needs to transfer the full map to each peer — because remember, as far as it knows, the entire map is different.`
  - __MatrixMan__ 1y ago
    Is it the CRDT that's slow there, or is the problem that they've made it one party's job to update everybody? By having a server in the mix it feels like we're forcing a hub/spoke model on something that wants to be a partial mesh. Not surprising that the hub is stressed out.
    - svieira 1y ago
      The whole point of Conflict-free Replicated Data Types is that you don't need an authoritative server. You're thinking of Operational Transform which does require an authority.
      - __MatrixMan__ 1y ago
        I may have worded that poorly but my intent was to suggest that it would work better if there wasn't a server. I didn't know the name for the serverful alternative though, so thanks for that.
867-5309 1y ago
Conflict-Free Replicated Data Type
deleted 1y ago
[deleted]
NetRunnerSu 1y ago
FHE is indeed slow, but the progress since 2009 is truly remarkable. Bootstrapping speed alone improved by tens of millions of times, and tfhe-rs already demonstrates homomorphic AES-128. Real-time FHE for AI inference/training feels increasingly plausible. > https://github.com/sharkbot1/tfhe-aes-128 https://github.com/sharkbot1/tfhe-aes-128
- ProofHouse 1y ago
  Can I double click on ‘plausible’ ?
  - ketralnis 1y ago
    Sure but it will just select the word in your browser
  - throitallaway 1y ago
    Someone's a Chamath fan.
mihau 1y ago
Sorry for going off-topic, but kudos for UI/UX on your blog! To name a few: Nice style (colors, font, style), "footnotes" visible on the margin, always on table of contents, interactivity and link previews on hover. Nice. What's your tech stack?
- jakelazaroff 1y ago
  No worries and thank you! The tech stack is really just Astro with content stored in Markdown files. The link previews on hover are powered by Tippy.js [1] (maybe deprecated by now?). I wrote a script to collect all the links from my Markdown files, scrape the open graph tags and commit the data to the repo as JSON files. The interactive demos are web components! I wrote a bit about how I built them [2] but maybe should do a more in-depth blog post at some point. [1] https://atomiks.github.io/tippyjs/ https://atomiks.github.io/tippyjs/ [2] https://jakelazaroff.com/words/web-components-will-outlive-your-javascript-framework/ https://jakelazaroff.com/words/web-components-will-outlive-y...
somezero 1y ago
FHE is simply the wrong tool here. FHE is for a central server operating on data held/known by another. They want MPC -multiple parties jointly computing on distributed data- and that’s fairly more efficient.
- hoppp 1y ago
  I agree. I also often want to use FHE only to realize there are better tools for the job and better ways to do things. The use-case is pretty niche
meindnoch 1y ago
I like it! The slowness and inefficiency of homomorphic encryption is nicely complemented by the storage bloat of CRDTs.
yusina 1y ago
I'm not sure I get the premise of the article. I know what a CRDT is and how homomorphic encryption works. But why do both parties have to be online at the same time to sync? They could send the updates asynchronously, store-and-forward style, and everything in flight is encrypted. Why does this need server that keeps state (which is kept in encrypted state and modified, as per the proposal)?
- noam_k 1y ago
  I think the issue here is that the server would have to store a copy of the register per peer, as it can't calculate which one is the most recent. Using FHE allows the server to hold a single copy. In other words the server could forward and not store if all parties are always online (at the same time).
  - yusina 1y ago
    So it's "just" a storage optimization?
  - neon_me 1y ago
    Server will store encrypted blob and its hash/etag. Client before upload of data, check for hash/etag of blob he originally fetched. If blob on server has different one, it will download it, decrypt, patch new data on existing one, encrypt and reupload. Whats the catch? AES is hardware accelerated on the most devices - so with all the ops it will be significantly faster than any homomorphic enc nowadays.
    - nixpulvis 1y ago
      I too was wondering the same thing. FHE is cool tech, but this seems to me to be a bad application of it since it will undoubtedly be less efficient. FHE is useful when trying to compute on data from various sources who all mutually want to keep some information secret. For example, Apple's use of FHE to categorize photos [1]. In this case all the server is really doing is "compressing" for lack of a better word, the change sets, so each offline client doesn't need to sync every message since they are already merged by the server. If all you want is to keep a synchronizing server in the dark, but all clients can be trusted with the unencrypted data, traditional key exchange and symmetric encryption should suffice. [1]: https://machinelearning.apple.com/research/homomorphic-encryption https://machinelearning.apple.com/research/homomorphic-encry...
drob518 1y ago
Love the presentation.
hoppp 1y ago
Don't use THFE-rs because Zama requires a commercial license for anything other than prototyping. Their license sucks. Instead use openFHE (C++) or lattigo (golang) libraries which are both free to use commercially.
jdefr89 1y ago
“We introduced a new abstraction for no reason! Take a look!!”
xvector 1y ago
> keep_self.select(&self.peer, &other.peer); > Rather than if or match expressions, we use FheBool’s select method. It returns the first argument if the underlying FheBool value is true, or the second argument if the underlying value is false. This wasn't super clear to me. I get the computation is performed on encrypted values, but how does ".select" actually work? Is ".select" just evaluating to "keep_self*self.peer + keep_self*other.peer"?
GRBurst 1y ago
Following the topic of FHE for quite some time and I am always hoping that we get some breakthroughs regarding speed. Seeing how this can be applied to CRDTs another awesome topic, is really cool, even if it still more theory than practice :-D
DPDmancul 1y ago
Theoretically only one operation is sufficient: both NAND and NOR are universal gates, meaning all boolean operations are expressible in terms of only NANDs (or equivalently only NORs). The downside is that the expressions became longer.
- zackmorris 1y ago
  You shouldn't have been downvoted. In chip design, boolean logic circuits are often reduced to their simplest NAND/NOR representation, optimized, then translated to RTL, DTL or TTL as explained below: https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NOR_logic https://en.wikipedia.org/wiki/NOR_logic https://en.wikipedia.org/wiki/De_Morgan%27s_laws https://en.wikipedia.org/wiki/De_Morgan%27s_laws https://en.wikipedia.org/wiki/Truth_table https://en.wikipedia.org/wiki/Truth_table https://en.wikipedia.org/wiki/Resistor–transistor_logic https://en.wikipedia.org/wiki/Resistor–transistor_logic https://en.wikipedia.org/wiki/Diode–transistor_logic https://en.wikipedia.org/wiki/Diode–transistor_logic https://en.wikipedia.org/wiki/Transistor–transistor_logic https://en.wikipedia.org/wiki/Transistor–transistor_logic https://www.etechnog.com/2021/12/comparison-between-rtl-dtl-and-ttl.html https://www.etechnog.com/2021/12/comparison-between-rtl-dtl-... https://hackaday.com/2015/06/30/gates-to-fpgas-ttl-electrical-properties/ https://hackaday.com/2015/06/30/gates-to-fpgas-ttl-electrica... I studied this heavily in my electrical and computer engineering (ECE) courses in the late 1990s, and wish that more programmers were exposed to it. On that note, I never had a single spreadsheet course. Which is regrettable, as that would have tied functional programming to logic circuits. Then it's a small step to understand mutability, then monads (which are more difficult), how they negatively impact determinism, and how that greatly increases the mental load of tracking state in imperative programming. Leading to why futures, promises, deferreds and async programming in general should be avoided. Unfortunately these insights are all but unknown today, which left us with the over-engineered soup of web languages and frameworks that bury us in mountains of unnecessary complexity. Which we tried to get away from when declarative and idempotent HTML/HTTP metaphors were invented late in the desktop computing era, when C++ and object-oriented programming dominated tech.
kristel100 1y ago
[dead]
DinoNuggies45 1y ago
This is wild. I’ve seen CRDTs pop up in collaborative editors, but hadn’t considered them alongside FHE before. What kind of performance hit are you seeing in practice?

277 points by jakelazaroff 1y ago

Encrypt the diffs for the server and write the hash to a blockchain to manage the ordering. Boom, problem solved without HME.

ergl 1y ago
You don't need ordering guarantees for diffs: apply them out of order and the final result should be the same (that's one of the key properties of CRDTs).
- scyclow 1y ago
  So why do you need timestamps? Or, why do you even need a third party server to run HME to begin with? Why not just encrypt the data and let the client figure it out?

chrisweekly 1y ago

For the uninitiated: "In the context of encryption, 'homomorphic' describes methods that enable computations on encrypted data without needing to decrypt it first.

qualeed 1y ago

It doesn't actually say it anywhere, so: CRDT = Conflict-free replicated data type. https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

Xeoncross 1y ago
e.g. commonly used by applications that need to deal with multiple people editing a document.
- MangoToupe 1y ago
  ...or, really, any kind of conflict-free syncing.

Joker_vD 1y ago

> Now, however, the server can no longer understand the changes you send. If you want to see your friend’s latest changes, you’ll need to both be online at the same time. What? No, the server sends you the changes you've not seen yet, you decrypt and merge them, and so you get the latest version of the document. Right? The homomorphic encryption is a fascinating topic, but it's almost never an answer if you need anything resembling reasonable performance and/or reasonable bandwidth. I've seen a paper that ingeniuously uses homomorphic encryption to implement arbitrary algorithmic computations, totally secret, by encoding a (custom-crafted) CPU together with RAM and then running "tick a clock" algorithm on them. And it works, so you can borrow some AWS huge instance and run you super-important calculations there — at 1 Hz. I am not kidding, it's literally 1 virtual CPU instruction per second. Well, if you are okay with such speed and costs, you either have very small data — at which point just run your computation locally, or you're really, really rich — at which point just buy your own goddamn hardware and, again, run it locally.

zawaideh 1y ago
If the server can't operate on the content, it can't merge it into the CRDT documents. Which means it would need to sending and receiving the entire state of the CRDT with each change. If the friend is online then sending operations is possible, because they can be decrypted and merged.
- Joker_vD 1y ago
  I... still can't make heads or tails out of this description. Let me restate how I understand the scheme in TFA: there are two people, editing on the same document using CRDTs. When one person makes an edit, they push an encrypted CRDT to the sync server. Periodically, each of them pulls edits made by the other from the sync server, apply them to their own copy, and push the (encrypted) result back. Because of CRDT's properties, they both end up with the same document. This scheme doesn't require them two people to be on-line simultaneously — all updates are mediated via the sync server, after all. So, where am I wrong?
  - 1y ago

teleforce 1y ago

>Runtime performance is also — to put it lightly — lacking. I benchmarked the unencrypted and encrypted versions of the last write wins register on an M4 MacBook Pro. The unencrypted one averaged a merge time of 0.52 nanoseconds.The encrypted one? 1.06 seconds. That’s not a typo: the homomorphically encrypted merge is two billion times slower. Ouch!

sieabahlpark 1y ago
[dead]

thrance 1y ago

Another cool use of FHE, allowing to browse wikipedia privately while still online: https://news.ycombinator.com/item?id=31668814 https://news.ycombinator.com/item?id=31668814

plopilop 1y ago

As the article mentions, fully homomorphic encryption is insanely slow and inefficient. But I have to say that it is a relatively new field (the first FHE scheme was discovered in 2009), and that the field has immensely progressed over the last decade and a half. The first FHE scheme required keys of several TB/PB, bootstrapping (an operation that is pivotal in FHE schemes, when too many multiplications are computed) would take thousands of hours. We are now down to keys of "only" 30 MB, and bootstrapping in less than 0.1 second. Hopefully progress will continue and FHE will become more practical.

6r17 1y ago
CRDTs are also crazy slow due to their architecture ; even the best alg out there are costly by design ; so adding homomorphic encryption is even more of a challenge ; tough it really is impressing I'm curious if this can be usable at all; edit so i bring some "proof" of my claim: from this very page : `To calculate the new map, the server must go through and merge every single key. After that, it needs to transfer the full map to each peer — because remember, as far as it knows, the entire map is different.`
- __MatrixMan__ 1y ago
  Is it the CRDT that's slow there, or is the problem that they've made it one party's job to update everybody? By having a server in the mix it feels like we're forcing a hub/spoke model on something that wants to be a partial mesh. Not surprising that the hub is stressed out.
  - svieira 1y ago
    The whole point of Conflict-free Replicated Data Types is that you don't need an authoritative server. You're thinking of Operational Transform which does require an authority.
    - __MatrixMan__ 1y ago
      I may have worded that poorly but my intent was to suggest that it would work better if there wasn't a server. I didn't know the name for the serverful alternative though, so thanks for that.

867-5309 1y ago

Conflict-Free Replicated Data Type

deleted 1y ago

[deleted]

NetRunnerSu 1y ago

FHE is indeed slow, but the progress since 2009 is truly remarkable. Bootstrapping speed alone improved by tens of millions of times, and tfhe-rs already demonstrates homomorphic AES-128. Real-time FHE for AI inference/training feels increasingly plausible. > https://github.com/sharkbot1/tfhe-aes-128 https://github.com/sharkbot1/tfhe-aes-128

ProofHouse 1y ago
Can I double click on ‘plausible’ ?
- ketralnis 1y ago
  Sure but it will just select the word in your browser
- throitallaway 1y ago
  Someone's a Chamath fan.

mihau 1y ago

Sorry for going off-topic, but kudos for UI/UX on your blog! To name a few: Nice style (colors, font, style), "footnotes" visible on the margin, always on table of contents, interactivity and link previews on hover. Nice. What's your tech stack?

jakelazaroff 1y ago
No worries and thank you! The tech stack is really just Astro with content stored in Markdown files. The link previews on hover are powered by Tippy.js [1] (maybe deprecated by now?). I wrote a script to collect all the links from my Markdown files, scrape the open graph tags and commit the data to the repo as JSON files. The interactive demos are web components! I wrote a bit about how I built them [2] but maybe should do a more in-depth blog post at some point. [1] https://atomiks.github.io/tippyjs/ https://atomiks.github.io/tippyjs/ [2] https://jakelazaroff.com/words/web-components-will-outlive-your-javascript-framework/ https://jakelazaroff.com/words/web-components-will-outlive-y...

somezero 1y ago

FHE is simply the wrong tool here. FHE is for a central server operating on data held/known by another. They want MPC -multiple parties jointly computing on distributed data- and that’s fairly more efficient.

hoppp 1y ago
I agree. I also often want to use FHE only to realize there are better tools for the job and better ways to do things. The use-case is pretty niche

meindnoch 1y ago

I like it! The slowness and inefficiency of homomorphic encryption is nicely complemented by the storage bloat of CRDTs.

yusina 1y ago

I'm not sure I get the premise of the article. I know what a CRDT is and how homomorphic encryption works. But why do both parties have to be online at the same time to sync? They could send the updates asynchronously, store-and-forward style, and everything in flight is encrypted. Why does this need server that keeps state (which is kept in encrypted state and modified, as per the proposal)?

noam_k 1y ago
I think the issue here is that the server would have to store a copy of the register per peer, as it can't calculate which one is the most recent. Using FHE allows the server to hold a single copy. In other words the server could forward and not store if all parties are always online (at the same time).
- yusina 1y ago
  So it's "just" a storage optimization?
- neon_me 1y ago
  Server will store encrypted blob and its hash/etag. Client before upload of data, check for hash/etag of blob he originally fetched. If blob on server has different one, it will download it, decrypt, patch new data on existing one, encrypt and reupload. Whats the catch? AES is hardware accelerated on the most devices - so with all the ops it will be significantly faster than any homomorphic enc nowadays.
  - nixpulvis 1y ago
    I too was wondering the same thing. FHE is cool tech, but this seems to me to be a bad application of it since it will undoubtedly be less efficient. FHE is useful when trying to compute on data from various sources who all mutually want to keep some information secret. For example, Apple's use of FHE to categorize photos [1]. In this case all the server is really doing is "compressing" for lack of a better word, the change sets, so each offline client doesn't need to sync every message since they are already merged by the server. If all you want is to keep a synchronizing server in the dark, but all clients can be trusted with the unencrypted data, traditional key exchange and symmetric encryption should suffice. [1]: https://machinelearning.apple.com/research/homomorphic-encryption https://machinelearning.apple.com/research/homomorphic-encry...

drob518 1y ago

Love the presentation.

hoppp 1y ago

Don't use THFE-rs because Zama requires a commercial license for anything other than prototyping. Their license sucks. Instead use openFHE (C++) or lattigo (golang) libraries which are both free to use commercially.

jdefr89 1y ago

“We introduced a new abstraction for no reason! Take a look!!”

xvector 1y ago

> keep_self.select(&self.peer, &other.peer); > Rather than if or match expressions, we use FheBool’s select method. It returns the first argument if the underlying FheBool value is true, or the second argument if the underlying value is false. This wasn't super clear to me. I get the computation is performed on encrypted values, but how does ".select" actually work? Is ".select" just evaluating to "keep_self*self.peer + keep_self*other.peer"?

GRBurst 1y ago

Following the topic of FHE for quite some time and I am always hoping that we get some breakthroughs regarding speed. Seeing how this can be applied to CRDTs another awesome topic, is really cool, even if it still more theory than practice :-D

DPDmancul 1y ago

Theoretically only one operation is sufficient: both NAND and NOR are universal gates, meaning all boolean operations are expressible in terms of only NANDs (or equivalently only NORs). The downside is that the expressions became longer.

zackmorris 1y ago
You shouldn't have been downvoted. In chip design, boolean logic circuits are often reduced to their simplest NAND/NOR representation, optimized, then translated to RTL, DTL or TTL as explained below: https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NOR_logic https://en.wikipedia.org/wiki/NOR_logic https://en.wikipedia.org/wiki/De_Morgan%27s_laws https://en.wikipedia.org/wiki/De_Morgan%27s_laws https://en.wikipedia.org/wiki/Truth_table https://en.wikipedia.org/wiki/Truth_table https://en.wikipedia.org/wiki/Resistor–transistor_logic https://en.wikipedia.org/wiki/Resistor–transistor_logic https://en.wikipedia.org/wiki/Diode–transistor_logic https://en.wikipedia.org/wiki/Diode–transistor_logic https://en.wikipedia.org/wiki/Transistor–transistor_logic https://en.wikipedia.org/wiki/Transistor–transistor_logic https://www.etechnog.com/2021/12/comparison-between-rtl-dtl-and-ttl.html https://www.etechnog.com/2021/12/comparison-between-rtl-dtl-... https://hackaday.com/2015/06/30/gates-to-fpgas-ttl-electrical-properties/ https://hackaday.com/2015/06/30/gates-to-fpgas-ttl-electrica... I studied this heavily in my electrical and computer engineering (ECE) courses in the late 1990s, and wish that more programmers were exposed to it. On that note, I never had a single spreadsheet course. Which is regrettable, as that would have tied functional programming to logic circuits. Then it's a small step to understand mutability, then monads (which are more difficult), how they negatively impact determinism, and how that greatly increases the mental load of tracking state in imperative programming. Leading to why futures, promises, deferreds and async programming in general should be avoided. Unfortunately these insights are all but unknown today, which left us with the over-engineered soup of web languages and frameworks that bury us in mountains of unnecessary complexity. Which we tried to get away from when declarative and idempotent HTML/HTTP metaphors were invented late in the desktop computing era, when C++ and object-oriented programming dominated tech.

kristel100 1y ago

[dead]

DinoNuggies45 1y ago

This is wild. I’ve seen CRDTs pop up in collaborative editors, but hadn’t considered them alongside FHE before. What kind of performance hit are you seeing in practice?