An Ethereum transaction needs to be included in a block and mined before it is processed and saved on the blockchain. As a result, on-chain transactions takes time and costs gas to compensate miners for their work.

In contrast, off-chain computation lets you perform actions instantly without waiting for transactions to be mined and does not cost any gas.

Cryptographic signatures can be used to validate the origin and integrity of messages. In this article, let’s look at how you can perform off-chain computation using Ethereum signatures. Then, we’ll examine real-life use cases of off-chain computation such as decentralized exchanges, state channels, and meta transactions.

# Background

In decentralized exchanges, signatures and off-chain computation are used to pre-authorize market Takers to fill any signed orders made by market Makers. Instead of posting buy or sell orders directly on-chain, Makers signs messages detailing their order using their private key. Makers then submit these signed orders to an off-chain order book - databases hosted by third-party Relayers on centralized servers - for Takers to browse and fill. These off-chain orders are submitted off-chain instantly, without having to pay any gas.

The magic ingridient that makes off-chain order books work are cryptographic signatures.

Cryptographic signatures are a foundational computer science primitive that enables all blockchain technology. Signatures can be used to authorize transactions on behalf of the signer. It can also be used to prove to a smart contract that a certain account approved a certain message.

# Public Key Cryptography

Before we proceed to signature signing and verification works, let’s start by looking at public-key cryptography and the ECDSA algorithm used by the Ethereum blockchain.

## Public Keys and Private Keys

Modern cryptography is founded on the idea that the key that you use to encrypt your data can be made public while the key that is used to to decrypt your data can be kept private. As such, these systems are known as public-key cryptographic systems.

The earliest and most well known of these systems is RSA, which we’ll examine in the next section.

## Trapdoor Functions

A key component of public-key cryptosystems are **Trapdoor Functions**: a set of algorithms that is easy to process in one direction, but hard to undo.

In RSA, the easy algorithm multiplies two large prime numbers. The hard algorithm is factoring the product of two large prime numbers.

However, RSA suffers from increasingly efficient factoring algorithms that have been moderately successful in solving the factorization problem. It’s becoming easier and easier to brute-force RSA encryption.

Finding a good Trapdoor Function is critical in making a secure public key cryptographic system. The bigger the spread between the difficulty between the easy and hard algorithms / directions, the more secure a cryptographic system based on it will be.

## ECDSA

To address the drawbacks of RSA, alternative cryptographic algorithms were proposed around the mathematics of elliptic curves known as Elliptic Curve Digital Signature Algorithm (ECDSA.) An elliptic curve cryptosystem can be defined by picking a prime number as a maximum, a curve equation, and a public point `A`

on the curve:

Take any two points on the curve above and draw a line through them; the line will intersect the curve at exactly one more place. Like a game of billiards, take a ball from point A and shoot it towards point B. When it hits the curve, the ball ‘bounces’ either straight up when it’s below the x-axis or straight down when it’s above the x-axis. Repeat this process `n`

times (this process represents a dot product.)

If you have two points, an initial point ‘bounced’ with itself `n`

times to arrive at a final point, finding out `n`

when you only know the final point and the first point is hard. At the same time, it’s easy to repeat over and over the procedure described above. This is a fine candidate for a trapdoor function.

In an elliptic curve cryptosystem, a private key is a number

`n`

, and a public key is the public point ‘bounced’ with itself`n`

times.

ECDSA’s elliptic curve logarithm problem is harder to compute than prime factorization. Since a more computationally intensive hard problem means a stronger cryptographic system, it follows that elliptic curve cryptosystems are harder to break than RSA and Diffie-Hellman.

Ethereum signatures uses ECDSA and secp256k1 constants to define the elliptic curve.

# Signing and Verifying Signatures

Each account in the Ethereum network has a public key and a private key. An Ethereum address is essentially a hashed version of the public key.

Accounts can use their private key to sign a piece of data, returning a signature of that data.

Anyone can verify the generated signature to:

- Recover the public key / address of the signer, and
- Verify the integrity of the message, that it is the same message that was signed by the signer.

## Signing

You can sign messages entirely off-chain in the browser, without interacting with the Ethereum network. Signing and the verification of ECDSA-signed messages allows tamper proof communications outside of the blockchain.

We can call the `eth_sign`

method via an Ethereum client such as `web3.js`

:

```
// Create a SHA3 hash of the message 'Apples'
const messageHash = web3.sha3('Apples');
// Signs the messageHash with a given account
const signature = await web3.eth.personal.sign(messageHash, web3.eth.defaultAccount);
```

The

`eth_sign`

method calculates an Ethereum specific signature with:`eth_sign(keccak256("\x19Ethereum Signed Message:\n" + len(message) + message)))`

