Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

lite2: align with the newer version of the spec #4329

Closed
melekes opened this issue Jan 21, 2020 · 2 comments · Fixed by #4400 or #4496
Closed

lite2: align with the newer version of the spec #4329

melekes opened this issue Jan 21, 2020 · 2 comments · Fixed by #4400 or #4496
Assignees
@melekes
Labels
C:light Component: Light T:enhancement Type: Enhancement

Comments

@melekes
Copy link
Contributor

melekes commented Jan 21, 2020

once tendermint/spec#61 is merged.
@melekes melekes added C:light Component: Light T:enhancement Type: Enhancement labels Jan 21, 2020
@cmwaters cmwaters mentioned this issue Feb 13, 2020
Merged
5 tasks
@melekes melekes changed the title lite2: switch to non-recursive bisection lite2: align with the newer version of the spec Feb 13, 2020
@melekes
Copy link
Contributor Author

melekes commented Feb 13, 2020

re non-recursive bisection:

It exists only in a branch: https://github.com/tendermint/spec/blob/zm_non-recursive-verification/spec/consensus/light-client/non-recursive-verification.md. We removed it from the spec as there haven’t been convincing arguments in favour of non-recursive vs recursive variant.

@melekes
Copy link
Contributor Author

melekes commented Feb 19, 2020 •
edited
Loading

bisection-kinds

somewhat important image showing the difference between old bisection VS new non-recursive bisection algorithms.

@cmwaters this needs to be added to ADR-046 and possibly lite2 README file.

melekes added a commit that referenced this issue Feb 19, 2020
@cmwaters @melekes
lite: modified bisection to loop (#4400)
1874a97 
refs #4329

As opposed to using recursion to implement the bisection method of verifying a header, which could have problems with memory allocation (especially for smaller devices), the bisection algorithm now uses a for loop.

* modified bisection to loop

* made lint changes

* made lint changes

* move note to VerifyHeader

since it applies both for sequence and bisection

* test bisection jumps to header signed by 1/3+

 of old validator set

* update labels in debug log calls

* copy tc

Co-authored-by: Anton Kaliaev <anton.kalyaev@gmail.com>
@melekes melekes reopened this Feb 19, 2020
@melekes melekes mentioned this issue Feb 27, 2020
Closed
@melekes melekes assigned melekes and unassigned cmwaters Feb 28, 2020
melekes added a commit that referenced this issue Feb 28, 2020
@melekes
docs: adr-046 add bisection algorithm details
925c946 
Closes #4329
@melekes melekes mentioned this issue Feb 28, 2020
Merged
5 tasks
melekes added a commit that referenced this issue Feb 28, 2020
@melekes
docs: adr-046 add bisection algorithm details (#4496)
a122a55 
* docs: adr-046 add bisection algorithm details

Closes #4329

* format fig. 1 title

* docs: adr-046 we no longer download headers in TrustedHeader

#4496 (comment)
melekes added a commit that referenced this issue Mar 2, 2020
@melekes
docs: adr-046 add bisection algorithm details (#4496)
c8d825e 
* docs: adr-046 add bisection algorithm details

Closes #4329

* format fig. 1 title

* docs: adr-046 we no longer download headers in TrustedHeader

#4496 (comment)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@melekes melekes

Labels
C:light Component: Light T:enhancement Type: Enhancement
Projects
None yet
Milestone
No milestone
2 participants
@melekes @cmwaters