-
Notifications
You must be signed in to change notification settings - Fork 7
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Optimize archival Mutator Sets, with a focus on IO #127
Comments
@zkclay If you want to have a look at this, maybe have a look at this blogpost. If you understand the mechanics of Merkle Mountain Ranges (MMR) you are 80 % towards understanding mutator sets. A mutator set contains two lists:
Both of these lists are represented by MMRs, so the logic to update a mutator set is 80 % MMR logic and 20 % other stuff. If you don't quite understand the mechanics of MMRs, maybe this blogpost of mine can help. |
Alright, I'll take a look at this! Thanks for the resources! |
Hey @Sword-Smith I spent some time reading up on the Merkle Mountain Ranges and the Mutator Set docs that you wrote and taking a look at the code. The blogs posts are dense and I had to reread it a few times, but now I have a much better understanding of the two concepts now :) Thanks for the work you and the team has put into them! However, I’m still a bit unsure as to the optimization strategy we want to pursue here. In taking a look at the mutator set code, it seems like the MMR operations are well encapsulated in the Archival MMR abstraction, and the bulk of the code for the mutator set is concerned with managing the sliding window bloom filter. Are the optimizations we want to do here? I’m still a little hazy on the specifics of the SWBF logic and all the chunks we are manipulating, but I can look deeper into this, if it is the intended focus. I also noticed that there seems to be some functionality duplicated across the Mutator Set and Mutator Set Accumulator, is this what we want to look into? Or are you thinking of something else entirely? |
My motivation for this issue and #126 was to optimize the time that the node spends when updating its state with a new block. I looked into the archival-MMR and the archival-mutator set code and it didn't look optimal to me. I wrote the original implementation of all of the MMR code and the mutator set code, but multiple (beneficial) rewrites have occurred since then: all access to persistent storage has been made Notice that the accumulator versions store everything in RAM whereas the archival versions handle so much data, that they must live on disk, and they need to be persisted when the program shuts down. With #126 behind us, I'm happy with the performance of A stylistic property I don't like about the current On the top of my list of priorities for this issue, though, is that the archival version is fast. So you could start by adding a relevant benchmark and then measure whether your changes make the code run faster. Since the archival version stores everything to disk, I would imagine that optimizing IO will yield the biggest result. I hope this addresses some of your questions :) |
Here's an example of a speedup I just found: pub async fn prove(
&self,
item: Digest,
sender_randomness: Digest,
receiver_preimage: Digest,
) -> MsMembershipProof {
MutatorSetAccumulator::new(
&self.aocl.get_peaks().await,
self.aocl.count_leaves().await,
&self.swbf_inactive.get_peaks().await,
&self.swbf_active.clone(),
)
.prove(item, sender_randomness, receiver_preimage)
} And in the accumulator, pub fn prove(
&self,
item: Digest,
sender_randomness: Digest,
receiver_preimage: Digest,
) -> MsMembershipProof {
// compute commitment
let item_commitment = Hash::hash_pair(item, sender_randomness);
// simulate adding to commitment list
let auth_path_aocl = self.aocl.to_accumulator().append(item_commitment);
let target_chunks: ChunkDictionary = ChunkDictionary::default();
// return membership proof
MsMembershipProof {
sender_randomness: sender_randomness.to_owned(),
receiver_preimage: receiver_preimage.to_owned(),
auth_path_aocl,
target_chunks,
}
} So the only thing the |
@Sword-Smith ok, all this context is very helpful, I'll take another look. Thanks! |
Hey @Sword-Smith, I took another look at this, but unfortunately there's still a lot for me to wrap my head around here in this mutator set, and I've been making a lot slower progress than I'd like. I will also be pretty busy with some other commitments in the next week, so I want to give this issue up for someone else to work on, rather than hold the team and the roadmap back. also, as note, I did test cutting out the MutatorSetAccumulator and moving the implementation into the MutatorSet itself, and I didn't see any speedups, so I think that could be left in depending on your preferences for the codebase. |
No problem. Thanks for the commits you already contributed. Hope to see you back here at some point :) |
Depends on #126.
The text was updated successfully, but these errors were encountered: