Add ed25519 Precompile

[fgrust]

Issue

ed25519 Precompile Contracts Verification #4028

Test

Unit Test

$ go test -run TestPrecompiledEd25519Verify -v
=== RUN   TestPrecompiledEd25519Verify
=== RUN   TestPrecompiledEd25519Verify/valid_input-Gas=1584
=== RUN   TestPrecompiledEd25519Verify/valid_input_2_word_msg-Gas=1608
=== RUN   TestPrecompiledEd25519Verify/valid_input_4_word_msg-Gas=1632
=== RUN   TestPrecompiledEd25519Verify/valid_input_with_empty_message-Gas=1584
=== RUN   TestPrecompiledEd25519Verify/invalid_input_malformed_public_key-Gas=1584
=== RUN   TestPrecompiledEd25519Verify/invalid_input_malformed_signature-Gas=1584
=== RUN   TestPrecompiledEd25519Verify/invalid_input_msg_too_short-Gas=1584
=== RUN   TestPrecompiledEd25519Verify/invalid_input_empty-Gas=1560
--- PASS: TestPrecompiledEd25519Verify (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/valid_input-Gas=1584 (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/valid_input_2_word_msg-Gas=1608 (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/valid_input_4_word_msg-Gas=1632 (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/valid_input_with_empty_message-Gas=1584 (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/invalid_input_malformed_public_key-Gas=1584 (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/invalid_input_malformed_signature-Gas=1584 (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/invalid_input_msg_too_short-Gas=1584 (0.00s)
    --- PASS: TestPrecompiledEd25519Verify/invalid_input_empty-Gas=1560 (0.00s)
PASS
ok  	github.com/harmony-one/harmony/core/vm	0.376s

Benchmark Test

$ GOMAXPROCS=1 go test  -cpu 1 -bench=BenchmarkPrecompiledEd25519Verify -benchmem
goos: darwin
goarch: amd64
pkg: github.com/harmony-one/harmony/core/vm
cpu: Intel(R) Core(TM) i3-8100 CPU @ 3.60GHz
BenchmarkPrecompiledEd25519Verify/valid_input-Gas=1584         	   17872	     67076 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrecompiledEd25519Verify/valid_input_2_word_msg-Gas=1608         	   17751	     67488 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrecompiledEd25519Verify/valid_input_4_word_msg-Gas=1632         	   17727	     67650 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrecompiledEd25519Verify/valid_input_with_empty_message-Gas=1584 	   17840	     69256 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrecompiledEd25519Verify/invalid_input_malformed_public_key-Gas=1584         	  270217	      4365 ns/op	      16 B/op	       1 allocs/op
BenchmarkPrecompiledEd25519Verify/invalid_input_malformed_signature-Gas=1584          	   17877	     66969 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrecompiledEd25519Verify/invalid_input_msg_too_short-Gas=1584                	   17731	     69212 ns/op	       0 B/op	       0 allocs/op
BenchmarkPrecompiledEd25519Verify/invalid_input_empty-Gas=1560                        	96895422	        12.29 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/harmony-one/harmony/core/vm	14.830s

Reference

This PR includes the implementation to perform fast and cheap verification of Ed25519 cryptographic signatures in smart contract in general by adding a precompiled contract for Ed25519 signature verification to the HVM. Referred to CIP-25.

Specs

Parameters:

• public key: the 32-octet Ed25519 public key of the signer
• signature: the 64-octet Ed25519 signature
• message: the arbitrary length message that was signed

Address

The address of Ed25519 is 0xFA

Gas costs

Gas cost for Ed25519 is calculated with the formula:

lengthCeil = LEN(INPUT) + SHA2_512_WORD_LENGTH - 1
words = lengthCeil / SHA2_512_WORD_LENGTH
gas = ED25519VFY_BASE_GAS + SHA2_512_BASE_GAS + (words * SHA2_512_PER_WORD_GAS)

The base gas price is 1500