Approaches to Delay Tolerant Networking

Architecture
1

Hi all, I’m interested in building p2p digital spaces, and have enjoyed following Spritely’s progress over the past couple years towards this goal. One aspect of p2p networking that I feel is important, is the ability to support more “human centered” networks e.g. networks where devices are not expected to have 100% uptime, and fail gracefully in disconnected scenarios.

Towards this, I have been investing time to projects like Briar and LXMF. In the context of OCapN, and Goblins, I was wondering if anyone would like to share thoughts on how to approach delay tolerant networking with Goblins?

I’m still trying to wrap my head around this project, but at a high level I feel like there are two different approaches:

  • Netlayer level: one way to support DTN capabilities could be to add netlayers that have these properties. I am a bit confused if DTN routing layers like NNCP can be implemented as OCapN netlayers, the example “pigeon netlayer” mentions that it would need some sort of capability to check if the pigeon got lost, which I am unsure is a property NNCP can provide.

  • Actor level: the other way I could think of, would be to have “Proxy Actors” which could implement some sort of store-and-forward, or mesh routing system in the event that a reference to the actual actor object could not be reached. I think that in this solution, there would still need to be some message passing to tell the sender that the message has only been sent to an initial proxy instead of the intended target. But to me this approach seems like it could work? Would love to hear some more thoughts on this.

Btw, I saw mention of a “Relay netlayer” in the IRC logs, if anyone has any additional insight into this project, I would love to hear more about it!

Cheers,
Avon

3 Likes
2

I’m not yet familiar with programming Goblins, but a note that might point you to some further reading in the field/community:

to have “Proxy Actors” which could implement some sort of store-and-forward, or mesh routing system in the event that a reference to the actual actor object could not be reached

This general idea is known as the unum pattern — one logical entity (the unum) made up of its concrete “presences” (actual actors) on many machines. The presences offer to their users some kind of local/low-latency/high-reliability protocol, and internally synchronize with each other via whatever protocol suits the application — it may be centralized (“thick client”s to a server) or decentralized (using some means to achieve consensus on what the state of the unum is).

For a high-level example, in a chat application, your client handling retrying sending messages automatically, and also showing you your message in context of already-received messages, is acting as an unum, by showing you a local state of the chat room and trying to keep it in sync as much as possible, but not blocking your own further actions with it on a successful network roundtrip. The unum pattern is about giving this sort of convenience and latency-avoidance to programs as well as people.

5 Likes
3

Thank you! Unum pattern is the exact idea I was searching for, I really like the distinction between a logical entity and presences.

For anyone like me looking to learn more about the Unum pattern, I found this great writeup: Habitat Chronicles: The Unum Pattern

3 Likes
4

Per the message that seems to have sparked this thread I have been thinking of stuff related to this topic for quite a while.

One idea is to use my ActiveCapCert (WIP) to describe certain kinds of custom unums implementations making them portable/migratable/copyable yet retaining their providence of their code.

Example of such is an unum acting as either part of a ToonTalk Nest-Bird pair. Possibly with in-order and contigious gurantees of messages sent via bird(s) to nest(s). (Though those can only be easily achived iff the bird end is only in one place which makes use of SAC-lines as the way to achive those aforesaid gurantees.)
What can such birdie nest setup be used for? Well, keeping track of baseball league game scores, cruise ship eatery menus, anything that you do not mind being a bit stale/out-of-date.

Another idea is to use the vocabulary/language of AmbientTalk (doesn’t have to be AmbientTalk, see this for an draft of js sketch) to write usefull applications that uses nearby discoverable resources to achive an users’ task.

And all that traffic carried inside Smart Messages that can be using routing code bricks that use climbing up a gradient of “smell” stratedgy towards a fitting target destination(s). (Heck, techniques from Clueless Software Agents could be used to obscure what spefic kind of target destination is sought.)

Other SmartMessage routing/emigration stratedgies possible might be net flood filling, random walk, “smell” gradient decent (“fleeing the stink”), opertunistic local cache perusal (could nearby nodes have a copy of what the SM is looking for) and probably many more.

