MuSig2 Spec Test

musig_spec.py

import hashlib
import secrets

from ec import *
from util import *

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

def is_infinite(P):
    return P.infinity

def x_(P):
    return P.x.a

def y_(P):
    return P.y.a

assert x_(G) == 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
assert y_(G) == 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

def bytes_i(x):
    return int_to_b32(x)

def bytes_p(P):
    return bytes_i(x_(P))

def has_even_y(P):
    return y_(P) % 2 == 0

def cbytes(P):
    a = 0x02 if has_even_y(P) else 0x03
    return [a] + bytes_p(P)

def _int(x):
    return b32_to_int(x)

def lift_x(x):
    assert x >= 0 and x <= p - 1
    c = (pow(x, 3, p) + 7) % p
    y_ = pow(c, (p + 1) // 4, p)
    assert c == pow(y_, 2, p)
    y = y_ if y_ % 2 == 0 else p - y_
    return GE(FE(x), FE(y))

def point(x):
    return lift_x(_int(x))

def pointc(x):
    P = lift_x(_int(x[1:33]))
    assert x[0] in (0x02, 0x03)
    return P if x[0] == 0x02 else -P

def tagged_hash(tag, x):
    m = tagged_hash_init(bytes(tag, 'utf8'))
    m.update(bytes(x))
    return list(m.digest())

def KeyAgg(pk_list):
    Q = KeyAggInternal(pk_list)
    return bytes_p(Q)

def KeyAggInternal(pk_list):
    Q = INFINITY
    for pk_i in pk_list:
        a_i = KeyAggCoeff(pk_list, pk_i)
        P_i = point(pk_i)
        Q += a_i * P_i
    assert not is_infinite(Q)
    return Q

def HashKeys(pk_list):
    return tagged_hash('KeyAgg list', sum(pk_list, []))

def IsSecond(pk_list, pk):
    for pk_j in pk_list:
        if pk_j != pk_list[0]:
            return pk_j == pk
    return False

def KeyAggCoeff(pk_list, pk):
    L = HashKeys(pk_list)
    if IsSecond(pk_list, pk):
        return 1
    else:
        return _int(tagged_hash('KeyAgg coefficient', L + pk)) % n

def NonceGen():
    k_1 = 1 + secrets.randbelow(n - 2)
    k_2 = 1 + secrets.randbelow(n - 2)
    R_1 = k_1 * G
    R_2 = k_2 * G
    pubnonce = cbytes(R_1) + cbytes(R_2)
    secnonce = bytes_i(k_1) + bytes_i(k_2)
    return secnonce, pubnonce

def NonceAgg(pubnonce_list):
    aggnonce = []
    for i in (1, 2):
        R_i_ = INFINITY
        for pubnonce_j in pubnonce_list:
            R_ij = pointc(pubnonce_j[(i-1)*33:i*33])
            R_i_ += R_ij
        R_i = R_i_ if not is_infinite(R_i_) else G
        aggnonce += cbytes(R_i)
    return aggnonce

def Sign(secnonce, sk, aggnonce, pk_list, m):
    R_1 = pointc(aggnonce[0:33])
    R_2 = pointc(aggnonce[33:66])
    Q = KeyAggInternal(pk_list)
    b = _int(tagged_hash('MuSig/noncecoef', aggnonce + bytes_p(Q) + m)) % n
    R = R_1 + b * R_2
    assert not is_infinite(R)
    k_1_ = _int(secnonce[0:32])
    k_2_ = _int(secnonce[32:64])
    assert 0 < k_1_ < n
    assert 0 < k_2_ < n
    k_1, k_2 = (k_1_, k_2_) if has_even_y(R) else (n - k_1_, n - k_2_)
    d_ = _int(sk)
    assert 0 < d_ < n
    P = d_ * G
    d = n - d_ if has_even_y(P) != has_even_y(Q) else d_
    e = _int(tagged_hash('BIP0340/challenge', bytes_p(R) + bytes_p(Q) + m)) % n
    mu = KeyAggCoeff(pk_list, bytes_p(P))
    s = (k_1 + b * k_2 + e * mu * d) % n
    psig = bytes_i(s)
    pubnonce = cbytes(k_1_ * G) + cbytes(k_2_ * G)
    PartialSigVerifyInternal(psig, pubnonce, aggnonce, pk_list, bytes_p(P), m)
    return psig

def PartialSigVerify(psig, pubnonce_list, pk_list, m, i):
    aggnonce = NonceAgg(pubnonce_list)
    PartialSigVerifyInternal(psig, pubnonce_list[i], aggnonce, pk_list, pk_list[i], m)

def PartialSigVerifyInternal(psig, pubnonce, aggnonce, pk_list, pk, m):
    s = _int(psig)
    assert s < n
    R_1 = pointc(aggnonce[0:33])
    R_2 = pointc(aggnonce[33:66])
    Q = KeyAggInternal(pk_list)
    b = _int(tagged_hash('MuSig/noncecoef', aggnonce + bytes_p(Q) + m)) % n
    R = R_1 + b * R_2
    R_1_ = pointc(pubnonce[0:33])
    R_2_ = pointc(pubnonce[33:66])
    R__ = R_1_ + b * R_2_
    R_ = R__ if has_even_y(R) else -R__
    e = _int(tagged_hash('BIP0340/challenge', bytes_p(R) + bytes_p(Q) + m)) % n
    mu = KeyAggCoeff(pk_list, pk)
    P_ = point(pk)
    P = P_ if has_even_y(Q) else -P_
    assert s * G == R_ + e * mu * P

def SigAgg(R, sig_list):
    s = 0
    for sig_i in sig_list:
        s_i = _int(sig_i)
        assert s_i <= n
        s = (s + s_i) % n
    return s

musig_test_vectors.py

from musig_spec import *

X1 = [
    0xF9, 0x30, 0x8A, 0x01, 0x92, 0x58, 0xC3, 0x10,
    0x49, 0x34, 0x4F, 0x85, 0xF8, 0x9D, 0x52, 0x29,
    0xB5, 0x31, 0xC8, 0x45, 0x83, 0x6F, 0x99, 0xB0,
    0x86, 0x01, 0xF1, 0x13, 0xBC, 0xE0, 0x36, 0xF9,
]

X2 = [
    0xDF, 0xF1, 0xD7, 0x7F, 0x2A, 0x67, 0x1C, 0x5F,
    0x36, 0x18, 0x37, 0x26, 0xDB, 0x23, 0x41, 0xBE,
    0x58, 0xFE, 0xAE, 0x1D, 0xA2, 0xDE, 0xCE, 0xD8,
    0x43, 0x24, 0x0F, 0x7B, 0x50, 0x2B, 0xA6, 0x59,
]

X3 = [
    0x35, 0x90, 0xA9, 0x4E, 0x76, 0x8F, 0x8E, 0x18,
    0x15, 0xC2, 0xF2, 0x4B, 0x4D, 0x80, 0xA8, 0xE3,
    0x14, 0x93, 0x16, 0xC3, 0x51, 0x8C, 0xE7, 0xB7,
    0xAD, 0x33, 0x83, 0x68, 0xD0, 0x38, 0xCA, 0x66,
]

def test_keyagg():
    expected = [
        [
            0xE5, 0x83, 0x01, 0x40, 0x51, 0x21, 0x95, 0xD7,
            0x4C, 0x83, 0x07, 0xE3, 0x96, 0x37, 0xCB, 0xE5,
            0xFB, 0x73, 0x0E, 0xBE, 0xAB, 0x80, 0xEC, 0x51,
            0x4C, 0xF8, 0x8A, 0x87, 0x7C, 0xEE, 0xEE, 0x0B,
        ],
        [
            0xD7, 0x0C, 0xD6, 0x9A, 0x26, 0x47, 0xF7, 0x39,
            0x09, 0x73, 0xDF, 0x48, 0xCB, 0xFA, 0x2C, 0xCC,
            0x40, 0x7B, 0x8B, 0x2D, 0x60, 0xB0, 0x8C, 0x5F,
            0x16, 0x41, 0x18, 0x5C, 0x79, 0x98, 0xA2, 0x90,
        ],
        [
            0x81, 0xA8, 0xB0, 0x93, 0x91, 0x2C, 0x9E, 0x48,
            0x14, 0x08, 0xD0, 0x97, 0x76, 0xCE, 0xFB, 0x48,
            0xAE, 0xB8, 0xB6, 0x54, 0x81, 0xB6, 0xBA, 0xAF,
            0xB3, 0xC5, 0x81, 0x01, 0x06, 0x71, 0x7B, 0xEB,
        ],
        [
            0x2E, 0xB1, 0x88, 0x51, 0x88, 0x7E, 0x7B, 0xDC,
            0x5E, 0x83, 0x0E, 0x89, 0xB1, 0x9D, 0xDB, 0xC2,
            0x80, 0x78, 0xF1, 0xFA, 0x88, 0xAA, 0xD0, 0xAD,
            0x01, 0xCA, 0x06, 0xFE, 0x4F, 0x80, 0x21, 0x0B,
        ],
    ]

    assert KeyAgg([X1, X2, X3]) == expected[0]
    assert KeyAgg([X3, X2, X1]) == expected[1]
    assert KeyAgg([X1, X1, X1]) == expected[2]
    assert KeyAgg([X1, X1, X2, X2]) == expected[3]

def test_sign():
    secnonce = [
        0x50, 0x8B, 0x81, 0xA6, 0x11, 0xF1, 0x00, 0xA6,
        0xB2, 0xB6, 0xB2, 0x96, 0x56, 0x59, 0x08, 0x98,
        0xAF, 0x48, 0x8B, 0xCF, 0x2E, 0x1F, 0x55, 0xCF,
        0x22, 0xE5, 0xCF, 0xB8, 0x44, 0x21, 0xFE, 0x61,
        0xFA, 0x27, 0xFD, 0x49, 0xB1, 0xD5, 0x00, 0x85,
        0xB4, 0x81, 0x28, 0x5E, 0x1C, 0xA2, 0x05, 0xD5,
        0x5C, 0x82, 0xCC, 0x1B, 0x31, 0xFF, 0x5C, 0xD5,
        0x4A, 0x48, 0x98, 0x29, 0x35, 0x59, 0x01, 0xF7,
    ]

    agg_pubnonce = [
        0x02,
        0x84, 0x65, 0xFC, 0xF0, 0xBB, 0xDB, 0xCF, 0x44,
        0x3A, 0xAB, 0xCC, 0xE5, 0x33, 0xD4, 0x2B, 0x4B,
        0x5A, 0x10, 0x96, 0x6A, 0xC0, 0x9A, 0x49, 0x65,
        0x5E, 0x8C, 0x42, 0xDA, 0xAB, 0x8F, 0xCD, 0x61,
        0x03,
        0x74, 0x96, 0xA3, 0xCC, 0x86, 0x92, 0x6D, 0x45,
        0x2C, 0xAF, 0xCF, 0xD5, 0x5D, 0x25, 0x97, 0x2C,
        0xA1, 0x67, 0x5D, 0x54, 0x93, 0x10, 0xDE, 0x29,
        0x6B, 0xFF, 0x42, 0xF7, 0x2E, 0xEE, 0xA8, 0xC9,
    ]

    sk = [
        0x7F, 0xB9, 0xE0, 0xE6, 0x87, 0xAD, 0xA1, 0xEE,
        0xBF, 0x7E, 0xCF, 0xE2, 0xF2, 0x1E, 0x73, 0xEB,
        0xDB, 0x51, 0xA7, 0xD4, 0x50, 0x94, 0x8D, 0xFE,
        0x8D, 0x76, 0xD7, 0xF2, 0xD1, 0x00, 0x76, 0x71,
    ]

    m = [
        0xF9, 0x54, 0x66, 0xD0, 0x86, 0x77, 0x0E, 0x68,
        0x99, 0x64, 0x66, 0x42, 0x19, 0x26, 0x6F, 0xE5,
        0xED, 0x21, 0x5C, 0x92, 0xAE, 0x20, 0xBA, 0xB5,
        0xC9, 0xD7, 0x9A, 0xDD, 0xDD, 0xF3, 0xC0, 0xCF,
    ]

    P_ = b32_to_int(sk) * G
    X = bytes_p(P_)

    expected = [
        [
            0x68, 0x53, 0x7C, 0xC5, 0x23, 0x4E, 0x50, 0x5B,
            0xD1, 0x40, 0x61, 0xF8, 0xDA, 0x9E, 0x90, 0xC2,
            0x20, 0xA1, 0x81, 0x85, 0x5F, 0xD8, 0xBD, 0xB7,
            0xF1, 0x27, 0xBB, 0x12, 0x40, 0x3B, 0x4D, 0x3B,
        ],
        [
            0x2D, 0xF6, 0x7B, 0xFF, 0xF1, 0x8E, 0x3D, 0xE7,
            0x97, 0xE1, 0x3C, 0x64, 0x75, 0xC9, 0x63, 0x04,
            0x81, 0x38, 0xDA, 0xEC, 0x5C, 0xB2, 0x0A, 0x35,
            0x7C, 0xEC, 0xA7, 0xC8, 0x42, 0x42, 0x95, 0xEA,
        ],
        [
            0x0D, 0x5B, 0x65, 0x1E, 0x6D, 0xE3, 0x4A, 0x29,
            0xA1, 0x2D, 0xE7, 0xA8, 0xB4, 0x18, 0x3B, 0x4A,
            0xE6, 0xA7, 0xF7, 0xFB, 0xE1, 0x5C, 0xDC, 0xAF,
            0xA4, 0xA3, 0xD1, 0xBC, 0xAA, 0xBC, 0x75, 0x17,
        ],
    ]

    assert Sign(secnonce, sk, agg_pubnonce, [X, X1, X2], m) == expected[0]
    assert Sign(secnonce, sk, agg_pubnonce, [X1, X, X2], m) == expected[1]
    assert Sign(secnonce, sk, agg_pubnonce, [X1, X2, X], m) == expected[2]

def test_partial_sig_verify():
    N = 4
    for i in range(N):
        sk_1 = list(secrets.token_bytes(32))
        sk_2 = list(secrets.token_bytes(32))
        pk_1 = bytes_p(b32_to_int(sk_1) * G)
        pk_2 = bytes_p(b32_to_int(sk_2) * G)
        pk_list = [pk_1, pk_2]

        secnonce_1, pubnonce_1 = NonceGen()
        secnonce_2, pubnonce_2 = NonceGen()
        pubnonce_list = [pubnonce_1, pubnonce_2]

        agg_pubnonce = NonceAgg(pubnonce_list)

        m = list(secrets.token_bytes(32))

        psig = Sign(secnonce_1, sk_1, agg_pubnonce, pk_list, m)
        PartialSigVerify(psig, pubnonce_list, pk_list, m, 0)

        verifyFail = False
        try:
            # Wrong public key
            PartialSigVerify(psig, pubnonce_list, pk_list, m, 1)
        except AssertionError:
            verifyFail = True
        assert verifyFail

test_keyagg()
test_sign()
test_partial_sig_verify()