gnark icon indicating copy to clipboard operation
gnark copied to clipboard

[std] Implement Bowe-Hopwood Pedersen hash in Montgomery form

Open yelhousni opened this issue 3 years ago • 0 comments

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).

yelhousni avatar Oct 28 '21 11:10 yelhousni