One question I have, is how to minimize likely hood of Denial of Service due to attack, over-use, or plainly bad programming. Postage? or some such via token bucket or other such well known mechanisms. (Heck using signed attestations by nodes that each node had proccessed particular SmartMessages, each ided by their hash and origin or something, for distributed reputation-tallying for postage credit/debit score might be how it will be done.)

Btw, sorry for the density of this message, I am willing to expand and elaborate here on request or when I suspect that missunderstanding might arise.

2 Likes
5

Thank you for sharing your thoughts! Lots of wonderful ideas here.

Since you first mentioned the project, I have been fascinated with AmbientTalk’s research.
(Quick aside: their work on RFID reminds me of the Folk Computer project. It would be amazing if some future version of Goblins could create a uniform development environment between distributed p2p networks and their spacial computing platform, mapping actors to physical objects etc.)

I think AmbientTalk’s “service advertising & discovery as a syntax” is particularly interesting, and I’m wondering if such a feature would make sense as an extension library for Goblins. Just off the top of my head, it is currently possible to do some sort of advertising/discovery using Bluetooth, p2p Wifi, WLAN multicast, packet radio, and even using certain overlay networks using ideas presented in p2p inboxes. So this peer discovery extension could even carry a similar “netlayer” abstraction that OCapN has. Also worth mentioning Briar project’s recent report covering peer advertising and discovery on Android devices, which you may find useful: Public Mesh Research Report · Wiki · briar / Public Mesh Research · GitLab
There is a close relationship between advertisements and capabilities. Because any receiver of an actor’s service advertisement is able to gain that capability, it might be worthwhile to investigate additional syntaxes for defining “recipient populations” for service advertisements.

I have been exploring Private Set Intersection as a way for nearby peers to see if they have any overlapping “interests” where interests could represent something like a group-chat, forum, really any arbitrary pub/sub relationship. In general this idea of “recipient populations” for service advertisements relies heavily on a digital identity system, so that would be the bigger problem we would need to solve first.

Once you give actors a way of discovering “ambient capabilities”, you could then pair this with one or more of the routing strategies you mentioned. Actors would be able to sense when other relevant actors become available, and react to these events via message passing.

One question I have, is how to minimize likely hood of Denial of Service due to attack, over-use, or plainly bad programming.

There are some papers researching this, the main one that comes to mind is the RESCUE paper from last year: RESCUE: A Resilient and Secure Device-to-Device Communication Framework for Emergencies - TUprints
For my personal research though, I have mostly been interested in the “Social Mesh”[1] use case where you have groups of devices that inherit some form of social trust & moderation (eg group chats as I mentioned above) which is how I dodge solving this problem.

Cheers,
Avon

[1]: With Briar project we generally use 2 terms for common recipient populations:
Public Mesh: Everyone running some sort of mesh software is automatically connected to each other. One quick example is something like the bittorrent DHT.
Social Mesh: Connections are only made with a subset of the public mesh population that you have some sort of existing relationship with. This is usually analogous to your device’s contact list.
This idea is discussed more in this blog post: Confronting Briar with disasters · Nico Alt
(archive.org link because it appears the site is currently down)

1 Like
6

Hmm… an idea comes to mind how to do Private Intersection Set via virtual sequential logic circuit run ontop of Ueli Maurer’s SMPC.

Aside: How to get an sequential logic circuit to work on that? Basically by adding a delay cell to the primitive compontents the SMPC supports. What is an delay cell in this context? Basically a component that acts both as an Output and an Input only the wire value outputed from previous tau/comm-round is the Input wire value this tau/comm-round. Implemented by having each SMPC node hold onto their secret-shares for the wire value to the Output from this tau/comm-round and use them directly as their secret-shares for the wire value for the Input wire.

Here is how the PIS circuit would look like: Think of a k by k grid of tag-value eq-comparators.
Each eq-comparator two value inputs are connected to a value bus running horizationally above it and a value bus running vertically left of it respectively.

The horizationally running buses are driven by Inputs from Alice whilist the vertical ones are driven by Inputs from Bob.

Hold on what is an eq-comparator, you ask? It is a rather simple composite device made up of x many XNOR gates and an multi input AND gate, where x is the bit width of the two input buses of the device.

