Comments (14)
Hey @terenc3t, the binary trie choice was originally mentioned on ETHResearch as proofs for light cilents would be much, much smaller. This would work well for a system such as sharding where we assume very little computational requirements or storage capacity of nodes.
from prysm.
No problem. All I'm doing at first is changing the radix of the state trie to 2, which mostly involves changes to the encoding and nodes. Having that should allow us to test whether the smaller Merkle proofs are worth the increased size of the tree. It's mostly an experiment for me to get more familiar with the trie package, and give us a place to start testing things out as @rauljordan suggested in the potential PR.
from prysm.
Just wanted to note that the Reed-Solomon encoded tree and the sparse merkle tree serve two different purposes, so they are not mutually exclusive.
The Reed-Solomon encoded tree is for representing the transaction data in each block (the "transactions merkle root"), in such a way that allows for data availability guarantees (i.e. that the transaction data is actually available), as opposed to using a standard merkle tree.
Sparse merkle trees are for representing the state of the entire blockchain (the "state merkle root"); having intermediate state roots reduces the cost of generating fraud proofs for incorrectly generated state roots. This still requires a data availability scheme to store these intermediate roots (unless light clients actually download them), such as the Reed-Solomon scheme, thus they are not mutually exclusive. I call this "data availability proof friendly" because you don't need to ensure availability of the entire state tree anymore, which would be insanely expensive to do per block (i.e. you don't want to apply Reed-Solomon encoding on the entire state!).
tl;dr: you don't want to be using the Reed-Solomon scheme for the state merkle root; just probably for the transaction merkle root.
from prysm.
Data availability
The Reed-Solomon approach seems more complex in term of algorithm and structure that having something close to a flat layout (nonce, balance, code, storage) in a simple tree (where hash can then easily be used for adressing).
Proof footprint
I also liked the idea of having smaller proof/receipt/simple-walk-along-one-tree in a environment where we are highly restricted by gas cost and gas usage, that may allow some extra functionalities in account abstraction possibilities.
Implementation issues
On the implementation sides of things, I think we should be more litterate on what kind of mecanism there is already in Geth and what that would that imply in term of how would be handled account in Geth (for example for hardware wallets, caching, storage, etc) with that new mindset.
from prysm.
Working on binary state trie version of geth, should be done by the end of the week.
from prysm.
@elihanover Thanks a lot for working on this! Before getting too deep into coding. Can you elaborate more on your design choice? In particular why a binary trie versus other options like Radix trie, Read-Solomon trie or Sparse Merkle trie?
from prysm.
Moving this to Sapphire release as not critical for minimal sharding protocol.
from prysm.
Just to give an update, I implemented the binary trie and just need to run some tests on it, so will hopefully have that by the end of the week.
from prysm.
awesome! thank for the update @elihanover
from prysm.
Thanks for this @elihanover can you share links to some code when you get a chance?
from prysm.
Forgot to get back to this for a while, but I've got an implementation of a binary trie with some results here that might be of interest. While proofs ended up being about half the size of radix 16 proofs, this is still far from optimal as mentioned here. I'm interested in optimizing this further and would appreciate feedback.
from prysm.
@elihanover That looks pretty interesting so instead of 4 bits of the hp - encoding you have 6 bits of encoding+padding from switching over to the binary trie ? Currently we will most likely be using the Sparse Merkle tree for representing the state of the whole chain
from prysm.
@nisdas HP has 4 bit prefix and 0 or 4 bits of padding, while the binary encoding is 4 bits prefix and 0-7 bits of padding. I saw this particular encoding as a simple way to take advantage of the preexisting HP encoding code (and luckily the 2 unused bits which just happened to be the exact amount of information needed for the change); however, I imagine there are significantly better encoding schemes for a binary tree. Let me know if/how I can be of use in regards to this.
from prysm.
This will change significantly and will not be touched until perhaps phase 2 of the spec. We will close for now until it is brought up in later research.
from prysm.
Related Issues (20)
- what is the format for the --peer parameter for the beacon-chain ?
- some issues in the ```GetLightClientUpdatesByRange``` function
- randomly dropping peer
- `--suggested-fee-recipient` for validator not overriding beacon's address in Prysm v5.0.3 HOT 3
- replace gorilla mux with http.ServeMux HOT 1
- add ``is_better_update`` helper function from CL specs
- cannot connect to peer HOT 1
- Replace multiple `--<network>` flags by an unique `--network=<network>` flag. HOT 1
- Misleading fee recipient used in `payload_attributes` event HOT 1
- Some places return an epoch where a sync committee period is expected instead
- Sepolia synchronization suddenly stopped working. HOT 2
- msg="Rebuilt deposit trie is invalid" error="wanted the canonical count of 1581467 but received 719741"
- Nethermind/Prysm sync is stuck, undefined execution engine error HOT 4
- Prysm VC ignores `--wallet-dir` tag and uses default path for `auth-token` file HOT 2
- eth/v1/node/syncing endpoint returns wrong value HOT 4
- p2p: fix redundant check while pruning peers in peer status
- Eth HOT 1
- Eth
- bug with minimal genesis preset: SynCommitteeBits length expected 64 HOT 1
- Minor Issues Identified in `runner` at `validator/client/runner.go` HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from prysm.