hyperlane.gno
11.57 Kb · 319 lines
1// Package hyperlane is Hyperlane's wire format, byte for byte, for a mailbox on gno.land: the message and its id,
2// the incremental merkle tree the validators checkpoint, the checkpoint digest they sign, a warp route's token
3// message, and the multisig check a destination runs over the signatures. It keeps no state and reads no chain.
4//
5// Sources (hyperlane-monorepo 3cd9308, 2026-10-10): solidity/contracts/libs/Message.sol, Merkle.sol,
6// CheckpointLib.sol, TypeCasts.sol, token/libs/TokenMessage.sol, isms/libs/MessageIdMultisigIsmMetadata.sol; the
7// vectors in vectors/ are this package's tests.
8//
9// One departure, and only on the gno side: gno.land has no secp256k1, so the multisig a gno mailbox runs
10// (VerifyMultisig) takes ed25519 signatures over the same checkpoint digest Hyperlane's validators sign with
11// secp256k1, and each signature names its validator in one leading byte (65 bytes a signature, as in Hyperlane's
12// metadata). Messages, ids, the tree and the digest are Hyperlane's exactly, so the other chain's ISM checks a gno
13// checkpoint with its stock code.
14package hyperlane
15
16import (
17 "crypto/bech32"
18 "crypto/ed25519"
19 "crypto/keccak256"
20 "encoding/binary"
21 "errors"
22)
23
24const (
25 // Version is the message version every Hyperlane mailbox speaks (Versioned.VERSION).
26 Version = 3
27 // HeaderLen is the message header: version 1, nonce 4, origin 4, sender 32, destination 4, recipient 32.
28 HeaderLen = 77
29 // TreeDepth is the merkle tree's depth (Merkle.sol TREE_DEPTH).
30 TreeDepth = 32
31 // MaxLeaves is how many leaves the tree takes (Merkle.sol MAX_LEAVES, 2^32 - 1).
32 MaxLeaves = 1<<TreeDepth - 1
33
34 sigLen = 65 // a signature's slot in multisig metadata: Hyperlane's r‖s‖v, here validator byte ‖ ed25519
35 metaLen = 68 // the metadata's fixed head: merkle tree hook 32, root 32, index 4
36)
37
38// ------------------------------------------------------------- message --
39
40// Message is a Hyperlane message (Message.sol). Sender and recipient are 32 bytes: a 20-byte address is padded on
41// the left with twelve zero bytes (AddressToBytes32); a Solana pubkey is its 32 bytes as they are.
42type Message struct {
43 Version uint8
44 Nonce uint32
45 Origin uint32
46 Sender [32]byte
47 Destination uint32
48 Recipient [32]byte
49 Body []byte
50}
51
52// Bytes is the message on the wire: abi.encodePacked of the fields, big-endian, no length prefixes.
53func (m Message) Bytes() []byte {
54 b := make([]byte, 0, HeaderLen+len(m.Body))
55 b = append(b, m.Version)
56 b = binary.BigEndian.AppendUint32(b, m.Nonce)
57 b = binary.BigEndian.AppendUint32(b, m.Origin)
58 b = append(b, m.Sender[:]...)
59 b = binary.BigEndian.AppendUint32(b, m.Destination)
60 b = append(b, m.Recipient[:]...)
61 return append(b, m.Body...)
62}
63
64// ID is the message's id: keccak256 of the whole message, body included.
65func (m Message) ID() [32]byte { return ID(m.Bytes()) }
66
67// ID is the id of a message as it came off the wire.
68func ID(raw []byte) [32]byte { return keccak256.Sum256(raw) }
69
70// ParseMessage reads a message off the wire. The body is a copy.
71func ParseMessage(b []byte) (Message, error) {
72 if len(b) < HeaderLen {
73 return Message{}, errors.New("hyperlane: message shorter than its header")
74 }
75 var m Message
76 m.Version = b[0]
77 m.Nonce = binary.BigEndian.Uint32(b[1:5])
78 m.Origin = binary.BigEndian.Uint32(b[5:9])
79 copy(m.Sender[:], b[9:41])
80 m.Destination = binary.BigEndian.Uint32(b[41:45])
81 copy(m.Recipient[:], b[45:77])
82 m.Body = append([]byte(nil), b[HeaderLen:]...)
83 return m, nil
84}
85
86// ---------------------------------------------------------- addresses --
87
88// AddressToBytes32 is a gno address as Hyperlane carries one: twelve zero bytes, then the address's twenty
89// (TypeCasts.addressToBytes32).
90func AddressToBytes32(a address) ([32]byte, error) {
91 var out [32]byte
92 hrp, bz, err := bech32.DecodeToBase256(string(a))
93 if err != nil {
94 return out, err
95 }
96 if hrp != "g" || len(bz) != 20 {
97 return out, errors.New("hyperlane: not a gno address: " + string(a))
98 }
99 copy(out[12:], bz)
100 return out, nil
101}
102
103// Bytes32ToAddress is the gno address a bytes32 names: twelve zero bytes, then the address's twenty (§13: the top
104// 12 bytes must be zero). A bytes32 whose top twelve bytes are not zero — a raw Solana pubkey, say — is no gno
105// address and errors, rather than landing on the address its last twenty bytes happen to spell, which nobody
106// holds (the EVM's TypeCasts.bytes32ToAddress truncates; a gno route sweeps such a recipient instead, §5.4).
107func Bytes32ToAddress(b [32]byte) (address, error) {
108 for _, c := range b[:12] {
109 if c != 0 {
110 return "", errors.New("hyperlane: not a gno address: the top twelve bytes are not zero")
111 }
112 }
113 s, err := bech32.EncodeFromBase256("g", b[12:])
114 if err != nil {
115 panic(err) // twenty bytes always encode
116 }
117 return address(s), nil
118}
119
120// -------------------------------------------------------- merkle tree --
121
122// Tree is Hyperlane's incremental merkle tree (Merkle.sol, the eth2 deposit contract's): depth 32, nodes
123// keccak256(left ‖ right), leaves the message ids themselves. The zero value is the empty tree.
124type Tree struct {
125 Branch [TreeDepth][32]byte
126 Count uint32
127}
128
129// zeroes[i] is the root of an empty subtree of height i: Z0 = 0, Zi+1 = keccak256(Zi ‖ Zi).
130var zeroes = func() [TreeDepth][32]byte {
131 var z [TreeDepth][32]byte
132 for i := 1; i < TreeDepth; i++ {
133 z[i] = hash2(z[i-1], z[i-1])
134 }
135 return z
136}()
137
138func hash2(a, b [32]byte) [32]byte {
139 buf := make([]byte, 64)
140 copy(buf, a[:])
141 copy(buf[32:], b[:])
142 return keccak256.Sum256(buf)
143}
144
145// Insert adds a leaf at index Count.
146func (t *Tree) Insert(leaf [32]byte) {
147 if t.Count >= MaxLeaves {
148 panic("hyperlane: merkle tree full")
149 }
150 t.Count++
151 size := t.Count
152 node := leaf
153 for i := 0; i < TreeDepth; i++ {
154 if size&1 == 1 {
155 t.Branch[i] = node
156 return
157 }
158 node = hash2(t.Branch[i], node)
159 size >>= 1
160 }
161 panic("hyperlane: merkle insert fell through") // unreachable: Count < 2^32 has a bit set below 32
162}
163
164// Root is the tree's root now (Merkle.sol root(), with the zero hashes).
165func (t *Tree) Root() [32]byte {
166 var cur [32]byte
167 for i := 0; i < TreeDepth; i++ {
168 if (t.Count>>uint(i))&1 == 1 {
169 cur = hash2(t.Branch[i], cur)
170 } else {
171 cur = hash2(cur, zeroes[i])
172 }
173 }
174 return cur
175}
176
177// ---------------------------------------------------------- checkpoint --
178
179// DomainHash binds a checkpoint to its origin chain and that chain's merkle tree hook: keccak256(origin ‖ hook ‖
180// "HYPERLANE"), 45 bytes hashed (CheckpointLib.domainHash). On Solana the hook is the mailbox program's id.
181func DomainHash(origin uint32, hook [32]byte) [32]byte {
182 b := make([]byte, 0, 45)
183 b = binary.BigEndian.AppendUint32(b, origin)
184 b = append(b, hook[:]...)
185 b = append(b, "HYPERLANE"...)
186 return keccak256.Sum256(b)
187}
188
189// CheckpointDigest is what a validator signs for one message: the EIP-191 personal-message hash of
190// keccak256(domainHash ‖ root ‖ index ‖ messageID) (CheckpointLib.digest). root and index are the origin tree's
191// right after messageID went in at index; a message-id ISM does not check them, only the signatures over them.
192func CheckpointDigest(origin uint32, hook, root [32]byte, index uint32, messageID [32]byte) [32]byte {
193 d := DomainHash(origin, hook)
194 b := make([]byte, 0, 100)
195 b = append(b, d[:]...)
196 b = append(b, root[:]...)
197 b = binary.BigEndian.AppendUint32(b, index)
198 b = append(b, messageID[:]...)
199 return EthSignedMessageHash(keccak256.Sum256(b))
200}
201
202// EthSignedMessageHash is EIP-191's hash of a 32-byte message: keccak256("\x19Ethereum Signed Message:\n32" ‖ h).
203func EthSignedMessageHash(h [32]byte) [32]byte {
204 b := append([]byte("\x19Ethereum Signed Message:\n32"), h[:]...)
205 return keccak256.Sum256(b)
206}
207
208// -------------------------------------------------------- token message --
209
210// TokenMessage is a warp route's body (TokenMessage.sol): the recipient on the destination, the amount as a
211// big-endian uint256, then metadata (usually none).
212func TokenMessage(recipient [32]byte, amount uint64, metadata []byte) []byte {
213 b := make([]byte, 0, 64+len(metadata))
214 b = append(b, recipient[:]...)
215 b = append(b, make([]byte, 24)...)
216 b = binary.BigEndian.AppendUint64(b, amount)
217 return append(b, metadata...)
218}
219
220// ParseTokenMessage reads a warp route's body. An amount past 2^64 - 1 is refused; trailing metadata (Solana's
221// TransferRemoteWithMemo writes a memo there) is returned, not refused.
222func ParseTokenMessage(b []byte) (recipient [32]byte, amount uint64, metadata []byte, err error) {
223 if len(b) < 64 {
224 return recipient, 0, nil, errors.New("hyperlane: token message shorter than 64 bytes")
225 }
226 for _, c := range b[32:56] {
227 if c != 0 {
228 return recipient, 0, nil, errors.New("hyperlane: token amount past 64 bits")
229 }
230 }
231 copy(recipient[:], b[:32])
232 return recipient, binary.BigEndian.Uint64(b[56:64]), append([]byte(nil), b[64:]...), nil
233}
234
235// ------------------------------------------------------------ multisig --
236
237// Checkpoint is the head of multisig metadata: the origin's merkle tree hook, and the root and index the
238// validators signed (MessageIdMultisigIsmMetadata).
239type Checkpoint struct {
240 Hook [32]byte
241 Root [32]byte
242 Index uint32
243}
244
245// Signature is one validator's ed25519 signature and its place in the validator set.
246type Signature struct {
247 Validator uint8
248 Sig [64]byte
249}
250
251// MultisigMetadata lays out what a relayer hands a gno mailbox: hook 32 ‖ root 32 ‖ index 4, then 65 bytes a
252// signature: the validator's index in the set, then its ed25519 signature over CheckpointDigest. Validator
253// indexes strictly increase, so no validator counts twice.
254func MultisigMetadata(c Checkpoint, sigs []Signature) []byte {
255 b := make([]byte, 0, metaLen+sigLen*len(sigs))
256 b = append(b, c.Hook[:]...)
257 b = append(b, c.Root[:]...)
258 b = binary.BigEndian.AppendUint32(b, c.Index)
259 for _, s := range sigs {
260 b = append(b, s.Validator)
261 b = append(b, s.Sig[:]...)
262 }
263 return b
264}
265
266// ParseMultisigMetadata reads metadata laid out by MultisigMetadata.
267func ParseMultisigMetadata(b []byte) (Checkpoint, []Signature, error) {
268 var c Checkpoint
269 if len(b) < metaLen || (len(b)-metaLen)%sigLen != 0 {
270 return c, nil, errors.New("hyperlane: metadata is not 68 bytes and whole 65-byte signatures")
271 }
272 copy(c.Hook[:], b[0:32])
273 copy(c.Root[:], b[32:64])
274 c.Index = binary.BigEndian.Uint32(b[64:68])
275 n := (len(b) - metaLen) / sigLen
276 sigs := make([]Signature, n)
277 for i := 0; i < n; i++ {
278 o := metaLen + sigLen*i
279 sigs[i].Validator = b[o]
280 copy(sigs[i].Sig[:], b[o+1:o+sigLen])
281 }
282 return c, sigs, nil
283}
284
285// VerifyMultisig is a message-id multisig ISM over ed25519: the first threshold signatures in metadata must be
286// valid signatures, by distinct validators in increasing order, over the checkpoint digest of this message from
287// its own origin. validators are ed25519 public keys of 32 bytes. Signatures past the threshold are not read.
288func VerifyMultisig(validators [][]byte, threshold int, metadata, message []byte) error {
289 if threshold < 1 || threshold > len(validators) {
290 return errors.New("hyperlane: no usable validator set for this origin")
291 }
292 m, err := ParseMessage(message)
293 if err != nil {
294 return err
295 }
296 c, sigs, err := ParseMultisigMetadata(metadata)
297 if err != nil {
298 return err
299 }
300 if len(sigs) < threshold {
301 return errors.New("hyperlane: fewer signatures than the threshold")
302 }
303 digest := CheckpointDigest(m.Origin, c.Hook, c.Root, c.Index, ID(message))
304 last := -1
305 for _, s := range sigs[:threshold] {
306 v := int(s.Validator)
307 if v <= last {
308 return errors.New("hyperlane: signatures out of validator order")
309 }
310 if v >= len(validators) {
311 return errors.New("hyperlane: signature names no validator")
312 }
313 if !ed25519.Verify(validators[v], digest[:], s.Sig[:]) {
314 return errors.New("hyperlane: a signature does not verify")
315 }
316 last = v
317 }
318 return nil
319}
