Asynchronous messaging, small groups and encryption

Problem description

I thought a lot recently about the Asynchronous Private Messaging problem, which is the same as your cell (=DHT) not being lively enough, particularly for small groups.
I mostly was thinking in terms of short-lived, mobile nodes (assuming that Holochain will one day be native for mobiles) with messaging (Kizuna, e.g.) or other apps where you’ll have smaller groups (digital pantry? :wink:).
If you use a Holo port, this probably won’t be a problem (since they normally have high uptimes - but they’re not really trusted themselves, so there is the thing about decrypting them only in the browser).

The only option (?!) in this case is to accept an untrusted agent with high uptime in your network. Untrusted, because you don’t trust him reading your data.

Solution 1:

Expand your cell(=DHT) with one or multiple servers, i.e. agents you don’t trust to read your data, but have a high uptime. This could include incentivized joining i.e. you pay them to be part of your cell. For this, you would need to encrypt all data/messages on the DHT using End-to-End Encryption (E2EE). This would effectively make a group inside the cell, where everyone in the cell has the encrypted data, but a subset - ‘the group (of friends)’ - also can decrypt the data.

Actually, to make larger cells with consequently higher livelihood, multiple groups could co-exist in one cell. If you don’t have the keys to a group, then you’re acting as a server to this group…

Solution 2:

You use 2 cells/DHTs. The first only consists of the group participants, so since this is a separate network, messages don’t even have to be encrypted. When it seems that the cell is not lively enough, e.g. the redundancy factor (as an absolute number of agents) cannot be reached, then the messages are encrypted and put into another cell (with much more - untrusted - agents or ‘servers’).

This has the benefit of reducing storage overhead for servers when everyone in the group is online. On the other hand, then has to be determined which message is already received by everyone, otherwise you would end up still putting everything on this second, encrypted cell. (I just realized this might become too complex, messy)
Furthermore, this might not be implementable with the Holochain core as it is right now?

Conclusion

In all cases (both + using Holo), some form of E2EE would be needed. As posted here on the forum, a Holochain dev is looking if x3dh is adaptable to a P2P environment.
I’m not a cryptography expert, but I’m really triggered about the problem, and it seems that there are already some algorithms using x3dh as their base. I found: OMEMO, (meg)olm and draft in progress: MLS.
If I understand correctly (no security expert!), there isn’t yet an E2EE that works in P2P, but these protocols work on a centralized and/or decentralized, federated environment.

The silver bullet would thus be an encryption scheme which allows asynchronous group communication with possible multiple devices(=agents) for each person, working in P2P.
(Is this all? See for example future comparison on OMEMO website)

Feedback

The core team and Kizuna probably have thought a lot more and harder on this…
This is only my attempt to summarize what I think I understand.
@Kizuna, is solution 1 how you’re seeing things?
@holochaindevs, I read somewhere that there is ‘work being done’ (if I recall) to reduce problems with small cells. Is this in essence not the only way too really do this? (adding more agents)

Discussions:

I take the liberty to ping a few people to see if my understanding is correct and if this is the way Holochain/Kizuna is developing… : @tats_sato @pauldaoust

1 Like

Hi @th1j5, you’re identifying some very important concerns re: the async private messaging pattern (and the extension thereof to small groups). I like your solution 1 best; IMO it’s a good balance between keeping a tight membrane around a small group vs enjoying the resilience of a large DHT. (Actually, it sounds like you’re talking about Holo Host :wink: :wink: :wink: ) Solution 2 is clever, but I think I agree with you about it adding complexity while potentially eventually converging on solution 1 anyway. (It would be possible on Holochain, though; it’s just application design.)

I’m not a crypto expert either, but x3dh definitely seems to require some sort of centralised stewardship of cryptographic material that people produce. This could be done on Holochain using trusted key steward nodes, but it would be lovely to get away from that completely.

The new crypto functions introduced to RSM, which I hope to write an article about soon) allow Alice and Bob to do a non-interactive D-H exchange using throwaway keypairs. It’s a simple black box, and it could be used to implement all sorts of probably pretty sure cryptographic protocols, though likely not double ratchets which require extra entropy over and above what these functions can accept.

