From Bytes to Points: How Try-and-Increment and Elligator 2 Map to Curves#

In cryptography, encoding arbitrary data onto elliptic curves is a foundational requirement. Whether you're implementing Verifiable Random Functions (VRFs), digital signatures, or zero-knowledge proofs, the ability to deterministically map messages to curve points is crucial. This process, referred to as Encode to Curve, is formally specified in RFC 9380 and RFC 9381, which outline multiple encoding mechanisms. In this post, we’ll explore two prominent methods: Try-and-Increment and Elligator 2.

Elliptic curves operate over finite fields and represent points that satisfy a specific equation. To utilize a message within a cryptographic operation—like ECVRFs, commitment schemes, or zkSNARK-friendly constructions—it needs to be transformed into a valid point on the curve.

A direct mapping isn’t always straightforward because not every field element maps to a curve point. That’s where Encode-to-Curve mechanisms come in.

Intuition#

Try-and-Increment is arguably the most intuitive approach. Given a message m, we hash it and treat the output as an x-coordinate candidate. We then check whether this x corresponds to a valid point on the elliptic curve. If not, increment x and repeat until a valid point is found.

Algorithm#

1. Set a counter ctr = 0
2. Compute x = Hash(m || ctr)
3. Check if (x, y) satisfies the curve equation.
4. If yes, return the point (x, y).
5. Otherwise, increment ctr and repeat.

Pros#

• Simple to implement
• Works for most curves (Weierstrass, Edwards, Montgomery)

Cons#

• Non-uniform output distribution
• May leak timing side-channel information (variable loop count)
• Not constant-time

Use Case#

This method is historically used in VRF implementations (e.g., early ECVRFs in RFC 9381), where simplicity trumps constant-time concerns.

Intuition#

Elligator 2 is a mathematically richer alternative that maps a uniformly random field element to a curve point in a way that is indistinguishable from random. Unlike Try-and-Increment, it guarantees constant-time execution and avoids rejection sampling.

Elligator 2 is designed for Montgomery and Twisted Edwards curves (e.g., Curve25519, Bandersnatch) and uses a deterministic isogeny-based transformation.

Overview#

Given a message m, we:

1. Hash it to a field element u.
2. Use a deterministic map u -> (x, y) based on the curve equation.
3. Return (x, y) as the encoded point.

Key Properties#

• Constant-time: Same operations regardless of m
• Uniform: Output is statistically uniform over the curve
• Indistinguishability: The output points look random (great for privacy)

Pros#

• Ideal for ZK systems and high-security cryptosystems
• Prevents side-channel attacks

Cons#

• Harder to implement
• Only compatible with specific curve types (Montgomery, Twisted Edwards)

Use Case#

Widely used in privacy-preserving protocols (like VRF-ADs, SNARK-friendly VRFs), especially in zk-oriented systems using Bandersnatch or Jubjub.

• If your curve is Twisted Edwards (e.g., Bandersnatch) and you care about uniformity and timing attacks: go for Elligator 2.
• If you want simplicity or are working in a constrained environment: Try-and-Increment might suffice.

Encoding to a curve is far more than just hashing—it’s about ensuring mathematical soundness, cryptographic security, and practical feasibility. With protocols like SNARKs and VRFs becoming mainstream, understanding these encoding techniques is vital for any cryptographer or blockchain developer.

Whether you lean toward the brute-force clarity of Try-and-Increment or the elegant math of Elligator 2, both approaches offer crucial insight into how we bridge the gap from arbitrary bytes to secure elliptic curve points.