search

MinaProtocol / mina

Mina is a cryptocurrency protocol with a constant size blockchain, improving scaling while maintaining decentralization and security.
https://minaprotocol.com
Apache License 2.0
2k stars 529 forks source link

Implement Transaction_snark_scan_state.target_merkle_root in O(1) #3733

Open nholland94 opened 5 years ago

nholland94 commented 5 years ago

The Transaction_snark_scan_state.target_merkle_root function was added in https://github.com/CodaProtocol/coda/pull/3439 to be used in the Sync_ledger code, but the implementation is not efficient. It's possible (and not very difficult) to implement this function in O(1) by making some changes to the data stored by the scan state (namely, by keeping track of the final target the scan state will reach). It's important to do this as answering Sync_ledger queries should be fast.

nholland94 commented 5 years ago

I was able to mitigate this by making an adjustment to the information captured by the Root_history transition frontier extension to make the target of the scan state available there instead. As such, this issue is not very important right now -- would be nice to have and shouldn't be too bad, but we no longer have an immediate need for it.