Data compression

[orivej]

Consider the following design space: some nodes on the network are used for storage, they store and serve compressed data to optimize network throughput and storage efficiency; other nodes are used for computation with the data and they are space constrained (e.g. they must minimize SSD usage), so they store only uncompressed files, but as long as their data is unmodified, they can also seed it to nearby nodes.
To support both compressed and uncompressed seeders, or to present compressed data to applications as being uncompressed, or to store and serve already seeded uncompressed data in a compressed form, it seems worthwhile to support data compression below application level, in IPFS. This suggests support for storage and transmission of IPFSObjects with an additional field specifying the method of decompression, whose hash is computed as if the data was not compressed and the field was not present.
In a way, this resembles squashfs, which deflates data and then presents it as a normal read-only filesystem.
Another option is to introduce a separate IPFSCompressedObject, advertise it both under its own and uncompressed hashes, and when another node requests it under uncompressed hash, negotiate either to serve the compressed object, or to decompress it prior to transmission.
What do you think about this problem? Can the solution be simplified?

[jbenet]

@orivej yes, these thoughts are on the right track. I'll expand more on this in the next couple weeks-- but consider also program as compression. imagine a simple language embedded in the data segment of an object. let the "final data" of an object be the output of running the (pure) program embedded in the data segment. (e.g. in a unixfs file, the output is concatenating the data segments of all children in-order). This allows us to represent final objects as programs, perhaps getting us closer to the kolmogorov complexity of the data.

[ion1]

Given an object with links to other objects and a representation of a program that uses those objects as input and whose output is the data the object represents, we could also do other neat things.

We could have normalizers for various data formats (see https://wiki.debian.org/ReproducibleBuilds/ExperimentalToolchain#strip-nondeterminism) which also output a program that takes byte ranges from the normalized version, applies possible transformations (decompression, binary diff etc.) to them and concatenates the results to recreate the original file (see https://joeyh.name/code/pristine-tar/).

For example, when user A and user B add a PNG image with the same pixels but the headers in a different order, both users would end up with the same large object for a normalized version of the image and different small objects transforming the normalized version back to what they added.

The language for the program must be pure (no nondeterminism or arbitrary IO) and strongly normalizing (no arbitrary recursion, no halting problem) and it must have static guarantees about memory consumption etc. for it to be safe.

[jbenet]

Yep! see also

• LLVM IR LLVM IR  #59
• things like stackstream:
  • streaming byte-string Stack-based Assembly draft #6
  • https://github.com/BrendanBenshoof/StackStream
  • Stackstream possibilities #25
• IPLD: https://github.com/ipfs/go-ipld/ and https://github.com/diasdavid/node-ipld
• ipfs tar
• and i talk about this in this talk https://youtu.be/h73bd9b5pPA?t=4689 ~ 1:18:00-1:27:00

[davidar]

@ion1 👍

Given an object with links to other objects and a representation of a program that uses those objects as input and whose output is the data the object represents, we could also do other neat things.

The language for the program must be pure (no nondeterminism or arbitrary IO) and strongly normalizing (no arbitrary recursion, no halting problem) and it must have static guarantees about memory consumption etc. for it to be safe.

@Gabriel439 could Morte/Annah be used for this?

and i talk about this in this talk https://youtu.be/h73bd9b5pPA?t=4689 ~ 1:18:00-1:27:00

@jbenet I like the way you think :)

[ion1]

@jbenet

and i talk about this in this talk https://youtu.be/h73bd9b5pPA?t=4689 ~ 1:18:00-1:27:00

Very nice, but I don't think we can make it quite Turing complete. As long as the language has a construct for arbitrary recursion, someone can give me an object with an arbitrary hash and I'll wait up to the heat death of the universe trying to check whether its output matches the hash.

However, a program in such Turing-incomplete language can always output a program in an arbitrary language. As long as I can safely “ipfs get” an object outputting an unsafe program, I can choose to execute the unsafe program and have it launch the missiles in a non-halting loop.

[davidar]

@ion1 Morte guarantees termination by disallowing recursion, but provides some tricks for translating recursive programs into non-recursive ones so that it's not too much of a limitation in practice.

Of course, you could also just place a hard time limit on executing computable objects.

[ion1]

I would really like the property that having downloaded a block and its dependencies, I am guaranteed to get the data out.

[cryptix]

As long as the language has a construct for arbitrary recursion, someone can give me an object with an arbitrary hash ...

Maybe I'm missing something but a valid IPFS object should have no cycles. An all links first-fetcher should see that miss-match quickly and error out.

[ion1]

Given an object that promises to generate the data for the hash Qmaaaaaaaaaa… programmatically, how can you tell you got the correct object without running the program?

[Gabriella439]

Yes, this is the use case for morte and annah, providing a high quality intermediate language for distributing and storing code fragments:

• morte provides the strongly normalizing core language that is 100% pure with no ways to cheat/coerce/subvert the type system
• annah translates recursive data types to non-recursive equivalents encoded in morte

morte is basically production ready. annah is still very experimental. The desugaring of recursive types is complete but decisions like how to encode strings and numbers are still in flux so it's not really ready for prime time just yet.

Using annah is not strictly necessary, it's purely syntactic sugar for morte code; I can step you through how to encode all your relevant datatypes and functions by hand without annah for your specific use case if you can explain exactly what you want the code to be able to do.

Relevant resources:

• Morte: an intermediate language for super-optimizing functional programs - Overview of morte
• The internet of code - Post that describes Morte's built-in support for securely distributing typed code fragments
• Secure execution of untrusted scripts - Talk about Morte's security model
• morte package on Hackage

[ion1]

👍

Have you thought about a binary representation for Morte code?

[Gabriella439]

Yes. Right now the binary representation is pretty naive, and there is a lot of room for compressing it further (by using bit-level encodings and symbol tables).

You can also compress things further by baking in the types of external primitives into the context that you use to type check your expressions.

[ion1]

I don’t know how familiar you are with IPFS, but it would make a great fit since IPFS represents everything as a distributed content-addressed DAG where objects can have links to other objects (by their hash) as well as a data payload. A Morte program in an IPFS object could list its direct dependencies as links and IPFS would handle getting all the transitive dependencies for you. You can not even construct a cycle.

[jbenet]

@ion1

Very nice, but I don't think we can make it quite Turing complete. As long as the language has a construct for arbitrary recursion, someone can give me an object with an arbitrary hash and I'll wait up to the heat death of the universe trying to check whether its output matches the hash.

Hence bounded computation. turns out there's very good heuristics for this. javascript is turing complete and unbounded computation there is not really a problem.

Given an object that promises to generate the data for the hash Qmaaaaaaaaaa… programmatically, how can you tell you got the correct object without running the program?

no, the program's hash would be Qmaaaaaaaaaa.... the data representation would be a different hash.

---

@Gabriel439 this is great, thanks for the links. will look deeper this weekend. i think there's a great marriage for ideas here that we should explore. and we still have some flexibility to fit better models. (thanks @davidar for bringing it up!)

[Gabriella439]

Yeah, I actually built Morte in such a way that you can swap out Morte's default dependency resolver with your own. Morte's default resolver also has a similar no-cycles restriction.

However, I highly suspect that the compressibility of Morte expressions will make or break its suitability for this purpose because right now the data type encodings have very high constant factors over more specialized encodings. I'm going to try running some basic compression algorithms over the serialized expressions and if that does not work then I will try more specialized encodings. In the worst case scenario I could just fork the core language for IPFS to provide built-in support for efficient data types.