Understanding the Information Dispersal Algorithm (IDA)

Features
1

Data on SN is replicated, but what if we can do better? More reliability, less overhead? That’s what Information Dispersal Algorithms are for.

This is well established work since it was originally published in 1989 by Michael Rabin in the paper Efficient dispersal of information for security, load balancing, and fault tolerance.

The current early code for this is in dirvine/rabin_ida

From the paper, some key points to appreciate are:

The storage and transmission of data tiles in distributed systems gives rise to significant security and reliability problems.

An obvious countermeasure against loss of files is to store copies at other network nodes. If we consider, say, a total of five copies to be necessary for the required safety margin, then this entails a fivefold blowup of the total storage in the system [which the IDA algorithm is trying to avoid / solve / improve].

we can create k copies of the file, select k paths connecting node A to node B, and send a copy along each path. This will result in k-fold increase in network load [which the IDA algorithm is trying to avoid / solve / improve].

We propose a method, the Information Dispersal Algorithm (IDA), of reliably dispersing the information in F into n pieces or locations. The file can be reconstructed from any m pieces. The salient point is that each piece is of size |F|/m, where |F| is the size (number of characters) of F. Consequently, the total number of characters is n/m ⋅ |F|. Since we can choose n so that n/m ~ 1, our dispersal method is space efficient. Also, the dispersal and reconstruction are computationally efficient.

Some things that are worth understanding a bit better which I’ll slowly try to understand (or if anyone has insights please chip in!):

Does IDA replace existing parts of the network logic or is it improving and extending it? (seems like it doesn’t replace anything, just improves it, see Update May 26)

How is this algorithm different from shamir sharing?

How is this algorithm different from erasure coding such as Reed-Solomon codes?

Is this algorithm used by clients, or is it used by nodes? (seems like both, see Update May 26)

Is this used before self encryption, after self encryption, or instead of self encryption?

How do we choose m and n? What are the tradeoffs? (seems to be related to elder size and thresholds, see Update May 26)

Some existing information from maidsafe about IDA:

Update May 26 2022

we’re not proposing replacing replication with an IDA

The change is that adults will be able to split chunk A into seven pieces using an IDA and pass just one piece back to the elders on request, rather than the whole chunk, meaning that much less data is exchanged.

IDA is a different beast from threshold cryptography, designed for optimising data storage and transfer rather than secret sharing.

Here’s a quick and easy paper on it https://www.eecs.harvard.edu/~michaelm/TALKS/RabinIDA.pdf

IDA was also mentioned back in 2014 in this post

IDA (Rabin - Information Dispersal)-> splits up data into N of P (N == number of shares, P == parts required to make up N). Its relatively efficient and the data/P is pretty close to efficient (similar to how RAID works). It is not secret though.

13 Likes
2

Something I wonder is whether I have the flow correct in my head or not.

From Update May 26, 2022

If the client contacts all seven section elders asking for a 1MB chunk ‘A’, and each elder in turn requests chunk A from the four adults holding it and returns them to the client, then potentially that’s 28MB (4x7) passing across the network for a single 1MB GET request.

Is this the correct diagram for this process?

IDA_understanding_1

Currently, we are using a halfway-house system where the client contacts three elders at random and those elders contact the four adults holding chunk A - so we potentially have 12MB (3x4) of data flowing across the network for a 1MB request - better, but still not great. And reducing contacts to three elders comes at a cost: if we have only three elders interacting with the adults we no longer have a supermajority to decide if one of the adults is dysfunctional, making dysfunction tracking more complex.

Is this the correct diagram for this halfway-house process?

IDA_understanding_2

A solution we are looking at now is information dispersal algorithms (IDA, also known as erasure coding). This could help us significantly reduce the volume of data transfer per GET, by having adults pass a share of the data to the elders rather than the whole thing. The elders then pass these data shares back to the client, who reassembles them and, voila, chunk A is recreated. Potentially this could reduce the flows on a GET to just 1.4MB for a 1MB chunk.

The change is that adults will be able to split chunk A into seven pieces using an IDA and pass just one piece back to the elders on request, rather than the whole chunk, meaning that much less data is exchanged.

Once it has collected five out of the seven pieces, the client can reassemble chunk A.

