Lineage Registry: an ERC-721 extension for on-chain genealogical trees

Author: Henrique L. Alvim ( @henriquelalvim ) Reference implementation: genealogicalRegistryBlockchain Base Sepolia deployment: Base Sepolia Blockscout TL;DR — I am proposing a standard for decentralized genealogical tree register , primarily used for genealogical tracking to verify pedigree. The proposed standard is this contract: LineageRegistry.sol . ERC-721 tokens form a sexed DAG : each token carries a sex and a birth date, and is either a founder or has exactly one sire and one dam. Six rules are mandatory, four extensions are opt-in behind ERC-165, and acyclicity needs no cycle check at all — it falls out of monotonic token IDs. The open questions at the end are what I actually want feedback on. The problem I am actually trying to solve For a pedigree animal, the pedigree is a large fraction of the value. The gap between a documented and an undocumented animal of the same quality is not a rounding error — it is often most of the price. That record lives in a studbook : a private database run by a breed association. If you are buying, what you receive is a PDF. You cannot check it. You are trusting the association, and transitively every clerk who ever typed into it. This produces three failures that anyone in the industry will recognize: You cannot verify a claim , only receive it. Associations disagree about the same animal, and there is no mechanism to reconcile them — the same horse exists twice, under two names, with two ancestries. When an association fails, the ancestry dies with it. Registries have been lost to bankruptcy, war, fire and simple neglect. The animals outlive the records. Why ERC-721 alone does not solve it Nothing stops you from putting "sire": 42 in your token metadata today. But metadata is a claim , and nothing checks it. Specifically, nothing stops: a parent recorded as born after its own offspring; a cycle — an animal that is transitively its own ancestor; me naming your champion stallion as my foal’s sire, without ever asking you; one parent recorded and the other quietly missing, indistinguishable from an animal with no known ancestry at all. Each of these is a real thing that happens in real studbooks. So the goal is not to put pedigrees on-chain — anyone can do that today. It is to replace the private studbook with a decentralized one : a directed acyclic graph whose structural rules are enforced at write time, by the contract, on every registration. No association owns it, no clerk can rewrite it, and a reader does not have to trust that it is consistent — it cannot be anything else. What the tokens look like ERC-721 tokens forming a sexed directed acyclic graph: every token carries its own sex and birth date, and is either a founder or descends from exactly one sire (a male token) and one dam (a female token). struct Node { uint256 sireId; // the father — a male token, or 0 uint256 damId; // the mother — a female token, or 0 uint64 birthTimestamp; // ─┐ packed together into one storage slot bool isMale; // ─┘ } Four facts, three storage slots, and token ID 0 is never minted so it doubles as the “no recorded parent” sentinel. Scope The standard is ILineageRegistry and LineageRegistry.sol , the abstract contract that enforces it: the node, the six rules below, and consent. It inherits ERC721 and nothing else — not even AccessControl . The repo also holds a concrete PedigreeRegistry , with breeds, animal names, studbook references and death records. That one is not part of the proposal. It is a worked example of a domain layer, there to prove the core is deployable and to give the gas numbers something real to measure. About the vocabulary: sireId and damId are just parentMale and parentFemale , and I picked the animal words deliberately. Pedigree animals are the use I actually understand, and the one I am most confident this is correct for. I did not design it for plants — I do not know that field well enough to claim it works there. I did not design it for people either: the data model would fit, but tokenizing human descent raises ethical questions a token standard should not settle quietly. Structurally the model is general — any genealogy of individuals with two parents of distinct sexes fits it unchanged, and I would be glad to hear which of those it should officially claim. But the scope I am proposing is animals. Acyclicity is free There is no cycle check anywhere in the contract, and the graph is still provably acyclic. It falls out of two rules a registry wants for independent reasons: both parents must already exist when the offspring is minted, and token IDs increase monotonically . Therefore a parent’s ID is always lower than its offspring’s. Following parent edges strictly decreases the token ID, so a cycle cannot exist and an upward walk always terminates — without a single comparison being written to enforce it. #1 ♂ #2 ♀ #3 ♂ #4 ♀ founders — no recorded parents └──┬──┘ └──┬──┘ │ │ #5 ♀ #6 ♂ sire #1, dam #2 / sire #3, dam #4 └────────┬─────────┘ │ #7 ♂ sire #6, dam #5 every edge points from a higher ID to a lower one — by construction, always There’s also this demo I’m building, so you can visualize what is being tried to accomplish (sorry it’s in portuguese for now, but it’s intuitive): This is not the chronology rule. Chronology is enforced separately and buys something else: the promise that the pedigree describes something that could have happened in the physical world . A foal born before its own sire is the most common form of bad studbook data, which is why that rule is not optional either. What is mandatory, and why exactly these The test each rule had to pass: if this were optional, could you still trust the graph? Rule Without it Sexed parentage — a sire is male, a dam is female the pedigree is not a pedigree All-or-nothing parentage — both parents or neither “no parents” and “one parent” become indistinguishable Parents pre-exist and IDs are monotonic acyclicity stops being free and needs an unbounded check Write-once — recorded parentage is never overwritten history is editable, and the record is worthless Chronology — parents born strictly before the offspring a foal can precede its own sire Consent — naming a token as a parent needs its owner’s permission anyone can hang their animal off your champion Consent is the one people do not expect, so: ancestry here is a mutually agreed record, not a unilateral claim . Grants come per-token (“this stud may be named as a parent by that address”) or blanket (“that address may name any token I own”). The blanket grant follows the owner , not the token, so it covers animals bought later and lapses the moment one is sold. The core interface (click to expand) (click for more details) What is optional, and what that costs Four extensions, each with its own ERC-165 ID, the way ERC721Metadata and ERC721Enumerable relate to ERC-721. A deployment composes exactly the registry it needs, and consumers discover at runtime what they got. Extension Adds Requires Offspring the reverse index: getOffspring , offspringCount — LateParentage attachParentage — promote a founder once, later — Mergeable fold a duplicate into a survivor, plus a forwarding tombstone Offspring Burnable destroy a leaf node; anything with offspring is refused Offspring One of those splits is worth a number, because it is why the standard is shaped this way at all. Stack register with two parents core only 138,516 gas core + Offspring 227,269 gas full reference composition 266,415 gas Offspring costs 88,753 gas — two cold SSTORE s per parented registration, comfortably more than everything core does put together. And the same information is fully reconstructible off-chain from ParentageLinked events. So install it only if you have to answer “who are this stallion’s foals?” on-chain . A core-only registry is 48% cheaper per registration and 59% smaller — which is what stopped me pushing more into the mandatory core, including things I personally always want. Objections I expect, answered in advance Why exactly two parents? Why binary sex? (click for more details) Why is half a pedigree unrecordable? (click for more details) Why is there no registrar role? (click for more details) Known limitations Two unbounded ancestor walks , in attachParentage and in the merge primitive. On a deep pedigree either can exhaust gas — which would make those operations permanently impossible on exactly the old, well-documented lines where they matter most. This is the weakest part of the design. See open question 6. isMale returns false for tokens that do not exist , so “female” and “absent” are indistinguishable without a separate existence check. See open question 1. Revert strings rather than custom errors , kept for legibility while the standard is being drafted. No frozen interface. Every ERC-165 ID moves if a signature changes. The test suite is a structured skeleton. Core, every extension and the reference composition have been exercised end-to-end against a deployed instance, but the published suite is not yet the proof it should be. I would not use this for real money today. Open questions — these are the ones I actually want help with 1. bool isMale , or enum Sex { Unknown, Male, Female } ? The enum fixes the “female vs. absent” ambiguity above and leaves room for reproductive models this currently excludes. It is an ABI change to the core, so it has to be settled before anything freezes. 2. Do monotonic token IDs cost something I have not noticed? They are what makes acyclicity free, so I am attached to them. But they also mean the ID leaks registration order, that IDs cannot be chosen — no deriving a token ID from an existing studbook number — and that importing a paper studbook forces you to insert every ancestor before its descendants. Is there a worse consequence I am not seeing? 3. Should the standard know about phantom placeholders? When only one parent is documented, the all-or-nothing rule makes you invent the other: you register an empty, nameless founder of the missing sex just to complete the pair. That node is a real token — transferable, usable as a parent — standing for an animal that never existed. Nothing marks it as fictitious, so a consumer reading the graph cannot tell a placeholder apart from a genuine undocumented founder. An isPlaceholder flag would fix that and grow the core; leaving it out keeps the convention in the domain layer and makes consumers guess. I do not know which is right. 4. Should attaching parents to an existing founder be part of the standard? It is optional today, and it is the only operation that can break the ID-ordering argument — an attached parent may hold a higher ID than its child, so it needs a real cycle check rather than a free one. The need is real: you register an animal and its ancestry surfaces years later. Blessed by default, kept optional, or left out? 5. Should merging duplicates be in the standard at all? The same animal registered twice is not an edge case — it is exactly what happens when two breeders or two registries describe the same animal, and it is one of the three problems I opened with. But folding one token into another means reconciling parentage, walking ancestors to refuse a cycle, and leaving a forwarding tombstone so old references still resolve. It is the most complex and most expensive thing in the repo, and it is why I made it optional. Is that too much weight for a standard to carry — or is a genealogy standard that cannot reconcile duplicates simply unfinished? 6. What do I do about the two unbounded ancestor walks? The obvious fix is a MAX_ANCESTOR_DEPTH constant, and I am against it. A genealogical record is meant to keep growing across generations — that is the entire reason to put it on a blockchain instead of in a database — and a depth cap breaks the standard precisely on the old, deep, well-documented lines that are worth the most. For the attach case there is a real fix: when the proposed parent’s ID is already lower than the child’s, ID ordering alone proves safety and the walk can be skipped, which covers the common path. For merging I have nothing good. Off-chain proof? A documented, accepted limitation? Something I have not thought of? 7. Cross-registry linking — is on-chain even the right answer? A parent is a bare uint256 that must exist in this contract, so a token in someone else’s registry is not merely unauthorized, it is unrepresentable. Three options: mirror nodes (import the foreign animal as an ordinary local token with an origin pointer — no core change, local acyclicity intact, but a fragmented getOffspring ); widened references (chainId, registry, tokenId) (honest, and a different ERC — the node triples, every read signature changes, and acyclicity degrades to a social guarantee); or off-chain attestations consumed by an indexer (federation with no data-model change, and it may well dominate the other two). I kept this out rather than guess. Should the core reserve anything for it now? 8. One ERC with four optional extensions, or five ERCs? Written as one, following ERC-721’s treatment of Metadata and Enumerable. The counter-argument is the ERC-1155 / ERC-1155 Supply split, which keeps the core tiny at the cost of inter-ERC dependencies — Mergeable and Burnable both require Offspring . Happy to be told the framing is wrong. The thing I am least sure of is question 7, and the thing I am most sure of is that the studbook problem is real and blockchain can solve it better, as the registers live onchain forever. 1 post - 1 participant Read full topic