Handling collisions by redundancy - Newton’s identities
$begingroup$
I am reading this paper (P2P Mixing and Unlinkable Bitcoin Transactions
by Tim Ruffing, Pedro Moreno-Sanchez and Aniket Kate) and I need help in understand something in Section III-A, Handling Collisions.
The scenario is about a situation in which n peers want to send their messages simultaneously over a network at the same time, but if they do so their messages collide (add up) which we don't want. The solution discussed here talks about handling collisions using redundancy and Newton Identities.
Please have a look at the specific part:
So far what I have understood is this:
All peers will send their messages and let them collide (add up). But they will do so multiple times (for each slot). Hence we will have sums of all peer's messages, raised to a power of the slot they were sent in.
What I don't understand:
How EXACTLY do we obtain the messages using these power sums? What's the polynomial g(x), do I find/create it? What are it's coefficients supposed to be? I am not interested in proof of Newton's Identities but how exactly "having knowledge of all coefficients of polynomial g" can I find it's roots which somehow are the messages?
My goal is to understand this part so I can write a program to implement this functionality. You must have guessed it right, I come from a non-mathematical background, so it'd be great if someone can help me using lay-men terms :)
BTW I have referred to the following, you may find it helpful:
- https://link.springer.com/content/pdf/10.1007/3-540-46885-4_33.pdf
- https://www.fq.math.ca/Issues/37-2.pdf
Thanks
field-theory roots
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
$endgroup$
add a comment |
$begingroup$
I am reading this paper (P2P Mixing and Unlinkable Bitcoin Transactions
by Tim Ruffing, Pedro Moreno-Sanchez and Aniket Kate) and I need help in understand something in Section III-A, Handling Collisions.
The scenario is about a situation in which n peers want to send their messages simultaneously over a network at the same time, but if they do so their messages collide (add up) which we don't want. The solution discussed here talks about handling collisions using redundancy and Newton Identities.
Please have a look at the specific part:
So far what I have understood is this:
All peers will send their messages and let them collide (add up). But they will do so multiple times (for each slot). Hence we will have sums of all peer's messages, raised to a power of the slot they were sent in.
What I don't understand:
How EXACTLY do we obtain the messages using these power sums? What's the polynomial g(x), do I find/create it? What are it's coefficients supposed to be? I am not interested in proof of Newton's Identities but how exactly "having knowledge of all coefficients of polynomial g" can I find it's roots which somehow are the messages?
My goal is to understand this part so I can write a program to implement this functionality. You must have guessed it right, I come from a non-mathematical background, so it'd be great if someone can help me using lay-men terms :)
BTW I have referred to the following, you may find it helpful:
- https://link.springer.com/content/pdf/10.1007/3-540-46885-4_33.pdf
- https://www.fq.math.ca/Issues/37-2.pdf
Thanks
field-theory roots
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
$endgroup$
$begingroup$
It'd be great if someone can help me tag this question more appropriately.
$endgroup$
– Vijay Chavda
Jan 2 at 14:35
add a comment |
$begingroup$
I am reading this paper (P2P Mixing and Unlinkable Bitcoin Transactions
by Tim Ruffing, Pedro Moreno-Sanchez and Aniket Kate) and I need help in understand something in Section III-A, Handling Collisions.
The scenario is about a situation in which n peers want to send their messages simultaneously over a network at the same time, but if they do so their messages collide (add up) which we don't want. The solution discussed here talks about handling collisions using redundancy and Newton Identities.
Please have a look at the specific part:
So far what I have understood is this:
All peers will send their messages and let them collide (add up). But they will do so multiple times (for each slot). Hence we will have sums of all peer's messages, raised to a power of the slot they were sent in.
What I don't understand:
How EXACTLY do we obtain the messages using these power sums? What's the polynomial g(x), do I find/create it? What are it's coefficients supposed to be? I am not interested in proof of Newton's Identities but how exactly "having knowledge of all coefficients of polynomial g" can I find it's roots which somehow are the messages?
My goal is to understand this part so I can write a program to implement this functionality. You must have guessed it right, I come from a non-mathematical background, so it'd be great if someone can help me using lay-men terms :)
BTW I have referred to the following, you may find it helpful:
- https://link.springer.com/content/pdf/10.1007/3-540-46885-4_33.pdf
- https://www.fq.math.ca/Issues/37-2.pdf
Thanks
field-theory roots
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
$endgroup$
I am reading this paper (P2P Mixing and Unlinkable Bitcoin Transactions
by Tim Ruffing, Pedro Moreno-Sanchez and Aniket Kate) and I need help in understand something in Section III-A, Handling Collisions.
The scenario is about a situation in which n peers want to send their messages simultaneously over a network at the same time, but if they do so their messages collide (add up) which we don't want. The solution discussed here talks about handling collisions using redundancy and Newton Identities.
Please have a look at the specific part:
So far what I have understood is this:
All peers will send their messages and let them collide (add up). But they will do so multiple times (for each slot). Hence we will have sums of all peer's messages, raised to a power of the slot they were sent in.
What I don't understand:
How EXACTLY do we obtain the messages using these power sums? What's the polynomial g(x), do I find/create it? What are it's coefficients supposed to be? I am not interested in proof of Newton's Identities but how exactly "having knowledge of all coefficients of polynomial g" can I find it's roots which somehow are the messages?
My goal is to understand this part so I can write a program to implement this functionality. You must have guessed it right, I come from a non-mathematical background, so it'd be great if someone can help me using lay-men terms :)
BTW I have referred to the following, you may find it helpful:
- https://link.springer.com/content/pdf/10.1007/3-540-46885-4_33.pdf
- https://www.fq.math.ca/Issues/37-2.pdf
Thanks
field-theory roots
field-theory roots
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
asked Jan 2 at 14:34
Vijay ChavdaVijay Chavda
1036
1036
$begingroup$
It'd be great if someone can help me tag this question more appropriately.
$endgroup$
– Vijay Chavda
Jan 2 at 14:35
add a comment |
$begingroup$
It'd be great if someone can help me tag this question more appropriately.
$endgroup$
– Vijay Chavda
Jan 2 at 14:35
$begingroup$
It'd be great if someone can help me tag this question more appropriately.
$endgroup$
– Vijay Chavda
Jan 2 at 14:35
$begingroup$
It'd be great if someone can help me tag this question more appropriately.
$endgroup$
– Vijay Chavda
Jan 2 at 14:35
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3059533%2fhandling-collisions-by-redundancy-newton-s-identities%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3059533%2fhandling-collisions-by-redundancy-newton-s-identities%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
It'd be great if someone can help me tag this question more appropriately.
$endgroup$
– Vijay Chavda
Jan 2 at 14:35