Implementing Solana IBC bridge, I had to deal with various constraints of the Solana protocol. Connecting Solana to Composable Foundation’s Picasso network, I needed to develop an on-chain light client capable of validating Tendermint blocks. This meant being able to validate 50 signatures in a single transaction.

Turns out that’s not possible on Solana and it’s not exactly because of the execution time limit. The real culprit is the transaction size limit which I’ve discussed previously. This article describes how signature verification is done on Solana, the limit on the number of signatures that can be verified in a single transaction and how that limit can be worked around.

Like before, this article assumes familiarity with Solana and doesn’t serve as a step-by-step guide for Solana development. Nonetheless, examples from the solana-sigverify repository can be used as a starting point when using the signature verification mechanism described below.

Cryptographic functions on Solana

Solana programs can perform any computation a regular computer can do. It is possible to implement cryptographic functions as part of a smart contract and have them executed on the blockchain. However, that’s a quick way to run into issues.

Calculating a 256-bit SHA2 digest of a 100-byte buffer takes 14 thousand compute units (CU). Meanwhile, Solana programs have a hard limit of 1.4 million CU. In other words, hashing 100 bytes takes up 1% of the absolute maximum computation that a smart contract can perform in a single transaction. Situation is even worse with more advanced cryptographic functions: a signature verification blows through the compute limit.

Thankfully, Solana offers native methods for popular cryptographic primitives. In particular, a sol_sha256 system call (accessible through solana_program::hash::hashv function) computes 256-bit SHA2 hash with cost of only 267 CU to hash a 100-byte buffer. One might expect a similar sol_ed25519_verify system call, however signature verification is done in much more convoluted way on Solana.

Signature verification

Solana includes a handful of native programs. Among those are programs, such as Ed25519 program, which perform signature verification. To check a signature, caller creates a transaction including two instructions: one calling the native signature verification program and another calling a smart contract. If a signature is invalid, the whole transaction fails an the smart contract is not called.¹

For example, consider transaction 56Qj­WeDD­DX4R­e2sX… which has three instructions: The first adjust compute unit limit, the second invokes the Ed25519 program and the final one calls a program which can check that signature has been verified. An annotated instruction data of the Ed25519 program invocation is shown below:

Signature count limit

Since public key, signature and signed message are stored in the instruction data, number of signatures that can be verified is subject to the 1232-byte transaction size limit. Accounting for overhead leaves less than 1100 bytes for the instruction data. To specify a signature for verification, a 14-byte header, 32-byte public key, 64-byte signature and the message are needed. Even assuming an empty message, that’s 110 bytes per signature which means at most ten signatures in a single transaction.²

For Solana IBC I needed to verify Tendermint block signatures. Tendermint validators timestamp their signatures and as a result each signature is for a different message of about 112 bytes. That gives a maximum of ⌊1100 / (14 + 32 + 64 + 112)⌋ = 4 signatures per transaction. Meanwhile, as mentioned at the start, I needed to verify about 50 of them.

The sigverify program

To address this limitation, signatures can be verified in batches with results aggregated into a signatures account that can be inspected later on.³ This scheme needs i) a smart contract capable of doing the aggregation and ii) an interface for other smart contracts to interpret the aggregated data.

The first point is addressed by the sigverify program. Using regular Solana way of signature verification, it observes what signatures have been checked in the transaction. It then aggregates all that information into a Program Derived Address (PDA) account it owns. As the owner, only the sigverify program can modify the account thus making sure that aggregated information stored in it is correct.

Even though the sigverify owns the account, it internally assigns it to the signer such that users cannot interfere with each other’s signatures account.

RPC Client

A convenient way to call the sigverify program is to use the client library functions packaged alongside it. To use them, first add a new dependency to the RPC client (making sure client feature is enabled):

[dependencies.solana-sigverify]
git = "https://github.com/mina86/solana-sigverify"
features = ["client"]

The crate has a UpdateIter iterator which generates instruction pairs that need to be executed to aggregate the signatures into the signatures account. The account can be reused but in that case each batch of signatures needs to use a different epoch. If account is freed each time, epoch can be set to None. Note that all the instruction pairs returned by UpdateIter can be executed in parallel transactions.

