Light clients/tx inclusion: ADH removal next steps

[Tamgros]

Context

Some teams use the ADH for inclusion proofs. This is not without issue. ADH does not include accounts with 0 lamports, so it can’t distinguish between an account being deleted vs never existing at all.

ADH also has pretty serious performance considerations, so it’s being removed.

Accounts Delta hash (ADH) will be feature gated and removed in this PR
anza-xyz/agave#4826

Problem

While, imperfect, some teams are still using ADH for their projects. We want teams to have a smooth transition. More importantly, we want a longer term solution. That solution could be multiple solutions to multiple cases, but we need more specificity from the projects on their needs.

Solution (near term)

The above PR checks if the feature is active that removes it. If it the feature is active, then it won’t calculate the ADH

        let delta_hash_info = (!self
            .feature_set
            .is_active(&feature_set::remove_accounts_delta_hash::id()))
        .then(|| {
            measure_us!({
                self.rc
                    .accounts
                    .accounts_db
                    .calculate_accounts_delta_hash_internal(
                        slot,
                        None,
                        self.skipped_rewrites.lock().unwrap().clone(),
                    )
            })

A validator could simply set this to always true

        let delta_hash_info = (true)
        .then(|| {
            measure_us!({
                self.rc
                    .accounts
                    .accounts_db
                    .calculate_accounts_delta_hash_internal(
                        slot,
                        None,
                        self.skipped_rewrites.lock().unwrap().clone(),
                    )
            })

This can be done in multiple ways when building from source.

Then a project could use the delta_hash_info as they wish. The ADH isn't returned in an RPC method today, so this doesn't change the current flow to verify inclusion as I understand it. Feedback welcomed

Solution (longer term)

This is where we are sourcing community feedback. Validators have ways of attesting to their votes and states, it doesn’t have to be the hash that the protocol itself passes around as long as it’s provable

There are also many other proposals of various levels of bakedness
https://x.com/aeyakovenko/status/1909975977331241013

[preston-evans98]

@Tamgros I think I'm missing some context here, but I'm not quite sure how this will work.

If the ADH isn't committed in the bank hash anymore then it's no longer usable for light clients. (The trick that light clients are using today is to verify an account against ADH, verify ADH against the bank hash, and then verify the bank hash against votes). If ADH is committed in the bankhash, then all (or almost all) voting validators need to recompute it in order to vote, so there won't be much performance benefit.

Are you able to elaborate?

[buffalojoec]

Some extremely nice node operators would have to pay to land these roots on chain. 😄

[fikunmi-ap]

How would that work @buffalojoec

[aeyakovenko]

This is what I would do

1. Write a program for the accumulator
2. Use a stake weighted oracle for the accumulator account
3. Once it’s stable make it a syscall and have the runtime hash that account into the bankhash.

There is state contention on updating the account so the interface should product always require taking a write lock to that account.

[grosu]

Thanks for starting this discussion, @Tamgros , this is very useful! Founder and CEO of pi2.network here (also PL prof at UIUC).

We are developing a Verifiable Settlement Layer (VSL) at \pi^2, which will basically allow L1s, L2s, and any applications (eg CEXes or AI agents) to settle claims which are provably true. They decide what counts as a "proof" for their claims. The VSL decentralized network only verifies those proofs and then settles the claims. We'd like to integrate Solana asap! That means, in particular, that each transaction/block on Solana becomes a VSL claim. The value prop for Solana ecosystem goes beyond other L1s, L2s, or apps being able to check membership/inclusion, in that it is also bi-directional: a SC on Solana will allow for checking any other VSL claims. Jointly with the Wormhole team, we used this idea to demonstrate an alternative to guardians.

It will be something like this initially, but for Solana instead of Ethereum: https://ethereum.mirroring.pi2.network/. Note that the size of each claim is pretty small, yet each claim can be checked completely independently and in parallel with any other claims, because it includes the state footprint (called "witness" in Ethereum, basically the sub-state including only the delta on the big state). The ADH proofs seem to be way to go for us. We'd like to read more about it, and ideally be able to use it as is, without re-implementing our own state footprinting.

You said that ADH is slow, but how slow? Maybe it is good enough for us, considering that we do the work post-mortem.

Will have our \pi^2 technical folks add more substance here soon, but in the meanwhile, anything you can recommend us to look into highly appreciated!

[damienen]

@grosu I am fearful that ADH isn't good enough to provide the verifiability of history Pi Squared (and Solana) needs if it can’t distinguish between an account being deleted and never existing at all (as per @Tamgros)

[Tamgros]

@grosu I am fearful that ADH isn't good enough to provide the verifiability of history Pi Squared (and Solana) needs if it can’t distinguish between an account being deleted and never existing at all (as per @Tamgros)

Correct. It won't give specificity to a state being deleted or never existing

And by "slow", we mean slow to compute. It slows down the cluster itself.

[damienen]

Initial thoughts

Since starting to look into this issue we have tried looking at multiple different possibilities to provide some type of verifiability to Solana historic data.

Our first instinct was take a semantics-first approach where we take the ledger at the beginning of the block and re-execute said block using the formal definition of SVM then check if the result is included in the current ledger of Solana, but this quickly proved to be impossible without having a Merkle Tree readily available to check inclusion. As @Tamgros the ADH is slow and is also being phased out.

Possible ALH based solution

If we are to use SIMD-223 & SIMD-215 (ALH) and our semantics-first approach, we might be able to offer verifiable historical data. Let's note down the state of the chain at block B with S. If we have a valid S and assume that is where the chain verification starts from (hardcoded checkpoint/snapshot), we can mathematically prove using formal semantics that the execution of block B on state S results in state S+1. The computation can be simplified by knowing the account list and thus knowing what exact accounts need to be loaded into the ledger.

If we have this starting point, using mathematical induction we would be able to show that executing some n blocks one can get from state S to state S+n. This would need to be computed only once and then future inductions can stop there. Now as long as the proof is available it can be checked or even recomputed by anyone not trusting it. A drawback of that is that it can be expensive depending on how much you want to recompute. An advantage of this is that it works around ALH's lack of inclusion proofs.

Of course, this is still very incipient so I'm hoping we can find the (probably imminent) issues and see if it can be feasible.

Possible ADH based solution

A solution based on ADH, which is what we initially thought about, would mean creating a Merkle Tree (or some other verifiable data structure) ourselves. It doesn't even need to be ADH, it can be any type of hash that is able to provide us with some type of inclusion proof.

Would this approach make sense even if it is slow? (especially if we consider we can highly parallelize based on our claim architecture)

[yzhang90]

Let me summarize what we want to build on Solana and I hope that you can throw more light on the problem:

• Stateless verification for each block. The idea is that a beefy node creates "witnesses" - the minimal set of data that prove the values of the state that are being accessed by the transactions in a block. Then the witness can be used to create a partial state in a verifiable way and replay the block on another machine for verification. I think ADH is a perfect fit for the witnesses, but it was removed in the recent updates.
• Light clients and state proof. The idea is to build on-chain light client for Solana and other blockchains can use state proof to query the Solana state. As far as I know, the ALH is an incremental algorithm to compute the hash of all accounts but it doesn't provide any mechanism to generate state proof. There are some research/prototype to enable the state proof for Solana(e.g., Composable finance and Sovereign labs ), but they are no longer valid after ADH is removed.

@aeyakovenko you mentioned a solution based on accumulator. Is it already implemented? Where can we find more detail about it?

[DavidM-D]

Is the ADH removal going to come before or after the introduction of BLS signatures in the Alpenglow update?

If so this is super easy to deal with, if not I'm going to have to spin up 60 mithril validators.

[Tamgros]

the

Before. I don't know if BLS is officially on the schedule, but ADH is being removed in a feature activation in 2.2