VerificationKey should not reject small-order points or the identity

[str4d]

VerificationKey::from(VerificationKeyBytes) currently rejects small-order points:

redjubjub/src/verification_key.rs

Lines 102 to 107 in 3db05e2

	// This checks that the verification key is not of small order.
	if <bool>::from(point.is_small_order()) == false {
	Ok(VerificationKey { point, bytes })
	} else {
	Err(Error::MalformedVerificationKey)
	}

This does not match the protocol spec, which defines RedDSA (and thus RedJubjub) public keys as elements of the represented group, not the subgroup (quotations below are from protocol spec version 2021.2.11):

• RedDSA and RedJubjub:

• Jubjub:

In particular, as a side-effect of the small-order check, the identity is being rejected by redjubjub as a valid VerificationKey encoding. However, SpendingKey does allow the all-zeroes spending key, from which the identity VerificationKey can be (and is) constructed:

redjubjub/src/verification_key.rs

Lines 139 to 146 in 3db05e2

	pub(crate) fn from(s: &Scalar) -> VerificationKey<T> {
	let point = &T::basepoint() * s;
	let bytes = VerificationKeyBytes {
	bytes: jubjub::AffinePoint::from(&point).to_bytes(),
	_marker: PhantomData,
	};
	VerificationKey { bytes, point }
	}

Rejecting small-order public keys does happen in the Zcash Sapling protocol, but not as part of the RedDSA signature scheme or its RedJubjub instantiation; it instead occurs as a consensus rule at the transaction level:

---

I encountered this bug in my RedDSA generalisation of this crate (#87), which I use to implement RedPallas. Pallas being a prime-order group, it doesn't have a small-order points to reject other than the identity, and there is not an Orchard consensus rule that rejects the identity for rk in Action descriptions:

I specifically encountered this bug when while debugging an unrelated issue, I set rcv = 0 for all of my Orchard spends and outputs, which resulted in bsk = 0 and a bvk of the identity. As redjubjub (and thus my fork) doesn't expose a way to construct a VerificationKey from a group element directly, I do the serialize-and-deserialize dance, which hit the bug.

[daira]

We need to make sure to preserve consensus compatibility with Sapling as currently implemented in zcashd when fixing this. In particular, as @str4d saw, the case bvk = 𝒪 can happen in practice. We may have to add a consensus rule to disallow this case for Sapling, if zcashd currently rejects it.

[daira]

We checked that zcashd implements RedJubjub according to the spec (as implemented by https://github.com/zcash/librustzcash/blob/master/zcash_primitives/src/sapling/redjubjub.rs), and so bvk = 𝒪 is accepted as it should be.

[dconnolly]

It's frustrating that we allow these sharp edges for RedJubjub, can someone help me grok why these small order points and the identity are explicitly allowed?

[daira]

Because there's no reason to reject them. Also rejecting them would make the use of RedDSA for balance signatures not complete: there you can't just avoid the zero private key, because the private key is a sum of blinding factors. (Yes the sum is zero only with negligible probability, but again, there's no reason to do so.)

[str4d]

Yeah, using RedDSA for binding signatures requires that the identity be permitted as a valid verification key, to ensure that it satisfies the definition of key monomorphism.

Meanwhile for spendAuth signatures we want the distribution of signing keys to be identical under re-randomization, and since RedDSA uses additive blinding, it is necessary to account for the zero scalar in that distribution (and thus the identity must be permitted as a valid verification key).

As for allowing small-order points as verification keys: the RedDSA verification equation requires multiplying by the cofactor, so any torsion components are eliminated by construction (ensuring that single and batch validation produce identical sets of valid signatures). Given that the identity is permitted, small-order verification keys are a subset of composite verification keys, and rejecting some but not all composite verification keys would make for a weird signature interface.

---

I dug up some history on this topic (and the motivations leading to the RedDSA design):

• [Sapling] Specify and implement the signature scheme for spend authorization zcash/zcash#2853
• Improve subgroup enforcements zcash/sapling-crypto#89

It indicates the motivation for adding the small-order checks was that we had wanted to operate uniformly in the prime-order subgroup of Jubjub where possible, but checking for that inside the circuit was deemed too expensive, so we rejected small-order points as a general layer of defense. It was probably overly conservative in hindsight, but given the overall level of complexity of Sapling, it was a reasonable decision at the time. Also note that originally RedDSA was not going to use the cofactor validation equation, so that might have contributed to the earlier concerns and decisions.

There might also have been concerns specifically related to not allowing the identity inside the circuit itself, but I wasn't involved enough in the circuit discussions at the time to know off-hand what those might have been. In any case, for Orchard we correctly handle [0]B in the circuit, so it does not provide any motivation to reject rk being the identity.

[dconnolly]

Note to self: add docs about why 0 is allowed (additive homomorphism for blinding, for the re-randomization)