[Money Supply] Try to audit the airdrop, and find duplicate addresses and keys in airdrop trees

[eggry]

Hi, I am new to the Handshake, and attracted by its interesting airdrop mechanism.

As #549 mentioned, the airdrop tree is impossible to audit. However, with the help of claim witnesses on the chain, it is still possible to audit this airdrop, at least to some extent.

I explore the airdrop claims for the first 150,000 blocks (until Dec. 10, 2022), and find multiple duplicates in the airdrop trees.

Duplicates in the faucet tree

The faucet tree is published in the plain text. so it is possible to audit each airdrop.

As discussed in handshake-org/hs-airdrop#20, seems like the faucet tree is designed to include each address only once. However, there are still 17 duplicate addresses in the final tree.

address                                       #
hs1qv7cndn4zttf2cyzw5dr330xnzylp5dz9dzh56x    2
hs1qu2zqenh8jdxvaqz7nwun4r3k32klmuf6ss2y9s    2
hs1qxgwd3t6kzw72m4ywx4fj9rqx5fqqsa6fm2sltc    2
hs1qymue45suswzt3ynkjl6vkutrafgfqr6g3dwzuc    2
hs1qeh4q4el90mklmdjxxrd5rfk9j72c755gq69w8f    2
hs1qgfzuxpg05t4zs323ly3dtnuwpc9tt94glvkvxm    2
hs1q3lkysn74p39xfxc2pzf8ewmvaezwagsvehdd7t    2
hs1q9qy2w96hphls2kq862pjf73shleuvf0sshrcxe    2
hs1qjk8ys3n3l7ct9lmpqsszxr34dn5h8efexfxf2j    2
hs1qwrrlczge2vt0xa3ktwvfwdpchhftzc0zhwyvr3    2
hs1qhzvr94u7yanswn6et25nrje3fsucgsd5nhmqfg    2
hs1qhsmch5g5dy9774ek46zmwk0pmj3z5ahrgsu0ep    2
hs1qp99ll9m9rqk39w6lexh06mvevf9gnkm0tpt04f    2
hs1qzpr7r25qu4qz9y6xjgjw3txnyhm777v27ljfqe    2
hs1q9drsmaqkpp7ewv4wedufw6rjgdcp9zv4e6c8le    2
hs1qng3mfk23uuqynl8s287h6nul8pye2rajdvz2gu    2
hs1qnvkypvp5uchnujj8awl8th0lm998m0c7c3pf5y    2

An explanation is that the implementation is problematic: The deduplicate is based on the hash of airdrop keys (codes), which related to more fields such as airdrop value (codes). In the end, two airdrops for the same recipient address would not be viewed as identical so long as their values differ, such as hs1qu2zqenh8jdxvaqz7nwun4r3k32klmuf6ss2y9s at L348 and L1273.

Duplicates in the airdrop tree

The airdrop tree includes the hashes of airdrop keys (code). Each airdrop key is derived from a public key by applying a nonce, or generating a new identity.

It is insufficient to audit the tree by comparing these hashes, as a single public key could produce multiple different hashes by simply changing the nonce. However, the witnesses of airdrop claims may reveal the underlying public keys, which enables us to audit those claimed parts.

According to those witnesses, there are 6522 airdrops claimed as of height 149,999, and thousands of them revealed publicly (all RSA keys, some ED25519 and some P256 keys).

KeyType       #
GOO        4709
RSA        1595
ED25519     198
P256         20

From these keys, we could identify at least 5 keys appeared twice:

Claim Height	Coinbase Index	Airdrop Tree Index	Subtree Index	Revealed Key
66497	1	87539	5	ssh-rsa AAAAB3N...pMfF47f
66498	1	176206	6	ssh-rsa AAAAB3N...pMfF47f
67359	2	168651	5	ssh-rsa AAAAB3N...aXM0Q==
67359	3	43780	2	ssh-rsa AAAAB3N...aXM0Q==
67563	1	32324	6	ssh-rsa AAAAB3N...7MU1Q==
67564	1	18035	7	ssh-rsa AAAAB3N...7MU1Q==
69311	1	170234	0	ssh-rsa AAAAB3N...6uKDw==
69311	2	65464	7	ssh-rsa AAAAB3N...6uKDw==
97877	1	189649	0	ssh-rsa AAAAB3N...9z88w==
97944	1	124990	2	ssh-rsa AAAAB3N...9z88w==

Therefore, some public keys are used multiple times when building the airdrop tree. Since only 3% airdrops have been claimed so far, there could be more duplicates in the actual tree.

