Motivation
Advanced orders such as stop limit, allows users to place an order to cap profit, or loss on the system automatically. This has been a frequent requested feature. The biggest challenge to doing this on the blockchain is how can we hide the stop price from the public. It's a valid concern because when other traders know where the stop is, they are incentivized to push the price up or down, and activate automated limit order to execute. When large stops cluster, and get triggered automatically, the price of the asset falls fast, and open opportunities for other traders to buy in cheap.
Scope
Ideally, we need a solution where it works without any interaction from the trader from the point when the order is placed. Computation time should be comparable to plaintext comparisons. And ideally it does not change the existing consensus protocol.
Research
We've looked at the most advanced research in cryptography including Zero knowledge proof, Homomorphic Encryption, Secure Function Evaluation, and Secure Computation Execution. The most well known solution is Yao's millionaire problem. It essentially goes, out of N millionaires, how do we know which millionaire is the richest without revealing their information. Most of these solutions require online interaction to obscure the message, or provide some proof. Unfortunately, we can't expect trader to be online, which is the feature in itself. Other solution such as Homomorphic encryption requires both inputs to be encrypted. The use case is for encryption data, send to someone else to compute, and send encrypted result back to the original user with the private key to decrypt. For us, trader stop and future price are separate, and so it does not apply directly. There are other solution such as SFE, requires too much computation time. Shared secret such as Shamir can be done, but requires too many rounds of communication.
If we can't encrypt the code or input, then the next best thing is input and code obfuscation. XOR operator is the most popular because of its simplicity.
Let's suppose m is the Message, and S is secret. The cipher is M XOR S.
C = M XOR S
To decrypt,
M = C XOR S
Other techniques can be used in addition to obscure such as block ciphering , encoding the code into string, Dead code insertion, register reassignment, subroutine re-ordering, instruction subroutine, and code transportation. See 4
Design
We propose to extend the existing limit order by introducing an "encoded_script":
signed_transaction sell_asset(string seller_account, string amount_to_sell, string symbol_to_sell, string min_to_receive, string symbol_to_receive, string encoded_script, uint32_t timeout_sec = 0, bool fill_or_kill = false, bool broadcast = false)
This encoded script is generated by a compiler then evaluated by each block producer.
Compiler
We will provide an open compiler which takes a high level script then convert and obfuscate the code in webassembly, then encoded as base64.
P(limit_price, stop_price, order_type) = EncodeBase64(Compile(limit_price, stop_price, order_type))
Execution
The block producer will execute the web assembly code in a closed environment with an input (such as the current price), the program will produce a limit order. Once the order has been produced, the limit order is marked for deletion and will not be executed in the future.
P = DecodeBase64(encoded_script)
P(current_price) = limit_order || none
Obfuscation
Suppose we break up an int64 in 8 bytes, XOR it with one of the random byte in the dataset, shuffle the 8 bytes where it is "shifting and combining back to int64.
Combined, we have 8 bytes for stop, 8 bytes for limit, and 2x8 bytes for dummy values. We shuffle data ordering. The guesser has to choose 8 from 32 = 35960 combinations.
RSA based instead of XOR
Pohlig-hellman is a good shared secret encryption to apply.
C=M^e(mod p)
where M is the message, e is the key, and p is a prime number.
Plain = C^d mod p
This produces much larger cipher say, 4 x the original bytes. This increases the range of bytes to choose from 32 out of 128. eg 1477806921502280666682474774300 combinations to choose from.
How much work it takes to find the stop price?
- Listen to each block
- Decode the user script back into assembly but the stop price is in pieces
- Every script would look different (different inputs, different code), it is difficult to extract value.
Cost & Limitation
We must immediately set a limit on # of bytes that can be submitted and executed to prevent abuse (say 10Kbytes). Any transaction that does not meet this criteria will be rejected immediately. We may consider adding a whitelist of assembly instructions to prevent any unexpected execution (even though it's in a safe environment). In addition, the cost of platform fee for the order can be calculated based on the # of bytes submitted.
Extensibility
Two areas open up for future work on top of this protocol changes.
-
The compiler is independent of the blockchain protocol since it is generated on client side. That means, we can innovate more on the obfuscation without significant change.
-
More advanced orders can be added without changing the client protocol.
Links
- https://medium.com/@juliankoh/introduction-to-privacy-preserving-smart-contracts-e7bdc1a121b1
- https://blog.ethereum.org/2016/01/15/privacy-on-the-blockchain/
- https://blog.ethereum.org/2014/12/26/secret-sharing-daos-crypto-2-0/
- https://sensorstechforum.com/advanced-obfuscation-techniques-malware/
- https://www.andreafortuna.org/cybersecurity/malware-obfuscation-techniques-four-simple-examples/
- https://stackoverflow.com/questions/31678344/compare-two-integers-using-bit-operator
- https://profsims.com/encryption/poh