SnarkPack v2: A New Version of Filecoin’s Proof Aggregator
In the recent Filecoin Network v16 Skyr Upgrade, a new version of the SnarkPack proof aggregation library was released. This version did not introduce any new functionality, but instead hardened the cryptographic protocol itself. This post details what motivated the examination of the SnarkPack library, the issues we discovered, and how they were resolved and shipped into the Filecoin Network.
What is SnarkPack?
At the heart of the Filecoin protocol are a collection of cryptographic proofs, called Proofs-of-Replication (PoReps). These PoReps make possible the central promise of the Filecoin network: decentralized, verifiable storage.
SnarkPack is a cryptographic protocol to aggregate and verify multiple proofs at the same time in an efficient manner. The Filecoin protocol uses the SnarkPark library on Proofs-of-Replication, allowing for faster onboarding of storage to the network. More information on the SnarkPack library can be found by watching the presentation at Financial Crypto ‘22, and reading the corresponding paper or the associated blog post.
Among the many cryptographic techniques that SnarkPark relies on are Fiat-Shamir transformations. Informally speaking, Fiat-Shamir transformations are a cryptographic technique that remove the need for the verifier of a proof to be communicating with the prover of the statement in question. As these transformations are foundational to the aggregated proofs generated through SnarkPack, any issues with the Fiat-Shamir transformations jeopardize the correctness of SnarkPack itself.
Frozen Heart vulnerabilities
On Apr 13, 2022, Trail of Bits announced the disclosure of vulnerabilities that broke the soundness of various proof systems. These vulnerabilities, termed “Frozen Heart” vulnerabilities by the Trail of Bits team, centered on insecure implementations of Fiat-Shamir transformations, and could be exploited by malicious agents to “prove” incorrect statements. Since the Frozen Heart vulnerabilities could be used to attack protocols already in production, they were first disclosed to the various affected projects so that they could be securely remediated.
The announcement motivated the Filecoin cryptography teams to audit the SnarkPack implementation for the same vulnerabilities. This inspection revealed issues of a similar nature to the Frozen Heart vulnerabilities, also based on insecure implementations of Fiat-Shamir transformations. Unlike the aforementioned disclosures, however, the cryptography teams working on Filecoin found no direct attack on the Filecoin protocol that could be launched as a result of these issues. Nevertheless, the team resolved to fix these issues in order to adhere to security best practices, and ensure maximum possible soundness of the proofs that are critical to Filecoin’s security.
Issues in SnarkPack v1
In order to understand the incorrect aspects of the implementation of SnarkPack v1, we need to dive a little deeper into how Fiat-Shamir transformations work. As discussed earlier, these transformations convert interactive proving systems, that involve the verifier of the proof communicating with the prover, to non-interactive ones. The so-called “interactive” step that is replaced is usually the verifier communicating a random value to the prover that serves as a challenge. Fiat-Shamir transformations allow replacing the interaction with what is called a “Random Oracle” to generate the challenge. In practice, the Random Oracle is replaced by a secure hash function, so the prover can simply hash the public information and the partial outputs to that step, and use the result of the hash as the necessary random value (the so-called “challenge”). It is important that the prover feed as much information as possible into the hash; in particular, the prover should feed in all the values that a verifier would have had access to in the interactive version.
While simple in concept, implementations of Fiat-Shamir transformations require delicate care, because any public information that is not included in the hashing step widens the surface area for an attack. A malicious agent could modify any unhashed public information to produce bogus proofs.
In SnarkPack, when aggregating N proofs, there are log2(N) Fiat-Shamir transformations that need to be performed, in turn requiring log2(N) hashes to perform. Each hash computation must take as input all of the elements that the prover has already generated in the proving process. This can be mocked up in pseudo-code as follows:
rand = H(...)
for i in 0…log2(n):
A <- generate_proof_step(i)
rand <- H(rand, A)
B <- generate_post_randomness_step(rand)
Once this process is complete (that is, once the loop terminates after log2(N) steps), there is one last hash that needs to be computed – that is, one last randomness to be calculated. This randomness is then fed into the rest of the SnarkPack protocol. In pseudo-code, this is simply:
final_randomness = H(B)
The audit by CryptoNet revealed two main problems with SnarkPack v1’s implementation of this process:
- Skipping the first hash generation in the loop: When i=0, the code skips the call to the hash function, and instead reuses the previously generated randomness,from the first line. The ramification is that the first proof element A could be changed by the prover, without having the first randomness change.
- Skipping the very last randomness generation: This means that the KZG_proof would not be “linked” correctly with the previous steps of the proof.
These issues are relatively benign, since the other random values in the loop are still computed correctly. A hypothetical attacker would thus need to find inputs that match the other computed values in order to forge a meaningful proof. However, wanting to follow security best practices, and given the recent attention drawn to exploits of Fiat-Shamir implementations, we decided to adopt the necessary fixes in the next Filecoin network upgrade.
Introducing SnarkPack v2 to the network
The fix to both issues described above were made in the Bellperson repository by the Filecoin Crypto team, the pull request that implemented the fix can be found here. For readers who wish to look at the corrected code, we share links to the relevant subsections for Issue A (prover, verifier). Issue B (prover, verifier).
In order to properly apply the fixes, while preserving backward compatibility, the API was updated to add an AggregateVersion enumeration. This version is used as a flag to indicate whether we’re using the new, more secure, code path (SnarkPack v2) or the legacy code path (SnarkPack v1). Aggregated proofs that landed before the Skyr network upgrade were expected to be v1, while those that landed after the upgrade epoch were expected to be v2. The pull request that implemented this versioning in the proofs implementation can be found here, and was released in version 11.1.0.
The lotus team helped share these issues with the rest of the Filecoin Core Devs at a core dev meeting. The Core Devs reached consensus that the fix should be introduced into the Filecoin network as soon as possible, and so the introduction of SnarkPack v2 to the Filecoin network was scoped into the Skyr upgrade. The builtin-actors implementation that supports SnarkPack v2 can be found here, and it is consumed by all client implementations; the reference client implementation can be found here.
Security in the Filecoin Network
SnarkPack has been audited by cryptographers within the PLEngRes teams, and by other experts. Despite that, given the complexity of the protocol, bugs may still exist! As soon as the Trail of Bits blog posts series went out, we decided to revisit the SnarkPack implementation to make sure the proofs that power the Filecoin network are not vulnerable to the same kind of issues. We want to uphold the highest standard of security in the Filecoin network, and that includes keeping up with the latest security developments and cryptographic vulnerabilities. Filecoin also invites all security and cryptographic researchers to join us in maintaining and stewarding the security of the Filecoin Network; learn more about the Bug Bounty Program here.