Block n's MMR delta corresponds to block n-1's chain root

[igamigo]

(Related to 0xPolygonMiden/miden-base#305)

In the client, we make requests to the sync state endpoint in order to retrieve newer blocks and apply changes to the local partial MMR.

It currently looks like incoming block data from the node follows this pattern: Block $n$'s MMR delta corresponds to block $n-1$'s chain root. As a consequence of this, any time we try to execute a transaction the prologue's check will fail because we provide block $n$'s chain root but the latest MMR peaks will only ever match block $n-1$'s chain root.

Here's an example when doing a state sync on 2 subsequent blocks from the client:

syncing block 1665
incoming block header's chain root 0xe422301a35bc197ba3c3b55d36241ceb68e78915983abee3b50f72afd53b6bf0
applying mmr delta
new peaks root hash 0x6abe8aa347394437177d33b6ffc9b37021befc5dc8e7d858026f4d634a991376
state synced to block 1665

...

syncing block 1666
incoming block header's chain root 0xbfc10f5d80736376a3cf6fc803ae36df26b317eebb5aa2c186d712cfc849b648
applying mmr delta
new peaks root hash 0xe422301a35bc197ba3c3b55d36241ceb68e78915983abee3b50f72afd53b6bf0
state synced to block 1666

[hackaugusto]

That is the correct behavior. The block needs to be created so that the MMR can be updated, meaning when the block is produced only the MMR of the previous block is available. Having the latest MMR in the block header would mean the structures are self referential (which doesn't work because of hashing).

related issue: #114

[bobbinth]

I think there is something off in the interplay between:

1. How MMR delta is being generated on the node.
2. How MMR delta is being applied on the client.

According to the snippet pasted by @igamigo - the MMR is kind of running 1 block behind where it should be (i.e., at block 1666 we get MMR root that we should have gotten at block 1665).

[bobbinth]

It seems like the issue is that chain_root for blocks is not set correctly for any block after the genesis block. This could be an issue in:

1. How we handle genesis block in the block producer.
2. How the MASM MMR code adds a node to an empty MMR.

Investigating...

[igamigo]

So I believe the issue could be tracked to this line.

When starting the node, the genesis block is first loaded to the DB (if not present from before) and after that, all corresponding worker threads are spawned. When the thread that handles the state is loaded, it initializes the state Mmr with DB data which means on startup the chain root of the state Mmr will have the genesis block. When it's time to build block number 1, get_block_inputs() returns as part of its response both the current Mmr peaks and the previous block, which is still the genesis block. The BlockWitness then takes this input and proves/computes the next chain root from an Mmr which now includes the genesis block header's twice.
I think I'm forgetting a couple of details from my investigation but it's a bit late and will review this tomorrow with time.

I drafted a PR (#134) mainly to test consistency with the client and it seems to work fine with those changes. This approach however causes state sync to fail when the only block in the chain is the genesis block. It's also a change that likely reaches some other parts of the protocol with which I am not familiar. I could have some wrong assumptions with this but talking to @bobbinth it seems that in general, for block N we want the Mmr to contain a forest of N-1, which was not what was happening anyway.

[bobbinth]

Great find! Indeed the error was in the store. I've addressed it slightly differently in #135 - I think it solves the problem in a slightly simpler way.