Reasearchy projects

[adiabat]

With at least one UROP joining, and hopefully others, here's a thread for research projects / ideas.

These are things that would improve utreexo, but that we're not quite sure about. And maybe they could be written up for academia points as well.

I'll put topics in separate replies here, just to try out the "discussions" feature.

[adiabat]

Multi-threading

Computers have a bunch of CPUs now. Even raspberry pis. I have a bunch of crummy old computers, some more than 10 years old, but none of them are single core. Also this code is in go, which is supposed to be good at multi-core stuff. So we should make things multi-core, right?

However, in #225, we made the accumulator pretty much completely single threaded, and that made it faster. This was likely due to a bad implementation, making way too many goroutines. It feels like there should be a way to make the accumulator multi-threaded and faster. This also doesn't seem like it should be too hard, so that's something that might make an interesting project.

[adiabat]

Sparse On-Disk Proofs

Right now the bridge node creates a batch proof for every block, and keeps it stored on disk in a flat file. This is pretty fast: when a client requests a block, the server reads the whole thing off disk and sends that data straight to the network without even looking at it.

The problem is the proofs are take up a lot of space, more than the actual blocks. (Something like 450GB on top of 380GB of block data)

There are likely ways to reduce on-disk storage by keeping full proofs for some "key" blocks, and for other subsequent blocks only keeping partial proofs or "diff" proofs building off the key state. Ideally this would cut down on space without too much extra CPU or DoS risk.

Another way to think about this: require that clients have a minimum TTL lookahead, and save proof blocks with that TTL. If the client doesn't need to download part of the proof, there's no need for the server to store it.

[adiabat]

Sparse proofs with no server CPU work

Expanding on the idea of sparse saved proofs

The idea of a "minimum TTL lookahead" has the issue that clients would never be able to clear out to only the tree roots, which is something we want to do. Having the server re-caclulate full proofs on the fly from a previous block's state & proof along with later blocks seems too CPU intense and abusable. What instead we can do is aggregate on a larger interval.

Block download is sequential, and usually clients will request a sequence of blocks from the same server, eg "give me block 50 through 59". Clients usually send a "getdata" message with a bunch of blocks requested, and the "block" messages come back in order. You could request different blocks from different servers but there doesn't seem to be much use there; if you're doing IBD it's not really a secret, and even if you said "hey give me blocks 53, 57, 61, 62, 68, 69, 70" the server could still tell that, OK, this client is doing IBD and is around block 53 but is probably randomly asking other servers for blocks. You can do that now, but it doesn't seem that useful, and so it seems fine to lose that capability.

We can then have minimum batches for block requests. The smallest relevant would be 2, so we'll use that as an example. Clients can request even blocks, but not odd blocks. When they request an even block, they get the block they requested, and the block after that. So request block 46, get [46, 47].

On disk, the server has the full proof for block 46. Every spent leaf al the way up to the root (or intersection with another branch). But for block 47, the server only stores a some of the proof: the server assumes that the client doesn't forget anything between block 46 and 47. So if leaves are added in block 46 and then removed in block 47, those leaves don't have proofs at all. If there is a hash that's used in a proof in block 46, and then used again in a proof in block 47, it doesn't need to be sent.

The nice thing about this is that the server needs to build the proofs this way, which has some complexity, but once the proofs are built, they're easy to serve. The server can still grab data off the disk and send it directly to the network interface, without doing any logic on them, and only the client does deserialization.

Clearly increasing the number of blocks that get grouped together will decrease the size of the whole proof set. So you could do 10 block ranges, or 16, or maybe more. If you go too high, it can be a problem as it's one "message" and needs to fit in ram all at once for the client.

It also seems that it can easily be a parameter for the server, so servers could have different grouping numbers that they advertise somehow on first connection. So most servers could have groupings of 8 blocks, but occasional servers would go down to 2 or even 1 (which is equivalent to what we have now) for clients that have limited ram or poor network connections where they'd like to download things in smaller chunks.

[adiabat]

Clairvoyant memorable leaves

