Beyond Identity Creation: Bilinear Sybil Cost in Identities and Time

summary

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…

In short

The paper addresses how to price Sybil defenses by focusing on maintaining identities over time rather than just creating them. It proposes four sufficient conditions—identity binding, freshness, shared deadline, and sequential work—to achieve a bilinear cost model. This model guarantees a total cost scaling with the number of identities (s) and time (T), while bounding the maximum simultaneous hardware usage.

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.

Terminology used across episodes

This episode discusses

The paper

Beyond Identity Creation: Bilinear Sybil Cost in Identities and Time · Read on arXiv

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

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

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.

More episodes

← Home