Bitcoin-Wildlife-Sanctuary / bitcoin-circle-stark

Building blocks of a Circle STARK verifier in Bitcoin script
https://docs.btcwild.life
MIT License
82 stars 18 forks source link

Use stwo-style Merkle tree #53

Closed weikengchen closed 1 month ago

weikengchen commented 1 month ago

This PR aims to implement the Merkle tree in a way that is consistent to the hash_node implementation in the channel.

To simplify this implementation further, it assumes that the twins are always being queried together. This is the case for FRI answers as well as the intermediate FRI results.

The next step, which should go into a separate PR, is to implement a convertor that can convert the current Merkle decommitment data into a non-batched format.

codecov[bot] commented 1 month ago

Codecov Report

Attention: Patch coverage is 94.01709% with 7 lines in your changes missing coverage. Please review.

Files Coverage Δ
src/channel/bitcoin_script.rs 100.00% <100.00%> (ø)
src/constraints/bitcoin_script.rs 100.00% <100.00%> (ø)
src/constraints/mod.rs 100.00% <100.00%> (ø)
src/fibonacci/bitcoin_script/composition.rs 100.00% <100.00%> (ø)
src/fibonacci/mod.rs 94.48% <100.00%> (+0.40%) :arrow_up:
src/fri/bitcoin_script.rs 100.00% <ø> (ø)
src/fri/mod.rs 100.00% <ø> (ø)
src/merkle_tree/bitcoin_script.rs 100.00% <100.00%> (ø)
src/merkle_tree/mod.rs 100.00% <100.00%> (ø)
src/precomputed_merkle_tree/bitcoin_script.rs 100.00% <ø> (ø)
... and 3 more

... and 1 file with indirect coverage changes