// Generate list of signatures to verify.
let entries: Vec<Entry> = signatures.iter()
    .map(|sig| Entry {
        pubkey: &sig.pubkey,
        signature: &sig.signature,
        message: &sig.message,
    })
    .collect();

// When signatures account is reused, each use needs
// a different epoch value.  Otherwise it can be None.
let epoch = std::time::SystemTime::now()
    .duration_since(std::time::UNIX_EPOCH)
    .unwrap()
    .as_nanos() as u64;
let epoch = Some(epoch);

// Generate all necessary instructions and send them to
// Solana.  UpdateIter splits signatures into groups as
// necessary to call sigverify.
let (iter, signatures_account, signatures_bump) =
    solana_sigverify::instruction::UpdateIter::new(
        &solana_sigverify::algo::Ed25519::ID,
        SIGVERIFY_PROGRAM_ID,
        signer.pubkey(),
        SIGNATURES_ACCOUNT_SEED,
        epoch,
        &entries,
    )?;
// To speed things up, all of those instruction pairs can
// be executed in parallel.
for insts in iter {
    let blockhash = client.get_latest_blockhash()?;
    let message = Message::new_with_blockhash(
        &insts,
        Some(&signer.pubkey()),
        &blockhash,
    );
    send_and_confirm_message(
        client, signer, blockhash, message)?;
}

// Invoke the target smart contract. signatures_account is
// the account with aggregated signatures.  It will need to
// be passed to the smart contract.
todo!("Invoke the target smart contract");

// Optionally free the account.  Depending on usage, the
// account can be reused (to save minor amount of gas fees)
// with a new epoch as described.
let instruction = solana_sigverify::instruction::free(
    SIGVERIFY_PROGRAM_ID,
    signer.pubkey(),
    Some(signatures_account),
    SIGNATURES_ACCOUNT_SEED,
    signatures_bump,
)?;
send_and_confirm_instruction(client, signer, instruction)?;

The signatures are aggregated into an account whose address is stored in signatures_account. The SIGNATURES_ACCOUNT_SEED allows a single signer to maintain multiple accounts if necessary.

The target smart contract

The target smart contract needs to be altered to support reading the aggregated signatures. Code which helps with that is available in the solana-sigverify crate as well. First, add a new dependency to the program (making sure lib feature is enabled)):

[dependencies.solana-sigverify]
git = "https://github.com/mina86/solana-sigverify"
features = ["lib"]

The crate has a Verifier family of types which can interface with the Solana’s native signature verification programs (like the Ed25519 program) and the aggregated signatures. This flexibility allows the smart contracts using this type to nearly transparently support normal Solana signature verification method or the signature aggregation through sigverify program.

/// Address of the sigverify program.  This must be set
/// correctly or the signature verification won’t work.
const SIGVERIFY_PROGRAM_ID: Pubkey =
    solana_program::pubkey!("/* … */");

let mut verifier =
    solana_sigverify::Ed25519Verifier::default();

// To check signatures from a call to a native signature
// verification program, the verifier must be initialised
// with Instructions sysvar.  The the native program call
// must immediately preceding the current instruction.
let instructions_sysvar = /* … */;
verifier.set_ix_sysvar(instructions_sysvar)?;

// To check signatures aggregated in a signatures account,
// the verifier must be initialised with the account.  For
// security, expected sigverify program ID must be specified
// as well.  verifier rejects signatures accounts not owned
// by the sigverify program.
let signatures_account = /* … */;
verifier.set_sigverify_account(
    account, &SIGVERIFY_PROGRAM_ID)?;

// To verify a signature, call verify method.
if !verifier.verify(message, pubkey, signature)? {
    panic!("Signature verification failed");
}

Conclusion

It’s perhaps counter intuitive that the transaction size limit constraints how many signatures can be verified in a single Solana transaction, but because of the design of the native signature verification programs, it is indeed the case. Thankfully, with some engineering the restriction can be worked around.

This article introduces a method of aggregating signatures across multiple transactions with the help of a sigverify program and library functions available in solana-sigverify repository. The library code supports regular Solana signature verification method as well as the aggregated signatures providing flexibility to the smart contract.

Lastly, the repository also provides solana-native-sigverify crate which offers APIs for interacting with the Solana native signature verification programs.