# Merkle Tally Tree

<img alt="Merkle Tally Tree Icon" src="./contrib/tallytree.png" height="300px" width="auto">

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](http://bitcoinunlimited.net/blockchain_voting)
article of Bitcoin Unlimited.

**[Reference Documentation](https://bitcoinunlimited.gitlab.io/tallytree/tallytree/)**

## Example

```rust
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]),
])
.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](https://t.me/bitcoinunlimit).

## Contributing

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