feat: Allow trees to be linked from the TopHat by topocount · Pull Request #79 · Hats-Protocol/hats-protocol

topocount · 2022-12-30T19:58:58Z

This feature allows for the following:

effectively infinitely deep trees (really, limited to 255 levels)
migrating suborgs into parent orgs without changing hat Ids

A few tasks left:

figure out the naming semantics for linked tophats and other naming nuances. Should we just call them "tree roots" when linked?
Ensure we can deploy the contract with this new feature!
test the new Hats.sol functions
Add more compreshensive testing to the HatsIdUtils changes
Add test for circular linkages and safe depth

spengrah · 2022-12-30T20:23:01Z

quick note: you can check contract size (including compared to max allowed size) with forge build --sizes

spengrah · 2022-12-30T20:28:29Z

src/HatsIdUtilities.sol


+    // for grafting one hats tree into another
+    // Trees can only be linked to another tree at the tophat level
+    mapping(uint32 => uint256) public linkedTreeAdmins; // topHatDomain => hatId


Is storage actually made cheaper here by using uint32 here instead of uint256 (ie the full top hat id)? My high level understanding of how storage for mappings works suggests that the answer is no, but I'm not highly confident in that analysis.

@slgraham It's meant to enforce that only TopHats can be stored here. Nothing else has a uint32 signature.

