[XRPL Performance]Add or change signing support for peer messaging from sepc256k1 to ED25519

sophiax851 commented 10 months ago

It's showing in lab profiling that the verifyDigest is the most CPU intensive operations during peer to peer messaging, among which 94% of the CPU cost was from secp256k1_ecdsa_verify. As showing in the following graph:

Summary

Adding or switching from sepc256k1 to ED25519 can dramatically reduce the peer to peer messaging's overall latency, hence improving network performance and capacity.

Proposing to add ED25519 support in the ripple::verifyDigest https://github.com/XRPLF/rippled/blob/develop/src/ripple/protocol/impl/PublicKey.cpp

Motivation

As studied and tested by @scottschurr and Murat Cenk at Ripple, ED25519 signature verification is twice as fast as secp256k1 signature verification. Currently, we already support ED25519 for client transaction submission's signature verification. We should add (or change) signature support for peer-to-peer messaging from secp256k1 to ED25519. This change is expected to result in a significant performance improvement in the consensus's throughput.

Solution

Paths Not Taken

Update following latency study on MainNet node

Research has revealed that the processing costs associated with individual checkValidation and checkPropose calls are relatively insignificant compared to the latency overhead incurred when relaying these messages to targeted validator nodes. Additionally, we've verified that rippled already has de-duplication and trust checking to filter out unwanted proposals and validations, the checkPropose and checkValidation were only called for valid messages from validators. As a result, the necessity and priority of implementing optimizations to further reduce the processing costs of these calls have diminished substantially.

The following are data extracted from a single consensus cycle in MainNet, where 71 transactions were processed in the ledger and validated by the 35 validators. The average peer to peer message relaying network latency is between 100ms - 300ms.

Total number of checkValidation calls: 172 Total latency: 22ms (22,000 µs) Average latency from each checkValidation call: 128µs

Total number of checkPropose calls: 56 Total latency: 5.56 ms (5,560 µs) Average latency from each checkPropose call: 99.3µs

sappenin commented 10 months ago

Relates to https://github.com/XRPLF/rippled/pull/2647 and https://github.com/XRPLF/rippled/issues/3105

sophiax851 commented 7 months ago

The verifyDigest requires the secp256k1 in code, and the additional assertion check. But for the client RPC, it allows for both protocol as shown in here:

bool verify( PublicKey const& publicKey, Slice const& m, Slice const& sig, bool mustBeFullyCanonical) noexcept { if (auto const type = publicKeyType(publicKey)) { if (type == KeyType::secp256k1) { return verifyDigest( publicKey, sha512Half(m), sig, mustBeFullyCanonical); } else if (type == KeyType::ed25519) { if (!ed25519Canonical(sig)) return false;

        // We internally prefix Ed25519 keys with a 0xED
        // byte to distinguish them from secp256k1 keys
        // so when verifying the signature, we need to
        // first strip that prefix.
        return ed25519_sign_open(
                   m.data(), m.size(), publicKey.data() + 1, sig.data()) ==
            0;
    }
}
return false;

}

