{"action":"created","issue":{"url":"https://api.github.com/repos/HarryR/ethsnarks/issues/73","repository_url":"https://api.github.com/repos/HarryR/ethsnarks","labels_url":"https://api.github.com/repos/HarryR/ethsnarks/issues/73/labels{/name}","comments_url":"https://api.github.com/repos/HarryR/ethsnarks/issues/73/comments","events_url":"https://api.github.com/repos/HarryR/ethsnarks/issues/73/events","html_url":"https://github.com/HarryR/ethsnarks/issues/73","id":378100492,"node_id":"MDU6SXNzdWUzNzgxMDA0OTI=","number":73,"title":"Implement Jarvis and Friday","user":{"login":"HarryR","id":303926,"node_id":"MDQ6VXNlcjMwMzkyNg==","avatar_url":"https://avatars3.githubusercontent.com/u/303926?v=4","gravatar_id":"","url":"https://api.github.com/users/HarryR","html_url":"https://github.com/HarryR","followers_url":"https://api.github.com/users/HarryR/followers","following_url":"https://api.github.com/users/HarryR/following{/other_user}","gists_url":"https://api.github.com/users/HarryR/gists{/gist_id}","starred_url":"https://api.github.com/users/HarryR/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/HarryR/subscriptions","organizations_url":"https://api.github.com/users/HarryR/orgs","repos_url":"https://api.github.com/users/HarryR/repos","events_url":"https://api.github.com/users/HarryR/events{/privacy}","received_events_url":"https://api.github.com/users/HarryR/received_events","type":"User","site_admin":false},"labels":[{"id":991949843,"node_id":"MDU6TGFiZWw5OTE5NDk4NDM=","url":"https://api.github.com/repos/HarryR/ethsnarks/labels/enhancement","name":"enhancement","color":"a2eeef","default":true},{"id":991949844,"node_id":"MDU6TGFiZWw5OTE5NDk4NDQ=","url":"https://api.github.com/repos/HarryR/ethsnarks/labels/help%20wanted","name":"help wanted","color":"008672","default":true}],"state":"open","locked":false,"assignee":{"login":"HarryR","id":303926,"node_id":"MDQ6VXNlcjMwMzkyNg==","avatar_url":"https://avatars3.githubusercontent.com/u/303926?v=4","gravatar_id":"","url":"https://api.github.com/users/HarryR","html_url":"https://github.com/HarryR","followers_url":"https://api.github.com/users/HarryR/followers","following_url":"https://api.github.com/users/HarryR/following{/other_user}","gists_url":"https://api.github.com/users/HarryR/gists{/gist_id}","starred_url":"https://api.github.com/users/HarryR/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/HarryR/subscriptions","organizations_url":"https://api.github.com/users/HarryR/orgs","repos_url":"https://api.github.com/users/HarryR/repos","events_url":"https://api.github.com/users/HarryR/events{/privacy}","received_events_url":"https://api.github.com/users/HarryR/received_events","type":"User","site_admin":false},"assignees":[{"login":"HarryR","id":303926,"node_id":"MDQ6VXNlcjMwMzkyNg==","avatar_url":"https://avatars3.githubusercontent.com/u/303926?v=4","gravatar_id":"","url":"https://api.github.com/users/HarryR","html_url":"https://github.com/HarryR","followers_url":"https://api.github.com/users/HarryR/followers","following_url":"https://api.github.com/users/HarryR/following{/other_user}","gists_url":"https://api.github.com/users/HarryR/gists{/gist_id}","starred_url":"https://api.github.com/users/HarryR/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/HarryR/subscriptions","organizations_url":"https://api.github.com/users/HarryR/orgs","repos_url":"https://api.github.com/users/HarryR/repos","events_url":"https://api.github.com/users/HarryR/events{/privacy}","received_events_url":"https://api.github.com/users/HarryR/received_events","type":"User","site_admin":false}],"milestone":null,"comments":11,"created_at":"2018-11-07T01:12:09Z","updated_at":"2018-11-24T12:35:19Z","closed_at":null,"author_association":"OWNER","body":"From:\r\n * https://www.esat.kuleuven.be/cosic/jarvis-and-friday-stark-friendly-cryptographic-primitives/\r\n * https://eprint.iacr.org/2018/1098.pdf\r\n\r\nThis ticket includes the following sub-tasks:\r\n\r\n * [ ] Analyse MiMC, Jarvis & Friday papers\r\n * [ ] Verify if the Python pseudocode below implements it faithfully\r\n * [ ] Wait for further analysis from somebody qualified to analyse security, or further papers\r\n * [ ] Implement Python version of Jarvis and Friday, add unit tests\r\n * [ ] Implement libsnark circuit which matches Python implementation\r\n * [ ] Implement Solidity functions which match Python and libsnark implementations\r\n\r\nJarvis is an improvement upon MiMC, it hopefully attains the same level of security in a way which costs much less to verify in a zkSNARK circuit.\r\n\r\nMiMC-p/p (sometimes called LongsightL) is has been implemented and included in Ethsnarks in combination with the Preneel one-way compression function:\r\n\r\n * https://github.com/HarryR/ethsnarks/blob/master/ethsnarks/longsight.py\r\n * https://github.com/HarryR/ethsnarks/blob/master/src/gadgets/onewayfunction.hpp\r\n * https://github.com/HarryR/ethsnarks/blob/master/src/gadgets/longsightl.cpp\r\n * https://github.com/HarryR/ethsnarks/blob/master/contracts/LongsightL.sol\r\n\r\nThis allows for very cheap merkle-trees and hashing, in a way which is 'field-native' - that is, it uses field elements rather than bits to achieve hashing and encryption of many bits per operation rather than many operations per bit.\r\n\r\nHowever, it would be good to implement Jarvis as an alternative to LongsightL and MiMC-p/p, as this could reduce the number of constraints required for large Merkle trees, and significantly proving time.\r\n\r\nThe difference between MiMC and Jarvis is that the modulo inverse is used to increase the degree of the polynomial to excessive numbers, rather than relying on a specified number of rounds to increase the degree to an acceptable number.\r\n\r\nThe Preneel one-way compression function is already implemented, and used in conjunction with MiMC in a very similar manner to Jarvis and Friday, however Jarvis is more complex to compute on EVM (requiring modulo inverse at every round via the `modexp` instruction), but relatively simple to verify (in the same way that constraints are verified).\r\n\r\nThe following are my notes on a possible implementation:\r\n\r\n> Making all these changes, the Jarvis round function becomes:\r\n<img src=\"https://www.esat.kuleuven.be/cosic/wp-content/uploads/2018/10/JarvisL0round-1.jpg.png\" />\r\n\r\n> Where the key expansion function is:\r\n<img src=\"https://www.esat.kuleuven.be/cosic/wp-content/uploads/2018/10/JarvisL0key-1.jpg.png\" />\r\n\r\nThe key derivation function being:\r\n\r\n```python\r\ndef jarvis_keys(k, c):\r\n    # key is master key\r\n    # c is list of round constants\r\n    for c_i in c:\r\n        k = (1/k) + c_i\r\n        yield k  # emit sequence of derived keys\r\n```\r\n\r\nThe Jarvis function would be:\r\n\r\n```python\r\ndef jarvis(k, m, c):\r\n    # m is a message\r\n    # k is master key\r\n    # c is list of round constants, length is the number of rounds\r\n    s_i = m + k\r\n    for k_i in jarvis_keys(k, c):\r\n        s_i = (1/s_i) + k_i\r\n    return s_i\r\n```\r\n\r\nThe Friday function is\r\n```python\r\ndef friday(k, messages, c):\r\n    for m in messages:\r\n        k = k + m + jarvis(k, m, c)\r\n    return k\r\n```\r\n\r\nWithout accounting for `x = 0`, this can be enforced with one constraint per round:\r\n\r\n```python\r\na = s_i\r\nb = 1/a + k_i\r\nassert (a * (b - k_i)) == 1\r\n```\r\n\r\nWhile accounting for `x=0` and `x!=0`, this can be enforced with 3 constraints per round:\r\n\r\n```python\r\n# r = f(x); uses linear combination to add round key?\r\nassert (1 - b) * b == 0\r\nassert (1 - b) * x == 0\r\nassert r * (x + b - 1) == b\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/HarryR/ethsnarks/issues/comments/441364928","html_url":"https://github.com/HarryR/ethsnarks/issues/73#issuecomment-441364928","issue_url":"https://api.github.com/repos/HarryR/ethsnarks/issues/73","id":441364928,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0MTM2NDkyOA==","user":{"login":"daira","id":643204,"node_id":"MDQ6VXNlcjY0MzIwNA==","avatar_url":"https://avatars2.githubusercontent.com/u/643204?v=4","gravatar_id":"","url":"https://api.github.com/users/daira","html_url":"https://github.com/daira","followers_url":"https://api.github.com/users/daira/followers","following_url":"https://api.github.com/users/daira/following{/other_user}","gists_url":"https://api.github.com/users/daira/gists{/gist_id}","starred_url":"https://api.github.com/users/daira/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/daira/subscriptions","organizations_url":"https://api.github.com/users/daira/orgs","repos_url":"https://api.github.com/users/daira/repos","events_url":"https://api.github.com/users/daira/events{/privacy}","received_events_url":"https://api.github.com/users/daira/received_events","type":"User","site_admin":false},"created_at":"2018-11-24T12:35:19Z","updated_at":"2018-11-24T12:35:19Z","author_association":"NONE","body":"I wrote:\r\n> However, if for the sake of argument we were going to use f such that f(0) = 0 and f(x) = 1/x when x ≠ 0 as a nonlinear function over F<sub>p</sub>, this would be how to implement r = f(x) in 3 R1CS constraints:\r\n> [...]\r\n> I conjecture that this is not possible in fewer than 3 constraints, if x = 0 needs to be handled correctly. Note that if you can guarantee that the case x ≠ 0 never occurs, then 1 constraint suffices.\r\n\r\nIn practical applications it might be permissible for the hash function or cipher to fail deterministically on a small proportion of possible inputs &mdash; provided that its R1CS implementation results in an unsatisfiable constraint system for those inputs. Call such a hash or cipher, if it fails for a proportion of inputs that is negligible in the security parameter, \"not quite total\".\r\n\r\nFor instance, the Merkle tree over commitments in Zcash is completely public. Whether a given commitment causes a failure in the computation of the new root will depend on the position at which it is added to the tree. We can tolerate a small probability of hash failure, by making it a consensus rule that no commitment is added at a position where it causes such a failure. This does not significantly increase the feasibility of finding non-failing collisions.\r\n\r\nSuppose that the probability that a given inversion fails is at most ε, and the number of inversions in the hash is k. By the [Fréchet inequality](https://en.wikipedia.org/wiki/Fr%C3%A9chet_inequalities) for disjunctions, the probability that any inversion fails for random input is at most k·ε. If there are d layers in the Merkle tree, then the probability of failure for adding a random commitment at a random position in the tree is at most d·k·ε. If this is small then heuristically, even if adding a commitment fails, it will be possible to add it in another position soon afterward.\r\n\r\n(The probabilities of failure at different positions in the tree cannot in general be assumed to be independent. In principle, it could be the case that a tree gets \"stuck\", unable to add new commitments, or unable to add a given commitment at *any* subsequent position. However, this will not occur in practice for a Miyaguchi–Preneel hash constructed from a random not-quite-total cipher used in a binary Merkle tree, where the left input to the Merkle hash at each layer occupies the first block, and the right input occupies the second block. Informally, that is because we alternate whether the commitment to be added is in the left or right input; and in Miyaguchi–Preneel the key for the second block gets randomized by the chaining value output from the first block. Other combinations of hash and tree constructions are likely to also avoid this potential problem, although each needs a specific analysis.)\r\n\r\nThe analysis for not-quite-total ciphers or keyed hashes is different. We need to assume that any failure of the encryption or decryption functions could act as an oracle for the adversary. In general this needs a protocol-specific analysis. On the other hand, if keys are independent and uniform-random, then the probability of a given encryption or decryption failing should be very small; so it seems plausible that using a not-quite-total cipher could be acceptable for protocols where the performance gain justifies the additional complexity of analysis."}}
{"actor":{"display_login":"daira"}}