2 Likes

talking about oracles?

:rofl:

Validation problem

As seen here: DevCamp Question: How does encrypted data gets validated? - #16 by th1j5, Solution 1 would make it very difficult to validate anything about the encrypted data. (Actually, the moment you start encrypting, nobody can validate it anymore)

Solution 2

I was thinking that for a chat app solution 2 might be feasible, since you probably already implement the ‘person x has seen post y’ marker, but still lots of work.

Solution 1a

Since these are small groups with people you might know, you don’t care if validation is done in between. (Only before encrypting and not as part of Holochain_validate, but of the UI or somewhere else). Even in medium-small groups where you don’t know everybody, you assume they will not hack there Conductor/UI to send too long chat messages or include the forbidden cat emoji :slight_smile:
Conclusion: no holochain validation needed, just always true

Solution 1b

I cannot help but wonder if ‘inconsistent validation’ would one day be a future and not a bug.
Let my clarify:
Trudy was invited to our encrypted chat about everything but cats. This is validated by using decryption keys to verify, if you’re not a ‘server’.
He hacks his conductor to include a cat smiley :scream:.
All agents of the group are astonished by the brutality and decide not too communicate with him anymore (validate failed, so… *) - this should also include automatically kicking him out of the group encryption.
The server, who can’t verify anything, doesn’t really care if Trudy still communicates with him or not, as long as he gets paid to be part of the DHT. (This might be better combined with **, where vouches are unencrypted)

2 remarks:

  • how huge/what would these problems be? (Probably advanced stuff :slight_smile:)
  • seems like this vouch pattern (**) concludes in somewhat a ‘majority’ vote, but on-chain and as app-logic, nothing for Holochain core to worry about. (all unencrypted, of course)

Solution 1c

After writing (1b) I thought: you can always write your own validation (after decryption) and if this fails somehow decide to

  • kick Trudy out of the encrypted group chat by in-app logic
  • ** anti-vouch Trudy? Like membership by invitation, but where you revoke your vouch… (something along these lines - no clue if/how easy this would be implementable)

Conclusion

Do you guys/girls think that there are some valid thoughts to solve the validation + encryption?


*maybe I should update my knowledge about what can and cannot be done when validation fails, so please forgive my ignorance if this scenario is not correct
Probably should also look at it to know what the important distinction is between using holochain validate and writing your own custom logic to undertake action.


My posts are really huge, damn :sweat_smile:, thank you all for bearing with me

1 Like

small side notes that the integrity of data is ensured by hash even if encrypted

if someone tries to modify an encrypted message it won’t hash correctly so will be flagged by the network and it won’t decrypt for the intended recipients because we use AEAD encryption

the rough length can be determined from the encrypted data, we pad messages out to 32 bytes but a message that is hundreds of chars too long will be detectable

other data about the message such as timestamps etc. can be validated even if some component of the message is encrypted

validation of forbidden characters or text within encrypted data can’t be handled with the default/native validation and so needs a domain-specific solution (without hand waving about zero knowledge proofs)

in this case…

can chat recipients themselves sign messages to move them from ‘unapproved’ to ‘approved’?

if so, and you have some concept of a ‘session’ that ties chat messages together somehow, can you force chat participants to frequently re-key the session (e.g. double ratchet)?

if so, can agents simply refuse to share/negotiate new keys with agents who don’t have all their current session’s chat messages signed?

4 Likes

hm, there’s a lot of good exploration in these ideas. I can see some of them working in combination: e.g., maybe a group has a rule that you need a majority of anti-vouches in order to boot Trudy out, and then once they’ve been collected, the group all changes the session secret without telling her. If the session secret were a blend of secrets contributed by all participants, anyone who refuses to help change it would automatically boot themselves out too.