We could enforce this at the function interface only (so consumers are forced to ensure they're passing in a topHat id) and make this a uint256.

My main priority here is preventing the need to check that we're only accepting tophats at the code level and letting the interfaces do that for us.

I see. That makes sense, though I'd think we'd want to trade off the need to do that extra check with the need to cast down to uint32 in a couple other places. Without doing a more in-depth analysis (I'm on mobile currently), my guess is that those casts are cheaper on a unit basis but will occur significantly more often than the check, which will only occur when linking a top hat to another hat.

The alternative is another check to verify that something is a tophat every time. This is more self-evident in my opinion, and therefore better API design.

Makes sense, lets go with the uint32 approach.

Food for future thought: I can see us enabling some kind of free-floating hat -- perhaps all hats under the uint32(0) tophat address space -- that can't have any child hats but can be linked and unlinked from trees. Which would likely require a uint256=>uint256 mapping.

src/HatsIdUtilities.sol

test/HatsIdUtils.t.sol

spengrah · 2023-01-05T15:37:03Z

figure out the naming semantics for linked tophats and other naming nuances. Should we just call them "tree roots" when linked?

A few ideas for naming linked tophats. I think we either tap into the hats memespace or the tree memespace.

"nested tophat", ie when you nest a tophat within another tree, it becomes, simply, a nested tophat
"grafted tophat", ie when you graft a tophat's tree onto another tree, it becomes, simply, a grafted tophat
"tree root" is nice
"root hat"

@topocount what other naming nuances are you thinking of?

topocount · 2023-01-07T10:50:09Z

@topocount what other naming nuances are you thinking of?

Tree root is a simple yet self-descriptive choice. If a tree root is linked into another tree, it's still positionally a tree root and more importantly, the root of an address space. The term "Tophat" holds special sudo/admin powers in addition to the characteristics of the tree root so I think good to nominally delineate between the these. This rules out any names containing the name "tophat", and I think "tree root" contains more information than "root hat".

figured I'd share this thinking here for the purposes of public documentation

topocount · 2023-01-07T10:54:01Z

quick note: you can check contract size (including compared to max allowed size) with forge build --sizes

Just seeing this now 😅

src/Hats.sol

spengrah · 2023-01-08T23:06:00Z

src/Hats.sol

        require(noCircularLinkage(_topHatId, _newAdminHat), 'Circular Linkage');
-        // TODO: hardcode
-        uint256 fullTopHatId = uint256(_topHatId) << (256 - TOPHAT_ADDRESS_SPACE);
+        uint256 fullTopHatId = uint256(_topHatId) << 224; // (256 - TOPHAT_ADDRESS_SPACE);


Does hardcoding change anything here? I was under the impression that constants are "reduced" at compile time, ie that bytecode produced by (256 - TOPHAT_ADDRESS_SPACE) is the same as that produced by 224. Doesn't matter much, obviously; mostly checking my understanding.

Just did some sensitivity analysis for this calculation with hardcoded vs non-hardcoded:

hardcoded

not hardcoded

I was really hoping you were right, but this was a consideration back in pragma 0.4.x as well. Maybe this becomes less of a concern with the optimizer runs increased, but this should be low-hanging fruit for the optimizer at any config since it saves both deployment and tx cost.

Thanks for running that analysis! I've updated my mental model.

src/Hats.sol

src/HatsIdUtilities.sol

spengrah · 2023-01-09T19:50:45Z

This looks good to go from a functionality perspective! Upon further reflection and discussion with @davehrlichman and @nintynick, the ability to link and unlink tophats creates a ton of flexibility for DAOs while still maintaining the gas efficiency and UX advantages of the addressable ID scheme as much as possible. Really strong work! 💪

@topocount, beyond the hardcoding comment just above (re line 49), are there any optimizations you were planning to make within the scope of this PR?

spengrah · 2023-01-09T20:42:31Z

since #78 was merged into develop a few days ago, I believe the merge destination for this PR should be develop

This feature allows for the following: - effectively infinitely deep trees (really, limited to 255 levels) - migrating suborgs into parent orgs without changing hat Ids A few todos left: - [ ] figure out the naming semantics for linked tophats and other naming nuances. Should we just call them "tree roots" when linked? - [ ] test the new Hats.sol functions - [ ] Add more compreshensive testing to the HatsIdUtils changes - [ ] Add test for circular linkages and safe depth

These bitshifts are cheaper to just hardcode as a single op than throw in an extra utility and add addtional contextual "jump" opcodes

spengrah · 2023-01-09T21:11:17Z

Reviewed one more time and realized two things:

We should emit an event when linking and unlinking tophats so that indexers / subgraph can update accordingly. We can probably get away with a single event for both cases, eg something like TopHatLinked(uint32 domain, uint256 newAdmin and set newAdmin = 0 when unlinking. What do you think @topocount?
Can you please add the functions sigs for linking and unlinking to IHats.sol?

(We should probably set down some clearer PR acceptance criteria; thanks for bearing with this haphazard review process 😅)

topocount requested a review from spengrah December 30, 2022 19:58

topocount marked this pull request as draft December 30, 2022 19:59

topocount force-pushed the feat/linkable-trees branch from 185de13 to 7163a66 Compare December 30, 2022 20:04

spengrah reviewed Dec 30, 2022

View reviewed changes

src/HatsIdUtilities.sol Outdated Show resolved Hide resolved

spengrah reviewed Dec 30, 2022

View reviewed changes

test/HatsIdUtils.t.sol Outdated Show resolved Hide resolved

spengrah mentioned this pull request Jan 6, 2023

Change hat tree shape to 14 levels with 16 bits per level #78

Merged

topocount force-pushed the feat/linkable-trees branch from 69226f6 to bf87099 Compare January 7, 2023 12:59

spengrah reviewed Jan 8, 2023

View reviewed changes

src/Hats.sol Outdated Show resolved Hide resolved

spengrah reviewed Jan 8, 2023

View reviewed changes

src/Hats.sol Outdated Show resolved Hide resolved

spengrah reviewed Jan 8, 2023

View reviewed changes

src/Hats.sol Outdated Show resolved Hide resolved

spengrah reviewed Jan 8, 2023

View reviewed changes

topocount requested a review from spengrah January 9, 2023 01:49

spengrah reviewed Jan 9, 2023

View reviewed changes

src/Hats.sol Show resolved Hide resolved

spengrah reviewed Jan 9, 2023

View reviewed changes

src/HatsIdUtilities.sol Outdated Show resolved Hide resolved

topocount marked this pull request as ready for review January 9, 2023 20:22

topocount added 8 commits January 9, 2023 14:54

Review Comments from @slgraham

96195a7

fmt Test Contract

a29290a

Add Top Level Linking Tests

cda3d98

Updated Comments and cleaned up some details

0eff38b

Implement Circular Linkage Check

040b226

Add extra circular linking test and hardcode bitshifts

750c3fc

These bitshifts are cheaper to just hardcode as a single op than throw in an extra utility and add addtional contextual "jump" opcodes

Disallow linking if already linked

ed7eb83

topocount added 5 commits January 9, 2023 14:54

Add error messages to checks

f2ade3b

Add test to prevent re-linking before unlinking

bc515c7

Utilize Errors instead of require error strings

4be63c8

Hardcode Levels Constant

c2cae6f

Add docstring comments for unlink and link functions

ee5ae76

topocount force-pushed the feat/linkable-trees branch from 3f9e0ce to ee5ae76 Compare January 9, 2023 20:55

topocount changed the base branch from feat/16x14 to develop January 9, 2023 20:55

Add TopHatLinked Event

a803093

spengrah merged commit 0e7b4b7 into develop Jan 10, 2023

spengrah deleted the feat/linkable-trees branch January 21, 2023 00:18

Conversation

topocount commented Dec 30, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

spengrah commented Dec 30, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

spengrah commented Jan 5, 2023

Uh oh!

topocount commented Jan 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

topocount commented Jan 7, 2023

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

topocount Jan 9, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

spengrah commented Jan 9, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

spengrah commented Jan 9, 2023

Uh oh!

spengrah commented Jan 9, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

topocount commented Dec 30, 2022 •

edited

Loading

topocount commented Jan 7, 2023 •

edited

Loading

topocount Jan 9, 2023 •

edited

Loading

spengrah commented Jan 9, 2023 •

edited

Loading