An XNOR gate itself is a composite made of an XOR gate, which is an primitive, whose output feeds into a NOT gate.
The NOT gate is basically an XOR gate whose one input is from the VCC wire, which should always have the wire value one, and the other is the NOT gate input.
And the VCC wire comes from the output of an AND gate whose inputs comes from VCC labeled Inputs from both Alice and Bob respectively. Btw the VCC feeds to an ON indicator Outputs to Alice and Bob.

So back to the grid of the eq-comparators. The outputs of each eq-comparator in a column feeds into an multi input XOR gate for that column. Same way for rows. This means each eq-comparator output feeds into two multi input XOR gates, one for the column it is in and one for the row it is in.
These column XOR gates’ outputs feed into Outputs to Alice. The row ones feed into Outputs to Bob.

This means that Alice gets to know which tag-value Input columns she shares with Bob.
Bob gets to know which tag-value Input rows he shares with Alice.
However neither gets to know the others other tag-values nor which corrisponding others rows or columns.

There is just a tiny teeny problem with this circuit. As multi input OR gates are quite a bit expensive to compose in this SMPC setup (basically an NAND gate with inverted inputs, and the AND gates costs in tau/comm-round delay) I used an multi input XOR gate. Which I can get away with iff all but one of its inputs is zero.

Alice (or Bob) could feed the same tag-value into two diffrent column/row Inputs thereby denying Bob (or Alice) knowledge that they have the tag-value in common yet learning that Bob (or Alice) has it.

But not to worry, we can add eq-comparators to compare each column (or row) tag-values with every other such and have an Output flags to both Alice and Bob telling them that the other party had put the same tag-value more than once whilist also preventing the column/row outputs.

Or it might be cheaper to just use an multi input OR gate instead of the last XOR gate in each column/row.

Here it is as a BLIF:

# extended Berkley Logic Interchange Format
# basically a .bus command added
# k is 4 in this example
.model PIS
.inputs VCC
.inputs Alice_I1 Alice_I2 Alice_I3 Alice_I4
.inputs Bob_I2 Bob_I2 Bob_I3 Bob_I4
.outputs Alice_O1 Alice_O2 Alice_O3 Alice_O4
.outputs Bob_O1 Bob_O2 Bob_O3 Bob_O4
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I1 o=tmp0
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I2 o=tmp1
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I3 o=tmp2
.subckt eq_comp VCC=VCC a=Alice_I1 b=Bob_I4 o=tmp3
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I1 o=tmp4
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I2 o=tmp5
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I3 o=tmp6
.subckt eq_comp VCC=VCC a=Alice_I2 b=Bob_I4 o=tmp7
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I1 o=tmp8
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I2 o=tmp9
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I3 o=tmpA
.subckt eq_comp VCC=VCC a=Alice_I3 b=Bob_I4 o=tmpB
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I1 o=tmpC
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I2 o=tmpD
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I3 o=tmpE
.subckt eq_comp VCC=VCC a=Alice_I4 b=Bob_I4 o=tmpF
.subckt or_4in VCC=VCC a=tmp0 b=tmp1 c=tmp2 d=tmp3 x=Alice_O1
.subckt or_4in VCC=VCC a=tmp4 b=tmp5 c=tmp6 d=tmp7 x=Alice_O2
.subckt or_4in VCC=VCC a=tmp8 b=tmp9 c=tmpA d=tmpB x=Alice_O3
.subckt or_4in VCC=VCC a=tmpC b=tmpD c=tmpE d=tmpF x=Alice_O4
.subckt or_4in VCC=VCC a=tmp0 b=tmp4 c=tmp8 d=tmpC x=Bob_O1
.subckt or_4in VCC=VCC a=tmp1 b=tmp5 c=tmp9 d=tmpD x=Bob_O2
.subckt or_4in VCC=VCC a=tmp2 b=tmp6 c=tmpA d=tmpE x=Bob_O3
.subckt or_4in VCC=VCC a=tmp3 b=tmp7 c=tmpB d=tmpF x=Bob_O4
.end

