search

Consensys / gnark

gnark is a fast zk-SNARK library that offers a high-level API to design circuits. The library is open source and developed under the Apache 2.0 license
https://hackmd.io/@gnark
Apache License 2.0
1.41k stars 361 forks source link

Unexpected behaviour with api.Select() and api.ToBinary() #203

Closed vck3000 closed 2 years ago

vck3000 commented 2 years ago

Hi there,

I'm having some issues with reliability in my circuits. I've narrowed it down to some unexpected behaviour in api.Select() and api.ToBinary().

Here's the minimal reproducible code for the issue:

package main

import (
    "github.com/consensys/gnark-crypto/ecc"
    "github.com/consensys/gnark/backend"
    "github.com/consensys/gnark/backend/groth16"
    "github.com/consensys/gnark/frontend"
)

type Circuit struct {
}

func (circuit *Circuit) Define(curveID ecc.ID, api frontend.API) error {
    a := api.Constant(1)
    b := api.Select(a, api.Constant(2), api.Constant(4))

    api.Println(b)                             // This is 2 as expected.
    api.Println(api.ToBinary(b))               // Expect this to be 0100, but is not.
    api.Println(api.ToBinary(api.Constant(2))) // This is 0100 as expected.

    return nil
}

func main() {
    var circuit Circuit
    r1cs, err := frontend.Compile(ecc.BN254, backend.GROTH16, &circuit)

    if err != nil {
        panic(err)
    }

    pk, _, _ := groth16.Setup(r1cs)

    var witness Circuit

    _, _ = groth16.Prove(r1cs, pk, &witness)
}

The output of the above code is: (Please scroll right to see the other unexpected 1 bits set)