Can we add the ED25519 support (or limit to only allow ED25519 ?? Not sure what'd be impact to the community) for peer to peer messaging in the next release? I think if our testing results are correct, it'd give us some sizable gains in the network performance and less contention with the locks. @intelliot @scottschurr

scottschurr commented 7 months ago

I've looked into this briefly, and I can't guarantee that I understand all the details. But here's my understanding at the moment.

Peer messages are one of several kinds of signed messages that are passed between nodes on the network. The messages are signed using a "node key pair", which is documented here: https://xrpl.org/peer-protocol.html#node-key-pair Right now that key pair appears as though is is always an sec256k1 key pair. The code is here: https://github.com/XRPLF/rippled/blob/develop/src/ripple/app/main/NodeIdentity.cpp#L55-L56

If we want the nodes to start using Ed25519 signatures then we need to

Make sure all paths for messages that are signed using the node key pair are changed so they support both secp256k1 signatures and Ed25519 signatures.
Then we need to wait a couple of release cycles, so we are confident that code that doesn't handle Ed25519 signatures is amendment blocked.
Then we start producing Ed25519 key pairs for node identities in such a way that we don't break things.

That last point requires us holding our tongues right. As it stands, someone with

A nodeid argument on the command line, or
A [node_seed] stanza in their config file, or
A preexisting database (which keeps a record of the generated node's key pair)

is guaranteed to get the secp256k1 key pair that would be expected from that seed. We shouldn't break that.

So we can replace secp256k1 node IDs when a node's database is completely removed and none of those arguments is available. We can also introduce new arguments that would produce Ed25519 node key pairs instead of secp256k1 key pairs.

I think we could do similar work with validators, since validations are signed with each validator's key pair.

All that said, it's important that we be realistic regarding how much this change would improve the overall performance of the application. It will certainly improve performance. But the overall impact is likely to be in small percentages

sophiax851 commented 7 months ago

Thanks @Scott Schurr @.***> for looking into this. Is it easy to set it up in the lab to check out the performance gain? Though from the CPU profiling, it showed the cost for verifyDigest is high (for both the checkValidation and checkPropose calls), it'd be good to know how much it helps with the peer to peer messaging. Can we do a PoC (do some quick and dirty changes) to have the nodes in the lab to use the Ed25519 to verify the performance gain? If the gain is trivial, we can reset our priority accordingly.

On Mon, Feb 5, 2024 at 10:05 AM Scott Schurr @.***> wrote:

I've looked into this briefly, and I can't guarantee that I understand all the details. But here's my understanding at the moment.

Peer messages are one of several kinds of signed messages that are passed between nodes on the network. The messages are signed using a "node key pair", which is documented here: https://xrpl.org/peer-protocol.html#node-key-pair https://urldefense.com/v3/__https://xrpl.org/peer-protocol.html*node-key-pair__;Iw!!PZTMFYE!93Y87DUQ39fUBwVzRr8igvOWOF1LscCS1yVrCJ1mSASLQpmls5uaJcy2ogtI9QpCSTn2sazHH8kIvCjnngBq$ Right now that key pair appears as though is is always an sec256k1 key pair. The code is here: https://github.com/XRPLF/rippled/blob/develop/src/ripple/app/main/NodeIdentity.cpp#L55-L56 https://urldefense.com/v3/__https://github.com/XRPLF/rippled/blob/develop/src/ripple/app/main/NodeIdentity.cpp*L55-L56__;Iw!!PZTMFYE!93Y87DUQ39fUBwVzRr8igvOWOF1LscCS1yVrCJ1mSASLQpmls5uaJcy2ogtI9QpCSTn2sazHH8kIvA4hMXZU$

If we want the nodes to start using Ed25519 signatures then we need to

Make sure all paths for messages that are signed using the node key pair are changed so they support both secp256k1 signatures and Ed25519 signatures.

Then we need to wait a couple of release cycles, so we are confident that code that doesn't handle Ed25519 signatures is amendment blocked.

Then we start producing Ed25519 key pairs for node identities in such a way that we don't break things.

That last point requires us holding our tongues right. As it stands, someone with

A nodeid argument on the command line, or

A [node_seed] stanza in their config file, or

A preexisting database (which keeps a record of the generated node's key pair)

is guaranteed to get the secp256k1 key pair that would be expected from that seed. We shouldn't break that.

So we can replace secp256k1 node IDs when a node's database is completely removed and none of those arguments is available. We can also introduce new arguments that would produce Ed25519 node key pairs instead of secp256k1 key pairs.

I think we could do similar work with validators, since validations are signed with each validator's key pair.

All that said, it's important that we be realistic regarding how much this change would improve the overall performance of the application. It will certainly improve performance. But the overall impact is likely to be in small percentages

— Reply to this email directly, view it on GitHub https://urldefense.com/v3/__https://github.com/XRPLF/rippled/issues/4795*issuecomment-1927654936__;Iw!!PZTMFYE!93Y87DUQ39fUBwVzRr8igvOWOF1LscCS1yVrCJ1mSASLQpmls5uaJcy2ogtI9QpCSTn2sazHH8kIvCaeykWa$, or unsubscribe https://urldefense.com/v3/__https://github.com/notifications/unsubscribe-auth/AZKCD23HIK4BVC4WC7PGUULYSENN3AVCNFSM6AAAAAA6Z3RPJCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTSMRXGY2TIOJTGY__;!!PZTMFYE!93Y87DUQ39fUBwVzRr8igvOWOF1LscCS1yVrCJ1mSASLQpmls5uaJcy2ogtI9QpCSTn2sazHH8kIvGupisNa$ . You are receiving this because you authored the thread.Message ID: @.***>

scottschurr commented 7 months ago

@sophiax851, unfortunately it's non-trivial to test the performance gain in a lab. The paths for the different key types need to be identified and fixed before the performance test can be performed. The changes are probably not extensive, but are required. You'll need a developer to do the required work.

intelliot commented 7 months ago

Internal tracker: RIPD-1832

XRPLF / rippled