---
# System prepended metadata

title: Chipmunk review

---

We thank the reviewers for editorial comments and we will address all of them.

Reviewers B, C (Incremental Contribution):

The main focus of our work lies in providing a **concretely** efficient multi-signature scheme that is plausibly post-quantum secure.
The result of these efforts is Chipmunk, which is 5x smaller than the previous state-of-the-art construction Squirrel.
This makes it the first plausibly post-quantum multi-signature scheme that may fit in a single Ethereum block and does not require post-quantum STARKs, which would significantly increase block time due to costly provers.
Our main contribution is the overall Chipmunk design, not any single improvement.
Given the significant importance of multi-signatures for cryptocurrencies, we think Chipmunk’s design and full implementation is an important practical contribution worthy of publication at CCS.

Reviewers B, C (Stronger Security Notion):

Both reviewers have noted the stronger security notions as weaknesses of our work. 
We apologize for any potential confusion here. 
At no point did we claim that Squirrel does not satisfy the new notion. Footnote 5 in Section 5 explicitly states that Squirrel satisfies it.
It is important to provide appropriate definitions for the primitives we aim to construct. Squirrel "accidentally" already satisfied them, but a future construction might not, which could lead to problems should such a primitive ever be deployed in practice.

Reviewer B (Security Loss vs Real-World Parameters):

We keep track of all constraints our parameters need to satisfy in Table 1. As is common practice, we ignore the loss incurred in the forking lemma. We follow best practices for setting the parameters in accordance to the best known attacks following the model from [ADPS16].

Reviewer B (128-bit security)

Parameters for 128-bit security are in Table 4.
For the use-case of Ethereum, block sizes are around 150 KB, so we want to find a parameterization that allows fitting signatures into a block. Trading security for size may appear risky but many of Ethereum's components already fall short of 128-bit security. The BN254 curve has ~100-bit while zkStarks/Plonky2 has ~80-bit.

Review B (NTRU)

Neither Squirrel nor Chipmunk use NTRU lattices.

Reviewer A (Synchronization in the Real World):

In Ethereum, slots are [12 seconds long](https://notes.ethereum.org/@vbuterin/SkeyEI3xv) and validators are required and financially incentivized to produce attestations for the *current* block within a small timeframe. This is not unreasonable, seeing that Ethereum currently does exactly this with BLS signatures. Typically, 99% of validators are signing timely.

Generally, for synchronized multi-signatures, slots are just arbitrary labels that the signers need to agree on.
The relation to "time" only comes from the (main) application in blockchains where using block height as labels is natural.
Validators need to produce signatures attesting to what they think the head of the blockchain at a given block height should be. Observe that this connection between a signature and a point in time pertains to the meaning of the message, not to the time of signing. Albeit typically useless, a validator could produce an attestation at any later time. Signers in our construction can miss signing for slot $i$, but then continue with slot $i+1$ and not all potential validator have to sign each block.


Reviewer A (Generalized Forking Lemma):

The order in which the adversary issues the random oracle queries for $j$ and $j-1$ (or whether any of those are issued at all) does not matter. The queries do not use designated parts of list of random values in the generalized Forking Lemma. At any point in time the next query (whatever the value of $j$) will use the next unused part of the list of random values. The only part to be slightly careful about is that we need to reorder the random values in each chunk, such that the designated key $pk^*$ we want to forge under is always associated with the **last** value in a particular chunk. But this was already the case in the unforgeability proof for Squirrel and does not change.

Reviewer A (Secret Key Size):

The techniques from Squirrel for mitigating the large key-size are equally applicable to Chipmunk.
Instead of storing the entire tree, the signer can store a PRF seed and the top few layers.
During signing they would recompute the bottom part of the path but fetch the top part from memory.
This way, the signer can trade signing times for secret key size.
Even a secret key that is a few GB large is not a real issue in practice. For example, in the Ethereum usecase, validators are all powerful nodes with lots of memory. E.g., a typical AWS instance is equiped with 64 cores and 128 GB of RAM.
We will elaborate a bit more on this in our paper.

Reviewer A (Number of SVP Calls):

The number of SVP calls is indeed $8d$. We will explicitly mention this in the revision.