packages/contracts-core/contracts/libs/memory/Snapshot.sol
// SPDX-License-Identifier: MIT
pragma solidity 0.8.17;
import {State, StateLib} from "./State.sol";
import {MemView, MemViewLib} from "./MemView.sol";
import {SNAPSHOT_MAX_STATES, SNAPSHOT_VALID_SALT, SNAPSHOT_TREE_HEIGHT, STATE_LENGTH} from "../Constants.sol";
import {IncorrectStatesAmount, IndexOutOfRange, UnformattedSnapshot} from "../Errors.sol";
import {MerkleMath} from "../merkle/MerkleMath.sol";
import {GasDataLib, ChainGas} from "../stack/GasData.sol";
/// Snapshot is a memory view over a formatted snapshot payload: a list of states.
type Snapshot is uint256;
using SnapshotLib for Snapshot global;
/// # Snapshot
/// Snapshot structure represents the state of multiple Origin contracts deployed on multiple chains.
/// In short, snapshot is a list of "State" structs. See State.sol for details about the "State" structs.
///
/// ## Snapshot usage
/// - Both Guards and Notaries are supposed to form snapshots and sign `snapshot.hash()` to verify its validity.
/// - Each Guard should be monitoring a set of Origin contracts chosen as they see fit.
/// - They are expected to form snapshots with Origin states for this set of chains,
/// sign and submit them to Summit contract.
/// - Notaries are expected to monitor the Summit contract for new snapshots submitted by the Guards.
/// - They should be forming their own snapshots using states from snapshots of any of the Guards.
/// - The states for the Notary snapshots don't have to come from the same Guard snapshot,
/// or don't even have to be submitted by the same Guard.
/// - With their signature, Notary effectively "notarizes" the work that some Guards have done in Summit contract.
/// - Notary signature on a snapshot doesn't only verify the validity of the Origins, but also serves as
/// a proof of liveliness for Guards monitoring these Origins.
///
/// ## Snapshot validity
/// - Snapshot is considered "valid" in Origin, if every state referring to that Origin is valid there.
/// - Snapshot is considered "globally valid", if it is "valid" in every Origin contract.
///
/// # Snapshot memory layout
///
/// | Position | Field | Type | Bytes | Description |
/// | ---------- | ----------- | ----- | ----- | ---------------------------- |
/// | [000..050) | states[0] | bytes | 50 | Origin State with index==0 |
/// | [050..100) | states[1] | bytes | 50 | Origin State with index==1 |
/// | ... | ... | ... | 50 | ... |
/// | [AAA..BBB) | states[N-1] | bytes | 50 | Origin State with index==N-1 |
///
/// @dev Snapshot could be signed by both Guards and Notaries and submitted to `Summit` in order to produce Attestations
/// that could be used in ExecutionHub for proving the messages coming from origin chains that the snapshot refers to.
library SnapshotLib {
using MemViewLib for bytes;
using StateLib for MemView;
// ═════════════════════════════════════════════════ SNAPSHOT ══════════════════════════════════════════════════════
/**
* @notice Returns a formatted Snapshot payload using a list of States.
* @param states Arrays of State-typed memory views over Origin states
* @return Formatted snapshot
*/
function formatSnapshot(State[] memory states) internal view returns (bytes memory) {
if (!_isValidAmount(states.length)) revert IncorrectStatesAmount();
// First we unwrap State-typed views into untyped memory views
uint256 length = states.length;
MemView[] memory views = new MemView[](length);
for (uint256 i = 0; i < length; ++i) {
views[i] = states[i].unwrap();
}
// Finally, we join them in a single payload. This avoids doing unnecessary copies in the process.
return MemViewLib.join(views);
}
/**
* @notice Returns a Snapshot view over for the given payload.
* @dev Will revert if the payload is not a snapshot payload.
*/
function castToSnapshot(bytes memory payload) internal pure returns (Snapshot) {
return castToSnapshot(payload.ref());
}
/**
* @notice Casts a memory view to a Snapshot view.
* @dev Will revert if the memory view is not over a snapshot payload.
*/
function castToSnapshot(MemView memView) internal pure returns (Snapshot) {
if (!isSnapshot(memView)) revert UnformattedSnapshot();
return Snapshot.wrap(MemView.unwrap(memView));
}
/**
* @notice Checks that a payload is a formatted Snapshot.
*/
function isSnapshot(MemView memView) internal pure returns (bool) {
// Snapshot needs to have exactly N * STATE_LENGTH bytes length
// N needs to be in [1 .. SNAPSHOT_MAX_STATES] range
uint256 length = memView.len();
uint256 statesAmount_ = length / STATE_LENGTH;
return statesAmount_ * STATE_LENGTH == length && _isValidAmount(statesAmount_);
}
/// @notice Returns the hash of a Snapshot, that could be later signed by an Agent to signal
/// that the snapshot is valid.
function hashValid(Snapshot snapshot) internal pure returns (bytes32 hashedSnapshot) {
// The final hash to sign is keccak(snapshotSalt, keccak(snapshot))
return snapshot.unwrap().keccakSalted(SNAPSHOT_VALID_SALT);
}
/// @notice Convenience shortcut for unwrapping a view.
function unwrap(Snapshot snapshot) internal pure returns (MemView) {
return MemView.wrap(Snapshot.unwrap(snapshot));
}
// ═════════════════════════════════════════════ SNAPSHOT SLICING ══════════════════════════════════════════════════
/// @notice Returns a state with a given index from the snapshot.
function state(Snapshot snapshot, uint256 stateIndex) internal pure returns (State) {
MemView memView = snapshot.unwrap();
uint256 indexFrom = stateIndex * STATE_LENGTH;
if (indexFrom >= memView.len()) revert IndexOutOfRange();
return memView.slice({index_: indexFrom, len_: STATE_LENGTH}).castToState();
}
/// @notice Returns the amount of states in the snapshot.
function statesAmount(Snapshot snapshot) internal pure returns (uint256) {
// Each state occupies exactly `STATE_LENGTH` bytes
return snapshot.unwrap().len() / STATE_LENGTH;
}
/// @notice Extracts the list of ChainGas structs from the snapshot.
function snapGas(Snapshot snapshot) internal pure returns (ChainGas[] memory snapGas_) {
uint256 statesAmount_ = snapshot.statesAmount();
snapGas_ = new ChainGas[](statesAmount_);
for (uint256 i = 0; i < statesAmount_; ++i) {
State state_ = snapshot.state(i);
snapGas_[i] = GasDataLib.encodeChainGas(state_.gasData(), state_.origin());
}
}
// ═════════════════════════════════════════ SNAPSHOT ROOT CALCULATION ═════════════════════════════════════════════
/// @notice Returns the root for the "Snapshot Merkle Tree" composed of state leafs from the snapshot.
function calculateRoot(Snapshot snapshot) internal pure returns (bytes32) {
uint256 statesAmount_ = snapshot.statesAmount();
bytes32[] memory hashes = new bytes32[](statesAmount_);
for (uint256 i = 0; i < statesAmount_; ++i) {
// Each State has two sub-leafs, which are used as the "leafs" in "Snapshot Merkle Tree"
// We save their parent in order to calculate the root for the whole tree later
hashes[i] = snapshot.state(i).leaf();
}
// We are subtracting one here, as we already calculated the hashes
// for the tree level above the "leaf level".
MerkleMath.calculateRoot(hashes, SNAPSHOT_TREE_HEIGHT - 1);
// hashes[0] now stores the value for the Merkle Root of the list
return hashes[0];
}
/// @notice Reconstructs Snapshot merkle Root from State Merkle Data (root + origin domain)
/// and proof of inclusion of State Merkle Data (aka State "left sub-leaf") in Snapshot Merkle Tree.
/// > Reverts if any of these is true:
/// > - State index is out of range.
/// > - Snapshot Proof length exceeds Snapshot tree Height.
/// @param originRoot Root of Origin Merkle Tree
/// @param domain Domain of Origin chain
/// @param snapProof Proof of inclusion of State Merkle Data into Snapshot Merkle Tree
/// @param stateIndex Index of Origin State in the Snapshot
function proofSnapRoot(bytes32 originRoot, uint32 domain, bytes32[] memory snapProof, uint8 stateIndex)
internal
pure
returns (bytes32)
{
// Index of "leftLeaf" is twice the state position in the snapshot
// This is because each state is represented by two leaves in the Snapshot Merkle Tree:
// - leftLeaf is a hash of (originRoot, originDomain)
// - rightLeaf is a hash of (nonce, blockNumber, timestamp, gasData)
uint256 leftLeafIndex = uint256(stateIndex) << 1;
// Check that "leftLeaf" index fits into Snapshot Merkle Tree
if (leftLeafIndex >= (1 << SNAPSHOT_TREE_HEIGHT)) revert IndexOutOfRange();
bytes32 leftLeaf = StateLib.leftLeaf(originRoot, domain);
// Reconstruct snapshot root using proof of inclusion
// This will revert if snapshot proof length exceeds Snapshot Tree Height
return MerkleMath.proofRoot(leftLeafIndex, leftLeaf, snapProof, SNAPSHOT_TREE_HEIGHT);
}
// ══════════════════════════════════════════════ PRIVATE HELPERS ══════════════════════════════════════════════════
/// @dev Checks if snapshot's states amount is valid.
function _isValidAmount(uint256 statesAmount_) internal pure returns (bool) {
// Need to have at least one state in a snapshot.
// Also need to have no more than `SNAPSHOT_MAX_STATES` states in a snapshot.
return statesAmount_ != 0 && statesAmount_ <= SNAPSHOT_MAX_STATES;
}
}