.The prefix to the message makes the calculated signature recognisable as an Ethereum specific signature.

Note that we can sign messages entirely client-side.

### Mitigating Replay Attacks

Signed messages should contain a nonce of some kind to mitigate against replay attacks. We don’t want someone to be able to submit our buy / sell orders again to execute another transaction. This can be implemented by keeping track of nonces seen so far:

```
mapping(address => mapping(uint256 => bool)) seenNonces;
function submitOrder(uint256 nonce, bytes sig) public {
address signer = // recover signer address from `sig`
require(!seenNonces[signer][nonce]);
seenNonces[signer][nonce] = true;
...
}
```

### Signing a Message with Arguments

A message can contain specific details about the action being authorized and any parameters required to execute the action. We can encode these arguments in the message itself.

We can use ethereumjs.ABI.soliditySHA3 to calculate the `sha3`

of given input parameters in the same way Solidity would:

```
function signOrder(amount, nonce, callback) {
var hash = "0x" + ethereumjs.ABI.soliditySHA3(
["address", "uint256", "uint256"],
[web3.eth.defaultAccount, amount, nonce]
).toString("hex");
web3.personal.sign(hash, web3.eth.defaultAccount, callback);
}
```

In the above example, we sign a message contains details of our order, containing an `address`

of the owner, `amount`

of tokens, and `nonce`

.

## Verification

ECDSA signatures in Ethereum consist of three parameters `r`

, `s`

, and `v`

. Solidity provides a globally available method `ecrecover`

that returns an address given these three parameters. If the returned address is the same as the signer’s address, then the signature is valid.

Signatures produced by `web3.js`

are the concatenation of `r`

, `s`

, and `v`

, so a necessary first step is splitting those parameters back out.

Both smart contracts and Ethereum clients have the ability to verify ECDSA signatures.

### Signature Verification with Smart Contracts

```
pragma solidity ^0.4.25;
library ECDSA {
/**
* @dev Recover signer address from a message by using their signature
* @param hash bytes32 message, the hash is the signed message. What is recovered is the signer address.
* @param signature bytes signature, the signature is generated using web3.eth.sign()
*/
function recover(bytes32 hash, bytes signature)
internal
pure
returns (address)
{
bytes32 r;
bytes32 s;
uint8 v;
// Check the signature length
if (signature.length != 65) {
return (address(0));
}
// Divide the signature in r, s and v variables with inline assembly.
assembly {
r := mload(add(signature, 0x20))
s := mload(add(signature, 0x40))
v := byte(0, mload(add(signature, 0x60)))
}
// Version of signature should be 27 or 28, but 0 and 1 are also possible versions
if (v < 27) {
v += 27;
}
// If the version is correct return the signer address
if (v != 27 && v != 28) {
return (address(0));
} else {
// solium-disable-next-line arg-overflow
return ecrecover(hash, v, r, s);
}
}
/**
* toEthSignedMessageHash
* @dev prefix a bytes32 value with "\x19Ethereum Signed Message:"
* and hash the result
*/
function toEthSignedMessageHash(bytes32 hash)
internal
pure
returns (bytes32)
{
return keccak256(
abi.encodePacked("\x19Ethereum Signed Message:\n32", hash)
);
}
}
```

The code above defines a `recover(bytes32 hash, bytes signature) returns address`

function that:

- Splits the
`signature`

to its three components`r`

,`s`

, and`v`

, and - Calls
`ecrecover(hash, v, r, s)`

, and - Returns the Ethereum address of the signer that signed the message.

Note that any attempt to tamper the message hash or signature will result in a decoded address that is different than the signer’s address. This ensures that the integrity of the message and signer can be enforced.

At this point we’ve recovered the signer of the message, but we haven’t validated the integrity of the message hash. It’s possible that the message is NOT the one that the was signed by the owner. To do so, the smart contract needs to know exactly what parameters were signed, and so it must recreate the message from the parameters and use that for signature verification:

```
using ECDSA for bytes32;
function submitOrder(uint256 owner, uint256 amount, uint256 nonce, bytes signature) public {
// This recreates the message hash that was signed on the client.
bytes32 hash = keccak256(abi.encodePacked(owner, amount, nonce));
bytes32 messageHash = hash.toEthSignedMessageHash();
// Verify that the message's signer is the owner of the order
address signer = messageHash.recover(signature)
require(signer == owner);
require(!seenNonces[signer][nonce]);
seenNonces[signer][nonce] = true;
... process order
}
```

In the `submitOrder()`

function above, we construct the `messageHash`

by passing in the original `owner`

, `amount`

, and `nonce`

arguments of the original message:

