In lib/circuits/mdoc/mdoc_generate_circuit.cc:generate_circuit(), the MdocSignature object is constructed with order=n256_order. This is passed to MAC::verify_mac() when checking the common inputs e, dpkx, and dpky. This adds assertions checking that each value is less than the scalar field order. It appears that the various forms of e are directly compared against signature verification witnesses and the SHA-256 output, with no modular reduction step. As a result, if a credential produces a hash greater than or equal to the scalar field modulus, the circuit would reject any proof involving that credential. This can happen with probability ≈2-32, which could lead to a small number of actual spurious failures if the system is deployed broadly enough, with periodically re-issued credentials. Since traditional ECDSA validation just computes s from e and other parameters using modular arithmetic, I think the ECDSA verification circuit ought to be able to validate signatures with e > n as well.
The comments note that the verification circuit's soundness does not hold for e=0, and the same would hold for e=n. However, I think the same reasoning applies to both cases: since the circuits also check that e is the output of a hash function, it is computationally infeasible to find a set of witness values that would exploit either the e=0 case or the e=n case.
The checks on dpkx and dpky appear to be incorrect, but their impact is very small, since the base field and scalar field orders are so close to each other. Each of the two checks adds ≈2-130 to the completeness error.
The e value shows up in three places in the signature circuit. It gets encoded as a single field element on its own witness wire, it gets packed into multiple wires for one of the MAC messages, and it gets mixed into multi-scalar multiplication table index witness values. Currently, the circuit reconstructs e from the latter two places, and asserts that all three values are equal. If we are to remove the e < n restriction, the rest of the circuit would need some changes. If we let both bitwise reconstructions wrap around in the base field, this would introduce a small amount of malleability, as the multi-scalar multiplication could use e ± p instead of e. This may not be an exploitable soundness issue, but it could pose a headache for validation efforts. Alternately, we could require that the MAC message exactly match the message hash, use e mod n for both the MSM table indices and the single-wire e witness input, and add a modular reduction step in the circuit when checking consistency between the different inputs. This would ensure the MSM produces the correct answer. (Or the modular reduction step could be placed in the hash circuit, changing witness inputs from e to e mod n across the board) Furthermore, the single-wire e witness input, at the start of the signature circuit private inputs, may not be necessary. The reconstructed values from the MAC message and table indices could potentially be compared against each other directly, if the reconstruction, conditional subtraction, and equality assertion don't increase the overall circuit depth.
In
lib/circuits/mdoc/mdoc_generate_circuit.cc:generate_circuit(), theMdocSignatureobject is constructed withorder=n256_order. This is passed toMAC::verify_mac()when checking the common inputse,dpkx, anddpky. This adds assertions checking that each value is less than the scalar field order. It appears that the various forms ofeare directly compared against signature verification witnesses and the SHA-256 output, with no modular reduction step. As a result, if a credential produces a hash greater than or equal to the scalar field modulus, the circuit would reject any proof involving that credential. This can happen with probability ≈2-32, which could lead to a small number of actual spurious failures if the system is deployed broadly enough, with periodically re-issued credentials. Since traditional ECDSA validation just computes s from e and other parameters using modular arithmetic, I think the ECDSA verification circuit ought to be able to validate signatures with e > n as well.The comments note that the verification circuit's soundness does not hold for e=0, and the same would hold for e=n. However, I think the same reasoning applies to both cases: since the circuits also check that e is the output of a hash function, it is computationally infeasible to find a set of witness values that would exploit either the e=0 case or the e=n case.
The checks on
dpkxanddpkyappear to be incorrect, but their impact is very small, since the base field and scalar field orders are so close to each other. Each of the two checks adds ≈2-130 to the completeness error.The
evalue shows up in three places in the signature circuit. It gets encoded as a single field element on its own witness wire, it gets packed into multiple wires for one of the MAC messages, and it gets mixed into multi-scalar multiplication table index witness values. Currently, the circuit reconstructsefrom the latter two places, and asserts that all three values are equal. If we are to remove thee < nrestriction, the rest of the circuit would need some changes. If we let both bitwise reconstructions wrap around in the base field, this would introduce a small amount of malleability, as the multi-scalar multiplication could use e ± p instead of e. This may not be an exploitable soundness issue, but it could pose a headache for validation efforts. Alternately, we could require that the MAC message exactly match the message hash, usee mod nfor both the MSM table indices and the single-wireewitness input, and add a modular reduction step in the circuit when checking consistency between the different inputs. This would ensure the MSM produces the correct answer. (Or the modular reduction step could be placed in the hash circuit, changing witness inputs frometoe mod nacross the board) Furthermore, the single-wireewitness input, at the start of the signature circuit private inputs, may not be necessary. The reconstructed values from the MAC message and table indices could potentially be compared against each other directly, if the reconstruction, conditional subtraction, and equality assertion don't increase the overall circuit depth.