Bulletproofs

Logarithmic-size inner-product argument and the single and batched range proofs built on top of it — plus the exported-API gap that currently makes the range layer callable only from inside the package.

bulletproof implements the protocol of eprint 2017/1066 in two layers, and the distinction between them is the most important thing on this page.

The inner-product argument (IPP) is the engine. It proves knowledge of two scalar vectors whose dot product is a claimed value, in proof size logarithmic in the vector length: a length-256 pair of vectors yields 8 pairs of L/R points, not 256.

The range proof is the application. It encodes a secret value as its bit vector, expresses “every bit is 0 or 1, and the bits sum to the committed value” as a single inner-product relation, and then delegates to the IPP. That is why one prover constructor takes two domain separators — the range layer and the IPP layer each need their own generator vectors.

When to use it

Range proofs are the right tool when a committed number must be shown to be well-formed without being revealed — confidential amounts that must be non-negative and non-overflowing, bounded bids, reserve proofs. The batched variant is the right tool when several such values are proved at once by the same party, because it amortises them into a single proof.

They are the wrong tool for set membership (use the accumulator), for proving knowledge of a discrete log (use Schnorr, which is orders of magnitude smaller and simpler), or for arbitrary statements — there is no general-purpose circuit layer here.

Layer 1: the inner-product argument

MarshalBinary() []byte on both InnerProductProof and RangeProof returns no error — an unusual signature that does not satisfy encoding.BinaryMarshaler. UnmarshalBinary does return an error, and must be called on a proof from the matching New…Proof(curve) constructor so that the curve is set.

// From bulletproof/ipp_verifier_test.go (TestIPPVerifyHappyPath).
curve := curves.ED25519()
vecLength := 256

prover, err := bulletproof.NewInnerProductProver(vecLength, []byte("test"), *curve)
if err != nil {
	panic(err)
}

a := randScalarVec(vecLength, *curve) // in-package test helper
b := randScalarVec(vecLength, *curve)
u := curve.Point.Random(crand.Reader)

transcriptProver := merlin.NewTranscript("test")
proof, err := prover.Prove(a, b, u, transcriptProver)
if err != nil {
	panic(err)
}
// len(proof.capLs) == log2(256) == 8

verifier, err := bulletproof.NewInnerProductVerifier(vecLength, []byte("test"), *curve)
if err != nil {
	panic(err)
}
capP, err := prover.getP(a, b, u) // unexported: see the danger callout
if err != nil {
	panic(err)
}
transcriptVerifier := merlin.NewTranscript("test")
verified, err := verifier.Verify(capP, u, proof, transcriptVerifier)
// verified == true

The Fiat-Shamir transcript is merlin. Both sides construct it with the same label — merlin.NewTranscript("test") in the tests — and each side must start from a fresh transcript in the same state. A transcript is consumed by proving or verifying; you cannot reuse one.

Layer 2: range proofs

What the parameters actually mean

n is a bit width, and it defines the range. Prove decodes v into an n-element bit vector via getaL, so the provable range is the set of values representable in n bits: [0, 2^n). n = 256 on ED25519 is the whole scalar field; n = 64 is a u64-shaped amount. n must be a power of two, because the inner-product recursion halves the vectors at every step. The range prover does not check this up front — unlike InnerProductProver.Prove, which has an explicit isPowerOfTwo gate — so a non-power-of-two n surfaces late as "length of scalars must be even" from inside the recursion.

maxVectorLength is a generator budget, not the range. The constructor precomputes 2 · maxVectorLength curve points by hashing the domain. Prove requires n <= maxVectorLength and trims the generator vectors to n. BatchProve requires n · len(v) <= maxVectorLength — proving four 256-bit values needs NewRangeProver(256*4, …), exactly as range_batch_prover_test.go does.

