News for hackers. Stuff that matters.
Re:Ask HN: What is new in Algorithms / Data Structures these... by some_furry on Wednesday May 10, 2023 @11:39AM (#35888951)
Problem 2 can be solved by "cryptographic erasure" techniques.

1. Encrypt the data with an ephemeral key.

2. Upon delete, just wipe the key. The data becomes unrecoverable.

I'm not sure about problem 1. A fast seekable stream cipher like ChaCha might help here (don't use e.g. RC4 for this), but a faster hash like BLAKE3 might be more appropriate. I'm happy to noodle over this some more. These are just my unfiltered thoughts.

If you combined the two: Each entry in the graph could have a public salt used for key derivation, for both the DAG and for the actual data. To delete an entry, zero-out the salt and the underlying key becomes unrecoverable.

Re:Ask HN: What is new in Algorithms / Data Structures these... by josephg on Wednesday May 10, 2023 @06:48PM (#35894523)
Yes. But diamond types stores a new entry in the DAG for every keystroke each user makes. The current scheme of IDs being (agent, sequence number) allows subsequent operations by the same user to be trivially run-length encoded. Eg if I make 1000 changes in order, we can encode that as (“seph”,1..1000). It takes much less than 1 byte of overhead on disk per character typed.

Salts per character + cryptographic erasure would solve problem 2. But how do we do it without a massive increase in storage, memory use and network bandwidth? I don’t want to generate and store a cryptographically unique salt per keystroke. (Even though it might run fine on modern hardware).

Re:Ask HN: What is new in Algorithms / Data Structures these... by some_furry on Wednesday May 10, 2023 @09:32PM (#35896136)
I'm not sure. I don't know if it's even possible, but until someone proves it isn't, I'm probably going to keep thinking about it.
Re:Ask HN: What is new in Algorithms / Data Structures these... by oconnor663 on Thursday May 11, 2023 @03:53AM (#35899125)
I apologize for commenting on this with almost no context about what the actual data structure looks like, but would it be possible to put the random salts "higher up in the tree"? Then whenever you want to delete some small leaf element, you actually delete a whole salted subtree and replace it with a new subtree, mostly the same but with a new salt and missing the deleted element? This might make edits more expensive, in exchange for reducing the storage overhead of the salts?
Re:Ask HN: What is new in Algorithms / Data Structures these... by tlb on Thursday May 11, 2023 @03:59AM (#35899175)
You can store a lot per typed character and never come close to the storage requirements of pictures and video.

Writing a novel is a couple million keystrokes over a year, so even storing a kilobyte per keystroke is trivial.