Change hat tree shape to 14 levels with 16 bits per level#78
Change hat tree shape to 14 levels with 16 bits per level#78
Conversation
nintynick
left a comment
There was a problem hiding this comment.
Just reviewed. All looks good to me at sanity check level.
My biggest concerns would be around off-by-one errors at the highest level and last hat, since we ran into that last time. Since tests pass I assume this ok.
Second concern would be if there is any code that did not get necessarily updated and doesn’t show up in the PR. Also assume this is ok given passing tests - relying on established strength of test suite. Happy to do a deeper dive here before merging if called for though.
Strong work!
topocount
left a comment
There was a problem hiding this comment.
Since the uint14 type does not exist -- we are nonetheless forced to use a uint16 to track
hat.lastHatId. This adds a small amount of overhead to thebuildHatIdfunction to prevent hats from creating between 214 and 216 hats, but for the small cost we gain two additional levels of tree depth.However, there are a couple drawbacks to using 14 bits per level vs. 16.
I figured this would be an issue. Now that we have an implementation in the wings that gives near-infinite tree depth, I'd rather invert to 14x16. and allow the bitspace to remain a nice 2^x multiple.
Pretty hat ids are slightly more annoying to generate, since we can no longer just insert periods into the hex version of a hat id. The simplest approach would be insert periods into the base-14 version of a hat id, but base-14 is not commonly used and this could create confusion since at first glance it may look like hex.
I'm honestly not sure what "inserting periods" means here.
test/HatsIdUtils.t.sol
Outdated
|
|
||
| vm.expectRevert(abi.encodeWithSelector(InvalidChildHat.selector)); | ||
|
|
||
| utils.buildHatId(admin, 2**14); |
There was a problem hiding this comment.
It might be better to demonstrate the range of invalid hats on a given level and show the boundary between valid and invalid.
test/Hats.t.sol
Outdated
| for (uint256 i = 1; i < type(uint16).max; ++i) { | ||
| if (i > (2**14 - 1)) { | ||
| vm.expectRevert( | ||
| abi.encodeWithSelector(InvalidChildHat.selector) | ||
| ); | ||
| } |
There was a problem hiding this comment.
Perfect, this actually does what I suggested above
|
@nintynick what do you think about the suggestion to move to 14 levels now that we have the ability to nest trees?
@topocount We have been playing around with a "pretty id" format that's similar to IP addresses. Eg in our previous 28x8 tree shape the second hat created under the fourth tophat would have the following:
|
I think it makes sense to do it that way, emphasizing @topocount's point:
If we consider the case where we use hatter contracts and each "level" of hats takes two levels, then we end up with 14/2 = 7 levels instead of 16/2 = 8 levels. At that small of a number of levels, the 1 level seems like it might make a difference, and would cause me to lean in that direction. But with infinite nested hat trees I think we'll be fine. All in, seems like a deal-with-it-once-we-see-it-in-prod type decision, which leans me toward 14 levels to keep the bitspace nice. |
|
Broadly speaking, it feels like 14 levels is going to waste a lot of the hat space. With 14 levels (ie 16 bits per level), there can be up to 65,536 child hats per hat. With 16 levels (ie 14 bits per), there can be up to 16,384 child hats per hat. I would be shocked if any DAO gets close to the latter number, so the extra 50k hats per level feels like a waste. That said, I do prefer the elegance of 2**n bits per level to have to move to base14. I'm kinda torn, but if I had to choose, I'd go with 14 levels since we'll also be able to nest trees for additional levels. |
|
Changed to 14x16, ie 14 levels with 16 bits per level |
|
fyi @topocount for purposes of rebasing #79 |
…bility Feat: prevent transfer of immutable hats
Overview
This PR changes the shape of the hat tree structure as follows:
The reason for this change is that we have learned that trees are generally likely to be wider than they are deep, and this new shape creates more flexibility for DAOs in that regard.
Why 14 vs 16 bits per level?
Since we're keeping 4 bytes of address space for tophats, we're left with 224 bits to work with for additional levels. Those bits can be broken down into several permutations of levels and address space per level. Here are the most likely candidates, in order of wider/shallower to skinnier/deeper:
16 x 14 gives the best available combination of tree depth and hats per level.
However, there are a couple drawbacks to using 14 bits per level vs. 16.
hat.lastHatId. This adds a small amount of overhead to thebuildHatIdfunction to prevent hats from creating between 214 and 216 hats, but for the small cost we gain two additional levels of tree depth.