arnaucube
arnaucube/arboPublic Self-hosted repository

Commit history

43cad713b0f9dcb494b231c8455f016b1587d2cd
a
Add Tree Circom Verifier Proofs Circom Verifier Proofs allow to verify through a zkSNARK proof the inclusion/exclusion of a leaf in a tree. This commit adds the needed code in go to generate the circuit inputs for a CircomVerifierProof.
arnaucube committed on Jun 16, 2021
43cad71
a
Add Tree.Snapshot method
arnaucube committed on Jun 11, 2021
465f0ed
a
Migrate repository to github.com/vocdoni/arbo
arnaucube committed on Jun 8, 2021
f10265e
a
Add Usage section to README.md
arnaucube committed on Jun 4, 2021
f2d5037
a
Update upFromNodes function for unbalanced tree - Update upFromNodes function for unbalanced tree case - Add AddBatchTestVector2 & 3 with some edge cases - Add checkRoots test method, which stores the Dump of the tree to file for after-debug
arnaucube committed on Jun 3, 2021
2c62f31
a
Migrate kv db to go.vocdoni.io/dvote/db interface Case tree empty, AddBatch was 10.95x times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.047k, dbGet: 1, dbPut: 2.049k) Case tree not empty w/ few leafs, AddBatch was 7.28x times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.047k, dbGet: 198, dbPut: 2.049k) Case tree not empty w/ enough leafs, AddBatch was 5.94x times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.047k, dbGet: 1.000k, dbPut: 2.049k) Case tree not empty, AddBatch was 9.27x times faster than without AddBatch nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory dbgStats(hash: 8.191k, dbGet: 1.800k, dbPut: 8.193k) Case tree not empty & unbalanced, AddBatch was 10.67x times faster than without AddBatch nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory dbgStats(hash: 10.409k, dbGet: 2.668k, dbPut: 10.861k) TestAddBatchBench: nCPU: 4, nLeafs: 50000, hash: Blake2b, db: badgerdb Add loop: 10.10829114s AddBatch: 732.030263ms dbgStats(hash: 122.518k, dbGet: 1, dbPut: 122.520k) TestDbgStats add in loop in emptyTree dbgStats(hash: 141.721k, dbGet: 134.596k, dbPut: 161.721k) addbatch caseEmptyTree dbgStats(hash: 24.402k, dbGet: 1, dbPut: 24.404k) addbatch caseNotEmptyTree dbgStats(hash: 26.868k, dbGet: 2.468k, dbPut: 26.872k)
arnaucube committed on Jun 3, 2021
c6059fc
a
Update check of already existing key on add - Update check of already existing key on add - Update docs of methods
arnaucube committed on Jun 2, 2021
467f063
a
Update public methods signatures - Update public methods signatures - Remove 'lastAccess' param - Add option to pass root for tree.Dump, Iterate, IterateWithStop, Graphviz (and related) - Move error messages to const defined error messages for external usage
arnaucube committed on May 26, 2021
0b2c3b0
a
Small update addbatch_test.go org
arnaucube committed on May 26, 2021
f24fb28
a
Rm functions related to Old AddBatch
arnaucube committed on May 24, 2021
d16ebd0
a
AddBatch implement using VirtualTree.AddBatch Reduces the num of hashes, dbGet and dbPut on cases D & E. Current benchmarks: ``` CASE A, AddBatch was 9.101855 times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.047k, dbGet: 1, dbPut: 2.049k) CASE B, AddBatch was 8.244078 times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.047k, dbGet: 198, dbPut: 2.049k) CASE C, AddBatch was 8.511131 times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.047k, dbGet: 202, dbPut: 2.049k) CASE D, AddBatch was 8.565696 times faster than without AddBatch nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory dbgStats(hash: 8.191k, dbGet: 1.800k, dbPut: 8.193k) CASE E, AddBatch was 8.970056 times faster than without AddBatch nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory dbgStats(hash: 10.409k, dbGet: 2.668k, dbPut: 10.861k) TestAddBatchBench: nCPU: 4, nLeafs: 50000, hash: Blake2b, db: leveldb Add loop: 10.616145533s dbgStats(hash: 824.884k, dbGet: 788.975k, dbPut: 924.884k) AddBatch: 942.34815ms dbgStats(hash: 122.051k, dbGet: 1, dbPut: 122.053k) TestDbgStats add in loop dbgStats(hash: 141.911k, dbGet: 134.650k, dbPut: 161.911k) addbatch caseA dbgStats(hash: 24.522k, dbGet: 1, dbPut: 24.524k) addbatch caseD dbgStats(hash: 26.985k, dbGet: 2.465k, dbPut: 26.989k) ```
arnaucube committed on May 24, 2021
f31ed1d
a
Implement VirtualTree.addBatch with cpu parallelization
arnaucube committed on May 23, 2021
d09bd60
a
Add dbgStats metrics Add dbgStats metrics to analyze number of Hashes, db Gets, and db Puts. Current benchmarks: ``` CASE A, AddBatch was 8.841700 times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.044k, dbGet: 1, dbPut: 2.049k) CASE B, AddBatch was 7.678766 times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.044k, dbGet: 199, dbPut: 2.049k) CASE C, AddBatch was 8.401087 times faster than without AddBatch nCPU: 4, nLeafs: 1024, hash: Poseidon, db: memory dbgStats(hash: 2.044k, dbGet: 207, dbPut: 2.049k) CASE D, AddBatch was 2.466346 times faster than without AddBatch nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory dbgStats(hash: 33.884k, dbGet: 30.697k, dbPut: 33.889k) CASE E, AddBatch was 1.958160 times faster than without AddBatch nCPU: 4, nLeafs: 4096, hash: Poseidon, db: memory dbgStats(hash: 41.419k, dbGet: 37.558k, dbPut: 41.874k) TestAddBatchBench: nCPU: 4, nLeafs: 50000, hash: Blake2b, db: leveldb Add loop: 10.089858449s dbgStats(hash: 825.285k, dbGet: 788.869k, dbPut: 925.285k) AddBatch: 904.647829ms dbgStats(hash: 122.458k, dbGet: 1, dbPut: 122.463k) TestDbgStats add in loop dbgStats(hash: 141.915k, dbGet: 134.602k, dbPut: 161.915k) addbatch caseA dbgStats(hash: 24.528k, dbGet: 1, dbPut: 24.533k) addbatch caseD dbgStats(hash: 115.506k, dbGet: 97.482k, dbPut: 115.516k) ```
arnaucube committed on May 23, 2021
4167583
a
Add TestAddBatchBench TestAddBatchBench nCPU: 4, nLeafs: 50000, hash: Blake2b, db: leveldb Add loop: 9.304195479s AddBatch: 817.590526ms
arnaucube committed on May 20, 2021
2a57e22
a
Remove cropping on pow of two the kvs for AddBatch - Remove cropping on power of two the kvs for AddBatch - As not needed to be power of two length with the Virtual Tree - Fix keyValuesToKvs keyPath
arnaucube committed on May 19, 2021
13378d3
a
AddBatch use Virtual Tree for empty trees/subtrees - AddBatch use Virtual Tree for cases A,B,C - ImportDump use AddBatch instead of adding one by one - Reorg & add more virtual tree tests
arnaucube committed on May 18, 2021
03bb9f7
a
Add computeHashes at virtual tree
arnaucube committed on May 17, 2021
66f6ae1
a
Add virtual tree graphviz printing methods
arnaucube committed on May 17, 2021
e13b092
a
Implement Virtual Tree construction VirtualTree (vt) computes a tree without computing any hash. With the idea of once all the leafs are placed in their positions, the hashes can be computed, avoiding computing a node hash more than one time.
arnaucube committed on May 17, 2021
8a8ec8c
a
Replace naive AddBatch by optimized AddBatch - Replace naive AddBatch by optimized AddBatch - Add blake2b hash support - Expose needed methods for external usage (ReadLeafValue, ReadIntermediateChilds) - Return 'value' in GenProof
arnaucube committed on May 8, 2021
6dcbbdf
a
Update CaseB to handle repeated keys cases - Update CaseB to handle repeated keys cases - Add test for AddBatch/CaseB with repeated keys - AddBatch-tests abstract code reusage
arnaucube committed on May 8, 2021
0eda440
a
AddBatch tests abstract code reusage
arnaucube committed on May 3, 2021
0dee3bc
a
Simplify cyclomatic complexity of AddBatch
arnaucube committed on May 1, 2021
da268ba
a
AddBatch: add CaseE, add parallelization on CaseB
arnaucube committed on Apr 27, 2021
f364cf6
a
AddBatch: commit tx at end,allow batch w/ len!=2^n
arnaucube committed on Apr 25, 2021
91a98bf
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