The Full Story

Precompiled Contracts
For each precompiled contract, we make use of a template function, ΞPRE, which implements the out-of-gas checking.

􏰒(∅,0,A0,()) if g<gr (197) ΞPRE(σ, g, I, T ) ≡ (σ, g − gr, A0, o) otherwise

The precompiled contracts each use these definitions and provide specifications for the o (the output data) and gr, the gas requirements.

We define ΞECREC as a precompiled contract for the elliptic curve digital signature algorithm (ECDSA) public key recovery function (ecrecover). See Appendix F for the definition of the function ECDSARECOVER. We also define d to be the input data, well-defined for an infinite length by appending zeroes as required. In the case of an invalid signature

(ECDSARECOVER(h, v, r, s) = ∅), we return no output.

(198) (199)

(200)

(201) (202) (203) (204) (205) (206) (207) (208) (209)

ΞECREC ≡ gr =

∥o∥ =

if ∥o∥=32: o[0..11] =

o[12..31] = d[0..(∥Id∥ − 1)] = d[∥Id ∥..] = h = v = r = s =

ΞPRE where:

3000

􏰒0 if ECDSARECOVER(h, v, r, s) = ∅ 32 otherwise

0
KEC􏰅ECDSARECOVER(h, v, r, s)􏰆[12..31] Id
(0, 0, ...)
d[0..31]
d[32..63]
d[64..95]
d[96..127]

where:

We define ΞSHA256 and ΞRIP160 as precompiled contracts implementing the SHA2-256 and RIPEMD-160 hash functions respectively. Their gas usage is dependent on the input data size, a factor rounded up to the nearest number of words.

ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER 21

(210) (211)

(212) (213)

(214)

(215) (216)

SHA2-256 of the form:

(217) SHA256(i ∈ B) ≡ o ∈ B32 (218) RIPEMD160(i ∈ B) ≡ o ∈ B20

The fourth contract, the identity function ΞID simply defines the output as the input:

ΞSHA256

gr

o[0..31]

ΞRIP160

gr

32 = SHA256(Id )

≡ ΞPRE where: = 60 + 12􏰚∥Id∥􏰛

≡ ΞPRE where:
= 600 + 120􏰚∥Id∥􏰛

32

=0

= RIPEMD160(Id )
For the purposes here, we assume we have well-defined standard cryptographic functions for RIPEMD-160 and

o[0..11] o[12..31]

ΞID ≡ ΞPRE where: gr = 15+3􏰚∥Id∥􏰛

32

o = Id

The fifth contract performs arbitrary-precision exponentiation under modulo. Here, 00 is taken to be one, and x mod 0 is zero for all x. The first word in the input specifies the number of bytes that the first non-negative integer B occupies. The second word in the input specifies the number of bytes that the second non-negative integer E occupies. The third word in the input specifies the number of bytes that the third non-negative integer M occupies. These three words are followed by B, E and M. The rest of the input is discarded. Whenever the input is too short, the missing bytes are considered to be zero. The output is encoded big-endian into the same format as M’s.

(219) (220) (221)

(222) (223)

(224)

(225)

(226)

(227) (228) (229) (230) (231) (232)

(233)

ΞEXPMOD ≡ gr =

f (x) ≡

l′E = o =

lB ≡ lE ≡ lM ≡ B ≡ E ≡ M ≡

i[x] ≡

ΞPRE except: 􏰐f􏰅max(lM,lB)􏰆max(l′E,1)􏰑

x2

􏰌 2􏰍 x

4



􏰌 2􏰍 x

 16 0

Gquaddivisor

+96x−3072
+ 480x − 199680

if x ≤ 64
if 64 < x ≤ 1024

otherwise

⌊log (E)⌋ 2

if lE ≤ 32 ∧ E = 0
iflE ≤32∧E̸=0
if 32 < lE ∧ i[(96 + lB)..(127 + lB)] ̸= 0 otherwise

8(lE − 32) + ⌊log2(i[(96 + lB)..(127 + lB)])⌋ 8(lE − 32)

􏰈BE mod M􏰉 ∈ N8lM i[0..31]

i[32..63]
i[64..95]
i[96..(95 + lB )]
i[(96 + lB)..(95 + lB + lE)]
i[(96+lB +lE)..(95+lB +lE +lM)] 􏰒Id[x] if x < ∥Id∥

0 otherwise

E.1. zkSNARK Related Precompiled Contracts. We choose two numbers, both of which are prime.

1. (234)  p ≡ 21888242871839275222246405745257275088696311157297823662689037894645226208583

2. (235)  q ≡ 21888242871839275222246405745257275088548364400416034343698204186575808495617

Since p is a prime number, {0, 1, . . . , p − 1} forms a field with addition and multiplication modulo p. We call this field Fp.

ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER 22

We define a set C1 with
(236) C1 ≡ {(X,Y) ∈ Fp ×Fp | Y2 = X3 +3}∪{(0,0)} We define a binary operation + on C1 for distinct elements (X1, Y1), (X2, Y2) with

(237) (X1, Y1) + (X2, Y2) ≡ λ≡

􏰒(X,Y) ifX1̸=X2 (0, 0) otherwise

Y2 − Y1 X2 − X1

X ≡ λ2−X1−X2
Y ≡ λ(X1−X)−Y1

In the case where (X1, Y1) = (X2, Y2), we define + on C1 with

(238) (X1, Y1) + (X2, Y2) ≡ λ≡

􏰒(X,Y) ifY1̸=0

X ≡ λ2−2X1
Y ≡ λ(X1−X)−Y1

