Implement multisig

[triwebb1]

It would be of tremendous value for RaiBlocks to implement a multisig scheme. Given the limited space, Schnorr signature aggregation may be the most practical approach.

[augustresende]

Yes,

[emcneal]

I agree!

[augustresende]

https://crypto.stackexchange.com/questions/50448/schnorr-signatures-multisignature-support

[rkeene]

We have a MuSig based implementation of this now from @PlasmaPower.

We'll want to extend the block signing RPC to be aware of how many signatures are needed, but passing around the message to be signed and pre-signed will be the user's job.

[funkspock]

Updated post from MuSig authors: https://blockstream.com/2019/02/18/musig-a-new-multisignature-standard/

Link to opensource MuSig library: https://github.com/ElementsProject/secp256k1-zkp/tree/secp256k1-zkp/src/modules/musig

Related posts

1006

1150

[PlasmaPower]

Unfortunately that implementation is for the secp246k1 curve. Nano uses curve25519.

[funkspock]

@PlasmaPower Kzen Networks has implemented a reference library for Ed25519 threshold signatures: https://github.com/KZen-networks/multi-party-eddsa/wiki/Aggregated-Ed25519-Signatures

Alternative Signatures Schemes other than MuSig that can be considered:

• Shamir’s Secret Sharing (SSS)
• Threshold ECDSA
• Schnorr Signatures
• BLS Signatures

Overview article: https://blockchainatberkeley.blog/alternative-signatures-schemes-14a563d9d562

Regardng BLS, it seems that it can be optimised: https://blog.dash.org/bls-is-it-really-that-slow-4ca8c1fcd38e

[lucaslopes]

We'll want to extend the block signing RPC to be aware of how many signatures are needed, but passing around the message to be signed and pre-signed will be the user's job.

Is it possible to set a variable (between 0 and 1) that will be multiply to the total number of wallets in the multisig, and the product indicates the minimum of signatures that are needed? (i.e set the percentage needed to send funds)

[unyieldinggrace]

@funkspock @PlasmaPower I've been working for about a week or so on trying to implement the aggregated-signature algorithm from KZen Networks in javascript. Ultimately, aggregated signatures are a necessary requirement for an opt-in Nano privacy scheme I'm working on, similar to cashfusion on BCH.

I've been trawling through KZen Networks' rust code. As far as I can tell, my implementation seems to match their spec, and the patterns in their rust code, but for some reason I just cannot get the two-party signature to verify correctly. The aggregated-signature code works fine as long as there is only one player. Adding a second player causes verification to fail. I've been comparing the rust and JS code all day to no avail, I'm getting close the point of giving up and moving on to another project. I thought I would post my progress here in case it helps someone else.

const elliptic = require('elliptic');

let EdDSA = elliptic.eddsa;
// Create and initialize EdDSA context
// (better do it once and reuse it)
let ec = new EdDSA('ed25519');

function getPlayerData(secret, zValue) {
    let key = ec.keyFromSecret(secret); // hex string, array or Buffer

    return {
        'secretKeyBytes': key.privBytes(),
        'publicKeyBytes': key.pubBytes(),
        'publicKeyPoint': ec.decodePoint(key.pubBytes()),
        'messagePrefix': key.messagePrefix(),
        'zValue': zValue
    };
}

function getSignatureComponentsForPlayer(playerData, message) {
    let r = ec.hashInt(playerData.messagePrefix, message, playerData.zValue);
    let R = ec.g.mul(r);
    let Rencoded = ec.encodePoint(R);
    let t = ec.hashInt(Rencoded);

    return {
        'rHash': r,
        'RPoint': R,
        'RPointCommitment': t
    };
}

function getAggregatedRPoint(RPoints) {
    let aggregatedRPoint = null;

    for (let i = 0; i < RPoints.length; i++) {
        if (aggregatedRPoint === null) {
            aggregatedRPoint = RPoints[i];
        } else {
            aggregatedRPoint = aggregatedRPoint.add(RPoints[i]); // point addition
        }
    }

    return aggregatedRPoint;
}