The two domains seed two independent generator sets. rangeDomain produces the G/H vectors that commit to the bit vectors; ippDomain produces the generators for the nested inner-product argument. They must be distinct strings — reusing one string for both would make the two generator sets identical, which is not a configuration the protocol’s security argument covers. The tests use []byte("rangeDomain") and []byte("ippDomain").

proofGenerators holds g, h, u, and both sides must use the same three points. g and h are the Pedersen bases for the value commitment; u blinds the inner product. Because the commitment capV = gamma·h + v·g is computed from g and h, a verifier with different points is verifying a commitment to a different value and gets false.

Single-value range proof

Grounded in bulletproof/range_prover_test.go and range_verifier_test.go. The unexported identifiers are marked; they are why this cannot be lifted verbatim into your own package.

curve := curves.ED25519()
n := 256

prover, err := bulletproof.NewRangeProver(n, []byte("rangeDomain"), []byte("ippDomain"), *curve)
if err != nil {
	panic(err)
}

v := curve.Scalar.Random(crand.Reader)     // the secret value
gamma := curve.Scalar.Random(crand.Reader) // the secret blinding factor

g := curve.Point.Random(crand.Reader)
h := curve.Point.Random(crand.Reader)
u := curve.Point.Random(crand.Reader)
proofGenerators := RangeProofGenerators{g: g, h: h, u: u} // unexported fields

transcript := merlin.NewTranscript("test")
proof, err := prover.Prove(v, gamma, n, proofGenerators, transcript)
if err != nil {
	panic(err)
}

// Verifier: same n, same domains, same curve, same g/h/u, fresh transcript
// with the same label.
verifier, err := bulletproof.NewRangeVerifier(n, []byte("rangeDomain"), []byte("ippDomain"), *curve)
if err != nil {
	panic(err)
}
transcriptVerifier := merlin.NewTranscript("test")
capV := getcapV(v, gamma, g, h) // unexported: h.Mul(gamma).Add(g.Mul(v))
verified, err := verifier.Verify(proof, capV, proofGenerators, n, transcriptVerifier)
// verified == true

In production the verifier receives capV over the wire; it never learns v or gamma. The commitment is a plain Pedersen commitment, h·gamma + g·v, so you can compute it yourself with core/curves point arithmetic without touching this package.

Batched range proof

BatchProve proves m values in one proof. From range_batch_prover_test.go, four 256-bit values:

curve := curves.ED25519()
n := 256

// maxVectorLength must cover n * m = 1024.
prover, err := bulletproof.NewRangeProver(n*4, []byte("rangeDomain"), []byte("ippDomain"), *curve)
if err != nil {
	panic(err)
}

v := []curves.Scalar{
	curve.Scalar.Random(crand.Reader),
	curve.Scalar.Random(crand.Reader),
	curve.Scalar.Random(crand.Reader),
	curve.Scalar.Random(crand.Reader),
}
gamma := []curves.Scalar{
	curve.Scalar.Random(crand.Reader),
	curve.Scalar.Random(crand.Reader),
	curve.Scalar.Random(crand.Reader),
	curve.Scalar.Random(crand.Reader),
}

transcript := merlin.NewTranscript("test")
proof, err := prover.BatchProve(v, gamma, n, proofGenerators, transcript)
if err != nil {
	panic(err)
}
// One proof, log2(1024) == 10 L/R pairs, covering all four values.

verifier, _ := bulletproof.NewRangeVerifier(n*4, []byte("rangeDomain"), []byte("ippDomain"), *curve)
capV := getcapVBatched(v, gamma, g, h) // unexported; one commitment per value
verified, err := verifier.VerifyBatched(proof, capV, proofGenerators, n, merlin.NewTranscript("test"))
// verified == true

Note that the batch call still takes the per-value bit width n, while the prover was constructed with n*4. Mixing those two up is the easiest way to get a confusing failure. VerifyBatched returns an error (rather than false) if a commitment in capV is tampered with in a way that breaks the point arithmetic — range_batch_verifier_test.go exercises that path — but a merely wrong proof still comes back as (false, nil).

Caveats

Related