.model eq_comp
.inputs VCC
.inputs a b
.outputs o
# we assume here that a and b are buses of bitwidth 16 but most likely would be 128 or 256 in non-example use
.bus bus=a w0=a0 w1=a1 w2=a2 w3=a3 w4=a4 w5=a5 w6=a6 w7=a7 w8=a8 w9=a9 wA=aA wB=aB wC=aC wD=aD wE=aE wF=aF
.bus bus=b w0=b0 w1=b1 w2=b2 w3=b3 w4=b4 w5=b5 w6=b6 w7=b7 w8=b8 w9=b9 wA=bA wB=bB wC=bC wD=bD wE=bE wF=bF
.subckt xnor VCC=VCC a=a0 b=b0 x=t0
.subckt xnor VCC=VCC a=a1 b=b1 x=t1
.subckt xnor VCC=VCC a=a2 b=b2 x=t2
.subckt xnor VCC=VCC a=a3 b=b3 x=t3
.subckt xnor VCC=VCC a=a4 b=b4 x=t4
.subckt xnor VCC=VCC a=a5 b=b5 x=t5
.subckt xnor VCC=VCC a=a6 b=b6 x=t6
.subckt xnor VCC=VCC a=a7 b=b7 x=t7
.subckt xnor VCC=VCC a=a8 b=b8 x=t8
.subckt xnor VCC=VCC a=a9 b=b9 x=t9
.subckt xnor VCC=VCC a=aA b=bA x=tA
.subckt xnor VCC=VCC a=aB b=bB x=tB
.subckt xnor VCC=VCC a=aC b=bC x=tC
.subckt xnor VCC=VCC a=aD b=bD x=tD
.subckt xnor VCC=VCC a=aE b=bE x=tE
.subckt xnor VCC=VCC a=aF b=bF x=tF
.subckt and_16in i0=t0 i1=t1 i2=i3 i4=t4 i5=t5 i6=t6 i7=t7 i8=t8 i9=t9 iA=tA iB=tB iC=tC iD=tD iE=tE iF=tF o=o
.end

.model and_16in
.inputs i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 iA iB iC iD iE iF
.outputs o
.subckt and_4in a=i0 b=i1 c=i2 d=i3 x=t0
.subckt and_4in a=i4 b=i5 c=i6 d=i7 x=t1
.subckt and_4in a=i8 b=i9 c=iA d=iB x=t2
.subckt and_4in a=iC b=iD c=iE d=iF x=t3
.subckt and_4in a=t0 b=t1 c=t2 d=t3 x=o
.end

.model and_4in
.inputs a b c d
.outputs x
.gate AND a=a b=b x=t0
.gate AND a=c b=d x=t1
.gate AND a=t0 b=t1 x=x
.end

.model or_4in
.inputs VCC
.inputs a b c d
.outputs x
.subckt or_2in VCC=VCC a=a b=b x=t1
.subckt or_2in VCC=VCC a=c b=d x=t2
.subckt or_2in VCC=VCC a=t1 b=t2 x=x
.end

.model or_2in
.inputs VCC
.inputs a b
.outputs x
.subckt not VCC=VCC a=a x=t1
.subckt not VCC=VCC a=b x=t2
.subckt nand_2in VCC=VCC a=t1 b=t2 x=x
.end

.model nand_2in
.inputs VCC
.inputs a b
.outputs x
.gate AND a=a b=b x=t1
.subckt not VCC=VCC a=x x=x
.end

.model not
.inputs VCC a
.outputs x
.gate XOR a=a b=VCC x=x
.end
1 Like
7

How strong is the privacy requirement?

From the weakest, where anyone can know that you are running Briar and what your Briar-handle is to strongest where only friends can know.

I am thinking of the middle of the road where anyone can know you are running Briar but does not know your Briar-handle, who you are communicating with, or such at all. Basically on the same level as Signal.

If that is the case and some incentive engineering such as earning perks in a fun mobile game or other such for providing DTN carrage could be brought to bear then it might be possible to make it look innocent and provide more mesh-/DTN-nodes in the same fell swoop.

1 Like
8

How strong is the privacy requirement?