This would allow you to have small groups within one DHT, giving the resilience of a large DHT but the privacy of a small DHT. One concern is that all the validation of anti-vouches would have to live in the client rather than the DNA, because if they were unencrypted they would leak information about group membership and that’s not cool! Leaving validation to a non-Holochain component would normally be a bad thing, because there’s no way to formally verify compliance, but in this case you’ve got a small group with a naturally higher level of trust where group membership is already being governed by human intervention anyway.

As for smaller DHTs where the DHT is the group, this is a bit trickier. On the one hand, you’ve got built-in membrane control techniques. You can’t rely on validation failure to boot out an agent, because you’re still using encryption in order to make that host be blind to the data it’s replication. But you can delete an agent ID entry, and FWIU that means they’ll be booted out of the DHT. The delete will need to be validated, and if you want anything better than “just trust all deletes” you’ll want them to be in plaintext – which of course means the Holo host will be able to read the member list (but they can anyway, because it’s the DHT peer table!) A validation rule could be “a delete of an agent ID requires endorsement from three members” or “endorsement from an admin” or something like that.

3 Likes

not to my knowledge either, but I think the concepts of membranes could help with this. how are you setting up the DNA? perhaps a fundamental change in structure might be appropriate. have you read: Throwaway DHT

in solution 2, why not use multiple throwaway DHTs? Once Trudy misbehaves, flag the account, gossip it, then for the next DHT their account is not allowed back. I guess in this case, a “boot” would mean a sort of fork where everyone agrees to fire up a new DHT sans Trudy. (Hope I’m understanding the question properly)

1 Like

Another option could be to create individual channels of encrypted comm, where validation is used to temporarily share that message with others.
Ex.
Chat server contains participants A,B,C,D
A->B private channel
B->C etc
When A ‘posts’ to server, really what their doing is sending a private message to B and then validating the option to share it with C & D

This basically falls under Solution 1c:
That way if someone acts up, just build in a block feature to allow you to stop sharing with Trudy… then only have to make sure the others are on board to not share the message you shared with them. Ideally you know who the participants are (because you invited them / authenticated via biometric or KYC etc) and thus can start banning accounts from DHT.

As he referenced, consider filtering messages through an oracle:

Thank you all for the answers.

Some answers suggest that I haven’t been clear with my intentions for these questions.

The problem about asynchronous messaging/small groups is something I think is important to be solved to create hApps with these small, confidential groups. My question was actually: how are you (Holochain/Kizuna) solving this? But I also wanted to include some of my own thoughts and see if these are valid.
After some response from the @thedavidmeister, it seemed that in these cases (with encryption) the baked in Holochain validation isn’t really helpful anymore.
And I wanted to know a bit more about that too…

I’m currently not in the process of writing any app (only thinking about it). What I probably will end up doing is having a good look at Kizuna (since it’s open source) and see how they solve it. Since sending encrypted group messages will probably the same as committing an encrypted entry. And in the case of digital pantry, just changing this to some format to update your food storage might be enough.
(since I wouldn’t mind copying some code, I of course backed Kizuna :slight_smile:)

This is probably very true, thank you. I cannot answer your counter questions, for the aforementioned reasons.

@pqcdev, I have seen Throwaway DHT, but I’m not sure how this helps here…

I’ve only now found these hackmd documents about Kizuna (so much for my good research before posting :sweat_smile:)
Anyway, I’ll tag @Akirawakabayashi here too (also part of Kizuna), so they can maybe comment on this if they have time. Since there only at the start of development (according to their timeline), they might not have figured this out either, but I think it’s something they will need to solve eventually too.

the way i think about it is that there is Agent Centric Validation and agent centric validation

like, there are callbacks and workflows etc. that are called Validation and work in a certain way

but also in a way everything in the wasm is agent centric validation, because it’s all part of the same hashed codebase that everyone runs

if you represent deterministic rules about key exchange/distribution in the wasm such that malicious/corrupt agents are dropped from the distribution due to reliable (for honest nodes) emergent behaviour, then that is also part of ‘agent centric validation’ even if it happens outside a callback explicitly called ‘validate’

3 Likes