Currently the top level directory contains basically all of the code
for the crypto package. This PR moves the crypto code into submodules
in a similar manner to what `golang/x/crypto` does. This improves code
organization.
Ref discussion: https://github.com/tendermint/tendermint/pull/1966Closes#1956
This commit switches all usage of math/rand to cmn's rand. The only
exceptions are within the random file itself, the tools package, and the
crypto package. In tools you don't want it to lock between the go-routines.
The crypto package doesn't use it so the crypto package have no other
dependencies within tendermint/tendermint for easier portability.
Crypto/rand usage is unadjusted.
Closes#1343
* Reformated the ResultStatus
* fix misuse of ResultStatus.
* updated changelog
* Fixed tests
* fixed rpc helper tests
* fixed rpc_tests
* fixed mock/status_test
* fixed typo
* fixed ommitempty on validatorstatus and the changelog
* fixed extra line in changelog
* Updated usage of the /status json response in tests after breaking changes
* Updated remaining tests with changes after searching the codebase for usage
* Reformated the ResultStatus
* fix misuse of ResultStatus.
* updated changelog
* Fixed tests
* fixed rpc helper tests
* fixed rpc_tests
* fixed mock/status_test
* fixed typo
* fixed ommitempty on validatorstatus and the changelog
* Updated usage of the /status json response in tests after breaking changes
* Updated remaining tests with changes after searching the codebase for usage
* rebased against develop
Addressing some feedback from @ebuchman in regards to
consolidating some common test headers into a variable.
I've added that for simple cases, trying to meet in the middle
instead of creating helpers that obscure readibility and easy
comparison of test cases.
* GetByHeight will now switch to using binary search once
we have >=50 items.
* Feedback from @ebuchman to catch a missed spot where
we forgot about lazy sorting that the original code
assumed would always have sorted commits by height.
Added a lazy sorting routine here too.
A test as well to ensure that we always get the properly
sorted and last value.
Addressing PR review requests from @melekes and @ebuchman to
add a test that checks that the heights returned from both are
the same thus providing a perceptible equivalence of the code
linear range search vs binary range search code.
Updates #1021
* Implement a GetHeightBinarySearch method that looks for
the height using the binary search algorithm guaranteeing
worst case iteration time of O(log2(n))
whereas
worst case iteration time of O(n) for the current linear search
So if n we had 500 commits stored by height and sorted, to
trigger the worst case scenario for each, pass in
the most negative height you can find e.g. -1
Linear search: 500 iterations
Binary search: 9 iterations
with n=1000, qHeight = -1
Linear search: 1000 iterations
Binary search: 10 iterations
with n=1e6, qHeight = -1
Linear search: 1e6 iterations
Binary search: 20 iterations
Of course there are realistic expectations e.g. a max of
commits that may be saved so linear search might be useful
for very small size set because it has less preparing overhead
and only ~2 types of comparisons, but nonetheless binary search
shines as soon as we start to hit say 50 commits to search from
as you can see below:
```shell
$ go test -v -run=^$ -bench=MemStore
goos: darwin
goarch: amd64
pkg: github.com/tendermint/tendermint/lite
BenchmarkMemStoreProviderGetByHeightLinearSearch5-4 300000 6491 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch50-4 200000 12064 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch100-4 50000 32987 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch500-4 5000 395521 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch1000-4 500 2940724 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch5-4 300000 6281 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch50-4 200000 10117 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch100-4 100000 18447 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch500-4 20000 89029 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch1000-4 5000 265719 ns/op 1600 B/op 15 allocs/op
PASS
ok github.com/tendermint/tendermint/lite 86.614s
$ go test -v -run=^$ -bench=MemStore
goos: darwin
goarch: amd64
pkg: github.com/tendermint/tendermint/lite
BenchmarkMemStoreProviderGetByHeightLinearSearch5-4 300000 6779 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch50-4 100000 12980 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch100-4 30000 43598 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch500-4 5000 377462 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightLinearSearch1000-4 500 3278122 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch5-4 300000 7084 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch50-4 200000 9852 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch100-4 100000 19020 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch500-4 20000 99463 ns/op 1600 B/op 15 allocs/op
BenchmarkMemStoreProviderGetByHeightBinarySearch1000-4 5000 259293 ns/op 1600 B/op 15 allocs/op
PASS
ok github.com/tendermint/tendermint/lite 86.204s
```
which gives
```shell
$ benchstat old.txt new.txt
name old time/op new time/op delta
MemStoreProviderGetByHeight5-4 6.63µs ± 2% 6.68µs ± 6% ~ (p=1.000 n=2+2)
MemStoreProviderGetByHeight50-4 12.5µs ± 4% 10.0µs ± 1% ~ (p=0.333 n=2+2)
MemStoreProviderGetByHeight100-4 38.3µs ±14% 18.7µs ± 2% ~ (p=0.333 n=2+2)
MemStoreProviderGetByHeight500-4 386µs ± 2% 94µs ± 6% ~ (p=0.333 n=2+2)
MemStoreProviderGetByHeight1000-4 3.11ms ± 5% 0.26ms ± 1% ~ (p=0.333 n=2+2)
```
If need be we can make a hybrid algorithm that switches between the
linear and binary search depending on the number of items.
This is reminiscent of Python's TimSort algorithm.
* Vulnerability in light client proxy
When calling GetCertifiedCommit the light client proxy would call
Certify and even on error return the Commit as if it had been correctly
certified.
Now it returns the error correctly and returns an empty Commit on error.
* Improve names for clarity
The lite package now contains StaticCertifier, DynamicCertifier and
InqueringCertifier. This also changes the method receivers from one
letter to two letter names, which will make future refactoring easier
and follows the coding standards.
* Fix test failures
* Rename files
* remove dead code
Zarko Milosevic
Dev Ojha
Jae Kwon
Ethan Buchman
ValarDragon
Alexander Simmerl
Anton Kaliaev
Liamsi
Bric3d
Emmanuel T Odeke
Zach
Emmanuel Odeke
Adrian Brink