# Clarify and Implement a Merkle Tree The preserved report names a 60-minute Merkle-tree coding exercise but does not retain its operations, input representation, output contract, proof format, update rules, or hashing convention. Begin by recovering those requirements. Then show how you would implement only the operations the interviewer confirms, using any worked contract as an explicitly illustrative choice rather than as the missing original statement. ### Constraints & Assumptions - “Merkle tree” and the timed coding context are the only preserved technical requirements. - Record order, leaf encoding, odd-node handling, empty-tree behavior, membership proofs, and updates are not source facts. - A cryptographic hash may be used only after the interviewer confirms the algorithm or supplies a hash primitive. - For illustration only, use ordered byte records of at most `2^64 - 1` bytes, SHA-256, `leaf = H(0x00 || uint64_be(length) || record)`, and `parent = H(0x01 || left_digest || right_digest)`. Hash raw bytes, promote an unpaired final digest unchanged, define the empty root as `H(0x02)`, and render a returned root as lowercase hexadecimal. This convention is not a source fact. ### Clarifying Questions to Ask - Must the implementation build a root, update leaves, append records, or create and verify proofs? - What are the leaf inputs and their order, and how are bytes serialized? - Which hash, empty-tree value, and odd-node rule are required? - What exact proof or update representation, if any, must be returned? ### Illustrative Byte-Level Fixture Under the illustrative convention above, two one-byte records `0x61` and `0x62` have leaf preimages: - `00000000000000000161` - `00000000000000000162` Their raw SHA-256 leaf digests are: - `8b19d7b3c8681f11ff11a3efc5496f59fd3581c65fec123e42c2f5fb17295d7a` - `c2603e20db4a933b8f13a4146907caa2c4cd6fe260b26030726366ba36567fca` Hash `0x01` followed by those two raw 32-byte digests. The expected lowercase root is `b3a32b93b5455c27f25f0f12725bc8bd8a0232280102bb1227a941243bbebb2d`. The vector fixes the practice convention; it does not claim that the original interview used these bytes. ### Part 1 — Recover the contract Turn the data-structure name into an exact operation set with inputs, outputs, encodings, and edge cases. #### What This Part Should Cover - Required operations and return values - Leaf and internal-node byte encodings - Empty, odd, duplicate, and ordering behavior - Hash primitive and collision assumptions ### Part 2 — Implement the confirmed operations Explain bottom-up construction for an illustrative build-and-root branch, and describe what additional state proofs or updates would require. #### What This Part Should Cover - Deterministic hashing with an eight-byte unsigned big-endian record length - Level construction and root publication - Conditional proof or update design only when requested - Time and space complexity in terms of record count and total payload bytes ### Part 3 — Test the chosen convention Define fixed vectors and edge cases that would distinguish common encoding and tree-shape mistakes. #### What This Part Should Cover - Empty, singleton, even, odd, duplicate, and non-power-of-two inputs - The supplied two-record root plus independent empty, singleton, odd, and duplicate vectors - Tamper tests if proofs are required - Versioning when the convention changes ```hint Ask what the tree must do A data-structure name does not determine its public API or hashed bytes. Fix the operations and encoding before implementing nodes. ``` ### What a Strong Answer Covers - No invented proof, index, or update requirement - An explicit contract before code - Correct construction under the selected convention - Tests, complexity, security assumptions, and conditional extensions ### Follow-up Questions 1. What extra information must a membership proof retain? 2. How would one-leaf updates change stored state and complexity? 3. Why can two reasonable odd-node conventions produce different roots?