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.

Reference Documentation

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.