```
bytes32 hash = keccak256(abi.encodePacked(owner, amount, nonce));
bytes32 messageHash = hash.toEthSignedMessageHash();
```

These arguments should be published alongside the signature on an off-chain relay server for market takers to submit alongside the signature.

Once we’ve verified that the message signer and the message arguments matches, we can be sure of its integrity and process the order:

```
address signer = messageHash.recover(signature)
require(signer == owner);
```

### Signature Verification with Ethereum Clients

We can also recover the signer using Ethereum clients such as `web3.js`

.

```
const signer = await web3.eth.personal.ecRecover(messageHash, signature);
```

### Signature Verification Summary

That’s it! We’ve just made use of signatures to perform an off-chain computation!

To speed up development, you can use OpenZeppelin’s

`SignatureBouncer`

contract to validate signatures. This contract defines modifiers you can use check if a signature was signed by a list of signer addresses and has valid`msg.data`

.

# Signatures Use Cases

Next, let’s look at how cryptographic signatures and off-chain computation are used in the wild. Most of these use cases revolve around minimizing the time spend on-chain and extracting most of the heavy lifting off-chain to optimize for transaction throughput and cost.

## 1. Decentralized Exchanges

Several types of decentralized exchanges exists: on-chain order books, automated market makers, state channels, and a hybrid off-chain order book approach. In particular, decentralized exchanges such as EtherDelta and 0x utilizes the off-chain computation approach in order to save gas costs.

This hybrid off-chain order book approach allows market makers to sign and transmit orders on an off-blockchain platform, with the blockchain only used for settlement. Signatures are used to pre-authorize market takers to fill any signed orders made by market makers. Instead of making a transaction to post buy or sell orders on-chain, Market Makers sign messages containing their orders. Market Makers submits these signed orders to an off-chain order book (hosted on a centralized server.)

Each off-chain order is a signed message indicating that you would like to do a particular trade. Market Takers can browse the order book and select the order they wish to fill by submitting the signed order to a smart contract and having the funds necessary to do so. The order will then be settled on-chain.

Off-chain computation lets traders post orders instantly without waiting for transactions to be mined, and avoids paying any gas costs! This pattern is known as ‘off-chain order books with on-chain settlement.’

You can learn more about decentralized exchanges by reading the 0x whitepaper.

## 2. State Channels

State channels are proposed as a means of scaling the Ethereum blockchain and reducing costs for a variety of applications by moving on-chain stateful components for blockchain applications off-chain. This means that the delays and fees associated with transactions can be avoided.

State channels (and Force-Move Games) allow participants to make repeated actions without using transactions.

Participants in a state channel pass cryptographically signed messages back and forth, accumulating intermediate state changes without publishing them to the canonical chain until the channel is closed. State channels are ideal for “bar tab” applications where numerous intermediate state changes may be accumulated off-chain before being settled by a single on-chain transaction (i.e. day trading, poker, turn-based games.)

## 3. Meta Transactions

Today, the barriers of entry for using dApps for regular users who aren’t crypto-savvy is steep. DApps need a significant improvement in UX to hide the complexity of fees and transactions so that it’s more intuitive for users to participate. Meta transaction is an initiative to lower barriers to entry and drive mass Ethereum adoption.

Meta Transactions lets dApps pay gas on behalf of users. By using cryptographic signatures, etherless accounts can sign meta transactions and incentivize relayers which holds ether to pay the gas for them (perhaps in exchange for fiat payment off-chain.)

Any relayer can submit and execute the meta transaction, paying gas on behalf of the user in exchange from other forms of compensation specified in the meta transaction message. Ether or tokens can be used to pay relayers. For example, this could be the meta transaction:

```
{
to // Contract address the transaction is going to
data // Function signature and parameters
gasPrice // Compensation for relayers
gasLimit // Maximum allowed gas for the transaction
nonce // To prevent replay attacks
signature // ECDSA signature
}
```

Instead of sending transactions directly to a smart contract, users sends it to a secondary relayer network. The network can parse meta transactions and ensure the signature is valid. Relayers then pick which transactions are most profitable and interfaces directly with the blockchain.

With meta transactions, users are able to interact with the blockchain from accounts that don’t hold any Ether. This lowers barriers to entry and encourage more mainstream adoption of dApps.

# Summary

Cryptographic signatures are a foundational computer science primitive that enables all blockchain technology. Signatures can be used to authorize transactions on behalf of the signer. It can also be used to prove to a smart contract that a certain account approved a certain message.

In this article, we’ve taken a look at how you can use Ethereum signatures validate the origin and integrity of messages and perform off-chain computation to optimize for throughput and cost. We’ve also looked at how signatures are used for decentralized exchanges, state channels, and meta transactions.