Currently, Briar’s threat model is to not only preserve message content privacy, but also to preserve metadata privacy wherever possible (e.g. keep private who is talking to who, and at what time). For example, currently 1-on-1 private messages aren’t able to be relayed through mutual contacts in order to preserve metadata privacy. Currently the only messages that can be properly multi-hopped through a network of contacts are group chat messages and blog posts.
There’s pretty much a direct correlation between privacy and connectivity in these types of ad-hoc networks, so we have been thinking about ways to allow users to selectively control their connection preferences over time, one suggestion is to add in a tor browser-like security level selector.
There’s also been some interesting discussion on this topic on the briar-devel mailing list if you’re interested: briar-devel Mailing List for Briar
Worth mentioning there is a project working on the “weakest” privacy level, optimizing for connectivity at the cost of metadata privacy (note that all message content is still e2ee): https://qaul.net

I am thinking of the middle of the road where anyone can know you are running Briar but does not know your Briar-handle, who you are communicating with, or such at all. Basically on the same level as Signal.

One interesting project I found since my last message was Willow Protocol. From my understanding, it actually uses private set intersection to allow peers to discover shared namespaces, and if there is >1 shared namespace, the peers deterministically sync those namespaces with each other.
This is very close to the idea I was describing previously, and might allow for a high-connectivity ad-hoc messaging system that also gives users reasonable privacy assurances.

Hmm… an idea comes to mind how to do Private Intersection Set via virtual sequential logic circuit run ontop of Ueli Maurer’s SMPC

Apologies because this is going to take me some time to wrap my head around, but this is really interesting work, thank you so much for the link to the SMPC paper and the circuit writeup!

1 Like
9

Oh hey, I’ve only just started reading through this thread but this is something that I’ve been interested in for a bit now. It does feel like there’s potential for some very nice user interactions there.

Among other things, the “whiskers” emanating from pages feel like they could almost directly map to capabilities between objects. (It’s not quite a perfect 1:1 relationship, since you likely do want connections between objects in non-adjacent pages too… I was struggling a bit with how to model that.) But indeed, you could do some pretty cool things in a system like that with local wireless communication. You might share a restricted revocable capability to interact with (parts of) your email inbox for as long as your phone is on the table, for example, or share a photo gallery from your phone for collaborative editing on the table, or… things like that.

For device introduction and for capturing user intent, the Folk/Dynamicland interaction model has maybe an easier time of it than some, because the system has a camera pointing down at the surface you’re working on. The software running the table can thus potentially read a pairing code (QR code, etc) off the screen of your phone.

2 Likes
10

Another way that comes to mind is to have each user-level-message (or bundle there of) carried by a Smart Message or such that is basically an basic construction from that Clueless Software agents paper I have linked in this thread. (Not fully fleshed out but I think it might work). What would be the environ symmetric key? Probably the destination user id or tags expanded by any Passphrase-to-symmetric key expansion algorithm of choice.
(If it is an ongoing conversation or the contacts know each other then the environ key could be a shared secret between them or other such stuff)

Heck such an envelope Smart Message could be carrying the entire, or portion there of, outbox of the sending user.

That means this kind of envelope Smart Message would require rather promicious distribution but that might be okay for reliability point of view.

Though it might put more pressure on finding a solution for the incentive-to-carry side of the problem. (See prior mention of the spam/over-use etc problem earlier in the thread.)

What about timing correlation attacks and “is this a new user-level message?” attacks?
Well the latter can be solved by using the environ symmetric key to encrypt an ephimeral symmetric key for the user level message. And the former can be somewhat mitigated by sending chaff. Heck the chaff could be (partial) backups of the users messages, media, etc, addressed back to the sender and a backup service.

Sorry if this was a bit rambly but I was just idly musing on how to start tackling this problem.

1 Like
11

I recently had a start of two ideas regarding the postage question in my ramblings above.

