TIP-911: Committing stakes with arrays optimized for SPV efficiency

[sadministrator]

TIP	911
Category	9xx (consensus-breaking)
Author	Marco Serrano (marco@themelio.org)

Summary

Currently, Themelio stakes at a particular height, State::stakes, are stored in a sparse Merkle tree implemented in novasmt that maps 256-bit transaction hashes to StakeDocs. The leaves of this tree are hashed together recursively and the root hash becomes the stakes hash stored in the header.

This TIP proposes changing the data structure over to a flat array whose contents get hashed once to become the stakes hash at any particular height.

Motivation

Due to the exorbitant gas cost of using non-native cryptographic primitives on Ethereum, we are trying to keep the number of Blake3 hashes and Ed25519 signature recoveries in the bridge smart contracts to a minimum.

Unfortunately, we require both hashing and signature recovery to verify the correctness of stakes and headers at any particular height so we must modify our State::stakes to something with better performance in this type of constrained environment.

Implementing the proposal will reduce the required hashes from 256 per StakeDoc for a sparse Merkle tree down to 1 hash. This hash will then become its header's stakes hash and will guarantee the integrity of the stakes at its height.

The exact structure of this new stakes hash preimage can additionally be optimized for the validation of Themelio headers by any SPV client, including the bridge contracts.

Proposed changes

After a certain "flag day" block height, the stakes_hash field of the header stops referring to the root hash of a 256-bit sparse Merkle tree, and instead becomes the hash of a byte array of concatenated, serialized StakeDocs.

To keep signature recovery to a minimum (in gas constrained, on-chain environments), the stakes array can:

• be prepended with the total number of staked syms in the current and upcoming epoch to allow header verification to be short-circuited once the minimum number of votes have been counted up
• be sorted by pubkey, with each group in turn sorted by total weight (the total syms staked by all StakeDocs associated with a particular public key). This allows each staker's votes to be tallied up with only one signature recovery and frontruns the array with the heaviest public keys

These two changes give us the minimum number of signature recoveries needed to verify any header, regardless of StakeDoc distribution.

Deployment

TBD

Alternatives

We could alternatively use a dense Merkle tree which would be a simpler change to the core protocol and would reduce the necessary hashes to log(n) per StakeDoc but this improvement is likely not enough to make this option feasible and could be susceptible to sybil DOS attacks by malicious stakers.