Beyond Identity Creation: Bilinear Sybil Cost in Identities and Time

arXiv:2611.06268 · cs.CR · Submitted 2026-11-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "Beyond Identity Creation".

Elias: Here's the gist of the paper. Sybil defenses price the creation of an identity, yet influence goes, again and again, to active identities The cost that matters is the cost of maintaining identities, as the distinction between stock and flow costs of attack in blockchains suggests A defense imposes a bilinear Sybil cost if keeping s identities active for T periods consumes at least a fixed amount of resource per identity and period This work gives four sufficient conditions for a defense that checks every identity each period to achieve bilinear Sybil cost: identity binding, freshness, a shared deadline, and sequential, non-batchable work They yield two guarantees: a bilinear total cost, with A the speed advantage of the adversary’s fastest hardware, and, because the work must be fresh and finished by a common deadline, a bound on the identities active in a period by the processors running at that time Cost Modeling and Failure Modes

Title and authors: Nadia: Let's talk about who wrote this paper, "Beyond Identity Creation: Bilinear Sybil Cost in Identities and Time." It’s Homayoun Maleki, Nekane Sainz, Jon Legarda, and Igor Santos-Grueiro.

Elias: I read the abstract again; it immediately signals that we are moving past just counting how many identities can be made. The focus is squarely on the long-term maintenance cost of influence.

Priya: It’s interesting they frame it as a cost model, separating the maintenance cost from the initial creation cost. That separation suggests they are trying to build a more realistic picture of sustained attacks.

Nadia: They define this bilinear Sybil cost C(s, T) and then immediately identify the three ways that recurring costs can fail to meet this scaling requirement: carried over, shared, and negligible.

Elias: That sets up the whole problem. It’s not just about building a defense once; it's about ensuring that every single identity actively participating meets a certain minimum computational requirement over time.

Priya: If we can understand those failure modes—how the cost gets carried over or shared—that gives us something tangible to test against in terms of data integrity and privacy leakage.

Nadia: And that’s what they do next: they propose four sufficient conditions for a defense to achieve this bilinear Sybil cost, which are identity binding, freshness, a shared deadline, and sequential non-batchable work.

The paper's summary: Elias: So the main summary is that if you impose those four conditions—binding identity, ensuring freshness of work, setting a common deadline for everyone, and making sure the work is sequential—you guarantee two things.

Nadia: First, you get a bilinear total cost where C(s, T) is at least s times T divided by A. That means the more identities you have and the longer they stay active, the more work they must do relative to an honest participant's cost.

Priya: And second, because of that common deadline and freshness requirement, they get a bound on how many identities can be active in any single period by looking at the processors running at that time.

Elias: That second guarantee is really interesting from a resource perspective. It’s not just about the total cost over time; it limits the simultaneous hardware usage during any given window.

Nadia: They show that these four conditions together are what deliver both of those guarantees, but they also prove that you can't get them all without violating one of the other three.

Priya: That’s a strong statement because it tells us exactly what kind of structure we need in our defense mechanism to actually achieve this desired scaling.

The paper's improvements: Nadia: The paper suggests several specific improvements on top of the basic concept, focusing heavily on how to actually build a defense that satisfies those four conditions. They suggest identity binding, freshness, a shared deadline, and sequential non-batchable work as the necessary checks.

Elias: I see they are proposing mechanisms where every identity has to deliver something verifiable in every window. Specifically, they suggest using an identity-bound verifiable delay function scheme without needing any payments.

Priya: That sounds like a significant practical step because if you can achieve that scaling cost through verifiable delay functions, it means the cost is baked into the protocol structure itself rather than relying on external incentives or payments.

Nadia: They detail how this works by requiring every identity to deliver the output of a verifiable delay function on an input derived from its key, which includes the period number and a fresh beacon value.

Elias: That requirement is what ties the cost model directly to the hardware's speed advantage, A. It ensures that even if an adversary uses super fast hardware, they still have to perform enough work proportional to their number of identities.

Priya: The way they structure the verification around these conditions—freshness and timeliness—seems designed specifically to bound simultaneous hardware usage down to s over A processors during a window.

Nadia: They also explore specific implementation choices, like using a verifiable delay function over class groups in chiavdf one point two.zero combined with an EUF-CMA secure signature and modeling the hash function as a random oracle to realize this identity-bound VDF scheme without payments <ref:2611.06268#pg1>.

Conclusion: Elias: So to wrap up, the paper "Beyond Identity Creation: Bilinear Sybil Cost in Identities and Time" shows that by imposing identity binding, freshness, a shared deadline, and sequential non-batchable work, you can guarantee a bilinear total cost where the cost is at least s times T divided by A.

Nadia: And crucially, this structure also provides a bound on the number of active identities in any period based on the processors running at that time. It's about controlling influence through verifiable computational work over time.

Priya: From my side, I’m just thinking about what they didn't cover deeply enough—the practical difficulty of implementing identity-bound VDFs in real-world blockchain consensus where you need high security without introducing new attack surfaces.

Elias: That is a fair point; the complexity of realizing those conditions practically is definitely something to watch for in future work. But the theoretical foundation they laid here about how cost scales with time and hardware speed advantage A is solid.

