arnaucube
arnaucube/arboPublic Self-hosted repository

Commit history

1c2b7d68712b710c96fefdc294a1ddcd3d5d1fbe
a
Add CPU parallelization to AddBatch CaseD AddBatch in CaseD, is parallelized (for each CPU) until almost the top level, almost dividing the needed time by the number of CPUs.
arnaucube committed on Apr 24, 2021
1c2b7d6
a
Add AddBatch CaseD CASE D: Already populated Tree ============================== - Use A, B, C, D as subtree - Sort the Keys in Buckets that share the initial part of the path - For each subtree add there the new leafs R / \ / \ / \ * * / | / \ / | / \ / | / \ L: A B C D /\ /\ / \ / \ ... ... ... ... ... ...
arnaucube committed on Apr 24, 2021
890057c
a
AddBatchOpt return invalid key positions
arnaucube committed on Apr 24, 2021
b3007a0
a
Add CPU parallelization to buildTreBottomUp buildTreeBottomUp splits the key-values into n Buckets (where n is the number of CPUs), in parallel builds a subtree for each bucket, once all the subtrees are built, uses the subtrees roots as keys for a new tree, which as result will have the complete Tree build from bottom to up, where until the log2(nCPU) level it has been computed in parallel. As result of this, the tree construction can be parallelized until almost the top level, almost dividing the time by the number of CPUs.
arnaucube committed on Apr 24, 2021
a4ada7e
a
Add AddBatch CaseC CASE C: ALMOST CASE B --> if Tree has few Leafs (but numLeafs>=minLeafsThreshold) ============================================================================== - Use A, B, G, F as Roots of subtrees - Do CASE B for each subtree - Then go from L to the Root R / \ / \ / \ * * / | / \ / | / \ / | / \ L: A B G D / \ / \ / \ C * / \ / \ / \ ... ... (nLeafs >= minLeafsThreshold)
arnaucube committed on Apr 23, 2021
a347307
a
Add AddBatch CaseB CASE B: ALMOST CASE A, Almost empty Tree --> if Tree has numLeafs < minLeafsThreshold ============================================================================== - Get the Leafs (key & value) (iterate the tree from the current root getting the leafs) - Create a new empty Tree - Do CASE A for the new Tree, giving the already existing key&values (leafs) from the original Tree + the new key&values to be added from the AddBatch call R R / \ / \ A * / \ / \ / \ B C * * / | / \ / | / \ / | / \ L: A B G D / \ / \ / \ C * / \ / \ / \ ... ... (nLeafs < minLeafsThreshold)
arnaucube committed on Apr 18, 2021
600fd21
a
Add Tree.emptyHash & nLeafs methods
arnaucube committed on Apr 17, 2021
6f43980
a
Start to impl AddBatch efficient algorithm Case A In case that the tree is empty, build the full tree from bottom to top (from all the leaf to the root).
arnaucube committed on Apr 17, 2021
02b141d
a
Add Graphviz generation methods
arnaucube committed on Apr 17, 2021
8ede441
a
Add Mutex, integrate tx into Tree struct
arnaucube committed on Apr 12, 2021
c26b23c
a
Add tree.Update(k, v) method
arnaucube committed on Apr 3, 2021
8af9216
a
Tests migrate from stretchr/testify to frankban/quicktest
arnaucube committed on Apr 3, 2021
f8ac4be
a
Add Iterate, Dump, ImportDump methods to Tree
arnaucube committed on Apr 2, 2021
f1665b1
a
Add tree.AddBatch (using db.Tx)
arnaucube committed on Apr 1, 2021
cf572f6
a
Add tree.Get
arnaucube committed on Mar 31, 2021
4cd2ff6
a
Add proof verification
arnaucube committed on Mar 31, 2021
bde87ca
a
Add proof generation
arnaucube committed on Mar 31, 2021
8c63b5d
a
Add Tree.Add compatible with circomlib
arnaucube committed on Mar 30, 2021
43cb604
a
Add GithubActions: lint & test
arnaucube committed on Mar 30, 2021
7cfa466
a
Add HashFunction interface (w/ Poseidon & Sha256)
arnaucube committed on Mar 30, 2021
e1d2173
a
Init: README.md & LICENSE
arnaucube committed on Mar 30, 2021
7af0dae