First one is a tracing record of where a message has traversed node wise and reward those nodes with cybercoinz (cryptocurrency), prestiege (karmapoints), stamps (see later) or what have you.
To ensure some privacy (thwart route tracing by passive eavesdropper) and each contribution (of carrying the message) I am going to steal a page from Macaroons and use a chained hmac construction.
The initial hmac key would either picked at random and encrypted to the destinations public key or something else (loose end).
In the first chunk for the hmac construction I put the hash of the payload message (or in the case of smart message, the hashes of the code bricks of the sm).
Then for each node hop I add an hmac chunk that is encrypted like the third party caveats in macaroons are. In those I put the node reward handle, which could be a shielded zcash address or some such. (Additional hmac chunks for smart messages contains the hashes of the SM’s data bricks migrated to or from that node).
This way, the destination of the message gets a list of node reward handles. This list could be augmented in the design to keep track of resource usage at each node.
Just one problem, this setup can be cheated a bit by nodes inflating the reports of resource usage and add in superfluidous node reward chunks making it look like the message had hopped more nodes than it actually had.

The second idea is for each node to mint their own stamps. These give messages with them, arriving at a node that minted them, priority processing/treatment over those that lack them. (Basically, sort the messages by postage paid.)
What would these stamps look like? Again a bit like macaroons. The minting node only needs to know its own initial hmac key to verify them and a list of unspent stamp serial-number/identifier. To afix a stamp to a message, the initial hmac chunk of the stamp contains the hash of the message (or for SMs the code brick hashes and in subseq chunks the data brick hashes).

(As the stamps are hmac constructions one could go my Macaroon-Paymer hybrid route but more on that only by request or when I decide to write about it here in a new post)

Sorry for necro bumping this topic if y’all had lost intrest but got notified.

Cheers.

1 Like
13

So, my Macaroon-Paymer hybrid.

First what the heck is a Paymer? It refers to a now defunct value-transfer product that provided bearer ‘cheques’.

These cheques are composed of three things: serial number (lets say here an uuid), code (basically a pass-word/-phrase/-numsequence, at least 12 chars), and amount (like Agoric Amounts, that is a bignum and brand).

The actions the Paymer service provided were

  • Issue, get a cheque by paying (via credit card, zcash transfer, what have you) the service.
  • Redeem, get paid by the service by giving the serial number and code of the cheque being withdrawn/redeemed.
  • Transfer, give a cheque (serial number & code) and transfer some or all of the amount to a given cheque (only serial number needed) or a new cheque.
  • Split a cheque into an array of new cheques with given amounts.
  • Merge two or more cheques.
  • Verify/Inspect a cheque, (only serial number needed)
  • Change code of a given cheque.

So, where do Macaroons or more spefically chained hmac constructions come into the story?

Well, instead of just using a serial number and code pair per cheque we transform each cheque into a Macaroon or such, by using the serial number as the ‘location’ and the code as the initial hmac key.

The ‘location’, timestamp of issuance, and initial amount is in the first hmac block, the header.

Then we can use following kinds of hmac blocks (each block uses the hmac output of previous block as its hmac key) to indicate to be performed Redeems, Transfers, Splits, Merges, as per the Paymer methods enumerated above, plus some types of caveat enforcements.

An Transfer block basically just indicates the serial number of another cheque and the amount to be transfered to that one.

An Split actually requires two kinds of blocks: one that lists how many splits and their amounts, and one that indicates which split (by index numeral) this branch of chain of hmac blocks we are continuing on with.
The former kind of hmac block must immediately be followed the latter.

An Merge block basically contains another entire ‘Macarooned’ cheque whose last hmac block is a Transfer to the serial number of this enclosing cheques. (tbd: does the hmac output of that enclosed cheque need to be encrypted or can it be in the clear?)

An Redeem block could contain sensitive information, such as bank details for example, so its payload should be AES-GCM encrypted using the hmac key of that hmac block as the symmetric key. (You get the next hmac output by hmacing the plaintext using the same hmac key).

Then there are the usual caveats such as onlyBeforeTimestamp, onlyAfterTimestamp, comment/noise (always passes), and verifyOnly.

The verifyOnly caveat must make it so no other hmac blocks other than caveats can be added/chained-on.

An caveat kind spefic to these cheque is currentAmount that can be used to sanity check the amount of a ‘Macarooned’ Paymer cheque.

Let me know if this was too rambly or if I need to expand upon something herein.