Your type is not type
The scrypt code of the prediction market vala.ai (you can find the code here) had a bug that allowed anyone to steal the money in every market that have less than 3 choices.
This bug existed (imo) because the type system of scrypt doesn't offer sufficient safety guarantee: to exploit this bug you have to use a publickey that is too long to possibly be a publickey (even tho in the code it has the type PubKey), and you have to make a collision between sha256(publickey + somestuff) and sha256(leftsubroot + rightsubroot), which would be impossible if you had only a function "hash" that would use a different hash function everytime unless specified otherwise, the programmer would have then specify that the root of the merkletree have a type "HASH1" and leafs a type "HASH2".
(The bug is now fixed, and the site is safe to use)
Vala.ai and how it stores entries
Vala.ai is prediction market. Users can vote on a market by buying/selling "shares" that'll be worth something if the chosen even turns out to happen. Each market have its own smart contract that store who has which shares.
Because there is no easy way in scrypt to store entries in a smart contract (in solidity a simple map does the job very well), vala.ai uses a merkletree (actually a modified version of the merkletree available in the boilerplate repository)
Leafs stored are the hash of the concatenation of a publickey and some information. To then update entries, a signature by your publickey is asked. However, to add an entry no signature is asked, hence you add entries with whatever publickey even if it's not a publickey.
For the rest of the article you don't need any knowledge about merkletrees, or how it is implemented, but if you want to learn more about it consider reading the vala.ai article about it.
The bug
Vala.ai stores leaf this way (link to the code here).
And the merkletree is stored this way (link to the code here).
So as soon as newLeaf is actually a subtree it's jackpot (yes that's it).
(Only possible because the same hash function is used on both side. You'd have a type for leafs and for subtree it'd be impossible).
Luckily the publicKey is first, so you choose publicKey to be "the root of the a tree of your choice" and some padding so that the right side is 32bytes (this is possible when the number of options is <= 3 because of newEntrySharesHex that have a variable length).
This is possible to choose publicKey this way because no checksig check is made, and even tho it has the type PubKey it can't be a publicKey.
You can play with this exploit here: ok.js (github.com)
It starts at line45. I was in the forked version of boilerplate by valaPM because it has a different merkletree scrypt code. I haven't tested in the regular boilerplate repo. I think you also need to modify merkletreetest to add testAddLeafSafe. You also need the old version of the boilerplate repo, because the current one has the bug fixed.
Here is also the explanation I wrote when I disclosed the bug. It can probably help to understand.
The fix
The bug was fixed with this commit. This fixes the bug because please read their article about it.
We waited for some markets to expire before releasing this article, so the only live market that can be exploited is "mine" about the rank of bsv at the end of 2022 and the TLV is quite low so please don't try to exploit it. Every new market have the bug fixed and are immune to this attack. I also believe it's unlikely another bug can be found in the code (I haven't checked everything tho, especially I checked only action==1 or 2).
What could have prevented it
Maybe abstraction would have prevent this bug.
With abstraction you'd have a map and so no need to use a subtle merkletree.
Also types (yes I know I write a language that have no types so it's a bit hypocritical).
Types would verify the types of the object used. You ask for a publickey, then ask for a checksig or issue a warning, at least it'd verify its length. You ask for an int, then verify it's an int (by adding 0 to it). The Sha256 type would make sure it's indeed an hash, ...
It's probably too naive anyway. Eth devs write (almost) assembly directly, so probably don't care much about abstraction/types.
So I'm now selling security audits :)
Because I've found this bug, and a bug in op_push_tx, I believe I am "good" at finding exploit, and so probably "good" at doing audits or at least "good" at finding bugs in your code (before someone malicious finds them).
To the best of my knowledge, I'm actually the only one to have found bugs in public scrypt code available to all. If you are looking for a security audit, I'm probably one of the best choice available.
Because of that, I'm either selling:
A standard security audit, that can be either private or public. You get a pdf with the list of all the issues, and if it's public you can claim that it's been audited by me (hopefully it builds trust). Whether I find bugs or not the price is unfortunately the same, and only depends on the complexity of the project and if it's private/public.
A check of your code, and you pay only if I find a bug. I actually prefer this option, win/win for everyone. And you pay only for major bugs, not small stuff (that I'll tell you for free), so a true win/win situation. Same as above, it can be either private or public I don't care.
If you are interested, or know someone that could be interested, please dm me on twitter.
End word
Please try my compiler, it’s awesome: frenchfrog42.github.io.
And please try vala.ai, the UI is actually very nice (the code too). I provide liquidity for a market that's about the rank of bsv at the end of 2022, please bet on it. I can remember checking quickly the scryptcode before placing 200$ on it and thinking "ok it seems my money is safe there, no apparent bugs" ^^'
And, please, be careful. Contracts are immutable.