main.go:17 2
main.go:18 {0: 1, 1: 1, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0, 13: 0, 14: 0, 15: 0, 16: 0, 17: 0, 18: 0, 19: 0, 20: 0, 21: 0, 22: 0, 23: 0, 24: 0, 25: 0, 26: 0, 27: 0, 28: 1, 29: 1, 30: 1, 31: 1, 32: 1, 33: 1, 34: 0, 35: 0, 36: 1, 37: 0, 38: 0, 39: 1, 40: 1, 41: 0, 42: 1, 43: 0, 44: 1, 45: 1, 46: 1, 47: 1, 48: 1, 49: 0, 50: 0, 51: 0, 52: 0, 53: 1, 54: 1, 55: 1, 56: 1, 57: 1, 58: 0, 59: 0, 60: 0, 61: 0, 62: 1, 63: 0, 64: 1, 65: 0, 66: 0, 67: 0, 68: 1, 69: 0, 70: 0, 71: 1, 72: 0, 73: 0, 74: 0, 75: 0, 76: 1, 77: 1, 78: 1, 79: 0, 80: 1, 81: 0, 82: 0, 83: 1, 84: 1, 85: 1, 86: 0, 87: 1, 88: 1, 89: 0, 90: 0, 91: 1, 92: 1, 93: 1, 94: 1, 95: 0, 96: 0, 97: 0, 98: 0, 99: 1, 100: 0, 101: 0, 102: 1, 103: 0, 104: 0, 105: 0, 106: 0, 107: 1, 108: 0, 109: 1, 110: 1, 111: 1, 112: 1, 113: 1, 114: 0, 115: 0, 116: 1, 117: 1, 118: 0, 119: 0, 120: 0, 121: 0, 122: 0, 123: 1, 124: 0, 125: 1, 126: 0, 127: 0, 128: 1, 129: 0, 130: 1, 131: 1, 132: 1, 133: 0, 134: 1, 135: 0, 136: 0, 137: 0, 138: 0, 139: 1, 140: 1, 141: 0, 142: 1, 143: 0, 144: 1, 145: 0, 146: 0, 147: 0, 148: 0, 149: 0, 150: 0, 151: 1, 152: 1, 153: 0, 154: 0, 155: 0, 156: 0, 157: 0, 158: 0, 159: 1, 160: 0, 161: 1, 162: 1, 163: 0, 164: 1, 165: 1, 166: 0, 167: 1, 168: 1, 169: 0, 170: 1, 171: 0, 172: 0, 173: 0, 174: 1, 175: 0, 176: 0, 177: 0, 178: 0, 179: 0, 180: 1, 181: 0, 182: 1, 183: 0, 184: 0, 185: 0, 186: 0, 187: 1, 188: 1, 189: 1, 190: 0, 191: 1, 192: 1, 193: 0, 194: 0, 195: 1, 196: 0, 197: 1, 198: 0, 199: 0, 200: 0, 201: 0, 202: 0, 203: 0, 204: 0, 205: 1, 206: 0, 207: 1, 208: 1, 209: 0, 210: 0, 211: 0, 212: 1, 213: 1, 214: 0, 215: 0, 216: 1, 217: 0, 218: 0, 219: 0, 220: 0, 221: 1, 222: 1, 223: 1, 224: 0, 225: 1, 226: 0, 227: 0, 228: 1, 229: 1, 230: 1, 231: 0, 232: 0, 233: 1, 234: 1, 235: 1, 236: 0, 237: 0, 238: 1, 239: 0, 240: 0, 241: 0, 242: 1, 243: 0, 244: 0, 245: 1, 246: 1, 247: 0, 248: 0, 249: 0, 250: 0, 251: 0, 252: 1, 253: 1}
main.go:19 {0: 0, 1: 1, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0, 13: 0, 14: 0, 15: 0, 16: 0, 17: 0, 18: 0, 19: 0, 20: 0, 21: 0, 22: 0, 23: 0, 24: 0, 25: 0, 26: 0, 27: 0, 28: 0, 29: 0, 30: 0, 31: 0, 32: 0, 33: 0, 34: 0, 35: 0, 36: 0, 37: 0, 38: 0, 39: 0, 40: 0, 41: 0, 42: 0, 43: 0, 44: 0, 45: 0, 46: 0, 47: 0, 48: 0, 49: 0, 50: 0, 51: 0, 52: 0, 53: 0, 54: 0, 55: 0, 56: 0, 57: 0, 58: 0, 59: 0, 60: 0, 61: 0, 62: 0, 63: 0, 64: 0, 65: 0, 66: 0, 67: 0, 68: 0, 69: 0, 70: 0, 71: 0, 72: 0, 73: 0, 74: 0, 75: 0, 76: 0, 77: 0, 78: 0, 79: 0, 80: 0, 81: 0, 82: 0, 83: 0, 84: 0, 85: 0, 86: 0, 87: 0, 88: 0, 89: 0, 90: 0, 91: 0, 92: 0, 93: 0, 94: 0, 95: 0, 96: 0, 97: 0, 98: 0, 99: 0, 100: 0, 101: 0, 102: 0, 103: 0, 104: 0, 105: 0, 106: 0, 107: 0, 108: 0, 109: 0, 110: 0, 111: 0, 112: 0, 113: 0, 114: 0, 115: 0, 116: 0, 117: 0, 118: 0, 119: 0, 120: 0, 121: 0, 122: 0, 123: 0, 124: 0, 125: 0, 126: 0, 127: 0, 128: 0, 129: 0, 130: 0, 131: 0, 132: 0, 133: 0, 134: 0, 135: 0, 136: 0, 137: 0, 138: 0, 139: 0, 140: 0, 141: 0, 142: 0, 143: 0, 144: 0, 145: 0, 146: 0, 147: 0, 148: 0, 149: 0, 150: 0, 151: 0, 152: 0, 153: 0, 154: 0, 155: 0, 156: 0, 157: 0, 158: 0, 159: 0, 160: 0, 161: 0, 162: 0, 163: 0, 164: 0, 165: 0, 166: 0, 167: 0, 168: 0, 169: 0, 170: 0, 171: 0, 172: 0, 173: 0, 174: 0, 175: 0, 176: 0, 177: 0, 178: 0, 179: 0, 180: 0, 181: 0, 182: 0, 183: 0, 184: 0, 185: 0, 186: 0, 187: 0, 188: 0, 189: 0, 190: 0, 191: 0, 192: 0, 193: 0, 194: 0, 195: 0, 196: 0, 197: 0, 198: 0, 199: 0, 200: 0, 201: 0, 202: 0, 203: 0, 204: 0, 205: 0, 206: 0, 207: 0, 208: 0, 209: 0, 210: 0, 211: 0, 212: 0, 213: 0, 214: 0, 215: 0, 216: 0, 217: 0, 218: 0, 219: 0, 220: 0, 221: 0, 222: 0, 223: 0, 224: 0, 225: 0, 226: 0, 227: 0, 228: 0, 229: 0, 230: 0, 231: 0, 232: 0, 233: 0, 234: 0, 235: 0, 236: 0, 237: 0, 238: 0, 239: 0, 240: 0, 241: 0, 242: 0, 243: 0, 244: 0, 245: 0, 246: 0, 247: 0, 248: 0, 249: 0, 250: 0, 251: 0, 252: 0, 253: 0}

For some reason, when api.Select() takes the 1st option (i.e. the first argument is 1), any subsequent api.ToBinary() will result in weird outputs. However, when api.Select() takes the 2nd option, the subsequent api.ToBinary() calls are as expected.

My go.mod file looks like:

module github.com/vck3000/gnark_apiToBinaryInconsistency

go 1.17

require (
    github.com/consensys/gnark v0.5.2
    github.com/consensys/gnark-crypto v0.5.3
)

require (
    github.com/fxamacker/cbor/v2 v2.2.0 // indirect
    github.com/x448/float16 v0.8.4 // indirect
    golang.org/x/crypto v0.0.0-20210322153248-0c34fe9e7dc2 // indirect
    golang.org/x/sys v0.0.0-20210420205809-ac73e9fd8988 // indirect
)

Any ideas on what is causing this or how I could get around this?

ivokub commented 2 years ago

Thanks @vck3000 for the feedback.

I have traced the bug down to the way constraint system builder handles constants. The way select works is by computing (1-b) * x + b * y. If all of the inputs were constants, then no constraints are recorded in the constraint system and the value was computed directly. However the computed constant value was not reduced by the modulus of the scalars and the returned value corresponded to 2 + Fr (instead of just 2) and thus the binary decomposition was unexpected. In computations this shouldn't have made a difference as 2 + Fr == 2 (mod Fr).

I have proposed a fix for that and hopefully it lands soon in develop and then in v.0.5.3.

vck3000 commented 2 years ago

Hi @ivokub,

Thanks for the speedy reply, fix, and explanations. Appreciate your efforts!