Luckily, the Goosig was disabled (#305), so all RSA claims must reveal their real key. To prevent this duplication, the miner could check whether the public key appears in the previous claims.

As for the code, the problem is that the public keys are NEVER deduplicated when building the airdrop tree. Although GitHub does not allow two users share the same public key at the same time, it is still possible to delete the key and add it to another account. Since the crawl takes about a week, such rebind may cause duplication in the crawled data. Moreover, the airdrop tree includes public keys from three sources. The duplication may occur among or within the lists. However, we may never know what happened when the tree was built, since the crawled raw data were destroyed.

Duplicates between the faucet tree and the airdrop tree

Although the keys of faucet recipients are removed from the airdrop key, there are still 4 addresses that claimed both faucet and airdrop:

• hs1q749at7cxz8favygqysx93pare0j87ltejd75wu
• hs1q7pa7lva9h4t2l9nzssldky0agen9gexrcm7wsg
• hs1qmny783ajv79t0246xvy90dleh22cqts3cvfwwh
• hs1qvdlme2mw9c6ymznhdqajhth6dffe6pl3nqlumr

Seems that the faucet recipients are not fully removed from the airdrop. For example, the deduplicate of GitHub users is performed only based on the username. It does not consider the emails of GitHub accounts as other lists do.

Summary

Based on the published faucet tree and the claim witnesses of the airdrop, we could audit the airdrop to some extent. Results show that some addresses and public keys may be added multiple times when the tree was built. Such duplication may be introduced by problematic implementations.

To eliminate possible sybil attacks, a soft fork could be deployed to reject duplicate public keys in the claim witness. Or take further actions as discussed in #549.

[pinheadmz]

Wow really fantastic research, especially for a new user!

I can maybe explain a few of these observations. The faucet tree for example may contain user addresses in more than one "category." I am willing to risk my own privacy to acknowledge that my own faucet address appears twice. That's because I qualified for the GitHub OSS dev airdrop AND as a project creator, having worked for Purse.io and contributed to HNS code during testnet. However, my GitHub OSS airdrop being included in the faucet removed my airdrop from the big tree (I have tried to claim it, its not there).

A similar mechanism may explain the tree/faucet duplicates. For example the first address: hs1q749at7cxz8favygqysx93pare0j87ltejd75wu appears in the faucet with a large amount ~609k HNS, probably a project sponsor or creator. That address also claimed its 4k HNS from the OSS dev airdrop tree. Assuming this was the same user, they did not necessarily have to re-use their faucet address to claim the OSS airdrop, but they did. It is also possible that some other completely random OSS dev selflessly donated their airdrop to that address which would have been public in the hs-tree-data repo.

In both of these examples so far, users only received ONE OSS dev airdrop.

So, the duplicate exposed keys is certainly the most interesting observation, and I can't explain it right away. Are you totally certain that github does not allow multiple users to set the same PGP or SSH key?

One final note: We observed in mid-2021 that some pgp keys must have been stolen and used by hackers to claim HNS. I don't think this explains any of your observations, but may help understand at least why some addresses seem to claim multiple airdrops.

[eggry]

Are you totally certain that github does not allow multiple users to set the same PGP or SSH key?

From what I can tell, yes.

The GitHub forbids me to add the key ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIEkPoZVoo8usduO8IzsrZiidfzrahBMNOv38RXrTQIU6 (from https://api.github.com/user/1/keys) to my account, saying "Key is already in use".

However, I can not find any GitHub documents specifiying this behavior :(

[eggry]

The faucet tree for example may contain user addresses in more than one "category."

If it is acceptable to appear in multiple categories, such deduplication could potentially rejects some valid faucet airdrops :(

For example, if both naming.json AND foss.json were

[
    {
        "address": "hs1q749at7cxz8favygqysx93pare0j87ltejd75wu",
        "value": 1
    }
]

It would be rejected by the deduplication because of hash-collision.

However, it is possible to include an address multiple times in foss.json like

[
    {
        "address": "hs1qmny783ajv79t0246xvy90dleh22cqts3cvfwwh",
        "value": 1
    },
    {
        "address": "hs1qmny783ajv79t0246xvy90dleh22cqts3cvfwwh",
        "value": 2
    }
]

Moreover, both addresses are still eligible for the key-based OSS airdrop, because they are not in faucet.json (the only file used to duplicate two airdrops)

In both of these examples so far, users only received ONE OSS dev airdrop.

Maybe not... as stated above.

It is also possible that some other completely random OSS dev selflessly donated their airdrop to that address which would have been public in the hs-tree-data repo.

Yeah, that makes sense. I admit that the address-based observation is limited and inaccurate.

One final note: We observed in mid-2021 that some pgp keys must have been stolen and used by hackers to claim HNS. I don't think this explains any of your observations, but may help understand at least why some addresses seem to claim multiple airdrops.

Thanks for this note. Not explain my observation, but very interesting :)
I did notice that there are some addresses claimed multiple times, and I think it is reasonable sometimes, such as the case in handshake-org/hs-airdrop#109.