About the contract account, there are 3 subtasks that make up the bad account series. This article is the second task of the series, Bendy Signatures.
Analysis
There are 2 contracts in the question, sphinx is an abstract account contract, which calls the open method of the gates contract. Sphinx has many restrictions and provides 3 public keys, one of which has a private key. The question simulates a 2/3 multi-signature problem, where 2 sets of signatures need to be passed in order to send a verification transaction.
In the __validate__ of the account contract, starknet::get_tx_info().unbox() is used to obtain the signature of the transaction. We need to construct a raw_sig with a length of 6, where raw_sig[0] and raw_sig[3] are public keys, raw_sig[1] and raw_sig[4] are the r values of the signatures, and raw_sig[2] and raw_sig[5] are the s values of the signatures. The public key needs to be one of the predetermined 3 public keys, and r and s cannot be repeated. At the same time, __execute__ limits calls.len() == 1, so we cannot generate 2 transactions with the same private key to solve the problem.
Since there is only 1 private key, we need to sign with this private key to generate two sets of r and s that can be verified and are not repeated. The problem becomes how to use the SDK to send a transaction with 2 valid signatures.
Process
First, I tried to generate two sets of open transactions with different maxFee in Starknet.js and signed them separately, but they could not be verified by the testnet.
After consulting with the mentor, I found that the actual problem to be cracked in this question is the ECDSA malleability problem, which can be referred to in the ZK book.
I spent some time learning about ECDSA, which involves a lot of mathematical knowledge. If you are not familiar with the principles of ECDSA, I recommend studying it in depth. The content in the ZK Book mentioned above is great.
StarkNet also uses ECDSA to generate signatures. The ECDSA signature process output by ChatGPT is as follows:
1. First, you need a private key, which is a randomly chosen integer. At the same time, you also need a public key, which is the product of the private key and the base point G, denoted as Q = dG, where d is the private key and G is the base point.
2. When you want to sign a message, first convert the message into an integer through a hash function, denoted as z.
3. Then, choose a random integer k and calculate the point R = kG. The x-coordinate of R is part of the signature, denoted as r.
4. Next, calculate s = (z + r * d) / k. This s is another part of the signature.
The final signature is (r, s).
The corresponding steps in Starknet.js are as follows:
- Use
ec.starkCurve.getStarkKey(privateKey)to obtain the public key. The public key is known and can be skipped. - Use
hash.calculateTransactionHashto convert the transaction details into a messageHash. The 6 parameters required for the transaction need to be set by yourself, and the calldata can be obtained usingtransaction.getExecuteCalldata. - r is a random number and does not need to be set by yourself. It can be obtained directly in the next step.
- Use
ec.starkCurve.sign(msgHash, privateKey)orsigner.signTransactionto obtain r and s.
According to the reference material on ECDSA malleability mentioned above, due to symmetry, one r corresponds to 2 s values that can make the signature valid. The calculation of the second s is very simple, and the required additional parameter can be found in the SDK source code. The final generated r1 == r2, s1 != s2.
Another method is to generate two different r values using different seeds. There is a corresponding method in the Python library. The final generated r1 != r2, s1 != s2.
Construct a list of length 6 as required by the question, pass it into the signature of account.invokeFunction, fill in the other required parameters, and send it to complete the task.
Summary
This question introduces how multi-signature wallet contracts work on one hand, and involves the ECDSA malleability problem on the other hand. It also requires understanding the composition of transactions. It will be very rewarding if you can complete it.