BIP-327: Fix reduction sketch for infinity in nonce aggregation #2354

pull real-or-random wants to merge 1 commits into bitcoin:master from real-or-random:202611-bip327-infinity-reduction changing 1 files +39 −6
  1. real-or-random commented at 11:59 AM on November 13, 2026: contributor

    The section "Dealing with Infinity in Nonce Aggregation" sketches a reduction from the unforgeability of the modified scheme, which sets the final nonce R to G whenever it would be the point at infinity, to the unforgeability of the original MuSig2* scheme. The sketch let the reduction translate aggnonce' = bytes(33, 0) || bytes(33, 0) into aggnonce = cbytes_ext(G) || bytes(33, 0). But the nonce coefficient b is derived by hashing the aggregate nonce, so the adversary expects a b computed from aggnonce' while the original game computes b from aggnonce. The resulting partial signatures do not match, and the sketch does not work as a black-box reduction.

    Replace the sketch with a reduction that programs the random oracles. For each pair of aggregate public key and message, it maps the three aggregate nonces whose final nonce is G or -G in the modified scheme, namely bytes(33, 0) || bytes(33, 0), cbytes(G) || bytes(33, 0), and cbytes(-G) || bytes(33, 0), to three aggregate nonces of its own choice whose final nonce in the original game is a random W or -W, and it swaps xbytes(G) with xbytes(W) in the inputs of the challenge hash. The three values that the partial signature depends on, i.e., the nonce coefficient, the challenge, and the parity of the final nonce, then agree between the adversary's view and the original game. Since the reduction knows the discrete logarithms of all group elements it introduces, the argument also applies in the algebraic group model, in which the security proof of MuSig2* is given. The full argument is in a footnote. Bump the version to 1.0.5.

    The problem with the previous sketch was found by mllwchrry while reviewing the corresponding section of the FROST signing BIP draft, see https://github.com/siv2r/bip-frost-signing/issues/73.

    The reduction has been found and written down with the help of Claude Fable 5.1.

  2. BIP-327: Fix reduction sketch for infinity in nonce aggregation
    The section "Dealing with Infinity in Nonce Aggregation" sketches a
    reduction from the unforgeability of the modified scheme, which sets the
    final nonce R to G whenever it would be the point at infinity, to the
    unforgeability of the original MuSig2* scheme. The sketch let the
    reduction translate aggnonce' = bytes(33, 0) || bytes(33, 0) into
    aggnonce = cbytes_ext(G) || bytes(33, 0). But the nonce coefficient b is
    derived by hashing the aggregate nonce, so the adversary expects a b
    computed from aggnonce' while the original game computes b from
    aggnonce. The resulting partial signatures do not match, and the sketch
    does not work as a black-box reduction.
    
    Replace the sketch with a reduction that programs the random oracles.
    For each pair of aggregate public key and message, it maps the three
    aggregate nonces whose final nonce is G or -G in the modified scheme,
    namely bytes(33, 0) || bytes(33, 0), cbytes(G) || bytes(33, 0), and
    cbytes(-G) || bytes(33, 0), to three aggregate nonces of its own choice
    whose final nonce in the original game is a random W or -W, and it swaps
    xbytes(G) with xbytes(W) in the inputs of the challenge hash. The three
    values that the partial signature depends on, i.e., the nonce
    coefficient, the challenge, and the parity of the final nonce, then
    agree between the adversary's view and the original game. Since the
    reduction knows the discrete logarithms of all group elements it
    introduces, the argument also applies in the algebraic group model, in
    which the security proof of MuSig2* is given. The full argument is in a
    footnote. Bump the version to 1.0.5.
    
    The problem with the previous sketch was found by mllwchrry while
    reviewing the corresponding section of the FROST signing BIP draft, see
    https://github.com/siv2r/bip-frost-signing/issues/73.
    
    The reduction has been found and written down with the help of Claude
    Fable 5.1.
    c51847a8f2
  3. real-or-random commented at 12:00 PM on November 13, 2026: contributor

    cc @mllwchrry , want to review this? :)

    (The version bump conflicts with #2351 at the moment.)

  4. jonatack added the label BIP Update by Owner on Nov 13, 2026

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bips. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-11-14 09:10 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me