### 7 releases

0.3.4 | Mar 3, 2022 |
---|---|

0.2.4 | Feb 27, 2022 |

0.1.0 | Dec 14, 2021 |

#**2910** in Magic Beans

**MIT**license

120KB

2K
SLoC

# Merkle Tally Tree

This is an implementation of Merkle Tally Tree in Rust. Merkle Tally Trees provide an efficent tally of an electronic vote. It scales to millions of votes, while still being able to prove efficently to every voter that the tally was fair. Using merkle tally tree, you can create:

- Efficient proof that a vote was tallied in a result (vote included).
- Efficient proof that a vote was not tallied in a result (vote excluded).
- Efficient proof of number of ballots included in the tally (no ballot witholding).

The reference documentation describes how proofs are designed.

See the whitepaper as part of the Blockchain Voting Techniques article of Bitcoin Unlimited.

## Example

`use` `tallytree``::``generate``::`generate_tree`;`
`use` `tallytree``::``hash``::`hash_node_ref`;`
`use` `tallytree``::``proof``::``{`
create_inclusion_exclusion_proof`,` create_proof_of_vote_count`,` verify_exclusion_proof`,`
verify_inclusion_proof`,` verify_proof_of_vote_count`,`
`}``;`
`use` `tallytree``::`Validation`;`
`//` A vote with 3 voters where:
`//`
`//` - 0xaa votes for the first option
`//` - 0xcc votes for the first option
`//` - 0xdd votes for the second option.
`let` tree `=` `generate_tree``(``vec!``[`
`(``[``0xaa``;` `32``]``,` `vec!``[``1``,` `0``]``)``,`
`(``[``0xcc``;` `32``]``,` `vec!``[``1``,` `0``]``)``,`
`(``[``0xdd``;` `32``]``,` `vec!``[``0``,` `1``]``)``,`
`]``,` `true``)`
`.``unwrap``(``)``;`
`let` v `=` `&``Validation``::`Strict`;`
`let` merkle_root_hash `=` `hash_node_ref``(``&`tree`,` v`)``.``unwrap``(``)``.``unwrap``(``)``.``0``;`
`//` Create a proof and verify that 0xaa's vote was tallied.
`let` `(`inclusion`,` `_``)` `=` `create_inclusion_exclusion_proof``(``&`tree`,` `&``[``0xaa``;` `32``]``,` v`)``.``unwrap``(``)``;`
`let` `(`proof_hash`,` `_``,` vote`)` `=` `verify_inclusion_proof``(``&`inclusion`,` `&``[``0xaa``;` `32``]``,` v`)``.``unwrap``(``)``;`
`assert_eq!``(`proof_hash`,` merkle_root_hash`)``;`
`//` Create a proof and verify that 0xbb's vote was not tallied.
`let` `(``_``,` exclusion`)` `=` `create_inclusion_exclusion_proof``(``&`tree`,` `&``[``0xbb``;` `32``]``,` v`)``.``unwrap``(``)``;`
`let` `(`proof_hash`,` `_``)` `=` `verify_exclusion_proof``(``&`exclusion`,` `&``[``0xbb``;` `32``]``,` v`)``.``unwrap``(``)``;`
`assert_eq!``(`proof_hash`,` merkle_root_hash`)``;`
`//` Create a proof and verify that there are 3 voters in the tally.
`let` votes_proof `=` `create_proof_of_vote_count``(``&`tree`,` v`)``.``unwrap``(``)``;`
`let` `(`votes`,` proof_hash`,` `_``)` `=` `verify_proof_of_vote_count``(``&`votes_proof`)``.``unwrap``(``)``;`
`assert_eq!``(`proof_hash`,` merkle_root_hash`)``;`
`assert_eq!``(`votes`,` `3``)``;`

## License

This project is MIT licensed.

## Contact

This project is part of Bitcoin Unlimited. Join the Bitcoin Unlimited telegram channel.

## Contributing

Merge requests welcome. It is suggested to contact project maintainer (dagurval) before making larger changes.

### Benchmarks

Benchmarks require Rust nightly and are enabled with a feature flag. To run
benchmarks:

.`cargo`` +nightly bench --features=with-benchmarks`

#### Dependencies

~350–710KB

~16K SLoC