function getAHashSignatureComponent(playerPublicKeyPoint, pubKeys) {
    let hashArguments = [ec.encodePoint(playerPublicKeyPoint)];

    for (let i = 0; i < pubKeys.length; i++) {
        hashArguments.push(ec.encodePoint(pubKeys[i]));
    }

    return ec.hashInt.apply(ec, hashArguments);
}

function getAggregatedPublicKeyPoint(pubKeys) {
    let aggregatedPublicKeyPoint = null;
    let aHashComponent = null;
    let aggregationComponentPoint = null;

    for (let i = 0; i < pubKeys.length; i++) {
        aHashComponent = getAHashSignatureComponent(pubKeys[i], pubKeys);
        aggregationComponentPoint = pubKeys[i].mul(aHashComponent);

        if (aggregatedPublicKeyPoint === null) {
            aggregatedPublicKeyPoint = aggregationComponentPoint;
        } else {
            aggregatedPublicKeyPoint.add(aggregationComponentPoint); // point addition
        }
    }

    return aggregatedPublicKeyPoint; // need to convert to key?
}

function getKHash(aggregatedRPoint, aggregatedPublicKeyPoint, message) {
    return ec.hashInt(ec.encodePoint(aggregatedRPoint), ec.encodePoint(aggregatedPublicKeyPoint), message);
}

function getSignatureContribution(aggregatedRPoint, pubKeys, message, playerData, signatureComponents) {
    let aggregatedPublicKeyPoint = getAggregatedPublicKeyPoint(pubKeys);
    let aHashSignatureComponent = getAHashSignatureComponent(playerData['publicKeyPoint'], pubKeys);
    let kHash = getKHash(aggregatedRPoint, aggregatedPublicKeyPoint, message);

    let signatureContribution = kHash.mul(ec.decodeInt(playerData['secretKeyBytes']));
    signatureContribution = signatureContribution.mul(aHashSignatureComponent); // not absolutely certain about the order of operations here.
    signatureContribution = signatureComponents['rHash'].add(signatureContribution); // bigint addition
    signatureContribution = signatureContribution.umod(ec.curve.n); // appears to not be needed? Rust implementation doesn't seem to have it, even for single sig.

    return signatureContribution;
}

function getAggregatedSignature(signatureContributions) {
    let aggregatedSignature = null;

    for (let i = 0; i < signatureContributions.length; i++) {
        if (aggregatedSignature === null) {
            aggregatedSignature = signatureContributions[i];
        } else {
            aggregatedSignature.add(signatureContributions[i]); // bigint addition
        }
    }

    return ec.makeSignature({ R: aggregatedRPoint, S: aggregatedSignature, Rencoded: ec.encodePoint(aggregatedRPoint) });
}

let msgHash = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];

let playerData1 = getPlayerData('31760bf21992fed876573423a3a1d4bffc41d692bb4f65f44ae21778f7fb941d', 'c9b67f7c8830b7c5a8d28acd9edee6d7082a02d1b2c8b11392296ea2965879b9')
let signatureComponents1 = getSignatureComponentsForPlayer(playerData1, msgHash);

let playerData2 = getPlayerData('6364c231f6d9755adf4960d7ed628b4e5e7a23ba2e191ff72df590fdf42383b9', '7b9b11bc0f882c436540c00ae3a7f5c18adf83fca2caa93454b17a6706552c00')
let signatureComponents2 = getSignatureComponentsForPlayer(playerData2, msgHash);

// when the second player's data is uncommented, verification fails

let pubKeys = [
    playerData1.publicKeyPoint,
    // playerData2.publicKeyPoint
];

let RPoints = [
    signatureComponents1.RPoint,
    // signatureComponents2.RPoint
];

let aggregatedRPoint = getAggregatedRPoint(RPoints);
let signatureContribution1 = getSignatureContribution(aggregatedRPoint, pubKeys, msgHash, playerData1, signatureComponents1);
let signatureContribution2 = getSignatureContribution(aggregatedRPoint, pubKeys, msgHash, playerData2, signatureComponents2);

let signatureContributions = [
    signatureContribution1,
    // signatureContribution2
];