Currently the server have TTL values for each leaf, indicating how long (in blocks) a leaf will stay in the accumulator before being removed. The lookahead mechanism is helpful in reducing proof sizes by keeping only soon-to-be-removed leaves in memory, but it's definitely not optimal. For example, what if a client were using a 10 block lookahead, and there were a block where every output has a TTL of 11, then 10 empty blocks. The client would remember nothing, and require a proof for everything, with it's accumulator RAM cache completely empty for the entire duration.

Since the entire schedule of insertions and deletions is known ahead of time, we can use a clairvoyant caching strategy to get optimal caching of leaves.

Some notes: I tried this a while ago and it seemed to only have a 1 or 2% improvement in proof sizes. I think I just did it wrong though, and it's kind of bugged me since. It's gotta do a better job than lookahead, right?

Also, if you want to get really fancy, this would only be optimal in terms of number of leaves cached; it doesn't know anything about adjacency of leaves, which is very important for proof sizes. It seems like that's also something that could be taken into account and optimized even further.

[adiabat]

Leaf clustering

Utreexo inserts leaves into the accumulator once a block, and we do it as a batch of every TXO created in that block. Even though we're inserting many leaves at once, the order still matters (insertion is not commutative).

The insertion ordering we use right now is just the block's ordering. So the coinbase outputs will be on the left, and block's last txo will be on the right. Miners usually order transactions within a block by fee rate, which doesn't have much to do with spending patterns. We could shuffle TXOs around any way we'd like, based on heuristics or TTL data, to get smaller proofs.

The tricky part shuffling the insertions changes all subsequent proofs, so it must be deterministic and causal so that everyone can do it the same way. This complicated TTL based insertion clustering because we can't update it as new information becomes available without rebuilding proofs. There are a bunch of ways to potentially deal with this but they all seem a bit tricky. Also the encoding of the insertion permutation will take up some space as well (though not too much, and probably much less than the proof size savings).

Overall it seems tricky / complex, but feels like it might result in much smaller proofs.

[adiabat]

More on leaf clustering

The general idea of giving IBD clients TTL-based hints as to how to order their inserted leaves seems good, but the problem is that this changes the proofs / roots, and we keep learning how to make better insertion schedules as time goes on, but can't update the old schedules without breaking everything.

This might not be as big a problem as it seems. If we're OK with pushing a little bit of "assumevalid" style hard-coded hashes into the binary, updating the schedules looks doable. In fact, this usage of hard-coded hashes involves much less trust than assumevalid, as everything still gets checked, and the hard-coded hashes are only there to optimize proof download.

The way to do it is to have multiple forest orderings. There's the canonical / main / default / straight-through ordering, where every leaf is inserted in the order it shows up in the blocks, and deletions happen deterministically based only on the deletions. This is what we have now.

Then there's also optimized forest orderings, which have the exact same set of leaves as the straight-through forest, but in different positions so with different roots. These forests are incompatible; the proofs for one won't work on the other. Instead what happens is that IBDing nodes start out on an optimized forest, then switch to straight-through once they've finished most of the IBD.

Example: Current block height is 100K. Server builds proofs / TTLs as today, call it forest st. Then server goes back and says, I'm going to make an optimized insertion schedule, call it forest o1. Then it has the full forest for both st and o1. It calculates the swaps needed to get from o1 to st. That's gonna be a lot of swaps, like a few million, so that's maybe a few megabytes of data of swaps, and might be hard to figure out the best way to swap from o1 to st, but it'd probably not that bad.

