Skip to content

Instantly share code, notes, and snippets.

@richardkiss
Created August 23, 2022 20:00
Show Gist options
  • Save richardkiss/86f8ba4a04f4eb6b44234f014daa3d31 to your computer and use it in GitHub Desktop.
Save richardkiss/86f8ba4a04f4eb6b44234f014daa3d31 to your computer and use it in GitHub Desktop.
Block Compression: serialization with back-references

Block Generators

Block generators in Chia are clvm programs that, when run with particular arguments, produce a list of coin spends. This provides opportunity to do compression by recognizing patterns and encoding.

CLVM Serialization

The standard serialization mechanism of clvm is defined here.

If you review this specification, you'll see that deserialization begins by inspecting the first byte. If the byte is 0xff, the object is a pair. If the byte is 0x00 to 0xfb, the object is an atom whose length is partially or fully encoded by this first byte.

However, the initial bytes 0xfc through 0xfe do not correspond to anything (and in fact, even an encoding that begins with 0xfb is an atom too long to be practical). This means these bytes can be repurposed as extensions to serialization for compression purposes.

During deserialization, objects are read one at a time and place onto a stack. A second stack of operators is used to determine what happens next: either we read another object onto the stack, or we do a pop-cons-push operation, which pops the top two objects off the stack, puts them together into a cons, and pushes the cons onto the stack. Any clvm tree can be create with just these two operations.

Chia generators expand to structures that contain reveals of puzzles, which can often be quite large. Puzzles are generally constructed by taking one of just a few MOD generic puzzle cores and currying arguments (such as public keys) onto the generic puzzle, making it specific to a user. When expanding, we often see the same large MOD appear over and over again, such as the core for NFTs or CATs, each of which has over 1K of code. This becomes a clear target for compression.

Instead of blindingly serializing repeated clvm trees, at each step we look to see if the next clvm sub-tree to be serialized has been encountered already. If it has, that means it's already in the stack of partial clvm objects. This also means, if you consider the stack to be a clvm object (and there's an obvious way to do so where a push is a cons c and a pop is a f/r), you can find a clvm path to that object.

We define 0xfe to mean "read the next clvm subtree, which must be an atom, and treat it like a path into the clvm object stack. Push that exact object onto the clvm object stack".

It's clear that kind of decompression can be very inexpensive. We can also easily implement it in chialisp, and have done so here.

With this technique, references to MOD cores, which can be over 1k, can be compressed into just a few bytes, so larger blocks compress even better. Eventually generator size costs becomes overwhelmed by puzzle execution costs and CREATE_COIN costs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment