Skip to content

Updates to SSZ Merkle proofs phase 0 doc#1186

Merged
protolambda merged 23 commits into
devfrom
vbuterin-patch-3
Aug 14, 2019
Merged

Updates to SSZ Merkle proofs phase 0 doc#1186
protolambda merged 23 commits into
devfrom
vbuterin-patch-3

Conversation

@vbuterin

Copy link
Copy Markdown
Contributor

No description provided.

@JustinDrake JustinDrake added the ssz Simple Serialize label Jun 17, 2019
@vbuterin vbuterin changed the title Updates to SSZ partials Updates to SSZ Merkle proofs phase 0 doc Jun 18, 2019
@hwwhww

hwwhww commented Jun 20, 2019

Copy link
Copy Markdown
Contributor

specs/light_client/merkle_proofs.md is coupled with SSZ partial implementation. IMO it seems more reasonable to move the code part into the SSZ module and describe the algorithm in English on the spec side. :'(

@vbuterin

Copy link
Copy Markdown
Contributor Author

Where's the "let's discuss on the next call" emoji where you need one 😄

@hwwhww

hwwhww commented Jun 21, 2019

Copy link
Copy Markdown
Contributor

fyi: the is_*_kind and is_*_type APIs are removed in #1180.

@djrtwo

djrtwo commented Jul 23, 2019

Copy link
Copy Markdown
Contributor

What's the status here @vbuterin ?

@vbuterin vbuterin requested review from djrtwo and protolambda July 30, 2019 16:16

@djrtwo djrtwo left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice! a few small things

Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md
vbuterin added a commit that referenced this pull request Aug 1, 2019
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
vbuterin and others added 2 commits August 1, 2019 18:11
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md
Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
"""
o = GeneralizedIndex(1)
for i in indices:
o = o * get_previous_power_of_2(i) + i

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do I read this right? We do padding by the length that does not include the leading 1 bit, but not actually remove the bit from the index before appending the bits to the output?

Example of what it looks like is happening here (assuming get_previous_power_of_2(i) just returns the closest power of 2 at i or lower):

indices = [ # (in binary for example purposes)
0b10001
0b1011
0b110001
]
o = 1
o = 1 0000 # pad
o = 1 0 0001 # add
o =    1 0001 000 # pad
o =    1 0010 011 # add
o =    1 0001 011 00000 # pad
o =    1 0001 100 10001 # add

What I expected:

o = 1
o = 1 0000 # pad
o = 1 0001 # add
o = 1 0001 000 # pad
o = 1 0001 011 # add
o = 1 0001 011 00000 # pad
o = 1 0001 011 10001 # add

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed! For inputs (10001, 1011, 110001) the output should indeed be 1 0001 011 10001 now.

Comment thread specs/light_client/merkle_proofs.md Outdated
"""
Returns the length of a path represented by a generalized index.
"""
return log(index)

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe use bit_length(), or at least log2()? And maybe explicitly rounded to an int, if choosing the log function?

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed to log2. I was assuming we have log2 explicitly defined elsewhere; if not happy to do bit_length() instead.

Comment thread specs/light_client/merkle_proofs.md Outdated
vbuterin and others added 6 commits August 2, 2019 09:43
Co-Authored-By: Danny Ryan <dannyjryan@gmail.com>
Co-Authored-By: Diederik Loerakker <proto@protolambda.com>
Co-Authored-By: Diederik Loerakker <proto@protolambda.com>
Co-Authored-By: Diederik Loerakker <proto@protolambda.com>
Comment thread specs/light_client/merkle_proofs.md
hwwhww pushed a commit that referenced this pull request Aug 11, 2019
raise Exception(f"Type not supported: {typ}")


def get_item_position(typ: SSZType, index: Union[int, str]) -> Tuple[int, int, int]:

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Worried about the [int, str] a bit, since they are exclusively (from each other) used based on typ. So e.g. Container with int is invalid. It is likely something to revisit with partials/other uses, but is ok for now.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think in all cases where we expect to use paths, the path would not be serialized, and it would be explicitly constructed directly as an input to get_generalized_index or similar methods (ie. never saved as a variable). So I think it's fine for that reason.

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes agree there, but we can maybe make it less error prone. We have others that are unfamiliar with the interface and need to use it as well.

Comment thread specs/light_client/merkle_proofs.md Outdated
Comment thread specs/light_client/merkle_proofs.md Outdated
vbuterin and others added 2 commits August 14, 2019 23:44
Co-Authored-By: Diederik Loerakker <proto@protolambda.com>
Co-Authored-By: Diederik Loerakker <proto@protolambda.com>
@protolambda protolambda merged commit f9d703c into dev Aug 14, 2019
@protolambda protolambda deleted the vbuterin-patch-3 branch August 14, 2019 21:50
@hwwhww hwwhww mentioned this pull request Aug 15, 2019
2 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

lightclients ssz Simple Serialize

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants