gnark
gnark copied to clipboard
[std] Implement Bowe-Hopwood Pedersen hash in Montgomery form
A double-and-add scalar multiplication by N
costs on average log(N)
doublings and log(N/2)
additions. For twisted Edwards curves (used in gnark for edDSA circuits), it costs 7 rank-1 constraints (Groth16) to describe an addition in affine coordinates and 6 for a doubling. These twisted Edwards curves can be converted to Montgomery form where it costs 4 R1C for an addition and 5 for a doubling. To convert a point from twisted Edwards to Montgomery it costs 2 R1C and the inverse map costs 2 R1C. Note that the formulae in Montgomery are incomplete. However, this form can be used only for implementing Bowe-Hopwood Pedersen hash which can be done using only additions.
N.B.: same logic might be applied to sparse R1CS count (PlonK).