# Changelog

All notable changes to this project will be documented in this file.

The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).

## [Unreleased]

## [0.5.3] - 2024-09-09

## Added

- Add `Default` implementation for `Tree`
- Add bounds check on `Tree::insert`, improving panic message [#91]

## [0.5.2] - 2023-10-27

### Fixed

- Fix `rkyv` serialization for `Tree` [#73]

## [0.5.1] - 2023-10-12

### Removed

- Remove unused `dusk-bls12_381` dependency

### Added

- Add `ff` dev-dependency

## [0.5.0] - 2023-06-28

### Removed

- Remove features `blake3`, `poseidon` and `zk` [#58]
- Remove `Aggregate` implementations for blake3 and poseidon [#58]

### Added

- Add more comprehensive benchmarks for `blake3` tree [#54]
- Add `to_var_bytes` and `from_slice` to `Opening` [#55]

### Changed

- Update to poseidon hash optimized for merkle openings [#62]

## [0.4.0] - 2023-06-07

### Added

- Documented poseidon related types [#31]

### Changed

- Modify `Aggregate` to include only one `EMPTY_SUBTREE` [#49]
- Relax `Aggregate` bounds to not be `Copy` [#49]
- Change return of `Tree::smallest_subtree` to `Ref<T>` as opposed to `Option<Ref<T>>` [#49]

## [0.3.0] - 2023-06-07

### Added

- Add lazy computation of node items [#37]
- Add missing Rkyv derivations for poseidon `Item`
- Add smallest_subtree functionality [#38]

### Changed

- Return `Ref<T>` from `Tree::root` instead of `&T` [#37]
- `Walk` now binds `T` to be `Aggregate` [#37]
- Change `Aggregate` trait to provide an array of references instead of an iterator [#44]
- Change the benchmarks to use criterion [#34]

### Removed

- Remove `Hash` derivation on `Tree` [#37]

## [0.2.0] - 2023-05-17

### Added

- Add getters for all fields in `Opening` [#25]
- Add merkle tree implementation with poseidon hash and opening gadget [#29]
- Add implementation of `Aggregate` for `()` [#34]

### Changed

- Change opening branch to hold `T` instead of `Option<T>` [#25]

## [0.1.0] - 2023-04-26

### Added

- Add `Tree::walk` allowing a user to walk the tree [#21]
- Add example of generating zero hashes for `blake3`
- Add `EMPTY_SUBTREES` to `Aggregate` trait
- Derive `Debug`, `Clone`, `PartialEq`, `Eq`, and `Hash` for `Tree` and `Opening` [#13]

### Changed

- Change `Aggregate` trait to bind `Self` to be `Copy`
- Change `Tree::root` to return `&T` as opposed to `Option<&T>`
- Change `Tree` structure by removing `len` field

### Fixed

- Fix `CheckBytes` derivation in `Node` [#15]

<!-- ISSUES -->
[#91]: https://github.com/dusk-network/merkle/issues/91
[#73]: https://github.com/dusk-network/merkle/issues/73
[#62]: https://github.com/dusk-network/merkle/issues/62
[#58]: https://github.com/dusk-network/merkle/issues/58
[#55]: https://github.com/dusk-network/merkle/issues/55
[#54]: https://github.com/dusk-network/merkle/issues/54
[#49]: https://github.com/dusk-network/merkle/issues/49
[#44]: https://github.com/dusk-network/merkle/issues/44
[#38]: https://github.com/dusk-network/merkle/issues/38
[#37]: https://github.com/dusk-network/merkle/issues/37
[#32]: https://github.com/dusk-network/merkle/issues/32
[#31]: https://github.com/dusk-network/merkle/issues/31
[#29]: https://github.com/dusk-network/merkle/issues/29
[#25]: https://github.com/dusk-network/merkle/issues/25
[#21]: https://github.com/dusk-network/merkle/issues/21
[#15]: https://github.com/dusk-network/merkle/issues/15
[#13]: https://github.com/dusk-network/merkle/issues/13

<!-- VERSIONS -->
[Unreleased]: https://github.com/dusk-network/merkle/compare/v0.5.3...HEAD
[0.5.3]: https://github.com/dusk-network/merkle/compare/v0.5.2...v0.5.3
[0.5.2]: https://github.com/dusk-network/merkle/compare/v0.5.1...v0.5.2
[0.5.1]: https://github.com/dusk-network/merkle/compare/v0.5.0...v0.5.1
[0.5.0]: https://github.com/dusk-network/merkle/compare/v0.4.0...v0.5.0
[0.4.0]: https://github.com/dusk-network/merkle/compare/v0.3.0...v0.4.0
[0.3.0]: https://github.com/dusk-network/merkle/compare/v0.2.0...v0.3.0
[0.2.0]: https://github.com/dusk-network/merkle/compare/v0.1.0...v0.2.0
[0.1.0]: https://github.com/dusk-network/merkle/releases/tag/v0.1.0