Nadia: Exactly, so we see this as a framework for designing defenses that focus on sustained influence rather than just initial identity creation. That's what this paper gives us to think about next.

Homayoun Maleki, Nekane Sainz, Jon Legarda, Igor Santos-Grueiro

DeustoTech University of Deusto Bilbao Spain · International University of La Rioja

cs.CR

Submitted: 2026-11-04

Updated: 2026-11-04

Comments: 16 pages, 4 figures. Main paper followed by the supplementary material. Submitted to IEEE Transactions on Information Forensics and Security

Code: https://github.com/Chia-Network/chia-blockchain

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: Sybil defenses price the creation of an identity, yet influence goes, again and again, to active identities The cost that matters is the cost of maintaining identities…

Key concepts

Bilinear Sybil Cost C(s, T)
This models the true cost of maintaining 's' identities active for 'T' periods. It is not just a creation fee but a cost that scales with both how many identities are active and how long they remain active. The goal is to show this cost grows at least as fast as sT divided by the adversary's speed advantage A.
Identity Binding
This condition ensures that an identity is cryptographically tied to a specific resource or process. It means the identity cannot be easily moved or duplicated without incurring a verifiable cost, making it harder for an attacker to simply generate many new identities freely.
Verifiable Delay Function (VDF)
A VDF is a cryptographic function that requires a specific amount of sequential time to compute, regardless of how fast the hardware is. Using VDFs ensures that every identity must perform work in a verifiable, time-consuming manner before it can be considered valid.
Freshness and Shared Deadline
Freshness means new work must be performed in each period. The shared deadline ensures all identities must complete this fresh work by the same common time. This combination forces the system to check every identity periodically, bounding the number of active processors at any given moment.

Summary

Sybil defenses price the creation of an identity, yet influence goes, again and again, to active identities The cost that matters is the cost of maintaining identities, as the distinction between stock and flow costs of attack in blockchains suggests A defense imposes a bilinear Sybil cost if keeping s identities active for T periods consumes at least a fixed amount of resource per identity and period This work gives four sufficient conditions for a defense that checks every identity each period to achieve bilinear Sybil cost: identity binding, freshness, a shared deadline, and sequential, non-batchable work They yield two guarantees: a bilinear total cost, with A the speed advantage of the adversary’s fastest hardware, and, because the work must be fresh and finished by a common deadline, a bound on the identities active in a period by the processors running at that time

Cost Modeling and Failure Modes

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improve Sybil defense cost modeling by shifting from a simple creation cost to a bilinear Sybil cost C(s, T) >= sT /A, which models maintenance as the cost of maintaining identities rather than just creation. This allows for more realistic analysis of long-term influence costs that scale with both the number of identities and the duration they remain active.

  2. Implement identity-bound verifiable delay function schemes to achieve a bilinear Sybil cost without payments, by requiring every identity in every window to deliver the output of a verifiable delay function (VDF) on an input derived from its key, the period number and a fresh beacon value. This ensures that the cost scales correctly with sT and provides a bound on simultaneous hardware usage.

  3. Design systems where the defense utilizes four sufficient conditions—identity binding, freshness, shared deadline, and sequential non-batchable work—to guarantee both a bilinear total cost C(s, T) >= sT /A and a bound on the identities active in a period by the processors running at that time. This allows for precise prediction of an adversary's maximum influence given their hardware capabilities.

  4. Develop protocols where the verification process uses a verifiable delay function (VDF) on an input derived from its key, the period number and a fresh beacon value, before a deadline that is the same for all identities, ensuring that work is fresh and finished by a common deadline. This condition helps bound simultaneous hardware usage to s/A processors during that window.

  5. Create verification mechanisms where no computation before ad can contribute to an accepted proof for window d (freshness) and Verify accepts a proof for window d only if rho shows that it was received by bd, the deadline shared by all identities (timeliness), ensuring work is completed inside one common slot per window. This fixes when the cost must be paid.

  6. Engineer systems where the verification scheme utilizes a VDF over class groups in chiavdf 1.2.0, combined with an EUF-CMA secure signature and a hash function modeled as a random oracle, to realize the identity-bound VDF scheme without payments. This provides a concrete realization for high-security environments like blockchain consensus protocols.

  7. Implement resource tracking where the cost is measured in processor time, stating the guarantee in resource units and leave money out on purpose, focusing on what an adversary cannot buy: time inside a slot. This allows for economic analysis based purely on computational effort rather than variable market prices.

  8. Integrate mechanisms that limit how many registered keys an adversary can keep active, bounding it by A per processor in each window, complementing creation defenses by controlling the activity of existing identities. This limits the adversary's ability to eclipse honest nodes or fill committees.

  9. Design systems where the speed ratio A is small (2 to 8 for CPUs), ensuring that one device replaces many honest ones and that A is small, which prevents one device from replacing thousands of honest participants against N = 10,000 honest participants. This ensures the bound on simultaneous hardware is meaningful.

  10. Develop mechanisms where a defense violates a condition in a predictable way, allowing for rapid identification of weaknesses in existing systems. For example, if identity binding (C1) is missing, an attacker accumulates them until it fills a committee or a victim’s routing table. This provides actionable intelligence for security architects.

Sources

Related papers