We can store logs and notifications in TransactionState and store the TransactionState in a NativeContract.

I think Stack is also needed and we can probably drop Transaction itself, it can be stored the way it is now (separately from Storage). Other than that, yeah, it works fine too.

What some projects do is to create an auxiliary data structure such as MPT/SPT for the notifications/applications logs, then, similar as MPT for state we just store certificates.

I think this is exactly where we can do better by leveraging native contracts and unifying it all under single MPT.

But why do we need notifications any more? Why not just store the transfer history in the NEP-5 contract's storage?

At the very minimum transfer is not the only type of notifications. Contract's A backend could react to contract's B notifications and do some A invocations. It's be nice for A then to have an ability to get B's notifications directly from the chain.

You can get the notifications in the same transaction. But you can't get the historical notifications.

I know. And I think it's worth fixing that, because there can be situations when doing it all in one transaction is just not possible. It's a scenario when some contract is doing something for its users (generating events along the way), but another contract (that has no direct relation to the first one) wants to do something related to things happening in the first contract. Or, more generally, when some reaction is needed to an independent event and there has to be some reliable proof for this event. This proposed contract can be trusted to provide that and bridge two contracts in question.

And it might also be useful for cross-chain bridging, as notifications will end up in the MPT you can always get a proof for them for outside use.

If you store the notifications in the native contract, someone must pay for the storage. Since they have to pay the same fees, why not store them directly in the NEP-5 contract? The function of Notification is to provide a message delivery mechanism at a lower price than storage. Since the price is lower, there will naturally be more restrictions.

The fee is paid for the syscall and it can adjusted if needed. But the difference between regular contract storage and proposed native contract is at least in honoring MaxTraceableBlocks for the duration of time when this data is available which exactly is a restriction that can justify lower price. After MaxTraceableBlocks this native contract will delete transaction's execution log from the storage (as transaction can also be deleted now).

Maybe we can store the state root of application logs in storage, when contract want to use it, user can proivde the notification and proof path by off-chain.

That's an interesting idea. I still would prefer having this data available directly from the ledger, but at the same time this can be a solution too.

This one also is still relevant, we don't capture transaction side-effects properly at the moment and we don't provide any solution to reaction is needed to an independent event and there has to be some reliable proof for this event case. If we don't care enough about these use-cases, at least I'd expect to see it written as resolution for this issue.

Should we store the entire notification without being able to read it through the smart contract?
This will resolve the storage price bypass (mentioned by @erikzhang) and the state notifications status issue, and might also allow us to read the notification in the future.

The problem is that the smart contract can already access to TransactionState, so we can't store it there.

NeoGo always stores them (but it has a quite different storage scheme overall).