merkledrop.gno
10.84 Kb · 316 lines
1// Package merkledrop is a Merkle-gated airdrop that actually moves GNOT.
2//
3// It is the successor to r/moul/x/daily/merkledrop/v0, which was generated by
4// the daily pipeline and is deployed on mainnet. v0 works, but it is a
5// demonstration rather than a drop, and its proof scheme is safe by accident.
6// Everything below is what changed and why.
7//
8// # 1. The leaf scheme is domain separated
9//
10// v0 hashed leaves bare and combined nodes commutatively, the OpenZeppelin
11// scheme: leaf = sha256(addr|amount), node = sha256(min||max). Without a
12// leaf/inner tag an inner-node hash is also a valid leaf hash, so anyone who
13// can present a 64-byte leaf preimage can prove membership of a leaf that was
14// never committed.
15//
16// v0 is not exploitable, but only by arithmetic: an inner preimage is exactly
17// 64 bytes, and a v0 leaf preimage is at most 40 (bech32 address) + 1 + 20
18// (uint64 has at most 20 digits) = 61 bytes. 61 < 64, so no collision is
19// reachable. Change the leaf encoding, widen the amount, use a different
20// address form, and the forgery goes live with no visible diff at the call
21// site. That is not a property to rely on.
22//
23// v1 uses gno.land/p/moul/x/merkle/v0, which is the Tendermint scheme: leaves
24// are tagged 0x00 and inner nodes 0x01, so the two preimage spaces cannot
25// overlap at any length.
26//
27// # 2. Proofs are bound to a position
28//
29// v0's proof was a bare sibling list of any length, folded until it ran out.
30// v1's proof carries its index and the total leaf count, and the verifier
31// rebuilds the tree shape from them: a proof cannot be replayed at another
32// index, and one of the wrong length is rejected rather than folded. The
33// sibling count is capped at merkle.MaxDepth, so an untrusted caller cannot
34// choose the length of the loop.
35//
36// # 3. The root is settable, and the drop can close
37//
38// v0's root is a `const`, so the drop can never be re-rooted, extended or
39// ended. v1's owner sets the root, the leaf count and an optional closing
40// height, and can sweep the remainder once it closes.
41//
42// # 4. It moves real coins
43//
44// v0 keeps a uint64 ledger and moves nothing; its README says so, but it sits
45// on mainnet reading like an airdrop. v1 sends ugnot from the realm's own
46// address through the banker, and refuses a claim it cannot pay rather than
47// marking it claimed.
48//
49// # Who the claimer is
50//
51// The claimer is PreviousRealm().Address(), the immediate caller. Called
52// directly by a user that is the user; called through another realm it is that
53// REALM. This is not a hole, because the leaf binds the address and the proof
54// must match the claimer, so an intermediary can only claim an allocation
55// granted to the intermediary itself. It does mean a wrapper realm cannot
56// claim on a user's behalf, which is deliberate.
57//
58// Built on gno.land/p/moul/x/merkle/v0.
59package merkledrop
60
61import (
62 "errors"
63 "strconv"
64 "strings"
65
66 "chain"
67 "chain/banker"
68 "chain/runtime"
69 "chain/runtime/unsafe"
70
71 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/merkle/v0"
72 "gno.land/p/nt/avl/v0"
73 "gno.land/p/nt/ownable/v0"
74)
75
76// Denom is the only coin this drop pays in.
77const Denom = "ugnot"
78
79// leafPrefix is part of every leaf preimage, so a proof for one drop cannot be
80// replayed against another realm that happens to use the same encoding.
81const leafPrefix = "gno.land/r/moul/x/daily/merkledrop/v1"
82
83// Owner may set the drop and sweep it.
84//
85// Hardcoded rather than derived from the deployer at init: inside a plain
86// `func Test(t *testing.T)` the gno test runner reports OriginCaller() as the
87// EMPTY address, so an owner taken from it is the empty address in every test
88// and whatever deployed on chain. That divergence is exactly where an
89// authorization bug hides, so the address is written down instead.
90const Owner = address("g1manfred47kzduec920z88wfr64ylksmdcedlf5")
91
92var (
93 // Ownable holds the address allowed to set the drop and sweep it.
94 Ownable *ownable.Ownable
95
96 root []byte // the committed allocation root; nil means no drop
97 total int // leaf count the root commits to
98 closesAt int64 // chain height after which claims are refused; 0 = never
99 claimed avl.Tree // padded index -> claimer address string
100 paid int64 // running total of ugnot sent
101
102 // demo holds the allocations of the seeded example drop, so Render can
103 // show working proofs. A real drop commits only a root and leaves this
104 // empty: the whole point of a Merkle drop is not storing the allocations.
105 demo []Allocation
106)
107
108// Allocation is one entry of a drop: who may claim, and how much.
109type Allocation struct {
110 Address address
111 Amount int64
112}
113
114var (
115 ErrNoDrop = errors.New("merkledrop: no drop is configured")
116 ErrClosed = errors.New("merkledrop: the drop has closed")
117 ErrClaimed = errors.New("merkledrop: already claimed")
118 ErrBadProof = errors.New("merkledrop: invalid proof")
119 ErrUnfunded = errors.New("merkledrop: the drop cannot cover this claim")
120 ErrStillOpen = errors.New("merkledrop: the drop has not closed yet")
121 ErrBadRoot = errors.New("merkledrop: root must be 32 bytes of hex")
122 ErrBadTotal = errors.New("merkledrop: total must be positive")
123 ErrBadAmount = errors.New("merkledrop: amount must be positive")
124)
125
126func init() {
127 Ownable = ownable.NewWithAddress(Owner)
128 seed()
129}
130
131// Leaf returns the exact preimage committed for one allocation. Reproduce it
132// off chain to rebuild the tree; it is the whole interface between the drop
133// and its generator.
134//
135// leaf = "<pkgpath>|<index>|<address>|<amount>"
136func Leaf(index int, addr address, amount int64) string {
137 return leafPrefix + "|" + strconv.Itoa(index) + "|" + addr.String() + "|" + strconv.FormatInt(amount, 10)
138}
139
140// SetDrop commits a new allocation root. Owner only.
141//
142// totalLeaves is the number of allocations the root commits to; the verifier
143// needs it to rebuild the tree shape, so a wrong value invalidates every
144// proof rather than weakening any. closesAtHeight is the last height at which
145// a claim is accepted, or 0 for a drop that never closes.
146//
147// Setting a new root abandons the previous claim ledger: a drop is a
148// commitment, and replacing it starts a new one.
149func SetDrop(cur realm, rootHex string, totalLeaves int, closesAtHeight int64) {
150 Ownable.AssertOwnedBy(unsafe.PreviousRealm().Address())
151 rb, err := parseRoot(rootHex)
152 if err != nil {
153 panic(err.Error())
154 }
155 if totalLeaves <= 0 {
156 panic(ErrBadTotal.Error())
157 }
158 root, total, closesAt = rb, totalLeaves, closesAtHeight
159 claimed, paid, demo = avl.Tree{}, 0, nil
160 chain.Emit("DropSet",
161 "root", rootHex,
162 "total", strconv.Itoa(totalLeaves),
163 "closesAt", strconv.FormatInt(closesAtHeight, 10),
164 )
165}
166
167// Claim proves the caller is allocated amount at index and pays it out.
168//
169// proof is the comma-separated hex sibling list from the tree generator, leaf
170// first. It panics on a closed drop, a double claim, a bad proof, or a drop
171// that cannot cover the amount; nothing is marked claimed in any of those
172// cases.
173func Claim(cur realm, index int, amount int64, proof string) {
174 if len(root) == 0 {
175 panic(ErrNoDrop.Error())
176 }
177 if IsClosed() {
178 panic(ErrClosed.Error())
179 }
180 if amount <= 0 {
181 panic(ErrBadAmount.Error())
182 }
183 if HasClaimed(index) {
184 panic(ErrClaimed.Error())
185 }
186
187 claimer := unsafe.PreviousRealm().Address()
188 p, err := merkle.ParseProof(index, total, proof)
189 if err != nil {
190 panic(ErrBadProof.Error())
191 }
192 if !p.Verify(root, []byte(Leaf(index, claimer, amount))) {
193 panic(ErrBadProof.Error())
194 }
195
196 // Check funds BEFORE recording the claim, so an underfunded drop does not
197 // burn an allocation.
198 if Balance() < amount {
199 panic(ErrUnfunded.Error())
200 }
201
202 claimed.Set(indexKey(index), claimer.String())
203 paid += amount
204
205 bnk := banker.NewBanker(banker.BankerTypeRealmSend, cur)
206 bnk.SendCoins(Address(), claimer, chain.NewCoins(chain.NewCoin(Denom, amount)))
207
208 chain.Emit("Claimed",
209 "index", strconv.Itoa(index),
210 "account", claimer.String(),
211 "amount", strconv.FormatInt(amount, 10),
212 )
213}
214
215// Sweep returns whatever is left to the owner, once the drop has closed. Owner
216// only. A drop with no closing height can never be swept, which is the point
217// of setting one.
218func Sweep(cur realm) {
219 owner := Ownable.Owner()
220 Ownable.AssertOwnedBy(unsafe.PreviousRealm().Address())
221 if closesAt == 0 || !IsClosed() {
222 panic(ErrStillOpen.Error())
223 }
224 left := Balance()
225 if left <= 0 {
226 return
227 }
228 bnk := banker.NewBanker(banker.BankerTypeRealmSend, cur)
229 bnk.SendCoins(Address(), owner, chain.NewCoins(chain.NewCoin(Denom, left)))
230 chain.Emit("Swept", "amount", strconv.FormatInt(left, 10))
231}
232
233// Address returns the realm's own address, which is where the drop is funded.
234// Send ugnot here to fund it.
235func Address() address { return chain.PackageAddress(leafPrefix) }
236
237// Balance returns the ugnot the drop still holds.
238func Balance() int64 {
239 return banker.NewReadonlyBanker().GetCoins(Address()).AmountOf(Denom)
240}
241
242// Root returns the committed root, hex-encoded, or "" when no drop is set.
243func Root() string {
244 if len(root) == 0 {
245 return ""
246 }
247 return hexOf(root)
248}
249
250// Total returns the number of allocations the root commits to.
251func Total() int { return total }
252
253// ClosesAt returns the last height a claim is accepted, or 0 for never.
254func ClosesAt() int64 { return closesAt }
255
256// IsClosed reports whether the drop is past its closing height.
257func IsClosed() bool { return closesAt != 0 && runtime.ChainHeight() > closesAt }
258
259// Paid returns the ugnot claimed so far.
260func Paid() int64 { return paid }
261
262// Claims returns the number of allocations claimed.
263func Claims() int { return claimed.Size() }
264
265// HasClaimed reports whether the allocation at index was claimed.
266func HasClaimed(index int) bool { return claimed.Has(indexKey(index)) }
267
268// ClaimedBy returns the address that claimed index, or the empty address.
269func ClaimedBy(index int) address {
270 v := claimed.Get(indexKey(index))
271 if v == nil {
272 return ""
273 }
274 return address(v.(string))
275}
276
277// Verify checks an allocation against the committed root without claiming it,
278// so a recipient can confirm a proof before spending gas on Claim.
279func Verify(index int, addr address, amount int64, proof string) bool {
280 if len(root) == 0 {
281 return false
282 }
283 p, err := merkle.ParseProof(index, total, proof)
284 if err != nil {
285 return false
286 }
287 return p.Verify(root, []byte(Leaf(index, addr, amount)))
288}
289
290func parseRoot(s string) ([]byte, error) {
291 p, err := merkle.ParseProof(0, 1, strings.TrimSpace(s))
292 if err != nil || len(p.Siblings) != 1 {
293 return nil, ErrBadRoot
294 }
295 return p.Siblings[0], nil
296}
297
298func hexOf(b []byte) string {
299 const digits = "0123456789abcdef"
300 out := make([]byte, 0, len(b)*2)
301 for _, c := range b {
302 out = append(out, digits[c>>4], digits[c&0x0f])
303 }
304 return string(out)
305}
306
307// indexKey pads the index so avl iteration is numeric, not lexicographic.
308// ufmt has no width flags, so the padding is by hand: unpadded keys sort
309// "0","1","10","11","2" and Render would lose the order past nine entries.
310func indexKey(i int) string {
311 s := strconv.Itoa(i)
312 for len(s) < 6 {
313 s = "0" + s
314 }
315 return s
316}
