Are sipa's standardized schnorr signatures incompatible with blind signatures?

Question

Here, sipa proposes a standardization of schnorr signatures: https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

For example, sign() returns Sig{R,s} which can be encoded with 64 bytes (R.x || s) where R.y can be disambiguated via quadratic residue.

After implementing sign() and verify() according to that document, I attempted to implement blind signatures.

However, verifying my unblinded signature fails 50% of the time because of the line return false if jacobi(R.y) !== 1 in verify(), enclosed below.

Here's my pseudocodey impl:

type Signature = { Rx: int, s: int }
type Unblinder = { alpha: int, Rx: int }
type BlindedMessage = { challenge: int }
type BlindedSignature = { s: int }

fn blindMessage(nonce: Point, signer: Point, message: bytes): (Unblinder, BlindedMessage) {
    R = nonce
    P = signer
    alpha = rand()
    beta = rand()
    R' = R + alpha*G + beta*P
    // challenge
    c' = int(hash(R'.x || P || message)) % curve.n
    // blinded challenge
    c = c' + beta
    return (Unblinder(alpha, R'.x), BlindedMessage(c))
}

fn blindSign(signer: privkey, nonce: privkey, blindedMessage: BlindedMessage): BlindedSignature {
    c = blindedMessage.challenge
    x = signer
    k = nonce

    s = k + c*x
    return BlindedSignature(s)
}

fn unblind(unblinder: Unblinder, blindedSig: BlindedSignature): Signature {
    Rx = unblinder.Rx
    s = blindedSig.s + unblinder.alpha
    return Signature(Rx, s)
} 

// implemented according to sipa's spec
fn verify(pubkey: Point, message: bytes, sig: Signature): bool {
    pk = pubkey
    m = message
    P = pubkey

    (r, s) = sig
    e = int(hash(r || P || m)) % curve.n
    R = s*G - e*P

    return false if isInfinitePoint(R)
    return false if jacobi(R.y) !== 1 // <-- Fails 50% here
    return false if R.x !== r
    return true
}

Here's the test that will fail 50% of the time:

noncePriv = rand()
signerPriv = rand()
noncePub = noncePriv * curve.G
signerPub = signerPriv * curve.G
message = hash('my message')

// blind
(unblinder, blindedMessage) = blindMessage(noncePub, signerPub, message)

// sign
blindedSig = blindSign(signerPriv, noncePriv, blindedMessage)

// unblind 
sig = unblind(unblinder, blindedSig)

// verify
verified = verify(signerPub, message, sig)

assert(verified)

The spec's sign() uses nonce = jacobi(y) === 1 ? nonce : curve.N - nonce to force a quadratic residue y, and I would assume my test fails because 50% of the time it generates a non-residue y. However, I was unable to figure out where and how to apply this in my blind-related code. None of my efforts had an effect on my 50% pass rate.

Answer 1

Andrew Poelstra suggests that:

R' = R + alpha*G + beta*G

should be put in a loop .. whenever R.x is not a quadratic residue. You can change beta and this should give you compat with sipa's scheme with no security, privacy loss or blind-sig-linkability loss