let aggregatedSignature = getAggregatedSignature(signatureContributions, aggregatedRPoint);

// console.log(aggregatedSignature);

let aggregatedPublicKeyPoint = getAggregatedPublicKeyPoint(pubKeys);
let aggPubKey = ec.keyFromPublic(aggregatedPublicKeyPoint);
console.log('Attempting to verify aggregated signature...');
// console.log('Verification Passed: ' + ec.verify(msgHash, aggregatedSignature, aggregatedPublicKeyPoint));
console.log('Verification Passed: ' + ec.verify(msgHash, aggregatedSignature, aggPubKey));

For simplicity, this implementation is still using a sha512 hash, just so it would match the rust implementation by KZen (https://github.com/KZen-networks/multi-party-eddsa/wiki/Aggregated-Ed25519-Signatures). Once I proved the concept, my plan was to try moving it over to Blake2 hashes. If that worked, then it should be possible to created aggregated signatures that can be verified natively by the existing Nano node.

The privacy protocol revolved around a binary tree of aggregate-signature addresses (which allowed everyone to be automatically refunded if one participant goes offline or doesn't send their input amount to the mixing address), plus a communication protocol to hide the linkages between output addresses. Sadly, without the aggregated-signature part working, the whole protocol doesn't work.

If anyone can tell me why the javascript code above fails to verify with 2 signers, I will be deeply grateful. Maybe someone who understands the math better than me can spot the bug.

[PlasmaPower]

@unyieldinggrace after some debugging with my curve25519-repl (very helpful for these things :slightly_smiling_face: ), I traced it down to your 2 loops where you did the start at null and set or add if it exists thing. .add doesn't mutate the value in either case, you need to reassign. I.e. change:

aggregatedPublicKeyPoint.add(aggregationComponentPoint);

to

aggregatedPublicKeyPoint = aggregatedPublicKeyPoint.add(aggregationComponentPoint);

and do the same for aggregatedSignature.

This makes the signature validate with more than one participant. However, your strategy of deterministically generating the R value is very dangerous, because an attacker could wait for the R value to be revealed, then disconnect and retry signing the same message, knowing what the R value will be in advance (bypassing the commitment which you should be checking in advance of sending the R value btw).

I built a library to do this which you might find helpful: https://github.com/PlasmaPower/musig-nano . It also has an example of compiling it to wasm and using it from js: https://github.com/PlasmaPower/musig-nano/tree/gh-pages

[PlasmaPower]

Since you brought up using this for privacy, you might be interested in a coinjoin-like scheme I posted in the discord a while back: https://discordapp.com/channels/370266023905198083/459677604669030400/583325217951055893

Pretty much as you alluded to, use musig to create a tree of potential transactions, the happy path being receive all then send all to new addresses, and after each receive an exit path to return the funds to the original sender in case the next participant doesn't receive (you can have one exit path per participant with funds in the account at that stage to hinder it from being maliciously used as a DoS).

This could probably benefit from batching optimizations though, like sending a commitment to all R values at once, which my musig-nano library doesn't allow for (I'd like to keep it simple).

[unyieldinggrace]

@PlasmaPower ha ha, I knew it would turn out to be something silly/simple, thanks heaps for the pointer! Looks like it's working now, even got it running with blake2b hashes instead of sha512 hashes.

I've seen some other nano-privacy stuff that you've written, big fan of your work (it was me that wrote the commentary on your orv-privacy proposal using bulletproofs: https://forum.nano.org/t/proof-of-concept-of-cryptography-to-add-amount-privacy-to-nano/577/4).

The repl looks pretty handy, I'll keep that in mind. Would love to read the coinjoin proposal, but I'm having trouble following the discord link. I don't use discord much, so not sure what the problem is. Do I need to be invited to the channel or something?

[PlasmaPower]

Thanks for the reply on the forum! I hadn't seen it actually. Are you in the nano discord? If not join here: https://chat.nano.org/

Here's a copy of my messages for the coinjoin thing: https://gist.github.com/PlasmaPower/0e8ee2f01fc8a951e2798473939f5651

[unyieldinggrace]

Ah, there we go. I'm in the nano discord now. Thanks very much!