(Are there like set permutation encoding schemes? Permutation compression? Sounds like something that very well may be the subject of many CS papers that I've never heard about!)

The developers of utreexo software then hard-code the hash of this o1->st transition permutation into the client binary. Client fires up, connects to server, builds through o1. Then gets to height 100K. By now the block height is up to 101K. The server sends the transition permutation to the client, which checks against its built-in hash, and then performs the permutation to the st forest roots. Then it goes along with the last 1K blocks of IBD in non-optimized, st forest.

Once the chain gets up to 150K or so, the server has new TTL data, and rebuilds an insertion schedule for forest o2. I don't think you need any transition from o1 -> o2, or o2 -> o1; make them infrequent, where new schedules come out alongside new software releases. Probably takes a few hours for a fast server to come up with a new insertion schedule and permutation to get to st.

This seems like a decent way to do it; the client binary has hard-coded hashes of the permutation to get to straight-through, and maybe some hashes for the proofs and stuff along the way so they don't waste too much time downloading from a malicious server. Once they've done their optimized IBD, they're back to straight-through with everyone else. Every few months a new optimized insertion schedule is added so that IBDing clients can stay optimized until pretty close to the end.

I think this makes looking at the proof size / speed benefits of insertion schedules much more worth it. The downsides will be: how big are the per block permutations, and how big is the final transition permutation. Worst case, per block it's like 5000 uint32s, so 20KB. And worst case final permutation is ~300MB. In practice they're hopefully less. If the proof size savings outweigh the size of the permutations it could be worth it.

Good and bad: there are a lot of degrees of freedom here. You can also optimize the o1 forest to minimize the size of the permutation to bring it up to st. Obviously the extreme is just to have no permutations at all the whole time, then there's no permutation needed to get back to st at the end. But maybe you gradually do different permutations along the way so that once you get up to the end of the schedule, you're right back to st without any final permutation. That would only be possible if the swaps could access anywhere in the forest each block, but... to some extent, yeah why not? The server could just give clients a proof for something that's not being deleted, and say, "hey swap this with this over here" and they just do it. There's really not much in terms of limitations on what the server can tell the client to do, as long as additions and deletions come from the blocks, and you get to the straight-through forest at the end.

Seems like it could help but also pretty complicated, so can stick to what we have for now, but an interesting research topic!

[adiabat]

Going further with the idea of different optimized forests-

While changing the insertion ordering and then shuffling back to normal at the end could reduce proof sizes and potentially speed things up, it's not super obvious how to change the insertion ordering to minimize total network traffic; you need to balance proof sizes with the size of the permutations and extra proofs needed to perform non-deletion swaps.

Using the [optimized for IBD forest] -> permutation -> [back to normal forest] model, there seems to be a more straightforward variant to try: a cache optimized forest. Right now with TTL / memorable values, the server can tell the client: "Remember these leaves, forget about these others". So we switch that to "Remember these leaves and don't bother putting them in the accumulator. The others, insert then forget".

The leaves to be omitted from the accumulator can be the same ones we're currently saying to cache in pollard. TTL lookahead works, and clairvoyant caching should work better. In fact clairvoyant caching is better suited to accumulator omission, as every UTXO in cache is the same size, but branches to leaves in the pollard can have variable size that we don't account for with clairvoyant schedule generation.

So the idea is that clients IBD with a modified accumulator which doesn't have short-lived leaves, and then once they're near the tip, the server tells them to shuffle their leaves to get to the same ordering as normal / straight-through. My guess is that this permutation won't be too big, as the accumulator design already tries to keep new stuff on the bottom right.

My guess is that the proof sizes will be about the same as well; we don't prove the cached leaves now. But we do insert them into the accumulator, which requires log(n)/2 hashes for each insertion. And then some swapping around and re-hashing when they're removed. So accumulator omission doesn't seem like it will reduce network traffic much, but it probably helps reduce the CPU load on the IBDing client considerably.

Clients could use a hash map to store the short-lived UTXOs, or we could do something even fancier, where the clients have fixed arrays and the servers do all the compaction / defrag stuff for them since they've already computed the schedule.

Basically you want the server to do all the work, and make it as easy as possible for the client. If an hour of CPU time saves the IBDing client 5 seconds, that's still worth it; as long as servers can send each other the schedules and results of that hour of processing, every server can get it once a single one computes it, and then every client can benefit from it.

This seems not as hard to implement as the clustering optimized forest, and could speed things up enough to be worthwhile. Of course it might also not do much of anything as we're already omitting those proofs. Worth looking into though.

[kcalvinalvin]

I guess in general I'm in favor of the o1 -> permutation but I still think we should look at leaf clustering with forest.

Forest sync on mainnet is still a pain/requires a ton of ram to do it fast. Maybe there is a way to cache the forest leaves better but as seen with the scatter plots, leaves left of the forest is accessed quite a bit, making it hard to cache effectively.

I'm thinking maybe if you have a beefy computer, one day to sync mainnet is a good target to aim for.