(C1,+) is known to form a group. We define scalar multiplication · with (239) n·P ≡(0,0)+P +···+P

􏰞 􏰝􏰜 􏰟

n

for a natural number n and a point P in C1.
We define P1 to be a point (1,2) on C1. Let G1 be the subgroup of (C1,+) generated by P1. G1 is known to be a

cyclic group of order q. For a point P in G1, we define logP1(P) to be the smallest natural number n satisfying n·P1 = P. logP1 (P ) is at most q − 1.

Let Fp2 be a field Fp[i]/(i2 + 1). We define a set C2 with
(240) C2 ≡ {(X,Y) ∈ Fp2 ×Fp2 | Y2 = X3 +3(i+9)−1}∪{(0,0)}

We define a binary operation + and scalar multiplication · with the same equations (237), (238) and (239). (C2,+) is also known to be a group. We define P2 in C2 with

(241) P2 ≡ (11559732032986387107991004021392285783925812861821192530917403151452391805634 × i+10857046999023057135944570762232829481370756359578518086990519993285655852781,4082367875863433681332203403145435568316851327593401208105741076214120093531 × i+8495653923123431417604973247489272438418190587263600148770280649306958101930)

We define G2 to be the subgroup of (C2,+) generated by P2. G2 is known to be the only cyclic group of order q on C2. ForapointP inG2,wedefinelogP2(P)bethesmallestnaturalnumbernsatisfyingn·P2 =P. Withthisdefinition, logP2 (P ) is at most q − 1.

Let GT be the multiplicative abelian group underlying Fq12. It is known that a non-degenerate bilinear map e : G1 × G2 → GT exists. This bilinear map is a type three pairing. There are several such bilinear maps, it does not matterwhichischosentobee. LetPT =e(P1,P2),abeasetofkpointsinG1,andbbeasetofkpointsinG2. It follows from the definition of a pairing that the following are equivalent

(242) logP1(a1)×logP2(b1)+···+logP1(ak)×logP2(bk) k

≡ 1 = PT

mod q

(243)
Thus the pairing operation provides a method to verify (242).

􏰕 e (ai, bi) i=0

A 32 byte number x ∈ P256 might and might not represent an element of Fp.

(244) δp(x) ≡

􏰒x ifx<p ∅ otherwise

(0, 0)

3X12 2Y1

otherwise

(245)

(246)

(247) (248)

(249)

(250)

(251) (252) (253) (254)

δ1(x) ≡ g1 ≡

x ≡

(255) (256) (257)

(258) (259)

(260)

(261) (262) (263)

(264) (265)

(266) (267) (268) (269) (270) (271)

ΞSNARKV ≡ ΞSNARKV(σ, g, I) = F ≡

k = gr =

o[0..31] ≡ v ≡

a1 ≡ b1 ≡

.

ΞBN

ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER 23

A 64 byte data x ∈ B512 might and might not represent an element of G1.

􏰒g1 if g1 ∈ G1 ∅ otherwise

􏰒(x,y) ifx̸=∅∧y̸=∅ ∅ otherwise

δp (x[0..31])

y ≡
A 128 byte data x ∈ B1024 might and might not represent an element of G2.

δ2 (x) ≡ g2 ≡

x0 ≡ y0 ≡ x1 ≡ y1 ≡

􏰒g2 if g2 ∈ G2 ∅ otherwise

􏰒((x0i+y0),(x1i+y1))
∅ otherwise

δp (x[0..31]) δp (x[32..63]) δp (x[64..95]) δp (x[96..127])

δp (x[32..63])

if x0 ̸= ∅∧y0 ̸= ∅∧x1 ̸= ∅∧y1 ̸= ∅

We define ΞSNARKV as a precompiled contract which checks if (242) holds, for intended use in zkSNARK verification.

ak ≡ bk ≡

ΞPRE except:
􏰅∅,0,A0,()􏰆 if F (∥Id∥mod192̸=0∨(∃j.aj =∅∨bj =∅))

∥Id ∥ 192

80000k + 100000 􏰒0x0000000000000000000000000000000000000000000000000000000000000001

0x0000000000000000000000000000000000000000000000000000000000000000 (logP1(a1)×logP2(b1)+···+logP1(ak)×logP2(bk)≡1 modq)

δ1 (Id [0..63]) δ2 (Id [64..191])

δ1 (Id [(∥Id ∥ − 192)..(∥Id ∥ − 129)])

if v ∧ ¬F if ¬v ∧ ¬F

δ2 (Id [(∥Id ∥ − 128)..(∥Id ∥ − 1)]) We define a precompiled contract for addition on G1.

ΞBN ADD ADD(σ, g, I) gr o x y

≡ ΞBN PRE except:

• =  􏰅∅,0,A0,()􏰆 ifx=∅∨y=∅

• =  500

• ≡  δ−1(x + y) where + is the group operation in G1 1

  􏰅 ̄ 􏰆

• ≡  δ1 Id [0..63]

  􏰅 ̄ 􏰆

• ≡  δ1 Id [64..127]

̄
Id [x] ≡

􏰒Id[x] if x < ∥Id∥ 0 otherwise

(272)
We define a precompiled contract for scalar multiplication on G1, where Id is defined in (272).

(273) (274) (275) (276) (277) (278)

ΞBN MUL ≡ ΞBN MUL(σ,g,I) = gr = o ≡ x ≡ n ≡

̄

δ−1(n · x) where · is the scalar multiplication in G1 1

􏰅 ̄ 􏰆 δ1 Id [0..63]

̄
Id [64..95]

ΞPRE except:

􏰅∅,0,A0,()􏰆 if x = ∅

40000