Figure out how to safely upgrade to libsodium 1.0.16+

[daira]

libsodium 1.0.16 introduces changes to Ed25519 and Curve25519 point validation: jedisct1/libsodium#662 . These could be used to provoke a chain fork if we were to naively upgrade. Some of the changes are disabled if ED25519_COMPAT is set; some are not.

[per-gron]

(Let me know if this is too obvious to be helpful)

Assuming that the breaking changes are actually good, if not for the fact that they can cause undesired forks, maybe one way is to upgrade in an orderly manner:

Assuming that zcash will have regular planned hard forks, is to make libsodium upgrades as part of hard forks. The next one is in June, no? The build system magic needed to support two libsodium versions in parallel (to be able to pull off the fork) might not be all that bad.

Another thing that could make sense to do is to ask the libsodium maintainers to conform to semantic versioning: It seems to me like 1.0.16 maybe should have been 2.0 if they followed semver. It doesn't solve anything in itself but at least it helps awareness. (Changing the major version doesn't have to be a big deal or entail a rewrite; it's okay to have large version numbers)

[str4d]

Assuming that zcash will have regular planned hard forks, is to make libsodium upgrades as part of hard forks. The next one is in June, no? The build system magic needed to support two libsodium versions in parallel (to be able to pull off the fork) might not be all that bad.

This is likely how we'd implement it. We'd need to either bundle two libsodium versions, or patch libsodium to provide both the older and newer rules. I think the latter would likely be simpler and cleaner.

After the upgrade is complete and the activation block is established, we could inspect the pre-upgrade chain to see if any old transactions are broken under the newer libsodium rules, and if not then just use the newer version with the older blocks (enabling us to drop the second bundled version, or the source patch). This isn't technically valid if we don't have checkpointing at epochs (because in theory a large reorg could introduce a problematic transaction before the activation height), but that kind of reorg would itself create a chain fork if we are far-enough in the future.

Another thing that could make sense to do is to ask the libsodium maintainers to conform to semantic versioning: It seems to me like 1.0.16 maybe should have been 2.0 if they followed semver. It doesn't solve anything in itself but at least it helps awareness. (Changing the major version doesn't have to be a big deal or entail a rewrite; it's okay to have large version numbers)

Certainly seems reasonable, but obviously out of scope for this issue (since they have already released 1.0.16).

[daira]

First we need to be clear about what changes are made in libsodium 1.0.16. I think the changes are:

1. Check for small-order points before, rather than after, scalar multiplications. This does not affect compatibility and in principle could help security against some side channel attacks; it also simplifies reasoning about optimizations performed in the multiplication code.

2. Check that Ed25519 public keys and input base points to Edwards scalar multiplication are "canonical". (It is not clear whether the latter applies to signatures, the control flow is a bit convoluted and there are lots of variants of scalar mult.) This cannot improve security, because a publically computable transformation on the public key and R point (reducing the y-coordinate representation modulo 2²⁵⁵-19) would make the check always pass. See also Changes in signature & public key validation for 1.0.16 cause problems for uses requiring strict consensus jedisct1/libsodium#662 (comment) .

Change 1 is applied to both Ed25519 and Curve25519. Change 2 affects only Ed25519. This is important because we use both in Zcash.

It is possible to make libsodium 1.0.16 behave like previous versions wrt change 2 by performing exactly the public transformation mentioned above before verifying a signature. We need a test that this works. (It may be nontrivial to write the test because we need to find a valid signature with a noncanonical public key that is not a point of low order, or possibly force a noncanonical base point to a multiplication.)

[daira]

jedisct1/libsodium#662 has been closed, so it looks like we're on our own with this :-(

We could have made this consensus change in Sapling (i.e. redundantly perform the additional check on public keys gated on Sapling activation, and then upgrade libsodium after Sapling activation), but we didn't. Sapling was certainly complicated enough already, so it would have been a reasonable decision not to do this, even if we'd remembered that the issue existed.

For the time being we should be prepared to backport any security fixes from after libsodium 1.0.15. There haven't been any releases since 1.0.16 at the time of writing this, and 1.0.16 has no security fixes. However, if there were a libsodium security flaw that affected us then we'd have to add a patch to the depends system rather than upgrading.

[str4d]

The other option is that we add a patch to the depends system now that makes the changes necessary for jedisct1/libsodium#662 (adding the config option etc.), and upgrade to 1.0.16, while we aren't under the stress of a security incident. Then in the case of a libsodium security flaw, we can very likely just upgrade (possibly with some merge conflict resolution against our patch), and if we can't then we're back where we would have been anyway.

[str4d]

@daira and I confirmed that the change to Ed25519 public key validation in libsodium 1.0.16 is a consensus-breaking change (the other Ed25519 changes do not affect us, and we have not fully-analysed the X25519 changes but they don't affect consensus, only the ability of users to detect Sprout funds). @jedisct1 was correct when saying that the set of valid signatures did not change in 1.0.16, because the signatures themselves were already constrained to be canonical; ...

[Edit by @daira: Actually there was a bug in libsodium's checking for small-order points that was later fixed (I'm not sure it was fixed in 1.0.16, but certainly by 1.0.18). So the set of valid signatures did change.]

... however, the public keys used to validate those signatures were not previously constrained to be canonical, and they are part of our consensus. (Incidentally, this change was partly-reverted for ED25519_COMPAT in 1.0.16, and then fully-reverted for ED25519_COMPAT in 1.0.17, presumably after someone noticed this was a breaking change there too).

The short-term fix for this is to write a depends-system patch for libsodium that removes the check, which will enable us to upgrade to current libsodium. We can then start constraining the public keys in a future network upgrade, and drop the patch once that NU has activated.

[daira]

It's also worth noting that it is not sufficient to canonicalize the public keys before passing them to libsodium signature validation, because:

• there is no way to canonicalize small-order points in a way that would be accepted by libsodium; and
• libsodium 1.0.15 hashes the public key as originally encoded when computing the hash internal to Ed25519.

[daira]

We'll also need to review all of the libsodium code that might rely on Ed25519 public keys being canonical. I don't anticipate a problem because in ED25519_COMPAT mode (which we do not use but the libsodium verification code must support), public key canonicity is not enforced.

[hdevalence]

In Zebra we've been planning to create an implementation of Zcash-flavored Ed25519 to avoid exactly this sort of problem (tracking issue: ZcashFoundation/zebra#109). Perhaps another way forward would be to switch zcashd to that implementation once it's complete?

[daira]

There's an issue of minimising dependencies: we currently use libsodium for other things, including Curve25519 and IETF_CHACHA20_POLY1305 for note encryption; and random number generation. If we could replace libsodium entirely with safe Rust, that would be nice. There's a difficult trade-off here between diversity of implementation and consensus compatibility — but I really don't like the status quo where we're just bug-for-bug compatible with undocumented subtleties of libsodium 1.0.15.

Fortunately the situation is much better with Sapling — we do rigourously specify point validation in Sapling even if it's a bit hairy and slightly inconsistent. (IETF_CHACHA20_POLY1305 is used in both Sprout and Sapling, but that's well-specified.) Anyone for just removing Sprout? <ducks/>

[daira]

I guess that I should clarify that we're not going to just destroy everyone's Sprout funds without plenty of warning. But as I've said before, it's not sustainable to maintain the protocol and implementation complexity of Sprout+Sapling forever.

[hdevalence]

I implemented basic functionality for ed25519-zebra yesterday, and made an issue with the edge cases that I was unclear about from reading the spec: ZcashFoundation/ed25519-zebra#1