7 releases
0.3.4 | Mar 3, 2022 |
---|---|
0.2.4 | Feb 27, 2022 |
0.1.0 | Dec 14, 2021 |
#2910 in Magic Beans
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