Commit history

890057cd826265f4457fc362b918696d3bb29dcb

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

a

AddBatchOpt return invalid key positions

arnaucube committed on Apr 24, 2021

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

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

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

a

Add Tree.emptyHash & nLeafs methods

arnaucube committed on Apr 17, 2021

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

a

Add Graphviz generation methods

arnaucube committed on Apr 17, 2021

a

Add Mutex, integrate tx into Tree struct

arnaucube committed on Apr 12, 2021

a

Add tree.Update(k, v) method

arnaucube committed on Apr 3, 2021

a

Tests migrate from stretchr/testify to frankban/quicktest

arnaucube committed on Apr 3, 2021

a

Add Iterate, Dump, ImportDump methods to Tree

arnaucube committed on Apr 2, 2021

a

Add tree.AddBatch (using db.Tx)

arnaucube committed on Apr 1, 2021

a

arnaucube committed on Mar 31, 2021

a

Add proof verification

arnaucube committed on Mar 31, 2021

a

Add proof generation

arnaucube committed on Mar 31, 2021

a

Add Tree.Add compatible with circomlib

arnaucube committed on Mar 30, 2021

a

Add GithubActions: lint & test

arnaucube committed on Mar 30, 2021

a

Add HashFunction interface (w/ Poseidon & Sha256)

arnaucube committed on Mar 30, 2021

a

Init: README.md & LICENSE

arnaucube committed on Mar 30, 2021