Does this diagram correctly reflect this process?

edit: no it can’t be correct since each elder only receives 4 shares (one from each adult), but we need 5 shares to reconstruct the data, ideally all 7 would arrive… do elders contact more than 4 adults? Is it 7 adults (to get 7 shares)?

IDA_understanding_3

Just trying to understand the flow of data and the amount of duplication and network messaging… still not sure if I got the flow right or not?

8 Likes
3

I don’t know about the maths or technicals of IDA’s but I definitely hope that it helps with network stability and reading up on it is interesting so far.

There was an old discussion (I think with a Storj dev) here.

4 Likes
4

Ah no. What happens is the replicants have the whole chunk. Elders ask the Adult to IDA the chunk, giving the Adult 7 pieces of the chunk. Each Elder gets a single piece and sends that back to the client.

In addition, what we are looking at is we ask Elders for the data from a single adult (all elders can see whether he is responsive or not). If the adult is non-responsive, the elders mark him as such.
The client would timeout that lost chunk and ask for the next closest adult.

Clients don’t know adults but do know there are 4 of them (likely to be 7 now) so can ask for Get(ABC)[0] to get ABC from the closest adult or Get(ABC)[1] for the next closest etc.

Adults could pre IDA ll data if required but the Rabin algo is pretty quick (about 220mb/s)

8 Likes
5

Shamir is a secret sharing mechanism. So not space efficiency (in fact, all shares are close to the original data size).

It is a similar algorithm, but AFAIK simpler and faster. (reed solomon from 60’s and rabin 90’s (late 80’s))

It is used on any data requested by a client, or it can be.

I hope we end up with 5 of 7 everywhere. 7 replicants, 7 elders etc. and have this ratio consistently used as it ties a lot together.

15 Likes
6

And it requires 5 of the 7 pieces to actually reconstruct the chunk?

So the client has to communicate with 7 Elders any time it wants a 1MB chunk? That seems inefficient. More importantly, it seems like there’s probably already a bad traffic analysis vulnerability, and IDA makes it even bigger.

Suppose I’m Eve and I want to find out whether Alice is downloading CookieRecipe.txt, which is a 256MB file because they’re complicated cookies. I have a certain number of observation points on the Internet.

As I understand it (and I could be wrong, because I’m just dabbling here), CookieRecipe.txt will be stored as 256 (plus a few?) independent chunks, and each of those chunks will be independently assigned to a section in the network. To reconstruct CookieRecipe.txt, Alice needs all of them or a large fraction of them. So Alice has to communicate with 256 or more different sections (via their Elders) to request all the chunks.

I, Eve, know which section has each chunk, because that’s public. If the network has grown large, the set of sections involved is likely unique to CookieRecipe.txt, so that choice of sections is a fingerprint for the file.

If my listening posts see Alice communicating, contemporaneously, with Elders in enough of the CookieRecipe.txt sections, probably a LOT less than 256, then I can say with high probability that Alice is fetching CookieRecipe.txt.

Whether I see enough communication to figure that out depends on how many of my listening points Alice’s communications with the Elders happen to pass. In all honesty, if I have a reasonable number of listening points, or if I’m listening close to where Alice is, then I’m probably going to see enough of Alice’s communication anyway… but if Alice has to talk to all 7 Elders in each section, then I have an even better chance. Instead of there being 256 potentially observable communication events, there are 1792.

2 Likes
7

Ah right I think I get it now. Is this closer to the IDA process?

IDA_understanding_4

6 Likes
8

Yes ( I had to switch off dark mode) I think you have it there.

Important switch here as Elders check requests verses responses but don’t tie them together. So an Adult not responding is noted over time. i.e. we ask for ABC[1] and ++requests and unless it responds we do not --requests. If he does not respond this counter increases and marks him dysfunctional.

So the client checks if he got the pieces and if not ask for the next adult to be queried.

This moves from fastest wins to closest ones should win. Therefore hopefully helps with the worries over faster nodes/ data centres winning.

Other mechanisms mean flooding elders with data and/or somehow sync their responses in a way all elders can be told of a bad adult.

8 Likes
9

:pray:t3: Anyone would think you’ve been thinking about this stuff for years. :joy:

Thanks for clarifying this @mav that diagram is great.

8 Likes