// SPDX-License-Identifier: MIT pragma solidity 0.8.28; import {Poseidon2} from "./Poseidon2.sol"; import {Zeros} from "./Zeros.sol"; /// @title Tree /// @notice One append-only Merkle tree with Poseidon2 nodes, 32 levels deep. Each leaf is /// hash(root, block time), where `root` is the root of a batch of hashes built off chain. A hash /// in a batch thereby provably existed at that time. /// @dev Only the right edge of the tree is kept, so storage never grows. To bring an old path /// up to the current root, read `edge()` once and the `Added` events that finished the parts /// to the right of it (each event lists the subtree roots its leaf completed, level 0 first). contract Tree { uint256 public constant DEPTH = 32; address public owner; address public adder; uint32 public count; bytes32 public root; bytes32[32] internal filled; // at each level, the left node waiting for its right neighbour bytes32[32] internal last; // the newest leaf's path: its node at each level event Added(uint32 indexed leafIndex, bytes32 batchRoot, uint64 time, bytes32 root, bytes32[] completed); event AdderChanged(address adder); error NotAdder(); error NotOwner(); error NotInField(); error Full(); constructor(address adder_, address owner_) { adder = adder_; owner = owner_; bytes memory z = Zeros.ALL; for (uint256 k = 0; k < DEPTH; k++) { filled[k] = bytes32(Zeros.at(z, k)); last[k] = filled[k]; } root = bytes32(Zeros.at(z, DEPTH)); } /// @notice Adds hash(batchRoot, block.timestamp) as the next leaf. function add(bytes32 batchRoot) external returns (uint32 index, bytes32 newRoot) { if (msg.sender != adder) revert NotAdder(); if (uint256(batchRoot) >= Poseidon2.P) revert NotInField(); index = count; if (index == type(uint32).max) revert Full(); uint64 time = uint64(block.timestamp); bytes memory z = Zeros.ALL; bytes memory rcp = Poseidon2.PARTIAL; // The parts this leaf completes: level 0 (the leaf) and one more per trailing 1 bit. uint256 ones = 0; while ((index >> ones) & 1 == 1) ones++; bytes32[] memory completed = new bytes32[](ones + 1); // Step 0 hashes the leaf, steps 1 to DEPTH climb a level each. One place calls the hash, // which keeps the contract under the size limit. uint256 left = uint256(batchRoot); uint256 right = time; uint256 cur; for (uint256 step = 0; ; step++) { cur = Poseidon2.hash2(left, right, rcp); if (step == DEPTH) break; uint256 k = step; last[k] = bytes32(cur); if (k <= ones) completed[k] = bytes32(cur); if ((index >> k) & 1 == 0) { filled[k] = bytes32(cur); (left, right) = (cur, Zeros.at(z, k)); } else { (left, right) = (uint256(filled[k]), cur); } } newRoot = bytes32(cur); count = index + 1; root = newRoot; emit Added(index, batchRoot, time, newRoot, completed); } /// @notice Everything needed, besides events, to bring a path up to the current root. function edge() external view returns (uint32 count_, bytes32 root_, bytes32[32] memory last_) { return (count, root, last); } /// @notice The left nodes waiting at each level: what the next leaf's path is made of. function waiting() external view returns (uint32 count_, bytes32[32] memory filled_) { return (count, filled); } function setAdder(address adder_) external { if (msg.sender != owner) revert NotOwner(); adder = adder_; emit AdderChanged(adder_); } }