[ZIP 304] Sapling Address Signatures (signmessage/verifymessage support)

[daira]

From zcash/zcash#1770 (comment) :

I confirmed that we can use the Sapling Spend circuit without modification to support signing.

The signer creates a fake note (with value 1 zatoshi; not zero) and a Spend proof for a fake commitment tree that has this note's commitment at position 0. It also reveals the opening of the fake note commitment, and a signature verifiable by the RedJubjub verification key rk that is a public input to the proof. This shows that the signer is authorized to spend for the diversified address corresponding to (g_d, pk_d) in the note commitment.

So, a signature is (d, pk_d, rcm, cv, rt, nf, rk, π, σ, M) such that:

• g_d = DiversifyHash(d) ≠ ⊥
• the same point validity checks are applied as for a Spend description
• ZKSpend.Verify((cv, rt, nf, rk), π) = 1
• NoteCommit^Sapling_rcm(repr_J(g_d), repr_J(pk_d), 1) = cm
• rt is the anchor of a fake Merkle tree with cm at position 0 (and no other entries)
• SpendAuthSig.Verify_rk(M, σ) = 1

The size overhead, excluding the message, of such a signature is 43 (size of Sapling diversified address) + 32 (size of rcm) + 384 (size of Spend description) = 459 bytes. It could be 43 + 32 (size of rk) + 192 (size of proof) + 64 (size of RedJubjub signature) = 331 bytes if we used a dedicated circuit that made (g_d, pk_d) public and so didn't need rcm, cv, rt or nf.

This is a non-consensus feature that does not block Sapling, but takes advantage of it. (There was no way to implement signmessage/verifymessage for Sprout z-addresses.)

[daira]

Outline of the ZIP:

• Header/Abstract
• Motivation
• Specification
  • Reference needed abstractions from protocol spec (DiversifyHash, ZKSpend, NoteCommit^Sapling, repr_J, SpendAuthSig, Merkle tree)
  • Define abstract form of a signmessage signature
  • Define signing algorithm
  • Define verifying algorithm
  • Define external signature format
  • Message format (arbitrary byte sequence with domain separation?)
  • RPC calls
    • Extend to allow domain separation?
• Link to reference implementation
• References

[daira]

See ZIP number assigned for existing ZIP number assignments in the 3xx range.

[str4d]

The size overhead, excluding the message, of such a signature is 43 (size of Sapling diversified address) + 32 (size of rcm) + 384 (size of Spend description) = 459 bytes. It could be 43 + 192 (size of proof) + 64 (size of RedJubjub signature) = 299 bytes if we used a dedicated circuit that made (gd, pkd) public and so didn't need rcm, cv, rt or nf.

For this kind of signature, the Sapling diversified address is acting as the "signing public key", so doesn't need to be counted as part of the signature. That brings the signature size down to 416 bytes (or 256 bytes with a dedicated circuit).

[Edit by @daira: the quoted text has an error in the computation of the size for the dedicated circuit case; it should have included 32 bytes for rk.]

[daira]

As mentioned on zcash/zcash#1770, it's possible to set rcm to zero (credit to @ebfull) and rcv to zero, then rcm, cv and rt can be omitted from the signature, bringing it down to 320 bytes –i.e. (nf, rk, π, σ)– without a dedicated circuit.

This narrows the gap in signature overhead to the variant using a specialised circuit, which actually requires 288 bytes because it still needs to include rk.

[daira]

signmessage encodes signatures as base64, so an encoded 320-byte signature would look like this:

F7T72py2QzFjpTHC5jIi3Aj1x7USDmrpc1unDRdM06zgLLSN/DAuQtkhSIQ++J+y0UK01XH824vEsZ7C
YHYXuu+W7kznDihvxzs0NfIqjyV8/t1thWVQw9SPwP0ubIhLCaJNSQrTqGuG2cNsTiHfJlqFEoTkvz9Y
bJnEhgVfn1NATTS/RKkHXl79sN9v4QCaWjRFBraHVbWM1EfAnBKJAC3gJDcj7ymLRsNso5EPPCNQ8Hlk
u33kjfyVuzxCw9BopZmJfFEqCRiBoYQGltZADBoV4ObkzVBb5ppJYA6In8erxk+XaQ2ScMp8ntF5u88y
Bde1DmaJ/OmJqPgm6kexSsLSvb0hO8urg6QR+2n7J3P6T3NAct2IEvvqJ5fl9O2TTx6qlKvtMxe5WeM4
CUkCMKwM+BWmPTwybI/7vz5UvBE=

which is not too unwieldy.

(Back in my day , we used to have to deal with RSA signatures that were about as long — e.g. a 2048-bit RSA signature would be 257 bytes.)

[daira]

It's obvious but worth saying explicitly: all of this still works when the signing key is on a separate hardware wallet. The hardware wallet is doing exactly the same thing it does for spend authorization, except that the signature will not be over a ZIP 243 sighash (it will be over a BLAKE2b-256 hash with personalization other than "ZcashSigHash" || CONSENSUS_BRANCH_ID).