Add flat list proof support [ECR-3608] - #1156
dmitry-timofeev merged 24 commits into
Conversation
|
Currently, only unit tests are implemented, hence WIP status. The unit tests in FlatListProofTest can be reviewed. |
|
I like tests so far 👍 |
78 of 81 tests pass; 3 — fail.
| * If it is valid, the proof contents may be accessed. See {@link CheckedListProof} | ||
| * and {@link CheckedMapProof} for available contents description. | ||
| */ | ||
| // todo: Why do we need to represent invalid proofs? |
There was a problem hiding this comment.
Aren't we throwing an exception?
There was a problem hiding this comment.
The flat proof currently does not implement UncheckedProof interface, that's why it may and does throw exceptions. I decided exceptions are easier to implement and test. The question is on the original reasoning to represent them this way.
There is a year-old https://jira.bf.local/browse/ECR-2410 to reconsider.
|
The implementation is complete. We might consider extracting verification of each type of proof in separate classes to share some data used during verification (e.g., treeHeight, proofEntriesByHeight, etc.) |
A HashMap constructor accepts the initial capacity of the internal table of hash buckets, not the expected number of elements (as ArrayList constructor), hence the code used to down-size that table (given the default 0.75 load factor). The benchmark with GC profiler confirms the fix: Profile 1, no fix: Benchmark (height) Mode Cnt Score Error Units FlatListProofBenchmark.verify 10 thrpt 10 85,289 ± 0,920 ops/ms FlatListProofBenchmark.verify:·gc.alloc.rate 10 thrpt 10 931,355 ± 10,365 MB/sec FlatListProofBenchmark.verify:·gc.alloc.rate.norm 10 thrpt 10 14320,003 ± 0,001 B/op FlatListProofBenchmark.verify:·gc.count 10 thrpt 10 292,000 counts FlatListProofBenchmark.verify:·gc.time 10 thrpt 10 159,000 ms Profile 2, with exp. size: Benchmark (height) Mode Cnt Score Error Units FlatListProofBenchmark.verify 10 thrpt 10 87,436 ± 0,961 ops/ms FlatListProofBenchmark.verify:·gc.alloc.rate 10 thrpt 10 921,130 ± 10,306 MB/sec FlatListProofBenchmark.verify:·gc.alloc.rate.norm 10 thrpt 10 13816,003 ± 0,001 B/op FlatListProofBenchmark.verify:·gc.count 10 thrpt 10 290,000 counts FlatListProofBenchmark.verify:·gc.time 10 thrpt 10 157,000 ms
| o — 'virtual' node — not present in the proof, inferred during verification. | ||
| Shown mostly to communicate the tree structure of the proof. | ||
|
|
||
| See also: https://wiki.bf.local/display/EXN/Flat+list+proofs |
There was a problem hiding this comment.
Link to the internal documentation? It's not a public class though, so it's probably fine
There was a problem hiding this comment.
It will be public soon, but this comment is not a Javadoc, it is an implementation comment, and having the docs available and discoverable to some developers (actually — most 🙃) is better than to none.
I could mark it with [internal] if needed
There was a problem hiding this comment.
It's good as it is, thanks - indeed it's not a Javadoc.
Push #getHeight to the hashed entry as the element entries are always at height 0 and their height is neither requested nor included in the proof originally.
|
Pushed #getHeight down from the interface: cb286cb |
Overview
Add flat list proof support.
See:
Definition of Done