Skip to content

Instantly share code, notes, and snippets.

@agramajo

agramajo/challenge.txt

Last active May 10, 2024 19:39
Show Gist options
  • Save agramajo/c32f66e85c6ba94a12d43309990b8b76 to your computer and use it in GitHub Desktop.
Save agramajo/c32f66e85c6ba94a12d43309990b8b76 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
challenge.txt
Alice has posted a challenge: she will pay 100 BTC to anybody who has a secret
string, that once hashed using SHA256, produces a hash value with 13 leading
zero bits. Bob knows such a string, and wants to collect the prize -- but he
doesn't want to expose the secret, because then Eve, who is evesdropping on
every conversation, might beat him to it and claim the prize for herself.
How can Bob prove to Alice that he has this secret without revelaing it?
Write a circuit, in either Circom or Rust (Golang?), that makes this possible.
Raw
generate.py
import hashlib
import random
def find_hash_with_zeros(prefix, num_bits):
while True:
text = prefix + str(random.randint(0, 2**32))
hash_value = hashlib.sha256(text.encode()).digest()
val = 256 - int.from_bytes(hash_value, 'big').bit_length()
#print (hash_value.hex(), val)
if val == num_bits:
return text
prefix = "testale"
num_bits = 16
result = find_hash_with_zeros(prefix, num_bits)
print("Text:", result)
print("SHA256 Hash:", hashlib.sha256(result.encode()).hexdigest())
Raw
go.mod
module challenge
go 1.21.1
require (
github.com/consensys/gnark v0.10.0
github.com/consensys/gnark-crypto v0.12.2-0.20240215234832-d72fcb379d3e
)
require (
github.com/bits-and-blooms/bitset v1.8.0 // indirect
github.com/blang/semver/v4 v4.0.0 // indirect
github.com/consensys/bavard v0.1.13 // indirect
github.com/davecgh/go-spew v1.1.1 // indirect
github.com/fxamacker/cbor/v2 v2.5.0 // indirect
github.com/google/pprof v0.0.0-20230817174616-7a8ec2ada47b // indirect
github.com/ingonyama-zk/icicle v0.0.0-20230928131117-97f0079e5c71 // indirect
github.com/ingonyama-zk/iciclegnark v0.1.0 // indirect
github.com/mattn/go-colorable v0.1.13 // indirect
github.com/mattn/go-isatty v0.0.19 // indirect
github.com/mmcloughlin/addchain v0.4.0 // indirect
github.com/pmezard/go-difflib v1.0.0 // indirect
github.com/rs/zerolog v1.30.0 // indirect
github.com/stretchr/testify v1.8.4 // indirect
github.com/x448/float16 v0.8.4 // indirect
golang.org/x/crypto v0.17.0 // indirect
golang.org/x/sys v0.15.0 // indirect
gopkg.in/yaml.v3 v3.0.1 // indirect
rsc.io/tmplfunc v0.0.3 // indirect
)
Raw
go.sum
github.com/bits-and-blooms/bitset v1.8.0 h1:FD+XqgOZDUxxZ8hzoBFuV9+cGWY9CslN6d5MS5JVb4c=
github.com/bits-and-blooms/bitset v1.8.0/go.mod h1:7hO7Gc7Pp1vODcmWvKMRA9BNmbv6a/7QIWpPxHddWR8=
github.com/blang/semver/v4 v4.0.0 h1:1PFHFE6yCCTv8C1TeyNNarDzntLi7wMI5i/pzqYIsAM=
github.com/blang/semver/v4 v4.0.0/go.mod h1:IbckMUScFkM3pff0VJDNKRiT6TG/YpiHIM2yvyW5YoQ=
github.com/consensys/bavard v0.1.13 h1:oLhMLOFGTLdlda/kma4VOJazblc7IM5y5QPd2A/YjhQ=
github.com/consensys/bavard v0.1.13/go.mod h1:9ItSMtA/dXMAiL7BG6bqW2m3NdSEObYWoH223nGHukI=
github.com/consensys/gnark v0.10.0 h1:yhi6ThoeFP7WrH8zQDaO56WVXe9iJEBSkfrZ9PZxabw=
github.com/consensys/gnark v0.10.0/go.mod h1:VJU5JrrhZorbfDH+EUjcuFWr2c5z19tHPh8D6KVQksU=
github.com/consensys/gnark-crypto v0.12.2-0.20240215234832-d72fcb379d3e h1:MKdOuCiy2DAX1tMp2YsmtNDaqdigpY6B5cZQDJ9BvEo=
github.com/consensys/gnark-crypto v0.12.2-0.20240215234832-d72fcb379d3e/go.mod h1:wKqwsieaKPThcFkHe0d0zMsbHEUWFmZcG7KBCse210o=
github.com/coreos/go-systemd/v22 v22.5.0/go.mod h1:Y58oyj3AT4RCenI/lSvhwexgC+NSVTIJ3seZv2GcEnc=
github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
github.com/fxamacker/cbor/v2 v2.5.0 h1:oHsG0V/Q6E/wqTS2O1Cozzsy69nqCiguo5Q1a1ADivE=
github.com/fxamacker/cbor/v2 v2.5.0/go.mod h1:TA1xS00nchWmaBnEIxPSE5oHLuJBAVvqrtAnWBwBCVo=
github.com/godbus/dbus/v5 v5.0.4/go.mod h1:xhWf0FNVPg57R7Z0UbKHbJfkEywrmjJnf7w5xrFpKfA=
github.com/google/go-cmp v0.5.9 h1:O2Tfq5qg4qc4AmwVlvv0oLiVAGB7enBSJ2x2DqQFi38=
github.com/google/go-cmp v0.5.9/go.mod h1:17dUlkBOakJ0+DkrSSNjCkIjxS6bF9zb3elmeNGIjoY=
github.com/google/pprof v0.0.0-20230817174616-7a8ec2ada47b h1:h9U78+dx9a4BKdQkBBos92HalKpaGKHrp+3Uo6yTodo=
github.com/google/pprof v0.0.0-20230817174616-7a8ec2ada47b/go.mod h1:czg5+yv1E0ZGTi6S6vVK1mke0fV+FaUhNGcd6VRS9Ik=
github.com/google/subcommands v1.2.0/go.mod h1:ZjhPrFU+Olkh9WazFPsl27BQ4UPiG37m3yTrtFlrHVk=
github.com/ingonyama-zk/icicle v0.0.0-20230928131117-97f0079e5c71 h1:YxI1RTPzpFJ3MBmxPl3Bo0F7ume7CmQEC1M9jL6CT94=
github.com/ingonyama-zk/icicle v0.0.0-20230928131117-97f0079e5c71/go.mod h1:kAK8/EoN7fUEmakzgZIYdWy1a2rBnpCaZLqSHwZWxEk=
github.com/ingonyama-zk/iciclegnark v0.1.0 h1:88MkEghzjQBMjrYRJFxZ9oR9CTIpB8NG2zLeCJSvXKQ=
github.com/ingonyama-zk/iciclegnark v0.1.0/go.mod h1:wz6+IpyHKs6UhMMoQpNqz1VY+ddfKqC/gRwR/64W6WU=
github.com/kr/pretty v0.3.1 h1:flRD4NNwYAUpkphVc1HcthR4KEIFJ65n8Mw5qdRn3LE=
github.com/kr/pretty v0.3.1/go.mod h1:hoEshYVHaxMs3cyo3Yncou5ZscifuDolrwPKZanG3xk=
github.com/kr/text v0.2.0 h1:5Nx0Ya0ZqY2ygV366QzturHI13Jq95ApcVaJBhpS+AY=
github.com/kr/text v0.2.0/go.mod h1:eLer722TekiGuMkidMxC/pM04lWEeraHUUmBw8l2grE=
github.com/leanovate/gopter v0.2.9 h1:fQjYxZaynp97ozCzfOyOuAGOU4aU/z37zf/tOujFk7c=
github.com/leanovate/gopter v0.2.9/go.mod h1:U2L/78B+KVFIx2VmW6onHJQzXtFb+p5y3y2Sh+Jxxv8=
github.com/mattn/go-colorable v0.1.12/go.mod h1:u5H1YNBxpqRaxsYJYSkiCWKzEfiAb1Gb520KVy5xxl4=
github.com/mattn/go-colorable v0.1.13 h1:fFA4WZxdEF4tXPZVKMLwD8oUnCTTo08duU7wxecdEvA=
github.com/mattn/go-colorable v0.1.13/go.mod h1:7S9/ev0klgBDR4GtXTXX8a3vIGJpMovkB8vQcUbaXHg=
github.com/mattn/go-isatty v0.0.14/go.mod h1:7GGIvUiUoEMVVmxf/4nioHXj79iQHKdU27kJ6hsGG94=
github.com/mattn/go-isatty v0.0.16/go.mod h1:kYGgaQfpe5nmfYZH+SKPsOc2e4SrIfOl2e/yFXSvRLM=
github.com/mattn/go-isatty v0.0.19 h1:JITubQf0MOLdlGRuRq+jtsDlekdYPia9ZFsB8h/APPA=
github.com/mattn/go-isatty v0.0.19/go.mod h1:W+V8PltTTMOvKvAeJH7IuucS94S2C6jfK/D7dTCTo3Y=
github.com/mmcloughlin/addchain v0.4.0 h1:SobOdjm2xLj1KkXN5/n0xTIWyZA2+s99UCY1iPfkHRY=
github.com/mmcloughlin/addchain v0.4.0/go.mod h1:A86O+tHqZLMNO4w6ZZ4FlVQEadcoqkyU72HC5wJ4RlU=
github.com/mmcloughlin/profile v0.1.1/go.mod h1:IhHD7q1ooxgwTgjxQYkACGA77oFTDdFVejUS1/tS/qU=
github.com/pkg/errors v0.9.1/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
github.com/rogpeppe/go-internal v1.11.0 h1:cWPaGQEPrBb5/AsnsZesgZZ9yb1OQ+GOISoDNXVBh4M=
github.com/rogpeppe/go-internal v1.11.0/go.mod h1:ddIwULY96R17DhadqLgMfk9H9tvdUzkipdSkR5nkCZA=
github.com/rs/xid v1.5.0/go.mod h1:trrq9SKmegXys3aeAKXMUTdJsYXVwGY3RLcfgqegfbg=
github.com/rs/zerolog v1.30.0 h1:SymVODrcRsaRaSInD9yQtKbtWqwsfoPcRff/oRXLj4c=
github.com/rs/zerolog v1.30.0/go.mod h1:/tk+P47gFdPXq4QYjvCmT5/Gsug2nagsFWBWhAiSi1w=
github.com/stretchr/testify v1.8.4 h1:CcVxjf3Q8PM0mHUKJCdn+eZZtm5yQwehR5yeSVQQcUk=
github.com/stretchr/testify v1.8.4/go.mod h1:sz/lmYIOXD/1dqDmKjjqLyZ2RngseejIcXlSw2iwfAo=
github.com/x448/float16 v0.8.4 h1:qLwI1I70+NjRFUR3zs1JPUCgaCXSh3SW62uAKT1mSBM=
github.com/x448/float16 v0.8.4/go.mod h1:14CWIYCyZA/cWjXOioeEpHeN/83MdbZDRQHoFcYsOfg=
golang.org/x/crypto v0.17.0 h1:r8bRNjWL3GshPW3gkd+RpvzWrZAwPS49OmTGZ/uhM4k=
golang.org/x/crypto v0.17.0/go.mod h1:gCAAfMLgwOJRpTjQ2zCCt2OcSfYMTeZVSRtQlPC7Nq4=
golang.org/x/sync v0.3.0 h1:ftCYgMx6zT/asHUrPw8BLLscYtGznsLAnjq5RH9P66E=
golang.org/x/sync v0.3.0/go.mod h1:FU7BRWz2tNW+3quACPkgCx/L+uEAv1htQ0V83Z9Rj+Y=
golang.org/x/sys v0.0.0-20210630005230-0f9fa26af87c/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
golang.org/x/sys v0.0.0-20210927094055-39ccf1dd6fa6/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
golang.org/x/sys v0.0.0-20220811171246-fbc7d0a398ab/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
golang.org/x/sys v0.6.0/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
golang.org/x/sys v0.15.0 h1:h48lPFYpsTvQJZF4EKyI4aLHaev3CxivZmv7yZig9pc=
golang.org/x/sys v0.15.0/go.mod h1:/VUhepiaJMQUp4+oa/7Zr1D23ma6VTLIYjOOTFZPUcA=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
gopkg.in/check.v1 v1.0.0-20201130134442-10cb98267c6c h1:Hei/4ADfdWqJk1ZMxUNpqntNwaWcugrBjAiHlqqRiVk=
gopkg.in/check.v1 v1.0.0-20201130134442-10cb98267c6c/go.mod h1:JHkPIbrfpd72SG/EVd6muEfDQjcINNoR0C8j2r3qZ4Q=
gopkg.in/yaml.v2 v2.4.0 h1:D8xgwECY7CYvx+Y2n4sBz93Jn9JRvxdiyyo8CTfuKaY=
gopkg.in/yaml.v2 v2.4.0/go.mod h1:RDklbk79AGWmwhnvt/jBztapEOGDOx6ZbXqjP6csGnQ=
gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
rsc.io/tmplfunc v0.0.3 h1:53XFQh69AfOa8Tw0Jm7t+GV7KZhOi6jzsCzTtKbMvzU=
rsc.io/tmplfunc v0.0.3/go.mod h1:AG3sTPzElb1Io3Yg4voV9AGZJuleGAwaVRxL9M49PhA=
Raw
main.go
/*
output:
bs:74657374616c6531323336343931383634
aux:[0 0 0 194 71 94 61 218 74 189 109 254 80 143 207 137 171 240 100 155 5 186 209 172 234 164 10 249 204 135 166 3]
aux encode:000000c2475e3dda4abd6dfe508fcf89abf0649b05bad1aceaa40af9cc87a603
[{116 true} {101 true} {115 true} {116 true} {97 true} {108 true} {101 true} {49 true} {50 true} {51 true} {54 true} {52 true} {57 true} {49 true} {56 true} {54 true} {52 true}]
[{0 true} {0 true} {0 true} {194 true} {71 true} {94 true} {61 true} {218 true} {74 true} {189 true} {109 true} {254 true} {80 true} {143 true} {207 true} {137 true} {171 true} {240 true} {100 true} {155 true} {5 true} {186 true} {209 true} {172 true} {234 true} {164 true} {10 true} {249 true} {204 true} {135 true} {166 true} {3 true}]
16:22:35 INF compiling circuit
16:22:35 INF parsed circuit inputs nbPublic=32 nbSecret=17
16:22:36 INF building constraint builder nbConstraints=153161
cs nbConstraints:153161, nbSecretWitness:17, nbPublicInstance:33
16:23:01 DBG constraint system solver done nbConstraints=153161 took=229.541274
16:23:01 DBG main.go:53 > {0_Val: 116, 1_Val: 101, 2_Val: 115, 3_Val: 116, 4_Val: 97, 5_Val: 108, 6_Val: 101, 7_Val: 49, 8_Val: 50, 9_Val: 51, 10_Val: 54, 11_Val: 52, 12_Val: 57, 13_Val: 49, 14_Val: 56, 15_Val: 54, 16_Val: 52}
16:23:01 DBG main.go:54 > {0_Val: 0, 1_Val: 0, 2_Val: 0, 3_Val: 194, 4_Val: 71, 5_Val: 94, 6_Val: 61, 7_Val: 218, 8_Val: 74, 9_Val: 189, 10_Val: 109, 11_Val: 254, 12_Val: 80, 13_Val: 143, 14_Val: 207, 15_Val: 137, 16_Val: 171, 17_Val: 240, 18_Val: 100, 19_Val: 155, 20_Val: 5, 21_Val: 186, 22_Val: 209, 23_Val: 172, 24_Val: 234, 25_Val: 164, 26_Val: 10, 27_Val: 249, 28_Val: 204, 29_Val: 135, 30_Val: 166, 31_Val: 3}
16:23:01 DBG main.go:55 > {0_Val: 0, 1_Val: 0, 2_Val: 0, 3_Val: 194, 4_Val: 71, 5_Val: 94, 6_Val: 61, 7_Val: 218, 8_Val: 74, 9_Val: 189, 10_Val: 109, 11_Val: 254, 12_Val: 80, 13_Val: 143, 14_Val: 207, 15_Val: 137, 16_Val: 171, 17_Val: 240, 18_Val: 100, 19_Val: 155, 20_Val: 5, 21_Val: 186, 22_Val: 209, 23_Val: 172, 24_Val: 234, 25_Val: 164, 26_Val: 10, 27_Val: 249, 28_Val: 204, 29_Val: 135, 30_Val: 166, 31_Val: 3}
16:23:02 DBG prover done acceleration=none backend=groth16 curve=bn254 nbConstraints=153161 took=979.78096
16:23:02 DBG verifier done backend=groth16 curve=bn254 took=1.905176
*/
package main
import (
"crypto/sha256"
"encoding/hex"
"fmt"
"github.com/consensys/gnark-crypto/ecc"
"github.com/consensys/gnark/backend/groth16"
"github.com/consensys/gnark/frontend"
"github.com/consensys/gnark/frontend/cs/r1cs"
"github.com/consensys/gnark/std/hash/sha2"
"github.com/consensys/gnark/std/math/uints"
)
type Packet struct {
Hash [32]uints.U8 `gnark:",public"` //Public hash
Secret []uints.U8 `gnark:",private"` //Secret
}
func (circuit *Packet) Define(api frontend.API) error { // circuit
uapi, err := uints.New[uints.U32](api)
if err != nil {
return err
}
h, err := sha2.New(api)
if err != nil {
return err
}
h.Write(circuit.Secret)
res := h.Sum()
api.Println(circuit.Secret)
api.Println(circuit.Hash)
api.Println(res)
uapi.ByteAssertEq(circuit.Hash[0], uints.NewU8(0))
uapi.ByteAssertEq(circuit.Hash[1], uints.NewU8(0))
uapi.ByteAssertEq(circuit.Hash[2], uints.NewU8(0))
for k := range circuit.Hash {
uapi.ByteAssertEq(circuit.Hash[k], res[k])
}
return nil
}
func bytetouint(PacketBytes []byte) [32]uints.U8 {
aux := uints.NewU8Array(PacketBytes)
var Packetaux [32]uints.U8
for j := 0; j < min(32, len(aux)); j++ {
Packetaux[j] = aux[j]
}
return Packetaux
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func Proof() Packet {
var Pack Packet
bs := []byte("testale1236491864")
fmt.Printf("bs:%v\n", hex.EncodeToString(bs))
shaa2 := sha256.New()
shaa2.Write(bs)
aux := shaa2.Sum(make([]byte, 0))
fmt.Printf("aux:%v\n", aux)
fmt.Printf("aux encode:%s\n", hex.EncodeToString(aux))
Pack.Hash = bytetouint(aux)
for i := 0; i < len(bs); i++ {
Pack.Secret = append(Pack.Secret, uints.NewU8(bs[i]))
}
fmt.Println(Pack.Secret)
fmt.Println(Pack.Hash)
return Pack
}
func main() {
packetaux := Proof()
assignment := &packetaux
myCircuit2 := Packet{
Secret: make([]uints.U8, len(packetaux.Secret)),
}
cs, _ := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &myCircuit2)
fmt.Printf("cs nbConstraints:%v, nbSecretWitness:%v, nbPublicInstance:%v\n", cs.GetNbConstraints(), cs.GetNbSecretVariables(), cs.GetNbPublicVariables())
pk, vk, _ := groth16.Setup(cs)
witness, errNW := frontend.NewWitness(assignment, ecc.BN254.ScalarField())
if errNW != nil {
panic(errNW)
}
proof, errProve := groth16.Prove(cs, pk, witness)
if errProve != nil {
panic(errProve)
}
pubWitness, _ := witness.Public()
err := groth16.Verify(proof, vk, pubWitness)
if err != nil {
panic(err)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment